Parameter control and online algorithm selection are well-studied problems in heuristic-based optimization. The former adapts algorithm parameters at runtime, improving its quality; while the latter is often tackled with hyper-heuristics: problem-independent optimization algorithms, operating problem-dependent heuristics. Combining these two approaches is challenging: parameter control is algorithm-dependent, while the search space comprising multiple algorithms and their parameters is highly hierarchical and hard to model and traverse. In this paper we provide an approach to automatically select the best-performing algorithm and its configuration at runtime, combining the benefits of both parameter control and hyper-heuristics. Parameter control is realized with a surrogate-model-based approach, while the complex search space is treated by using individual surrogate models for each level in the hierarchy. We evaluate our approach with four instances of the symmetric traveling salesman problem. Our findings show that the presented approach is comparable with heuristics tuned offline and is highly recommended in cases when the best-performing heuristic is not known in advance.
|Veröffentlicht - 4 Dez. 2020
|2020 IEEE Symposium Series on Computational Intelligence (SSCI)
|1 - 4 Dezember 2020
|Canberra, ACT, Australia
- Optimization, Heuristic algorithms, Parameter Tuning, parameter control, Search problems, Runtime, surrogate models, hyper-heuristics, traveling salesman problem