Comparison of the ant colony optimization algorithm and its two modifications

Abstract

The ant optimization algorithm is one of the effective modern algorithms for finding ap-proximate solutions of the salesman problem and similar problems of finding routes on graphs. The first version of this metaheuristic optimization algorithm was proposed by Marco Dorigo in 1992 [1]. After some time, several modifications of this algorithm have been proposed in the literature. The aim of the study is to conduct a comparative analysis of the ant optimization algo-rithm (Ant Colony Optimization, ASO) [1] and its most successful modifications: Ant Colony System (ACS) [2] and Max-Min Ant System (MMAS) [3]. To do this, the system features of information exchange in the ant colony during the search for food are analyzed. A step-by-step algorithm that simulates the natural behavior of forage ants in finding the shortest path to deliver food to the anthill is presented. A software implementation of the three listed ant algorithms for solving the travelling salesman problem has been developed. Through the interface window, you can enter the number of cities, the number of ants, and the maximum number of iterations, fix the settings of the algorithm and select any of the three algorithms. The program randomly locates cities and selects the starting city for each ant. The software product is multi-threaded, i.e. during the calculations the interface is not blocked, which allows you to control the process of program execution, namely: start, pause, stop, resume work. The results of the program are: vis-ualization of the shortest route found, the length of this route and the smallest iteration number, which achieves the shortest route. Comparative analysis of the results allowed us to draw the following conclusions: 1) With well-chosen algorithm settings, iterative methods usually give a result close to optimal, however, the number of iterations required for this may differ significantly. 2) The study of the travelling salesman problem by ant algorithms is experimental rather than theoretical. The result very much depends on the parameters of the algorithm settings, but the theoretical study of these dependencies remains relevant and unresolved.