Analyzing the Generalizability of Automated Algorithm Selection: A Case Study for Numerical Optimization
Urban Škvorc, Tome Eftimov, Peter Koroec · 2023
In numerical single-objective optimization, auto-mated algorithm selection that uses exploratory landscape analy-sis to describe problem features has achieved great results when the machine learning models used for prediction are trained and tested on the same problem set. However, recent work has shown that the performance of such models decreases when the training and testing sets contain different problems. In this paper, we examine a recently developed algorithm selection model trained on a set of artificial problems and tested on a well-known set of hand-made benchmark problems. This model performed poorly when it was originally presented. Here, we provide an explanation for its poor performance by analyzing the feature importance of the model using Shapley Additive Explanations. We then compare these results to an alternative algorithm selection model that was both trained and tested on the same set of hand-made benchmark problems and achieved much higher performance. This allows us to determine which features each model considers as most significant for their predictions, and where they differ. We show that the original and the alternative model use different landscape features for their predictions, which explains the difference in their performance. Further, by plotting the SHAP values on a 2D plane, we show that the original model is unable to distinguish between certain types of problems. Finally, we show that regardless of their differences in utilizing the features both the original and the alternative models perform poorly on a specific group of problems.