Conference paper · Journal article
Lower bounds on the runtime of crossover-based algorithms via decoupling and family graphs
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.
Language: | English |
---|---|
Publisher: | Springer US |
Year: | 2020 |
Pages: | 3180-3208 |
Proceedings: | 2019 Genetic and Evolutionary Computation Conference |
ISSN: | 14320541 and 01784617 |
Types: | Conference paper and Journal article |
DOI: | 10.1007/s00453-020-00776-6 |
ORCIDs: | Witt, Carsten and 0000-0003-1295-6715 |