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

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]=Θ(nlognλ+nλ/μ+nlog+log+(λ/μ)log+(λ/μ)), where log ⁺x: = max { 1 , log x} for all x> 0. The same methods allow to improve the previous-best O(nlognλ+nlogλ) runtime guarantee for the (λ+ λ) EA with fair parent selection to a tight Θ(nlognλ+n) runtime result.