Runtime analysis via symmetry arguments
Benjamin Doerr · Proceedings of the Genetic and Evolutionary Computation Conference Companion · 2021
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].