A tight runtime analysis for the (+) EA

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 n n log⁺ log⁺ /, E[T ] = Θⁿ logⁿ + + / log⁺ / where log⁺ x := max{1, log x } for all x > 0.