Размещено на http://www.allbest.ru/

Національний університет "Львівська політехніка"

Автореферат дисертації на здобуття наукового ступеня

кандидата технічних наук

Розроблення і використання генетичних алгоритмів для розв'язання задач розкрою плоских заготовок

Спеціальність 05.13.12 - Системи автоматизації проектувальних робіт

Кривий Ростислав Зіновійович

Львів - 2010

Дисертацією є рукопис

Робота виконана у Національному університеті “Львівська політехніка”

Міністерства освіти і науки України

Науковий керівник: доктор технічних наук, професор

Лобур Михайло Васильович,

Національний університет “Львівська політехніка”,

завідувач кафедри систем автоматизованого проектування

Офіційні опоненти:

доктор технічних наук, доцент

Романишин Юрій Михайлович,

Національний університет „Львівська політехніка”,

професор кафедри електронних засобів інформаційно-комп'ютерних технологій;

кандидат технічних наук, професор

Крищук Володимир Миколайович,

Запорізький національний технічний університет,

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

ЗАГАЛЬНА ХАРАКТЕРИСТИКА РОБОТИ

Актуальність теми. Одна з головних задач сучасного виробництва - зменшення втрат матеріалів. Важливим фактором зниження витрат і раціонального використання матеріальних ресурсів є вдосконалення систем технологічної підготовки розкрою промислових матеріалів. Огляд робіт, пов'язаних з оптимізацією розкрою, дає змогу зробити висновок про те, що у деяких галузях промисловості ця проблема вирішується досить успішно. На сьогодні для одновимірного розкрою заготовок вздовж смуг існують ефективні алгоритми, але для двовимірного матеріалу, навіть для заготовок прямокутної форми (не кажучи вже про заготовки довільної форми), універсальних і водночас ефективних алгоритмів їх розміщення розроблено досить мало. Саме ці обставини спонукають сучасних дослідників по-новому глянути на розроблення методів і алгоритмів оптимізації планів розкрою матеріалів в таких галузях промисловості, як деревообробна, машинобудівна тощо. алгоритм генетичний модифікація

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

Зв'язок роботи з науковими програмами, планами, темами. Дисертаційна робота безпосередньо пов'язана з планами наукових досліджень, які виконувалися і виконуються за науковою тематикою кафедри „Системи автоматизованого проектування” Національного університету „Львівська політехніка” “Розташування плоских об'єктів у площині”, зокрема здобувач приймав участь у виконанні теми “Автоматизація конструкторського проектування мікроелектронних пристроїв”. Термін виконання з червня 2007 р. по грудень 2009 р. (№ держ. реєстр. 0107U006229), де здобувачем досліджені впливи параметрів операторів генетичних алгоритмів на якість розв'язку задач розміщення і розкрою плоских заготовок та запропоновані нові алгоритми їх розв'язання.

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

Для досягнення зазначеної мети необхідно вирішити такі основні завдання:

· проаналізувати сучасний стан еволюційних алгоритмів;

· модифікувати базові алгоритми гільйотинного розкрою, застосувавши еволюційні алгоритми;

· розробити нові та модифікувати існуючі генетичні алгоритми розв'язання задач розкрою плоских заготовок різного роду матеріалів в площині;

· розробити програмну систему для дослідження та використання генетичних алгоритмів;

· експериментально дослідити ефективність запропонованих алгоритмів розкрою на розробленому програмному забезпеченні.

Об'єктом досліджень дисертаційної роботи є процес автоматизованого проектування карт розкрою з використанням алгоритмів еволюційного типу.

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

Методи дослідження. У дисертаційній роботі для розв'язання поставлених завдань використано методи теорії алгоритмів, теорію шаблонів і теорію еволюційних алгоритмів.

Наукова новизна одержаних результатів:

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

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

· Вперше запропоновано генетичний алгоритм розв'язання задач розкрою і розміщення заготовок довільної форми в площині довільної форми, що дозволило забезпечити зниження втрат матеріалів.

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

Практичне значення одержаних результатів:

