Upper bounds on the runtime of the univariate marginal distribution algorithm on onemax

A runtime analysis of the Univariate Marginal Distribution Algorithm (UMDA) is presented on the OneMax function for wide ranges of the parameters μ and λ. If μ ≥ 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 [EQUATION] log n for a constant c' > 0 and λ = (1 + Θ(1))μ, the behavior of the algorithm changes and the bound on the expected runtime becomes [EQUATION], which typically even holds if the borders on the marginal probabilities are omitted.