# Self-adjusting Population Sizes for the (1, λ)-EA on Monotone Functions

arXiv: https://arxiv.org/abs/2204.00531 · HTML: https://mlsanity.com/paper/2204.00531/

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 1 Apr 2022.

## Built on by (most cited first, 3 of 3)

- [EvoPress: Accurate Dynamic Model Compression via Evolutionary Search](https://mlsanity.com/paper/2410.14649/) (2024)
- [Plus Strategies are Exponentially Slower for Planted Optima of Random Height](https://mlsanity.com/paper/2404.09687/) (2024)
- [Decoupling Numerical and Structural Parameters: An Empirical Study on Adaptive Genetic Algorithms via Deep Reinforcement Learning for the Large-Scale TSP](https://mlsanity.com/paper/2603.20702/) (2026)

## Abstract (arXiv)

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(nlog n) for the number of function evaluations, and for c=1 we show O(nlog n) generations and O(n2loglog n) 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.