基于聚类集成的蚁群算法求解大规模TSP问题

叶家琪，符 强，2，贺亦甲，叶 浩

(1.宁波大学科学技术学院，浙江 宁波 315212； 2.宁波大学信息科学与工程学院,浙江 宁波 315211)

0 引 言

TSP问题又称货郎担问题。该问题描述的是由旅行商人拜访给定的城市，而每个城市必须经过且只能访问一次，最后回到第一次拜访的城市从而完成旅行，为满足该条件旅行商人有多种不同的路线选择，求解TSP问题是为了找出所有路线中具有最短距离的路线。当代的车辆路径规划、物流配送等问题都属于生活中常见的TSP问题。对该问题的求解方法可概括为精确算法和群智能算法。精确算法的目的是为了找到问题的最优解，然而该算法在求解问题时的复杂度大，对计算机的性能要求很高，且随着TSP问题数据规模的扩大，求解问题的时间呈指数增长。故同时考虑到在求解TSP问题时的时间与精度，更多是运用群智能算法求取问题的近似解。常见的群智能算法有ACA[1-6]、GA(Genetic Algorithm)[7-9]以及PSO(Particle Swarm Optimization)[10-12]。在这些群智能算法中，蚁群算法具有鲁棒性强、求解组合优化问题效率高的特点，故被广泛应用于解决TSP问题。

但在处理具有较大规模数据的TSP问题时，蚁群算法具有时间复杂度大、搜索结果精度低、求解效率不强等问题。文献[13]针对蚁群算法求解TSP问题搜索时间长、易出现早熟停滞现象，利用变参数选择城市策略,并且在交叉策略中选择PMX(Partially Matched Crossover)交叉策略，从而减小了算法运行时间，提高了算法效率。文献[14]通过对信息素进行方向引导,并通过对信息素重新分配，在全局引入动态因子，使得最后问题的结果更为精确。文献[15]提出了一种改进信息素二次更新局部优化蚁群算法解决蚁群算法收敛速度慢、容易陷入局部最优的缺陷。尽管以上文献对蚁群算法的改进可以有效解决数据规模较大的TSP问题，但是仍有不足。若数据规模再继续扩大，城市数目达到几百甚至几千时，算法求解TSP问题的效果便会越来越差，求解时间长，误差率增大。

因此针对该现象，本文提出一种基于聚类集成[16-19]的蚁群算法。基于改进聚类集成的蚁群算法采用了“分合治之”的思想，“分”是利用AP聚类[20-23]将大规模TSP问题分为若干子问题，并对每个子问题用蚁群算法进行寻优，“合”是利用改进的集成方案对子问题进行组合。最后，分别将蚁群算法、基本集成聚类的蚁群算法以及基本改进集成聚类的蚁群算法对TSP的标准数据库进行测试，将各算法的实验结果进行对比。所得结果表明，相比于传统蚁群算法，基本改进集成聚类的蚁群算法在求解大规模TSP问题时求解时间短，改进的集成方案使该算法的求解质量也得以保证。

1 算法原理及简介

1.1 蚁群算法

自然界中蚂蚁会根据前面走过的其他蚂蚁所留下的信息素对接下来要走的路径进行选择。一条路径的信息素浓度越强，蚂蚁选择该路径的概率越高。因此，在由大量蚂蚁组成的群体的路径寻优过程中，形成一种信息学习的正反馈现象。即某一条路径走过的蚂蚁越多，后边的蚂蚁选择该路径的概率越大。蚂蚁的个体便通过信息素的反馈寻求通向食物的最短路径。蚁群算法解决TSP问题的传统方案可简要概括如下：

Step1在初始时刻，把m只蚂蚁随机放在n个城市中，信息素初始值设为0。

Step2用dij(i,j=0,1,…,n-1)表示城市i和城市j之间的距离，蚂蚁k(k=1,2,3，…，m)选择下一个城市的转移概率如公式(1)所示：

(1)

