# Runtime Analysis of Evolutionary Algorithms via Symmetry Arguments

arXiv: https://arxiv.org/abs/2006.04663 · HTML: https://mlsanity.com/paper/2006.04663/

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 8 Jun 2020.

## Built on by (most cited first, 2 of 2)

- [The Runtime of Random Local Search on the Generalized Needle Problem](https://mlsanity.com/paper/2403.08153/) (2024)
- [A Block-Coordinate Descent EMO Algorithm: Theoretical and Empirical Analysis](https://mlsanity.com/paper/2404.03838/) (2024)

## Abstract (arXiv)

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.