Comma Selection Outperforms Plus Selection on OneMax with Randomly Planted Optima

Joost Jorritsma, Johannes Lengler, Dirk Sudholt

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

7 Citations (Scopus)

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.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.

Original languageEnglish
Title of host publicationGECCO 2023 - Proceedings of the 2023 Genetic and Evolutionary Computation Conference
PublisherAssociation for Computing Machinery, Inc
Pages1602-1610
Number of pages9
ISBN (Electronic)9798400701191
DOIs
Publication statusPublished - 15 Jul 2023
Event2023 Genetic and Evolutionary Computation Conference, GECCO 2023 - Lisbon, Portugal
Duration: 15 Jul 202319 Jul 2023

Conference

Conference2023 Genetic and Evolutionary Computation Conference, GECCO 2023
Country/TerritoryPortugal
CityLisbon
Period15/07/2319/07/23

Bibliographical note

Publisher Copyright:
© 2023 ACM.

Fingerprint

Dive into the research topics of 'Comma Selection Outperforms Plus Selection on OneMax with Randomly Planted Optima'. Together they form a unique fingerprint.

Cite this