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 language | English |
---|---|
Title of host publication | Parallel Problem Solving from Nature |
Editors | Thomas Bäck, Mike Preuss, André Deutz, Michael Emmerich, Hao Wang, Carola Doerr, Heike Trautmann |
Publisher | Springer |
Publication date | 2020 |
Pages | 648-660 |
ISBN (Print) | 9783030581145 |
DOIs | |
Publication status | Published - 2020 |
Event | 16th International Conference on Parallel Problem Solving from Nature - Leiden, Netherlands Duration: 5 Sep 2020 → 9 Sep 2020 Conference number: 16 |
Conference
Conference | 16th International Conference on Parallel Problem Solving from Nature |
---|---|
Number | 16 |
Country/Territory | Netherlands |
City | Leiden |
Period | 05/09/2020 → 09/09/2020 |
Series | Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) |
---|---|
Volume | 12270 LNCS |
ISSN | 0302-9743 |