Upper bounds on the runtime of the univariate marginal distribution algorithm on OneMax

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

DOI

View graph of relations

A runtime analysis of the Univariate Marginal Distribution Algorithm (UMDA) is presented on the OneMax function for wide ranges of the parameters μ and λ. If μ ≥ c log n for some constant c > 0 and λ = (1 + O(1))μ, a general bound O(μn) on the expected runtime is obtained. This bound crucially assumes that all marginal probabilities of the algorithm are confined to the interval [1/n, 1 - 1/n]. If μ ≥ c'√n log n for a constant c' > 0 and λ = (1 + O(1))μ, the behavior of the algorithm changes and the bound on the expected runtime becomes O (μ√n), which typically even holds if the borders on the marginal probabilities are omitted. The results supplement the recently derived lower bound Ω (μ √n+ n log n) by Krejca and Witt (FOGA 2017) and turn out as tight for the two very different values μ = c log n and p = c'√n log n. They also improve the previously best known upper bound O(n log n log log n) by Dang and Lehre (GECCO 2015).
Original languageEnglish
Title of host publicationProceedings of 2017 Genetic and Evolutionary Computation Conference
Publication date2017
Pages1415-1422
ISBN (print)9781450349208
DOIs
StatePublished - 2017
EventThe Genetic and Evolutionary Computation Conference (2017) - Berlin, Germany

Conference

ConferenceThe Genetic and Evolutionary Computation Conference (2017)
Number`
LocationVIENNA HOUSE ANDEL'S BERLIN Landsberger Allee 106
CountryGermany
CityBerlin
Period15/07/201719/07/2017
Internet address
SeriesGecco - Proc. Genet. Evol. Comput. Conf
CitationsWeb of Science® Times Cited: No match on DOI

    Keywords

  • Œeory, Estimation of Distribution Algorithms, UMDA, Runtime Analysis
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

ID: 134946610