Abstract
We investigate the effect of crossover in the context of parameterized complexity on a well-known fixed-parameter tractable combinatorial optimization problem known as the closest string problem. We prove that a multi-start (+1) GA solves arbitrary length-n instances of closest string in 2O(d 2+d log k) · poly(n) steps in expectation. Here, k is the number of strings in the input set, and d is the value of the optimal solution. This confirms that the multi-start (+1) GA runs in randomized fixed-parameter tractable (FPT) time with respect to the above parameterization. On the other hand, if the crossover operation is disabled, we show there exist instances that require nΩ(log(d+k)) steps in expectation. The lower bound asserts that crossover is a necessary component in the FPT running time.
Original language | English (US) |
---|---|
Title of host publication | GECCO 2018 - Proceedings of the 2018 Genetic and Evolutionary Computation Conference |
Publisher | Association for Computing Machinery, Inc |
Pages | 1531-1538 |
Number of pages | 8 |
ISBN (Electronic) | 9781450356183 |
DOIs | |
State | Published - Jul 2 2018 |
Event | 2018 Genetic and Evolutionary Computation Conference, GECCO 2018 - Kyoto, Japan Duration: Jul 15 2018 → Jul 19 2018 |
Publication series
Name | GECCO 2018 - Proceedings of the 2018 Genetic and Evolutionary Computation Conference |
---|
Other
Other | 2018 Genetic and Evolutionary Computation Conference, GECCO 2018 |
---|---|
Country/Territory | Japan |
City | Kyoto |
Period | 7/15/18 → 7/19/18 |
Bibliographical note
Publisher Copyright:© 2018 Copyright held by the owner/author(s).
Keywords
- Crossover
- Evolutionary algorithms
- Fixed-parameter tractability
- Parameterized complexity
- Recombination
- Theory