A few ants are enough: ACO with iteration-best update

Simple item page
dc.contributor.authorNeumann, F.
dc.contributor.authorSudholt, D.
dc.contributor.authorWitt, C.
dc.contributor.conferenceGenetic and Evolutionary Computation Conference (12th : 2010 : Portland, Oregon)
dc.contributor.editorPelikan, M.
dc.contributor.editorBranke, J.
dc.date.issued2010
dc.description.abstractAnt 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.
dc.description.statementofresponsibilityFrank Neumann, Dirk Sudholt and Carsten Witt
dc.identifier.citationProceedings of the 12th annual conference on Genetic and evolutionary computation (GECCO'10), held in Portland, Oregon, USA 2010: pp.63-70
dc.identifier.doi10.1145/1830483.1830493
dc.identifier.isbn9781450300728
dc.identifier.orcidNeumann, F. [0000-0002-2721-3618]
dc.identifier.urihttp://hdl.handle.net/2440/65688
dc.language.isoen
dc.publisherACM Press
dc.publisher.placeNew York
dc.rightsCopyright 2010 ACM
dc.source.urihttps://doi.org/10.1145/1830483.1830493
dc.subjectAnt Colony Optimization
dc.subjectIteration-Best Update
dc.subjectRuntime Analysis
dc.subjectTheory
dc.titleA few ants are enough: ACO with iteration-best update
dc.typeConference paper
pubs.publication-statusPublished

Files

Collections

Computer Science publications