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 proceedingConference contribution

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 (US)
Title of host publicationGECCO 2019 - Proceedings of the 2019 Genetic and Evolutionary Computation Conference
PublisherAssociation for Computing Machinery, Inc
Pages1515-1522
Number of pages8
ISBN (Electronic)9781450361118
DOIs
StatePublished - Jul 13 2019
Event2019 Genetic and Evolutionary Computation Conference, GECCO 2019 - Prague, Czech Republic
Duration: Jul 13 2019Jul 17 2019

Publication series

NameGECCO 2019 - Proceedings of the 2019 Genetic and Evolutionary Computation Conference

Conference

Conference2019 Genetic and Evolutionary Computation Conference, GECCO 2019
CountryCzech Republic
CityPrague
Period7/13/197/17/19

    Fingerprint

Keywords

  • Crossover
  • Decoupling
  • Randomised search heuristics
  • Runtime analysis

Cite this

Sutton, A. M., & Witt, C. (2019). Lower bounds on the runtime of crossover-based algorithms via decoupling and family graphs. In GECCO 2019 - Proceedings of the 2019 Genetic and Evolutionary Computation Conference (pp. 1515-1522). (GECCO 2019 - Proceedings of the 2019 Genetic and Evolutionary Computation Conference). Association for Computing Machinery, Inc. https://doi.org/10.1145/3321707.3321848