Escaping Local Optima with Non-Elitist Evolutionary Algorithms

Most discrete evolutionary algorithms (EAs) implement elitism, meaning that they make the biologically implausible assumption that the fittest individuals never die. While elitism favours exploitation and ensures that the best seen solutions are not lost, it has been widely conjectured that non-elitism is necessary to explore promising fitness valleys without getting stuck in local optima. Determining when non-elitist EAs outperform elitist EAs has been one of the most fundamental open problems in evolutionary computation. A recent analysis of the ($\mu$,~$\lambda$)~EA shows that non-elitism does not outperform its elitist counterparts on the theoretical benchmark problem Jump.

We solve this open problem through rigorous runtime analysis of elitist and non-elitist population-based EAs on a class of multi-modal problems. We show that with 3-tournament selection and appropriate mutation rates, the non-elitist EA optimises a multi-modal problem in expected polynomial time $O(n\lambda\log(\lambda)+n^2\log n)$, while the elitist ($\mu$+$\lambda$)~EA requires exponential time with overwhelmingly high probability.

A key insight in our analysis is the non-linear selection profile of the tournament selection mechanism which, with appropriate mutation rates, allows a small sub-population to reside on the local optimum while the rest of the population explores the fitness valley. In contrast, we show that the $(\mu,\lambda)$-selection mechanism which does not have this non-linear profile, fails to optimise this problem in polynomial time.

The theoretical analysis is complemented with empirical investigation on instances of the set cover problem, showing that non-elitist EAs can perform better than the elitist ones. We also provide examples where usage of mutation rates close to the error thresholds is beneficial when employing non-elitist population-based EAs.