· Розроблено генетичні алгоритми та програми для розв'язання завдання прямокутного розкрою, що дозволило зменшити втрати матеріалу.

· Розроблено і реалізовано програмну систему “ГЕН”, яка дозволяє дослідити часову ефективність алгоритмів еволюційного типу.

Теоретичні і практичні результати дисертаційної роботи реалізовані в ході виконання кафедральної теми «Автоматизація конструкторського проектування мікроелектронних пристроїв». Термін виконання: з червня 2007 р. по грудень 2009 р. Це підтверджується відповідним актом. Також практичні результати впроваджено у виробництво ТзОВ “Чумак”.

Особистий внесок здобувача. Всі наукові результати теоретичних і практичних досліджень, викладені в дисертації, одержані автором особисто. У друкованих працях, опублікованих у співавторстві, дисертанту належать:

· реалізація та дослідження шаблонів для дослідження генетичних алгоритмів і розробка структури системи [1,3,13,14];

· метод розв'язання задачі прямокутного розкрою і розміщення плоских заготовок в площині [2,5,6,7];

· дослідження чинників і класифікація факторів, які впливають на ефективність генетичних алгоритмів [4,12,11];

· розроблено програмну систему для дослідження часової ефективності генетичних алгоритмів [3,8,9,10].

Апробація результатів дисертації. Матеріали дисертації доповідались та обговорювалися на міжнародних науково-технічних конференціях:

· Міжнародних науково-технічних конференціях «Досвід розробки і застосування приладо-технологічних САПР в мікроелектроніці» - CADSM'2007, 2009 (Поляна 2007, 2009);

· Польсько-українській науково-практичній конференції «САПР в машинобудуванні - впровадження і проблеми освіти» - CADMD'2008 (Львів, 2008); CADMD'2009 (Красічін, Польща, 2009);

· Міжнародних конференціях молодих вчених «Перспективні технології і методи проектування МЕМС» - MEMSTECH'2007, 2008, 2009 (Поляна 2007, 2008, 2009);

· Міжнародних науково-технічних конференціях «Сучасні проблеми радіоелектроніки, телекомунікацій, комп'ютерної інженерії» - TCSET'2008, 2010 (Славське, 2008, 2009);

· Наукових семінарах кафедри «Системи автоматизованого проектування» Національного університету «Львівська політехніка» (2007-2009 р.р.).

Публікації. За темою дисертації опубліковано 14 друкованих праць, з них 4 статті у фахових виданнях України, 10 у матеріалах міжнародних конференцій.

Структура дисертації. Дисертаційна робота складається із вступу, чотирьох розділів, висновків, двох додатків та списку літературних джерел (112 найменувань). Загальний обсяг роботи становить 132 сторінку. Основний зміст викладено на 107 сторінках. Робота містить 45 рисунків та 6 таблиць.

ОСНОВНИЙ ЗМІСТ РОБОТИ

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

У першому розділі розглянуто головні передумови розв'язання задач розкрою. Проведено порівняльний аналіз існуючих методів оптимізації плану розкрою промислових матеріалів і упаковки, таких як: лінійне програмування, модифікований симплекс-метод та інші. Значний вклад в розвиток методів оптимізації плану розкрою внесли: Л.В. Канторович і В.А. Залгаллер (метод лінійного програмування, методи комбінаторної (дискретної) оптимізації), Дж. Данціг (симплексний метод, модифікований симплекс-метод), Гілмор і Гоморі (симплексний алгоритм визначення оптимального плану розкрою), М.І. Коробов і В.В. Кузнєцов (методот лінійного програмування з використанням стандартної процедури симплекс-методу), Ф.В. Бабаєв (евристичні методи), Е.А. Мухачова, Ю.Г. Стоян (методи комбі-наторної оптимізації, послідовно-одиночного розміщування, асимптотичного перебору локальних екстремумів, тощо). Огляд робіт, пов'язаних з оптимізацією розкрою, дає змогу зробити висновок про те, що у деяких галузях промисловості ця проблема вирішується досить успішно.

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

