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 $\mathrm{\Omega }(2^n\mathrm{/}\sqrt{n})$ 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 $\mathrm{\Omega }(\exp (n^{\delta \mathrm{/}2}))$ valid for population sizes $\mu = O(n^{1/2 - \delta})$,$0 < \delta < 1/2$.