Instance-Specific Algorithm Selection via Multi-Output Learning

Instance-specific algorithm selection technologies have been successfully used in many research fields, such as constraint satisfaction and planning. Researchers have been increasingly trying to model the potential relations between different candidate algorithms for the algorithm selection. In this study, we propose an instance-specific algorithm selection method based on multi-output learning, which can manage these relations more directly. Three kinds of multi-output learning methods are used to predict the performances of the candidate algorithms: (1) multi-output regressor stacking; (2) multi-output extremely randomized trees; and (3) hybrid single-output and multi-output trees. The experimental results obtained using 11 SAT datasets and 5 MaxSAT datasets indicate that our proposed methods can obtain a better performance over the state-of-the-art algorithm selection methods.