Conference paper
Lower bounds on the run time of the univariate marginal distribution algorithm on OneMax
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.
| Language: | English |
|---|---|
| Publisher: | Association for Computing Machinery |
| Year: | 2017 |
| Pages: | 65-79 |
| Proceedings: | 14th ACM/SIGEVO Workshop on Foundations of Genetic Algorithms |
| ISBN: | 1450346510 and 9781450346511 |
| Types: | Conference paper |
| DOI: | 10.1145/3040718.3040724 |
| ORCIDs: | Witt, Carsten |
Advanced analysis Benchmark functions Black-box complexity Computer Programming Estimation of distribution algorithm Estimation of distribution algorithms Evolutionary algorithms Genetic algorithms Heuristic algorithms Lower bound Lower bounds Population statistics Potential function Run time analysis Run-time analysis Stochastic systems Systems Science Univariate marginal distribution algorithms
Design and analysis of algorithms Discrete optimization Mathematical optimization Optimization with randomized search heuristics Theory and algorithms for application domains Theory of computation Theory of randomized search heuristics estimation of distribution algorithm lower bound run time analysis
