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

Abstract

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] = (n n +n / + n ^+ ^+ / ^+ / ),\] where ^+ x := \1, x\ for all x > 0. The same methods allow to improve the previous-best O(n n + n ) runtime guarantee for the (+)~EA with fair parent selection to a tight (n n + n) runtime result.

Tasks

Reproductions