On the robustness of evolutionary algorithms to noise
Dirk Sudholt · Proceedings of the Genetic and Evolutionary Computation Conference · 2018
We present refined results for the expected optimisation time of the (1+1) EA and the (1+λ) EA on LeadingOnes in the prior noise model, where in each fitness evaluation the search point is altered before evaluation with probability p. Previous work showed that the (1+1) EA runs in polynomial time if p = O((log n)/n2) and needs superpolynomial 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 Θ(n2) · exp(Θ(pn2)), allowing for the first time to locate the threshold between polynomial and superpolynomial expected times at p = Θ((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.42 log n can effectively deal with much higher noise than known before.