Article

On the runtime analysis of the 1-ANT ACO algorithm

Authors:

Benjamin Doerr,

Carsten WittAuthors Info & Claims

GECCO '07: Proceedings of the 9th annual conference on Genetic and evolutionary computation

Pages 33 - 40

https://doi.org/10.1145/1276958.1276964

Published: 07 July 2007 Publication History

Abstract

The runtime analysis of randomized search heuristics is a growing field where, in the last two decades, many rigorous results have been obtained. These results, however, apply particularly to classical search heuristics such as Evolutionary Algorithms (EAs) and Simulated Annealing. First runtime analyses of modern search heuristics have been conducted only recently w.r.t a simple Ant Colony Optimization (ACO) algorithm called 1-ANT. In particular, the influence of the evaporation factor in the pheromone update mechanism and the robustness of this parameter w.r.t the runtime behavior have been determined for the example function OneMax.This paper puts forward the rigorous runtime analysis of the 1-ANT on example functions, namely on the functions LeadingOnes and BinVal. With respect to EAs, such analyses have been essential to develop methods for the analysis on more complicated problems. The proof techniques required for the 1-ANT, unfortunately, differ significantly from those for EAs, which means that a new reservoir of methods has to be built up. Again, the influence of the evaporation factor is analyzed rigorously, and it is proved that its choice can be very crucial to allow efficient runtimes. Moreover, the analyses provide insight into the working principles of ACO algorithms and, in terms of their robustness, describe essential differences to other randomized search heuristics.

References

[1]

B. Doerr, N. Hebbinghaus, and F. Neumann. Speeding up evolutionary algorithms by restricted mutation operators. In Proc. of PPSN IX, volume 4193 of LNCS, pages 978--987, 2006.

Digital Library

[2]

M. Dorigo and C. Blum. Ant colony optimization theory: A survey. Theoretical Computer Science, 344:243--278, 2005.

Digital Library

[3]

M. Dorigo and T. Stutzle. Ant Colony Optimization. MIT Press, 2004.

Digital Library

[4]

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

[5]

W. Feller. An Introduction to Probability Theory and Its Applications, volume 1. Wiley, 3rd edition, 1968.

[6]

W. Feller. An Introduction to Probability Theory and Its Applications, volume 2. Wiley, 2nd edition, 1971.

[7]

O. Giel and I. Wegener. Evolutionary algorithms and the maximum matching problem. In Proc. of STACS '03, volume 2607 of LNCS, pages 415-426, 2003.

Digital Library

[8]

W. J. Gutjahr. A generalized convergence result for the graph-based ant system metaheuristic. Probability in the Engineering and Informational Sciences, 17:545--569, 2003.

Digital Library

[9]

W. J. Gutjahr. Mathematical runtime analysis of ACO algorithms: Survey on an emerging issue. Technical Report 2006-08, Department of Statistics and Decision Support Systems, University of Vienna, Austria, 2006.

[10]

W. J. Gutjahr. First steps to the runtime complexity analysis of Ant Colony Optimization. Computers and Operations Research, 2007. To appear.

Digital Library

[11]

D. Merkle and M. Middendorf. Modelling the dynamics of Ant Colony Optimization algorithms. Evolutionary Computation, 10:235--262, 2002.

Digital Library

[12]

R. Motwani and P. Raghavan. Randomized Algorithms. Cambridge University Press, 1995.

Digital Library

[13]

F. Neumann and I. Wegener. Randomized local search, evolutionary algorithms, and the minimum spanning tree problem. In Proc. of GECCO '04, volume 3102 of LNCS, pages 713--724, 2004.

[14]

F. Neumann and C. Witt. Ant Colony Optimization and the minimum spanning tree problem. In Electronic Colloquium on Computational Complexity (ECCC), 2006. Report No. 143.

[15]

F. Neumann and C. Witt. Runtime analysis of a simple Ant Colony Optimization algorithm. In Proc. of ISAAC '06, volume 4288 of LNCS, pages 618--627. Springer, 2006.

Digital Library

[16]

G. Rudolph. Convergence Properties of Evolutionary Algorithms. Verlag Dr. Kovač, 1997.

[17]

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

Digital Library

[18]

D. Sudholt. Crossover is provably essential for the Ising model on trees. In Proc. of GECCO '05, pages 1161--1167. ACM Press, 2005.

Digital Library

[19]

C. Witt. Worst-case and average-case approximations by simple randomized search heuristics. In Proc. of STACS '05, volume 3404 of LNCS, pages 44--56, 2005.

Digital Library

Cited By

Kergaßner MKeszocze OWanka RLi XHandl J(2024)Markov Chain-based Optimization Time Analysis of Bivalent Ant Colony Optimization for Sorting and LeadingOnesProceedings of the Genetic and Evolutionary Computation Conference10.1145/3638529.3654022(1488-1496)Online publication date: 14-Jul-2024
https://dl.acm.org/doi/10.1145/3638529.3654022
Mühlenthaler MRaß ASchmitt MWanka R(2021)Exact Markov chain-based runtime analysis of a discrete particle swarm optimization algorithm on sorting and OneMaxNatural Computing10.1007/s11047-021-09856-021:4(651-677)Online publication date: 13-Jun-2021
https://doi.org/10.1007/s11047-021-09856-0
Elbes MAlzubi SKanan TAl-Fuqaha AHawashin B(2019)A survey on particle swarm optimization with emphasis on engineering and network applicationsEvolutionary Intelligence10.1007/s12065-019-00210-zOnline publication date: 21-Feb-2019
https://doi.org/10.1007/s12065-019-00210-z
Show More Cited By

