Meta-learning to select the best meta-heuristic for the Traveling Salesman Problem: A comparison of meta-features

• Type: Article in International Scientific Journal
• Date: 2016

Authors

Kanda, J (Author) Other; de Carvalho, A (Author) Other; Hruschka, E (Author) Other; Carlos Soares (Author) FEUP; Pavel Brazdil (Author) FEP

Journal

Title: Neurocomputing

Vol. 205

Pages: 393-406

ISSN: 0925-2312

Publisher: Elsevier

Indexing

ISI Web of Knowledge - 35 Citations

Scopus - 50 Citations

Other information

Authenticus ID: P-00K-K0A

DOI: 10.1016/j.neucom.2016.04.027

Abstract (EN): The Traveling Salesman Problem (TSP) is one of the most studied optimization problems. Various meta heuristics (MHs) have been proposed and investigated on many instances of this problem. It is widely accepted that the best MH varies for different instances. Ideally, one should be able to recommend the best MHs for a new TSP instance without having to execute them. However, this is a very difficult task. We address this task by using a meta-learning approach based on label ranking algorithms. These algorithms build a mapping that relates the characteristics of those instances (i.e., the meta-features) with the relative performance (i.e., the ranking) of MHs, based on (meta-)data extracted from TSP instances that have been already solved by those MHs. The success of this approach depends on the quality of the meta-features that describe the instances. In this work, we investigate four different sets of meta-features based on different measurements of the properties of TSP instances: edge and vertex measures, complex network measures, properties from the MHs, and subsampling landmarkers properties. The models are investigated in four different TSP scenarios presenting symmetry and connection strength variations. The experimental results indicate that meta-learning models can accurately predict rankings of MHs for different TSP scenarios. Good solutions for the investigated TSP instances can be obtained from the prediction of rankings of MHs, regardless of the learning algorithm used at the meta level. The experimental results also show that the definition of the set of meta-features has an important impact on the quality of the solutions obtained.

Language: English

Type (Professor's evaluation): Scientific

No. of pages: 14