Evolutionary algorithms for the satisfiability problem.
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 satisfiability 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.
Gottlieb
Jens
J
SAP AG, Neurottstrasse 16, 69190 Walldorf, Germany. jens.gottlieb@sap.com
Marchiori
Elena
E
Rossi
Claudio
C
D000465:Algorithms; D005075:Biological Evolution; D008957:Models, Genetic; D008962:Models, Theoretical