Study on the Ant Colony Optimization

Abstract:

As a hot spot of the algorithms of swarm intelligence, Ant Colony Optimization is proposed by an Italian scholar M.Dorigo by simulating the foraging actions of ants. This paper introduces the principle of this algorithm and its merit and demerit in great detail. It proposes an effective method named “four steps” based on others scholars’ “three steps” to choose the optimal combinational parameter of ant colony algorithms, then analyzes the improved algorithm of ant colony. At the same time, several kinds of algorithms are compared and analyzed in performance in solving TSP problems through the experiments. the optimal results can be obtained.

• Periodical: Key Engineering Materials (Volumes 467-469)
• Pages: 300-305
• DOI: https://doi.org/10.4028/www.scientific.net/KEM.467-469.300
• Online since: February 2011
• Authors: Xian Wen Luo
• Keywords: Ant Colony Optimization (ACO), Parameter Selection, Swarm Intelligence, TSP

References

[1] B Bullnheimer, R F Hartl, and C. C Strauss. A new rank-based version of the Ant System: computational study [J]. Central European Journal for Operations Research and Economics, 1999, 7(1): 25-38.

[2] T Stotzle, H Hoos. The MAX-MIN ant system and local search for the traveling salesman problem [C]. In: IEEE International Conference on Evolutionary Computation and Evolutionary Programming. Indianapolis, USA: IEEE Press, 1997. 309-314.

DOI: 10.1109/icec.1997.592327

[3] M. Dorigo, V. Maniezzo, and A Colorni. Positive feedback as a search strategy[R]. Politecnico di Milano, Italy, Technical Report: No. 91-016, (1991).

[4] M Dorigo. Optimiztion, Learning and Natural Algorithma [D]. Ph.D. thesis, Department of Electronics, Politecnico di Milano, IT, (1992).

[5] A Colorni, M Dorigo, V Maniezzo, et al. Distributed optimization by ant colonies [C]. In: Proceedings of the 1st European Conference on Artificial Life, 1991. 134-142.

[6] M Dorigo and LM Gambardella. Ant colony system: A cooperative learning approach to the traveling salesman problem [J]. IEEE Transactions on Evolutionary Computation, 1997, 1(1): 53-66.

DOI: 10.1109/4235.585892

[7] M. Dorigo, V. Maniezzo, and A. Colorni. The Ant System: Optimization by colony of cooperating agents [J]. IEEE Transactions on Systems, Man, and Cybernetics–Part B, 1996, 26(1): 29-41.

DOI: 10.1109/3477.484436

[8] G. D. Caro, M. Dorigo. Extending AntNet for Best-Effort Quality-of-Service Routing. First International Workshop on Ant Colony Optimization(ANTS'98), October 15-16, (1998).

[9] G. D. Caro, M. Dorigo. Antnet: distributed stigmergetic control for communication netw-orks. Journal of Artificial Intelligence Research, 1998, (9): 317-365.

DOI: 10.1613/jair.530

[10] Cz Leguizamon, Z. Michalewicz. A new version of ant system for subset problems. Proceeding of the 1999 Congress on Evolutionary Computation, Washington, DC: USA, 1999: 1459-1464.

DOI: 10.1109/cec.1999.782655

[11] R. Parra-Hernandez, N. Dimopoulos. On the performance of the ant colony system for solving the multidimensional knapsack problem. IEEE Pacific Rim Conference on Communications. Computers and Signal Processing, Victoria, Canada, 2003: 338-341.

DOI: 10.1109/pacrim.2003.1235786

[12] L. Schoofs, B. Naudts. Ant colonies are good at solving constraint satisfaction problems. Proceeding of the2000 Congress on Evolutionary Computation, LaJoIIa, CA, USA, 2000: 1190-1195.

DOI: 10.1109/cec.2000.870784

[13] C. Solnon. Ants Can Solve Constraint Satisfaction Problems. IEEE Transactions on Ev-olutionary Computation, 2002, (6): 347-357.

DOI: 10.1109/tevc.2002.802449