Please use this identifier to cite or link to this item:
https://hdl.handle.net/2440/109146
Citations | ||
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: | Lecture Notes in Artificial Intelligence, 2014 / BartzBeielstein, T., Branke, J., Filipic, B., Smith, J. (ed./s), 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 1611-3349 |
Conference Name: | 13th International Conference on Parallel Problem Solving from Nature (PPSN XIII) (13 Sep 2014 - 17 Sep 2014 : Ljubljana, Slovenia) |
Editor: | BartzBeielstein, T. Branke, J. Filipic, B. Smith, J. |
Statement of Responsibility: | 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 |
DOI: | 10.1007/978-3-319-10762-2_93 |
Grant ID: | http://purl.org/au-research/grants/arc/DP140103400 |
Published version: | http://dx.doi.org/10.1007/978-3-319-10762-2_93 |
Appears in Collections: | Aurora harvest 3 Computer Science publications |
Files in This Item:
File | Description | Size | Format | |
---|---|---|---|---|
RA_hdl_109146.pdf Restricted Access | Restricted Access | 199.21 kB | Adobe PDF | View/Open |
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.