聚类处理的蚁群算法在旅行商问题中的应用

2015-12-09孟喜艳傅文灵

湖北民族大学学报(自然科学版) 2015年1期

孟喜艳，傅文灵，马波，方壮

(1．恩施职业技术学院人文科学系，湖北恩施445000;2．湖北民族学院理学院，湖北恩施445000)

旅行商问题(Traveling Saleman Problem，TSP)是指已知n个城市的两两距离，商人从自己所处的城市出发，确定一条访遍各个城市顾客一次且仅一次的最短路径问题．若将城市记为顶点集V={v1，v2，…，vn}，相连接顶点vi与vj组成的边eij构成集合记为边集E，相连接顶点vi与vj之间的距离dij构成的距离矩阵记为D，TSP 问题的图论描述即为:在图G=(v，e)中确定一条长度最短的Hamilton 回路．

TSP 是一个NP 完全难题，很多典型的组合优化问题如芯片加工问题、电路板设计中的钻孔问题、航迹规划等，最终都可归结为TSP 问题．因此快速、有效地解决TSP 有着重要的理论价值和极高的实际应用价值．相对于传统算法，蚁群算法［1］自1991 年Dorigo 提出后，就成功应用到TSP 问题，并吸引了很多学者对其进行研究．黄翰等［2］分析了蚁群算法的收敛速度;徐红梅等［3］分析了参数的初始设置对蚁群算法的影响;冀俊忠［4－5］、李成兵［6］、吴华峰［7］、梁志茂等［8］通过修正信息素更新方式，对蚁群算法进行了改进;胡俊鹏［9］研究了双向选择相遇算法，提高了搜索速度;怀丽波等［10］讨论了蚁群算法在其他优化方面的应用．春花等［11］研究了蚁群算法参数的设置;孙凯等［12］还将蚁群算法与其它优化算法相融合，提高了部分TSP 问题的求解精度．

对于大规模的TSP，蚁群算法容易陷入局部最优．考虑到旅行商问题的实际背景，商人访问一个城市群中的每一个城市后，再访问下一个城市群是合理的，为此，先将所有城市聚类成若干城市群后，在每一个城市群内求解TSP 子问题，然后选择合适的城市群之间的连接线路，使总的的连接路线最短，这样可以降低算法的复杂度，最终得到所有城市最佳巡游路线的一个满意解．依据这一思想，卢欣［13］对这一算法的复杂度进行了分析;丁建立［14］以pcb442 问题为例，通过动态聚类结合蚁群优化算法得到了该问题的一个近似解，冀俊忠［4］、侯文静［15］、任志刚等［16］通过不同的类与类之间连接方式结合蚁群算法，得到了大规模TSP 的近似解．通过聚类的方法求解TSP 问题，其准确性依赖于各城市群建的连接顺序，这样，如何从已有的分类及连接顺序中找到一个满意的巡游圈，就是一个值得研究的问题，本文通过蚁群算法确定了城市群的连接顺序，并在此顺序下，通过标记城市群接入点的方式，以TSP 问题测试库中的Pr152 数据为例，得到了一个最佳巡游圈的满意解．

1 算法基本思想

如图1 示，将所有城市聚类，图1 所示聚成4 个城市群，在每一城市群中用蚁群算法求解其最佳巡游圈，并求出城市群的连接顺序，图1 中每一类的最佳巡游圈如黑色线条所示，城市群的连接顺序为G1→G2→G3→G4→G1．任给一点P1∈G1，在下一个城市群G2找到距P1离最短的点P2，将P2标记为G2的接入点，P'2，P″2为P2在G2中巡游圈中的邻接点;在第三个城市群G3中找到距P'2，P″2最短的点P'G3，P″G3，并分别求其距离DP'2P'G3，DP″2P″G3，计算DP'2P'G3－w'2，DP″2P″G3－w″2，比较两者中的最小值，将最小值对应的在G3中的点记为P3，P3作为G3城市群的接入点，P'3，P″3为P3在G3城市群中巡游圈中的邻接点;

按此方法依次经行下去，当同一个点有两次标记为接入点时，输出一个巡游圈，更新P1．寻找下一个巡游圈，当P1遍历完第一个城市群中的每一个点时，结束循环．将巡游圈距离最小者作为输出．

图1 算法示意图Fig．1 Schematic algorithm

2 聚类分析的蚁群算法

2．1 聚类分析

在上节中，首先要对所有城市进行聚类．本文采用的是谱系聚类以城市点间的欧氏距离来进行分类，谱系聚类是对统计样本进行定量分析的一种多元统计分析法，该方法是对待处理样本进行依次归类，然后由聚类的方法得到一个二叉树聚类图．观测点之间的距离能够用欧氏距离或欧氏距离的平方来计算，而类间聚类的计算方法有多种，这里计算类间距离的方法是Ward 最小方差法:若现在有n个观测数，v个变量数，G为分类的个数，xi为i个观测，CK是当前水平G的第K类，NK为CK中的观测个数，均值向量为，类CK中的均值向量(中心)为为欧氏长度是总离差平方和，是类CK的类内离差平方和，PG=ΣWJ为聚类水平G对应的各类的类内离差平方和的总和．假设某一步聚类过程中把类CK和类CL合并为下一水平的类CM，那么定义BKL=WM－WK－WL为合并导致的类内离差平方和的增量．用d(x，y)来表示两个观测点之间的距离或非相似性测度，DKL是第G水平的类CK和类CL之间的距离或非相似性测度．采用Ward 最小方差法时

