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] = 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.