· генетичний алгоритм, призначений для оптимізації функції дискретних змінних, що акцентує увагу на рекомбінації генів;

· еволюційне програмування, орієнтоване на оптимізацію неперервних функцій без використання рекомбінації;

· еволюційні стратегії, орієнтовані на оптимізацію неперервних функцій з використанням рекомбінації;

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

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

Спочатку генерується початкова популяція особин (індивідуумів), тобто деякий набір рішень задачі. Як правило, це робиться випадковим чином. Потім моделюється розмноження всередині цієї популяції. Для цього випадково відбирається декілька пар індивідуумів, відбувається схрещування між хромосомами в кожній парі, а отримані нові хромосоми втілюються в популяцію нового покоління. У генетичному алгоритмі зберігається основний принцип природнього відбору - чим пристосованіший індивідуум (чим більше відповідне йому значення цільової функції), тим з більшою ймовірністю він буде брати участь у схрещуванні. При такому відборі члени популяції з більш високою пристосованістю з більшою ймовірністю будуть частіше вибиратися, ніж особини з низькою пристосованістю. Для кожного індивідуума може застосовуватися кросинговер, після якого отримані нащадки заміняють собою батьків і переходять до мутації. Тоді моделюються мутації - у декількох випадково обраних особинах нового покоління змінюються деякі гени. Потім стара популяція частково або цілком знищується, здійснюється перехід до розгляду наступного покоління. Популяція наступного покоління в більшості реалізацій генетичних алгоритмів містить стільки ж особин, скільки початкова, але в силу відбору пристосованість у ній у середньому вища. Після чого процеси відбору, схрещування й мутації повторюються вже для цієї популяції, тощо. У кожному наступному поколінні спостерігається виникнення зовсім нових рішень задачі, що розв'язується. Серед них будуть як погані, так і хороші, але завдяки відбору число прийнятних рішень буде зростати. Робота генетичного алгоритму є ітераційним процесом, що продовжується, поки не виконається задане число ітерацій або інший заданий критерій зупинки. Таким чином, генетичні алгоритми є однією з важливих парадигм широкої області алгоритмів пошуку оптимальних рішень, що активно розвиваються, а з розвитком методів комп'ютерної підтримки ухвалення рішень вони набувають все більшого значення.

Програмні продукти в цій області діляться на декілька великих категорій. Перша категорія програм - це пакети, що реалізують класичний генетичний алгоритм з можливим відлагодженням параметрів керування основними операторами генетичних алгоритмів. Модель хромосоми в таких пакетах має, як правило, стандартну бінарну структуру, а функція відбору задана одним математичним виразом. До таких програм відносяться: пакет Evolver 4.0 компанії Palisade Corp, пакет GeneHunter компанії Ward System Group, тощо. Істотним недоліком цих методів є прив'язка до бінарної або числової моделі хромосоми (хромосома не може мати складної структури). До другої категорії програм відносяться спеціалізовані програми, призначені для вирішення конкретних завдань. Їх генетичні алгоритми розроблені і оптимізовані для вирішення вузької, чітко визначеної проблеми. Ефективність даної категорії програм залежить від багатьох чинників і, зокрема, від таких, як генетичні оператори і вибір відповідних значень параметрів, а також від способу представлення рішення на хромосомі. Оптимізація цих чинників приводить до підвищення швидкості і стійкості пошуку, що істотно впливає на застосування генетичних алгоритмів. Третя категорія розробок по генетичних алгоритмах включає наукові дослідження, що полягають в дослідженні властивостей і характеристик різних генетичних алгоритмів, їх збіжності і виродженості (MATLAB 7.0, Evolvica, E2K).

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

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

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

В розділі розглянута класична постановка задачі прямокутного розкрою, запропонована проф. Стояном Ю. Г., в якій заданий прямокутник з довжиною і шириною . Також заданий набір прямокутників з лінійними розмірами , , де . Положенням прямокутника в назвемо трійку , де - це (локальні в ) координати лівої-нижньої вершини , а - орієнтація в . Ми будемо говорити, що орієнтація пряма, якщо ширина прямокутника розташована вздовж осі , і зворотний, якщо вздовж осі знаходиться довжина даного прямокутника. Скрізь далі вважаємо, що всі положення заготовок знаходяться всередині прямокутника , тобто для прямої орієнтації:

