Dynamic heuristic set selection for cross-domain selection hyper-heuristics

Abstract

Selection hyper-heuristics have proven to be effective in solving various real-world problems. Hyper-heuristics differ from traditional heuristic approaches in that they explore a heuristic space rather than a solution space. These techniques select constructive or perturbative heuristics to construct a solution or improve an existing solution respectively. Previous work has shown that the set of problem-specific heuristics made available to the hyper-heuristic for selection has an impact on the performance of the hyper-heuristic. Hence, there have been initiatives to determine the appropriate set of heuristics that the hyper-heuristic can select from. However, there has not been much research done in this area. Furthermore, previous work has focused on determining a set of heuristics that is used throughout the lifespan of the hyper-heuristic with no change to this set during the application of the hyper-heuristic. This paper investigates dynamic heuristic set selection (DHSS) which applies dominance to select the set of heuristics at different points during the lifespan of a selection hyper-heuristic. The DHSS approach was evaluated on the benchmark set for the CHeSC cross-domain hyper-heuristic challenge. DHSS was found to improve the performance of the best performing hyper-heuristic for this challenge.