An Improved Ant Colony Algorithm Applied in the TSP Problem

Abstract:

Ant colony algorithm is a kind of intelligent algorithm imitating the group behavior of ants. The positive feedback mechanism is not only its advantage which makes the ant colony algorithm quickly converge to optimal solutions of a problem, but also its defect which makes it easy to fall into the local optimal solutions. ACS and MMAS are the two typically improved ant algorithms by introducing the pseudo random probability selection rule and maximum-minimum pheromone restriction rule to accelerate the converging speed of this algorithm and avoid falling into local optimal solutions. At present, there is no algorithm put forward to improve the algorithm using the effect of the heuristic information. This paper presents an improved ant colony algorithm based on the heuristic information of direction, and provides a new idea for the study on the improved ant colony algorithm.

• Periodical: Applied Mechanics and Materials (Volumes 380-384)
• Pages: 1738-1741
• DOI: https://doi.org/10.4028/www.scientific.net/AMM.380-384.1738
• Online since: August 2013
• Authors: Meng Lan Wang
• Keywords: ACS, Ant Colony Algorithm (ACA), Heuristic Information of Direction, MMAS, Positive Feedback Mechanism

References

[1] Wang DingWei., Intelligent optimization methods. Beijing: Higher Education Press, (2007).

[2] DuanHai Bin, The principle of ant colony algorithm and its application . Beijing: Science Press, (2005).

[3] Dorigo M, Cgmbardella L M, Ant colony system: A cooperative learning approach to the traveling salesman problem, IEEE Trans on Evolutionary Computation, 1997, 1(1) : 53-66.

DOI: 10.1109/4235.585892

[4] Colorm A, Dorigo M, Minieaao V, Distributed optimization by ant：colonies, Proc of the First European Conf on Artificial Life, 1991. Paris: France Elsevier Publishing, p.134–142.

[5] Gutin, G.; Punnen, A. P, The Traveling Salesman Problem and its Variations, Springer, (2006).

[6] Johnson, D. S.; McGeoch, L. A. The Traveling Salesman Problem: A Case Study in Local Optimization, in Aarts, E. H. L.; Lenstra, J. K., Local Search in Combinatorial Optimization, John Wiley and Sons Ltd, 1997, p.215–310.

DOI: 10.2307/j.ctv346t9c.13

[7] Lawler, E. L.; Lenstra, J. K.; Rinnooy Kan, A. H. G.; Shmoys, D. B. The Traveling Salesman Problem: A Guided Tour of Combinatorial Optimization, John Wiley & Sons, (1985).

DOI: 10.1002/net.3230180309

[8] MacGregor, J. N.; Ormerod, T.  Human performance on the traveling salesman problem, Perception & Psychophysics, 1996, 58 (4): 527–539.

DOI: 10.3758/bf03213088

[9] Paola Pellegrini, Daniela Favaretto, Elena Moretti. Exploration in Stochastic Algorithms: An Application on MAX – MIN Ant System. Nature Inspired Cooperative Strategies for Optimization (NICSO 2008) Studies in Computational Intelligence, 2009, 236: 1-13.

DOI: 10.1007/978-3-642-03211-0_1