# Already Moderate Population Sizes Provably Yield Strong Robustness to Noise

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 11 of its 53 references that are in the map.
- First posted on arXiv 2 Apr 2024.

## Builds on (most cited first, 11 of 11)

- [A Tight Runtime Analysis for the (μ + λ) EA](https://mlsanity.com/paper/1812.11061/) (2018)
- [Optimal Parameter Choices via Precise Black-Box Analysis](https://mlsanity.com/paper/1807.03403/) (2018)
- [Analysing the Robustness of Evolutionary Algorithms to Noise: Refined Runtime Bounds and an Example Where Noise is Beneficial](https://mlsanity.com/paper/1812.00966/) (2018)
- [Comma Selection Outperforms Plus Selection on OneMax with Randomly Planted Optima](https://mlsanity.com/paper/2304.09712/) (2023)
- [Runtime Analyses of Multi-Objective Evolutionary Algorithms in the Presence of Noise](https://mlsanity.com/paper/2305.10259/) (2023)
- [Runtime Analysis for Self-adaptive Mutation Rates](https://mlsanity.com/paper/1811.12824/) (2018)
- [Analysing the Robustness of NSGA-II under Noise](https://mlsanity.com/paper/2306.04525/) (2023)
- [Running Time Analysis of the (1+1)-EA for OneMax and LeadingOnes under Bit-wise Noise](https://mlsanity.com/paper/1711.00956/) (2017)
- [Theoretical Study of Optimizing Rugged Landscapes with the cGA](https://mlsanity.com/paper/2211.13801/) (2022)
- [Analysis of Noisy Evolutionary Optimization When Sampling Fails](https://mlsanity.com/paper/1810.05045/) (2018)
- [From Understanding Genetic Drift to a Smart-Restart Mechanism for Estimation-of-Distribution Algorithms](https://mlsanity.com/paper/2206.09090/) (2022)

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

- [MMAO-Cls: Metabolic Multi-Agent Optimization for Joint Feature Selection and Classifier Tuning](https://mlsanity.com/paper/2607.01539/) (2026)

## Abstract (arXiv)

Experience shows that typical evolutionary algorithms can cope well with stochastic disturbances such as noisy function evaluations. In this first mathematical runtime analysis of the (1+λ) and (1,λ) evolutionary algorithms in the presence of prior bit-wise noise, we show that both algorithms can tolerate constant noise probabilities without increasing the asymptotic runtime on the OneMax benchmark. For this, a population size λ suffices that is at least logarithmic in the problem size n. The only previous result in this direction regarded the less realistic one-bit noise model, required a population size super-linear in the problem size, and proved a runtime guarantee roughly cubic in the noiseless runtime for the OneMax benchmark. Our significantly stronger results are based on the novel proof argument that the noiseless offspring can be seen as a biased uniform crossover between the parent and the noisy offspring. We are optimistic that the technical lemmas resulting from this insight will find applications also in future mathematical runtime analyses of evolutionary algorithms.