Time Complexity Analysis of Evolutionary Algorithms on Random Satisfiable k-CNF Formulas

Benjamin Doerr, Frank Neumann, Andrew M. Sutton

Research output: Contribution to journalArticlepeer-review

8 Scopus citations

Abstract

We contribute to the theoretical understanding of randomized search heuristics by investigating their optimization behavior on satisfiable random k-satisfiability instances both in the planted solution model and the uniform model conditional on satisfiability. Denoting the number of variables by n, our main technical result is that the simple (1 + 1) evolutionary algorithm with high probability finds a satisfying assignment in time O(nlog n) when the clause-variable density is at least logarithmic. For low density instances, evolutionary algorithms seem to be less effective, and all we can show is a subexponential upper bound on the runtime for densities below 1k(k-1). We complement these mathematical results with numerical experiments on a broader density spectrum. They indicate that, indeed, the (1 + 1) EA is less efficient on lower densities. Our experiments also suggest that the implicit constants hidden in our main runtime guarantee are low. Our main result extends and considerably improves the result obtained by Sutton and Neumann (Lect Notes Comput Sci 8672:942–951, 2014) in terms of runtime, minimum density, and clause length. These improvements are made possible by establishing a close fitness-distance correlation in certain parts of the search space. This approach might be of independent interest and could be useful for other average-case analyses of randomized search heuristics. While the notion of a fitness-distance correlation has been around for a long time, to the best of 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 languageEnglish (US)
Pages (from-to)561-586
Number of pages26
JournalAlgorithmica
Volume78
Issue number2
DOIs
StatePublished - Jun 1 2017

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

Keywords

  • Fitness-distance correlation
  • Runtime analysis
  • Satisfiability

Fingerprint Dive into the research topics of 'Time Complexity Analysis of Evolutionary Algorithms on Random Satisfiable k-CNF Formulas'. Together they form a unique fingerprint.

Cite this