research-article

Open access

A rigorous runtime analysis of the 2-MMAS_ib on jump functions: ant colony optimizers can cope well with local optima

Authors:

Benjamin DoerrAuthors Info & Claims

GECCO '21: Proceedings of the Genetic and Evolutionary Computation Conference

Pages 4 - 13

https://doi.org/10.1145/3449639.3459350

Published: 26 June 2021 Publication History

Abstract

Ant colony optimizers have been successfully used as general-purpose optimization heuristics. Due to the complicated nature of the random processes that describe the runs of ACO algorithms, the mathematical understanding of these algorithms is much less developed than that of other nature-inspired heuristics. In this first runtime analysis of a basic ACO algorithm on a classic multimodal benchmark, we analyze the runtime of the 2-MMAS_ib on jump functions. For moderate jump sizes k ≤ α₀ ln n, α₀ > 0 a constant, we prove a runtime of order O(√n/ρ), when the evaporation factor ρ satisfies ρ ≤ Cn^-1/2 ln(n)^-1 for a sufficiently small constant C. For ρ = Θ(n^-1/2 ln(n)^-1), we thus obtain a runtime of O(n ln(n)). This result shows that simple ACO algorithms can cope much better with local optima than many evolutionary algorithms, which need Ω(n^k) time.

References

[1]

Denis Antipov, Maxim Buzdalov, and Benjamin Doerr. 2021. Lazy parameter tuning and control: choosing all parameters randomly from a power-law distribution. In Genetic and Evolutionary Computation Conference, GECCO 2021. ACM.

Digital Library

[2]

Denis Antipov and Benjamin Doerr. 2020. Runtime analysis of a heavy-tailed (1 + (λ, λ)) genetic algorithm on jump functions. In Parallel Problem Solving From Nature, PPSN 2020, Part II. Springer, 545--559.

[3]

Denis Antipov, Benjamin Doerr, and Vitalii Karavaev. 2020. The (1 + (λ, λ)) GA is even faster on multimodal problems. In Genetic and Evolutionary Computation Conference, GECCO 2020. ACM, 1259--1267.

Digital Library

[4]

Anne Auger and Benjamin Doerr (Eds.). 2011. Theory of Randomized Search Heuristics. World Scientific Publishing.

[5]

Henry Bambury, Antoine Bultel, and Benjamin Doerr. 2021. Generalized jump functions. In Genetic and Evolutionary Computation Conference, GECCO 2021. ACM.

Digital Library

[6]

Leonora Bianchi, Marco Dorigo, Luca Maria Gambardella, and Walter J. Gutjahr. 2009. A survey on metaheuristics for stochastic combinatorial optimization. Natural Computing 8 (2009), 239--287.

Digital Library

[7]

Dogan Corus, Pietro S. Oliveto, and Donya Yazdani. 2017. On the runtime analysis of the Opt-IA artificial immune system. In Genetic and Evolutionary Computation Conference, GECCO 2017. ACM, 83--90.

Digital Library

[8]

Dogan Corus, Pietro S. Oliveto, and Donya Yazdani. 2018. Fast artificial immune systems. In Parallel Problem Solving from Nature, PPSN 2018, Part II. Springer, 67--78.

[9]

Duc-Cuong Dang, Tobias Friedrich, Timo Kötzing, Martin S. Krejca, Per Kristian Lehre, Pietro S. Oliveto, Dirk Sudholt, and Andrew M. Sutton. 2016. Escaping local optima with diversity mechanisms and crossover. In Genetic and Evolutionary Computation Conference, GECCO 2016. ACM, 645--652.

[10]

Duc-Cuong Dang, Tobias Friedrich, Timo Kötzing, Martin S. Krejca, Per Kristian Lehre, Pietro S. Oliveto, Dirk Sudholt, and Andrew M. Sutton. 2018. Escaping local optima using crossover with emergent diversity. IEEE Transactions on Evolutionary Computation 22 (2018), 484--497.

[11]

Benjamin Doerr. 2019. A tight runtime analysis for the cGA on jump functions: EDAs can cross fitness valleys at no extra cost. In Genetic and Evolutionary Computation Conference, GECCO 2019. ACM, 1488--1496.

Digital Library

[12]

