Abstract
In the discrete domain, self-adjusting parameters of evolutionary algorithms (EAs) has emerged as a fruitful research area with many runtime analyses showing that self-adjusting parameters can out-perform the best fixed parameters. Most existing runtime analyses focus on elitist EAs on simple problems, for which moderate performance gains were shown. Here we consider a much more challenging scenario: the multimodal function Cliff, defined as an example where a (1, λ) EA is effective, and for which the best known upper runtime bound for standard EAs is O(n25).
We prove that a (1, λ) EA self-adjusting the offspring population size λ using success-based rules optimises Cliff in O(n) expected generations and O(n log n) expected evaluations. Along the way, we prove tight upper and lower bounds on the runtime for fixed λ (up to a logarithmic factor) and identify the runtime for the best fixed λ as nη for η ≈ 3.9767 (up to sub-polynomial factors). Hence, the self-adjusting (1, λ) EA outperforms the best fixed parameter by a factor of at least n2.9767 (up to sub-polynomial factors).
We prove that a (1, λ) EA self-adjusting the offspring population size λ using success-based rules optimises Cliff in O(n) expected generations and O(n log n) expected evaluations. Along the way, we prove tight upper and lower bounds on the runtime for fixed λ (up to a logarithmic factor) and identify the runtime for the best fixed λ as nη for η ≈ 3.9767 (up to sub-polynomial factors). Hence, the self-adjusting (1, λ) EA outperforms the best fixed parameter by a factor of at least n2.9767 (up to sub-polynomial factors).
Original language | English |
---|---|
Title of host publication | FOGA '21 |
Subtitle of host publication | Proceedings of the 16th ACM/SIGEVO Conference on Foundations of Genetic Algorithms |
Place of Publication | New York |
Publisher | Association for Computing Machinery (ACM) |
Number of pages | 15 |
ISBN (Print) | 9781450383523 |
DOIs | |
Publication status | Published - 6 Sept 2021 |
Event | FOGA '21: Foundations of Genetic Algorithms XVI - Virtual Duration: 6 Sept 2021 → 8 Sept 2021 |
Publication series
Name | FOGA: Foundations of Genetic Algorithms |
---|---|
Publisher | ACM |
Conference
Conference | FOGA '21: Foundations of Genetic Algorithms XVI |
---|---|
Abbreviated title | FOGA '21 |
Period | 6/09/21 → 8/09/21 |