DACS3: Embedding Individual Ant Behavior in Ant Colony System

Authors: Zulaiha Ali Othman, Helmi Md Rais, Abdul Razak Hamdan

Abstract:

Ants are fascinating creatures that demonstrate the ability to find food and bring it back to their nest. Their ability as a colony, to find paths to food sources has inspired the development of algorithms known as Ant Colony Systems (ACS). The principle of cooperation forms the backbone of such algorithms, commonly used to find solutions to problems such as the Traveling Salesman Problem (TSP). Ants communicate to each other through chemical substances called pheromones. Modeling individual ants- ability to manipulate this substance can help an ACS find the best solution. This paper introduces a Dynamic Ant Colony System with threelevel updates (DACS3) that enhance an existing ACS. Experiments were conducted to observe single ant behavior in a colony of Malaysian House Red Ants. Such behavior was incorporated into the DACS3 algorithm. We benchmark the performance of DACS3 versus DACS on TSP instances ranging from 14 to 100 cities. The result shows that the DACS3 algorithm can achieve shorter distance in most cases and also performs considerably faster than DACS.

Keywords: Dynamic Ant Colony System (DACS), TravelingSalesmen Problem (TSP), Optimization, Swarm Intelligent.

Digital Object Identifier (DOI): doi.org/10.5281/zenodo.1085425

References:

[1] M. Dorigo, V. Maniezzo, and A. Colorni, The Ant System: Optimization by a colony of cooperating agents, IEEE Transactions on Systems, Man and Cybernatics-Part B, vol. 26, no. 1, pp.1-13, 1996.
[2] M. Dorigo, and L. M. Gambardella, Ant Colony System: A Cooperative Learning Approach to the Traveling Salesman Problem, IEEE Transaction of Evolutionary Computation, vol.1, no 1, pp.53-66, 1997.
[3] Y. Li, and S. Gong, Dynamic ant colony optimization for TSP, Int J Adv Manuf Technol, vol. 22, pp. 528-533, July 2003.
[4] L. M. Gambardella, E. Taillard, and G. Agazzi, MACS-VRPTW: A Multiple Ant Colony System for Vehicle Routing Problems with Time Windows, Technical Report IDSIA (IDSIA-06-99), 1999.
[5] R. Montemanni, L. M. Gambardella, A. E. Rizzoli, and A. V. Donati, Ant colony system for a dynamic vehicle routing problem, Journal of Combinatorial Optimization, vol. 10, no. 4, pp. 327-343, December 2005.
[6] M. Dorigo, and K. Socha, An Introduction to Ant Colony Optimization, Book Chapter in Approximation Algorithms and Metaheuristic, CRC Press 2007.
[7] M. Dorigo, M. Birattari, and T. Stutzle, Ant Colony Optimization - Artificial Ants as a Computational Intelligence Technique, IEEE Computation Intelligent Magazine, 2006.
[8] M. Dorigo, E. Bonabeau, and G. Theraulaz, Ant algorithms and stigmergy, Journal of Future Generation Computer Systems, vol. 16, pp. 851 - 871, 2000.
[9] M. Dorigo, and K. Socha, An Introduction to Ant Colony Optimization, Technical Report IRIDIA 2006-010, April 2006.
[10] J-L. Deneubourg, S. Aron, S. Goss, and J.M. Pasteels, The selforganizing exploratory pattern of Argentine Ant, Journal of Insect Behavior, vol. 3, pp. 59-168, 1990.
[11] M. Dorigo, G. Di Caro and L. M. Gambardella, Ant Algorithms for Discrete Optimization. Journal of Artificial Life, vol. 5, no. 2x, pp. 137- 172, 1990.
[12] C. Anderson, and N. R. Franks, Teams in animal societies, Journal of Behavioral Ecology, vol. 12, no. 5, pp. 534-540, September 2000.
[13] L.M. Gambardella, and M. Dorigo, Ant-Q: A Reinforcement Learning Approach to the Traveling Salesman Problem. Proceedings of ML-95, Twelfth International Conference on Machine Learning, 1995, pp. 252- 260.
[14] T. St├╝tzle, and H. H. Hoos, MAX-MIN Ant System, Journal of Future Generation Computer Systems, vol. 16, no. 8, pp. 889-914, 2000.
[15] M. Fleischer, Foundation of Swarm Intelligence: From Principles to Practice, Conference on Swarming: Network Enabled C4ISR, January 2003.
[16] M. Dorigo, and G. Di Caro, The Ant Colony Optimization Meta- Heuristic, In D. Corne, M. Dorigo and F. Glover, editors, New Ideas in Optimization, McGraw-Hill, 1999, pp. 11-32.
[17] M. Gendreau, and J. Y. Potvin, Metaheuristic in Combinatorial Optimization, Annals of Operation Research, vol. 140, pp. 189-213, 2005.
[18] B. Fox, W. Xiang, and H. P. Lee, Industrial applications of the ant colony optimization algorithm, Int J Adv Manuf Technol, July 2005.
[19] E. Bonabeau, and C. Meyer, Swarm Intelligence: A Whole New Way to Think about Business, Harvard Business Review, May 2001.
[20] D. Gaertner, and K. Clark, On Optimal Parameters for Ant Colony Optimization algorithms, Proceedings of International Conference on Artificial.
[21] P. E. Merloti, Optimization Algorithms Inspired by Biological Ants and Swarm Behavior, San Diego State University, Artificial Intelligence Technical Report, CS550, San Diego, June 2004.
[22] C. Grosan, and A. Abraham, Stigmergic Optimization: Inspiration, Technologies and Perspectives. Studies in Computational Intelligence Journal, vol. 31, Springer Publishing 2006.
[23] H. Md Rais, Z.A. Othman and A. R. Hamdan, Improved Dynamic Ant Colony System (DACS) on Symetric Traveling Salesman Problem (TSP), International Conference on Intelligent and Advanced System (ICIAS 2007), November 2007.