Підвищення ефективності прикладних алгоритмів комбінаторної оптимізації в інформаційних системах
Ескіз недоступний
Дата
2018
Автори
Красников, Сергій Олександрович
Науковий керівник
Назва журналу
Номер ISSN
Назва тому
Видавець
Анотація
Актуальність: Відомо що результат роботи будь-якого алгоритму залежить від налаштування його параметрів. Вони можуть покращити точність розв’язку, пришвидшити час роботи алгоритму. Підбір параметрів для алгоритмів є затратною з точки зору часу і може потребувати експертної групи для визначення найкращих параметрів алгоритму.
Задача комівояжера є однієї з найбільш поширених задач комбінаторної оптимізації, до яких можна звести і ряд інших проблем оптимізації. Такими проблемами, наприклад, є пошук оптимальних туристичних маршрутів, задача офіцера та оптимізація шляху для зварювання в електронних платах. Для розв’язування цієї задачі використовуються прикладні алгоритми комбінаторної оптимізації. Майже всі вони мають деяку кількість параметрів.
Саме тому дослідження налаштування параметрів алгоритмів для розв’язування задачі комівояжера є актуальним. Для цього потрібно розробити підхід до налаштування параметрів алгоритму для широкого кола задач.
Зв'язок роботи з науковими програмами, планами, темами. Робота виконувалась у філії кафедри автоматизованих систем обробки інформації та управління Національного технічного університету України «Київський політехнічний інститут ім. Ігоря Сікорського» у рамках науково-дослідницької теми Інституту кібернетики ім. В. М. Глушкова НАН України ВФ.180.11 «Розробити математичний апарат, орієнтований на створення інтелектуальних інформаційних технологій розв'язування проблем комбінаторної оптимізації та інформаційної безпеки» (2017-2021 рр.), що виконується за Постановою бюро Відділення інформатики НАН України від 23.06.2016 р. № 2.
Мета дослідження – розробити формальний підхід до підвищення ефективності прикладних алгоритмів комбінаторної оптимізації та апробувати його при розв’язуванні відомих задач комівояжера.
Для досягнення цієї мети необхідно виконати наступні завдання:
− виконати огляд відомих результатів для алгоритмів комбінаторної оптимізації в області налаштування параметрів для алгоритму;
− виконати формалізацію задачі знаходження оптимальних параметрів алгоритму в обмеженій сітці;
− розробити програмну реалізацію алгоритмів комбінаторної оптимізації, для яких буде відбуватись налаштування параметрів;
− провести експерименти налаштування параметрів алгоритму для набору задач;
− виконати аналіз отриманих результатів експерименту.
Об’єкт дослідження – процеси розв’язку задач комбінаторної оптимізації.
Предмет дослідження – моделі та методи налаштування параметрів алгоритмів комбінаторної оптимізації.
Наукова новизна одержаних результатів полягає в розробці формалізованого підходу до налаштування параметрів прикладних алгоритмів комбінаторної оптимізації, який дозволяє підвищити точність розв’язку алгоритмів.
Публікації. Матеріали роботи опубліковані у журналі «Вчені записки Таврійського національного університету імені В.І. Вернадського Серія: Технічні науки», збірнику статей за XL Міжнародної науково-практичної конференції: «Розвиток науки в XXI столітті» та на Всеукраїнській науково-практичній конференції молодих вчених та студентів «Інформаційні системи та технології управління» (ІСТУ-2018).
Опис
Ключові слова
алгоритми комбінаторної оптимізації, задача комівояжера, параметри алгоритмів, налаштування параметрів, стохастичний локальний пошук, combinatorial optimization algorithm, the travelling salesman problem, algorithm parameters, setting parameters, stochastic local search
Бібліографічний опис
Красников, С. О. Підвищення ефективності прикладних алгоритмів комбінаторної оптимізації в інформаційних системах : магістерська дис. : 126 Інформаційні системи та технології / Красников Сергій Олександрович. – Київ, 2018. – 93 с.