# A Tight Runtime Analysis for the (μ + λ) EA

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

## Key facts

- Cited by 8 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 28 Dec 2018.

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

- [Lazy Parameter Tuning and Control: Choosing All Parameters Randomly From a Power-Law Distribution](https://mlsanity.com/paper/2104.06714/) (2021)
- [The First Proven Performance Guarantees for the Non-Dominated Sorting Genetic Algorithm II (NSGA-II) on a Combinatorial Optimization Problem](https://mlsanity.com/paper/2305.13459/) (2023)
- [Choosing the Right Algorithm With Hints From Complexity Theory](https://mlsanity.com/paper/2109.06584/) (2021)
- [The (1+(λ,λ)) Global SEMO Algorithm](https://mlsanity.com/paper/2210.03618/) (2022)
- [From Understanding Genetic Drift to a Smart-Restart Mechanism for Estimation-of-Distribution Algorithms](https://mlsanity.com/paper/2206.09090/) (2022)
- [Already Moderate Population Sizes Provably Yield Strong Robustness to Noise](https://mlsanity.com/paper/2404.02090/) (2024)
- [Larger Offspring Populations Help the (1 + (λ, λ)) Genetic Algorithm to Overcome the Noise](https://mlsanity.com/paper/2305.04553/) (2023)
- [Parent Selection Mechanisms in Elitist Crossover-Based Algorithms](https://mlsanity.com/paper/2604.04083/) (2026)

## Abstract (arXiv)

Despite significant progress in the theory of evolutionary algorithms, the theoretical understanding of evolutionary algorithms which use non-trivial populations remains challenging and only few rigorous results exist. Already for the most basic problem, the determination of the asymptotic runtime of the (μ+λ) evolutionary algorithm on the simple OneMax benchmark function, only the special cases μ=1 and λ=1 have been solved. In this work, we analyze this long-standing problem and show the asymptotically tight result that the runtime T, the number of iterations until the optimum is found, satisfies [E[T] = Thetabigg(fracnlog nλ+fracnλ / μ + fracnlog^+log^+ λ/ μlog^+ λ / μbigg),] where log^+ x := max1, log x for all x > 0. The same methods allow to improve the previous-best O(fracn log nλ + n log λ) runtime guarantee for the (λ+λ)~EA with fair parent selection to a tight Theta(fracn log nλ + n) runtime result.