TY - GEN

T1 - Crossover can simulate bounded tree search on a fixed-parameter tractable optimization problem

AU - Sutton, Andrew M.

PY - 2018/7/2

Y1 - 2018/7/2

N2 - 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.

AB - 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.

KW - Crossover

KW - Evolutionary algorithms

KW - Fixed-parameter tractability

KW - Parameterized complexity

KW - Recombination

KW - Theory

UR - http://www.scopus.com/inward/record.url?scp=85050633760&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85050633760&partnerID=8YFLogxK

U2 - 10.1145/3205455.3205598

DO - 10.1145/3205455.3205598

M3 - Conference contribution

AN - SCOPUS:85050633760

T3 - GECCO 2018 - Proceedings of the 2018 Genetic and Evolutionary Computation Conference

SP - 1531

EP - 1538

BT - GECCO 2018 - Proceedings of the 2018 Genetic and Evolutionary Computation Conference

PB - Association for Computing Machinery, Inc

T2 - 2018 Genetic and Evolutionary Computation Conference, GECCO 2018

Y2 - 15 July 2018 through 19 July 2018

ER -