Runtime analysis of evolutionary algorithms on randomly constructed high-density satisfiable 3-CNF formulas

Andrew M. Sutton, Frank Neumann

Research output: Contribution to journalArticlepeer-review

11 Scopus citations

Abstract

We show that simple mutation-only evolutionary algorithms find a satisfying assignment on two similar models of random planted 3-CNF Boolean formulas in polynomial time with high probability in the high constraint density regime. We extend the analysis to random formulas conditioned on satisfiability (i.e., the so-called filtered distribution) and conclude that most high-density satisfiable formulas are easy for simple evolutionary algorithms. With this paper, we contribute the first rigorous study of randomized search heuristics from the evolutionary computation community on well-studied distributions of random satisfiability problems.

Bibliographical note

Funding Information:
Acknowledgments. 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:
© Springer International Publishing Switzerland 2014.

Fingerprint

Dive into the research topics of 'Runtime analysis of evolutionary algorithms on randomly constructed high-density satisfiable 3-CNF formulas'. Together they form a unique fingerprint.

Cite this