Upper Bounds on the Running Time of the Univariate Marginal Distribution Algorithm on OneMax

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+\Theta (1\left)\right)\mu$, we obtain a general bound $O\left(\mu n\right)$ 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^{\prime }\sqrt{n}\log n$ for a constant $c^{\prime }>0$ and $\lambda =(1+\Theta (1\left)\right)\mu$, the behavior of the algorithm changes and the bound on the expected running time becomes $O\left(\mu \sqrt{n}\right)$, which typically holds even if the borders on the marginal probabilities are omitted. The results supplement the recently derived lower bound $\Omega (\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^{\prime }\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+\Theta (1\left)\right)\mu$.