General Univariate Estimation-of-Distribution Algorithms
This work provides a theoretical framework for analyzing and improving EDAs, which are incremental for optimization algorithms in evolutionary computation.
The authors proposed a general formulation for univariate estimation-of-distribution algorithms (EDAs) that unifies several classic algorithms, enabling a unified analysis of genetic drift and identifying more efficient EDAs for benchmarks like OneMax and LeadingOnes.
We propose a general formulation of a univariate estimation-of-distribution algorithm (EDA). It naturally incorporates the three classic univariate EDAs \emph{compact genetic algorithm}, \emph{univariate marginal distribution algorithm} and \emph{population-based incremental learning} as well as the \emph{max-min ant system} with iteration-best update. Our unified description of the existing algorithms allows a unified analysis of these; we demonstrate this by providing an analysis of genetic drift that immediately gives the existing results proven separately for the four algorithms named above. Our general model also includes EDAs that are more efficient than the existing ones and these may not be difficult to find as we demonstrate for the OneMax and LeadingOnes benchmarks.