і для прямокутника, обернутого на 90 градусів:

Для двох положень вводиться операція перетину , як перетин внутрішніх множин у . Розміщенням в називається множина , така що для будь-яких двох положень , виконується Ш, при . На множині всіх розміщень задана функція . Потрібно знайти таке розміщення :

.

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

Знаходження цих показників повинно відбуватись за наступних умов:

· ребра заготовки, що підлягають розкрою, паралельні ребрам матеріалів;

· заготовки, що підлягають розкрою, не перетинаються одна з одною;

· заготовки, що підлягають розкрою, не перетинаються із сторонами прямокутників матеріалу.

Для опису хромосоми рішення в такому випадку пропонується використовувати диплоїдну модель, яка складається з двох хромосом, що дозволяє враховувати орієнтацію заготовки. В першій зберігається інформація в якому порядку розміщати заготовки, а в другій - які заготовки необхідно обернути на 90 градусів. Наприклад, на рис.1 представлено приклад хромосоми, в якій заготовки під номером 4, 1, 8, 6, 9 - необхідно обернути на 90 градусів:

4	7	3	2	1	5	8	6	0	9
1	0	0	0	1	0	1	1	0	1

Рис.1. Приклад диплоїдної моделі рішення задачі розкрою

Ідея алгоритму полягає в наступному. Задаємо довільну послідовність елементів для подальшої оптимізації. Далі необхідно змінювати порядок розташування елементів в сегментах. В процесі цього необхідно вибирати такі елементи, які забезпечують високу якість стиснення. У випадку, коли ширина рядка певних заготовок перевищує ширину сегмента, необхідно обертання заготовок на 90 градусів до тих пір, поки заготовки не помістяться в сегменті. Якщо ширина заготовок не буде менша чи рівна ширині сегменту, тоді останню переносимо на наступний рядок сегменту. Після чого необхідно відсортувати ряди з заготовками в сегменті по величині втрат площі:

,(1)

,

.(2)

де S_U - площа сегмента, S_R - загальна площа заготовок, які можна розмістити в одному сегменті, W - витрати матеріалу, W_R - відносні витрати матеріалу.

У випадку, коли втрати площі сегмента дорівнюють нулю (1), будь-які маніпуляції з ним припиняються. Він переходить у наступне покоління. Тобто блоки, які знаходяться в цьому сегменті, потрапляють в шаблон. Поняття шаблону було введено для визначення множини хромосом, які володіють деякими загальними властивостями. Шаблоном називають рядок вигляду (a₁, a₂, ..., a_i, ..., a_l), де a_i є {0, 1, *}. Символом "*" в деякому розряді позначається те, що там може бути як 1, так і 0. Це призводить до прискорення знаходження результату оптимального гільйотинного розкрою.

У генетичному алгоритмі логічно побудувати оператор схрещування так, щоб він був максимально наближений до реальних біологічних процесів, таких, як мейоз і утворення зиготи, що має свої переваги в порівнянні з описаними схемами. Використання механізму диаллельного розщеплювання, закладеного в основі генетичного алгоритму, дало можливість побудувати принципово нову схему, в яку включено фазу формування хромосомного набору нащадка із двох хромосомних наборів батьківських особин. Також відмінністю пропонованої схеми кросинговера від більшості існуючих є наявність поняття «статі» у особин, які беруть участь в кросинговері, кількість яких, як і в простому генетичному алгоритмі, рівна двом.

На рис. 2 представлено порівняльну характеристику роботи програми, що реалізує запропонований алгоритм, і роботи системи RealCut2D. В даному випадку розглядався приклад з розміщенням більше 100 заготовок.

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

