Refined Upper Bounds on the Expected Runtime of Non-elitist Populations from Fitness-Levels

Recently, an easy-to-use fitness-level technique was introduced to prove upper bounds on the expected runtime of randomised search heuristics with non-elitist populations and unary variation operators. Following this work, we present a new and much more detailed analysis of the population dynamics, leading to a significantly improved fi tness-level technique. In addition to improving the technique, the proof has been simplified. From the new fi tness-level technique, the upper bound on the runtime in terms of generations can be improved from linear to logarithmic in the population size. Increasing the population size therefore has a smaller impact on the runtime than previously thought. To illustrate this improvement, we show that the current bounds on the runtime of EAs with non-elitist populations on many example functions can be significantly reduced. Furthermore, the new fi tness-level technique makes the relationship between the selective pressure and the runtime of the algorithm explicit. Surprisingly, a very weak selective pressure is sufficient to optimise many functions in expected polynomial time. This observation has important consequences of which some are explored in a companion paper.