A Simplified Run Time Analysis of the Univariate Marginal Distribution Algorithm on LeadingOnes

Abstract

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.

References in corpus (5)

• Probabilistic Tools for the Analysis of Randomized Optimization Heuristics
• Sharp Bounds for Genetic Drift in Estimation of Distribution Algorithms
• Improved Runtime Bounds for the Univariate Marginal Distribution Algorithm via Anti-Concentration
• A Tight Runtime Analysis for the cGA on Jump Functions---EDAs Can Cross Fitness Valleys at No Extra Cost
• Runtime Analysis of the Univariate Marginal Distribution Algorithm under Low Selective Pressure and Prior Noise

Cited by in corpus (3)

• Estimation-of-Distribution Algorithms for Multi-Valued Decision Variables
• Runtime Analysis of the Compact Genetic Algorithm on the LeadingOnes Benchmark
• From Understanding Genetic Drift to a Smart-Restart Mechanism for Estimation-of-Distribution Algorithms