Selection of algorithms to solve traveling salesman problems using meta-learning¹

Issue title: Feature and algorithm selection with Hybrid Intelligent Techniques

Guest editors: Teresa B. Ludermir, Ricardo B.C. Prudêncio and Cleber Zanchettin

Article type: Research Article

Authors: Kanda, Jorge^{a; b; *} | Carvalho, Andre^{a; c} | Hruschka, Eduardo^a | Soares, Carlos^d

Affiliations: [a] Instituto de Ciencias Matematicas e de Computacao, Universidade de Sao Paulo, Sao Carlos, Brazil | [b] Instituto de Ciencias Exatas e Tecnologias, Universidade Federal do Amazonas, Itacoatiara, Brazil | [c] School of Computing, University of Kent, Canterbury, CT2 7NF, UK | [d] LIAAD-INESC Porto LA/Faculdade de Economia, Universidade do Porto, Porto, Portugal | Federal University of Pernambuco, Recife, Brazil

Correspondence: [*] Corresponding author: Instituto de Ciencias Matematicas e de Computacao, Universidade de Sao Paulo, Av. Trabalhador sao-carlense, 400, Centro, 13560-970, Sao Carlos, Sao Paulo, Brazil. Tel.: +55 16 3373 8161; Fax: +55 16 3373 9650; E-mail: kanda@icmc.usp.br

Note: [1] This is the extended version of the paper: Kanda et al. “Using Meta-learning to Classify Traveling Salesman Problems,” in Proc. of the 11th Brazilian Symposium on Neural Networks (SBRN 2010), pp. 73–78, IEEE Press, 2010.

Abstract: Many real-world problems, like microchip design, can be modeled by means of the well-known traveling salesman problem (TSP). Many instances of this problem can be found in the literature. Although several optimization algorithms have been applied to TSP instances, the selection of the more promising algorithm is, in practice, a difficult decision. In this paper, a new meta-learning-based approach is investigated for the selection of optimization algorithms for TSP instances. Essentially, a learning model is trained with TSP instances for which the performance of a set of optimization algorithms is known a priori. Then, the learned model is used to predict the best algorithm for a new TSP instance. Each instance is described by meta-features that capture characteristics of the TSP that affect the performance of the optimization algorithms. Given that the best solution for a given TSP instance can be obtained by several algorithms, the meta-learning problem is considered here to be a multi-label classification problem. Several experiments illustrate the performance of the proposed approach, with promising results.

Keywords: Meta-learning, multi-label classification, traveling salesman problem, meta-heuristics, algorithm selection

DOI: 10.3233/HIS-2011-0133

Journal: International Journal of Hybrid Intelligent Systems, vol. 8, no. 3, pp. 117-128, 2011