# Does Comma Selection Help To Cope With Local Optima

arXiv: https://arxiv.org/abs/2004.01274 · HTML: https://mlsanity.com/paper/2004.01274/

## Key facts

- Cited by 15 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 2 Apr 2020.

## Built on by (most cited first, 15 of 15)

- [A First Runtime Analysis of the NSGA-II on a Multimodal Problem](https://mlsanity.com/paper/2204.13750/) (2022)
- [Runtime Analysis for the NSGA-II: Provable Speed-Ups From Crossover](https://mlsanity.com/paper/2208.08759/) (2022)
- [Lazy Parameter Tuning and Control: Choosing All Parameters Randomly From a Power-Law Distribution](https://mlsanity.com/paper/2104.06714/) (2021)
- [Lower Bounds from Fitness Levels Made Easy](https://mlsanity.com/paper/2104.03372/) (2021)
- [Choosing the Right Algorithm With Hints From Complexity Theory](https://mlsanity.com/paper/2109.06584/) (2021)
- [How the Move Acceptance Hyper-Heuristic Copes With Local Optima: Drastic Differences Between Jumps and Cliffs](https://mlsanity.com/paper/2304.10414/) (2023)
- [An Extended Jump Functions Benchmark for the Analysis of Randomized Search Heuristics](https://mlsanity.com/paper/2105.03090/) (2021)
- [Hyper-Heuristics Can Profit From Global Variation Operators](https://mlsanity.com/paper/2407.14237/) (2024)
- [Towards a Stronger Theory for Permutation-based Evolutionary Algorithms](https://mlsanity.com/paper/2204.07637/) (2022)
- [How Well Does the Metropolis Algorithm Cope With Local Optima?](https://mlsanity.com/paper/2304.10848/) (2023)
- [When Non-Elitism Meets Time-Linkage Problems](https://mlsanity.com/paper/2104.06831/) (2021)
- [From Understanding Genetic Drift to a Smart-Restart Mechanism for Estimation-of-Distribution Algorithms](https://mlsanity.com/paper/2206.09090/) (2022)
- [Plus Strategies are Exponentially Slower for Planted Optima of Random Height](https://mlsanity.com/paper/2404.09687/) (2024)
- [Runtime Analysis for Permutation-based Evolutionary Algorithms](https://mlsanity.com/paper/2207.04045/) (2022)
- [Larger Offspring Populations Help the (1 + (λ, λ)) Genetic Algorithm to Overcome the Noise](https://mlsanity.com/paper/2305.04553/) (2023)

## Abstract (arXiv)

One hope when using non-elitism in evolutionary computation is that the ability to abandon the current-best solution aids leaving local optima. To improve our understanding of this mechanism, we perform a rigorous runtime analysis of a basic non-elitist evolutionary algorithm (EA), the (μ,λ) EA, on the most basic benchmark function with a local optimum, the jump function. We prove that for all reasonable values of the parameters and the problem, the expected runtime of the (μ,λ)~EA is, apart from lower order terms, at least as large as the expected runtime of its elitist counterpart, the (μ+λ)~EA (for which we conduct the first runtime analysis on jump functions to allow this comparison). Consequently, the ability of the (μ,λ)~EA to leave local optima to inferior solutions does not lead to a runtime advantage. We complement this lower bound with an upper bound that, for broad ranges of the parameters, is identical to our lower bound apart from lower order terms. This is the first runtime result for a non-elitist algorithm on a multi-modal problem that is tight apart from lower order terms.