On the Time Complexity of Algorithm Selection Hyper-Heuristics for Multimodal Optimisation


  • Andrei Lissovoi The University of Sheffield
  • Pietro S. Oliveto University of Sheffield
  • John Alasdair Warwicker The University of Sheffield




Selection hyper-heuristics are automated algorithm selection methodologies that choose between different heuristics during the optimisation process. Recently selection hyperheuristics choosing between a collection of elitist randomised local search heuristics with different neighbourhood sizes have been shown to optimise a standard unimodal benchmark function from evolutionary computation in the optimal expected runtime achievable with the available low-level heuristics. In this paper we extend our understanding to the domain of multimodal optimisation by considering a hyper-heuristic from the literature that can switch between elitist and nonelitist heuristics during the run. We first identify the range of parameters that allow the hyper-heuristic to hillclimb efficiently and prove that it can optimise a standard hillclimbing benchmark function in the best expected asymptotic time achievable by unbiased mutation-based randomised search heuristics. Afterwards, we use standard multimodal benchmark functions to highlight function characteristics where the hyper-heuristic is efficient by swiftly escaping local optima and ones where it is not. For a function class called CLIFFd where a new gradient of increasing fitness can be identified after escaping local optima, the hyper-heuristic is extremely efficient while a wide range of established elitist and non-elitist algorithms are not, including the well-studied Metropolis algorithm. We complete the picture with an analysis of another standard benchmark function called JUMPd as an example to highlight problem characteristics where the hyper-heuristic is inefficient. Yet, it still outperforms the wellestablished non-elitist Metropolis algorithm.




How to Cite

Lissovoi, A., Oliveto, P. S., & Warwicker, J. A. (2019). On the Time Complexity of Algorithm Selection Hyper-Heuristics for Multimodal Optimisation. Proceedings of the AAAI Conference on Artificial Intelligence, 33(01), 2322-2329. https://doi.org/10.1609/aaai.v33i01.33012322



AAAI Technical Track: Heuristic Search and Optimization