research-article

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

Authors:

Carsten WittAuthors Info & Claims

GECCO '10: Proceedings of the 12th annual conference on Genetic and evolutionary computation

Pages 63 - 70

https://doi.org/10.1145/1830483.1830493

Published: 07 July 2010 Publication History

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.

References

[1]

N. Attiratanasunthron and J. Fakcharoenphol. A running time analysis of an ant colony optimization algorithm for shortest paths in directed acyclic graphs. Information Processing Letters, 105(3):88--92, 2008.

Digital Library

[2]

B. Doerr, F. Neumann, D. Sudholt, and C. Witt. On the runtime analysis of the 1-ANT ACO algorithm. In H. Lipson, editor, GECCO, pages 33--40. ACM, 2007.

Digital Library

[3]

M. Dorigo and T. Stützle. Ant Colony Optimization. MIT Press, 2004.

Digital Library

[4]

S. Droste. A rigorous analysis of the compact genetic algorithm for linear functions. Natural Computing, 5(3):257--283, 2006.

Digital Library

[5]

S. Droste, T. Jansen, and I. Wegener. On the analysis of the (1+1) evolutionary algorithm. Theoretical Computer Science, 276:51--81, 2002.

Digital Library

[6]

W. J. Gutjahr and G. Sebastiani. Runtime analysis of ant colony optimization with best-so-far reinforcement. Methodology and Computing in Applied Probability, 10:409--433, 2008.

Digital Library

[7]

J. He and X. Yao. A study of drift analysis for estimating computation time of evolutionary algorithms. Natural Computing, 3(1):21--35, 2004.

Digital Library

[8]

C. Horoba and D. Sudholt. Running time analysis of ACO systems for shortest path problems. In Proc. of SLS '09, volume 5752 of LNCS, pages 76--91. Springer, 2009.

Digital Library

[9]

J. Jägersküpper and T. Storch. When the plus strategy outperforms the comma strategy and when not. In FOCI, pages 25--32. IEEE, 2007.

[10]

T. Jansen, K. A. De Jong, and I. Wegener. On the choice of the offspring population size in evolutionary algorithms. Evolutionary Computation, 13(4):413--440, 2005.

Digital Library

[11]

H. Mühlenbein. How genetic algorithms really work: mutation and hillclimbing. In Proc. of PPSN '92, pages 15--26. Elsevier, 1992.

[12]

F. Neumann, P. S. Oliveto, and C. Witt. Theoretical analysis of fitness-proportional selection: landscapes and efficiency. In F. Rothlauf, editor, GECCO, pages 835--842. ACM, 2009.

Digital Library

[13]

F. Neumann, D. Sudholt, and C. Witt. Analysis of different MMAS ACO algorithms on unimodal functions and plateaus. Swarm Intelligence, 3:35--68, 2009.

[14]

F. Neumann and C. Witt. Runtime analysis of a simple ant colony optimization algorithm. Algorithmica, 54(2):243--255, 2009.

Digital Library

[15]

P. S. Oliveto and C. Witt. Simplified drift analysis for proving lower bounds in evolutionary computation. Algorithmica, 2010. In press, http://dx.doi.org/10.1007/s00453-010-9387-z.

Digital Library

[16]

T. Stützle and H. H. Hoos. MAX-MIN ant system. Journal of Future Generation Computer Systems, 16:889--914, 2000.

Digital Library

[17]

D. Sudholt. Computational Complexity of Evolutionary Algorithms, Hybridizations, and Swarm Intelligence. PhD thesis, Technische Universität Dortmund, 2008.

[18]

D. Sudholt and C. Witt. Runtime analysis of a binary particle swarm optimizer. Theoretical Computer Science, 2010. In press, http://dx.doi.org/10.1016/j.tcs.2010.03.002.

Digital Library

[19]

Y. Zhou. Runtime analysis of an ant colony optimization algorithm for TSP instances. IEEE Transactions on Evolutionary Computation, 13(5):1083--1092, 2009.

Digital Library

Cited By

Adak SWitt C(2024)Runtime Analysis of a Multi-valued Compact Genetic Algorithm on Generalized OneMaxParallel Problem Solving from Nature – PPSN XVIII10.1007/978-3-031-70071-2_4(53-69)Online publication date: 7-Sep-2024
https://doi.org/10.1007/978-3-031-70071-2_4
Ajimakin ADevi V(2023)The Competing Genes Evolutionary Algorithm: Avoiding Genetic Drift Through Competition, Local Search, and Majority VotingIEEE Transactions on Evolutionary Computation10.1109/TEVC.2022.322903827:6(1678-1689)Online publication date: Dec-2023
https://doi.org/10.1109/TEVC.2022.3229038
Janett DLengler J(2023)Two-Dimensional Drift Analysis: Optimizing Two Functions Simultaneously Can Be HardTheoretical Computer Science10.1016/j.tcs.2023.114072(114072)Online publication date: Jul-2023
https://doi.org/10.1016/j.tcs.2023.114072
Show More Cited By

Index Terms

A few ants are enough: ACO with iteration-best update
1. Theory of computation
  1. Design and analysis of algorithms

Recommendations

