Already Moderate Population Sizes Provably Yield Strong Robustness to Noise
This provides a theoretical foundation for robustness in evolutionary algorithms, addressing noise tolerance for practitioners in optimization, though it is incremental as it builds on prior work with a more realistic noise model.
The paper tackles the problem of evolutionary algorithms' runtime under prior bit-wise noise, showing that both (1+λ) and (1,λ) algorithms can tolerate constant noise probabilities without asymptotic runtime increase on OneMax, requiring only a logarithmic population size in problem size n.
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.