Runtime analysis of the univariate marginal distribution algorithm under low selective pressure and prior noise

Per Kristian Lehre, Phan Trung Hai Nguyen

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

3 Citations (Scopus)
146 Downloads (Pure)

Abstract

We perform a rigorous runtime analysis for the Univariate Marginal Distribution Algorithm on the LeadingOnes function, a well-known benchmark function in the theory community of evolutionary computation with a high correlation between decision variables. For a problem instance of size n, the currently best known upper bound on the expected runtime is O (nλ log λ + n2) (Dang and Lehre, GECCO 2015), while a lower bound necessary to understand how the algorithm copes with variable dependencies is still missing. Motivated by this, we show that the algorithm requires a eΩ(µ) runtime with high probability and in expectation if the selective pressure is low; otherwise, we obtain a lower bound of Ω(nλ/( log(λ−µ))) on the expected runtime. Furthermore, we for the first time consider the algorithm on the function under a prior noise model and obtain an O(n2) expected runtime for the optimal parameter settings. In the end, our theoretical results are accompanied by empirical findings, not only matching with rigorous analyses but also providing new insights into the behaviour of the algorithm.
Original languageEnglish
Title of host publicationThe Genetic and Evolutionary Computation Conference 2019 (GECCO 2019)
EditorsManuel López-Ibáñez
PublisherAssociation for Computing Machinery (ACM)
Pages1497-1505
Number of pages9
ISBN (Electronic)978-1-4503-6111-8
DOIs
Publication statusPublished - 13 Jul 2019
EventThe Genetic and Evolutionary Computation Conference 2019 (GECCO 2019) - Prague, Czech Republic
Duration: 13 Jul 201917 Jul 2019

Publication series

NameGECCO 2019 - Proceedings of the 2019 Genetic and Evolutionary Computation Conference

Conference

ConferenceThe Genetic and Evolutionary Computation Conference 2019 (GECCO 2019)
Country/TerritoryCzech Republic
CityPrague
Period13/07/1917/07/19

Keywords

  • Univariate marginal distribution algorithm
  • eadingones
  • noisy optimisation
  • running time analysis
  • theory

Fingerprint

Dive into the research topics of 'Runtime analysis of the univariate marginal distribution algorithm under low selective pressure and prior noise'. Together they form a unique fingerprint.

Cite this