Comma Selection Outperforms Plus Selection on OneMax with Randomly Planted Optima

Abstract 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 $$(\mu +\lambda )$$ EA (plus selection) keeps the best $$\mu $$ search points out of the union of $$\mu $$ parents in the old population and $$\lambda $$ offspring, whereas a $$(\mu ,\lambda )$$ EA (comma selection) discards all parents and only keeps the best $$\mu $$ out of $$\lambda $$ 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 OneMax with randomly planted local optima, generated by frozen noise. We show that comma selection (the $${(1,\lambda )}$$ EA) is faster than plus selection (the $${(1+\lambda )}$$ EA) on this benchmark, in a fixed-target scenario, and for offspring population sizes $$\lambda $$ for which both algorithms behave differently. For certain parameters, the $${(1,\lambda )}$$ EAfinds the target in $$\Theta (n \ln n)$$ evaluations, with high probability (w.h.p.), while the $${(1+\lambda )}$$ EAw.h.p. requires $$\omega (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.