A Meta-Learning Approach to Select
Meta-Heuristics for the Traveling Salesman
Problem Using MLP-Based Label Ranking
Jorge Kanda1,2 , Carlos Soares3, Eduardo Hruschka1 , and Andre de Carvalho1
1
Instituto de Ciencias Matematicas e de Computacao, Universidade de Sao Paulo,
Avenida Trabalhador Sao-Carlense, 400 - Centro, 13566-590 Sao Carlos - SP, Brazil
{kanda,erh,andre}@icmc.usp.br
2
Instituto de Ciencias Exatas e Tecnologias, Universidade Federal do Amazonas,
Rua Nossa Senhora do Rosario, 3863 - Tiradentes, 69103-128 Itacoatiara - AM, Brazil
3
INESC TEC Porto LA/Faculdade de Economia, Universidade do Porto,
Rua Dr. Roberto Frias, 4200-464 Porto, Portugal
csoares@fep.up.pt
Abstract. Different meta-heuristics (MHs) may find the best solutions
for different traveling salesman problem (TSP) instances. The a priori
selection of the best MH for a given instance is a difficult task. We
address this task by using a meta-learning based approach, which ranks
different MHs according to their expected performance. Our approach
uses Multilayer Perceptrons (MLPs) for label ranking. It is tested on
two different TSP scenarios, namely: re-visiting customers and visiting
prospects. The experimental results show that: 1) MLPs can accurately
predict MH rankings for TSP, 2) better TSP solutions can be obtained
from a label ranking compared to multilabel classification approach, and
3) it is important to consider different TSP application scenarios when
using meta-learning for MH selection.
Keywords: meta-learning, label ranking, multilayer perceptron, travel-
ing salesman problem.
1 Introduction
The Traveling Salesman Problem (TSP) is a classic optimization problem, which
is formally defined by means of a weighted graph G = (V, E), in which V = {v1 ,
v2 , ..., vn } is a set of vertices and E = {vi , vj : vi ,vj ∈ V } is a set of edges. Each
vertex vi ∈ V represents a city and each edge vi , vj ∈ E connects the vertices
vi and vj . The cost of travel from vi to vj is given by the weight value of the
edge vi , vj . The best solution for a TSP instance involves finding the minimal
cost tour visiting each of n cities only once and returning to the starting city [1].
It is difficult to find the best solution for several TSP instances, since this
problem belongs to the class of problems known as NP-complete [16]. The TSP
complexity is factorial with the number of cities, thus exhaustive search methods
T. Huang et al. (Eds.): ICONIP 2012, Part III, LNCS 7665, pp. 488–495, 2012.
c Springer-Verlag Berlin Heidelberg 2012
, A Meta-Learning Approach to Select MHs for the TSP Using Label Ranking 489
present a high computational cost even for small TSP instances. For example,
there are approximately 1.22 × 1017 feasible solutions for a TSP with 20 cities.
Good solutions for TSP can be quickly found by different meta-heuristics
(MHs) — e.g., Genetic Algorithms [13], and Ant Colony [5]. MHs are search
methods that try to escape from local optima through of interaction between
local improvement procedures and higher level strategies [8]. Each MH has its
own bias which makes it more suitable for a particular class of instances [25].
Thus, given the large number of available MHs, there can be a MH that is the
best for a new TSP instance.
Recently, a meta-learning approach addressed the problem of recommending
MHs for new TSP instances as a multilabel classification task [14]. However,
when multiple MHs are recommended, no guidance is provided concerning the
order in which they should be executed. In this work, we address this problem
by using a label ranking approach [4] to predict a ranking of MHs, according
to their expected performance. Additionally, previous approaches do not distin-
guish between different TSP scenarios. Here we separately investigate two im-
portant scenarios: when the salesperson (re-)visits current customers and when
the prospects are visited for the first time.
The remainder of this paper is organized as follows. Section 2 provides a brief
background on meta-learning for algorithm selection and on label ranking. The
adaptation of MLPs to learn label rankings is discussed in Section 3. Practi-
cal application scenarios of interest are described in Section 4. Based on such
scenarios, the experimental setting is detailed in Section 5, and the results are
reported in Section 6. Finally, the conclusions are presented in Section 7.
2 Meta-Learning and Label Ranking
The selection of the best algorithm for a given problem has been dealt with
in Machine Learning (ML) with meta-learning [2]. Meta-learning studies how
learning systems can increase in efficiency through experience and how learning
itself can become flexible according to the domain or task under study [24].
Studies that relate ML and optimization problems are recent [20]. Concern-
ing the TSP, a meta-learning approach to recommend MHs [14] classifies TSP
instances according to the solutions obtained by a set of MHs. As the best solu-
tion for a given TSP instance may be achieved by more than one MH, multilabel
classification techniques are applied. In [19], MLP-based models are induced to
predict the search effort that each algorithm will need to find the best solution.
The induction of a meta-learning model to select MHs for the TSP is illus-
trated in Figure 1. TSP properties (meta-features) are calculated to a set of TSP
instances. Each instance corresponds to one meta-example in the meta-data. A
meta-example is labeled by the performance of different MHs when applied to
TSP instance. The meta-data is used by a ML technique to induce a meta-model.
In this work, meta-learning is addressed as a label ranking task [7]. In label
ranking, the learning problem is to map the instances x from a dataset X to
rankings ≻x (total strict orders) over a finite set of labels L = {λ1 , ..., λm },
