改进的分布式并行遗传算法求解大规模TSP问题

曾坤，姜志侠，赵红梦

（长春理工大学 数学与统计学院，长春 130022）

TSP（Traveling Salesman Problem）旅行商问题，又称货郎问题，是数学学科中的一个著名问题。TSP问题的数学模型在实际应用中有着十分重要的作用，如物流配送、车辆路径优化、激光切割、机器人路径规划等［1-3］。TSP问题的具体描述为：旅行商拜访指定城市，已知各个城市的位置坐标，旅行商拜访仅且拜访每个城市一次，最终回到原来出发的城市，求旅行商经过城市的最短路径。此问题提出后，学者们相继对其进行了研究，也取得了不少成就。其求解方法大致分为精确式算法和启发式算法。精确式算法如穷举、动态规划、分支定界算法等，他们能够求解较小规模的TSP问题最优值，但是对于大规模TSP问题精确式算法求解所消耗的时间和计算资源往往是不能够接受的。近年来，随着启发式算法的发展，如遗传算法、粒子群算法、蚁群算法等，学者们将启发式算法用于求解TSP问题。启发式算法虽然不能像精确式算法那样求解到全局最优解，但是在能够接受一定偏差的情况下，节约了大量的计算时间和计算资源。其中遗传算法能够跳出局部最优，有着较强的随机搜索全局最优解的能力，利用交叉和变异可能产生出较目前更优的解，同时还有较好的扩展性，易与其他算法进行结合，在TSP问题的应用中也展现出了优良特性。文献［4］中，针对遗传算法求解TSP问题过程中收敛速度慢甚至无法收敛的情形，改进了适应度函数，以此增加个体区分度，对交叉算子采用淘汰机制，加快了算法的收敛能力。对50个城市点进行了求解，使得在较短时间内求得了较优解，但是该文献中仅对小规模TSP问题进行了研究。当城市规模较大时，自然分而治之的思想便产生了。郑旭峰等人［5］提出了一种k-均值聚类蚁群算法优化求解大规模TSP问题的方法，将大规模TSP问题聚类分组为小规模的子问题，然后用蚁群算法分别求解子问题，最后再将每个子问题合并，但是该算法对于小规模TSP问题求解精度较低，而大规模TSP问题的求解时间较多。李庆［6］等人分析了传统遗传算法的不足，传统遗传算法容易出现早熟、收敛速度慢、收敛结果不准确等问题。并对选择、交叉、变异三个阶段进行了优化，在一定程度上避免了“早熟”现象的发生，加快了收敛速度。针对以上问题，结合聚类分组小规模求解速度快、遗传算法较强的全局最优解搜索能力以及分布式计算运算速度快的优点，提出了一种改进的分布式并行遗传算法求解大规模TSP问题的方法。首先对大规模TSP问题用k-均值聚类，然后对每个子问题用分布式并行遗传算法进行求解。在大多数研究中，对遗传算法的染色体初始化采用的是随机初始化方法，其随机初始化的解质量差。因此用改进的贪心策略进行初始化，同时对遗传算法的交叉、变异和选择进行了改进，以此提高求解质量，最后将求解的每个子问题利用Delaunay三角剖分进行合并，得到整条TSP路径的解。

1 模型及算法原理

1.1 TSP问题模型

TSP问题是一个经典的组合优化问题。对于n个城市规模的TSP问题，其数学模型为［7］：

其中，Z表示TSP问题的目标函数值；dij表示城市点i到城市点j的距离；xij为决策变量。如果城市点i到城市点j连通则xij的值为1，否则为0。n表示TSP问题的城市点个数。约束（1）和约束（2）表示任何一个城市点都只有两个城市点相连，即旅行商从一个城市点进入该城市点，以及从该城市点出发达到另一个城市点。V={1,2,…,n}表示由城市点的序号组成的点集，Q表示点集V中任意元素个数大于2的真子集。|Q|表示点集Q的元素个数，约束（3）表示所有拜访过的城市点组成仅且组成一个回路。xij取值为0～1的整型变量，并且i≠j，即每一个城市点不能与自身相连。

1.2 k-均值聚类算法

