Please use this identifier to cite or link to this item:
https://hdl.handle.net/2440/65688
Citations | ||
Scopus | Web of ScienceĀ® | Altmetric |
---|---|---|
?
|
?
|
Type: | Conference paper |
Title: | A few ants are enough: ACO with iteration-best update |
Author: | Neumann, F. Sudholt, D. Witt, C. |
Citation: | Proceedings of the 12th annual conference on Genetic and evolutionary computation (GECCO'10), held in Portland, Oregon, USA 2010: pp.63-70 |
Publisher: | ACM Press |
Publisher Place: | New York |
Issue Date: | 2010 |
ISBN: | 9781450300728 |
Conference Name: | Genetic and Evolutionary Computation Conference (12th : 2010 : Portland, Oregon) |
Editor: | Pelikan, M. Branke, J. |
Statement of Responsibility: | Frank Neumann, Dirk Sudholt and Carsten Witt |
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. |
Keywords: | Ant Colony Optimization Iteration-Best Update Runtime Analysis Theory |
Rights: | Copyright 2010 ACM |
DOI: | 10.1145/1830483.1830493 |
Published version: | http://dx.doi.org/10.1145/1830483.1830493 |
Appears in Collections: | Aurora harvest Computer Science publications |
Files in This Item:
There are no files associated with this item.
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.