Евристичний метод багатокритеріальної оптимізації
Вантажиться...
Дата
2018-12
Автори
Науковий керівник
Назва журналу
Номер ISSN
Назва тому
Видавець
Анотація
Актуальність теми. З розвитком сучасних технологій стає необхідним швидкий та ефективний розв‟язок складних математичних задач. Особливо популярними є задачі оптимізації. Проблема розв‟язання оптимізаційних задач постає не лише в надсучасних комп‟ютерних технологіях, а і в повсякденному людському житті. Дуже часто ці задачі зводяться до оптимізації певного об‟єкту за групою критеріїв. Наприклад, в ряді задач економічної галузі необхідно максимально збільшити прибуток, але при цьому мінімізувати витрати. В задачі про комівояжера необхідно врахувати не лише відстань від початкового до кінцевого пункту, а і затримки, витрати, загальний час переїзду та певні інші критерії. Всі ці задачі можуть бути сформульовані в загальному випадку наступним чином: максимізувати/мінімізувати декілька функцій, що визначенні на певному проміжку розв‟язків з певним критерієм оптимальності. Такий ряд задач називається багатокритеріальною задачею оптимального рівняння. Вона займає важливе місце серед задач теорії вибору та прийняття рішень. Кожен параметр оптимальності певного розв‟язку може конфліктувати з іншим параметром оптимальності. Через це на сьогоднішній день існує багато підходів до розв‟язання такого ряду задач та аналізу оптимальності знайденого розв‟язку. Тому створення алгоритму, який може аналізувати групу параметрів та знаходити розв‟язок, що задовольняє кожному з критеріїв є складною задачею і на сьогоднішній день.
Об’єкт дослідження є процес багатокритеріальної оптимізації.
Предметом дослідження є евристичні методи розв‟язання задачі багатокритеріальної оптимізації.
Мета роботи є розробка нового методу для розв‟язання задачі багатокритеріальної оптимізації, що характеризується вищою швидкодією та більшою точністю розв‟язків, ніж відомі методи.
Методи дослідження. В роботі використовуються методи евристичних алгоритмів, методи дискретної математики, методи дослідження операцій, методи комбінаторної оптимізації.
Наукова новизна:
• Проаналізовано існуючі алгоритми оптимізації в неперервному просторі, показано їх недоліки в порівнянні з алгоритмом квіткового запилення;
• Запропоновано модифікацію існуючого алгоритму квіткового запилення для розв‟язання задачі багатокритеріальної оптимізації;
• Виконано порівняльний аналіз оригінального алгоритму та модифікованого алгоритму квіткового запилення для розв‟язання задачі багатокритеріальної оптимізації.
Практична цінність отриманих в роботі результатів полягає в тому, що розроблений модифікований алгоритм дозволяє прискорити процес багатокритеріальної оптимізації та покращити результат в сенсі точності і сталості результату. Крім того, алгоритм показав що здатний розв‟язувати задачу багатокритеріальної оптимізації без будь-якої додаткової інформації, крім тої, що необхідна для обчислення цільової функції. Лише за допомогою методу скаляризації декількох функцій його було приведено до форми, що дозволяє розв‟язувати задачу багатокритеріальної оптимізації.
Структура та обсяг роботи. Магістерська дисертація складається з вступу, п‟яти розділів та висновків.
У вступі подано загальну характеристику роботи, зроблено оцінку сучасного стану проблеми, обґрунтовано актуальність роботи, сформульовану мету і задачу дослідження, показано наукову новизну і практичну цінність виконаної роботи.
У першому розділі розглянуто існуючі алгоритми розв‟язання задачі оптимізації в неперервному просторі, їхні особливості, переваги та недоліки, їхні реалізації.
У другому розділі розглянуто алгоритм квіткового запилення для розв‟язання задачі оптимізації в неперервному просторі та запропоновано модифікацію існуючого алгоритму для його покращення і розв‟язання задачі багатокритеріальної оптимізації.
У третьому розділі наведено особливості реалізації розробленої системи.
У четвертому розділі проведено аналіз отриманих результатів та порівняння їх з результатами оригінального алгоритму.
У п’ятому розділі проведено результат науково-дослідної практики.
У висновках представленні результати проведеної роботи.
Робота представлена на 124 аркушах, містить посилання на список використаних літературних джерел.
Опис
Ключові слова
задача багатокритеріальної оптимізації, алгоритм квіткового запилення, ефективність за Парето, скаляризація, problem of multicriteria optimization, algorithm of flower pollination, efficiency by Pareto, scalarization, задача многокритериальной оптимизации, алгоритм цветочного опыления, эффективность по Парето, скаляризация
Бібліографічний опис
Місік, Д. С. Евристичний метод багатокритеріальної оптимізації : магістерська дис. : 123 Комп’ютерна інженерія. Спеціалізовані комп’ютерні системи / Місік Дмитро Сергійович. – Київ, 2018. – 99 с.