Abstract
The usual approach in runtime analysis is to derive estimates on the number of fitness function evaluations required by a method until a suitable element of the search space is found. One justification for this is that in real applications, fitness evaluation often contributes the most computational effort. A tacit assumption in this approach is that this effort is uniform and static across the search space. However, this assumption often does not hold in practice: some candidates may be far more expensive to evaluate than others. This might occur, for example, when fitness evaluation requires running a simulation or training a machine learning model.Despite the availability of a wide range of benchmark functions coupled with various runtime performance guarantees, the runtime analysis community currently lacks a solid perspective of handling variable fitness cost. Our goal with this paper is to argue for incorporating this perspective into our theoretical toolbox. We introduce two models of handling variable cost: a simple non-adaptive model together with a more general adaptive model. We prove cost bounds in these scenarios and discuss the implications for taking into account costly regions in the search space.
Original language | English (US) |
---|---|
Title of host publication | GECCO 2023 - Proceedings of the 2023 Genetic and Evolutionary Computation Conference |
Publisher | Association for Computing Machinery, Inc |
Pages | 1611-1618 |
Number of pages | 8 |
ISBN (Electronic) | 9798400701191 |
DOIs | |
State | Published - Jul 15 2023 |
Externally published | Yes |
Event | 2023 Genetic and Evolutionary Computation Conference, GECCO 2023 - Lisbon, Portugal Duration: Jul 15 2023 → Jul 19 2023 |
Publication series
Name | GECCO 2023 - Proceedings of the 2023 Genetic and Evolutionary Computation Conference |
---|
Conference
Conference | 2023 Genetic and Evolutionary Computation Conference, GECCO 2023 |
---|---|
Country/Territory | Portugal |
City | Lisbon |
Period | 7/15/23 → 7/19/23 |
Bibliographical note
Publisher Copyright:© 2023 ACM.
Keywords
- adaptive strategies
- runtime analysis
- variable cost model