Sharp bounds on the runtime of the (1+1) EA via drift analysis and analytic combinatorial tools

Hsien-Kuei Hwang, Carsten Witt

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

56 Downloads (Pure)

Abstract

The expected running time of the classical (1+1) EA on the ONEMAX benchmark function has recently been determined by Hwang et al. (2018) up to additive errors of O((log n)/n). The same approach proposed there also leads to a full asymptotic expansion with errors of the form O(n-K log n) for any K > 0. This precise result is obtained by matched asymptotics with rigorous error analysis (or by solving asymptotically the underlying recurrences via inductive approximation arguments), ideas radically different from well-established techniques for the running time analysis of evolutionary computation such as drift analysis. This paper revisits drift analysis for the (1+1) EA on ONE MAX and obtains that the expected running time E (T), starting from [n/2] one-bits, is determined by the sum of inverse drifts up to logarithmic error terms, more precisely
Original languageEnglish
Title of host publicationProceedings of the 15th ACM/SIGEVO Conference on Foundations of Genetic Algorithms
Number of pages12
PublisherAssociation for Computing Machinery
Publication date2019
Pages1-12
ISBN (Print)978-1-4503-6254-2
DOIs
Publication statusPublished - 2019
Event15th ACM/SIGEVO Conference on Foundations of Genetic Algorithms - Potsdam, Germany
Duration: 27 Aug 201929 Aug 2019

Conference

Conference15th ACM/SIGEVO Conference on Foundations of Genetic Algorithms
CountryGermany
CityPotsdam
Period27/08/201929/08/2019
SeriesProceedings of the 15th Acm/sigevo Conference on Foundations of Genetic Algorithms

Keywords

  • Randomized search heuristics
  • (1+1) EA
  • Drift analysis
  • Asymptotic methods

Fingerprint Dive into the research topics of 'Sharp bounds on the runtime of the (1+1) EA via drift analysis and analytic combinatorial tools'. Together they form a unique fingerprint.

Cite this