THE USE OF ANT OPTIMIZATION ALGORITHM IN THE SALESMAN PROBLEM

Authors

  • Lidiia Boiko
  • Illia Liashenko

DOI:

https://doi.org/10.34185/1991-7848.itmm.2022.01.040

Keywords:

Travelling Salesman Problem, Ant Colony Optimization, Ant Colony System, Max-Min Ant System, software implementation of algorithms

Abstract

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.

References

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.

Published

2022-05-18

Issue

Section

Статті