An improved choice function heuristic selection for cross domain heuristic search

Citation

Drake J, Ozcan E & Burke E (2012) An improved choice function heuristic selection for cross domain heuristic search. In: Coello CC, Cutello V, Deb K K, Forrest S, Nicosia G & Pavone M (eds.) Parallel Problem Solving from Nature - PPSN XII. Lecture Notes in Computer Science, 7492. 12th International Conference on Parallel Problem Solving from Nature - PPSN XII, Taormina, Italy, 01.09.2012-05.09.2012. Berlin Heidelberg: Springer, pp. 307-316. http://link.springer.com/chapter/10.1007%2F978-3-642-32964-7_31; https://doi.org/10.1007/978-3-642-32964-7_31

Abstract
Hyper-heuristics are a class of high-level search technologies to solve computationally difficult problems which operate on a search space of low-level heuristics rather than solutions directly. A iterative selection hyper-heuristic framework based on single-point search relies on two key components, a heuristic selection method and a move acceptance criteria. The Choice Function is an elegant heuristic selection method which scores heuristics based on a combination of three different measures and applies the heuristic with the highest rank at each given step. Each measure is weighted appropriately to provide balance between intensification and diversification during the heuristic search process. Choosing the right parameter values to weight these measures is not a trivial process and a small number of methods have been proposed in the literature. In this study we describe a new method, inspired by reinforcement learning, which controls these parameters automatically. The proposed method is tested and compared to previous approaches over a standard benchmark across six problem domains.

Keywords
Hyper-heuristics; Choice Function; Heuristic Selection; Cross-domain Optimisation; Combinatorial Optimization