Grammar-based generation of variable-selection heuristics for constraint satisfaction problems
Created by W.Langdon from
gp-bibliography.bib Revision:1.8098
- @Article{Sosa-Ascencio:2015:GPEM,
-
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
Citations