Benjamin Doerr. 2020. Does comma selection help to cope with local optima?. In Genetic and Evolutionary Computation Conference, GECCO 2020. ACM, 1304--1313.

Digital Library

[13]

Benjamin Doerr, Carola Doerr, and Timo Kötzing. 2018. Static and self-adjusting mutation strengths for multi-valued decision variables. Algorithmica 80 (2018), 1732--1768.

Digital Library

[14]

Benjamin Doerr, Carola Doerr, and Timo Kötzing. 2019. Solving problems with unknown solution length at almost no extra cost. Algorithmica 81 (2019), 703--748.

Digital Library

[15]

Benjamin Doerr, Edda Happ, and Christian Klein. 2012. Crossover can provably be useful in evolutionary computation. Theoretical Computer Science 425 (2012), 17--33.

Digital Library

[16]

Benjamin Doerr and Martin S. Krejca. 2020. The univariate marginal distribution algorithm copes well with deception and epistasis. In Evolutionary Computation in Combinatorial Optimization, EvoCOP 2020. Springer, 51--66.

[17]

Benjamin Doerr, Huu Phuoc Le, Régis Makhmara, and Ta Duy Nguyen. 2017. Fast genetic algorithms. In Genetic and Evolutionary Computation Conference, GECCO 2017. ACM, 777--784.

Digital Library

[18]

Benjamin Doerr and Frank Neumann (Eds.). 2020. Theory of Evolutionary Computation---Recent Developments in Discrete Optimization. Springer. Also available at https://cs.adelaide.edu.au/~frank/papers/TheoryBook2019-selfarchived.pdf.

[19]

Benjamin Doerr, Frank Neumann, Dirk Sudholt, and Carsten Witt. 2011. Runtime analysis of the 1-ANT ant colony optimizer. Theoretical Computer Science 412 (2011), 1629--1644.

Digital Library

[20]

Benjamin Doerr and Weijie Zheng. 2020. Sharp bounds for genetic drift in estimation-of-distribution algorithms. IEEE Transactions on Evolutionary Computation 24 (2020), 1140--1149.

Digital Library

[21]

Benjamin Doerr and Weijie Zheng. 2021. Theoretical analyses of multi-objective evolutionary algorithms on multi-modal objectives. In Conference on Artificial Intelligence, AAAI 2021. AAAI Press. To appear.

Digital Library

[22]

Marco Dorigo and Thomas Stützle. 2004. Ant colony optimization. MIT Press.

[23]

Stefan Droste, Thomas Jansen, and Ingo Wegener. 2002. On the analysis of the (1 + 1) evolutionary algorithm. Theoretical Computer Science 276 (2002), 51--81.

Digital Library

[24]

Xiequan Fan, Ion Grama, and Quansheng Liu. 2015. Exponential inequalities for martingales with applications. Electronic Journal of Probability 20 (2015), 22 pp.

[25]

Matthias Feldmann and Timo Kötzing. 2013. Optimizing expected path lengths with ant colony optimization using fitness proportional update. In Foundations of Genetic Algorithms, FOGA 2013. ACM, 65--74.

Digital Library

[26]

Tobias Friedrich, Timo Kötzing, Martin S. Krejca, Samadhi Nallaperuma, Frank Neumann, and Martin Schirneck. 2016. Fast building block assembly by majority vote crossover. In Genetic and Evolutionary Computation Conference, GECCO 2016. ACM, 661--668.

Digital Library

[27]

Tobias Friedrich, Timo Kotzing, Martin S. Krejca, and Andrew M. Sutton. 2016. Robustness of ant colony optimization to noise. Evolutionary Computation 24 (2016), 237--254.

Digital Library

[28]

Walter J. Gutjahr. 2006. On the finite-time dynamics of ant colony optimization. Methodology and Computing in Applied Probability 8 (2006), 105--133.

Digital Library

[29]

Walter J. Gutjahr. 2008. First steps to the runtime complexity analysis of ant colony optimization. Computers & Operations Research 35 (2008), 2711--2727.

Digital Library

[30]

Walter J. Gutjahr. 2011. Ant colony optimization: recent developments in theoretical analysis. In Theory of Randomized Search Heuristics: Foundations and Recent Developments, Anne Auger and Benjamin Doerr (Eds.). Vol. 1. World Scientific, 225--254.

[31]

