A few ants are enough: ACO with iteration-best update
Date
2010
Authors
Neumann, F.
Sudholt, D.
Witt, C.
Editors
Pelikan, M.
Branke, J.
Branke, J.
Advisors
Journal Title
Journal ISSN
Volume Title
Type:
Conference paper
Citation
Proceedings of the 12th annual conference on Genetic and evolutionary computation (GECCO'10), held in Portland, Oregon, USA 2010: pp.63-70
Statement of Responsibility
Frank Neumann, Dirk Sudholt and Carsten Witt
Conference Name
Genetic and Evolutionary Computation Conference (12th : 2010 : Portland, Oregon)
Abstract
Ant colony optimization (ACO) has found many applications in different problem domains. We carry out a first rigorous runtime analysis of ACO with iteration-best update, where the best solution in the each iteration is reinforced. This is similar to comma selection in evolutionary algorithms. We compare ACO to evolutionary algorithms for which it is well known that an offspring size of (log n), n the problem dimension, is necessary to optimize even simple functions like OneMax. In sharp contrast, ACO is efficient on OneMax even for the smallest possible number of two ants. Remarkably, this only holds if the pheromone evaporation rate is small enough; the collective memory of many ants stored in the pheromones makes up for the small number of ants. We further prove an exponential lower bound for ACO with iteration-best update that depends on a trade-off between the number of ants and the evaporation rate.
School/Discipline
Dissertation Note
Provenance
Description
Access Status
Rights
Copyright 2010 ACM