Per-instance algorithm configuration: from meta-learning to multi-objective decomposition

Abstract

The search for the best algorithm and its configuration is a difficult task on most optimization scenarios, especially on NP-hard problems, since different proposed metaheuristics exist, and testing many parameters demands high computational costs. Moreover, the understanding of such parameters and their relation to problem instances is of great importance in the field of algorithm configuration. The literature on Automatic Algorithm Configuration (AAC) proposes several strategies to find out the best configuration, although the focus is usually less on explainability and more on the performance of the different configurations. Based on past experience obtained from data, Per-Instance Algorithm Configuration (PIAC) focuses on the mapping built to recommend the best configurations. This work aims at proposing and analyzing two PIAC approaches. The first, namely MetaL PIAC, is an extension of the algorithm selection problem and uses meta-learning to recommend metaheuristics and their configuration parameters. The other, namely MOAAC/D is based on a brand new multi-objective formulation of the AAC problem, that decomposes the problem space and uses a decomposition-based framework to provide generalist and specialist configurations at the same time. For each objective, there is a set of problems related to it, and a decomposition based multi-objective algorithm is proposed to find good trade-off configurations. As the main study case, the work addresses flowshop problems. Extensive experiments performed on more than 6000 instances, consider MetaL PIAC to tune the parameters of different metaheuristics, and MOAAC/D to tune iterated local search and iterated greedy configurations. The results show that both strategies outperform the generalist solution provided by irace – one of the best well-known AAC – with a slight advantage of MOAAC/D over MetaL PIAC.