Combined Selection and Parameter Control of Meta-heuristics

Research output: Contribution to conferencesPaperContributedpeer-review

Contributors

Abstract

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.

Details

Original languageEnglish
Pages3125-3132
Number of pages8
Publication statusPublished - 4 Dec 2020
Peer-reviewedYes

Conference

Title2020 IEEE Symposium Series on Computational Intelligence (SSCI)
Duration1 - 4 December 2020
LocationCanberra, ACT, Australia

External IDs

Scopus 85099679202

Keywords

Keywords

  • Optimization, Heuristic algorithms, Parameter Tuning, parameter control, Search problems, Runtime, surrogate models, hyper-heuristics, traveling salesman problem