Using learning classifier systems to design selective hyper-heuristics for constraint satisfaction problems

Constraint satisfaction problems (CSP) are defined by a set of variables, where each variable contains a series of values it can be instantiated with. There is a set of constraints among the variables that restrict the different values they can take simultaneously. The task is to find one assignment to all the variables without breaking any constraint. To solve a CSP instance, a search tree is created where each node represents a variable of the instance. The order in which the variables are selected for instantiation changes the form of the search tree and affects the cost of finding a solution. Many heuristics have been proposed to help to decide the next variable to instantiate during the search and they have proved to be helpful for some instances. In this paper we explore the use of learning classifier systems to construct selective hyper-heuristics that dynamically select, from a set of variable ordering heuristics for CSPs, the one that best matches the current problem state in order to perform well on a wide range of instances. During a training phase, the system constructs state-heuristic rules as it explores the search space. Heuristics with good performance at certain points are rewarded and become more likely to be applied in similar situations. The approach is tested on random instances, providing promising results with respect to the median performance of the variable ordering heuristics used in isolation.