Walter J. Gutjahr and Giovanni Sebastiani. 2008. Runtime analysis of ant colony optimization with best-so-far reinforcement. Methodology and Computing in Applied Probability 10 (2008), 409--433.

Digital Library

[32]

Václav Hasenöhrl and Andrew M. Sutton. 2018. On the runtime dynamics of the compact genetic algorithm on jump functions. In Genetic and Evolutionary Computation Conference, GECCO 2018. ACM, 967--974.

Digital Library

[33]

Jens Jägersküpper and Tobias Storch. 2007. When the plus strategy outperforms the comma strategy and when not. In Foundations of Computational Intelligence, FOCI 2007. IEEE, 25--32.

[34]

Thomas Jansen. 2013. Analyzing Evolutionary Algorithms - The Computer Science Perspective. Springer.

Digital Library

[35]

Thomas Jansen. 2015. On the black-box complexity of example functions: the real jump function. In Foundations of Genetic Algorithms XIII, FOGA 2015. ACM, 16--24.

Digital Library

[36]

Thomas Jansen and Ingo Wegener. 2002. The analysis of evolutionary algorithms - a proof that crossover really can help. Algorithmica 34 (2002), 47--66.

Digital Library

[37]

Timo Kötzing, Per Kristian Lehre, Frank Neumann, and Pietro S. Oliveto. 2010. Ant colony optimization and the minimum cut problem. In Genetic and Evolutionary Computation Conference, GECCO 2010. ACM, 1393--1400.

[38]

Timo Kötzing and Hendrik Molter. 2012. ACO beats EA on a dynamic pseudo-Boolean function. In Parallel Problem Solving from Nature, PPSN 2012, Part I. Springer, 113--122.

[39]

Timo Kötzing, Frank Neumann, Heiko Röglin, and Carsten Witt. 2010. Theoretical properties of two ACO approaches for the traveling salesman problem. In Swarm Intelligence, ANTS 2010. Springer, 324--335.

[40]

Guillermo Leguizamón and Enrique Alba. 2013. Ant colony based algorithms for dynamic optimization problems. In Metaheuristics for Dynamic Optimization. Springer, 189--210.

[41]

Per Kristian Lehre. 2010. Negative drift in populations. In Parallel Problem Solving from Nature, PPSN 2010. Springer, 244--253.

Digital Library

[42]

Per Kristian Lehre and Phan Trung Hai Nguyen. 2019. On the limitations of the univariate marginal distribution algorithm to deception and where bivariate EDAs might help. In Foundations of Genetic Algorithms, FOGA 2019. ACM, 154--168.

Digital Library

[43]

Per Kristian Lehre and Carsten Witt. 2013. General drift analysis with tail bounds. CoRR abs/1307.2559 (2013).

[44]

Per Kristian Lehre and Carsten Witt. 2014. Concentrated hitting times of randomized search heuristics with variable drift. In International Symposium on Algorithms and Computation, ISAAC 2014. Springer, 686--697.

[45]

Andrei Lissovoi, Pietro S. Oliveto, and John Alasdair Warwicker. 2019. On the time complexity of algorithm selection hyper-heuristics for multimodal optimisation. In Conference on Artificial Intelligence, AAAI 2019. AAAI Press, 2322--2329.

Digital Library

[46]

Andrei Lissovoi and Carsten Witt. 2016. MMAS versus population-based EA on a family of dynamic fitness functions. Algorithmica 75 (2016), 554--576.

Digital Library

[47]

Manuel López-Ibáñez, Thomas Stützle, and Marco Dorigo. 2018. Ant colony optimization: a component-wise overview. In Handbook of Heuristics, Rafael Martí, Panos M. Pardalos, and Mauricio G. C. Resende (Eds.). Springer International Publishing, Cham, 371--407.

[48]

Frank Neumann, Dirk Sudholt, and Carsten Witt. 2008. Rigorous analyses for the combination of ant colony optimization and local search. In Ant Colony Optimization and Swarm Intelligence, ANTS 2008. Springer, 132--143.

[49]

Frank Neumann, Dirk Sudholt, and Carsten Witt. 2010. A few ants are enough: ACO with iteration-best update. In Genetic and Evolutionary Computation Conference, GECCO 2010. ACM, 63--70.

Digital Library

