Runtime Analysis of Evolutionary Algorithms via Symmetry Arguments

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