Performance comparison of selection hyper-heuristics on new HyFlex domains - Almutairi, Alhanof Khalid S (2015)
Since most real-world computational problems are difficult to solve, significant attention has been drawn to design an automatic mechanism for selecting heuristics and increasing the generality of the search approach. Hyper-heuristics are high-level search mechanisms which aim to solve a range of difficult combinatorial optimisation problems by operating in the space of heuristics rather than space of solutions, which differs from the traditional approach. Hyper-heuristics are classified into two main categories: generation and selection methodologies. This study concentrates on the second methodology. The traditional approach of selection hyper-heuristic framework utilises a single solution. It iteratively selects and applies a heuristic from a set number of low-level heuristics to this solution until a decision is made either to accept or reject the new solution based on a move acceptance strategy. The process is iteratively repeated until a defined set of termination criteria is satisfied. This study mainly focuses on the use of a selection hyper-heuristic framework. More precisely, it examines the performance of different state-of-the-art hyper-heuristics, including a proposed method across a different set of problem domains provided on the HyFlex benchmark, which is a common framework designed to test and compare the performance of heuristic search algorithms over multiple domain problems. Only the three new problem domains that have recently been added to HyFlex are examined: the 0-1 Knap Sack, the Quadratic Assignment and the Max-Cut Problem. A series of experiments have been conducted to evaluate the performance of a range of existing hyper-heuristic methods and the newly proposed method. Based on the experiment results, Adap-HH, which was the winner of CHeSC2011, apparently performs the best across the three domains. In addition, the proposed SR-GD shows consistent performance over all the domains and is proven to be a simple yet powerful algorithm. It is also observed that the performances of different hyper-heuristics vary significantly not only across different domains but also across different instances within the same domain.