Population Dynamics and Improved Runtime Guarantees for the (μ+1) EA on BinVal

Populations play a key role in the area of evolutionary computation to tackle complex optimization problems. Nevertheless, it is hard to understand the underlying population dynamics from a theoretical perspective, and only a limited number of theoretical results for population-based algorithms are available even for simple benchmark functions. In this paper, we study the classic (μ+1) EA on the benchmark problem BinVal, which allows for exponentially many function values. Previous methods for the analysis, based on fitness levels and multiplicative drift analysis, lead to runtime bounds for this function of size n that include an additive term of Θ(n2). We provide new insights into how this standard algorithm optimizes BinVal, and we provide runtime bounds that are polynomial in the population size μ and do not include this additive term. In particular, we prove bounds on the expected runtime that are O(μ5n log (n/μ4)) for standard bit mutation, which is O(n log n) for constant μ. Our analysis considers the population dynamics of the (μ+1) EA more closely, proving that copies created by mutation lead to a low diversity in short blocks of bits across all individuals. We extend this method to mutation operators that cannot create duplicates, and prove bounds similar to standard bit mutation.