# Upper Bounds on the Runtime of the Univariate Marginal Distribution Algorithm on OneMax

arXiv: https://arxiv.org/abs/1704.00026 · HTML: https://mlsanity.com/paper/1704.00026/

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 31 Mar 2017.

## Built on by (most cited first, 4 of 4)

- [Many Objective Problems Where Crossover is Provably Essential](https://mlsanity.com/paper/2412.18375/) (2024)
- [From Understanding Genetic Drift to a Smart-Restart Mechanism for Estimation-of-Distribution Algorithms](https://mlsanity.com/paper/2206.09090/) (2022)
- [General Univariate Estimation-of-Distribution Algorithms](https://mlsanity.com/paper/2206.11198/) (2022)
- [Larger Offspring Populations Help the (1 + (λ, λ)) Genetic Algorithm to Overcome the Noise](https://mlsanity.com/paper/2305.04553/) (2023)

## Abstract (arXiv)

A runtime analysis of the Univariate Marginal Distribution Algorithm (UMDA) is presented on the OneMax function for wide ranges of its parameters μ and λ. If μ≥ clog n for some constant c>0 and λ=(1+Theta(1))μ, a general bound O(μ n) on the expected runtime is obtained. This bound crucially assumes that all marginal probabilities of the algorithm are confined to the interval [1/n,1-1/n]. If μ≥ c' √nlog n for a constant c'>0 and λ=(1+Theta(1))μ, the behavior of the algorithm changes and the bound on the expected runtime becomes O(μ√n), which typically even holds if the borders on the marginal probabilities are omitted. The results supplement the recently derived lower bound Omega(μ√n+nlog n) by Krejca and Witt (FOGA 2017) and turn out as tight for the two very different values μ=clog n and μ=c'√nlog n. They also improve the previously best known upper bound O(nlog nloglog n) by Dang and Lehre (GECCO 2015).