Combined Selection and Parameter Control of Meta-heuristics

Publikation: Beitrag zu KonferenzenPaperBeigetragenBegutachtung

Beitragende

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

OriginalspracheEnglisch
Seiten3125-3132
Seitenumfang8
PublikationsstatusVeröffentlicht - 4 Dez. 2020
Peer-Review-StatusJa

Konferenz

Titel2020 IEEE Symposium Series on Computational Intelligence (SSCI)
Dauer1 - 4 Dezember 2020
OrtCanberra, ACT, Australia

Externe IDs

Scopus 85099679202
ORCID /0000-0003-1537-7815/work/168720053
ORCID /0000-0002-3513-6448/work/168720165

Schlagworte

Schlagwörter

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