Update Strength in EDAs and ACO: How to Avoid Genetic Drift
GECCO '16: Proceedings of the Genetic and Evolutionary Computation Conference 2016

We provide a rigorous runtime analysis concerning the update strength, a vital parameter in probabilistic model-building GAs such as the step size 1/K in the compact Genetic Algorithm (cGA) and the evaporation factor ρ in ACO. While a large update ...
Theory of swarm intelligence
GECCO Comp '14: Proceedings of the Companion Publication of the 2014 Annual Conference on Genetic and Evolutionary Computation

Social animals as found in fish schools, bird flocks, bee hives, and ant colonies are able to solve highly complex problems in nature. This includes foraging for food, constructing astonishingly complex nests, and evading or defending against predators. ...
Theory of Swarm Intelligence
GECCO Companion '15: Proceedings of the Companion Publication of the 2015 Annual Conference on Genetic and Evolutionary Computation

Social animals as found in fish schools, bird flocks, bee hives, and ant colonies are able to solve highly complex problems in nature. This includes foraging for food, constructing astonishingly complex nests, and evading or defending against predators. ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

GECCO '10: Proceedings of the 12th annual conference on Genetic and evolutionary computation

July 2010

1520 pages

ISBN:9781450300728

DOI:10.1145/1830483

General Chair:
Martin Pelikan
University of Missouri, USA
,
Program Chair:
Jürgen Branke
University of Warwick, Coventry, UK

Copyright © 2010 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

SIGEVO: ACM Special Interest Group on Genetic and Evolutionary Computation

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 07 July 2010

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Conference

GECCO '10

Sponsor:

SIGEVO

GECCO '10: Genetic and Evolutionary Computation Conference

July 7 - 11, 2010

Oregon, Portland, USA

Acceptance Rates

Overall Acceptance Rate 1,669 of 4,410 submissions, 38%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

34
Total Citations
View Citations
381
Total Downloads

Downloads (Last 12 months)20
Downloads (Last 6 weeks)2

Reflects downloads up to 29 Sep 2024

Other Metrics

View Author Metrics

Citations

Cited By

Adak SWitt C(2024)Runtime Analysis of a Multi-valued Compact Genetic Algorithm on Generalized OneMaxParallel Problem Solving from Nature – PPSN XVIII10.1007/978-3-031-70071-2_4(53-69)Online publication date: 7-Sep-2024
https://doi.org/10.1007/978-3-031-70071-2_4
Ajimakin ADevi V(2023)The Competing Genes Evolutionary Algorithm: Avoiding Genetic Drift Through Competition, Local Search, and Majority VotingIEEE Transactions on Evolutionary Computation10.1109/TEVC.2022.322903827:6(1678-1689)Online publication date: Dec-2023
https://doi.org/10.1109/TEVC.2022.3229038
Janett DLengler J(2023)Two-Dimensional Drift Analysis: Optimizing Two Functions Simultaneously Can Be HardTheoretical Computer Science10.1016/j.tcs.2023.114072(114072)Online publication date: Jul-2023
https://doi.org/10.1016/j.tcs.2023.114072
Aishwaryaprajna Rowe J(2023)The Voting Algorithm is Robust to Various Noise ModelsTheoretical Computer Science10.1016/j.tcs.2023.113844(113844)Online publication date: Mar-2023
https://doi.org/10.1016/j.tcs.2023.113844
Janett DLengler J(2022)Two-Dimensional Drift Analysis:Parallel Problem Solving from Nature – PPSN XVII10.1007/978-3-031-14721-0_43(612-625)Online publication date: 15-Aug-2022
https://doi.org/10.1007/978-3-031-14721-0_43
Benbaki RBenomar ZDoerr BKrawiec K(2021)A rigorous runtime analysis of the 2-MMASib on jump functionsProceedings of the Genetic and Evolutionary Computation Conference10.1145/3449639.3459350(4-13)Online publication date: 26-Jun-2021
https://dl.acm.org/doi/10.1145/3449639.3459350
Witt CCoello Coello C(2020)Theory of estimation-of-distribution algorithmsProceedings of the 2020 Genetic and Evolutionary Computation Conference Companion10.1145/3377929.3389888(1254-1282)Online publication date: 8-Jul-2020
https://dl.acm.org/doi/10.1145/3377929.3389888
Doerr BZheng W(2020)Sharp Bounds for Genetic Drift in Estimation of Distribution AlgorithmsIEEE Transactions on Evolutionary Computation10.1109/TEVC.2020.298736124:6(1140-1149)Online publication date: Dec-2020
https://doi.org/10.1109/TEVC.2020.2987361
Lengler JSudholt DWitt C(2020)The Complex Parameter Landscape of the Compact Genetic AlgorithmAlgorithmica10.1007/s00453-020-00778-4Online publication date: 4-Nov-2020
https://doi.org/10.1007/s00453-020-00778-4
Witt CAuger AStützle T(2019)Theory of estimation-of-distribution algorithmsProceedings of the Genetic and Evolutionary Computation Conference Companion10.1145/3319619.3323367(1197-1225)Online publication date: 13-Jul-2019
https://dl.acm.org/doi/10.1145/3319619.3323367
Show More Cited By

View Options

Get Access

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents