Quarterly (spring, summer, fall, winter)
176 pp. per issue
7 x 10
2014 Impact factor:

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)

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.