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

NEUROCOMPUTING

卷:205

Article

Kanda, Jorge¹  de Carvalho, Andre²  Hruschka, Eduardo²  Soares, Carlos³  Brazdil, Pavel⁴ 

[1] Univ Fed Amazonas, Inst Ciencias Exatas & Tecnol, Rua Nossa Senhora Rosario 3863, BR-69103128 Itacoatiara, Amazonas, Brazil

[2] Univ Sao Paulo, Inst Ciencias Matemat & Comp, Av Trabalhador Sancarlense 400, BR-13566590 Sao Paulo, Brazil

[3] Univ Porto, Fac Engn, INESC TEC, Oporto, Portugal

[4] Univ Porto, Fac Econ, LIAAD INESC Tec, Oporto, Portugal

关键词: Meta-learning;    Meta-features;    Label ranking;    Meta-heuristics;    Traveling Salesman Problem;   

DOI  :  10.1016/j.neucom.2016.04.027

来源: Elsevier

【 摘 要 】

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. (C) 2016 Elsevier B.V. All rights reserved.

【 授权许可】

Free