НАЦІОНАЛЬНИЙТЕХНІЧНИЙ УНІВЕРСИТЕТ УКРАЇНИ
«КИЇВСЬКИЙПОЛІТЕХНІЧНИЙ ІНСТИТУТ»
Курсова робота
На тему:
Використаннягенетичних алгоритмів в САПР ТП
факультет:Приладобудівний
кафедра: Виробництваприладів
Київ – 2009
План
Вступ
1. Класифікація інформаційних технологічних систем
2. Задачі технологічної підготовки виробництва, щорозв’язуються за допомогою математичного моделювання
3. Аналіз інформаційних зв’язків в технологічнихсистемах виготовлення деталей та складання приладів
4. Моделювання процесів з використанням методівлінійного і нелінійного програмування
5. Перспективи використання генетичних алгоритмівв САПР ТП
5.1 Теоретичначастина
5.2 Застосуваннягенетичних алгоритмів
5.3Проблеми при використанні генетичних алгоритмів
Висновки
Summary
Список використанихджерел
Вступ
Інформаційнісистеми на базі сучасних комп’ютерів, оснащених відповідним програмнимзабезпеченням, відіграють важливу роль в організації, керуванні та плануваннівиробництва, і технологічних процесів в ньому.
Застосуваннякомп’ютерів при рішенні задач технологічного проектування дозволяє оперуватидосить складними схемами і формулами, проте інколи, із-за недостатньоїформалізації завдань, ці залежності неадекватні реальним виробничим процесам. Взв'язку з цим, одним з методів оцінки рішень і вибору оптимального рішення ємоделювання. При моделюванні рішень широко використовують методи математичногота імітаційного моделювання. Для цього створюються спеціальні засоби. Методиматематичного та імітаційного моделювання зазвичай реалізуються на комп’ютерах.
Виробничасистема, як і більшість систем, являє собою сукупність підсистеми, що керується(об’єкт управління), та керованої підсистеми (суб’єкта управління, який має усвоєму розпорядженні відповідні механізми управління). В системі управління формуванняуправляючої дії здійснюється на базі прийняття управлінського рішення. Томууправління можна представити як процес підготовки, прийняття та реалізаціїрішень, що спрямовані на досягнення цілей, які були поставлені. Технологічнийпроцес повинен здійснюватися на базі принципів системного підходу, тому що вінявляє собою сукупність багатьох взаємопов’язаних процесів.
Такимчином ефективне розв’язання задач технологічного проектування виробництваможливе при наявності адекватних математичних та імітаційних моделей параметріві показників технологічних процесів виготовлення виробів приладобудування.
Колиуправляюча підсистема належить виробничій системі, управління її діяльністю тарозвитком здійснюється у замкненому контурі за допомогою зворотного зв’язкувиходу системи (результатів діяльності) із входом до неї (факторами діяльності,у тому числі, факторами виробництва). Наявність зворотного зв’язку забезпечує впливна виробничі фактори за рахунок власних ресурсів, завдяки чому й досягаєтьсясамоорганізація виробничої системи.
1.Класифікація інформаційних технологічних систем
Наоснові опублікованих джерел [3], можна сказати, що ефективність для виробництвасвоєчасно отриманої інформації у 3 рази вища від ефективності освіти для цієї жсфери діяльності, у 6 разів – від темпів розвитку науково-технічного прогресу,у 12 разів – від вкладеного капіталу, та у 18-25 разів – від нерухомості.
Длярозв’язку проблем, які пов’язані з інформаційним забезпеченням технологічнихпроцесів, сьогодні використовуються автоматичні системи управліннятехнологічними процесами (АСУТП) типу SCADA (Supervisory Control and DataAcquisition) або DCS (Distributed Control Systems). Обидва вказаних типи системналежать класу MMI (Man-Machine Interface), що означає „людино-машиннийінтерфейс” у контексті забезпечення двобічного зв’язку „оператор — технологічнеобладнання”.
Протеголовну увагу слід звернути на САПР (системи автоматизованого проектування),без яких не може обійтися жодне промислове підприємство, чия продукція потребуєконструкторської та технологічної документації. Сучасні технології САПР дляпідприємств представлені системами CAD/CAM/CAE/PDM (Сomputer Aided Design,Manufacturing, Engineering, Product Data Management). Ці системи дозволяютьобійтися без „паперової” документації, здійснюючи прямий зв’язок між процесамирозробки виробу та його виробництвом, що дозволяє підвищити якість продукції таскоротити час розробки.
Поволіміж ММІ та ERP утворилася проміжна група систем, що зветься MES (ManufacturingExecution 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 oneof the main goal of instrument making branch. Design of new mathematics methodsand approaches for such CAD systems is important part of modern scientific works.
From the many methods, using for CAD systems, the GeneticAlgorithm was chosen like most perspective method.
The Genetic Algorithm module implements the Genetic Searchand Chromosome classes. The Genetic Search is a generic class, and can be usedto solved any kind of problems. The Genetic Search class performs a stochasticsearch 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 likeChromosome classes. In such case, time for design of new technological processmay be considerably reduced.
Quality of designed technological process and perspectives ofnext implantation will be known after implant developed CAD software ininstrument making production.
Список використаних джерел
1. SergioFierens. Genetics Algorithms in Ruby – 2007. – 2 p.
2. Gabriel Balan, DanaRichards, Sean Luke. Algorithms for Leximin-Optimal Fair Policies inRepeated Games – George Mason University. Department of Computer Science, USA, 2006.– 10 p.
3. Keynote Papers.Virtual and Augmented Reality Technologies for Product Realization – The IMPACTLaboratory, University of Southern California, USA, CAD Laboratory, MechanicalEngineering, TECHNION, ISRAEL, CARVE Laboratory, University ofWisconsin-Madison, USA, 2002. – P. 1-8.
4. EngelbertWestkamper, Sabine Roth-Koch, Martin Stotz. A New Strategy for DesignOrientated Digitizing Integrating Conceptual Design into Design Engineering –2005. – 5 p.
5. KlausWeinert, Tobias Surmann, Patrick Damm. Real Time Solid Modelling of theMilling Process – 2005. – 2 p.
6. GiinterPritschow, Stefan Heusinger. STEP-NC based Process Chain for ImprovingWorkpiece Accuracy – 2006. – 1 p.
7. TatyanaAksenova, Vladimir Volkovich, Alessandro E.P. Villa. Robust StructuralModeling and Outlier Detection with GMDH-Type Polynomial Neural
Networks– 1998. – 3 p.
8. EckartUhlmanrf, Guenter Braeuer, Eric Wiemann, Martin Keunecke. CBN Coatings onCutting Tools – Technical University Berlin, Institute for Machine Tools andFactory Management, 1999. – P. 1 – 5.
9. M.Tim Jones. Al Application Programming – Hingham, Massachusetts,
2004.– P. 112 – 140.
10. ManfredGeiger, Frank Baches, Thomas Menzel. Technology Oriented Off-lineProgramming 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 DataHandling (GMDH) – Pattern Recognition and Image Analysis, Vol. 5, No. 4, 1995 –P.527 – 535.