Вхідними даними для розв'язування задачі розміщення довільних об'єктів на площині є масив заготовок, які необхідно розмістити, і масив контурів, в яких потрібно розташувати заготовки. Самі контури можуть бути як прямокутної форми, так і довільної, тобто матеріал міг використовуватися в попередніх задачах і залишився у відходах. Так само і заготовки можуть мати правильну і неправильну форму. В першу чергу необхідно визначити, які заготовки можна буде розмістити і в яких контурах. У випадку, коли у деякий контур неможливо розмістити ні одну заготовку, контур автоматично попадає у відходи і видаляється з масиву контурів.

Оптимальне розміщення об'єктів довільної форми є значно складнішою задачею, ніж у випадку об'єктів прямокутної форми. Дуже часто її рішення розбивають на дві складові. Перша - це побудова карти розкрою з використанням певних евристичних підходів, наприклад відповідно до “жадібної” стратегії розкрою. Вхідним параметрам такого завдання відповідає задана послідовність розміщення заготовок і їх орієнтація. Друга складова - оптимізаційна, вона полягає в пошуку послідовності розміщення, що забезпечує мінімальні втрати. Для їх оптимізації використовуються стохастичні методи, такі як генетичні алгоритми і метод околиць, що звужуються.

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

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

Одна з важливих переваг розробленого алгоритму - його універсальність. Кожна стадія його розробки проводилася з врахуванням необхідності розміщення двовимірних об'єктів довільної форми, зокрема, допускається розміщення об'єктів з немонотонними кордонами, багатозв'язних об'єктів, вкладене розміщення. В алгоритмі, який використовується, відсутні будь-які спрощуючі припущення, пов'язані з перевагою окремих типів заготовок або інших особливостей, пов'язаних зі сферою застосування даного методу (текстильне виробництво або металообробка і тощо). У зв'язку з цим запропонований алгоритм може бути адаптований для використання в різних виробничих областях.

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

У роботі пропонується в якості локальних характеристик форми заготовок і площі розміщення використовувати сегменти обмежуючих їх контурів, що складаються з трьох послідовних ребер, які утворюють два внутрішні кути (рис.3).

Розглядається локальне поєднання пари таких сегментів, один з яких опуклий (обидва кути між ребрами > 180⁰), а другий є увігнутий (обидва кути між ребрами < 180⁰). В результаті кількість можливих варіантів скорочується за рахунок підбору поєднуваних локальних елементів конура з найкращим збігом форми. Після того, як вибрана пара поєднується, локальні характеристики форми далі використовуються для визначення положення і орієнтації об'єкту. Таким чином, вибір та розміщення заготовок засновані на використанні локального аналізу геометрії контурів.

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

де Н - шаблон; m(H,t) - частка рядків, відповідних шаблону Н, яка присутня в поточному поколінні t; m(H,t+1) - частка рядків, відповідних шаблону Н, яка присутня в популяції в наступному поколінні; l - довжини двійкових рядків; - довжина шаблону Н; - вірогідність проведення кросовера; -вірогідність мутації одного розряду; о(Н) - порядок шаблону Н; - вірогідність того, що мутація не зруйнує шаблон, g(H) - кількість рядків шаблонів, які переходять у наступне покоління, m(t) - це загальна кількість хромосом в поточному поколінні.

Якщо вважати, що - вірогідність того, що точка розриву потрапить всередину шаблону, то - вірогідність того, що кросовер не зруйнує шаблон. Згідно стратегії відбору методом усікання канонічного генетичного алгоритму шанси особини взяти участь в схрещуванні обчислюються відповідно до відношення g(H)/m(t).

Вплив шаблонів на результат роботи генетичного алгоритму було досліджено за допомогою тестових функцій Де Йонга, які були розроблені для аналізу ефективності генетичних алгоритмів. Всі тестові функції можуть мати різне число параметрів n. Так як генетичний алгоритм використовує стохастичність, то для того щоб визначити наскільки ефективний генетичний алгоритм, потрібно запустити його на одній і тій же тестовій функції декілька разів, а потім взяти середній результат. В таблиці 1 показано результати серій досліджень максимізації функції з двома змінними на певному відрізку з використанням шаблонів після 20 покоління. Генетичний алгоритм без використання шаблонів знаходить оптимальний результат для даної функції не раніше 60 покоління. Отже, отримані результати підтвердили те, що шаблони пришвидшують знаходження оптимального результату.

