# Comma Selection Outperforms Plus Selection on OneMax with Randomly Planted Optima

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

## Key facts

- Cited by 5 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 19 Apr 2023.

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

- [EvoPress: Accurate Dynamic Model Compression via Evolutionary Search](https://mlsanity.com/paper/2410.14649/) (2024)
- [How the Move Acceptance Hyper-Heuristic Copes With Local Optima: Drastic Differences Between Jumps and Cliffs](https://mlsanity.com/paper/2304.10414/) (2023)
- [How Well Does the Metropolis Algorithm Cope With Local Optima?](https://mlsanity.com/paper/2304.10848/) (2023)
- [Already Moderate Population Sizes Provably Yield Strong Robustness to Noise](https://mlsanity.com/paper/2404.02090/) (2024)
- [Plus Strategies are Exponentially Slower for Planted Optima of Random Height](https://mlsanity.com/paper/2404.09687/) (2024)

## Abstract (arXiv)

It is an ongoing debate whether and how comma selection in evolutionary algorithms helps to escape local optima. We propose a new benchmark function to investigate the benefits of comma selection: OneMax with randomly planted local optima, generated by frozen noise. We show that comma selection (the (1,λ) EA) is faster than plus selection (the (1+λ) EA) on this benchmark, in a fixed-target scenario, and for offspring population sizes λ for which both algorithms behave differently. For certain parameters, the (1,λ) EA finds the target in Theta(n ln n) evaluations, with high probability (w.h.p.), while the (1+λ) EA) w.h.p. requires almost Theta((nln n)2) evaluations. We further show that the advantage of comma selection is not arbitrarily large: w.h.p. comma selection outperforms plus selection at most by a factor of O(n ln n) for most reasonable parameter choices. We develop novel methods for analysing frozen noise and give powerful and general fixed-target results with tail bounds that are of independent interest.