[50]

Frank Neumann and Carsten Witt. 2009. Runtime analysis of a simple ant colony optimization algorithm. Algorithmica 54 (2009), 243--255.

Digital Library

[51]

Frank Neumann and Carsten Witt. 2010. Ant colony optimization and the minimum spanning tree problem. Theoretical Computer Science 411 (2010), 2406--2413.

Digital Library

[52]

Frank Neumann and Carsten Witt. 2010. Bioinspired Computation in Combinatorial Optimization - Algorithms and Their Computational Complexity. Springer.

Digital Library

[53]

Pietro S. Oliveto, Tiago Paixão, Jorge Pérez Heredia, Dirk Sudholt, and Barbora Trubenová. 2018. How to escape local optima in black box optimisation: when non-elitism outperforms elitism. Algorithmica 80 (2018), 1604--1633.

Digital Library

[54]

Tiago Paixão, Jorge Pérez Heredia, Dirk Sudholt, and Barbora Trubenová. 2017. Towards a runtime comparison of natural and artificial evolution. Algorithmica 78 (2017), 681--713.

Digital Library

[55]

Amirhossein Rajabi and Carsten Witt. 2020. Self-adjusting evolutionary algorithms for multimodal optimization. In Genetic and Evolutionary Computation Conference, GECCO 2020. ACM, 1314--1322.

Digital Library

[56]

Amirhossein Rajabi and Carsten Witt. 2021. Stagnation detection in highly multimodal fitness landscapes. In Genetic and Evolutionary Computation Conference, GECCO 2021. ACM.

Digital Library

[57]

Amirhossein Rajabi and Carsten Witt. 2021. Stagnation detection with randomized local search. In Evolutionary Computation in Combinatorial Optimization, EvoCOP 2021. Springer, 152--168.

Digital Library

[58]

Jonathan E. Rowe and Aishwaryaprajna. 2019. The benefits and limitations of voting mechanisms in evolutionary optimisation. In Foundations of Genetic Algorithms, FOGA 2019. ACM, 34--42.

Digital Library

[59]

Thomas Stützle and Holger H. Hoos. 2000. MAX-MIN ant system. Future Generation Computer Systems 16, 8 (2000), 889--914.

Digital Library

[60]

Dirk Sudholt and Christian Thyssen. 2012. A simple ant colony optimizer for stochastic shortest path problems. Algorithmica 64 (2012), 643--672.

Digital Library

[61]

Dirk Sudholt and Carsten Witt. 2019. On the choice of the update strength in estimation-of-distribution algorithms and ant colony optimization. Algorithmica 81 (2019), 1450--1489.

Digital Library

[62]

Darrell Whitley, Swetha Varadarajan, Rachel Hirsch, and Anirban Mukhopadhyay. 2018. Exploration and exploitation without mutation: solving the jump function in Θ(n) time. In Parallel Problem Solving from Nature, PPSN 2018, Part II. Springer, 55--66.

[63]

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

Digital Library

Cited By

Doerr BQu ZWilliams BChen YNeville J(2023)Runtime analysis for the NSGA-IIProceedings of the Thirty-Seventh AAAI Conference on Artificial Intelligence and Thirty-Fifth Conference on Innovative Applications of Artificial Intelligence and Thirteenth Symposium on Educational Advances in Artificial Intelligence10.1609/aaai.v37i10.26461(12399-12407)Online publication date: 7-Feb-2023
https://dl.acm.org/doi/10.1609/aaai.v37i10.26461
Zheng WDoerr B(2023)Theoretical Analyses of Multiobjective Evolutionary Algorithms on Multimodal Objectives*Evolutionary Computation10.1162/evco_a_0032831:4(337-373)Online publication date: 1-Dec-2023
https://doi.org/10.1162/evco_a_00328
Ivanova AAntipov DDoerr BSilva SPaquete L(2023)Larger Offspring Populations Help the (1 + (λ, λ)) Genetic Algorithm to Overcome the NoiseProceedings of the Genetic and Evolutionary Computation Conference10.1145/3583131.3590514(919-928)Online publication date: 15-Jul-2023
https://dl.acm.org/doi/10.1145/3583131.3590514
Show More Cited By

Index Terms

