Runtime analysis of evolutionary algorithms via symmetry arguments

DOI10.1016/J.IPL.2020.106064MaRDI QIDQ2224858zbMATH OpenOpenAlexFDO

Authors Benjamin Doerr

Publication date 4 February 2021

Published in Information Processing Letters (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2006.04663

zbMATH Keywords

crossoverevolutionary algorithmruntime analysis

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Evolutionary algorithms, genetic algorithms (computational aspects) (68W50)

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 $Omega(2^n/sqrtn)$ iterations to find any particular target search point. This bound is valid for all population sizes $mu$. Our result improves over the previous lower bound of $Omega(exp(n^{delta/2}))$ valid for population sizes $mu=O(n^{1/2-delta})$, $0<delta<1/2$.

Recommendations

• On the runtime analysis of the simple genetic algorithm
• A tight runtime analysis for the \((\mu + \lambda)\) EA
• Improved time complexity analysis of the simple genetic algorithm
• On the analysis of the \((1+1)\) evolutionary algorithm
• Combining Markov-chain analysis and drift analysis. The \((1+1)\) evolutionary algorithm on linear functions reloaded

Cites work

• Analyzing evolutionary algorithms. The computer science perspective.
• Bioinspired computation in combinatorial optimization. Algorithms and their computational complexity
• scientific article; zbMATH DE number 1543348 (Why is no real title available?)
• scientific article; zbMATH DE number 5686753 (Why is no real title available?)
• Improved time complexity analysis of the simple genetic algorithm
• Simplified drift analysis for proving lower bounds in evolutionary computation
• The impact of random initialization on the runtime of randomized search heuristics
• Theory of evolutionary computation. Recent developments in discrete optimization

Cited in

(4)

• On the runtime analysis of the simple genetic algorithm
• scientific article; zbMATH DE number 6019547 (Why is no real title available?)
• The role of selective pressure when solving symmetric functions in polynomial time
• Finding Symmetry Groups of Some Quadratic Programming Problems

This page was built for publication: Runtime analysis of evolutionary algorithms via symmetry arguments

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2224858)