公式(1)中，τij(t)表示边(i,j)上的信息素，allowedk表示可供蚂蚁k下一步选择的所有城市的集合；α为信息启发式因子，表示路径上的信息素浓度对蚂蚁选择路径所起的影响程度；β为期望启发式因子，表示能见度的相对重要性。

Step3为了让每个城市仅访问一次，用禁忌表tabuk记录蚂蚁k已经走过的路径。在m只都访问完n个城市并回到出发城市时，保留最优路径，并更新信息素。信息素按公式(2)和公式(3)更新：

τij(t+n)=(1-ρ)×τij(t)+Δτij(t)

(2)

(3)

Step4若算法达到了结束要求，输出最优路径以及长度。

1.2 AP聚类

AP聚类算法是2007年Frey和Dueck在Science杂志上提出的一种新的聚类算法。对于N个数据点，AP聚类算法可以对这些点之间的相似度进行聚类。这些相似度组成N×N的相似度矩阵S。AP聚类算法不需要事先指定聚类数目,相反它将所有的数据点都作为潜在的聚类中心,并在迭代的过程不断搜索合适的聚类中心,自动从数据点间识别聚类中心的位置以及个数，使所有的数据点到最近的聚类代表点的相似度之和最大。AP聚类的算法流程如下：

Step1建立相似度矩阵S，计算数据点i和数据点j之间相似度s(i,j)。2个数据点间的相似度大小用欧氏距离的负数表示，如公式(4)所示：

s(i,k)=-‖xi-xk‖2

(4)

Step2聚类过程中，共有2种消息在各数据点间传递，分别是吸引度和归属度。建立吸引度矩阵r(i,k),表示数据点k适合作为数据点i的聚类中心的程度,归属度矩阵a(i,k)，表示数据点i选择数据点k作为聚类中心的合适程度。

Step3按公式(5)和公式(6)迭代更新r(i,k)、a(i,k)：

(5)

(6)

Step4经过若干次迭代后，对数据点的吸引度和归属度进行求和，确定数据点的聚类中心。当聚类中心保持不变或达到迭代次数时，算法结束。

2 基于改进聚类集成的蚁群算法

针对在求解大规模TSP问题时传统算法求解效率差、求解时间过长、误差率增大等问题，本文通过运用AP聚类，将一个大规模TSP问题(设城市数为n)分为若干个小规模的问题(设数量为m)，每个问题单独作为一个分组，然后，将每一个分组都作为一个独立的TSP问题，用蚁群算法求解它的最短路线。最后，为了缩短整个问题的路径长度，本文设计了一个改进的集成方案，以有效地将所有分组连接成一个整体。

2.1 大规模TSP问题的聚类

首先，根据TSP问题给定的坐标点，可以构建坐标点之间的相似度矩阵S(i,k)(见公式(4))，随后每个坐标点都作为聚类中心。之后在聚类的过程中以吸引度r(i,k)和归属度a(i,k)在各坐标点之间传递，吸引度r(i,k)表示坐标点k成为聚类中心的能力大小，归属度a(i,k)表示坐标点i对坐标点k作为聚类中心的合适程度。并通过迭代过程更新每个坐标点的吸引度和归属度。具体迭代公式见公式(5)和公式(6)。

经过若干次迭代后，综合吸引度与归属度的值，取r(i,j)+a(i,j)的最大值时，对应的坐标点k为i的聚类中心。在聚类中心不变或达到一定迭代次数时，算法结束，得到划分后的若干个簇。

2.2 子问题的求解

通过AP聚类将大规模TSP问题分为m个子问题后，为得到m个子问题连接成一个整体的最短路径，需要得到每个子问题的最优路径。本文运用蚁群算法对每个分组的给定节点(即城市点)进行路径寻优，得到该子问题的最优路径。每个子问题运用蚁群算法的过程如下：

Step1输入子问题。

Step2为每个节点相互之间的距离建立一个距离矩阵。