当观测距离为d(X，Y)=‖X－Y‖2/2 时递推公式为:

2．2 基本蚁群优化算法

设C表示观测点的集合，bi(t)表示t时刻位于城市点i的蚂蚁数目，τij(t)为t时刻路径(i，j)上的信息量，m为蚁群中蚂蚁的总数目，n表示TSP 规模，则是t时刻集合C中所有城市点任意两个城市点间残留信息素量的集合，设定在最开始时刻每条路径上的存储信息量相等，设定τij(0)=const．因为任意蚂蚁k在遍历过程中不能重复经过同一个城市，建立禁忌表tabuk(k=1，2，…，11)来记录蚂蚁已经过的城市，禁忌表随着蚂蚁的运动做动态变化．搜索过程中，每只蚂蚁根据每条路径上的信息量及路径本身的启发信息来计算状态转移概率，建立蚂蚁k由i城市转移到j城市的状态转移概率如下［16］:

其中:ηij表示从i到j的期望程度，一般认为从i到j的距离的倒数即ηij=1/dij，成为启发函数;α 为信息启发式因子，表示路径的相对重要性，反映了蚂蚁在搜索路径过程中所积累的信息量在蚂蚁运动中所起的作用，其值越大，那么其它蚂蚁走过的路径就更容易被后续蚂蚁选择，蚂蚁之间的相互协作性也就越强;β 为期望启发式因子，反映了蚂蚁在搜索路径过程中启发信息在蚂蚁选择路径中所受到重视程度，其值越大，则该状态转移概率就会越接近贪心规则，越倾向于最优路径;pkij(t)表示信息素较多且距离较短的路径被选中的概率越大．

引入信息素在算法中的全局更新规则:当全部蚂蚁完成一次游历后，在其走过的路径上留下一定量的信息素，从而改变信息素，则t+n时刻的信息素修改公式:

其中:ρ 表示信息素挥发系数，则1－ρ 表示信息素的持久性系数，ρ∈［0，1);初始时刻)表示第k只蚂蚁在本次迭代中留在边eij上信息素量，若蚂蚁k没有经过eij，则的值为零，所以将表示为:

其中:Q表示信息素强度;Ck表示第k只蚂蚁在本次周游中所走过的路径长度．

信息素局部更新规则:在路径构建过程中，对每只蚂蚁，每当其经过一条eij时，它将立刻对这条边进行信息素的更新:

其中:ξ 是信息素局部挥发速率，满足0 ＜ξ ＜1;τ0是信息素的初始值．

在算法的构建过程中，信息启发式因子α 和期望值启发式因子β 对算法性能的影响和作用是相互配合、密切相关的，要得到好的优化结果必须适当的选择α 和β 的取值范围一般的选取范围为α=0．5～5，β =1～5．研究表明信息素的持久性系数1－ρ 关系到蚁群算法的全局搜索能力及收敛速度，系数过大则以前搜索过的路径被再次选择的可能性过大，也会影响到算法的随机性能和全局搜索能力，反之减少系数虽可以提高算法的随机性能和全局搜索能力但又会使得算法的收敛速度降低，因此在信息素的持久性系数选择的时候要对全局搜索能力和收敛速度两方面做出合理折中的选择．

在TSP 测试库中以Oliver30(问题规模30)数据为例，设定参数:α =1，β =5，ρ =0．1，Q=100，最大迭代次数为200 次，计算得到图2 所示结果．

由图2 可知蚁群优化算法在解决TSP 上能较快得到可行解，结果也较为理想，但随着问题规模的增加，算法的计算复杂度也在增加，收敛速度变慢，极有可能陷入局部最优解，例如取测试库中的pr107(问题规模107)测试时，得到如图3 所示的结果．

图2 Oliver30 的TSP 最短路径及收敛分析Fig．2 The shortest route and the convergence analysis of Oliver 30

图3 Pr107 的TSP 最短路径及收敛分析Fig．3 The shortest route and the convergence analysis of Pro107

图3 所示，按收敛分析显示最短路径已收敛到最优解，但从其结果明显可看出此结果并非最优． Pr107问题的最优解为44303，而图3 所示的路径的最优解为45845．大量的实验显示ACO 算法因为其本身的鲁棒性、自学习能力强能特点能有效解决小规模TSP 问题，但随着问题的规模变大、复杂度增加，迭代次数也要增加，时间花费变大且不能得到全局最优解．

2．3 基于聚类处理蚁群算法的步骤