TSP问题属于NP难问题，复杂度随着城市数量的增加成指数增长，其精确式算法求解所带来的时间成本往往是不能够让人接受的。因此采用分而治之的思想，将TSP问题用k-均值算法进行聚类分组，然后求每个子问题的解，最后将子问题进行合并。虽然分组优化求解的最终结果不一定是原问题的最优解，但是聚类分组能够极大地降低求解时间和复杂度，在求解精度和求解时间之间起到了一个很好的均衡作用。k-均值聚类是一种无监督算法，不需要数据集有标签。只需要输入聚类的类别数k，然后根据欧式距离将数据集中离每个聚类中心较近的点分为k个类。其主要步骤为［8］：

（1）随机选取k个点，作为聚类中心。

（2）计算数据集中每个点分别到聚类中心的距离，然后将该点分配到离聚类中心最近的聚类族中。

（3）更新聚类中心，利用族中所有点的均值作为每一个族新的聚类中心。

（4）重复上述步骤，直到聚类中心的位置趋于稳定。

采用k-均值聚类算法对大规模TSP问题进行分组，经过多次实验发现每个子问题的规模为250个城市点时算法的各个性能较为均衡。对于规模300以下的数据集直接采用遗传算法进行求解。对于规模大于300个城市点的数据集，进行聚类分组，将聚类分组的每个子问题分别用遗传算法进行求解，得到子问题的优化解，然后再进行合并。

1.3 改进的贪心策略初始化种群

贪心算法是一种逐步逼近最优解的算法［9］。虽然贪心算法求到的解可能不是全局最优，但是对于一些不能在多项式时间内求到最优求解的问题，贪心算法在一定程度上能够靠近最优解。本小节采用贪心策略对遗传算法的种群进行初始化，贪心策略在执行时每一步总是寻找当前最优，在一定程度上影响了初始种群的质量。若仅考虑当前最优，在拜访城市过程中，可能会出现四个城市两条路径相互交叉的情况，如图6虚线框B处。由于在三角形中两边长度之和大于第三边长度，其交叉的路径会增加访问的最终距离，因此对贪心策略进行改进。

改进的贪心策略初始化种群的具体思想为：随机选择一个城市作为初始城市点，然后寻找离该城市最近的城市点作为拜访的下一个城市，对当前两个城市点连成的线段进行判断是否与前面的路径存在交叉，如果存在交叉则重新选择一个城市作为下一个要拜访的城市点。如果重复w次仍然找不到满足要求的城市点，则接受这个交叉以该城市作为下一个要拜访的城市点。依次重复上述步骤，直到全部拜访完所有的城市点回到初始的城市点。判断两条线段是否交叉的步骤如下：设有四个城市点分别为，四个点组成的两条线段为 p1p2，p3p4。

（1）判断p1p2和p3p4组成的直线是否重合或平行，如果否，计算直线p1p2和直线p3p4的交点D(x ,y)。

（2）分别计算两条线段的端点与交点的凸组合，求解系数 λ1～λ4：

（3）如果0 ≤ λ1～λ4≤ 1，则线段 p1p2与线段p3p4相交。

1.4 分布式并行遗传算法求解大规模TSP问题

遗传算法由 Holland，John在 1975提出［10］，是一种模仿自然界中生物进化原理的启发式算法。通过遗传机制、自然进化和自然选择搜索全局最优解。遗传算法具有十分强的全局最优解搜索能力。同时遗传算法具有非常好的可扩展性，易于与其他算法进行结合，以此提高求解的质量。遗传算法的一般步骤为编码、种群初始化、选择、交叉、变异。遗传算法求解TSP问题的一般过程中，存在交叉变异后城市点出现重复和缺少现象。并且基于概率的交叉、变异和选择方式存在很大的不确定性。本文对上述问题进行了改进，摒弃了传统遗传算法中基于概率的交叉、变异和选择方式，让种群依次顺序进行交叉、就近策略进行变异，每一次交叉变异后进行局部最优选择子代，再对每一次选择的局部最优个体进行优化。

编码及种群初始化：编码及种群初始化是遗传算法中的一个重要环节，好的编码和种群初始化策略能够有效地提高初始解的质量。根据TSP问题的性质，采用符号编码方法进行编码，每一个城市对应一个序号。如有5个城市，则序列3→2→5→1→4表示一条路径。使用改进后的贪心策略进行种群初始化。

