A Tight Runtime Analysis for the (μ+ λ) EA
share
Despite significant progress in the theory of evolutionary algorithms, the theoretical understanding of true population-based evolutionary algorithms 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.
READ FULL TEXT