Step3为每个节点之间建立一个信息素矩阵。

Step4设有n只蚂蚁，每一只蚂蚁随机选择一个节点，作为自己的起点。

Step5计算每只蚂蚁向不同的节点移动的概率。

Step6每只蚂蚁根据概率，通过轮盘法向下一个城市行动。

Step7回到Step5，直到所有的节点都被走遍。

Step8挥发信息素。

Step9根据蚂蚁走过的节点和路径长度，更新信息素表。

Step10回到Step4，直到迭代结束。

Step11迭代结束，给定最优路径。

2.3 改进后的集成方案

在上文的步骤中，是通过比较欧氏距离来确定删除的路径和新路径，但可能由于部分节点分布的特殊性，导致集成后端口附近出现路径与路径的交叉问题，如图1所示。

图1 可能存在的交叉问题

当聚类算法划分出很多子问题时，这类交叉必然会导致全局最优解的精度大幅度降低，所以必须对路径进行进一步的优化。若是为此在集成完成后对路径进行全局搜索，虽然可以找到并解开交叉，但必然会耗费大量的时间。因此，本文为该集成方案引入局部路径优化算子，以达到找到并且解开交叉的同时又花费较少的时间。

假设A组与B组路径连接，所需要删除的路径是A组中i与i+1之间的路径和B组中j与j+1之间的路径。研究发现，导致交叉的4个节点位置必然存在于(i-1，i，i+1，i+2，j-1，j，j+1，j+2)之中，那么，只要在此范围内判断出现交叉的位置，即可大幅度减少搜索交叉的时间。本文根据此构想，设计了局部路径优化算子，具体实现步骤如下：

Step1判断上文8个节点中所有可能形成的2条路径之间是否存在交叉，具体方案如下：

1)设2条路径分别为AB、CD，判断以AB为对角线形成的矩形和以CD为对角线形成的矩形是否有重合的部分(见图2)。

图2 2个矩形是否有重合部分

即判断以下式子是否成立：

min (Ax,Bx)max (Dx,Cx)&min (Cx,Dx)max (Ax,Bx)

min (Ay,By)max (Dy,Cy)&min (Cy,Dy)max (Ay,By)

(7)

2)若满足以上要求，则判断路径AB的2个节点是否分布在路径CD的2侧，具体方案如下：引入平面向量，若相关向量满足以下公式：

(8)

则路径AB的2个节点必定分布在路径CD的2侧。

3)当以上2个条件均满足时，即可判断路径AB与CD之间存在交叉。

Step2若AB与CD之间存在交叉，即可删去路径AB和路径CD，建立新路径AD、BC，如图3所示。

图3 优化后的新路径

Step3完成局部路径优化。

最后，经过改进后的集成方案的效果如图4所示。

图4 解开交叉后的路径效果图

从图4可明显看出，通过设计局部路径优化算子，本文算法以极少的时间成本解决了图1中的交叉问题，找到了更优的路径方案。

最后，基于改进聚类集成的蚁群算法过程如下：

Step1输入大规模TSP问题。

Step2运用AP聚类将大规模TSP问题分为m个子问题。

Step3每个子问题用蚁群算法进行寻优，得到最优子路径。

Step4利用蚁群算法对聚类中心点的寻优找到最佳组合序列。

Step5将所有的最优子路径根据最佳组合序列进行组合。

Step6组合的过程中用局部路径优化算子解决可能存在的交叉问题。

Step7所有子路径组合完毕，输出整体最优路径。

3 实验结果与分析

本文的实验仿真环境是在Window 10系统Core i5的环境下进行，测试平台为MATLAB R017b。在实验中ACA、APACA、IACA蚁群算法均设置蚂蚁数为2/3的城市数目，信息启发式因子α均为1，期望启发式因子β均为5，信息素挥发系数ρ为0.5，信息素总量Q为100。本文使用的数据均来自于TSPLIB标准库中的测试数据，每组实验均测试10次，为公平起见，每种算法在连续5次迭代过程中结果不变化时立即输出路径长度以及所需时间。

