Використання генетичних алгоритмів в САПР ТП

Слід зауважити, що серед факторів виробництва надзвичайно важливе значення мають робоча сила та виробничі потужності, тому отримання інформації, що відноситься до них, вельми необхідно.

Інформація, що відноситься до наявності робочої сили, повинна бути різнобічною. Потреба у робочій силі, співвідношення жіночої та чоловічої праці, кваліфікованої, навченої або ненавченої робочої сили визначаються характером виробничого процесу, його технології. Характер виробництва висуває до працівника підвищені вимоги, які в умовах серійного виробництва зводяться до здатності працюючих здійснювати технологічний процес з використанням монотонної та важкої фізичної праці. Робота персоналу виробництва в умовах граничного напруження не може не впливати на якість

технологічних операцій, які виконують у процесі виробництва працюючі, та забезпечення стабільності якості промислової продукції.

Проведений аналіз інформаційних зв'язків в технологічних схемах промислових виробництв дозволяє переходити до подальших кроків у дослідженні технологічних систем у приладобудуванні.

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.

Страницы: 1, 2