nach oben

Swarm Intelligence

Erschienen in:

01.12.2012

The dynamics of ant colony optimization algorithms applied to binary chains

verfasst von: Claudio Iacopino, Phil Palmer

Erschienen in: Swarm Intelligence | Ausgabe 4/2012

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config

KI-gestützte Suche

Aus

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.

Vorheriger Artikel Set-based particle swarm optimization applied to the multidimensional knapsack problem

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

Jetzt informieren

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. CrossRef

Bonabeau, E. (1997). Flexibility at the edge of chaos: a clear example from foraging in ants. Acta Biotheoretica, 45(1), 29–50. CrossRef

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. MathSciNetMATHCrossRef

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. CrossRef

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. CrossRef

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. CrossRef

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. CrossRef

Gutjahr, W. J. (2000). A graph-based ant system and its convergence. Future Generations Computer Systems, 16(9), 873–888. CrossRef

Gutjahr, W. J. (2002). ACO algorithms with guaranteed convergence to the optimal solution. Information Processing Letters, 82(3), 145–153. MathSciNetMATHCrossRef

Gutjahr, W. J. (2006). On the finite-time dynamics of ant colony optimization. Methodology and Computing in Applied Probability, 8(1), 105–133. MathSciNetMATHCrossRef

Gutjahr, W. J. (2008). First steps to the runtime complexity analysis of ant colony optimization. Computers & Operations Research, 35(9), 2711–2727. MathSciNetMATHCrossRef

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. CrossRef

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. CrossRef

Merkle, D., & Middendorf, M. (2002). Modeling the dynamics of ant colony optimization. Evolutionary Computation, 10(3), 235–262. CrossRef

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. CrossRef

Nicolis, S., & Deneubourg, J. (1999). Emerging patterns and food recruitment in ants: an analytical study. Journal of Theoretical Biology, 198(4), 575–592. CrossRef

Nicolis, S., & Dussutour, A. (2011). Resource exploitation strategies in the presence of traffic between food sources. Biosystems, 103(1), 73–78. CrossRef

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. CrossRef

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. CrossRef

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. CrossRef

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. CrossRef

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. CrossRef

Titel: The dynamics of ant colony optimization algorithms applied to binary chains
verfasst von: Claudio Iacopino
Phil Palmer
Publikationsdatum: 01.12.2012
Verlag: Springer US
Erschienen in: Swarm Intelligence / Ausgabe 4/2012
Print ISSN: 1935-3812
Elektronische ISSN: 1935-3820
DOI: https://doi.org/10.1007/s11721-012-0074-3

Springer Professional

Abstract

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Wirtschaft"

Springer Professional "Technik"