Runtime Analysis of Evolutionary Algorithms via Symmetry Arguments

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 $\hat{I}\text{c◯}(2^n/\sqrt{n})$ iterations to find any particular target search point. This bound is valid for all population sizes $\hat{I}¼$. Our result improves over the previous lower bound of $\hat{I}\text{c◯}(\exp (n^{\hat{I}´/2}))$ valid for population sizes $\hat{I}¼=O(n^{1/2-\hat{I}´})$, $0<\hat{I}´<1/2$.

Minor changes compared to the previous version