Improving the performance of vector hyper-heuristics through local search

Hyper-heuristics enable us to selectively apply the most suitable low-level heuristic depending on the properties of the problem at hand. They can be used for solving Constraint Satisfaction Problems (CSP) in different ways considering the variety of hyper-heuristics and low-level heuristics. A particular approach which has been receiving attention in the recent years is based on variable ordering using hyper-heuristics. A hyper-heuristic decides the next variable to process using a set of predefined heuristics considering the features that describe the instance at a given point during the search in this framework. This study explores an approach in which each hyper-heuristic is represented as a set of vectors mapping instance features to heuristics for variable ordering. The results suggest that the proposed approach is able to combine the strengths of different heuristics and compensate for their weaknesses performing better than each heuristic in isolation across a range of instances.