English
 
Help Privacy Policy Disclaimer
  Advanced SearchBrowse

Item

ITEM ACTIONSEXPORT

Released

Book Chapter

Computational Complexity of Ant Colony Optimization and Its Hybridization with Local Search

MPS-Authors
/persons/resource/persons45115

Neumann,  Frank
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

External Resource
No external resources are shared
Fulltext (restricted access)
There are currently no full texts shared for your IP range.
Fulltext (public)
There are no public fulltexts stored in PuRe
Supplementary Material (public)
There is no public supplementary material available
Citation

Neumann, F., Sudholt, D., & Witt, C. (2009). Computational Complexity of Ant Colony Optimization and Its Hybridization with Local Search. In C. P. Lim, L. C. Jain, & S. Dehuri (Eds.), Innovations in Swarm Intelligence (pp. 91-120). Berlin: Springer.


Cite as: https://hdl.handle.net/11858/00-001M-0000-000F-181F-9
Abstract
he computational complexity of ant colony optimization (ACO) is a new and rapidly growing research area. The finite-time dynamics of ACO algorithms is assessed with mathematical rigor using bounds on the (expected) time until an ACO algorithm finds a global optimum. We review previous results in this area and introduce the reader into common analysis methods. These techniques are then applied to obtain bounds for different ACO algorithms on classes of pseudo-Boolean problems. The resulting runtime bounds are further used to clarify important design issues from a theoretical perspective. We deal with the question whether the current best-so-far solution should be replaced by new solutions with the same quality. Afterwards, we discuss the hybridization of ACO with local search and present examples where introducing local search leads to a tremendous speed-up and to a dramatic loss in performance, respectively.