交叉：将种群中个体的染色体进行重组，得到的子代的基因可能优于父代，是遗传算法中获取更优个体的重要途径。由路径组成的染色体随机选择父代中的片段进行交叉，得到的子代路径可能出现城市点重复或缺少的现象，或者可能会大量修改交叉片段之外的基因信息［11］。对传统交叉方式进行改进，采用基因片段先删除后插入策略，对n个个体的种群pop，进行n次循环，循环变量为i，父代f1=pop[i]依次从种群中顺序选取，父代f2随机选取异于f1的个体，让整个种群的父代f1按顺序进行交叉。随机选择两个交叉点索引 i1和 i2（i1＜i2），记 f1和 f2中 i1的前一个点分别为p1和p2，取f1和f2交叉点之间的基因片段s1和s2，然后删除在f1中的基因片段s2的点，在f1中查找点p2的下标索引idx2，将基因片段s2插入到f1的idx2位置后面，从而得到子代child1。对p2做同样的处理，删除在f2中的基因片段s1的点，在f2中查找p1的下标索引idx1，将基因片段s1插入到f2的idx1位置后面，得到子代child2。这样的交叉方式，插入新基因前已经在要插入的父代中删除了新基因表示的城市点，保证了交叉的个体不会出现城市点缺失和重复。同时新基因插入点为原来个体中基因片段的前一个点，保证了新插入的基因片段与新个体的有效融合。

变异：经过交叉后得到两个子代child1和child2，将这四条染色体进行变异。常用的方法有随机变异法，即随机选择两个城市点，然后交换这两个城市的位置。显然对于两个相距较远的城市进行变异很难获得更优的解。因此本节对交换城市进行限制采用就近交叉机制，以此提高获得更优解的概率。首先对所有城市点的距离矩阵按列排序。随机选择变异点c1，在距离矩阵中检索离c1最近的m个点，将c1删除，然后将c1随机插入m个点中的一个点后。

选择：传统遗传算法中选择操作是以某一概率（如轮盘赌）的形式从父代种群中选择父代种群规模大小的个体组成新的种群，以便进行下一次的迭代。由于以概率的方式进行选择，带有很大的不确定性。如不能保证上一代最优的个体能够遗传到下一代。不能保证种群的多样性。提出了一种种群中所有个体按顺序全部进行交叉、变异的局部最优的选择方法。对f1和f2进行交叉操作后得到child1和child2，将child1和child2两条染色体进行变异，得到变异后的染色体mut1和mut2。分别计算这两条染色体的适应度值（以该条路径的距离的倒数作为适应度值）。比较这两条染色体和父代f1的适应度值，若有比f1适应度值更大的个体，则将该个体替换父代f1，从而组成新的种群。

分布式并行运算：使用k-均值算法进行聚类分组后的每个子问题之间的计算不需要进行通信，耦合度低。对于分组后的子问题，每个子问题的交叉、变异之间互不影响，因此可以将大规模问题进行分组在多个节点上，分别计算子问题，达到分布式并行计算的目的，提高计算效率。利用改进的贪心策略初始化种群，由于每个子问题之间是独立的，将分组后的子问题分配到不同的计算节点中同时进行交叉、变异以及适应度值计算，每一个子问题经过交叉变异后在子代和父代中选择出最优的个体，组成新的种群。然后进入下一轮迭代，重复上述步骤直到满足终止条件，最终得到每一个子问题的解。

优个体插入：在迭代多次后，适应度值较低的个体优化空间较大，能够继续进行更新，而种群整体的最优适应度值更新较慢。根据遗传机制特点，在第t次迭代后，删除种群中适应度值较小的r个个体，将适应度值最大的个体，随机插入删除后的种群中r次，继续迭代。这样增加了最优个体与其他个体交叉、变异的几率，更有机会产生更好的个体优于当前种群的最优个体。

优化：在遗传算法中，经过交叉变异选择后的个体还有一些较多的优化空间。如：（1）某一个城市点离其他城市点连接成的线段非常近，可以通过将该城市点插入到其中减小拜访距离，如图6虚线框A处；（2）路径中可能还存在两个线段交叉，如图6虚线框B处，可以移除交叉进行优化；（3）交换两个城市点的顺序可以将拜访的总距离减少，如图6虚线框C处。由于TSP问题是NP难问题较多的城市点导致计算复杂度较高，因此只对每一次交叉、变异后局部最优选择得到的个体用上述三种方法进行优化，具体过程如下。

