Papers › Self-adjusting Population Sizes for the (1, λ)-EA on Monotone Functions
Self-adjusting Population Sizes for the (1, λ)-EA on Monotone Functions
Marc Kaufmann, Maxime Larcher, Johannes Lengler, Xun Zou
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 behavior 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(nlogn) for the number of function evaluations, and for c=1 we show O(nlogn) generations and O(n²loglogn) 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.
Code
Repository list and official/mentioned flags are the archive's, frozen 2025-07-28. Reachability, where shown, is from one Syntology probe window (2026-09-16 to 2026-09-18); repositories not probed show nothing. GitHub stars are not tracked.
Code Syntology ran Syntology
Not run by Syntology. Nothing on this page verifies that the listed code works.
Results from the paper archive 2025-07-28
No leaderboard rows for this paper in the archive.
Report a problem or propose a change · a person checks every report against the paper or source before anything changes; decisions are listed on /corrections