Comma Selection Outperforms Plus Selection on OneMax with Randomly Planted Optima

Journal article

Evolutionary algorithms (EAs) are general-purpose optimisation algorithms that maintain a population (multiset) of candidate solutions and apply variation operators to create new solutions called offspring. A new population is typically formed using one of two strategies: a EA (plus selection) keeps the best search points out of the union of parents in the old population and offspring, whereas a EA (comma selection) discards all parents and only keeps the best out of offspring. Comma selection may help to escape from local optima, however when and how it is beneficial is subject to an ongoing debate. We propose a new benchmark function to investigate the benefits of comma selection: the well known benchmark function OneMaxwith randomly planted local optima, generated by frozen noise. We show that comma selection (the EA) is faster than plus selection (the EA) on this benchmark, in a fixed-target scenario, and for offspring population sizes for which both algorithms behave differently. For certain parameters, the EAfinds the target in evaluations, with high probability (w.h.p.), while the EAw.h.p. requires 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 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.

Authors: Jorritsma, J; Lengler, J; Sudholt, D

• Publication status: Published
• Peer review status: Peer reviewed
• Publisher: Springer
• Journal: Algorithmica
• Volume: 87
• Issue: 12
• Pages: 1804-1863
• Publication date: 2025-08-18
• Acceptance date: 2025-06-09
• DOI: 10.1007/s00453-025-01330-y
• EISSN: 1432-0541
• ISSN: 0178-4617
• Language: English
• Keywords: Drift analysis; Fixed-target running times; Runtime analysis; Non-elitism; Multimodal optimisation; Comma strategies