Using Meta-learning to Recommend Meta-heuristics for the Traveling Salesman Problem

• Main Authors: Kanda, J. Y., de Carvalho, A. C. P. L. F., Hruschka, E. R., Soares, C.
• Format: Conference Proceeding
• Language: English
• Subjects: Algorithm selection; Cities and towns; Genetic algorithms; meta-learning; multilayer perceptron network; Neurons; Optimization methods; Prediction algorithms; Predictive models; traveling salesman problem
• DOI: 10.1109/ICMLA.2011.153

Several optimization methods can find good solutions for different instances of the Traveling Salesman Problem (TSP). Since there is no method that generates the best solution for all instances, the selection of the most promising method for a given TSP instance is a difficult task. This paper describes a meta-learning-based approach to select optimization methods for the TSP. Multilayer perceptron (MLP) networks are trained with TSP examples. These examples are described by a set of TSP characteristics and the cost of solutions obtained by a set of optimization methods. The trained MLP network model is then used to predict a ranking of these methods for a new TSP instance. Correlation measures are used to compare the predicted ranking with the ranking previously known. The obtained results suggest that the proposed approach is promising.