Comma Selection Outperforms Plus Selection on OneMax with Randomly Planted Optima
Joost Jorritsma, Johannes Lengler, Dirk Sudholt
2023Proceedings of the Genetic and Evolutionary Computation Conference14 citationsDOIOpen Access PDF
Abstract
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.
Topics & Concepts
Selection (genetic algorithm)Benchmark (surveying)Local optimumPopulationMathematical optimizationMathematicsEvolutionary algorithmComputer scienceBiologyArtificial intelligenceGeographyDemographyGeodesySociologyEvolutionary Algorithms and ApplicationsMetaheuristic Optimization Algorithms ResearchAdvanced Multi-Objective Optimization Algorithms