Automatic generation of heuristics for constraint satisfaction problems Chapter in Scopus uri icon

Abstract

  • The constraint satisfaction problem (CSP) is a generic problem with many applications in different areas of artificial intelligence and operational research. When solving a CSP, the order in which the variables are selected to be instantiated has a tremendous impact in the cost of finding a solution. In this paper we explore a novel type of heuristic that combines different features that describe the current state of the instance to decide which variable to instantiate next. A generational genetic algorithm is used to automatically tune the parameters used by these new heuristics. This paper contributes to the development of new heuristics that can be either very specialized to one class of instances, or general enough to deal with different classes of instances with an acceptable performance. © 2014 Springer International Publishing Switzerland.

Publication date

  • January 1, 2014