Kerschke Pascal, Kotthoff Lars, Bossek Jakob, Hoos Holger H, Trautmann Heike
Information Systems and Statistics, University of Münster, 48149 Münster, Germany
Department of Computer Science, University of British Columbia, Vancouver, B.C., V6T 1Z4, Canada
Evol Comput. 2018 Winter;26(4):597-620. doi: 10.1162/evco_a_00215. Epub 2017 Aug 24.
The Travelling Salesperson Problem (TSP) is one of the best-studied NP-hard problems. Over the years, many different solution approaches and solvers have been developed. For the first time, we directly compare five state-of-the-art inexact solvers-namely, LKH, EAX, restart variants of those, and MAOS-on a large set of well-known benchmark instances and demonstrate complementary performance, in that different instances may be solved most effectively by different algorithms. We leverage this complementarity to build an algorithm selector, which selects the best TSP solver on a per-instance basis and thus achieves significantly improved performance compared to the single best solver, representing an advance in the state of the art in solving the Euclidean TSP. Our in-depth analysis of the selectors provides insight into what drives this performance improvement.
旅行商问题（TSP）是研究得最为深入的NP难问题之一。多年来，人们开发了许多不同的求解方法和求解器。我们首次在大量著名的基准实例上直接比较了五个最先进的不精确求解器，即LKH、EAX、它们的重启变体以及MAOS，并展示了互补性能，因为不同的实例可能由不同的算法最有效地求解。我们利用这种互补性构建了一个算法选择器，该选择器在每个实例的基础上选择最佳的TSP求解器，因此与单个最佳求解器相比，性能有显著提高，这代表了在求解欧几里得TSP方面的技术进步。我们对选择器的深入分析揭示了推动这种性能提升的因素。
