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 language | English (US) |
---|---|
Title of host publication | GECCO 2019 - Proceedings of the 2019 Genetic and Evolutionary Computation Conference |
Publisher | Association for Computing Machinery, Inc |
Pages | 1515-1522 |
Number of pages | 8 |
ISBN (Electronic) | 9781450361118 |
DOIs | |
State | Published - Jul 13 2019 |
Event | 2019 Genetic and Evolutionary Computation Conference, GECCO 2019 - Prague, Czech Republic Duration: Jul 13 2019 → Jul 17 2019 |
Publication series
Name | GECCO 2019 - Proceedings of the 2019 Genetic and Evolutionary Computation Conference |
---|
Conference
Conference | 2019 Genetic and Evolutionary Computation Conference, GECCO 2019 |
---|---|
Country/Territory | Czech Republic |
City | Prague |
Period | 7/13/19 → 7/17/19 |
Bibliographical note
Publisher Copyright:© 2019 Copyright held by the owner/author(s). Publication rights licensed to the Association for Computing Machinery.
Keywords
- Crossover
- Decoupling
- Randomised search heuristics
- Runtime analysis