Upper Bounds on the Running Time of the Univariate Marginal Distribution Algorithm on OneMax
Carsten Witt · Technical University of Denmark, DTU Orbit (Technical University of Denmark, DTU) · 2019
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 $$ .