Навигация
Моделювання процесів з використанням методів лінійного і нелінійного програмування
37537
знаков
0
таблиц
2
изображения
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 особин.
Найбільше часто використаними генетичними операторами на етапі розмноження є перехресне схрещування й мутація. Оператор перехресного схрещування – бере дві хромосоми батьків, розділяє їх у довільній крапці, а потім міняє місцями, що вийшли хвости. При цьому утворяться дві нові хромосоми. Оператор мутації вносить довільну зміну в гени хромосоми, що дозволяє створювати новий матеріал у популяції.
Похожие работы
... адміністратор локальної мережі, який є у штатному розкладі і займається усіма проблемами, зв’язаними з комп’ютерами. Рисунок 1.2 – Функціональна схема автоматизованого робочого місця науково-технічної бібліотеки Метою розробки АРМ є - скорочення часу обробки оперативних даних, зменшення кількості помилок при обробці інформації. Основні функціональні вимоги до розроблюваного автоматизованого ...
... інші території. На додаток до цього моделі прогнозування в СППР та основані на реальних знаннях системи часто використовуються як настільні, розраховані на одного користувача системи. Системи підтримки прийняття рішень набули широкого застосування в економіках передових країн світу, причому їхня кількість постійно зростає. На рівні стратегічного управління використовується ряд СППР, зокрема для ...
... ічного університету, доктором технічних наук, професором М-П.Зборщиком. Висновок установи, в якій виконано дисертацію, с першою і дуже важливою її експертизою з точки зору відповідності дисертації вимогам “Порядку”. Висновок затверджується ректором (директором) або проректором (заступником директора) з наукової роботи, які несуть персональну відповідальність за якість, об'єктивність і строки пі ...
... видів риб та водоплавних та навколоводних птахів. З птахів домінують гусеподібні, сивкоподібні, а також зустрічаються норцеподібні, лелекоподібні, журавлеподібні і горобцеподібні. Розділ 4. Проектування екологічних мереж Ратнівського району 4.1 Загальні поняття Сучасна стратегія охорони природи полягає у забезпеченні динамічної екологічної рівноваги окремих регіонів, пошуку різноманітних ...
0 комментариев