OneMax Is Not the Easiest Function for Fitness Improvements
METADATA ONLY
Loading...
Author / Producer
Date
2025
Publication Type
Journal Article
ETH Bibliography
yes
Citations
Altmetric
METADATA ONLY
Data
Rights / License
Abstract
We study the (1:s+1) success rule for controlling the population size of the (1,λ)-EA. It was shown by Hevia Fajardo and Sudholt that this parameter control mechanism can run into problems for large s if the fitness landscape is too easy. They conjectured that this problem is worst for the OneMax benchmark, since in some well-established sense OneMax is known to be the easiest fitness landscape. In this paper, we disprove this conjecture. We show that there exist s and ɛ such that the self-adjusting (1,λ)-EA with the (1:s+1)-rule optimizes OneMax efficiently when started with ɛn zero-bits, but does not find the optimum in polynomial time on Dynamic BinVal. Hence, we show that there are landscapes where the problem of the (1:s+1)-rule for controlling the population size of the (1,λ)-EA is more severe than for OneMax. The key insight is that, while OneMax is the easiest function for decreasing the distance to the optimum, it is not the easiest fitness landscape with respect to finding fitness-improving steps.
Permanent link
Publication status
published
External links
Editor
Book title
Journal / series
Volume
33 (1)
Pages / Article No.
27 - 54
Publisher
MIT Press
Event
Edition / version
Methods
Software
Geographic location
Date collected
Date created
Subject
Parameter control; onemax; (1,λ)-EA; one-fifth rule; dynamic environments; evolutionary algorithm