针对单纯的ACO 算法已不能完全解决大规模TSP 问题，为了能有效求得可行解并求解过程中提高求解速度，因此在ACO 算法的基础上加入聚类处理，通过聚类分析，将相似性大的城市点聚为一类，相似性小的分开，每个小类可做一次TSP 子问题求解，然后将每个类作为一个城市点，再进行一次求解，最后即可合成所需问题的可行解．如此一来，既保留了算法的特点，同时也提高了算法的求解速度，可避免出现局部最优现象．其基本步骤如下:

1)对所有城市进行聚类．得到若干个城市群G1，G2，…，Gk;

2)利用蚁群算法，求每一个城市群的最佳巡游圈CG1，CG2，…，CGk．并求每一类城市的聚类中心;

3)确定聚类中心的连接顺序，并将其作为城市群的连接顺序，不妨设其顺序就为G1，G2，…，Gk;

4)确定城市群的接入点．任给Pi∈Gi，在Gi+1中确定到Pi距离最短的点Pi+1，将Pi+1标记为Gi+1的接入点，P'i+1，P″i+1为Pi+1在第二类中巡游圈中的邻接点;在Gi+2中确定到P'i+1，P″i+1距离最短的点P'Gi+2，P″Gi+2，并分别求其距离DP'i+1P'Gi+2，DP″i+1P″Gi+2，计算DP'i+1P'Gi+2－w'i+1，DP″i+1P″Gi+2－w″i+1，比较两者中的最小值，将最小值对应的在Gi+2中的点记为Pi+2，Pi+2作为Gi+2的接入点，P'i+2，P″i+2为Pi+2在Gi+2中巡游圈中的邻接点;按此方法依次经行下去，当同一个点有两次标记为接入点时，输出一个巡游圈，更新Pi及接入城市标志．寻找下一个巡游圈，当Pi遍历完Gi中的每一个点时，结束循环．将巡游圈距离最小者作为输出．

3 实验结果及分析

同样的设定参数α=1，β=5，ρ=0．1，Q=100，最大迭代次数为500 次，分成30 个城市群，以测试数据库中的Pr152 为例，计算得到如图4 所示，其可行解为73 683 与其最优解73 682 的误差不超过0．001 5%．

图4 本文算法处理Pr152 所得结果Fig．4 The processing result of pr152

4 结论

本文所提出的在ACO 蚁群优化算法的基础上加入聚类的处理，对大规模的TSP 问题进行分解，大大降低了问题的难度系数，也减小了问题的复杂度，同时也保留了算法的求解特点．在聚类的基础上，问题被细化，算法求解速度得到提高，避免了算法本身易陷入停滞现象的局限性，但此方法也会因聚类的方法不一样而得到不一样的结果，同时还会因城市点间的相似程度而影响聚类结果，所以对于这类的大规模TSP 问题的求解还需具体考虑到实际问题，从实际出发才能更好的解决问题．

［1］ Colorni A，Dorigo M，Maniezzo V．Distributed optimization by ant colonies． Proceeding of the 1st European Conference on Arificial Life［C］//Paris，France:Elsevier Publishing，1991:134－142．

［2］黄翰，郝志峰，吴春国，等．蚁群算法的收敛速度分析［J］．计算机学报，2007(8):1344－1353．

［3］徐红梅，陈义保，刘加光，等．蚁群算法中参数设置的研究［J］．山东理工大学学报:自然科学版，2008(1):7－11．

［4］冀俊忠，黄振，刘椿年．基于聚类和分段优化的蚁群算法［J］．北京工业大学学报，2008(4):434－440．

［5］冀俊忠，黄振，刘椿年．一种快速求解旅行商问题的蚁群算法［J］．计算机研究与发展，2009(6):968－978．

［6］李成兵，郭瑞雪，李敏．改进蚁群算法在旅行商问题中的应用［J］．计算机应用，2014(S1):131－132．

［7］吴华锋，陈信强，毛奇凰，等．基于自然选择策略的蚁群算法求解TSP 问题［J］．通信学报，2013(4):165－170．

［8］梁志茂，腾建华，何晋．基于改进蚁群算法的TSP 问题研究［J］．云南民族大学学报:自然科学版，2010，19(3):220－223．

［9］胡俊鹏．基于双向选择的蚁群相遇算法的优化［J］．湖北民族学院学报:自然科学版，2013，31(1):60－64．

［10］怀丽波，崔某一，赵在慧．基于改进的蚁群算法的教室管理的优化问题［J］．延边大学学报:自然科学版，2014，40(4):335－339．

［11］春花，特日格勒，任哲明．关于蚁群算法参数的设定［J］．内蒙古民族大学学报:自然科学版，2011，26(4):402－404．

［12］孙凯，吴红星，王浩，等．蚁群与粒子群混合算法求解TSP 问题［J］．计算机工程与应用，2012(34):60－63．

［13］卢欣，李衍达．TSP 问题分层求解算法的复杂度研究［J］．自动化学报，1999(2):139－142．