Abstract
In the last decade Ant Colony Optimization (ACO) algorithms have received increasing attention due to their flexibility and adaptability to different applications. Despite these advantages, their design and analysis are still critical issues; research on formal methods could increase the reliability of these systems and extend their applications to critical scenarios such as space or military.
This paper aims at exploring the potential of formal modelling techniques already developed for studying dynamical systems. The benefits of these techniques are shown in the analysis of a generic ACO algorithm applied to problems modelled as binary chains. The theoretical model developed is able to give new insights on the overall system dynamics, predicting the system long-term behaviours and the influence of specific parameters on such behaviours. This paper first offers a complete stability analysis for a basic problem providing an easy description of the key concepts before generalizing the model to problems of n nodes, allowing its application to real problems. The picture of the system dynamics is then completed by a convergence time analysis, which is necessary to draw sensible conclusions.
Similar content being viewed by others
Explore related subjects
Discover the latest articles, news and stories from top researchers in related subjects.References
Blum, C., & Dorigo, M. (2004). The hyper-cube framework for ant colony optimization. IEEE Transactions on Systems, Man, and Cybernetics. Part B. Cybernetics, 34(2), 1161–1172.
Bonabeau, E. (1997). Flexibility at the edge of chaos: a clear example from foraging in ants. Acta Biotheoretica, 45(1), 29–50.
Brueckner, S. (2000). Return from the ant. Synthetic ecosystems for manufacturing control. Ph.D. thesis, Humboldt-Universität, Berlin.
Dorigo, M., & Blum, C. (2005). Ant colony optimization theory: a survey. Theoretical Computer Science, 344(2–3), 243–278.
Dorigo, M., & Stützle, T. (2001). An experimental study of the simple ant colony optimization algorithm. In Artificial intelligence series: Advances in fuzzy systems and evolutionary computation (pp. 253–258). Dallas: World Scientific and Engineering Society Press.
Dorigo, M., Maniezzo, V., & Colorni, A. (1996). Ant system: optimization by a colony of cooperating agents. IEEE Transactions on Systems, Man and Cybernetics. Part B, 26(1), 29–41.
Duarte, L., Foss, L., Wagner, F., & Heimfarth, T. (2010). Model checking the ant colony optimisation. In Distributed, parallel and biologically inspired systems (pp. 221–232). Berlin: Springer.
Fernandes, C., Ramos, V., & Rosa, A. C. (2007). Stigmergic optimization in dynamic binary landscapes. In Proceedings of the 2007 ACM symposium on applied computing (pp. 747–748). New York: ACM.
Gabbai, J., Yin, H., Wright, W., & Allinson, N. (2005). Self-organization, emergence and multi-agent systems. In International conference on neural networks and brain. ICNN&B’05 (Vol. 3, pp. 1858–1863). Piscataway: IEEE Press.
Gutjahr, W. (2007). Mathematical runtime analysis of ACO algorithms: survey on an emerging issue. Swarm Intelligence, 1(1), 59–79.
Gutjahr, W. J. (2000). A graph-based ant system and its convergence. Future Generations Computer Systems, 16(9), 873–888.
Gutjahr, W. J. (2002). ACO algorithms with guaranteed convergence to the optimal solution. Information Processing Letters, 82(3), 145–153.
Gutjahr, W. J. (2006). On the finite-time dynamics of ant colony optimization. Methodology and Computing in Applied Probability, 8(1), 105–133.
Gutjahr, W. J. (2008). First steps to the runtime complexity analysis of ant colony optimization. Computers & Operations Research, 35(9), 2711–2727.
Huang, H., Wu, C., & Hao, Z. (2009). A pheromone-rate-based analysis on the convergence time of ACO algorithm. IEEE Transactions on Systems, Man and Cybernetics. Part B. Cybernetics, 39(4), 910–923.
Kong, M., & Tian, P. (2005). A binary ant colony optimization for the unconstrained function optimization problem. In Computational intelligence and security (Vol. 3801, pp. 682–687). Berlin: Springer.
Merkle, D., & Middendorf, M. (2002). Modeling the dynamics of ant colony optimization. Evolutionary Computation, 10(3), 235–262.
Meyer, B. (2004). Convergence control in ACO. In Genetic and evolutionary computation conference (GECCO), Seattle, WA. Berlin: Springer, late-breaking paper.
Meyer, B. (2008). A tale of two wells: noise-induced adaptiveness in self-organized systems. In Second IEEE international conference on self-adaptive and self-organizing systems, 2008. SASO’08 (pp. 435–444). Los Alamitos: IEEE Computer Society.
Nicolis, S., & Deneubourg, J. (1999). Emerging patterns and food recruitment in ants: an analytical study. Journal of Theoretical Biology, 198(4), 575–592.
Nicolis, S., & Dussutour, A. (2011). Resource exploitation strategies in the presence of traffic between food sources. Biosystems, 103(1), 73–78.
Parunak, H. V. D., Sauter, J., & Clark, S. (1998). Toward the specification and design of industrial synthetic ecosystems. In Proceedings of the 4th international workshop on intelligent agents IV, agent theories, architectures, and languages, ATAL’97 (pp. 45–59). London: Springer.
Purkayastha, P., & Baras, J. S. (2007). Convergence results for ant routing algorithms via stochastic approximation and optimization. In 2007 46th IEEE conference on decision and control (pp. 340–345). Piscataway: IEEE Press.
Reif, F. (1965). Fundamentals of statistical and thermal physics. New York: McGraw-Hill.
Solé, R. V., Miramontes, O., & Goodwin, B. C. (1993). Oscillations and chaos in ant societies. Journal of Theoretical Biology, 161(3), 343–357.
Stützle, T., & Dorigo, M. (2002). A short convergence proof for a class of ACO algorithms. IEEE Transactions on Evolutionary Computation, 6(4), 358–365.
Wei, K., Tuo, H., & Jing, Z. (2010). Improving binary ant colony optimization by adaptive pheromone and commutative solution update. In 2010 IEEE fifth international conference on bio-inspired computing: theories and applications (BIC-TA) (pp. 565–569). Piscataway: IEEE Press.
Yang, Z., Huang, H., Cai, Z., & Qin, Y. (2010). A theoretical framework for runtime analysis of ant colony optimization. In 2010 international conference on machine learning and cybernetics (ICMLC) (Vol. 4, pp. 1817–1822). Piscataway: IEEE Press.
Acknowledgements
This work is co-funded by the Surrey Space Centre (SSC) of the University of Surrey, the Surrey Satellite Technology Ltd (SSTL) and the Operations Centre of the European Space Agency (ESA/ESOC).
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Iacopino, C., Palmer, P. The dynamics of ant colony optimization algorithms applied to binary chains. Swarm Intell 6, 343–377 (2012). https://doi.org/10.1007/s11721-012-0074-3
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s11721-012-0074-3