Index Terms

On the runtime analysis of the 1-ANT ACO algorithm
1. Theory of computation
  1. Design and analysis of algorithms

Recommendations

Runtime analysis of the 1-ANT ant colony optimizer

The runtime analysis of randomized search heuristics is a growing field where, in the last two decades, many rigorous results have been obtained. First runtime analyses of ant colony optimization (ACO) have been conducted only recently. In these studies ...
First steps to the runtime complexity analysis of ant colony optimization

The paper presents results on the runtime complexity of two ant colony optimization (ACO) algorithms: ant system, the oldest ACO variant, and GBAS, the first ACO variant for which theoretical convergence results have been established. In both cases, as ...
A Tight Runtime Analysis of the (1+(λ, λ)) Genetic Algorithm on OneMax
GECCO '15: Proceedings of the 2015 Annual Conference on Genetic and Evolutionary Computation

Understanding how crossover works is still one of the big challenges in evolutionary computation research, and making our understanding precise and proven by mathematical means might be an even bigger one. As one of few examples where crossover provably ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

GECCO '07: Proceedings of the 9th annual conference on Genetic and evolutionary computation

July 2007

2313 pages

ISBN:9781595936974

DOI:10.1145/1276958

General Chair:
Hod Lipson
Cornell University, USA

Copyright © 2007 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

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 07 July 2007

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Article

Conference

GECCO07

Sponsor:

GECCO07: Genetic and Evolutionary Computation Conference

July 7 - 11, 2007

London, England

Acceptance Rates

GECCO '07 Paper Acceptance Rate 266 of 577 submissions, 46%;

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

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

35
Total Citations
View Citations
483
Total Downloads

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

Reflects downloads up to 29 Sep 2024

Other Metrics

View Author Metrics

Citations

Cited By

Kergaßner MKeszocze OWanka RLi XHandl J(2024)Markov Chain-based Optimization Time Analysis of Bivalent Ant Colony Optimization for Sorting and LeadingOnesProceedings of the Genetic and Evolutionary Computation Conference10.1145/3638529.3654022(1488-1496)Online publication date: 14-Jul-2024
https://dl.acm.org/doi/10.1145/3638529.3654022
Mühlenthaler MRaß ASchmitt MWanka R(2021)Exact Markov chain-based runtime analysis of a discrete particle swarm optimization algorithm on sorting and OneMaxNatural Computing10.1007/s11047-021-09856-021:4(651-677)Online publication date: 13-Jun-2021
https://doi.org/10.1007/s11047-021-09856-0
Elbes MAlzubi SKanan TAl-Fuqaha AHawashin B(2019)A survey on particle swarm optimization with emphasis on engineering and network applicationsEvolutionary Intelligence10.1007/s12065-019-00210-zOnline publication date: 21-Feb-2019
https://doi.org/10.1007/s12065-019-00210-z
Raß ASchreiner JWanka R(2019)Runtime Analysis of Discrete Particle Swarm Optimization Applied to Shortest Paths ComputationEvolutionary Computation in Combinatorial Optimization10.1007/978-3-030-16711-0_8(115-130)Online publication date: 24-Apr-2019
https://dl.acm.org/doi/10.1007/978-3-030-16711-0_8
Doerr BKrejca MTakadama K(2018)Significance-based estimation-of-distribution algorithmsProceedings of the Genetic and Evolutionary Computation Conference10.1145/3205455.3205553(1483-1490)Online publication date: 2-Jul-2018
https://dl.acm.org/doi/10.1145/3205455.3205553
Friedrich TKötzing TMelnichenko A(2017)Analyzing search heuristics with differential equationsProceedings of the Genetic and Evolutionary Computation Conference Companion10.1145/3067695.3075607(313-314)Online publication date: 15-Jul-2017
https://dl.acm.org/doi/10.1145/3067695.3075607
Mühlenthaler MRaß ASchmitt MSiegling AWanka RIgel CSudholt DWitt C(2017)Runtime Analysis of a Discrete Particle Swarm Optimization Algorithm on Sorting and OneMaxProceedings of the 14th ACM/SIGEVO Conference on Foundations of Genetic Algorithms10.1145/3040718.3040721(13-24)Online publication date: 12-Jan-2017
https://dl.acm.org/doi/10.1145/3040718.3040721
Cleghorn CEngelbrecht A(2017)Firefly optimization: A study on frame invariance2017 IEEE Symposium Series on Computational Intelligence (SSCI)10.1109/SSCI.2017.8285251(1-6)Online publication date: Nov-2017
https://doi.org/10.1109/SSCI.2017.8285251
Hongyue WHan HShuling YYushan Z(2017)Running-Time Analysis of Particle Swarm Optimization with a Single Particle Based on Average GainSimulated Evolution and Learning10.1007/978-3-319-68759-9_42(515-527)Online publication date: 14-Oct-2017
https://doi.org/10.1007/978-3-319-68759-9_42
Pat A(2014)Ant Colony Optimization and hypergraph covering problems2014 IEEE Congress on Evolutionary Computation (CEC)10.1109/CEC.2014.6900294(1714-1720)Online publication date: Jul-2014
https://doi.org/10.1109/CEC.2014.6900294
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