Підвищення ефективності прикладних алгоритмів комбінаторної оптимізації в інформаційних системах
| dc.contributor.advisor | Гуляницький, Леонід Федорович | |
| dc.contributor.author | Красников, Сергій Олександрович | |
| dc.date.accessioned | 2019-02-21T18:53:32Z | |
| dc.date.available | 2019-02-21T18:53:32Z | |
| dc.date.issued | 2018 | |
| dc.description.abstracten | Relevance: It is known that the result of any algorithm depends on the setting of its parameters. They can improve the accuracy of the solution, accelerate the time of the algorithm. Selection of parameters for algorithms is costly in terms of time and may require an expert group to determine the best parameters of the algorithm. The traveling salesman problem is one of the most common combinatorial optimization problem, which can be reduced to a number of other optimization problems. Such problems are, for example, the search for optimal tourist routes, the task of the officer and the optimization of the path for welding in electronic circuits. Applied algorithms for combinatorial optimization are used to solve this problem. Almost all of them have a number of parameters. That is why the study of setting parameters of algorithms for solving the traveling salesman problem is relevant. To do this, you need to develop an approach to configuring algorithm parameters for a wide range of tasks. Connection of the thesis with scientific programs, plans, topics. The thesis was written at the branch of The Department of Computer-aided management and data processing systems of the National Technical University of Ukraine «Igor Sikorsky Kyiv Polytechnic Institute» at the V. M. Glushkov Institute of Cybernetics of the National Academy of Sciences of Ukraine under the topic VF.180.11 «To develop a mathematical apparatus focused on the creation of intelligent information technologies for solving combinatorial optimization and information security problems» (2017-2021 biennium), which is executed by the Resolution of the Bureau of Informatics of the National Academy of Sciences of Ukraine from 23.06 .2016 р. № 2. The purpose of the study - is to develop a formal approach to increasing the efficiency of the applied algorithms of combinatorial optimization and to test it in solving known traveling salesman problem. To achieve this purpose, it is need to complete these tasks: − perform a review of known results for combinatorial optimization algorithms in the parameter setting area for the algorithm; − perform formalization of the problem of finding optimal parameters of the algorithm in a limited grid; − develop software implementation of combinatorial optimization algorithms, for which parameters will be configured; − conduct experiments to configure the parameters of the algorithm for a set of tasks; − perform an analysis of the results of the experiment. The object of study is processes of solving combinatorial optimization problems. The subject of study is models and methods for setting parameters of combinatorial optimization algorithms. The scientific novelty of the results obtained is to develop a formalized approach to configuring the parameters of the applied algorithms of combinatorial optimization, which allows you to increase the accuracy of the solution algorithm. Publications. Materials of the work were published in the journal «Scientists' notes of the Taurida National University named after VI Vernadsky Series: Technical Sciences», a collection of articles on the XL International Scientific and Practical Conference: «The Development of Science in the 21st Century» and at the All-Ukrainian Scientific and Practical Conference of Young Scientists and Students "Information Systems and Technologies of Management" (ISTM-2018). | uk |
| dc.description.abstractuk | Актуальність: Відомо що результат роботи будь-якого алгоритму залежить від налаштування його параметрів. Вони можуть покращити точність розв’язку, пришвидшити час роботи алгоритму. Підбір параметрів для алгоритмів є затратною з точки зору часу і може потребувати експертної групи для визначення найкращих параметрів алгоритму. Задача комівояжера є однієї з найбільш поширених задач комбінаторної оптимізації, до яких можна звести і ряд інших проблем оптимізації. Такими проблемами, наприклад, є пошук оптимальних туристичних маршрутів, задача офіцера та оптимізація шляху для зварювання в електронних платах. Для розв’язування цієї задачі використовуються прикладні алгоритми комбінаторної оптимізації. Майже всі вони мають деяку кількість параметрів. Саме тому дослідження налаштування параметрів алгоритмів для розв’язування задачі комівояжера є актуальним. Для цього потрібно розробити підхід до налаштування параметрів алгоритму для широкого кола задач. Зв'язок роботи з науковими програмами, планами, темами. Робота виконувалась у філії кафедри автоматизованих систем обробки інформації та управління Національного технічного університету України «Київський політехнічний інститут ім. Ігоря Сікорського» у рамках науково-дослідницької теми Інституту кібернетики ім. В. М. Глушкова НАН України ВФ.180.11 «Розробити математичний апарат, орієнтований на створення інтелектуальних інформаційних технологій розв'язування проблем комбінаторної оптимізації та інформаційної безпеки» (2017-2021 рр.), що виконується за Постановою бюро Відділення інформатики НАН України від 23.06.2016 р. № 2. Мета дослідження – розробити формальний підхід до підвищення ефективності прикладних алгоритмів комбінаторної оптимізації та апробувати його при розв’язуванні відомих задач комівояжера. Для досягнення цієї мети необхідно виконати наступні завдання: − виконати огляд відомих результатів для алгоритмів комбінаторної оптимізації в області налаштування параметрів для алгоритму; − виконати формалізацію задачі знаходження оптимальних параметрів алгоритму в обмеженій сітці; − розробити програмну реалізацію алгоритмів комбінаторної оптимізації, для яких буде відбуватись налаштування параметрів; − провести експерименти налаштування параметрів алгоритму для набору задач; − виконати аналіз отриманих результатів експерименту. Об’єкт дослідження – процеси розв’язку задач комбінаторної оптимізації. Предмет дослідження – моделі та методи налаштування параметрів алгоритмів комбінаторної оптимізації. Наукова новизна одержаних результатів полягає в розробці формалізованого підходу до налаштування параметрів прикладних алгоритмів комбінаторної оптимізації, який дозволяє підвищити точність розв’язку алгоритмів. Публікації. Матеріали роботи опубліковані у журналі «Вчені записки Таврійського національного університету імені В.І. Вернадського Серія: Технічні науки», збірнику статей за XL Міжнародної науково-практичної конференції: «Розвиток науки в XXI столітті» та на Всеукраїнській науково-практичній конференції молодих вчених та студентів «Інформаційні системи та технології управління» (ІСТУ-2018). | uk |
| dc.format.page | 93 с. | uk |
| dc.identifier.citation | Красников, С. О. Підвищення ефективності прикладних алгоритмів комбінаторної оптимізації в інформаційних системах : магістерська дис. : 126 Інформаційні системи та технології / Красников Сергій Олександрович. – Київ, 2018. – 93 с. | uk |
| dc.identifier.uri | https://ela.kpi.ua/handle/123456789/26496 | |
| dc.language.iso | uk | uk |
| dc.publisher.place | Київ | uk |
| dc.subject | алгоритми комбінаторної оптимізації | uk |
| dc.subject | задача комівояжера | uk |
| dc.subject | параметри алгоритмів | uk |
| dc.subject | налаштування параметрів | uk |
| dc.subject | стохастичний локальний пошук | uk |
| dc.subject | combinatorial optimization algorithm | uk |
| dc.subject | the travelling salesman problem | uk |
| dc.subject | algorithm parameters | uk |
| dc.subject | setting parameters | uk |
| dc.subject | stochastic local search | uk |
| dc.subject.udc | 519.8 | uk |
| dc.title | Підвищення ефективності прикладних алгоритмів комбінаторної оптимізації в інформаційних системах | uk |
| dc.type | Master Thesis | uk |