问题背景

旅行商问题（简写为TSP问题)是一类非常经典的NP-难的组合优化问题。给定n个节点以及它们两两之间的距离，求解TSP问题需要找到这n个点的最短遍历路径。TSP问题是物流配送、工程调度、金融投资等领域中的许多实际问题的抽象形式，其在20世纪中叶被提出。时至今日，TSP问题依然是运筹优化领域的热门研究方向。TSP问题解空间中充满了海量的局部最优点，求解难度随着问题规模的增大而急速增大。

主要贡献

虽然针对TSP问题的研究有很多，但将TSP问题进行平滑化（smoothing）处理的研究极少。本课题组发表于IEEE Transaction on Cybernetics的论文提出了一种基于同伦凸变换(Homotopic Convex Transformation，简写为HC变换)的2维TSP平滑方法。

该方法的基本原理如下：假设原TSP问题有n个节点，并且我们已知该问题的一个局部最优解x*，HC变换法首先构造一个同样具有n个节点的新TSP问题，称为“凸包TSP问题”（convex-hull TSP），在新构造的凸包TSP问题中，n个节点排列成一个圆环（凸包）形状，并且它们的排列顺序与x^*中节点的排列顺序一样，如图1所示。

        （a）原TSP问题及其局部最优x^*      （b）针对原问题和所构造的凸包TSP

图1 构造凸包TSP的一个例子

在论文中，我们从理论上证明了，凸包TSP问题对于任意一种基于局部搜索的算法，其解空间都是单峰的（unimodal），即其中不存在局部最优解，只存在一个全局最优解，这个全局最优解就是凸包上的节点按顺序连接后的对应的解。这就意味着，凸包TSP问题的解空间是单峰且完全平滑的。

基于构造的凸包TSP，HC变换法将原TSP问题f_o(x)和凸包TSP问题f_c(x)据权重λ加权求和得到新问题g(x)，来达到平滑原问题的目的：

g(x|λ)=(1-λ) f_o(x)+λf_c(x)

可以看到，当λ=0时，g就等于未被平滑的原问题f_o，当λ=1时，g就等于完全平滑的凸包问题f_c，如图2所示。这与拓扑学中同伦（homotopic）的概念相类似，这也是为什么我们将这种变化方法称为同伦变换的原因。

图2  HC变换法中λ对TSP解空间的平滑性的影响（示意图）

在论文中，我们探索了局部最优解x^*的质量对HC变换法的效果的影响。实验结果表明，x^*的质量越高，基于其所进行的HC变换的效果在整体上越接近于基于原问题的全局最优解所进行的HC变换。

基于该观察，我们提出了结合HC变换的迭代局部搜索算法框架，并将该框架分别应用于3-Opt局部搜索算法和LK局部搜索算法。我们在一些中、大规模的TSP问题实例（n最大达到20000）上进行了算法对比实验，结果证明，通过引入λ取值的自适应变化,在结合了HC变换法之后，3-Opt局部搜索算法和LK局部搜索算法的性能都有了大幅提升。例如，图3为在pcb3038问题上的算法比较结果，横轴为时间，纵轴为当前最好解与全局最优值的差距，其中的LSILS-LK所标记的四条曲线即为基于HC变换的算法框架所取得的结果，与其他对比算法相比，基于HC变换的算法框架在相同的时间内所得到的结果更接近于全局最优解。这清晰说明了我们所提出的HC变换方法对求解TSP问题的重要性。

图3 在pcb3038上的算法对比结果

参考文献

[1] J. Shi, J. Sun（*）, Q. Zhang and K Ye, "Homotopic Convex Transformation: A New Landscape Smoothing Method for the Traveling Salesman Problem," accepted in IEEE Transactions on Cybernetics, 2020.