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

Publication: Research - peer-reviewArticle in proceedings – Annual report year: 2017

Documents

DOI

View graph of relations

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
Publication date2017
Pages65-79
ISBN (print)9781450346511
DOIs
StatePublished - 2017
Event14th ACM/SIGEVO Workshop on Foundations of Genetic Algorithms - Copenhagen, Denmark

Conference

Conference14th ACM/SIGEVO Workshop on Foundations of Genetic Algorithms
LocationFrederiksberg Campus
CountryDenmark
CityCopenhagen
Period12/01/201715/01/2017
SeriesFoga - Proc. Acm/sigevo Conf. Found. Genet. Algorithms
CitationsWeb of Science® Times Cited: No match on DOI

    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
Download as:
Download as PDF
Select render style:
APAAuthorCBE/CSEHarvardMLAStandardVancouverShortLong
PDF
Download as HTML
Select render style:
APAAuthorCBE/CSEHarvardMLAStandardVancouverShortLong
HTML
Download as Word
Select render style:
APAAuthorCBE/CSEHarvardMLAStandardVancouverShortLong
Word

Download statistics

No data available

ID: 132536169