Open access
Date
2023-11-10Type
- Journal Article
ETH Bibliography
yes
Altmetrics
Abstract
We study the (1, λ)-EA with mutation rate c/n for c ≤ 1, where the population size is adaptively controlled with the (1 : s + 1)-success rule. Recently, Hevia Fajardo and Sudholt have shown that this setup with c = 1 is efficient on OneMax for s < 1, but inefficient if s ≥ 18. Surprisingly, the hardest part is not close to the optimum, but rather at linear distance. We show that this behaviour is not specific to OneMax. If s is small, then the algorithm is efficient on all monotone functions, and if s is large, then it needs superpolynomial time on all monotone functions. In the former case, for c < 1 we show a O(n) upper bound for the number of generations and O(n logn) for the number of function evaluations, and for c = 1 we show O(n logn) generations and O(n2 log logn) evaluations. We also show formally that optimization is always fast, regardless of s, if the algorithm starts in proximity of the optimum. All results also hold in a dynamic environment where the fitness function changes in each generation. Show more
Permanent link
https://doi.org/10.3929/ethz-b-000637220Publication status
publishedExternal links
Journal / series
Theoretical Computer ScienceVolume
Pages / Article No.
Publisher
ElsevierSubject
Parameter control; Self-adaptation; (1, λ)-EA; One-fifth rule; Monotone functions; Dynamic environments; Evolutionary algorithmOrganisational unit
08738 - Lengler, Johannes (Tit.-Prof.) / Lengler, Johannes (Tit.-Prof.)
03672 - Steger, Angelika / Steger, Angelika
Funding
192079 - DynaGIRG (SNF)
173721 - Temporal Information Integration in Neural Networks (SNF)
More
Show all metadata
ETH Bibliography
yes
Altmetrics