Остання редакція: 2019-05-17
Анотація
Анотація. У даній роботі розглядається гібридний генетичний алгоритм, який використовує аналоги еволюційних механізмів (спадкування, мутації та природного відбору) та локальну 2-opt евристику для пошуку квазіоптимального розв’язку NP-повної задачі комівояжера.
HYBRID GENETIC ALGORITHM FOR SOLVING THE TRAVELLING SALESMAN PROBLEM
Abstract. In this paper has been considered a hybrid genetic algorithm, which uses analogues of evolutionary mechanisms (inheritance, mutation and natural selection) and local 2-opt heuristic, to search for a quasi-optimal solution of the NP-complete travelling salesman problem.
Ключові слова
Посилання
1. Рутковская Д. Нейронные сети, генетические алгоритмы и нечеткие системы / Д. Рутковская, М. Пилиньский, Л. Рутковский. – М.: Горячая линия-Телеком, 2004. – 452 с.
2. Іванов Ю.Ю. Методи штучного інтелекту та наука про дані: лекції, алгоритми та задачі / Ю.Ю. Іванов. – 2018. – 110 с.
3. Whitley D. A Genetic Algorithm Tutorial / D. Whitley // Statistics and Computing. – Springer Netherlands, 1994. – V. 4. – P. 65-85.
4. Genetic Local Search Algorithms for the Traveling Salesman Problem [Web Resource] / N. Ulder, E. Aarts, H.-J. Bandelt, P. van Laarhoven, E. Pesch // Parallel Problem Solving from Nature. – Springer, 1990. – P. 109-116. – Access mode: http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.473.581 &rep=rep1&type=pdf.
5. Shujia L. A Powerful Genetic Algorithm for Traveling Salesman Problem [Web Resource] / L. Shujia. – Guangzhou, 2012. – 5 p. – Access mode: https://arxiv.org/pdf/1402.4699.pdf.
6. Keresztury B. Genetic Algorithms and the Traveling Salesman Problem / B. Keresztury. – Budapest: Eötvös Loránd University, Department of Operations Research, 2017. – 50 p.
7. Lin S. An Effective Heuristic Algorithm for the Traveling-Salesman Problem / Operations Research // S. Lin, B.W. Kernighan. – 1973. – № 21. – 498-516.