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

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

Original languageEnglish (US)
Pages (from-to)942-951
Number of pages10
JournalLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume8672
StatePublished - Jan 1 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