Exploring the landscape of the space of heuristics for local search in SAT

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

  author =       "Andrew W. Burnett and Andrew J. Parkes",
  booktitle =    "2017 IEEE Congress on Evolutionary Computation (CEC)",
  title =        "Exploring the landscape of the space of heuristics for
                 local search in SAT",
  year =         "2017",
  editor =       "Jose A. Lozano",
  pages =        "2518--2525",
  address =      "Donostia, San Sebastian, Spain",
  publisher =    "IEEE",
  isbn13 =       "978-1-5090-4601-0",
  abstract =     "Local search is a powerful technique on many
                 combinatorial optimisation problems. However, the
                 effectiveness of local search methods will often depend
                 strongly on the details of the heuristics used within
                 them. There are many potential heuristics, and so
                 finding good ones is in itself a challenging search
                 problem. A natural method to search for effective
                 heuristics is to represent the heuristic as a small
                 program and then apply evolutionary methods, such as
                 genetic programming. However, the search within the
                 space of heuristics is not well understood, and in
                 particular little is known of the associated search
                 landscapes. In this paper, we consider the domain of
                 propositional satisfiability (SAT), and a generic class
                 of local search methods called `WalkSAT'. We give a
                 language for generating the heuristics; using this we
                 generated over three million heuristics, in a
                 systematic manner, and evaluated their associated
                 fitness values. We then use this data set as the basis
                 for an initial analysis of the landscape of the space
                 of heuristics. We give evidence that the heuristic
                 landscape exhibits clustering. We also consider local
                 search on the space of heuristics and show that it can
                 perform quite well, and could complement genetic
                 programming methods on that space.",
  keywords =     "genetic algorithms, genetic programming,
                 computability, search problems, WalkSAT, clustering,
                 combinatorial optimisation problems, evolutionary
                 methods, local search, propositional satisfiability,
                 search space landscapes, Computer science, Measurement,
                 Reactive power, Systematics",
  isbn13 =       "978-1-5090-4601-0",
  DOI =          "doi:10.1109/CEC.2017.7969611",
  month =        "5-8 " # jun,
  notes =        "IEEE Catalog Number: CFP17ICE-ART Also known as

Genetic Programming entries for Andrew W Burnett Andrew J Parkes