General Univariate Estimation-of-Distribution Algorithms

  • 2022-06-22 17:32:04
  • Benjamin Doerr, Marc Dufay
  • 0


We propose a general formulation of a univariate estimation-of-distributionalgorithm (EDA). It naturally incorporates the three classic univariate EDAs\emph{compact genetic algorithm}, \emph{univariate marginal distributionalgorithm} and \emph{population-based incremental learning} as well as the\emph{max-min ant system} with iteration-best update. Our unified descriptionof the existing algorithms allows a unified analysis of these; we demonstratethis by providing an analysis of genetic drift that immediately gives theexisting results proven separately for the four algorithms named above. Ourgeneral model also includes EDAs that are more efficient than the existing onesand these may not be difficult to find as we demonstrate for the OneMax andLeadingOnes benchmarks.


Quick Read (beta)

loading the full paper ...