Simplified Runtime Analysis of Estimation of Distribution Algorithms
Duc-Cuong Dang, Per Kristian Lehre · 2015
Estimation of distribution algorithms (EDA) are stochastic search methods that look for optimal solutions by learning and sampling from probabilistic models. Despite their popularity, there are only few rigorous theoretical analyses of their performance. Even for the simplest EDAs, such as the Univariate Marginal Distribution Algorithm (UMDA) which assumes independence between decision variables, there are only a handful of results about its runtime, and results for simple functions such as Onemax are still missing.