THE USE OF ANT OPTIMIZATION ALGORITHM IN THE SALESMAN PROBLEM
Keywords:Travelling Salesman Problem, Ant Colony Optimization, Ant Colony System, Max-Min Ant System, software implementation of algorithms
A comparative analysis of three algorithms for solving the salesman problem is performed. These algorithms are Ant Colony Optimization (ASO) and its modifications: Ant Colony System (ACS) and Max-Min Ant System (MMAS). For this purpose, a software implementation of these three ant algorithms has been developed, which simulate the natural behavior of forage ants in finding the shortest path to deliver food to the anthill. The possibilities of the developed computer program are described. The results of a computer experiment are given on a specific example. The program allows you to visualize the shortest route found by each ant algorithm. A comparative analysis of the results, conclusions about the advantages and disadvantages of the considered ant algorithms.
Dorigo, M., Stützle, T., Ant Colony Optimization. MIT Press, Cambridge, MA, 2004, 305 p.
Dorigo M., Gambardella L. M., Ant colony system: A cooperative learning approach
to the traveling salesman problem. IEEE Transactions on Evolutionary Computation,
v. 1, 1997, p. 53–66.
Stützle T., H. H. Hoos., MAX–MIN Ant System. Future Generation Computer Systems, v. 16, 2000, p. 889-914.