 |
    |
Evolving Local Search Heuristics for SAT Using Genetic Programming
Alex S. Fukunaga
Computer Science Department, University of California, Los Angeles, CA 90024, USAfukunaga@cs.ucla.edu
Abstract. Satisfiability testing (SAT) is a very active area of research today, with numerous real-world applications. We describe CLASS2.0, a genetic programming system for semi-automatically designing SAT local search heuristics. An empirical comparison shows that that the heuristics generated by our GP system outperform the state of the art human-designed local search algorithms, as well as previously proposed evolutionary approaches, with respect to both runtime as well as search efficiency (number of variable flips to solve a problem).
LNCS 3103, p. 483 ff.
lncs@springer.de
© Springer-Verlag Berlin Heidelberg 2004