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

Відбір – це етап, на якому хромосоми вибираються для подальшого використання в іншій популяції, здійснюється на підставі здоров'я хромосом. При цьому, якщо відібрати тільки дуже здорові хромосоми, то рішення стає обмеженим через недостатню розмаїтість, а якщо відбирати випадковим образом, то ГА зводиться до методу випадкового пошуку. Згідно [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 popu