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

arXiv (Cornell University)

Abstract

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 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.

Authors 7

1. Ana Kostovska

   Jožef Stefan Institute · Jožef Stefan International Postgraduate School

   Affiliation as printed

   Jožef Stefan Institute , Ljubljana , Slovenia

   Jožef Stefan International Postgraduate School , Ljubljana , Slovenia

2. Anja Jankovič

   Centre National de la Recherche Scientifique · Sorbonne Université · Université Paris 1 Panthéon-Sorbonne

   Affiliation as printed

   LIP6 , Sorbonne Université , CNRS , Paris , France

3. Diederick Vermetten Aachen

   Leiden University

   Affiliation as printed

   LIACS , Leiden University , Leiden , The Netherlands

4. Jacob de Nobel Aachen

   Leiden University

   Affiliation as printed

   LIACS , Leiden University , Leiden , The Netherlands

5. Hao Wang Aachen

   Leiden University

   Affiliation as printed

   LIACS , Leiden University , Leiden , The Netherlands

6. Tome Eftimov

   Jožef Stefan Institute

   Affiliation as printed

   Jožef Stefan Institute , Ljubljana , Slovenia

7. Carola Doerr

   Centre National de la Recherche Scientifique · Sorbonne Université · Université Paris 1 Panthéon-Sorbonne

   Affiliation as printed

   LIP6 , Sorbonne Université , CNRS , Paris , France