# Analysing the Robustness of Evolutionary Algorithms to Noise: Refined Runtime Bounds and an Example Where Noise is Beneficial

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

## Key facts

- Cited by 5 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 3 Dec 2018.

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

- [Runtime Analyses of Multi-Objective Evolutionary Algorithms in the Presence of Noise](https://mlsanity.com/paper/2305.10259/) (2023)
- [From Understanding Genetic Drift to a Smart-Restart Mechanism for Estimation-of-Distribution Algorithms](https://mlsanity.com/paper/2206.09090/) (2022)
- [Fourier Analysis Meets Runtime Analysis: Precise Runtimes on Plateaus](https://mlsanity.com/paper/2302.08021/) (2023)
- [Already Moderate Population Sizes Provably Yield Strong Robustness to Noise](https://mlsanity.com/paper/2404.02090/) (2024)
- [Larger Offspring Populations Help the (1 + (λ, λ)) Genetic Algorithm to Overcome the Noise](https://mlsanity.com/paper/2305.04553/) (2023)

## Abstract (arXiv)

We analyse the performance of well-known evolutionary algorithms (1+1)EA and (1+λ)EA in the prior noise model, where in each fitness evaluation the search point is altered before evaluation with probability p. We present refined results for the expected optimisation time of the (1+1)EA and the (1+λ)EA on the function LeadingOnes, where bits have to be optimised in sequence. Previous work showed that the (1+1)EA on LeadingOnes runs in polynomial expected time if p = O((log n)/n2) and needs superpolynomial expected time if p = ω((log n)/n), leaving a huge gap for which no results were known. We close this gap by showing that the expected optimisation time is Theta(n2) · exp(Theta(minpn2, n)) for all p ≤ 1/2, allowing for the first time to locate the threshold between polynomial and superpolynomial expected times at p = Theta((log n)/n2). Hence the (1+1)EA on LeadingOnes is much more sensitive to noise than previously thought. We also show that offspring populations of size λ ≥ 3.42log n can effectively deal with much higher noise than known before. Finally, we present an example of a rugged landscape where prior noise can help to escape from local optima by blurring the landscape and allowing a hill climber to see the underlying gradient. We prove that in this particular setting noise can have a highly beneficial effect on performance.