On Constructing Algorithm Portfolios inAlgorithm Selection for Computationally Expensive
Black-box Optimization in the Fixed-budget Setting
IAM Workshop 2024 at Melbourne

Takushi Yoshikawa and Ryoji Tanabe
Yokohama National University
Yokohama city, Japan

Algorithm selection for BBO

Issue1

Issue2

Setup

Results

Conclusion

Black-box continuous optimization

2 / 17

Algorithm selection for BBO

Issue1

Issue2

Setup

Results

Conclusion

Algorithm selection problem for BBO
Best optimizer depends on the property of a problem• A user needs to select the most promising optimizer• Hand-selecting requires tedious trial-and-error
3 / 17

Algorithm selection for BBO

Issue1

Issue2

Setup

Results

Conclusion

Feature-based offline algorithm selection for BBO
Training phase (on a training problem set)
1. Generate a solution set X and calculate f (X )2. Compute features based on the pair of X and f (X )3. Train k ML models for k optimizers in a portfolio A• A: a set of k candidate optimizers (k = 4 in this work)

Testing phase (on a target problem)
1. Generate a solution set X and calculate f (X )2. Compute features based on the pair of X and f (X )3. Predict the performance of k optimizers by the k ML
models, then select the best one
4 / 17

Algorithm selection for BBO

Issue1

Issue2

Setup

Results

Conclusion

1. Generate a solution set X and calculate f (X )5 / 17

Algorithm selection for BBO

Issue1

Issue2

Setup

Results

Conclusion

2. Compute features based on X and f (X )• Exploratory Landscape Analysis (ELA) [Mersmann 11]• Input: the pair of X and f (X )• Output: a set of numerical features of a problem

Olaf Mersmann, Bernd Bischl, Heike Trautmann, Mike Preuss, Claus Weihs, Günter Rudolph: Exploratory landscape analysis.
GECCO 2011: 829-836

6 / 17

Algorithm selection for BBO

Issue1

Issue2

Setup

Results

Conclusion

3. Predict the performance of k optimizers by the k
ML models, then select the best one
E.g., a portfolio A = { BFGS, DE, CMA-ES, PSO }• The system selects a promising optimizer without:• any user interaction• actually running the k optimizers on a real-world problem
7 / 17

Algorithm selection for BBO

Issue1

Issue2

Setup

Results

Conclusion

Contribution: Suggestion for constructing portfolios• We focus on computationally expensive optimization• Some real-world problems require a long computation timeto evaluate a solution x by expensive computer simulations• The max. number of fevals. (MaxFE) should be small• Algorithm selection for compu. expensive opt.
• has not been studied well
• A few previous studies did it, but the setup was incorrect• We point out two issues in existing approaches

8 / 17

Algorithm selection for BBO

Issue1

Issue2

Setup

ResultsConclusion

Issue1: Most studies did not correctly count fevals• XFE : fevals used for generating the solution set X• A selection system requires XFE to calculate f (X )• OFE : fevals used for a selected optimizer• E.g., the max. fevals of CMA-ES is OFE• MaxFE : the max. fevals for the whole system• Correct: MaxFE = XFE + OFE• However, most previous studies ignored XFE• Incorrect: MaxFE = XFE + OFE• This leads to an overestimation of the performance• Correct: the selected optimizer can use only OFE•

XFE should be small because a large XFE leads a small OFE• Incorrect: the selected optimizer can use MaxFE•XFE can be large as possible ( XFE >> MaxFE in some work)
9 / 17

Algorithm selection for BBO

Issue1

Issue2

Setup

Results

Conclusion

Our approach for the issue1

MaxFE = XFE + OFE

10 / 17

Algorithm selection for BBO

Issue1

Issue2

Setup

Results

Conclusion

Issue2: Previous studies considered MaxFE insteadof OFE when constructing algorithm portfolios• OFE : fevals used for a selected optimizer• MaxFE : max. fevals for the whole system• How to construct a portfolio in previous studies• Run many optimizers on training problems until MaxFE• Select k optimizers based on their performance at MaxFE• But, an optimizer can use only OFE , not MaxFE• Suppose: MaxFE= 1 000 and OFE= 500• The portfolio consists of good optimizers at 1 000 fevals• But, they are unlikely to perform well at 500 fevals• This gap can make the effectiveness of portfolio poor
11 / 17

Algorithm selection for BBO

Issue1

Issue2

SetupResults

Conclusion

Our approach for the issue2

