Improved runtime bounds for the (1+1) EA on random 3-CNF formulas based on fitness-distance correlation

Benjamin Doerr; Frank Neumann; Andrew M. Sutton

doi:10.1145/2739480.2754659

Improved runtime bounds for the (1+1) EA on random 3-CNF formulas based on fitness-distance correlation

Benjamin Doerr, Frank Neumann, Andrew M. Sutton

Computer Science (Duluth)

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

11 Scopus citations

Abstract

With this paper, we contribute to the theoretical understanding of randomized search heuristics by investigating their behavior on random 3-SAT instances. We improve the results for the (1+1) EA obtained by Sutton and Neumann. [PPSN 2014, 942-951] in three ways. First, we reduce the upper bound by a linear factor and prove that the (1+1) EA obtains optimal solutions in time O (nlog n) with high probability on asymptotically almost all high-density satisfiable 3-CNF formulas. Second, we extend the range of densities for which this bound holds to satisfiable formulas of at least logarithmic density. Finally, we complement these mathematical results with numerical experiments that summarize the behavior of the (1+1) EA on formulas along the density spectrum, and suggest that the implicit constants hidden in our bounds are low. Our proofs are based on analyzing the run of the algorithm by establishing a fitness-distance correlation. This approach might be of independent interest and we are optimistic that it is useful for the analysis of randomized search heuristics in various other settings. To our knowledge, this is the first time that fitness-distance correlation is explicitly used to rigorously prove a performance statement for an evolutionary algorithm.

Original language	English (US)
Title of host publication	GECCO 2015 - Proceedings of the 2015 Genetic and Evolutionary Computation Conference
Editors	Sara Silva
Publisher	Association for Computing Machinery, Inc
Pages	1415-1422
Number of pages	8
ISBN (Electronic)	9781450334723
DOIs	https://doi.org/10.1145/2739480.2754659
State	Published - Jul 11 2015
Event	16th Genetic and Evolutionary Computation Conference, GECCO 2015 - Madrid, Spain Duration: Jul 11 2015 → Jul 15 2015

Publication series

Name	GECCO 2015 - Proceedings of the 2015 Genetic and Evolutionary Computation Conference

Other

Other	16th Genetic and Evolutionary Computation Conference, GECCO 2015
Country/Territory	Spain
City	Madrid
Period	7/11/15 → 7/15/15

Bibliographical note

Funding Information:
The research leading to these results has received funding from the Australian Research Council (ARC) under grant agreement DP140103400 and from the European Union Seventh Framework Programme (FP7/2007-2013) under grant agreement no 618091 (SAGE).

Publisher Copyright:
© 2015 Copyright held by the owner/author (s).

Keywords

Fitness-distance correlation
Runtime analysis
Satisfiability

Publisher link

10.1145/2739480.2754659

Find It

Find It at U of M Libraries

Cite this

Doerr, B., Neumann, F., & Sutton, A. M. (2015). Improved runtime bounds for the (1+1) EA on random 3-CNF formulas based on fitness-distance correlation. In S. Silva (Ed.), GECCO 2015 - Proceedings of the 2015 Genetic and Evolutionary Computation Conference (pp. 1415-1422). (GECCO 2015 - Proceedings of the 2015 Genetic and Evolutionary Computation Conference). Association for Computing Machinery, Inc. https://doi.org/10.1145/2739480.2754659

Improved runtime bounds for the (1+1) EA on random 3-CNF formulas based on fitness-distance correlation. / Doerr, Benjamin; Neumann, Frank; Sutton, Andrew M.
GECCO 2015 - Proceedings of the 2015 Genetic and Evolutionary Computation Conference. ed. / Sara Silva. Association for Computing Machinery, Inc, 2015. p. 1415-1422 (GECCO 2015 - Proceedings of the 2015 Genetic and Evolutionary Computation Conference).

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

Doerr, B, Neumann, F & Sutton, AM 2015, Improved runtime bounds for the (1+1) EA on random 3-CNF formulas based on fitness-distance correlation. in S Silva (ed.), GECCO 2015 - Proceedings of the 2015 Genetic and Evolutionary Computation Conference. GECCO 2015 - Proceedings of the 2015 Genetic and Evolutionary Computation Conference, Association for Computing Machinery, Inc, pp. 1415-1422, 16th Genetic and Evolutionary Computation Conference, GECCO 2015, Madrid, Spain, 7/11/15. https://doi.org/10.1145/2739480.2754659

Doerr B, Neumann F, Sutton AM. Improved runtime bounds for the (1+1) EA on random 3-CNF formulas based on fitness-distance correlation. In Silva S, editor, GECCO 2015 - Proceedings of the 2015 Genetic and Evolutionary Computation Conference. Association for Computing Machinery, Inc. 2015. p. 1415-1422. (GECCO 2015 - Proceedings of the 2015 Genetic and Evolutionary Computation Conference). doi: 10.1145/2739480.2754659

Doerr, Benjamin ; Neumann, Frank ; Sutton, Andrew M. / Improved runtime bounds for the (1+1) EA on random 3-CNF formulas based on fitness-distance correlation. GECCO 2015 - Proceedings of the 2015 Genetic and Evolutionary Computation Conference. editor / Sara Silva. Association for Computing Machinery, Inc, 2015. pp. 1415-1422 (GECCO 2015 - Proceedings of the 2015 Genetic and Evolutionary Computation Conference).

