Please use this identifier to cite or link to this item:
Scopus Web of Science® Altmetric
Type: Conference paper
Title: Runtime analysis of evolutionary algorithms on randomly constructed high-density satisfiable 3-CNF formulas
Author: Sutton, A.
Neumann, F.
Citation: Proceedings of the 13th International Conference on Parallel Problem Solving from Nature, 2014 / vol.8672, pp.942-951
Publisher: Springer, Cham
Issue Date: 2014
Series/Report no.: Lecture Notes in Computer Science (LNCS, vol. 8672)
ISBN: 978-3-319-10762-2
ISSN: 0302-9743
Conference Name: 13th International Conference on Parallel Problem Solving from Nature (PPSN XIII) (13 Sep 2014 - 17 Sep 2014 : Ljubljana, Slovenia)
Statement of
Andrew M. Sutton, and Frank Neumann
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.
Rights: © Springer International Publishing Switzerland 2014
RMID: 0030024392
DOI: 10.1007/978-3-319-10762-2_93
Grant ID:
Published version:
Appears in Collections:Computer Science publications

Files in This Item:
File Description SizeFormat 
RA_hdl_109146.pdfRestricted Access199.21 kBAdobe PDFView/Open

Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.