Per-run Algorithm Selection with Warm-starting using Trajectory-based Features - Sorbonne Université
Communication Dans Un Congrès Année : 2022

Per-run Algorithm Selection with Warm-starting using Trajectory-based Features

Ana Kostovska
  • Fonction : Auteur
JSI
Anja Jankovic
  • Fonction : Auteur
  • PersonId : 1099542
Tome Eftimov
  • Fonction : Auteur
  • PersonId : 1099541
JSI
Carola Doerr

Résumé

Per-instance algorithm selection seeks to recommend, for a given problem instance and a given performance criterion, one or several suitable algorithms that are expected to perform well for the particular setting. The selection is classically done offline, using openly available information about the problem instance or features that are extracted from the instance during a dedicated feature extraction step. This ignores valuable information that the algorithms accumulate during the optimization process. In this work, we propose an alternative, online algorithm selection scheme which we coin as "per-run" algorithm selection. In our approach, we start the optimization with a default algorithm, and, after a certain number of iterations, extract instance features from the observed trajectory of this initial optimizer to determine whether to switch to another optimizer. We test this approach using the CMA-ES as the default solver, and a portfolio of six different optimizers as potential algorithms to switch to. In contrast to other recent work on online per-run algorithm selection, we warm-start the second optimizer using information accumulated during the first optimization phase. We show that our approach outperforms static per-instance algorithm selection. We also compare two different feature extraction principles, based on exploratory landscape analysis and time series analysis of the internal state variables of the CMA-ES, respectively. We show that a combination of both feature sets provides the most accurate recommendations for our test cases, taken from the BBOB function suite from the COCO platform and the YABBOB suite from the Nevergrad platform.
Fichier principal
Vignette du fichier
PerRun-AlgoSelect-PPSN2022.pdf (2.03 Mo) Télécharger le fichier
Origine Fichiers produits par l'(les) auteur(s)

Dates et versions

hal-03740760 , version 1 (29-07-2022)

Identifiants

Citer

Ana Kostovska, Anja Jankovic, Diederick Vermetten, Jacob de Nobel, Hao Wang, et al.. Per-run Algorithm Selection with Warm-starting using Trajectory-based Features. 17th Proceedings of Parallel Problem Solving from Nature - (PPSN) 2022, 2022, Dortmund, Germany. pp.46-60, ⟨10.1007/978-3-031-14714-2_4⟩. ⟨hal-03740760⟩
93 Consultations
37 Téléchargements

Altmetric

Partager

More