Paper Info
Title
Improved runtime bounds for the univariate marginal distribution algorithm via anti-concentration.
Abstract
Unlike traditional evolutionary algorithms which produce offspring via genetic operators, Estimation of Distribution Algorithms (EDAs) sample solutions from probabilistic models which are learned from selected individuals. It is hoped that ED As may improve optimisation performance on epistatic fitness landscapes by learning variable interactions. However, hardly any rigorous results are available to support claims about the performance of EDAs, even for fitness functions without epistasis. The expected runtime of the Univariate Marginal Distribution Algorithm (UMDA) on OneMax was recently shown to be in 𝒪(nλ log λ) [9]. Later, Krejca and Witt proved the lower bound [EQUATION] via an involved drift analysis [16]. We prove a O (nλ) bound, given some restrictions on the population size. This implies the tight bound Θ (n log n) when λ = O (log n), matching the runtime of classical EAs. Our analysis uses the level-based theorem and anti-concentration properties of the Poisson-binomial distribution. We expect that these generic methods will facilitate further analysis of EDAs.
Year
DOI
Venue
2018
10.1145/3071178.3071317
Proceedings of the Genetic and Evolutionary Computation Conference
Keywords
DocType
Volume
Runtime Analysis, Level-based Analysis, Estimation of Distribution Algorithms
Journal
abs/1802.00721
ISSN
Citations 
PageRank 
Proceedings of the Genetic and Evolutionary Computation Conference (GECCO 2017). ACM, New York, NY, USA, 1383-1390
6
0.46
References 
Authors
13
2
Name
Order
Citations
PageRank
Per Kristian Lehre162742.60
Phan Trung Hai Nguyen2132.25