A Study of Agnostic Hyper-heuristics based on Sampling Solution Chains

Abstract

In this paper, we study a simple hyper-heuristic that functions by sampling solution chains. A solution chain in this algorithm is formed by successively applying a randomly chosen heuristic to the previous solution to generate the next solution. Operating in this way, the algorithm can benefit from the accumulated effect of applying multiple heuristics. A key factor in this algorithm is the strategy for choosing the sampling length. We discuss a balanced strategy in a setting that contains two agnostic assumptions: First, we do not have detailed knowledge about the problem domain being solved except that we have access to the objective function and a set of predefined heuristics. Secondly, we have no information about the amount of time allocated for running our algorithm. We present a theoretical guarantee on using this strategy to choose the sampling lengths and derive some variants based on this strategy. Empirical results also confirm that these strategies deliver desired behavior. Finally, we briefly discuss the extension of incorporating a learning mechanism into the algorithm.