Популяционный алгоритм решения задачи коммивояжера
Authors: Полупанова Е.Е. , Поляков А.С. 
Published: December 2024

В данной статье рассматривается популяционный гибридный алгоритм решения задачи коммивояжера, построенный с применением двух алгоритмов – генетического и алгоритма роя частиц, объединенных по принципу высокоуровневой гибридизации вложением – предполагает слабую связность рассматриваемых алгоритмов. В статье приводится постановка задачи коммивояжера и подробный разбор данной проблемы, относящейся к классу задач комбинаторной оптимизации. Приводятся аргументы в пользу выбора эвристического популяционного алгоритма решения данной проблемы: задача коммивояжера является NP-трудной и для неё не доказано существование алгоритма, который мог бы решить её за полиномиальное время, даже более того – неизвестно, существует ли эвристический подход, который будет давать гарантированную точность решения (данный вопрос до сих пор является открытым). Кроме того, задачу коммивояжера относят к классу трансвычислительных задач – при количестве городов больше 66 для нахождения точного решения методом полного перебора необходимо обработать более чем 1093бит информации. Следовательно, эффективные приближенные методы решения являются очень важными для данной задачи. Далее формулируется популяционный гибридный метод решения задачи коммивояжера в виде пошаговой структуры с подробным описанием каждого из шагов алгоритма. Затем приводится блок-схема полученного алгоритма. Далее рассмотрен результат работы программы: построенный граф, найденный маршрут коммивояжёра, его длина и последовательность городов. Также в статье приводятся разработанный пользовательский интерфейс с возможностью регулировки различных параметров алгоритма, позволяющий оптимизировать работу алгоритма. В последней части статьи приведены сравнительный анализ эффективности работы полученного алгоритма, а также сравнение точности разработанного популяционного гибридного алгоритма решения задачи коммивояжера с алгоритмом ближайшего соседа и муравьиным алгоритмом.

This article covers the population-based hybrid algorithm for solving the traveling salesman problem. The algorithm is built on two algorithms: the genetic algorithm and the particle swarm algorithm. Hybridization was performed using high level hybridization. This article presents a detailed problem statement of the traveling salesman problem. The traveling salesman problem belongs to the class of NP-complete combinatorial optimization problems. There are arguments in favor of heuristic algorithms for this problem – the traveling salesman problem is considered to be NP-hard, and existence of an algorithm that could solve it in polynomial time is not proven, even more it is not known whether there is a heuristic algorithm that will guarantee accuracy of its solution (this question is still open). In addition, the traveling salesman problem is classified as a transcomputational problem – if the number of cities is more than 66, it is necessary to process more than 1093 bits of information in order to find the exact solution using the exhaustive search. Therefore, effective approximate methods of solving this problem are very important. Further in the article, population-based hybrid algorithm is formulated in a form of a step-by-step structure with detailing the steps of the algorithm. Then a block diagram of the formulated algorithm is presented. In addition, the article presents the results of the program, the developed user interface with the ability to adjust various parameters of the algorithm, which allows us to change the performance of the algorithm. The last part of the article devoted to: comparative efficiency analysis of the formulated algorithm, comparison of the developed population-based hybrid algorithm with the nearest neighbor algorithm and the ant colony algorithm.