Improved runtime bounds for the univariate marginal distribution algorithm via anti-concentration

Per Kristian Lehre, Phan Trung Hai Nguyen

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

27 Citations (Scopus)
185 Downloads (Pure)


Unlike traditional evolutionary algorithms which produce offspring via genetic operators, Estimation of Distribution Algorithms (EDAs) sample solutions from probabilistic models which are learned from selected individuals. It is hoped that EDAs may improve optimisation performance on epistatic fitness landscapes by learning variable interactions. However, hardly any rigorous results are available to support claims about the performance of EDAs, even for fitness functions without epistasis. The expected runtime of the Univariate Marginal Distribution Algorithm (UMDA) on OneMax was recently shown to be in O (nX log X) [9]. Later, Krejca and Witt proved the lower bound Q (Xs/n + n log n) via an involved drift analysis [16]. We prove a O (nX) bound, given some restrictions on the population size. This implies the tight bound 8 (n log n) when X = O (log n), matching the runtime of classical EAs. Our analysis uses the level-based theorem and anti-concentration properties of the Poisson-binomial distribution. We expect that these generic methods will facilitate further analysis of EDAs.

Original languageEnglish
Title of host publicationGECCO '17 Proceedings of the Genetic and Evolutionary Computation Conference
PublisherAssociation for Computing Machinery
Number of pages8
ISBN (Print)978-1-4503-4920-8
Publication statusPublished - 1 Jul 2017
EventGECCO 2017:: The Genetic and Evolutionary Computation Conference - Berlin, Germany
Duration: 15 Jul 201719 Jul 2017


ConferenceGECCO 2017:
Internet address


  • Runtime Analysis
  • Level-based Analysis
  • Estimation of Distribution Algorithms

ASJC Scopus subject areas

  • Software
  • Computer Science Applications
  • Computational Theory and Mathematics


Dive into the research topics of 'Improved runtime bounds for the univariate marginal distribution algorithm via anti-concentration'. Together they form a unique fingerprint.

Cite this