@inproceedings{28836f9798f544999919ecf4542ab0b3,

title = "Improved runtime bounds for the (1+1) EA on random 3-CNF formulas based on fitness-distance correlation",

abstract = "With this paper, we contribute to the theoretical understanding of randomized search heuristics by investigating their behavior on random 3-SAT instances. We improve the results for the (1+1) EA obtained by Sutton and Neumann. [PPSN 2014, 942-951] in three ways. First, we reduce the upper bound by a linear factor and prove that the (1+1) EA obtains optimal solutions in time O (nlog n) with high probability on asymptotically almost all high-density satisfiable 3-CNF formulas. Second, we extend the range of densities for which this bound holds to satisfiable formulas of at least logarithmic density. Finally, we complement these mathematical results with numerical experiments that summarize the behavior of the (1+1) EA on formulas along the density spectrum, and suggest that the implicit constants hidden in our bounds are low. Our proofs are based on analyzing the run of the algorithm by establishing a fitness-distance correlation. This approach might be of independent interest and we are optimistic that it is useful for the analysis of randomized search heuristics in various other settings. To our knowledge, this is the first time that fitness-distance correlation is explicitly used to rigorously prove a performance statement for an evolutionary algorithm.",

keywords = "Fitness-distance correlation, Runtime analysis, Satisfiability",

author = "Benjamin Doerr and Frank Neumann and Sutton, {Andrew M.}",

note = "Funding Information: The research leading to these results has received funding from the Australian Research Council (ARC) under grant agreement DP140103400 and from the European Union Seventh Framework Programme (FP7/2007-2013) under grant agreement no 618091 (SAGE). Publisher Copyright: {\textcopyright} 2015 Copyright held by the owner/author (s).; 16th Genetic and Evolutionary Computation Conference, GECCO 2015 ; Conference date: 11-07-2015 Through 15-07-2015",

year = "2015",

month = jul,

day = "11",

doi = "10.1145/2739480.2754659",

language = "English (US)",

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

publisher = "Association for Computing Machinery, Inc",

pages = "1415--1422",

editor = "Sara Silva",

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

}

TY - GEN

T1 - Improved runtime bounds for the (1+1) EA on random 3-CNF formulas based on fitness-distance correlation

AU - Doerr, Benjamin

AU - Neumann, Frank

AU - Sutton, Andrew M.

N1 - Funding Information: The research leading to these results has received funding from the Australian Research Council (ARC) under grant agreement DP140103400 and from the European Union Seventh Framework Programme (FP7/2007-2013) under grant agreement no 618091 (SAGE). Publisher Copyright: © 2015 Copyright held by the owner/author (s).

PY - 2015/7/11

Y1 - 2015/7/11

N2 - With this paper, we contribute to the theoretical understanding of randomized search heuristics by investigating their behavior on random 3-SAT instances. We improve the results for the (1+1) EA obtained by Sutton and Neumann. [PPSN 2014, 942-951] in three ways. First, we reduce the upper bound by a linear factor and prove that the (1+1) EA obtains optimal solutions in time O (nlog n) with high probability on asymptotically almost all high-density satisfiable 3-CNF formulas. Second, we extend the range of densities for which this bound holds to satisfiable formulas of at least logarithmic density. Finally, we complement these mathematical results with numerical experiments that summarize the behavior of the (1+1) EA on formulas along the density spectrum, and suggest that the implicit constants hidden in our bounds are low. Our proofs are based on analyzing the run of the algorithm by establishing a fitness-distance correlation. This approach might be of independent interest and we are optimistic that it is useful for the analysis of randomized search heuristics in various other settings. To our knowledge, this is the first time that fitness-distance correlation is explicitly used to rigorously prove a performance statement for an evolutionary algorithm.

AB - With this paper, we contribute to the theoretical understanding of randomized search heuristics by investigating their behavior on random 3-SAT instances. We improve the results for the (1+1) EA obtained by Sutton and Neumann. [PPSN 2014, 942-951] in three ways. First, we reduce the upper bound by a linear factor and prove that the (1+1) EA obtains optimal solutions in time O (nlog n) with high probability on asymptotically almost all high-density satisfiable 3-CNF formulas. Second, we extend the range of densities for which this bound holds to satisfiable formulas of at least logarithmic density. Finally, we complement these mathematical results with numerical experiments that summarize the behavior of the (1+1) EA on formulas along the density spectrum, and suggest that the implicit constants hidden in our bounds are low. Our proofs are based on analyzing the run of the algorithm by establishing a fitness-distance correlation. This approach might be of independent interest and we are optimistic that it is useful for the analysis of randomized search heuristics in various other settings. To our knowledge, this is the first time that fitness-distance correlation is explicitly used to rigorously prove a performance statement for an evolutionary algorithm.

KW - Fitness-distance correlation

KW - Runtime analysis

KW - Satisfiability

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

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

U2 - 10.1145/2739480.2754659

DO - 10.1145/2739480.2754659

M3 - Conference contribution

AN - SCOPUS:84963668426

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

SP - 1415

EP - 1422

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

A2 - Silva, Sara

PB - Association for Computing Machinery, Inc

T2 - 16th Genetic and Evolutionary Computation Conference, GECCO 2015

Y2 - 11 July 2015 through 15 July 2015

ER -

Improved runtime bounds for the (1+1) EA on random 3-CNF formulas based on fitness-distance correlation

Abstract

Publication series

Other

Bibliographical note

Keywords

Publisher link

Find It

Other files and links

Fingerprint

Cite this