A Simplified Run Time Analysis of the Univariate Marginal Distribution Algorithm on LeadingOnes
This work offers incremental theoretical improvements for evolutionary computation researchers analyzing runtime bounds on benchmark functions.
The paper tackles the runtime analysis of the Univariate Marginal Distribution Algorithm (UMDA) on the LeadingOnes benchmark, proving a linear runtime in problem size divided by log selection rate with high probability when population size is quasilinear, improving over prior results and also providing the first matching lower bound.
With elementary means, we prove a stronger run time guarantee for the univariate marginal distribution algorithm (UMDA) optimizing the LeadingOnes benchmark function in the desirable regime with low genetic drift. If the population size is at least quasilinear, then, with high probability, the UMDA samples the optimum within a number of iterations that is linear in the problem size divided by the logarithm of the UMDA's selection rate. This improves over the previous guarantee, obtained by Dang and Lehre (2015) via the deep level-based population method, both in terms of the run time and by demonstrating further run time gains from small selection rates. With similar arguments as in our upper-bound analysis, we also obtain the first lower bound for this problem. Under similar assumptions, we prove that a bound that matches our upper bound up to constant factors holds with high probability.