Construct algorithm portfolios based on
the performance of optimizers at OFE ,not at MaxFE

12 / 17

Algorithm selection for BBO

Issue1

Issue2

Setup

Results

Conclusion

Experimental setup• The COCO platform [Hansen 21]• The 24 bbob functions with n ∈ {2, 3, 5, 10}• Portfolios were constructed based on the benchmarking
data of 244 optimizers in the COCO archive• Local search method for subset selection was used

• Settings for algorithm selection systems• flacco [Kerschke 19] was used for feature computation• MaxFE was set to 100 × n (n: dimension)• The first study to set MaxFE below 100 × n actually• Random forest regressor was used
Nikolaus Hansen, Anne Auger, Raymond Ros, Olaf Mersmann, Tea Tušar, Dimo Brockhoff: COCO: a platform for comparing
continuous optimizers in a black-box setting. Optim. Methods Softw. 36(1): 114-144 (2021)
Pascal Kerschke and Heike Trautmann. 2019. Comprehensive Feature-Based Landscape Analysis of Continuous and Constrained
Optimization Problems Using the R-package flacco. In Applications in Statistical Computing – From Music Data Analysis to Industrial
Quality Improvement. Springer, 93-123.

13 / 17Algorithm selection for BBO

Issue1

Issue2

Setup

ResultsConclusion

6 portfolios constructed in this work (k = 4)
• OFE : fevals used for a selected optimizer• XFE : fevals used for generating the solution set X• MaxFE : max. fevals for the whole system• MaxFE = XFE + OFE = 100n (n: dimension)• Amax : based on the perf. at MaxFE = 100n
• Traditional, incorrect construction approach• A90 : based on the perf. at OFE= 90n• XFE = 100n − 90n = 10n• A85 : based on the perf. at OFE= 85n• XFE = 100n − 85n = 15n• A80 , A75 , A50 were constructed in the same way
14 / 17

Algorithm selection for BBO

Issue1

Issue2

Setup

ResultsConclusion

6 portfolios constructed in this work (k = 4)
Surrogate-CMA-ES STEP-based mathematical DIRECT-based
Amax

lq-CMA-ES , BIPOP-aCMA-STEP , MLSL , oMads-2N

A90

DTS-CMA-ES 005 , BrentSTEPif , DIRECT-REV , CMA-ES-2019

A85

lq-CMA-ES , lmm-CMA-ES , STEPifeg , fmincon

A80

lq-CMA-ES , lmm-CMA-ES , STEPifeg , fmincon

A75

lq-CMA-ES , lmm-CMA-ES , BrentSTEPif , DIRECT-REV

A50

lq-CMA-ES , lmm-CMA-ES , BrentSTEPrr , oMads-2N• Left surrogate-CMA-ES is the single-best solver (SBS)• The best optimizer in terms of the average performance• Only in A90 , the SBS is DTS-CMA-ES 005
15 / 17

Algorithm selection for BBO

Issue1

Issue2

Setup

Results

Conclusion

Average rankings of 10 algorithm selection systems• The system with A90 performs the best

• Importance of using the performance at OFE (not MaxFE )• A large OFE allows a long run of an optimizer

Portfolio

OFE

XFE

MaxFE

n = 2 n = 3 n = 5 n = 10Amax
Amax
Amax
Amax
Amax

90n
85n
80n
75n
50n

10n
15n
20n
25n
50n

100n
100n
100n
100n
100n

5.50
5.54
6.21
5.50
5.00

5.65
5.48
5.10
4.85
5.85

5.73
6.02
5.35
4.60
6.00

5.58
6.06
6.15
5.94
5.98

A90
A85
A80
A75
A50

90n
85n
80n
75n
50n

10n
15n
20n
25n
50n

100n
100n
100n
100n
100n

4.44
4.38
5.29
5.21
7.94

4.15
4.52
5.65
5.81
7.94

4.12
5.37
5.79
4.73
7.27

3.04
4.04
4.67
5.298.25
16 / 17

Algorithm selection for BBO

Issue1

Issue2

Setup

Results

Conclusion

Conclusion: This work focused on portfolios inalgorithm selection for comput. expensive BBO• XFE : fevals used for generating the solution set X• OFE : fevals used for a selected optimizer• MaxFE : the max. fevals for the whole system• Two take home messages:• MaxFE should be XFE + OFE• Portfolios should be constructed based on theperformance of optimizers for OFE , not MaxFE• Future work: Improving selection systems• The performance of the present system is not good
17 / 17