Евристичний метод багатокритеріальної оптимізації
| dc.contributor.advisor | Зорін, Юрій Михайлович | |
| dc.contributor.author | Місік, Дмитро Сергійович | |
| dc.date.accessioned | 2019-03-13T16:35:05Z | |
| dc.date.available | 2019-03-13T16:35:05Z | |
| dc.date.issued | 2018-12 | |
| dc.description.abstracten | Actuality of theme. With the development of modern technologies, it is necessary to quickly and efficiently solve complex mathematical problems. A lot of popularity receives optimization tasks. The problem of solving optimization tasks arises not only in the up-to-date computer technologies, but also in everyday human life. Very often these tasks are reduced to the optimization of an object by a group of criteria. For example, in several tasks in the economic sphere, it is necessary to maximize profit, but at the same time minimize costs. In the task of salesman should consider not only the distance from the start to the final point, but also the delays, costs, total travel time and certain other criteria. All these tasks can be formulated in the general case next: maximize/minimize several functions that are defined at a certain interval of decisions with a certain criterion of optimality. Such a set of problems is called the multicriteria problem of an optimal equation. It occupies an important place among the tasks of the theory of choice and decision-making. Each optimality parameter of a solution may conflict with another optimality parameter. Because of this, today there are many approaches to solving such problems and analyzing the optimality of the solution found. Therefore, creating a solution that can analyze a group of parameters and find a solution that satisfies each of the criteria is a complex task to date. The object of the study is the process of multicriteria optimization. The subject of the study is heuristic methods for solving the multicriteria optimization problem. The purpose of the work is to develop a new method for solving the multicriterial optimization problem characterized by higher speed and greater accuracy of solutions than known methods. Research methods. Methods of heuristic algorithms, methods of discrete mathematics, methods of investigation of operations, methods of combinatorial optimization are used in this work. Scientific novelty: • The existing optimization algorithms in the continuous space are analyzed, their disadvantages are compared with the algorithm of flower pollination; • The modification of the existing algorithm of flower pollination for solving the optimization problem in a continuous space is proposed; • A comparative analysis of the original algorithm and the modified algorithm of flower pollination for the solution of the multicriteria optimization problem has been performed. The practical value of the results obtained in the work consists in the fact that the developed modified algorithm allows to improve the process of multi-criteria optimization and improve the result in terms of accuracy and sustainability of the result. In addition, the algorithm has shown that it can solve the multicriterial optimization problem without any additional information other than what is necessary for the calculation of the target function. Only using the scalarization method applied for several functions it was brought to a form that allows solving the problem of multi-criteria optimization. Structure and scope of work. The master's thesis consists of an introduction, five chapters and conclusions. The introduction gives a general description of the work, assesses the current state of the problem, substantiates the relevance of the work, formulates the purpose and task of the study, shows the scientific novelty and practical value of the work performed. In the first section, existing algorithms for solving the problem of optimization in a continuous space, their features, advantages and disadvantages, and their implementation are considered. In the second section we consider the algorithm of flower pollination to solve the problem of optimization in a continuous space and proposed modification of the existing algorithm to improve it. The third section presents the peculiarities of the implementation of the developed system. In the fourth section, the analysis of the obtained results and comparison with the results of the original algorithm are carried out. In fifth section, the analysis of scientific research practice. The conclusions are presented by the results of the work. The work is presented on 124 sheets of paper, contains a link to the list of used literary sources. | uk |
| dc.description.abstractru | Актуальность темы. С развитием современных технологий становится необходимым быстрое и эффективное решение сложных математических задач. Особенно популярны задачи оптимизации. Проблема решения оптимизационных задач возникает не только в сверхсовременных компьютерных технологиях, но и в повседневной человеческой жизни. Очень часто эти задачи сводятся к оптимизации определенного объекта с группой критериев. Например, в ряде задач экономической области необходимо максимально увеличить прибыль, но при этом минимизировать расходы. В задачи о коммивояжере необходимо учесть не только расстояние от начального до конечного пункта, а и задержки, расходы, общее время переезда и некоторые другие критерии. Все эти задачи могут быть сформулированы в общем случае следующим образом: максимизировать/минимизировать несколько функций, определенные на некотором промежутке решений по нескольким критериям оптимальности. Такой ряд задач называется многокритериальные задачи оптимального уравнения. Эта задача занимает важное место среди задач теории выбора и принятия решений. Каждый параметр оптимальности определенного решения может конфликтовать с другим параметром оптимальности. Поэтому на сегодняшний день существует много подходов к решению такого ряда задач и анализа оптимальности найденного решения. Поэтому создание решения, которое может анализировать группу параметров и находить решение, удовлетворяющее каждому из критериев, является сложной задачей и по сегодняшний день. Объект исследования является процесс многокритериальной оптимизации. Предметом исследования является эвристические методы решения задачи многокритериальной оптимизации. Цель работы является разработка нового метода для решения задачи многокритериальной оптимизации, которая характеризуется более высоким быстродействием и большей точностью решений, чем известные методы. Методы исследования. В работе используются методы эвристических алгоритмов, методы дискретной математики, методы исследования операций, методы комбинаторной оптимизации. Научная новизна: • Проанализированы существующие алгоритмы оптимизации в непрерывном пространстве, показано их недостатки по сравнению с алгоритмом цветочного опыления; • Предложена модификация существующего алгоритма цветочного опыления для решения задачи оптимизации в непрерывном пространстве; • Выполнен сравнительный анализ оригинального алгоритма и модифицированного алгоритма цветочного опыления для решения задачи многокритериальной оптимизации. Практическая ценность полученных в работе результатов заключается в том, что разработан модифицированный алгоритм позволяет ускорить процесс многокритериальной оптимизации и улучшить результат в смысле точности и устойчивости результата. Кроме того, алгоритм показал, что способен решать задачу многокритериальной оптимизации без какой-либо дополнительной информации, кроме той, которая необходима для вычисления целевой функции. Только с помощью метода скаляризации нескольких функций был приведен к форме, что позволяет решать задачу многокритериальной оптимизации. Структура и объем работы. Магистерская диссертация состоит из введения, пяти глав и выводов. Во введении представлена общая характеристика работы, произведена оценка современного состояния проблемы, обоснована актуальность работы, сформулирована цель и задача исследования, показано научную новизну и практическую ценность выполненной работы. В первой главе рассмотрены существующие алгоритмы решения задачи оптимизации в непрерывном пространстве, их особенности, преимущества и недостатки, их реализации. Во второй главе рассмотрен алгоритм цветочного опыления для решения задачи оптимизации в непрерывном пространстве и предложены модификации существующего алгоритма для его улучшения. В третьей главе приведены особенности реализации разработанной системы. В четвертой главе проведен анализ полученных результатов и сравнение их с результатами оригинального алгоритма. В пятой главе проведен анализ научно-исследовательской практики. В выводах представлены результаты проведенной работы. Работа представлена на 124 листах, содержит ссылки на список использованных литературных источников. | uk |
| dc.description.abstractuk | Актуальність теми. З розвитком сучасних технологій стає необхідним швидкий та ефективний розв‟язок складних математичних задач. Особливо популярними є задачі оптимізації. Проблема розв‟язання оптимізаційних задач постає не лише в надсучасних комп‟ютерних технологіях, а і в повсякденному людському житті. Дуже часто ці задачі зводяться до оптимізації певного об‟єкту за групою критеріїв. Наприклад, в ряді задач економічної галузі необхідно максимально збільшити прибуток, але при цьому мінімізувати витрати. В задачі про комівояжера необхідно врахувати не лише відстань від початкового до кінцевого пункту, а і затримки, витрати, загальний час переїзду та певні інші критерії. Всі ці задачі можуть бути сформульовані в загальному випадку наступним чином: максимізувати/мінімізувати декілька функцій, що визначенні на певному проміжку розв‟язків з певним критерієм оптимальності. Такий ряд задач називається багатокритеріальною задачею оптимального рівняння. Вона займає важливе місце серед задач теорії вибору та прийняття рішень. Кожен параметр оптимальності певного розв‟язку може конфліктувати з іншим параметром оптимальності. Через це на сьогоднішній день існує багато підходів до розв‟язання такого ряду задач та аналізу оптимальності знайденого розв‟язку. Тому створення алгоритму, який може аналізувати групу параметрів та знаходити розв‟язок, що задовольняє кожному з критеріїв є складною задачею і на сьогоднішній день. Об’єкт дослідження є процес багатокритеріальної оптимізації. Предметом дослідження є евристичні методи розв‟язання задачі багатокритеріальної оптимізації. Мета роботи є розробка нового методу для розв‟язання задачі багатокритеріальної оптимізації, що характеризується вищою швидкодією та більшою точністю розв‟язків, ніж відомі методи. Методи дослідження. В роботі використовуються методи евристичних алгоритмів, методи дискретної математики, методи дослідження операцій, методи комбінаторної оптимізації. Наукова новизна: • Проаналізовано існуючі алгоритми оптимізації в неперервному просторі, показано їх недоліки в порівнянні з алгоритмом квіткового запилення; • Запропоновано модифікацію існуючого алгоритму квіткового запилення для розв‟язання задачі багатокритеріальної оптимізації; • Виконано порівняльний аналіз оригінального алгоритму та модифікованого алгоритму квіткового запилення для розв‟язання задачі багатокритеріальної оптимізації. Практична цінність отриманих в роботі результатів полягає в тому, що розроблений модифікований алгоритм дозволяє прискорити процес багатокритеріальної оптимізації та покращити результат в сенсі точності і сталості результату. Крім того, алгоритм показав що здатний розв‟язувати задачу багатокритеріальної оптимізації без будь-якої додаткової інформації, крім тої, що необхідна для обчислення цільової функції. Лише за допомогою методу скаляризації декількох функцій його було приведено до форми, що дозволяє розв‟язувати задачу багатокритеріальної оптимізації. Структура та обсяг роботи. Магістерська дисертація складається з вступу, п‟яти розділів та висновків. У вступі подано загальну характеристику роботи, зроблено оцінку сучасного стану проблеми, обґрунтовано актуальність роботи, сформульовану мету і задачу дослідження, показано наукову новизну і практичну цінність виконаної роботи. У першому розділі розглянуто існуючі алгоритми розв‟язання задачі оптимізації в неперервному просторі, їхні особливості, переваги та недоліки, їхні реалізації. У другому розділі розглянуто алгоритм квіткового запилення для розв‟язання задачі оптимізації в неперервному просторі та запропоновано модифікацію існуючого алгоритму для його покращення і розв‟язання задачі багатокритеріальної оптимізації. У третьому розділі наведено особливості реалізації розробленої системи. У четвертому розділі проведено аналіз отриманих результатів та порівняння їх з результатами оригінального алгоритму. У п’ятому розділі проведено результат науково-дослідної практики. У висновках представленні результати проведеної роботи. Робота представлена на 124 аркушах, містить посилання на список використаних літературних джерел. | uk |
| dc.format.page | 99 с. | uk |
| dc.identifier.citation | Місік, Д. С. Евристичний метод багатокритеріальної оптимізації : магістерська дис. : 123 Комп’ютерна інженерія. Спеціалізовані комп’ютерні системи / Місік Дмитро Сергійович. – Київ, 2018. – 99 с. | uk |
| dc.identifier.uri | https://ela.kpi.ua/handle/123456789/26722 | |
| dc.language.iso | uk | uk |
| dc.publisher.place | Київ | uk |
| dc.subject | задача багатокритеріальної оптимізації | uk |
| dc.subject | алгоритм квіткового запилення | uk |
| dc.subject | ефективність за Парето | uk |
| dc.subject | скаляризація | uk |
| dc.subject | problem of multicriteria optimization | uk |
| dc.subject | algorithm of flower pollination | uk |
| dc.subject | efficiency by Pareto | uk |
| dc.subject | scalarization | uk |
| dc.subject | задача многокритериальной оптимизации | uk |
| dc.subject | алгоритм цветочного опыления | uk |
| dc.subject | эффективность по Парето | uk |
| dc.subject | скаляризация | uk |
| dc.subject.udc | 044.77 | uk |
| dc.title | Евристичний метод багатокритеріальної оптимізації | uk |
| dc.type | Master Thesis | uk |
Файли
Контейнер файлів
1 - 1 з 1
Вантажиться...
- Назва:
- Misik_magistr.pdf
- Розмір:
- 1.98 MB
- Формат:
- Adobe Portable Document Format
- Опис:
Ліцензійна угода
1 - 1 з 1
Ескіз недоступний
- Назва:
- license.txt
- Розмір:
- 9.06 KB
- Формат:
- Item-specific license agreed upon to submission
- Опис: