Upper Bounds on the Runtime of the Univariate Marginal Distribution Algorithm on OneMax
This work provides theoretical insights into the performance of evolutionary algorithms, specifically UMDA, which is incremental as it refines existing bounds for a well-studied benchmark problem.
The paper presents runtime analysis of the Univariate Marginal Distribution Algorithm (UMDA) on the OneMax function, deriving upper bounds of O(μn) and O(μ√n) for different parameter ranges, which improve upon previous results and match known lower bounds in specific cases.
A runtime analysis of the Univariate Marginal Distribution Algorithm (UMDA) is presented on the OneMax function for wide ranges of its parameters $μ$ and $λ$. If $μ\ge c\log n$ for some constant $c>0$ and $λ=(1+Θ(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 $μ\ge c' \sqrt{n}\log n$ for a constant $c'>0$ and $λ=(1+Θ(1))μ$, the behavior of the algorithm changes and the bound on the expected runtime becomes $O(μ\sqrt{n})$, which typically even holds if the borders on the marginal probabilities are omitted. The results supplement the recently derived lower bound $Ω(μ\sqrt{n}+n\log n)$ by Krejca and Witt (FOGA 2017) and turn out as tight for the two very different values $μ=c\log n$ and $μ=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 (GECCO 2015).