Meta-learning to select the best meta-heuristic for the Traveling Salesman Problem: A comparison of meta-features
Meta-learning to select the best meta-heuristic for the Traveling Salesman Problem: A comparison of meta-features
复制标题
DOI：
10.1016/j.neucom.2016.04.027
复制
发表时间：
2016-09-12
期刊：
影响因子：
6
通讯作者：
Brazdil, Pavel
中科院分区：
文献类型：
--
作者：
Kanda, Jorge;de Carvalho, Andre;Brazdil, Pavel
旅行商问题（TSP）是研究最多的优化问题之一。各种Meta分析（MH）已被提出，并在此问题的许多情况下进行了研究。人们普遍认为，最佳MH因不同情况而异。理想情况下，应该能够为新的TSP实例推荐最佳MH，而不必执行它们。然而，这是一项非常艰巨的任务。我们通过使用基于标签排名算法的元学习方法来解决这个任务。这些算法构建了将那些实例的特征（即，元特征）与相对性能（即，MH的排名），基于从那些MH已经解决的TSP实例中提取的（Meta）数据。这种方法的成功取决于描述实例的元特征的质量。在这项工作中，我们研究了四组不同的元功能的基础上不同的测量TSP实例的属性：边缘和顶点的措施，复杂的网络措施，从MH的属性，和子采样地标属性。在四个不同的TSP方案提出对称性和连接强度的变化模型进行了研究。实验结果表明，元学习模型可以准确地预测不同TSP场景的MH的排名。良好的解决方案，调查TSP的情况下，可以得到从预测的排名的MH，无论使用的学习算法在Meta水平。实验结果还表明，元特征集的定义对所获得的解决方案的质量有重要影响。(C)© 2016 Elsevier B.V.版权所有。
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.