3.1 小规模城市下ACA算法的优越性

设置PSO中个体经验保留率和全局经验保留率为0.8，粒子数为40。GA中初始种群大小为200，交叉概率和变异概率为0.8。结果如表1所示。

表1 ACA、PSO及GA小规模城市仿真结果

TSP问题ACAPSOGA平均值/m最优值/m时间/s平均值/m最优值/m时间/s平均值/m最优值/m时间/sBays29931792733.517286165871198019944474ch3115647156024.630383295671215993157205eil5145444619121811662051247813Berlin52771376812021987210382193308596615pr76119771190964453194438631313132520458gr96548543131270726404119101761115

如表1所示，ACA算法相比于PSO算法在TSP问题的解决上具有压倒性的优势。相比较于GA算法，ACA算法在速度上略低于GA算法，但其在鲁棒性和求解质量上明显优于GA算法，尤其在城市数大于50的测试数据中。因此本文在选择算法求子路径回路时，选择了ACA算法。

3.2 验证IAPACA算法可以更有效求解大规模TSP问题

表2 ACA与GA仿真结果

TSP问题已知最优解ACAGAAPACAIAPACA最小值/m平均值/m偏差率/%时间花费/s最小值/m平均值/m偏差率/%时间花费/s最小值/m平均值/m偏差率/%时间花费/s最小值/m平均值/m偏差率/%时间花费/sKroA1002128221887223262.819.107021956225643.115.3482442224994.514.75.86312346623727.210.36.0937a28025793149.53280.722.1494.18702990.03005.816.3101.532979.73067.7215.512.4582929.92992.5613.615.505rat7838806118461190834.515965117531250833.419569839.59849.211.727.0639766.3980810.931.470dsj10001.86×10721163000213300012.825711288670002895000055.230283209100002122850012.190.477208720002111710011.893.523u215264253————————————————————————734837463814.4168.873731987435213.8176.231pcb3038137694————————————————————————15419015474811.9252.35921451301531985.4255.7424

偏差率的计算公式为：

通过表2的实验结果可以看到，在求解KroA100这种小规模TSP问题时，ACA及GA算法的求解时间较短，所得结果精度良好，然而随着问题的规模逐渐增大，它们的求解质量开始大幅度下降。比如在解决a280、rat783、dsj1000问题时，花费的时间大幅度增加，偏差率也随之增大，显然不能满足求解需求，而APACA以及IAPACA的最小值、偏差率和平均值均优于ACA，且大大降低了时间的成本。之后随着问题的规模再逐渐增大，这些不足也被随之放大。故在解决大规模TSP问题时，本文又设计了改进的集成方案，从实验结果可看出，IAPACA的平均值和最小值的偏差均优于APACA，有效证明了通过对集成方案的改进，提升了所得结果的精度，验证了IAPACA在求解精度与求解时间上做到了很好的权衡，相比ACA、GA、IAPACA既大幅度减小了求解时间，又保证了求解精度。

最后，本文绘制了部分问题的路径图，因篇幅限制，图5仅显示dsj1000、u2152的测试结果。

(a) dsj1000

4 结束语

随着TSP问题的规模逐渐增大，蚁群算法的求解质量会大幅度下降，求解时间指数增长，误差率增大。本文设计了基于聚类集成的蚁群算法的大规模TSP问题解决方案，运用AP聚类将大规模TSP问题分为若干子问题，用蚁群算法对每个子问题进行路径寻优，得到每个子问题的路径方案。最后，为了提高最终结果的精度，用一种改进的集成方案对所有子问题的路径方案进行组合，得到大规模TSP问题的解。实验结果表明，在求解大规模TSP问题时，IAPACA相对ACA，不仅大幅度缩短了花费时间，而且减小了求解问题的误差率。故本文设计的基于改进聚类集成的蚁群算法在求解大规模TSP问题具有优秀的性能。