 |
    |
Runtime Analysis of Evolutionary Algorithms on Randomly Constructed High-Density Satisfiable 3-CNF Formulas
Andrew M. Sutton1 and Frank Neumann2
1Friedrich-Schiller-Universität Jena, 07743, Jena, Germany
2Optimisation and Logistics, School of Computer Science, The University of Adelaide, Adelaide, SA, 5005, Australia
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.
LNCS 8672, p. 942 ff.
lncs@springer.com
© Springer International Publishing Switzerland 2014