# Lasting Diversity and Superior Runtime Guarantees for the (μ+1) Genetic Algorithm

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

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 24 Feb 2023.

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

- [How the Move Acceptance Hyper-Heuristic Copes With Local Optima: Drastic Differences Between Jumps and Cliffs](https://mlsanity.com/paper/2304.10414/) (2023)
- [Larger Offspring Populations Help the (1 + (λ, λ)) Genetic Algorithm to Overcome the Noise](https://mlsanity.com/paper/2305.04553/) (2023)

## Abstract (arXiv)

Most evolutionary algorithms (EAs) used in practice employ crossover. In contrast, only for few and mostly artificial examples a runtime advantage from crossover could be proven with mathematical means. The most convincing such result shows that the (μ+1) genetic algorithm (GA) with population size μ=O(n) optimizes jump functions with gap size k ≥ 3 in time O(nk / μ + nk-1log n), beating the Theta(nk) runtime of many mutation-based EAs. This result builds on a proof that the GA occasionally and then for an expected number of Omega(μ2) iterations has a population that is not dominated by a single genotype. In this work, we show that this diversity persist with high probability for a time exponential in μ (instead of quadratic). From this better understanding of the population diversity, we obtain stronger runtime guarantees, among them the statement that for all cln(n)≤μ ≤ n/log n, with c a suitable constant, the runtime of the (μ+1) GA on Jumpk, with k ≥ 3, is O(nk-1). Consequently, already with logarithmic population sizes, the GA gains a speed-up of order Omega(n) from crossover.