Табл.1.

Результат роботи генетичного алгоритму з використанням шаблонів після 20 покоління

Номер досліду	Покоління
	5	10	20	40	60	80	100
1.	16.805866	20.167982	20.438866	20.438866	20.438866	20.438866	20.438866
2.	17.962017	19.712310	20.411669	20.438866	20.438866	20.438866	20.438866
3.	18.096183	19.818836	20.438866	20.438866	20.438866	20.438866	20.438866
4.	19.426227	19.534080	20.384507	20.438866	20.438866	20.438866	20.438866
5.	19.478245	20.330287	20.438866	20.438866	20.438866	20.438866	20.438866

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

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

На розробку, програмну реалізацію і результат роботи генетичних алгоритмів впливає ряд факторів, серед яких:

· програмна реалізація кожного генетичного алгоритму відбувається практично з нуля, тому всі напрацювання з попередніх проектів в більшості випадків втрачаються;

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

Враховуючи особливості генетичного алгоритму, було розроблено структуру системи, де, крім основних генетичних операторів, важлива роль надається роботі над шаблоном рішень (множиною рішень, які володіють деякими загальними властивостями) (рис.4).

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

ПМК “ГЕН” реалізує генетичний алгоритм без прив'язки до конкретних специфікацій предметної області. В якості програмної платформи для реалізації ПМК “ГЕН” вибрано Microsoft Visual Studio. В якості мови програмування вибрано мову програмування високого рівня С++. Вона дозволяє максимально компактно та ефективно оперувати даними, будувати великі абстрактні моделі та одночасно доступатися до низьких рівнів програмування, що дає змогу повністю контролювати процес реалізації та відлагодження алгоритму на всіх його етапах.

Програмно-методичний комплекс ”ГЕН” реалізований у вигляді графічної аплікації, яка складається з набору вкладок, які відображають кроки роботи алгоритму. Після внесення всіх параметрів в програму закінчується процес формування вхідних даних генетичного алгоритму. Для кожного покоління вказується його номер, середнє значення цільової функції в популяції. В даному програмно-методичному комплексі передбачено зберігання всіх необхідних для роботи генетичного алгоритму даних у форматі XML. Це дозволило іншим системам використовувати напрацювання даної системи для подальших досліджень.

ОСНОВНІ РЕЗУЛЬТУТИ ТА ВИСНОВКИ

В дисертаційній роботі розв'язано актуальну наукову задачу розроблення методу розкрою плоских заготовок за допомогою генетичних алгоритмів з метою вдосконалення існуючих САПР. При цьому отримано такі основні результати:

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

2. На основі теорії генетичних алгоритмів отримав подальший розвиток метод розкрою прямокутних об'єктів, що дало змогу оптимізувати площу розкрою і зменшити відходи матеріалу на 3-5%.

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

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

5. Розроблено формати для внутрішнього представлення моделей генетичного алгоритму і його характеристик на основі формату XML. Розроблено редактор для формування різних моделей генетичного алгоритму.

6. На основі запропонованих методів і алгоритмів модернізована програмна система розкрою для прямокутних плоских заготовок.

7. Розроблено програмну систему ''ГЕН'' для дослідження параметрів генетичних алгоритмів.

СПИСОК ОПУБЛІКОВАНИХ ПРАЦЬ ЗА ТЕМОЮ ДИСЕРТАЦІЙНОЇ РОБОТИ

1. Кривий Р. З. Можливості використання шаблонів при проектуванні МЕМС / Р. З. Кривий, М. В. Лобур, В. М. Теслюк, С. П. Ткаченко // Зб. наук. праць ІППМЕ ім.Г.Є. Пухова НАН України : Моделювання та інформаційні технології. - 2009. - Вип. 54. - С. 195-199.

