Grammar-based generation of variable-selection heuristics for constraint satisfaction problems

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

  author =       "Alejandro Sosa-Ascencio and Gabriela Ochoa and 
                 Hugo Terashima-Marin and Santiago Enrique Conant-Pablos",
  title =        "Grammar-based generation of variable-selection
                 heuristics for constraint satisfaction problems",
  journal =      "Genetic Programming and Evolvable Machines",
  year =         "2016",
  volume =       "17",
  number =       "2",
  pages =        "119--144",
  month =        jun,
  keywords =     "genetic algorithms, genetic programming, Constraint
                 satisfaction problems, Hyper-heuristics, Variable
                 ordering heuristics, Grammar-based framework",
  ISSN =         "1389-2576",
  DOI =          "doi:10.1007/s10710-015-9249-1",
  size =         "26 pages",
  abstract =     "We propose a grammar-based genetic programming
                 framework that generates variable-selection heuristics
                 for solving constraint satisfaction problems. This
                 approach can be considered as a generation
                 hyper-heuristic. A grammar to express heuristics is
                 extracted from successful human-designed
                 variable-selection heuristics. The search is performed
                 on the derivation sequences of this grammar using a
                 strongly typed genetic programming framework. The
                 approach brings two innovations to grammar-based
                 hyper-heuristics in this domain: the incorporation of
                 if-then-else rules to the function set, and the
                 implementation of overloaded functions capable of
                 handling different input dimensionality. Moreover, the
                 heuristic search space is explored using not only
                 evolutionary search, but also two alternative simpler
                 strategies, namely, iterated local search and parallel
                 hill climbing. We tested our approach on synthetic and
                 real-world instances. The newly generated heuristics
                 have an improved performance when compared against
                 human-designed heuristics. Our results suggest that the
                 constrained search space imposed by the proposed
                 grammar is the main factor in the generation of good
                 heuristics. However, to generate more general
                 heuristics, the composition of the training set and the
                 search methodology played an important role. We found
                 that increasing the variability of the training set
                 improved the generality of the evolved heuristics, and
                 the evolutionary search strategy produced slightly
                 better results.",

Genetic Programming entries for Alejandro Sosa-Ascencio Gabriela Ochoa Hugo Terashima-Marin Santiago Enrique Conant-Pablos