TY - JOUR AU - Dang, Duc-Cuong AU - Eremeev, Anton AU - Lehre, Per Kristian PY - 2021/05/18 Y2 - 2024/03/29 TI - Escaping Local Optima with Non-Elitist Evolutionary Algorithms JF - Proceedings of the AAAI Conference on Artificial Intelligence JA - AAAI VL - 35 IS - 14 SE - AAAI Technical Track on Search and Optimization DO - 10.1609/aaai.v35i14.17457 UR - https://ojs.aaai.org/index.php/AAAI/article/view/17457 SP - 12275-12283 AB - Most discrete evolutionary algorithms (EAs) implement elitism,meaning that they make the biologically implausible assumptionthat the fittest individuals never die. While elitism favoursexploitation and ensures that the best seen solutions are notlost, it has been widely conjectured that non-elitism isnecessary to explore promising fitness valleys without gettingstuck in local optima. Determining when non-elitist EAsoutperform elitist EAs has been one of the most fundamental openproblems in evolutionary computation. A recent analysis of anon-elitist EA shows that this algorithm does not outperform itselitist counterparts on the benchmark problem JUMP.We solve this open problem through rigorous runtime analysis ofelitist and non-elitist population-based EAs on a class ofmulti-modal problems. We show that with 3-tournament selectionand appropriate mutation rates, the non-elitist EA optimises themulti-modal problem in expected polynomial time, while an elitistEA requires exponential time with overwhelmingly highprobability.A key insight in our analysis is the non-linear selection profileof the tournament selection mechanism which, with appropriatemutation rates, allows a small sub-population to reside on thelocal optimum while the rest of the population explores thefitness valley. In contrast, we show that the comma-selectionmechanism which does not have this non-linear profile, fails tooptimise this problem in polynomial time.The theoretical analysis is complemented with an empiricalinvestigation on instances of the set cover problem, showing thatnon-elitist EAs can perform better than the elitist ones. We alsoprovide examples where usage of mutation rates close to the errorthresholds is beneficial when employing non-elitistpopulation-based EAs. ER -