PS-AAS: Portfolio Selection for Automated Algorithm Selection in
  Black-Box Optimization
Ana Kostovska Gjorgjina Cenikj Diederick Vermetten Anja Jankovic Ana Nikolikj Urban Skvorc Peter Korosec Carola Doerr Tome Eftimov
The performance of automated algorithm selection (AAS) strongly depends on
the portfolio of algorithms to choose from. Selecting the portfolio is a
non-trivial task that requires balancing the trade-off between the higher
flexibility of large portfolios with the increased complexity of the AAS task.
In practice, probably the most common way to choose the algorithms for the
portfolio is a greedy selection of the algorithms that perform well in some
reference tasks of interest.
  We set out in this work to investigate alternative, data-driven portfolio
selection techniques. Our proposed method creates algorithm behavior
meta-representations, constructs a graph from a set of algorithms based on
their meta-representation similarity, and applies a graph algorithm to select a
final portfolio of diverse, representative, and non-redundant algorithms. We
evaluate two distinct meta-representation techniques (SHAP and performance2vec)
for selecting complementary portfolios from a total of 324 different variants
of CMA-ES for the task of optimizing the BBOB single-objective problems in
dimensionalities 5 and 30 with different cut-off budgets. We test two types of
portfolios: one related to overall algorithm behavior and the `personalized'
one (related to algorithm behavior per each problem separately). We observe
that the approach built on the performance2vec-based representations favors
small portfolios with negligible error in the AAS task relative to the virtual
best solver from the selected portfolio, whereas the portfolios built from the
SHAP-based representations gain from higher flexibility at the cost of
decreased performance of the AAS. Across most considered scenarios,
personalized portfolios yield comparable or slightly better performance than
the classical greedy approach. They outperform the full portfolio in all
scenarios.