Please use this identifier to cite or link to this item: http://hdl.handle.net/2440/109146
Citations
Scopus Web of Science® Altmetric
?
?
Full metadata record
DC FieldValueLanguage
dc.contributor.authorSutton, A.en
dc.contributor.authorNeumann, F.en
dc.date.issued2014en
dc.identifier.citationProceedings of the 13th International Conference on Parallel Problem Solving from Nature, 2014 / vol.8672, pp.942-951en
dc.identifier.isbn978-3-319-10762-2en
dc.identifier.issn0302-9743en
dc.identifier.issn1611-3349en
dc.identifier.urihttp://hdl.handle.net/2440/109146-
dc.description.abstractWe 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.en
dc.description.statementofresponsibilityAndrew M. Sutton, and Frank Neumannen
dc.language.isoenen
dc.publisherSpringer, Chamen
dc.relation.ispartofseriesLecture Notes in Computer Science (LNCS, vol. 8672)en
dc.rights© Springer International Publishing Switzerland 2014en
dc.source.urihttps://doi.org/10.1007/978-3-319-10762-2en
dc.titleRuntime analysis of evolutionary algorithms on randomly constructed high-density satisfiable 3-CNF formulasen
dc.typeConference paperen
dc.identifier.rmid0030024392en
dc.contributor.conference13th International Conference on Parallel Problem Solving from Nature (PPSN XIII) (13 Sep 2014 - 17 Sep 2014 : Ljubljana, Slovenia)en
dc.identifier.doi10.1007/978-3-319-10762-2_93en
dc.relation.granthttp://purl.org/au-research/grants/arc/DP140103400en
dc.identifier.pubid171886-
pubs.library.collectionComputer Science publicationsen
pubs.library.teamDS06en
pubs.verification-statusVerifieden
pubs.publication-statusPublisheden
dc.identifier.orcidNeumann, F. [0000-0002-2721-3618]en
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.