# Addressing the Algorithm Selection Problem through an Attention-Based Meta-Learner Approach
## 2 Background and Related Work  
The ASP was first introduced as a framework for choosing the best algorithm from a set of candidates that would yield the best performance for a particular problem in stance [22]. It was originally formulated as learning the selection mapping \(5(f(x))\) from problem instances \(x\in\mathcal{P}\), characterized by features \(f(x)\in\mathcal{F}\), into algorithm space \(\mathcal{A}\) such that, when solving the problem instance \(x\in\mathcal{P}\) with the selected algorithm \(a\in\mathcal{A}\), the performance metric \(y(a,f(x))\in\mathcal{Y}\) is maximized [6, 7]. A more modern outlook approaches the problem from a meta-learning perspective and focuses on learning the mapping \(5(f(x))\) through machine learning. In this case, the data that describe the four elements \(\{\mathcal{P},\mathcal{A},\mathcal{Y},\mathcal{F}\}\) are regarded as the meta-data [6, 7]. In such an approach, characterizing problem instances using relevant features plays an essential role in identifying the algorithm or configuration that yields the best performance for a specific problem instance. The set of features \(\mathcal{F}\) can include various types of information, such as the size of the problem instance, the type of data, or any other relevant characteristic. A critical aspect of the algorithm selection problem is determining the best features that accurately capture the relevant characteristics of the problem instance and lead to the selection of the most suitable algorithm. Identifying the optimal set of features that adequately characterizes a given problem instance is challenging. Moreover, it requires domain knowledge and experimentation to determine which features can be used to predict the performance of a particular algorithm or class of algorithms [6]. Multiple methods, both online and offline [23], have been proposed for computing the best problem-algorithm mapping, with the direction of research favoring the latter. Among offline methods, the ones following the meta-learning approach have gained attention and shown that using meta-learners, in combination with common meta-heuristics such as genetic algorithms (GAs) [17] or simulated annealing (SA) [24], can yield good results. Additionally, the literature that focuses explicitly on using supervised learning to select meta-heuristics for solving combinatorial optimization problems shows that the most common approaches employ mainly straightforward implementations of machine learning techniques. Among these implementations, we can mention neural networks [17, 18], linear and logistic regression [24], \(k\)-nearest neighbor (\(k\)-NN) [17], support vector machines (SVM) [18, 25], and decision trees (DT) [18, 26, 27]. [PERSON] et al. [23] and [PERSON] et al. [28] show that this applies to the most relevant and recent papers focusing on researching the ASP for selecting meta-heuristics to solve combinatorial optimization problems. Thus, works that fail to include one of these three main components (machine learning, meta-heuristics, or combinatorial optimization problems), as identified by [PERSON] et al. [23], are considered to not be within the scope of this work and, for that reason, excluded. Furthermore, meta-learners based on neural networks have proven to be adequate performance mapping mechanisms [17], even when most of the research has been mainly limited to simple architectures. For example, [PERSON] and [PERSON] proposed a meta-learning framework for analyzing the relationships between quadratic assignment problem characteristics and meta-heuristic performance, in which a multi-layer perceptron (MLP) was used as meta-learner [19]. Similarly, [PERSON] et al. used an MLP as a meta-learner for selecting the best meta-heuristic for the traveling salesman problem (TSP) [20].