A rigorous runtime analysis of the 2-MMAS_ib on jump functions: ant colony optimizers can cope well with local optima
1. Theory of computation
  1. Randomness, geometry and discrete structures
    1. Random search heuristics

Recommendations

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. ...
Theory of swarm intelligence
GECCO '12: Proceedings of the 14th annual conference companion 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 '21: Proceedings of the Genetic and Evolutionary Computation Conference

June 2021

1219 pages

ISBN:9781450383509

DOI:10.1145/3449639

Editor:
Francisco Chicano
University of Malaga
,
General Chair:
Krzysztof Krawiec
Poznan University of Technology

Copyright © 2021 ACM.

Publication rights licensed to ACM. ACM acknowledges that this contribution was authored or co-authored by an employee, contractor or affiliate of a national government. As such, the Government retains a nonexclusive, royalty-free right to publish or reproduce this article, or to allow others to do so, for Government purposes only.

Sponsors

SIGEVO: ACM Special Interest Group on Genetic and Evolutionary Computation

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 26 June 2021

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Funding Sources

Agence Nationale de la Recherche

Conference

GECCO '21

Sponsor:

SIGEVO

GECCO '21: Genetic and Evolutionary Computation Conference

July 10 - 14, 2021

Lille, France

Acceptance Rates

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

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

8
Total Citations
View Citations
438
Total Downloads

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

Reflects downloads up to 19 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Doerr BQu ZWilliams BChen YNeville J(2023)Runtime analysis for the NSGA-IIProceedings of the Thirty-Seventh AAAI Conference on Artificial Intelligence and Thirty-Fifth Conference on Innovative Applications of Artificial Intelligence and Thirteenth Symposium on Educational Advances in Artificial Intelligence10.1609/aaai.v37i10.26461(12399-12407)Online publication date: 7-Feb-2023
https://dl.acm.org/doi/10.1609/aaai.v37i10.26461
Zheng WDoerr B(2023)Theoretical Analyses of Multiobjective Evolutionary Algorithms on Multimodal Objectives*Evolutionary Computation10.1162/evco_a_0032831:4(337-373)Online publication date: 1-Dec-2023
https://doi.org/10.1162/evco_a_00328
Ivanova AAntipov DDoerr BSilva SPaquete L(2023)Larger Offspring Populations Help the (1 + (λ, λ)) Genetic Algorithm to Overcome the NoiseProceedings of the Genetic and Evolutionary Computation Conference10.1145/3583131.3590514(919-928)Online publication date: 15-Jul-2023
https://dl.acm.org/doi/10.1145/3583131.3590514
Doerr BDremaux ALutzeyer JStumpf ASilva SPaquete L(2023)How the Move Acceptance Hyper-Heuristic Copes With Local Optima: Drastic Differences Between Jumps and CliffsProceedings of the Genetic and Evolutionary Computation Conference10.1145/3583131.3590509(990-999)Online publication date: 15-Jul-2023
https://dl.acm.org/doi/10.1145/3583131.3590509
Doerr BGhannane YIbn Brahim M(2023)Runtime Analysis for Permutation-based Evolutionary AlgorithmsAlgorithmica10.1007/s00453-023-01146-886:1(90-129)Online publication date: 26-Jul-2023
https://doi.org/10.1007/s00453-023-01146-8
Antipov DBuzdalov MDoerr B(2023)Lazy Parameter Tuning and Control: Choosing All Parameters Randomly from a Power-Law DistributionAlgorithmica10.1007/s00453-023-01098-z86:2(442-484)Online publication date: 22-Feb-2023
https://doi.org/10.1007/s00453-023-01098-z
Bambury HBultel ADoerr B(2022)An Extended Jump Functions Benchmark for the Analysis of Randomized Search HeuristicsAlgorithmica10.1007/s00453-022-00977-186:1(1-32)Online publication date: 23-May-2022
https://doi.org/10.1007/s00453-022-00977-1
Antipov DDoerr BKaravaev V(2022)A Rigorous Runtime Analysis of the $$(1 + (\lambda , \lambda ))$$ GA on Jump FunctionsAlgorithmica10.1007/s00453-021-00907-784:6(1573-1602)Online publication date: 15-Jan-2022
https://doi.org/10.1007/s00453-021-00907-7

View Options

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

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

Media

Figures

Other

Tables

View Table of Contents