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

Andrew M. Sutton, Carsten Witt

Research output: Chapter in Book/Report/Conference proceedingArticle in proceedingsResearchpeer-review

64 Downloads (Pure)

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
Title of host publicationProceedings of the 2019 Genetic and Evolutionary Computation Conference
PublisherAssociation for Computing Machinery
Publication date13 Jul 2019
Pages1515-1522
ISBN (Electronic)9781450361118
DOIs
Publication statusPublished - 13 Jul 2019
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
SeriesGECCO 2019 - Proceedings of the 2019 Genetic and Evolutionary Computation Conference

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