Quarterly (spring, summer, fall, winter)
176 pp. per issue
7 x 10
ISSN
1063-6560
E-ISSN
1530-9304
2014 Impact factor:
2.37

Evolutionary Computation

Spring 2002, Vol. 10, No. 1, Pages 35-50
(doi: 10.1162/106365602317301763)
© 2002 Massachusetts Institute of Technology
Evolutionary Algorithms for the Satisfiability Problem
Article PDF (200.45 KB)
Abstract

Several evolutionary algorithms have been proposed for the satisfiability problem. We review the solution representations suggested in literature and choose the most promising one—the bit string representation—for further evaluation. An empirical comparison on commonly used benchmarks is presented for the most successful evolutionary algorithms and for WSAT, a prominent local search algorithm for the satisfi-ability problem. The key features of successful evolutionary algorithms are identified, thereby providing useful methodological guidelines for designing new heuristics. Our results indicate that evolutionary algorithms are competitive to WSAT.