Comma Selection Outperforms Plus Selection on OneMax with Randomly Planted Optima
Joost Jorritsma, Johannes Lengler, Dirk Sudholt · Proceedings of the Genetic and Evolutionary Computation Conference · 2023
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 Θ(n ln n) evaluations, with high probability (w.h.p.), while the (1 + Λ) EA w.h.p. requires almost Θ((n ln n)2) evaluations.