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

Andrew M. Sutton

doi:10.1145/3205455.3205598

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

Andrew M. Sutton

Computer Science (Duluth)

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

7 Scopus citations

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 2^O(^d ²⁺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	https://doi.org/10.1145/3205455.3205598
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

Keywords

Crossover
Evolutionary algorithms
Fixed-parameter tractability
Parameterized complexity
Recombination
Theory

Access

10.1145/3205455.3205598

Cite this

Sutton, A. M. (2018). Crossover can simulate bounded tree search on a fixed-parameter tractable optimization problem. In GECCO 2018 - Proceedings of the 2018 Genetic and Evolutionary Computation Conference (pp. 1531-1538). (GECCO 2018 - Proceedings of the 2018 Genetic and Evolutionary Computation Conference). Association for Computing Machinery, Inc. https://doi.org/10.1145/3205455.3205598

Crossover can simulate bounded tree search on a fixed-parameter tractable optimization problem. / Sutton, Andrew M.

GECCO 2018 - Proceedings of the 2018 Genetic and Evolutionary Computation Conference. Association for Computing Machinery, Inc, 2018. p. 1531-1538 (GECCO 2018 - Proceedings of the 2018 Genetic and Evolutionary Computation Conference).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Sutton, AM 2018, Crossover can simulate bounded tree search on a fixed-parameter tractable optimization problem. in GECCO 2018 - Proceedings of the 2018 Genetic and Evolutionary Computation Conference. GECCO 2018 - Proceedings of the 2018 Genetic and Evolutionary Computation Conference, Association for Computing Machinery, Inc, pp. 1531-1538, 2018 Genetic and Evolutionary Computation Conference, GECCO 2018, Kyoto, Japan, 7/15/18. https://doi.org/10.1145/3205455.3205598

Sutton AM. Crossover can simulate bounded tree search on a fixed-parameter tractable optimization problem. In GECCO 2018 - Proceedings of the 2018 Genetic and Evolutionary Computation Conference. Association for Computing Machinery, Inc. 2018. p. 1531-1538. (GECCO 2018 - Proceedings of the 2018 Genetic and Evolutionary Computation Conference). https://doi.org/10.1145/3205455.3205598

@inproceedings{422305ad52b74c3696c2cb775a2055e3,

title = "Crossover can simulate bounded tree search on a fixed-parameter tractable optimization problem",

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.",

keywords = "Crossover, Evolutionary algorithms, Fixed-parameter tractability, Parameterized complexity, Recombination, Theory",

author = "Sutton, {Andrew M.}",

year = "2018",

month = jul,

day = "2",

doi = "10.1145/3205455.3205598",

language = "English (US)",

series = "GECCO 2018 - Proceedings of the 2018 Genetic and Evolutionary Computation Conference",

publisher = "Association for Computing Machinery, Inc",

pages = "1531--1538",

booktitle = "GECCO 2018 - Proceedings of the 2018 Genetic and Evolutionary Computation Conference",

note = "2018 Genetic and Evolutionary Computation Conference, GECCO 2018 ; Conference date: 15-07-2018 Through 19-07-2018",

}

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 -

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

Abstract

Publication series

Other

Keywords

Access

Other files and links

Fingerprint

Cite this