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