Современные информационные технологии и IT-образование (Jun 2021)
Population-Based Algorithm for Solving the Traveling Salesman Problem
Abstract
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.
Keywords