2. Грицишин Я.М. Генетичні алгоритми для вирішенні задач розміщення / Я. М. Грицишин, Д. В. Корпильов, Р. З. Кривий, Т. В. Свірідова, С. П. Ткаче-нко // Вісник Національного університету «Львівська політех-ніка» : Комп'ютерні науки та інформаційні технології. - 2009. - № 638. - С. 271-276.

3. Кривий Р.З. Розробка підсистеми для дослідження генетичних алгоритмів з використанням шаблонів / Р.З. Кривий, М.М. Лобур, С.П. Ткаченко // Вісник Національного університету “Львівська політехніка” : Комп'ютерні системи проектування. Теорія і практика. - 2009. - № 651. - C. 182-186.

4. Теслюк В.М. Розроблення підсистеми для розв'язання оптимізаційних задач еволюційними методами / В.М. Теслюк, Р.З. Кривий, Тарік (Мох'д Тайсір) Алі Аль-Омарі, Т.М. Теслюк // Збірник науково-технічних праць. Науковий Вісник НЛТУ України. - 2009. - Випуск 19.4. - С. 243-249.

5. Hrytsyshyn Y. Genetic programming for solving cutting problem / Y. Hrytsyshyn, R. Kryvyy, S. Tkatchenko // Proc. of the IX-th International Conference CADSM. - Lviv-Polyana, 2007. - P. 280-282.

6. Kryvyy R. Orthogonal placement of dіfferent overall components in plane / Rostyslav Kryvyy, Maryan Lobur, Sergiy Tkatchenko // Proc. of the X-th International Conference TCSET. - Lviv-Slavske, 2010. - P.329.

7. Kernytskyy A. VLSI topology synthesis using the method of parallel genetic algorithms / A. Kernytskyy, R. Kryvyу, S. Tkatchenko // Proc. of the 3rd International Conference of Young Scientists MEMSTECH, - Lviv-Polyana, 2007. - P. 151-152.

8. Lobur M. System's structure design for genetic search / M. Lobur, S. Tkatchenko, R. Kryvyy, I. Darnobyt // Proc. of the 5th International Conference of Young Scientists MEMSTECH. - Lviv-Polyana, 2009. - P. 60.

