A Tight Runtime Analysis for the $(μ+ λ)$ EA
This provides a foundational theoretical result for evolutionary algorithms with non-trivial populations, addressing a core challenge in the field.
The paper tackled the long-standing problem of determining the asymptotic runtime of the (μ+λ) evolutionary algorithm on the OneMax benchmark function, showing a tight runtime bound of Θ(n log n/λ + n/(λ/μ) + n log⁺log⁺(λ/μ)/log⁺(λ/μ)).
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] = Θ\bigg(\frac{n\log n}λ+\frac{n}{λ/ μ} + \frac{n\log^+\log^+ λ/ μ}{\log^+ λ/ μ}\bigg),\] where $\log^+ x := \max\{1, \log x\}$ for all $x > 0$. The same methods allow to improve the previous-best $O(\frac{n \log n}λ + n \log λ)$ runtime guarantee for the $(λ+λ)$~EA with fair parent selection to a tight $Θ(\frac{n \log n}λ + n)$ runtime result.