EUVIMEDEUVIMED entdecken
Crossref

Precise Runtime Analysis for Plateau Functions

Denis Antipov, Benjamin Doerr

ACM Transactions on Evolutionary Learning and Optimization · 2021

DOI: 10.1145/3469800 ↗

Kurz gefasst

Fachartikel in der Zeitschrift ACM Transactions on Evolutionary Learning and Optimization, 2021. Verfasst von Denis Antipov und 1 weiteren Autor:innen. Die Arbeit wurde bisher 11-mal zitiert (Crossref) und nennt 67 Literaturangaben. Gefördert von: National Center for Cognitive Research of ITMO University, Investissements d’avenir project.

AbstractBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

To gain a better theoretical understanding of how evolutionary algorithms (EAs) cope with plateaus of constant fitness, we propose the n -dimensional Plateau k function as natural benchmark and analyze how different variants of the (1 + 1) EA optimize it. The Plateau k function has a plateau of second-best fitness in a ball of radius k around the optimum. As evolutionary algorithm, we regard the (1 + 1) EA using an arbitrary unbiased mutation operator. Denoting by α the random number of bits flipped in an application of this operator and assuming that Pr [α = 1] has at least some small sub-constant value, we show the surprising result that for all constant k ≥ 2, the runtime T follows a distribution close to the geometric one with success probability equal to the probability to flip between 1 and k bits divided by the size of the plateau. Consequently, the expected runtime is the inverse of this number, and thus only depends on the probability to flip between 1 and k bits, but not on other characteristics of the mutation operator. Our result also implies that the optimal mutation rate for standard bit mutation here is approximately k/(en) . Our main analysis tool is a combined analysis of the Markov chains on the search point space and on the Hamming level space, an approach that promises to be useful also for other plateau problems.

Förderung

  • National Center for Cognitive Research of ITMO University
  • Investissements d’avenir project

Zitieren

APA

Antipov, D., & Doerr, B. (2021). Precise Runtime Analysis for Plateau Functions. ACM Transactions on Evolutionary Learning and Optimization. https://doi.org/10.1145/3469800

Vancouver

Antipov D, Doerr B. Precise Runtime Analysis for Plateau Functions. ACM Transactions on Evolutionary Learning and Optimization. 2021. doi:10.1145/3469800

BibTeX
@article{Antipov2021,
  author = {Antipov, Denis and Doerr, Benjamin},
  title = {Precise Runtime Analysis for Plateau Functions},
  journal = {ACM Transactions on Evolutionary Learning and Optimization},
  year = {2021},
  doi = {10.1145/3469800}
}
Kostenlos starten →