Runtime analysis via symmetry arguments: (hot-off-the-press track at GECCO 2021)
Pages 23 - 24
Abstract
We use an elementary argument building on group actions to prove that the selection-free steady state genetic algorithm analyzed by Sutton and Witt (GECCO 2019) takes an expected number of [EQUATION] iterations to find any particular target search point. This bound is valid for all population sizes μ. Our result improves and extends the previous lower bound of Ω(exp(nδ/2)) valid for population sizes μ = O(n1/2--δ), 0 < δ < 1/2. This paper for the Hot-off-the-Press track at GECCO 2021 summarizes the work Benjamin Doerr. Runtime Analysis of Evolutionary Algorithms via Symmetry Arguments. Information Processing Letters, 166:106064. 2021. [5].
Supplementary Material
p23-doerr_suppl.pdf
- Download
- 424.05 KB
References
[1]
Anne Auger and Benjamin Doerr (Eds.). 2011. Theory of Randomized Search Heuristics. World Scientific Publishing.
[2]
Axel de Perthuis de Laillevault, Benjamin Doerr, and Carola Doerr. 2015. Money for nothing: speeding up evolutionary algorithms through better initialization. In Genetic and Evolutionary Computation Conference, GECCO 2015. ACM, 815--822.
[3]
Benjamin Doerr. 2020. Exponential upper bounds for the runtime of randomized search heuristics. In Parallel Problem Solving From Nature, PPSN 2020, Part II. Springer, 619--633.
[4]
Benjamin Doerr. 2020. Probabilistic tools for the analysis of randomized optimization heuristics. In Theory of Evolutionary Computation: Recent Developments in Discrete Optimization, Benjamin Doerr and Frank Neumann (Eds.). Springer, 1--87. Also available at https://arxiv.org/abs/1801.06733.
[5]
Benjamin Doerr. 2021. Runtime analysis of evolutionary algorithms via symmetry arguments. Information Processing Letters 166 (2021), 106064.
[6]
Benjamin Doerr and Carola Doerr. 2016. The impact of random initialization on the runtime of randomized search heuristics. Algorithmica 75 (2016), 529--553.
[7]
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.
[8]
Benjamin Doerr and Madeleine Theile. 2009. Improved analysis methods for crossover-based algorithms. In Genetic and Evolutionary Computation Conference, GECCO 2009. ACM, 247--254.
[9]
Thomas Jansen. 2013. Analyzing Evolutionary Algorithms - The Computer Science Perspective. Springer.
[10]
Frank Neumann and Carsten Witt. 2010. Bioinspired Computation in Combinatorial Optimization - Algorithms and Their Computational Complexity. Springer.
[11]
Pietro S. Oliveto, Dirk Sudholt, and Carsten Witt. 2020. A tight lower bound on the expected runtime of standard steady state genetic algorithms. In Genetic and Evolutionary Computation Conference, GECCO 2020. ACM, 1323--1331.
[12]
Pietro S. Oliveto and Carsten Witt. 2011. Simplified drift analysis for proving lower bounds in evolutionary computation. Algorithmica 59 (2011), 369--386.
[13]
Pietro S. Oliveto and Carsten Witt. 2015. Improved time complexity analysis of the simple genetic algorithm. Theoretical Computer Science 605 (2015), 21--41.
[14]
Dirk Sudholt. 2013. A new method for lower bounds on the running time of evolutionary algorithms. IEEE Transactions on Evolutionary Computation 17 (2013), 418--435.
[15]
Andrew M. Sutton and Carsten Witt. 2019. Lower bounds on the runtime of crossover-based algorithms via decoupling and family graphs. In Genetic and Evolutionary Computation Conference, GECCO 2019. ACM, 1515--1522.
[16]
Carsten Witt. 2018. Domino convergence: why one should hill-climb on linear functions. In Genetic and Evolutionary Computation Conference, GECCO 2018. ACM, 1539--1546.
Index Terms
- Runtime analysis via symmetry arguments: (hot-off-the-press track at GECCO 2021)
Recommendations
Towards a Runtime Comparison of Natural and Artificial Evolution
Evolutionary algorithms (EAs) form a popular optimisation paradigm inspired by natural evolution. In recent years the field of evolutionary computation has developed a rigorous analytical theory to analyse the runtimes of EAs on many illustrative ...
A Tight Runtime Analysis of the (1+(λ, λ)) Genetic Algorithm on OneMax
GECCO '15: Proceedings of the 2015 Annual Conference on Genetic and Evolutionary ComputationUnderstanding 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 ...
The choice of the offspring population size in the (1,λ) evolutionary algorithm
We extend the theory of non-elitist evolutionary algorithms (EAs) by considering the offspring population size in the (1,@l) EA. We establish a sharp threshold at @l=log"e"e"-"1n~5log"1"0n between exponential and polynomial running times on OneMax. For ...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
July 2021
2047 pages
Copyright © 2021 Owner/Author.
Permission to make digital or hard copies of part or all 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 third-party components of this work must be honored. For all other uses, contact the Owner/Author.
Sponsors
Publisher
Association for Computing Machinery
New York, NY, United States
Publication History
Published: 08 July 2021
Check for updates
Author Tags
Qualifiers
- Abstract
Funding Sources
Conference
GECCO '21
Sponsor:
Acceptance Rates
Overall Acceptance Rate 1,669 of 4,410 submissions, 38%
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- 0Total Citations
- 48Total Downloads
- Downloads (Last 12 months)0
- Downloads (Last 6 weeks)0
Reflects downloads up to 18 Dec 2024
Other Metrics
Citations
Cited By
View allView Options
Login options
Check if you have access through your login credentials or your institution to get full access on this article.
Sign in