优化1：对存在交叉的路径进行去交叉操作，具体步骤为：利用1.3中的判断两条线段相交的算法找出路径中相交线段，改变相交线段点的顺序，使得路径不存在交叉，路径中其他点的顺序不变，如图1。

图1 移除交叉路径示意图

优化2：对于一些距离其他路径非常近的城市点，将这些城市点就近插入到与其最近的路径中，然后比较插入前和插入后的局部路径的距离。如图2，计算优化前路径与优化后路径的距离差值，如果插入后的距离有所减少，则插入成功，否则不插入。

图2 城市点就近插入示意图

优化 3：采用 2-opt方法［12］对路径进行优化，具体步骤为选取有序的四个城市a→b→c→d，交换b→ c的顺序，交换后的路径为a→c→b→d，然后计算交换前后的路径的距离，如果距离优于交换前则接受这个交换，否则不接受。

1.5 子问题的合并

通过上述的遗传算法求得了TSP问题子路径的优化解，本小节主要将每个子路径连接成一个最短路径。文献［13］中，作者给出了一种连接两个不相交多边形成一条最短回路的算法。在本问题采用该方法对子问题进行相继合并。先将所有子问题两两计算合并后增加的距离，找出增加距离最小的两个子问题进行合并，将合并后的路径与剩下所有子问题分别计算合并后增加的距离，然后将已合并的路径与增加距离最短的子问题进行合并，依次这样合并，直到所有子问题被全部合并。其合并算法具体步骤如下：

（1）将两个子路径path1和path2的首尾分别相连组成回路，如图3，分别求出回路的凸壳p1p2p3p4p5p6p7p1和q1q2q3q4q6q7q1。

图3 未删除Delaunay边的剖分图

（2）求出凸壳的两条不相交的切线段p2q7和p6q3，path1的切点分别为 p2和 p6，path2的切点分别为q7和q3。分别将子路径相近一侧的切点之间的点组成序列sqe1为p2p3p4p5p6和sqe2为q3q4q5q6q7，将sqe1和sqe2的首尾相连组成一个不相交的回路，sqe为p2p3p4p5p6q3q4q5q6q7p2。

（3）对sqe进行Delaunay三角剖分［14］，图3中虚线段则为Delaunay边，Delaunay三角剖分中的任意一条Delaunay边均存在一个过该边端点的圆，其圆内不包含点集中其他的点，圆上最多三点共圆，这样避免了距离较大的顶点对连接成凸四边形，使得相邻两个三角形组成的凸四边形对边长度和的差较小。删除两个顶点都在同一个路径点集中的Delaunay边，例如p3p5、q6q4等，仅保留顶点在不同的路径点集中的Delaunay边，如p2q6、p3q6等。图4是删除顶点在同一路径点集中Delaunay边的三角剖分图。对三角剖分后形成的凸四边形进行遍历，如p2p3q6q7、p4p5q3q4等，然后计算每一个凸四边形两组对边和的差值，如：将差值最小的一组凸四边形作为两个子问题合并的接口，如凸四边形p4p5q3q4删除p4p5和q3q4边，连接p4q4和p5q3边，这样得到的路径是最短的，合并后的路径为p1p2p3p4q4q5q6q7q1q2q3p5p6p7p8p1。

图4 删除Delaunay边的剖分图

在小本节通过k-均值聚类算法将大规模TSP问题进行分组，有效地降低了求解时间复杂度。利用改进的贪心策略对种群进行初始化，大幅度提升了初始种群的质量。利用改进的分布式并行遗传算法进行求解，同时使用三种优化方法对局部最优个体进行优化，使得求到的解精度大大提高。对于大规模问题，通过Delaunay三角剖分算法进行子问题的合并，保证了所有子问题合并后距离是最短的。整个算法的流程图如图5所示。

图5 整个算法流程图

2 实验

针对提出的算法，选取了不同规模的TSP问题进行求解验证算法的性能。实验环境为：处理器Intel（R）CPU E5-2620 v4@2.10 GHz 2.10 GHz，内存16.00 GB，操作系统为windows10，编程语言环境为Python3.7。算法中一些参数值预先设定：聚类的类别数以城市点个数除以250。在贪心策略初始化中w值取5。插入最优个体时的迭代次数t为50，插入最优个体次数r为5次。遗传算法的种群设为40，迭代次数为1 000，或连续50次迭代结果无变化则终止算法。交叉染色体片段的最大长度为染色体长度的一半。

