Runtime Analysis of Evolutionary Algorithms via Symmetry Arguments
This provides a tighter theoretical runtime bound for evolutionary algorithms, which is incremental but important for theoretical computer science and algorithm analysis.
The paper tackles the problem of analyzing the runtime of a selection-free steady state genetic algorithm, proving that it takes an expected Ω(2^n / √n) iterations to find any target search point, which improves over a previous lower bound of Ω(exp(n^{δ/2})) for certain population sizes.
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 $Ω(2^n / \sqrt 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 $Ω(\exp(n^{δ/2}))$ valid for population sizes $μ= O(n^{1/2 - δ})$, $0 < δ< 1/2$.