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 a non-elitist EA shows that this algorithm does not outperform its elitist counterparts on the 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 the multi-modal problem in expected polynomial time, while an elitist 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 comma-selection mechanism which does not have this non-linear profile, fails to optimise this problem in polynomial time. The theoretical analysis is complemented with an 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.