Paper Info
Title
Lower Bounds on the Run Time of the Univariate Marginal Distribution Algorithm on OneMax.
Abstract
The Univariate Marginal Distribution Algorithm (UMDA), a popular estimation of distribution algorithm, is studied from a run time perspective. On the classical OneMax benchmark function, a lower bound of Ω(μ√n + n log n), where μ is the population size, on its expected run time is proved. This is the first direct lower bound on the run time of the UMDA. It is stronger than the bounds that follow from general black-box complexity theory and is matched by the run time of many evolutionary algorithms. The results are obtained through advanced analyses of the stochastic change of the frequencies of bit values maintained by the algorithm, including carefully designed potential functions. These techniques may prove useful in advancing the field of run time analysis for estimation of distribution algorithms in general.
Year
DOI
Venue
2017
10.1145/3040718.3040724
FOGA
Field
DocType
Citations 
Mathematical optimization,Estimation of distribution algorithm,Evolutionary algorithm,Upper and lower bounds,Computer science,Population size,Univariate marginal distribution algorithm,Time complexity,Genetic algorithm,Computer programming
Conference
13
PageRank 
References 
Authors
0.59
19
2
Name
Order
Citations
PageRank
Martin Krejca1829.47
Carsten Witt298759.83