Run-Time Analysis of Population-Based Evolutionary Algorithm in Noisy Environments
Adam Prügel‐Bennett, Jonathan E. Rowe, Jonathan Shapiro · 2015
This paper analyses a generational evolutionary algorithm using only selection and uniform crossover. With a probability arbitrarily close to one the evolutionary algorithm is shown to solve onemax in O(n log2(n)) function evaluations using a population of size c,n, log(n). We then show that this algorithm can solve onemax with noise variance n again in O(n log2(n)) function evaluations.