Simplified runtime analysis of estimation of distribution algorithms

Duc Cuong Dang, Per Kristian Lehre

Research output: Chapter in Book/Report/Conference proceedingConference contribution

30 Citations (Scopus)


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. In this paper, we show that the recently developed levelbased theorem for non-elitist populations is directly applicable to runtime analysis of EDAs. To demonstrate this approach, we derive easily upper bounds on the expected runtime of the UMDA.

Original languageEnglish
Title of host publicationGECCO 2015 - Proceedings of the 2015 Genetic and Evolutionary Computation Conference
PublisherAssociation for Computing Machinery
Number of pages6
ISBN (Electronic)9781450334723
Publication statusPublished - 11 Jul 2015
Event16th Genetic and Evolutionary Computation Conference, GECCO 2015 - Madrid, Spain
Duration: 11 Jul 201515 Jul 2015


Conference16th Genetic and Evolutionary Computation Conference, GECCO 2015


  • Estimation of distribution algorithm
  • Level-based analysis
  • Runtime analysis

ASJC Scopus subject areas

  • Computational Theory and Mathematics
  • Computer Science Applications
  • Software


Dive into the research topics of 'Simplified runtime analysis of estimation of distribution algorithms'. Together they form a unique fingerprint.

Cite this