9. Teslyuk V. Development of subsystems for solving optimization problems with the help of genetic algorithms / V. Teslyuk, R. Kryvyy, T. Teslyuk, Tariq (Moh'd Taisir) Ali AlOmari // Proc. of the X-th International Conference CADSM. - Lviv-Polyana, 2009. - P. 364.

10. Kryvyy R. Analysis of existent systems in researching genetic algorithms / R. Kryvyy, M. Lobur, S. Tkatchenko // Proc. of the XV Ukrainian-Polish CADMD. - Krasiczyn (Poland), 2009. - P. 24-25.

11. Lobur M. Type of migrations of individuals in parallel genetic algorithms / M. Lobur, S. Tkatchenko, A. Kernytskyy, R. Kryvyy // Proc. of the IX-th International Conference TCSET. - Slavske, 2008. - P. 75.

12. Kryvyy R. Factors of influence on genetic algorithm's work in MEMS design / R. Kryvyy, M. Lobur, S. Tkatchenko, I. Darnobyt // Proc. of the X-th International Conference CADSM. - Lviv-Polyana, 2009. - P. 327.

13. Kryvyy R. Possibilities of the use of patterns in MEMS design / R. Kryvyy, M. Lobur, S. Tkatchenko, I. Darnobyt // Proc. of the XIV Ukrainian-Polish Conference CADMD. - Lviv, 2008. - P. 45-46.

14. Darnobyt I. Possibilities of the use of genetic algorithms in design of MEMS elements / I. Darnobyt, R. Kryvyy, M. Lobur, S. Tkatchenko // Proc. of the 4th International Conference of Young Scientists MEMSTECH. - Lviv-Polyana, 2008. - P. 57.

АНОТАЦІЇ

Кривий Р.З. Розроблення і використання генетичних алгоритмів для розв'язання задач САПР розкрою плоских заготовок. - Рукопис.

Дисертація на здобуття наукового ступеня кандидата технічних наук за спеціальністю 05.13.12 - системи автоматизації проектувальних робіт. Національний університет «Львівська політехніка», Львів, 2010.

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

Ключові слова: генетичний алгоритм, задача розкрою, задача розміщення, шаблон.

Кривой Р.З. Разработка и использование генетических алгоритмов для решения задач САПР раскроя плоских заготовок. - Рукопис.

Диссертация на соискание ученой степени кандидата технических наук по специальности 05.13.12 - системы автоматизации проектных работ. Национальный университет «Львовская политехника», Львов, 2010.

В диссертации исследованы особенности решения задач раскроя плоских заготовок. Проанализированы существующие методы оптимизации планов раскроя промышленных материалов. Исследовано также развитие эволюционных алгоритмов, идея работы которых заимствована у живой природы. Проведена классификация программных продуктов в данной области. Исследовав особенности раскроя прямоугольных заготовок, можно выделить два важных аспекта. Первый состоит в формировании критерия оптимальности, а второй - в выборе эффективного метода решения задачи оптимизации по выбранному критерию. Целевыми функциями для проектирования планов раскроя могут служить любые показатели, которые обеспечивают экономию сырья или характеризуют эффективность работы оборудования для раскроя или цеха раскроя прямоугольных заготовок. С целью оптимизации решения задачи раскроя прямоугольных объектов был использован генетический алгоритм. В данном алгоритме использована диплоидная модель описания хромосом решений, в которой содержится не только информация о последовательности заготовок, но и об их ориентации. Соответственно выбранной модели был построен оператор скрещивания, максимально приближенный реальным биологическим процессам. Использование шаблонов в генетическом алгоритме привело к более быстрому нахождению решения задачи прямоугольного раскроя.

Задача размещения объектов произвольной формы является значительно более сложной, чем для прямоугольных объектов. В работе эта задача разбивается на две составляющие. Первая - это построение карты раскроя с использованием определенных эвристических подходов. Вторая составляющая - оптимизация последованости размещения с целью получения максимальной плотности расположения заготовок, что обеспечивает минимальные потери. Для улучшения группирования заготовок использованы результаты анализа сегментов их ограничивающих контуров. Заготовки с минимальными потерями площади при стыковке объединяются в группы. Для решения задачи размещения объектов произвольной формы при их группировании предложено использовать шаблоны в алгоритмах генетического типа. Рассмотрены особенности работы с шаблонами. Результаты исследований показали, что использование шаблонов приводит к значительному ускорению получения оптимального результата.

С учетом особенностей генетических алгоритмов разработана структура программной системы, где кроме основных генетических операторов большое внимание уделяется работе над шаблонами решений. Разработанный программно-методический комплекс “ГЕН” позволяет максимально компактно оперировать данными, создавать модели генетических алгоритмов и т.д.

Ключевые слова: генетический алгоритм, задача раскроя, размещение, шаблон.

Kryvyy R.Z. Development and usage of genetic algorithms for solving CAD problems - cutting the flat workpieces. - Manuscript.

Dissertation for the scientific degree of candidate of engineering sciences in computer aided design, speciality 05.13.12, Lviv Polytechnic National University, Lviv, 2010.

In the thesis the method of location and spacing of rectanglar shape blanks and the algorithm for solving location and spacing issues of arbitrary shape blanks on an arbitrary plane based on the theory of genetic algorithms have received the further development. Particular attention is paid to the methods of flat parts grouping in a plane and using templates, which helped optimize cutting area and reduce the waste material. This thesis investigates the influence of patterns for optimal solutions, using genetic algorithms and based on theorem templates added stochastic variable mathematical model for determining the number of templates. Structure of the system was developed for genetic search, which provided an important role for working on template decision. Program-Methodical Complex, which are built on the developed framework allows to investigate factors that affect the temporal performance of various types of evolutionary algorithms.

Key words: genetic algorithm, cutting problem, task allocation, template.

Размещено на Allbest.ru

...