一种基于分层模型的TSP构建算法*
2017-04-13宋海声吕耕耕刘岸果
宋海声，吕耕耕，刘岸果
(西北师范大学 物理与电子工程学院，甘肃 兰州 730070)
一种基于分层模型的TSP构建算法*
宋海声，吕耕耕，刘岸果
(西北师范大学 物理与电子工程学院，甘肃 兰州 730070)
提出了一种新算法，有效地减少了最近邻域法和贪婪算法在构建旅行商问题可行解过程中引入不合理长边的问题。该算法先借助一种由伪凸包算子所得到的分层模型对旅行商问题中的城市分布进行分析，之后通过将分层模型中相对外层的点逐个添加到内层的规则得到可行解。借助仿真实验求解TSPLIB标准库中的40实例，并与最近邻域法和贪婪算法进行对比，结果表明分层融合算法具有更高的精度，其平均求解质量达到8.47%。
旅行商问题；伪凸包；分层模型；分层融合算法
0 引言
旅行商问题(Traveling Salesman Problem, TSP)是在1954年由美国学者Dantzig[1]提出的，是已被证明的NP-Hard组合优化问题[2]。由于其在邮递员投递路线选择、生产作业排序VLSI芯片设计、电路板钻孔、机器人控制、X光设备定位、电子地图和计算机网络等众多领域有广泛应用价值，因此近些年来产生了大量的关于TSP的文献。其中大多数文献主要集中于启发式算法的研究，可以分为构建型和以构建型为基础的改进型两类。比较常见的改进型算法有遗传算法[3]、蚁群算法[4]、粒子群算法[5]、免疫算法[6]、模拟退火算法[7]、禁忌搜索算法[8]等，其求解质量高，速度比较慢；而构建型算法具有简洁、求解速度快的特点。经典的构建算法有最近邻域法(the Nearest Neighborhood Algorithm, NN)[9]、贪婪算法(Greedy Algorithm, GA)[10]、插入法[9]等。
由于最近邻域法、贪婪算法和插入算法的构建结果中均含有不合理的长边，因此本文在继承最近邻域法、贪婪算法的思想后，通过建立分层模型来规避这一问题，提出了分层融合算法(Hierarchical Fusion Algorithm, HFA)。通过实验求解TSPLIB标准库中的40实例并与NN和GA算法进行对比，结果表明本文算法求解TSP具有更高的精度。
1 TSP的描述
TSP可以描述为：在目标城市个数和任意两城市之间距离都已知的情况下，求解一条遍历所有城市一次且仅一次并返回到起点城市的最短线路。该问题可以用如下的数学模型描述：
设N表示城市个数，D表示距离矩阵，dij表示两城市间的距离，Inf为一足够大的正数,i，j为下标表示城市，Tour表示线路的集合,Tp(l)表示线路Tp中的第l个城市，Len(Tp)为线路Tp总长度，那么有：
(1)
(2)
(3)
显然，使得Len(Tp)取得最小值的线路Tp就是TSP的最优解。根据不同的划分标准TSP大致可以分为三类：
(1)按距离矩阵是否为对称矩阵，分为对称TSP和非对称TSP；
(2)按任意3个城市间距离值是否满足三角不等式，分为三角不等式TSP和非三角不等式TSP；
(3)按城市的坐标位置是否完全符合欧几里得平面规则(两城市之间的距离可以通过坐标计算得出)，分为欧几里得TSP和非欧几里得TSP。本文在未加声明时的TSP均为欧几里得TSP。
2 分层融合算法
2.1 分层模型
分层模型是指将问题的处理过程分解为多个具有结构相似性或功能独立性的过程。建立分层模型可以让问题的描述变得简单，并使得问题的求解过程更具条理性。本文针对TSP建立分层模型并提出以下假设：
(1)使用坐标点表示城市的位置，且所有的城市都分布在二维平面上；
(2)不存在具有相同坐标的两个点，若坐标相同则按一个点处理；
(3)任意一个点，不能同时出现在两个不同的层中；
(4)各个层必须采用相同的方式得到。
2.2 伪凸包算子
本文采用伪凸包算子得到的伪凸包结构进行分层模型的建立，其步骤如下：
(1)找出剩余城市的坐标矩阵tempX和剩余城市的个数ccity，按照剩余城市的横坐标从小到大的排序得到剩余城市在横坐标方向的排序xsq；
(2)当ccity<4时，返回xsq和ccity,否则，执行步骤(3)；
(3)按照剩余城市的纵坐标从小到大地排序得到剩余城市在纵坐标方向的排序ysq并取得端点西west=xsq(1)，东east=xsq(ccity)，南south=ysq(1)，北north=ysq(ccity)；
(4)初始化层layer=zero(1,N),层中城市个数cl=0；
(5)从西到北取得纵坐标增大的点并添加到layer中，更新cl；
(6)从东到北取得纵坐标增大的点并反向添加到layer中，更新cl；
(7)从东到南添加纵坐标减小且未曾添加到layer中的点到layer中，更新cl；
(8)从西到南取得纵坐标增大且未曾添加到layer中的点并反向添加到layer中，更新cl，返回layer和cl。
图1是TSPLIB标准库中att48城市的分布图。图2为分层模型所得到的att48城市分层图，其中每一条多段线表示一个层。
图1 att48城市的分布图
图2 att48城市的分层图
2.3 分层融合算法求解TSP
本文提出的分层融合算法建立在分层模型基础之上，采用伪凸包算子得到TSP的分层模型，之后将分层模型中相对外层的城市加入到相对内层的层中完成融合。其中融合过程只限于两层之间并且是从最内层向最外层进行的。分层融合算法求解TSP的过程可以分为两个阶段：第一阶段使用伪凸包算子进行分层模型的构建；第二阶段将得到的分层模型按照融合规则进行融合求出构造解。
第一阶段：得到分层模型。
(1)初始化城市个数N，剩余城市的集合CITY=1:N，剩余城市个数ccity=N，城市坐标矩阵X。
(2)如果ccity>0，创建层记录矩阵xLayers=zeros(ccity,N)并令层个数clayers=0，跳到步骤(3)；否则，提示错误。
(3)当ccity>0时，重复执行步骤(4)；否则返回分层模型矩阵Layers=xLayers(1:clayers,:)。
(4)采用伪凸包算子得到一层，更新剩余城市的集合CITY，ccity，clayers++。
第二阶段：对分层模型进行融合。
(1)初始化得到第一阶段所生成的分层模型矩阵Layers和层个数clayers。
(2)当clayers>1时；重复执行步骤(3)；否则，返回Layers(1,:)。
(3)分取得相对内层inlayer=Layers(clayer,:)和相对外层outlayer=Layers(clayer-1,:)，利用融合规则算子将两层融合并将得到的结果赋给Layers(clayer-1,:)。
其中步骤(3)中所用到的融合规则算子详细步骤如下：
①取得相对内层inlayer、相对外层outlayer、outlayer中城市的个数coutlayer以及inlayer中城市的个数cinlayer。
②当coutlayer>0时，重复执行步骤②；否则，返回inlayer。
③随机从outlayer中选择一个点作为将要添加的点addpoint。
④当cinlayer<3时，neighbourhood=inlayer;否则，从inlayer中选择2个距离addpoint最近的点的集合作为neighbourhood。
⑤计算addpoint分别插入到neighbourhood中两点两侧时的距离增量，将addpoint插入到距离增量最小的位置，coutlayer--，更新inlayer。
3 算法测试
实验求解了TSPLIB标准库中的40个实例，通过比较NN、GA与HFA三种算法的求解质量，对算法的性能进行了测试。实验平台为MATLAB 7.10.0(R2010a)，CPU为AMD A8-3500M，内存为2.0 GB，主频为1.5 GHz。三种算法求解TSP实例的结果对比表如表1所示。其中实例名称指的是TSP的名称和该问题所包含的城市个数；最优路径长度指的是实例已知的最优路径长度；平均解和最优解分别指的是平均求解质量和最优求解质量，计算方法为：(解得路径长度/最优路径长度-1)*100%。需要注意的是，GA为确定算法，每次求出的结果都相同，所以只求解一次；而NN和HFA为不确定算法，所以进行了多次实验。当城市个数n≤100时，进行n次求解；当100
由表1可知，在求解质量上NN的平均求解质量最差，为26.02%；NN的最优求解质量和GA的求解质量相当，为18%左右；本文提出的分层融合算法求解质量明显优于NN和GA。其平均求解质量和平均最优求解质量的均值分别为8.47%和4.99%，说明算法的鲁棒性和求解质量同时得到提高，相对于GR+MVODM的性能更好[11]。
4 结论
本文针对旅行商问题提出了分层融合算法，借助分层模型从整体入手有效避免了经典构造算法后期引入长边的问题，从新的方向给出了旅行商问题构造解方式。该算法的优点在于求解质量高，建立了可重复使用的分层模型；不足之处在于伪凸包算子构建的层模型过于单一，各层之间进行融合时邻域制约了构造解的多样性。
表1 三种算法求解TSP实例的结果对比表
[1] DANTZIG G, JOHNSON S. Solution of a large-scale traveling-salesman problem[J]. Operations Research, 1954, 2(4):393-410.
[2] GAREY M R, JOHNSON D S. Computers and intractability: a guide to the theory of NP-completeness[M].W.H. Freeman and Company， 1979.
[3] 刘荷花, 崔超, 陈晶. 一种改进的遗传算法求解旅行商问题[J]. 北京理工大学学报, 2013, 33(4):390-393.
[4] 吴华锋, 陈信强, 毛奇凰,等. 基于自然选择策略的蚁群算法求解TSP问题[J]. 通信学报, 2013, 34(4):165-170.
[5] 钟一文, 杨建刚, 宁正元. 求解TSP问题的离散粒子群优化算法[J]. 系统工程理论与实践, 2006, 26(6):88-94.
[6] 吴建辉, 章兢, 张小刚,等. 一种求解TSP问题的分层免疫算法[J]. 计算机科学, 2010, 37(6):256-260.
[7] 乔彦平, 张骏. 基于一种改进遗传模拟退火算法的TSP求解[J]. 计算机仿真, 2009, 26(5):205-208.
[8] GLOVER F, MARTI R. Tabu search[M]. Metaheuristic Procedures for Training Neutral Networks, Springer US, 2006.
[9] 饶卫振, 金淳, 黄英艺. 求解TSP问题的最近邻域与插入混合算法[J]. 系统工程理论与实践, 2011, 31(8):1419-1428.
[10] VINCE A. A framework for the greedy algorithm[J]. Discrete Applied Mathematics, 2001, 121(1-3):247-260.
[11] 饶卫振, 王新华, 金淳, 等.一类求解TSP构建型算法的通用改进策略[J].中国科学信息科学, 2015, 45(8):1060-1079.
A construction algorithm for TSP based on hierarchical model
Song Haisheng，Lv Genggeng，Liu Anguo
(School of Physics and Electronic, Northwest Normal University, Lanzhou 730070, China)
This paper proposes a new algorithm for making a feasible solution of traveling salesman problem, which availably reduces unreasonable long sides introduced in nearest neighborhood algorithm and greedy algorithm. With the hierarchical model formed from pseudo convex hull algorithm, the algorithm, at first, analyzes the city distribution of traveling salesman problem and then a feasible solution can be found by inserting the point in the relatively outside layer to the relatively inside layer one by one. We use 40 examples from TSPLIB to test the algorithm and contrast it with the nearest neighborhood algorithm and greedy algorithm. The result shows that hierarchical fusion algorithm has a better result with the average solution quality of 8.47%.
traveling salesman problem; pseudo convex hull; hierarchical model; hierarchical fusion algorithm
甘肃省自然科学基金(1606RJZA065)
TP301.6
A
10.19358/j.issn.1674- 7720.2017.06.005
宋海声，吕耕耕，刘岸果. 一种基于分层模型的TSP构建算法[J].微型机与应用，2017,36(6)：13-15，21.
2016-10-26)
宋海声(1964-)，男，副教授，主要研究方向：计算机测量与控制。
吕耕耕(1992-)，男，硕士研究生，主要研究方向：智能算法、嵌入式系统。
刘岸果(1972-)，男，硕士研究生，主要研究方向：物联网。
