DACS3:Embedding Individual Ant Behavior in Ant Colony System
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.
[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.
[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.
@article{"International Journal of Information, Control and Computer Sciences:53450", author = "Zulaiha Ali Othman and Helmi Md Rais and Abdul Razak Hamdan", title = "DACS3:Embedding Individual Ant Behavior in Ant Colony System", 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), Traveling Salesmen Problem (TSP), Optimization, Swarm Intelligent.", volume = "3", number = "4", pages = "981-6", }
