Paper Info
Title
Upper Bounds on the Running Time of the Univariate Marginal Distribution Algorithm on OneMax
Abstract
The Univariate Marginal Distribution Algorithm (UMDA) is a randomized search heuristic that builds a stochastic model of the underlying optimization problem by repeatedly sampling \(\lambda \) solutions and adjusting the model according to the best \(\mu \) samples. We present a running time analysis of the UMDA on the classical OneMax benchmark function for wide ranges of the parameters \(\mu \) and \(\lambda \). If \(\mu \ge c\log n\) for some constant \(c>0\) and \(\lambda =(1+\varTheta (1))\mu \), we obtain a general bound \(O(\mu n)\) on the expected running time. This bound crucially assumes that all marginal probabilities of the algorithm are confined to the interval \([1/n,1-1/n]\). If \(\mu \ge c' \sqrt{n}\log n\) for a constant \(c'>0\) and \(\lambda =(1+\varTheta (1))\mu \), the behavior of the algorithm changes and the bound on the expected running time becomes \(O(\mu \sqrt{n})\), which typically holds even if the borders on the marginal probabilities are omitted. The results supplement the recently derived lower bound \(\varOmega (\mu \sqrt{n}+n\log n)\) by Krejca and Witt (Proceedings of FOGA 2017, ACM Press, New York, pp 65–79, 2017) and turn out to be tight for the two very different choices \(\mu =c\log n\) and \(\mu =c'\sqrt{n}\log n\). They also improve the previously best known upper bound \(O(n\log n\log \log n)\) by Dang and Lehre (Proceedings of GECCO ’15, ACM Press, New York, pp 513–518, 2015) that was established for \(\mu =c\log n\) and \(\lambda =(1+\varTheta (1))\mu \).
Year
DOI
Venue
2019
10.1007/s00453-018-0463-0
Algorithmica
Keywords
Field
DocType
Randomized search heuristics,Estimation-of-distribution algorithms,UMDA,Running time analysis
Binary logarithm,Discrete mathematics,Combinatorics,Upper and lower bounds,Univariate marginal distribution algorithm,Mathematics,Lambda
Journal
Volume
Issue
ISSN
81.0
SP2
1432-0541
Citations 
PageRank 
References 
4
0.39
22
Authors
1
Name
Order
Citations
PageRank
Carsten Witt198759.83