Cross-domain Algorithm Selection: Algorithm Selection across Selection Hyper-heuristics

The present study introduces algorithm selection on selection hyper-heuristics. Hyper-heuristics are known as problem-independent methods utilized to solve different instances from varying problem domains. In the literature, there has been effective hyper-heuristic designs providing a certain level of generality in problem solving. Still, the relevant existing research indicates that there is no single hyper-heuristic which performs always the best on different problem solving scenarios. Algorithm selection has been investigated essentially to address this issue, mainly for the problem-specific algorithms, by automatically identifying the (near) best algorithm(s) for each given problem instance. This paper performs algorithm selection on selection hyper-heuristics, for the first time, delivering cross-domain algorithm selection. For this purpose, a suite of problem-independent features is initially introduced. Then, algorithm selection is examined across 9 single-objective combinatorial optimization problems with 6 online selection hyper-heuristics. The experimental results carried out on these problems indicated that algorithm selection is effective for choosing hyper-heuristics while offering improved generality and robustness.

I. Introduction

Hyper-heuristics (HHs)¹

a hyper-heuristic bibliography: http://mustafamisir.github.io/hh.html

[1], [2] are high-level search and optimization strategies operating in a problem-independent manner, with the goal of raising the level of generality [3]. Their problem-independent nature makes them different than the majority of the existing algorithms. The HH concept arose by the idea of combining the strengths of multiple heuristics for benefiting their capabilities. This class of HHs is called as Selection Hyper-heuristics (SHHs). As the focus of this work, a traditional SHH is composed of two sub-mechanisms: heuristic selection and move acceptance. Heuristic selection is concerned with determining the best heuristic(s) at a decision step. Move acceptance is responsible to assess the solutions derived by the selected heuristics.