 |
    |
An Improved Choice Function Heuristic Selection for Cross Domain Heuristic Search
John H. Drake1, Ender Özcan1, and Edmund K. Burke2
1School of Computer Science, University of Nottingham, Jubilee Campus, Wollaton Road, Nottingham, NG8 1BB, UK
jqd@cs.nott.ac.uk
exo@cs.nott.ac.uk
2Computing Science and Mathematics, School of Natural Sciences, University of Stirling, Stirling, FK9 4LA, Scotland
e.k.burke@stir.ac.uk
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
LNCS 7492, p. 307 ff.
lncs@springer.com
© Springer-Verlag Berlin Heidelberg 2012