Lower bounds on the run time of the univariate marginal distribution algorithm on OneMax

Martin S. Krejca, Carsten Witt

Research output: Chapter in Book/Report/Conference proceedingArticle in proceedingsResearchpeer-review

380 Downloads (Pure)

Abstract

The Univariate Marginal Distribution Algorithm (UMDA), a popular estimation of distribution algorithm, is studied from a run time perspective. On the classical OneMax benchmark function, a lower bound of Ω(μ√n + n log n), where μ is the population size, on its expected run time is proved. This is the first direct lower bound on the run time of the UMDA. It is stronger than the bounds that follow from general black-box complexity theory and is matched by the run time of many evolutionary algorithms. The results are obtained through advanced analyses of the stochastic change of the frequencies of bit values maintained by the algorithm, including carefully designed potential functions. These techniques may prove useful in advancing the field of run time analysis for estimation of distribution algorithms in general.
Original languageEnglish
Title of host publication14th ACM/SIGEVO Workshop on Foundations of Genetic Algorithms
PublisherAssociation for Computing Machinery
Publication date2017
Pages65-79
ISBN (Print)9781450346511
DOIs
Publication statusPublished - 2017
Event14th ACM/SIGEVO Workshop on Foundations of Genetic Algorithms - Frederiksberg Campus, Copenhagen, Denmark
Duration: 12 Jan 201715 Jan 2017

Conference

Conference14th ACM/SIGEVO Workshop on Foundations of Genetic Algorithms
LocationFrederiksberg Campus
Country/TerritoryDenmark
CityCopenhagen
Period12/01/201715/01/2017

Keywords

  • Computer Programming
  • Systems Science
  • Estimation of distribution algorithm
  • Lower bound
  • Run time analysis
  • Genetic algorithms
  • Heuristic algorithms
  • Population statistics
  • Stochastic systems
  • Advanced analysis
  • Benchmark functions
  • Black-box complexity
  • Estimation of distribution algorithms
  • Lower bounds
  • Potential function
  • Run-time analysis
  • Univariate marginal distribution algorithms
  • Evolutionary algorithms

Fingerprint

Dive into the research topics of 'Lower bounds on the run time of the univariate marginal distribution algorithm on OneMax'. Together they form a unique fingerprint.

Cite this