对于小规模TSP问题不进行k-均值聚类分组，直接使用改进的遗传进行求解，其求解结果如表1和表2所示。已知最优解是TSPlib公布的最优解（http：//elib.zib.de/pub/mp-testdata/tsp/tsplib/stsp-sol.html），改进算法是通过改进的分布式并行遗传算法进行求解的结果。误差率计算公式为：（改进算法-已知最优解）/已知最优解，对比可以看出提出的算法在求解质量和求解时间都较优。由误差率可以看出提出的算法求出的解十分接近已知最优解，与已知最优解误差均在1%以内。由10次实验平均值与改进算法求得的解相近，说明提出的算法具有较强的稳定性。表3给出了传统遗传算法和现有的用于求解TSP问题的蚁群算法结果，从表中可以看出传统的遗传算法的精度较低，且求解时间长，对比表1和表2可以看出，改进的遗传算法较传统的遗传算法和蚁群算法无论是在求解精度和求解时间均相对较优。

表1 小规模TSP问题求解结果1

表2 小规模TSP问题求解结果2

表3 传统遗传和蚁群算法求解TSP结果

以数据集st70为例，图6～图8给出了求解过程的可视化。图6是数据集st70经过改进贪心策略初始化的一个个体。相比于随机初始化，个体质量明显较优。图7是经过提出的算法优化求解得到的最优路径图。图8是遗传算法中最优个体的路径距离进化过程。可以看出刚开始迭代进化速度快，这是由于初始化形成的个体存在图6虚线框A、B、C三种情形，优化空间较大，因此前期曲线下降较快。随着迭代的进行越来越趋近于最优解，进化速度较慢，最终达到稳定，收敛曲线图符合理论分析。

图6 数据集st70初始化染色体

图7 数据集st70最优路径图

图8 数据集st70收敛曲线

对于超过300个城市点的大规模TSP问题，采用聚类分组对子问题进行求解，然后将子问题进行合并得到问题的解。选取了部分大规模TSP城市进行求解，其求解结果如表4和表5所示。

表4 大规模TSP问题求解结果1

表5 大规模TSP问题求解结果2

从表4和表5中可以看出，对于大规模TSP问题，改进算法求得的解与已知最优解相近，其误差均在10%以内。其多次求解的平均值与最优值相差不大，改进算法求解大规模TSP问题较为稳定，求解质量好，求解时间较少。在表1和表2最后一栏列出了文献［15］中求解大规模TSP问题的误差率，改进算法结果中除数据集pcb3038比文献［15］稍差以外，其余结果均比文献［15］较优，特别是对于小规模TSP问题，提出的算法相比于文献［15］的结果精度高很多。在表1和表2中，数据集pr439没有进行聚类分组求解，直接使用遗传算法求解。在表4和表5中数据集pr439采用聚类分组求解，通过对比可以看出聚类分组求解对于大规模问题在求解时间和求解精度上都明显较优。

随着TSP城市点数量的增多，大规模TSP问题的求解的误差和求解时间都有所增加。图9给出rl1323优化后最优路径图。在大规模求解中，由于求解的各个子问题相对独立，因此在大规模求解TSP问题时对子问题采用分布式并行运算，每一个子问题分配一个计算节点进行并行求解，以此提高求解速度。因此在表4和表5中的求解时间受多因素影响，如计算机性能、计算节点数、代码优化等。

图9 数据集rl1323最优路径图

3 结论

针对求解大规模TSP问题，采用k-均值算法对大规模TSP问题进行聚类分组，用分布式并行遗传算法对分组后的子问题进行求解。首先用改进的贪心策略进行种群初始化，摒弃了传统遗传算法基于概率的交叉、变异、选择方式，提出了按顺序交叉、变异和局部最优选择的分布式并行遗传算法，同时给出了三种优化方法对局部最优的个体进行优化，有效地提升了遗传算法的求解质量。对于优化求解后的子问题，采用Delaunay三角剖分算法对子问题进行合并，使得合并后的路径最短。最后通过实验仿真以及其他文献结果对比，显示了提出的算法性能良好。如今快递、物流行业等的快速发展，车辆路径优化需求大，在此基础上可以考虑更多的约束和具体实际背景，求解车辆路径优化相关问题，也是接下来研究的方向之一。