Lower bounds on the runtime of crossover-based algorithms via decoupling and family graphs

Andrew M. Sutton, Carsten Witt

Research output: Contribution to journalConference articleResearchpeer-review

Abstract

The runtime analysis of evolutionary algorithms using crossover as search operator has recently produced remarkable results indicating benefits and drawbacks of crossover and illustrating its working principles. Virtually all these results are restricted to upper bounds on the running time of the crossover-based algorithms. This work addresses this lack of lower bounds and rigorously bounds the optimization time of simple algorithms using uniform crossover on the search space {0, 1}n from below via two novel techniques called decoupling and family graphs. First, a simple steady-state crossover-based evolutionary algorithm without selection pressure is analyzed and shown that after O(µ log µ) generations, bit positions are sampled almost independently with marginal probabilities corresponding to the fraction of one-bits at the corresponding position in the initial population. Afterwards, a crossover-based algorithm using tournament selection is analyzed by a novel generalization of the family tree technique originally introduced for mutation-only EAs. Using these so-called family graphs, almost tight lower bounds on the optimization time on the OneMax benchmark function are shown.

Original languageEnglish
JournalAlgorithmica
Number of pages29
ISSN0178-4617
DOIs
Publication statusPublished - 2020
Event2019 Genetic and Evolutionary Computation Conference - Prague, Czech Republic
Duration: 13 Jul 201917 Jul 2019

Conference

Conference2019 Genetic and Evolutionary Computation Conference
CountryCzech Republic
CityPrague
Period13/07/201917/07/2019
SponsorAssociation for Computing Machinery

Bibliographical note

A preliminary version of this paper appeared in the Proceedings of the Genetic and Evolutionary Computation Conference (GECCO 2019)

Keywords

  • Crossover
  • Decoupling
  • Randomised search heuristics
  • Runtime analysis

Fingerprint Dive into the research topics of 'Lower bounds on the runtime of crossover-based algorithms via decoupling and family graphs'. Together they form a unique fingerprint.

Cite this