НАЦІОНАЛЬНИЙ ТЕХНІЧНИЙ УНІВЕРСИТЕТ УКРАЇНИ
«КИЇВСЬКИЙ ПОЛІТЕХНІЧНИЙ ІНСТИТУТ»
Курсова робота
На тему:
Використання генетичних алгоритмів в САПР ТП
факультет: Приладобудівний
кафедра: Виробництва приладів
Київ – 2009
План
Вступ
1. Класифікація інформаційних технологічних систем
2. Задачі технологічної підготовки виробництва, що розв’язуються за допомогою математичного моделювання
3. Аналіз інформаційних зв’язків в технологічних системах виготовлення деталей та складання приладів
4. Моделювання процесів з використанням методів лінійного і нелінійного програмування
5. Перспективи використання генетичних алгоритмів в САПР ТП
5.1 Теоретична частина
5.2 Застосування генетичних алгоритмів
5.3 Проблеми при використанні генетичних алгоритмів
Висновки
Summary
Список використаних джерел
Вступ
Інформаційні системи на базі сучасних комп’ютерів, оснащених відповідним програмним забезпеченням, відіграють важливу роль в організації, керуванні та плануванні виробництва, і технологічних процесів в ньому.
Застосування комп’ютерів при рішенні задач технологічного проектування дозволяє оперувати досить складними схемами і формулами, проте інколи, із-за недостатньої формалізації завдань, ці залежності неадекватні реальним виробничим процесам. В зв'язку з цим, одним з методів оцінки рішень і вибору оптимального рішення є моделювання. При моделюванні рішень широко використовують методи математичного та імітаційного моделювання. Для цього створюються спеціальні засоби. Методи математичного та імітаційного моделювання зазвичай реалізуються на комп’ютерах.
Виробнича система, як і більшість систем, являє собою сукупність підсистеми, що керується (об’єкт управління), та керованої підсистеми (суб’єкта управління, який має у своєму розпорядженні відповідні механізми управління). В системі управління формування управляючої дії здійснюється на базі прийняття управлінського рішення. Тому управління можна представити як процес підготовки, прийняття та реалізації рішень, що спрямовані на досягнення цілей, які були поставлені. Технологічний процес повинен здійснюватися на базі принципів системного підходу, тому що він являє собою сукупність багатьох взаємопов’язаних процесів.
Таким чином ефективне розв’язання задач технологічного проектування виробництва можливе при наявності адекватних математичних та імітаційних моделей параметрів і показників технологічних процесів виготовлення виробів приладобудування.
Коли управляюча підсистема належить виробничій системі, управління її діяльністю та розвитком здійснюється у замкненому контурі за допомогою зворотного зв’язку виходу системи (результатів діяльності) із входом до неї (факторами діяльності, у тому числі, факторами виробництва). Наявність зворотного зв’язку забезпечує вплив на виробничі фактори за рахунок власних ресурсів, завдяки чому й досягається самоорганізація виробничої системи.
1. Класифікація інформаційних технологічних систем
На основі опублікованих джерел [3], можна сказати, що ефективність для виробництва своєчасно отриманої інформації у 3 рази вища від ефективності освіти для цієї ж сфери діяльності, у 6 разів – від темпів розвитку науково-технічного прогресу, у 12 разів – від вкладеного капіталу, та у 18-25 разів – від нерухомості.
Для розв’язку проблем, які пов’язані з інформаційним забезпеченням технологічних процесів, сьогодні використовуються автоматичні системи управління технологічними процесами (АСУТП) типу SCADA (Supervisory Control and Data Acquisition) або DCS (Distributed Control Systems). Обидва вказаних типи систем належать класу MMI (Man-Machine Interface), що означає „людино-машинний інтерфейс” у контексті забезпечення двобічного зв’язку „оператор - технологічне обладнання”.
Проте головну увагу слід звернути на САПР (системи автоматизованого проектування), без яких не може обійтися жодне промислове підприємство, чия продукція потребує конструкторської та технологічної документації. Сучасні технології САПР для підприємств представлені системами CAD/CAM/CAE/PDM (Сomputer Aided Design, Manufacturing, Engineering, Product Data Management). Ці системи дозволяють обійтися без „паперової” документації, здійснюючи прямий зв’язок між процесами розробки виробу та його виробництвом, що дозволяє підвищити якість продукції та скоротити час розробки.
Поволі між ММІ та ERP утворилася проміжна група систем, що зветься MES (Manufacturing Execution Systems). Вона виникла внаслідок відокремлення задач, що не відносяться до жодної з раніше визначених груп. До системи MES прийнято відносити додатки, що відповідають:
·за управління виробничими та людськими резервами у межах технологічного процесу;
·планування та контроль послідовності операцій технологічного процесу;
·керування якістю продукції;
·зберігання вихідних матеріалів та виробничої продукції по технологічних підрозділах;
·технічне обслуговування виробничого обладнання;
·зв’язок систем ERP та SCADA/DCS.
Одна з причин виникнення таких систем – спроба виділити задачі управління виробництвом на рівні технологічного підрозділу. Але дуже швидко були виявлені недоліки розділення задач планування та управління виробництвом на два рівня. Досвід показав, що інформаційна база цих задач повинна бути єдиною.
Інший шлях виникнення систем MES – знизу, від АСУТП. Так здійснилося відділення тактичних задач оперативного управління технологічними процесами від стратегічних задач ведення процесу у цілому. Так, зокрема, у хімічній, металургійній, харчовій та деяких інших галузях промисловості можна виділити задачі управління технологічними послідовностями (batch control). Їх суть – забезпечення випуску продукції у потрібному об’ємі із заданими технологічними характеристиками за наявністю можливого переходу на новий вид продукції. Були відокремлені також й задачі ведення архіву значень технологічних змінних з можливістю відновлення виробничих ситуацій попередніх періодів та аналізу нештатних ситуацій. З’явилися програми навчання технологічного персоналу та оптимізація ведення технологічних процесів.
Аналіз існуючих в даний час на підприємствах України автоматизованих інформаційних систем свідчить про їх незначну кількість та велику застарілість. Вони, з різних причин, обмежують розвиток технології виробництв, особливо якщо це стосується таких виробництв, які характеризуються високими технологіями, а саме підприємств приладобудівного профілю. Тому нагальною потребою є створення автоматизованих систем збирання, обробки технологічної інформації та проектування технології виробництва, особливо для приладобудівної галузі.
Широкий спектр задач, що вирішується технологами, пред’являє високі вимоги до таких систем. Відомі складності останніх років призвели до того, що на підприємствах приладобудівного профілю залишилися фахівці з великим досвідом та знаннями виробництва, але без достатніх навичок роботи на персональних комп’ютерах, а поповнення технологічних кадрів випускниками вузів виявилося явно недостатнім. Тому вимоги, що ставляться до розроблюваних систем такого роду, повинні бути такими, щоб системі були притаманні:
· простота освоєння;
· розвинені функціональні можливості;
· зручність у роботі;
· гнучкість у надбудові.
Все це дозволить розробленій автоматизованій системі зайняти достойне місце в приладобудівному виробництві, а також дасть можливість не тільки забезпечити технологічний цикл всім необхідним для його нормального функціонування, але й надасть змогу виробництву до саморозвитку, удосконалення та опанування нових технологічних розробок.
2. Задачі технологічної підготовки виробництва, що розв’язуються за допомогою математичного моделювання
Автоматизація виробництва вимагає інтеграції і автоматизації всіх робіт з технологічної підготовки виробництва (ТПВ). Інтеграція конструкторської, технологічної, організаційної і економічної підготовки виробництва полягає в забезпеченні достовірних своєчасних прямих і зворотних зв'язків між завданнями в цілях вибору оптимальних рішень на всіх етапах підготовки виробництва. Забезпечити безперервний ефективний зв'язок між завданнями зазвичай можливо лише в умовах автоматизації підготовки виробництва на основі єдиної інформаційної бази, яка включає постійну (нормативно-довідкову) і змінну інформацію, що формується в процесі рішення задачі.
Але, не дивлячись на інтеграцію робіт, в підготовці виробництва можна виділити два самостійні види робіт, що відрізняються за складом і метою:
1. проектування або реорганізація виробництва (пряме завдання) (рис. 1);
2. експлуатація організованого виробництва (обернена задача проектування) (рис. 2).
Рис. 1. Прямі завдання проектування
Рис. 2. Обернені завдання проектування
Метою проектування виробництва є побудова виробничої системи і створення таких умов, які забезпечували б протягом тривалого часу виготовлення запланованих і прогнозованих виробів в заданий термін, і з мінімальними затратами. При проектуванні багатономенклатурної виробничої системи формується одна з найважливіших їх властивостей виробництва – його перенастроюваність (гнучкість). Метою сучасного виробництва є максимальне використання технічного рівня виробничої системи при виготовленні запланованих виробів. Це припускає максимізацію термінів проектування і виготовлення виробів при мінімальних витратах на ТПВ.
Інтеграція двох видів робіт при сумісному їх розгляді полягає в створенні, при проектуванні виробництва, технічної, організаційної і інформаційної баз, на основі яких приймаються рішення при експлуатації виробництва і досягається необхідна гнучкість виробничої системи.
В наведених схемах (рис. 1, 2) передбачені оцінки рішень і вибір ефективних рішень, для чого організовуються складні образні зв'язки (на схемах вказані не всі). У схемі проектування виробничої системи оптимізація проводиться при уніфікації, а також при проектуванні технологічного оснащення і виробничих підрозділів. При рішенні задач уніфікації визначається оптимальний склад уніфікованих виробів. При проектуванні групових операційних технологічних процесів (ТП) оптимізуються план обробки, склад інструментальних переходів, поєднання в обробці, при проектуванні технологічного оснащення – склад комплектів базових поверхонь і маршрутних ТП, при проектуванні виробничих підрозділів – маршрутний ТП, склад допоміжного, транспортно-накопичувального і складського устаткування, розміщення устаткування. У схемі (рис. 2) оптимізація виконується в процесі проектування ТП і формування плану-графіка при оперативному управлінні виробничими підрозділами. Очевидно, для розробки оптимальних варіантів робочих ТП необхідно допустити, щоб деяка сукупність деталей могла бути віднесена не до однієї, а до декількох груп. За рахунок такого „перетину” груп спрощується вибір оптимального варіанту ТП і плану-графіка виконання робіт.
Оцінка і порівняння варіантів рішення в обох схемах може проводитися по логічних і аналітичних залежностях. Застосування ЕОМ при рішенні задач ТПВ дозволяє оперувати при оцінці досить складними схемами і формулами, але часто із-за недостатньої формалізації завдань ці залежності неадекватні реальним виробничим процесам. У зв'язку з цим основним методом оцінки рішень і вибору оптимального рішення є моделювання. При моделюванні рішень в даний час широко застосовують методи математичного та імітаційного моделювання. Для цього створюються спеціальні засоби. Методи математичного та імітаційного моделювання реалізуються на ЕОМ.
До моделювання рішень вдаються в обох схемах (рис. 1, 2). Але в схемі проектування виробництва моделювання і вибір оптимального рішення проводять на основі довгострокового прогнозу розвитку виробів і технології, а в схемі експлуатації виробництва використовують реальні схеми організації технологічних процесів, устаткування, інструменти, пристосування і т.д. У зв'язку з цим в схемі проектування особливу увагу слід приділяти роботам по коротко- і довгостроковому прогнозуванню розвитку технології, виробів, устаткування.
Таким чином ефективне розв’язання задач ТПВ можливе при наявності адекватних математичних та імітаційних моделей параметрів і показників технологічних процесів виготовлення виробів приладобудування.
3. Аналіз інформаційних зв’язків в технологічних системах виготовлення деталей та складання приладів
Основна задача системи інформації підприємства полягає у максимальному задоволенні потреб підприємства в інформації, що необхідна для його безвідмовного функціонування. Це відноситься до всіх господарчих одиниць підприємства і відповідних підсистем їх інформації. Таким чином, про задовільну систему інформації підприємства можна казати лише у тому випадку, якщо ця система є комплексною, приймаючи до уваги як структуру організації, так і характер та зміст самої інформації.
При розробці загальної системи інформації підприємства необхідно враховувати два фактори [4]: по-перше, у відповідності з двома основними видами інформації – економічною та технічною – на підприємстві повинні бути створені дві специфічні підсистеми інформації – економічна і технічна; по-друге, кожна окрема господарська одиниця підприємства у процесі своєї діяльності повинна користуватися як економічною, так і технічною інформацією.
Таким чином, структура систем інформації підприємства відповідає його організаційній структурі, а інформаційна діяльність підприємства нерозривно пов’язана з його господарчою діяльністю. З усього сказаного випливає, що розробка та удосконалення системи інформації не можуть виконуватися тільки шляхом простих організаційних змін, а лише завдяки забезпеченню комплексних зв’язків між системою інформації та управлінським, оперативним і контролюючим відділами підприємства, а також його виробничим сектором.
Управління виробничим процесом займає центральне місце в системі керування підприємством та в системі його інформації. У той же час при плануванні процесу управління виробництвом і в ході його здійснення виникає ряд спірних питань, пов’язаних з тим, що вимоги, які пред’являються до виробничого процесу, є надзвичайно широкими.
Система інформаційних зв’язків в технологічних процесах відіграє одну з найважливіших ролей у виробництві. Це стосується як конвеєрного засобу виробництва, так і інших форм виробничого процесу.
Зупинимося детально на аналізі деяких видів технологічних процесів та необхідності їх інформаційного забезпечення, яке може бути побудованим як на традиційній системі обліку руху матеріальних потоків та супроводжувальної технологічної документації, так і з застосуванням сучасних методів інформаційного забезпечення на базі обчислювальної техніки.
Майже усі виробництва, у тому числі й приладобудівне, мають справу з власним виготовленням деяких деталей та вузлів з матеріалів та сировини, а також з напівфабрикатів або комплектуючих. В цьому виробництві використовуються потужності механічних цехів. Механічні цехи різних виробництв мають як традиційне обладнання, так і станки та установки з числовим програмним керуванням (ЧПК), які входять до складу обладнання цеху як окремі одиниці, так і у складі технологічних ліній. В обох цих випадках комплектації обладнання цеху установками або станками виникає потреба в інформаційному забезпеченні їх роботи відповідними програмами, за якими здійснюється технологічний процес з виготовлення деталей.
При цьому послідовність операцій технологічного процесу в такому підрозділі загального виробництва виглядає таким чином:
- надходження програмного забезпечення для виготовлення деталей певного виду;
- надходження сировини, матеріалів або напівфабрикатів для виготовлення цих деталей, його облік в автоматизованій інформаційній системі поетапного супроводження всього заводського виробничого циклу;
- встановлення (інсталяція) цього програмного забезпечення в обладнання та тестові виготовлення виробів за допомогою цих програмних пакетів;
- серійне (потокове) виготовлення деталей на обладнанні з ЧПК та проведення контролю параметрів технологічного процесу;
- вибірковий контроль якості виготовлених деталей із застосуванням автоматизованих методів технічного тестування;
- облік результатів виготовлення продукції на цьому етапі технологічного процесу та передача відповідних даних про проходження продукції на наступний етап виробничого процесу.
Процес виготовлення або деяких вузлів чи агрегатів продукції, або загальної збірки готового виробу може здійснюватися конвеєрним або звичайним засобами. При цьому послідовність операцій технологічного процесу в такому підрозділі загального виробництва виглядає таким чином:
- надходження програмного забезпечення для виконання технологічних операцій в умовах автоматизованого обладнання складального виробництва (наприклад, автоматизована система компанії Philips для збирання друкованих плат на базі товстошарової клеєної технології; автомати чи напівавтомати технології мікрозварки тощо);
- надходження комплектуючих, напівфабрикатів або вузлів для виготовлення цих агрегатів, блоків чи готових виробів; облік продукції, що надходить, в автоматизованій інформаційній системі по-етапного супроводження всього заводського виробничого циклу;
- встановлення (інсталяція) цього програмного забезпечення в обладнання та тестові виготовлення виробів за допомогою цих програмних пакетів;
- серійне (потокове) виготовлення деталей на автоматизованому чи працюючому в ручному режимі керування обладнанні та проведення контролю параметрів технологічного процесу;
- вибірковий, на базі методів статистичного аналізу, контроль якості виготовлених вузлів, агрегатів або готових виробів із застосуванням автоматизованих методів технічного тестування;
- облік результатів виготовлення продукції на цьому етапі технологічного процесу та передача відповідних даних про проходження продукції на наступний етап виробничого процесу, склад готової продукції та до АСУ виробництвом.
Управління виробничим процесом будується у відповідності з річним планом підприємства, якій ділиться на місячні завдання. Місячний
план-завдання (програма) містить інформацію про об’єм та асортимент накресленого випуску окремих видів продукції, про терміни і виробничі витрати.
Для визначення термінів випуску продукції необхідно мати інформацію про:
- робочий час, необхідний для виробництва продукції на окремих виробничих одиницях та агрегатах і машинах та який розраховується на основі норм витрат часу;
- тривалість і фази повного виробничого циклу;
- виробничі потужності;
- фондомісткість та потреби в інструментах для виконання виробничої програми;
- наявний парк машин і стан машинного обладнання і т.д.
Служба керування виробництвом (диспетчерська служба) повинна мати правильно розроблену та побудовану інформаційну систему, тому що це необхідно для безперебійного здійснення процесу виробництва. Диспетчерська служба
В системі управління виробничим процесом диспетчерська служба займає центральне місце і виступає у ролі оперативного інформаційного центру, куди надходить інформація про виробництво і пов’язані з ним проблеми. Диспетчерська служба цю інформацію групує та своєчасно передає органам, що приймають рішення. Управління виробничим процесом на заводах має у своєму розпорядженні у більшості випадків добре розроблену мережу диспетчерської служби. У центральної диспетчерської служби є цехові диспетчерські служби, у функцію яких входить отримання та передача інформації.
Однією з найважливіших умов ефективного керівництва виробничим процесом є обробка даних, що забезпечує отримання інформації у необхідному об’ємі та потрібної якості.
Для того, щоб виробництво могло враховувати всі тонкощі технологічного процесу, необхідно максимально механізувати обробку даних, використовуючи при цьому комп’ютерну техніку.
У процесі керівництва виробничим процесом постійно приходиться вивчати зворотні зв’язки, оскільки вони характеризуються системою взаємопов’язаних та взаємозалежних задач. Тому організацію та управління виробництвом доцільно розглядати як кібернетичну систему, що має свої особливості у приладобудівному виробництві [4].
Слід зауважити, що серед факторів виробництва надзвичайно важливе значення мають робоча сила та виробничі потужності, тому отримання інформації, що відноситься до них, вельми необхідно.
Інформація, що відноситься до наявності робочої сили, повинна бути різнобічною. Потреба у робочій силі, співвідношення жіночої та чоловічої праці, кваліфікованої, навченої або ненавченої робочої сили визначаються характером виробничого процесу, його технології. Характер виробництва висуває до працівника підвищені вимоги, які в умовах серійного виробництва зводяться до здатності працюючих здійснювати технологічний процес з використанням монотонної та важкої фізичної праці. Робота персоналу виробництва в умовах граничного напруження не може не впливати на якість
технологічних операцій, які виконують у процесі виробництва працюючі, та забезпечення стабільності якості промислової продукції.
Проведений аналіз інформаційних зв’язків в технологічних схемах промислових виробництв дозволяє переходити до подальших кроків у дослідженні технологічних систем у приладобудуванні.
4. Моделювання процесів з використанням методів лінійного і нелінійного програмування
Дану групу методів ще називають методами оптимального планування. 3 цієї назви і випливає їхня суть. Вона полягає в тому, що дослідник (аналітик) намагається досягти максимально корисного за складеним ним критерієм ефективності використання ресурсів при заданих обмеженнях на ці ресурси.
Цільовою функцією, як правило, бувають вимога максимізації або мінімізації. Обмеженнями моделей даного класу є символьне (у вигляді функцій) представлення обмеженості ресурсів.
Критерієм оптимальності розв'язку задач даного типу є максимум (мінімум) цільової функції на множині припустимих розв’язків
моделі – множині утвореної обмеженнями моделі.
З математичної точки зору, основна ідея, застосування методів даного класу, полягає у знаходженні оптимального поєднання ресурсів множинні припустимих планів. В залежності від форми цільової функції та вигляду обмежень методи поділяються на задачі лінійного та нелінійного програмування.
В задачі лінійного програмування цільова функція та обмеження лінійні. Множина допустимих рішень, в такому випадку – це опуклий многогранник. І задача оптимізації зводиться до перебору всіх крайніх точок даного многогранника.
В іншому випадку, якщо цільова функція або обмеження набувають нелінійного характеру, для знаходження оптимального розв'язку використовується принцип опуклості (увігнутості) задачі нелінійного програмування, яке гарантує досягнення глобального оптимуму на множині припустимих рішень.
Недоліки цього класу моделей очевидні.
1. Необхідність мати достатньо обмежень для утворення множини припустимих рішень. У випадку незадоволення даної вимога множина рішень стає необмеженою і зникає гарантія отримання оптимального рішення. Дуже часто, отримані розв'язки не мають економічного обґрунтування.
2. Необхідність мати чітко сформульовану цільову функцію – критерій якості отриманого розв'язку. Дуже часто його важко побудувати. До того ж існує небезпека, що побудована функція якості є суб'єктивною думкою дослідника, що може не відповідати дійсності. Отже, для отримання максимально якісного розв'язку необхідно вкласти максимум інформації про досліджуваний об'єкт у вигляді обмежень та скласти максимально об’єктивний критерій оцінки ефективності отриманої моделі.
5. Перспективи використання генетичних алгоритмів в САПР ТП
Система автоматизованого проектування технологічних процесів (САПР ТП) призначена для автоматичного проектування й нормування технологічних процесів виготовлення деталей машино-, приладобудування й інших виробництв, що мають у своєму складі механооброблюючі підрозділи (інструментальні, механоскладальні й т.п.). При цьому бажано найменше втручання людини в процес розробки технологічного процесу (ТП), що повинно забезпечити мінімізацію строків проектування.
Серед найбільше часто використовуваних методів автоматизованого проектування ТП варто виділити експертні системи (ЕС) і нейронні мережі (НС). До недоліків ЕС варто віднести велику їх залежність від людини технолога, який повинен указувати ЕОМ ключові вузли ТП, визначати послідовність технологічних операцій і т.д. Недоліком НС можна назвати довгий строк навчання й необхідність повторювати процес навчання для кожної нової базової деталі або вузла.
Згідно [9], генетичний алгоритм (ГА) – це евристичний алгоритм пошуку, використовуваний для рішення завдань оптимізації й моделювання шляхом послідовного підбора, комбінування й варіації шуканих параметрів з використанням механізмів, що нагадують біологічну еволюцію. Є різновидом еволюційних обчислень. Відмінною рисою генетичного алгоритму є акцент на використання оператора «схрещування», що робить операцію рекомбінації рішення-кандидатів, роль якої аналогічна ролі схрещування в живій природі.
Таким чином, використовуючи ГА можна навчити ЕОМ самостійно створювати нові ТП, значно скоротивши строки підготовки виробництва. При цьому немає необхідності в створенні бази даних з типовими деталями й вузлами, що значно спростить завдання створення такого САПР ТП.
5.1 Теоретична частина
ГА являє собою метод, що відбиває природну еволюцію методів рішення проблем, і в першу чергу задач оптимізації. Так автори [1, 2] вважають, що ГА – це процедури пошуку, основані на механізмах природного добору й спадкування. При природному доборі виживають самі пристосовані особини, при цьому ступінь адаптації залежить від набору хромосом конкретної особини, отриманого від батьків.
Завдання кодується таким чином, щоб її рішення могло бути представлене у вигляді вектора («хромосома»). Випадковим образом створюється деяка кількість початкових векторів («початкова популяція»). Вони оцінюються з використанням «функції пристосованості», у результаті чого кожному вектору привласнюється певне значення («пристосованість»), що визначає ймовірність виживання організму, представленого даним вектором. Після цього з використанням отриманих значень пристосованості вибираються вектора (селекція), допущені до «схрещування». До цих векторів застосовуються «генетичні оператори», створюючи в такий спосіб наступне «покоління». Особини наступного покоління також оцінюються, потім виробляється селекція, застосовуються генетичні оператори й так у циклі, поки не буде виконаний один із критеріїв зупинки алгоритму: знаходження глобального, або субоптимального рішення; вичерпання числа поколінь, відпущених на еволюцію; вичерпання часу, відпущеного на еволюцію.
У такий спосіб узагальнений алгоритм ГА буде складаються з наступних операцій:
1. Ініціалізація;
2. Оцінка;
3. Відбір;
4. Рекомбінація;
5. Якщо виконуються умови зупинки, то (кінець циклу), інакше (початок циклу).
Ініціалізація
, тобто створення початкової популяції дозволяє сформувати відправну точку для роботи алгоритму. При цьому популяція найчастіше створюється шляхом довільного створення хромосом, навіть якщо вона виявиться зовсім неконкурентоспроможної, генетичний алгоритм однаково досить швидко переведе її в життєздатну популяцію. Підсумком першого кроку є популяція H, що складається з N особин.
Етап оцінки
дозволяє визначити, як кожна хромосома (рішення) справляється з даною проблемою. Хромосома декодується відносно до заданої проблеми й перевіряється результат рішення заданого завдання, на підставі якого розраховується «здоров'я» хромосоми. Передбачається, що функція пристосованості завжди має невід’ємне значення, а також те, що для рішення оптимізаційного завдання потрібно максимізувати цю функцію.
Відбір
– це етап, на якому хромосоми вибираються для подальшого використання в іншій популяції, здійснюється на підставі здоров'я хромосом. При цьому, якщо відібрати тільки дуже здорові хромосоми, то рішення стає обмеженим через недостатню розмаїтість, а якщо відбирати випадковим образом, то ГА зводиться до методу випадкового пошуку. Згідно [9], найбільш популярним методом відбору є так називані метод рулетки
. Відповідно до цього методу, чим краще здоров'я хромосоми, тим більше ймовірність її відбору для формування наступного покоління. Імовірність виживання особини h повинна залежати від значення функції пристосованості Fitness (h). Сама частка, що вижили, s звичайно є параметром генетичного алгоритму, і її просто задають заздалегідь. За підсумками відбору з N особин популяції H повинні залишитися s особин, які ввійдуть у підсумкову популяцію H'. Інші особини гинуть.
При рекомбінуванні
частини хромосом переміщаються, а нові хромосоми, що вийшли, повертаються назад у популяцію для формування наступного покоління. Перша група хромосом звичайно називається родителями, друга - дітьми. Головна вимога до розмноження – щоб нащадок, або нащадки, мали можливість успадкувати риси обох батьків, "змішавши" їх яким-небудь досить розумним способом. Загалом кажучи, для того щоб провести операцію розмноження, потрібно вибрати (1-s)p/2 пара гіпотез із H і провести з ними розмноження, одержавши по двох нащадка від кожної пари (якщо розмноження визначене так, щоб давати одного нащадка, потрібно вибрати (1 - s)p пара), і додати цих нащадків в H'. У результаті H' буде складатися з N особин.
Найбільше часто використаними генетичними операторами на етапі розмноження є перехресне схрещування й мутація. Оператор перехресного схрещування
– бере дві хромосоми батьків, розділяє їх у довільній крапці, а потім міняє місцями, що вийшли хвости. При цьому утворяться дві нові хромосоми. Оператор мутації
вносить довільну зміну в гени хромосоми, що дозволяє створювати новий матеріал у популяції.
5.2. Застосування генетичних алгоритмів
При застосуванні ГА першим завданням стає кодування рішення, тобто визначення значення генів. Пропонуємо використати як гени технологічні переходи, як наприклад, «Підрізати торець», «Точити поверхню», «Свердлити отвір наглухо» й ін. При цьому доцільно виділити деякі технологічні операції (включаючи переходи) в окремі гени, наприклад, «Слюсарна», «Лакофарбова» і т.п., що дасть можливість прискорити пошук рішення ГА. Крім того пропонуються деякі технологічно зв'язані переходи також об'єднати в один ген, що також оптимізує роботу ГА. Подальші дослідження допоможуть створити оптимальний словник кодування для мінімізації часу виконання ГА з одержанням найбільш якісного ТП.
Оцінку здоров'я хромосом пропонується проводити в кілька етапів, оскільки в основі розробки будь-якого ТП лежать технічний, техніко-економічний й економічний принципи. Відповідно до першого принципу ТП повинен забезпечити виконання всіх вимог на виготовлення виробу, другий забезпечити максимальну продуктивність, а третій визначає умови, що забезпечують мінімальні витрати праці й найменші витрати виробництва (найбільше часто приймають мінімальну собівартість).
Техніко-економічний критерій оптимальності (критерій максимальної продуктивності, тобто найменшого штучного часу) пропонується вибрати як цільову функцію, по якій визначається здоров'я хромосоми.
Технічний принцип, тобто умова достатності наявності переходів у хромосомі для обробки всіх поверхонь деталі, можна реалізувати, використовуючи експертну систему. При цьому не тільки недолік переходів погіршує здоров'я особини, але й зайві переходи також негативно позначаються на її коефіцієнті пристосованості. Також варто враховувати, що наявність технологічно вірної послідовності операцій позитивно позначається на здоров'я особини, а інакше - негативно.
Вага коефіцієнтів буде визначатись експериментально. Наприклад, при наявності операції «Термічна» першої в ТП даної хромосоми визначити
k = 0.5, але, наприклад, при наявності в ТП даної хромосоми операції «Слюсарна» безпосередньо за «Свердлильна» привласнити k = 1.1. Проведення подальших дослідів дозволить виявити найбільш значимі технологічні критерії для даного завдання й значення ваги коефіцієнтів для них.
5.3 Проблеми при використанні генетичних алгоритмів
Згідно [2], серед проблем ГА варто виділити передчасне сходження й епістазис.
Проблема передчасного сходження
пов'язана з недостатньою розмаїтістю хромосом у популяції. Найпоширенішою причиною передчасного сходження є занадто малий розмір популяції. При недостатній розмаїтості, коефіцієнт здоров'я знижується в наступних поколіннях. Іншою причиною може бути алгоритм відбору. Якщо для розмноження відбираються особини тільки з високим коефіцієнтом здоров'я (наприклад у методи еліти
), то це приводить до сильного зменшення розміру популяції в порівнянні з початковим.
Епістазисом
називається внутрішня залежність між змінними (генами), закодованими в хромосомі. Якщо жоден ген не пов'язаний з іншими генами в хромосомі, уважається, що епістазис дуже малий або не існує, інакше епістазис високий і може створити проблеми для алгоритмів рекомбінування. Рекомендується зберегти гени (змінні), які близько зв'язані один з одним у хромосомі, щоб уникнути руйнування цих груп при рекомбінуванні.
Також проблемою ГА високі вимоги до продуктивності апаратного забезпечення САПР ТП.
Висновки
Отже, однією з головних функцій, що виконують інформаційні системи в приладобудуванні, можна назвати моделювання, проектування та оптимізацію технологічних процесів, оскільки технологічні процеси є основою виробничої системи.
Побудова подібних автоматизованих інформаційних систем для виробничих потреб повинна здійснюватися на базі методології дослідження технологічних процесів з використанням інструментальної програмної оболонки.
Розроблена структура автоматизованої системи на базі САПР дозволяє отримувати інформацію про технологічний процес, ідентифікувати окремі технологічні об’єкти, аналізувати інформацію, керувати окремими його стадіями і через АСУ усім виробництвом.
Вибір вищезгаданого методу генетичних алгоритмів дає можливість розробляти за допомогою ЕОМ технологічні процеси, основані на вхідній інформації щодо характеристик оброблювальних об’єктів, параметрів механічної обробки об’єктів і т.і.
Розроблене у роботі програмне забезпечення для системи автоматизованого проектування технологічного процесу повинно мати високу ступінь гнучкості і бути придатним до модифікацій для розв’язку інших задач створення, керування та контролю технологічних процесів.
Дані, отримані з прочитаної літератури, будуть використані в теоретичній частині наукової роботи і допоможуть при написанні програми для проведення досліджень на виробництві.
Summary
Development of CAD systems for technological process is one of the main goal of instrument making branch. Design of new mathematics methods and approaches for such CAD systems is important part of modern scientific works.
From the many methods, using for CAD systems, the Genetic Algorithm was chosen like most perspective method.
The Genetic Algorithm module implements the Genetic Search and Chromosome classes. The Genetic Search is a generic class, and can be used to solved any kind of problems. The Genetic Search class performs a stochastic search of the solution of a given problem. It uses the following pseudocode:
1. Choose initial population
2. Evaluate the fitness of each individual in the population
3. Repeat as many times as generations we allow
1. Select randomly best-ranking individuals to reproduce
2. Breed new generation through crossover and mutation (genetic operations) and give birth to offspring
3. Evaluate the individual fitnesses of the offspring
4. Replace worst ranked part of population with offspring
In scientific work proposing use technological operations like Chromosome classes. In such case, time for design of new technological process may be considerably reduced.
Quality of designed technological process and perspectives of next implantation will be known after implant developed CAD software in instrument making production.
Список використаних джерел
1. Sergio Fierens
. Genetics Algorithms in Ruby – 2007. – 2 p.
2. Gabriel Balan, Dana Richards, Sean Luke
. Algorithms for Leximin-Optimal Fair Policies in Repeated Games – George Mason University. Department of Computer Science, USA, 2006. – 10 p.
3. Keynote Papers
. Virtual and Augmented Reality Technologies for Product Realization – The IMPACT Laboratory, University of Southern California, USA, CAD Laboratory, Mechanical Engineering, TECHNION, ISRAEL, CARVE Laboratory, University of Wisconsin-Madison, USA, 2002. – P. 1-8.
4. Engelbert Westkamper, Sabine Roth-Koch, Martin Stotz
. A New Strategy for Design Orientated Digitizing Integrating Conceptual Design into Design Engineering – 2005. – 5 p.
5. Klaus Weinert, Tobias Surmann, Patrick Damm.
Real Time Solid Modelling of the Milling Process – 2005. – 2 p.
6. Giinter Pritschow, Stefan Heusinger
. STEP-NC based Process Chain for Improving Workpiece Accuracy – 2006. – 1 p.
7. Tatyana Aksenova, Vladimir Volkovich, Alessandro E.P. Villa
. Robust Structural Modeling and Outlier Detection with GMDH-Type Polynomial Neural
Networks – 1998. – 3 p.
8. Eckart Uhlmanrf, Guenter Braeuer, Eric Wiemann, Martin Keunecke.
CBN Coatings on Cutting Tools – Technical University Berlin, Institute for Machine Tools and Factory Management, 1999. – P. 1 – 5.
9. M. Tim Jones
. Al Application Programming – Hingham, Massachusetts,
2004. – P. 112 – 140.
10. Manfred Geiger, Frank Baches, Thomas Menzel.
Technology Oriented Off-line Programming of 3D Laser Machines – 2001. – P. 1 – 3.
11. A.G.Ivakhnenko, G.A.Ivakhnenko
. The Review of Problems Solvable by Algorithms of the Group Method of Data Handling (GMDH) – Pattern Recognition and Image Analysis, Vol. 5, No. 4, 1995 – P.527 – 535.