Heuristic Space Diversity Measures for Population-based Hyper-heuristics
Stéfan A.G. van der Stockt, Andries Petrus Engelbrecht, Christopher W. Cleghorn · 2020
A hyper-heuristic is an optimization approach that continually selects the most appropriate heuristic(s) to apply to an optimization problem. Hyper-heuristics conduct a search in the space of heuristics, or heuristic space, for the most suitable heuristic to apply to candidate solutions in problem space. Traditionally, hyper-heuristics manage relatively simple low-level heuristics, which are often based on human domain intuition. Increasingly, hyper-heuristics are being used in conjunction with population-based meta-heuristics as the low-level heuristics. A heuristic space diversity measure helps practitioners understand the behavior of hyper-heuristics that manage population-based heuristics. This paper discusses existing measures to quantity heuristic space diversity, highlights shortcomings of these existing measures, and proposes a new heuristic space diversity entropy-based measure. Spatial and temporal volatility measures that characterize entity-to-heuristic assignments are also proposed.