Improved Variation Genetic Algorithm for Travelling Salesman Problem*
Askhat Diveev, Elizaveta Yu. Shmalko · 2024
The work presents original approach for solving the most popular computational traveling salesman problem. This is a modified genetic algorithm built on the basis of the principle of small variations of the basic solution. Its advantage is that the time of its operation does not depend on the complexity of the problem in this case on the number of cities, but only depends on the parameters of the algorithm. In this algorithm, a possible solution is not an ordered set of visited cities but a set of small variations of some one possible solution. This solution is called basic. It is determined by the researcher as the closest to the optimal solution. In this case, the basic solution is made by a greedy algorithm. During the search process, the basic solution changes to the best current solution found. Together with the genetic algorithm, an accurate overlap algorithm is used, which has polynomial complexity and improves solutions by eliminating the self-intersections of the path.