Improved fixed-budget results via drift analysis

Timo Kötzing*, Carsten Witt

*Corresponding author for this work

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

Abstract

Fixed-budget theory is concerned with computing or bounding the fitness value achievable by randomized search heuristics within a given budget of fitness function evaluations. Despite recent progress in fixed-budget theory, there is a lack of general tools to derive such results. We transfer drift theory, the key tool to derive expected optimization times, to the fixed-budged perspective. A first and easy-to-use statement concerned with iterating drift in so-called greed-admitting scenarios immediately translates into bounds on the expected function value. Afterwards, we consider a more general tool based on the well-known variable drift theorem. Applications of this technique to the LeadingOnes benchmark function yield statements that are more precise than the previous state of the art.

Original languageEnglish
Title of host publicationParallel Problem Solving from Nature
EditorsThomas Bäck, Mike Preuss, André Deutz, Michael Emmerich, Hao Wang, Carola Doerr, Heike Trautmann
PublisherSpringer
Publication date2020
Pages648-660
ISBN (Print)9783030581145
DOIs
Publication statusPublished - 2020
Event16th International Conference on Parallel Problem Solving from Nature, PPSN 2020 - Leiden, Netherlands
Duration: 5 Sep 20209 Sep 2020

Conference

Conference16th International Conference on Parallel Problem Solving from Nature, PPSN 2020
CountryNetherlands
CityLeiden
Period05/09/202009/09/2020
SeriesLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume12270 LNCS
ISSN0302-9743

Fingerprint Dive into the research topics of 'Improved fixed-budget results via drift analysis'. Together they form a unique fingerprint.

Cite this