Automated Discovery of Local Search Heuristics for Satisfiability Testing

Created by W.Langdon from gp-bibliography.bib Revision:1.4192

  author =       "Alex S. Fukunaga",
  title =        "Automated Discovery of Local Search Heuristics for
                 Satisfiability Testing",
  journal =      "Evolutionary Computation",
  year =         "2008",
  volume =       "16",
  number =       "1",
  pages =        "31--61",
  month =        "Spring",
  keywords =     "genetic algorithms, genetic programming, STGP,
                 satisfiability, constraint satisfaction, SAT,
                 hyper-heuristic, hybrid genetic-local search",
  ISSN =         "1063-6560",
  URL =          "",
  DOI =          "doi:10.1162/evco.2008.16.1.31",
  size =         "31 pages",
  abstract =     "The development of successful metaheuristic algorithms
                 such as local search for a difficult problem such as
                 satisfiability testing (SAT) is a challenging task. We
                 investigate an evolutionary approach to automating the
                 discovery of new local search heuristics for SAT. We
                 show that several well-known SAT local search
                 algorithms such as Walksat and Novelty are composite
                 heuristics that are derived from novel combinations of
                 a set of building blocks. Based on this observation, we
                 developed CLASS, a genetic programming system that uses
                 a simple composition operator to automatically discover
                 SAT local search heuristics. New heuristics discovered
                 by CLASS are shown to be competitive with the best
                 Walksat variants, including Novelty+. Evolutionary
                 algorithms have previously been applied to directly
                 evolve a solution for a particular SAT instance. We
                 show that the heuristics discovered by CLASS are also
                 competitive with these previous, direct evolutionary
                 approaches for SAT. We also analyse the local search
                 behaviour of the learned heuristics using the depth,
                 mobility, and coverage metrics proposed by Schuurmans
                 and Southey.",

Genetic Programming entries for Alex S Fukunaga