引用本文
申铉京, 刘阳阳, 黄永平, 徐 铁 等. 求解TSP问题的快速蚁群算法[J]. 吉林大学学报(工学版), 2013, 43(1): 147-151[SHEN Xuan-jing, LIU Yang-yang, HUANG Yong-ping, XU Tie et al. Fast ant colony algorithm for solving traveling salesman problem[J]. Journal of Jilin University Engineering and Technology Edition, 2013, 43(1): 147-151]  
Permissions
求解TSP问题的快速蚁群算法
申铉京1,2, 刘阳阳1,2, 黄永平1,2, 徐 铁3, 何习文1
1.吉林大学 计算机科学与技术学院,长春 130012
2.吉林大学 符号计算与知识工程教育部重点实验室,长春 130012
3.吉林石油集团有限责任公司 洮河农场,吉林 松原 138000
基金:吉林省自然科学基金项目(201115025);符号计算与知识工程教育部重点实验室开放基金项目(450060445325);吉林大学研究生创新基金项目(20111063);吉林大学“大学生创新性实验计划”项目(2011A53100)
摘要
针对蚁群算法求解旅行商问题时存在收敛速度慢并容易陷入局部最优的问题,提出了一种改进的蚁群算法。改进算法采用信息素挥发因子自适应调整机制,调节算法收敛速度,保证算法的全局搜索能力。同时根据公共路径降低蚁群算法运算时间,诱导蚁群寻找更优解。实验结果表明,改进算法在迭代次数相对较少的情况下求得的平均解与已知最优解偏差为0.46%,最优解与已知最优解偏差为0.23%,在收敛速度及求解精度上均取到了较好的效果。
关键词: 人工智能; 蚁群算法; 公共路径; 自适应; 旅行商问题
Fast ant colony algorithm for solving traveling salesman problem
SHEN Xuan-jing1,2, LIU Yang-yang1,2, HUANG Yong-ping1,2, XU Tie3, He Xi-wen1
1.College of Computer Science and Technology, Jilin University, Changchun 130012, China
2.Key Laboratory of Symbolic Computation and Knowledge Engineering of Ministry of Education, Jilin University, Changchun 130012, China
3.Taohe Farm, Jilin Oil Refco Group Ltd, Songyuan 138000,China
Abstract
Using ant colony algorithm to solve Traveling Salesman Problem (TSP) has certain disadvantages, such plunging into local minimum, slower convergence speed and so on. In order to find the optimal path accurately and rapidly, an improved ant colony algorithm is proposed. The improved algorithm uses adaptive adjusting mechanism of pheromone decay parameter to adjust the convergence speed and ensure the global search ability. With the help of common path, the computation time is reduced and the better solution can be obtained. Experiments show that, in a relatively few iterations, the percentage deviation of the average solution to the best known solution is 0.46%, and the percentage deviation of the best solution to the best known solution is 0.23%. The improved algorithm has high accuracy and convergence speed.
Keyword: artificial intelligence; ant colony algorithm; common path; adaptive; traveling salesman problem

TSP是著名的NP难问题,在电路板布局、VLSI芯片设计、车辆调度等组合优化问题中有着广泛的应用。蚁群算法是由意大利学者Dorigo等[1]首先提出的一种基于种群模拟进化智能启发式算法,并已经成功应用于TSP等多个NP难的组合优化问题求解,但基本蚁群算法也存在着易出现早熟、停滞的缺陷。针对蚁群算法的这些缺点,人们提出了许多改进的算法,如结合Q-Learning提出的Ant-Q算法[2]、MMAS算法[3],基于负反馈的蚁群算法[4]等。在逐渐认识到蚁群有组织、有分工的特性,人们又提出多态蚁群算法,在一定程度上改善了蚁群算法的性能,也是提高TSP求解效率的一个发展方向。但现有方法在收敛速度和求解精度上未达到一个很好的平衡。

本文算法通过采用信息素挥发因子自适应调整机制,保证算法的全局搜索能力,有效地避免算法陷入局部最优解。另外,通过加强公共路径的选择引导算法寻找更优路径,使得在算法停滞前易于发现更好的路径,并趋向最优路径解。该算法可以有效防止陷入局部最优解,同时提高收敛的速度。

1 算法策略
1.1 蚂蚁群体移动规则

该算法中,第k只蚂蚁由城市i选择到下一个城市j的规则是:.

当q≤q0时,

当q>q0时,蚂蚁根据转移概率公式(2)选择下一个点:

式中:q0是一个给定的位于(0,1)之间的常数;q是一个在(0,1)之间均匀分布的随机数;τiu(t)表示城市i和城市u之间路径上的信息素浓度;dij为两个城市之间的距离;信息启发式因子α反映蚂蚁在运动过程中所积累的信息量(即残留信息量τiu(t))在指导蚁群搜索中的相对重要程度;期望值启发式因子β反映蚂蚁在运动过程中启发信息(即期望值ηij)在指导蚁群搜索中的相对重要程度;allowedk表示第k只蚂蚁当前的可行点集。由式(1)和式(2)组成的转移规则称为伪随机规则,此规则倾向于选择短且信息素浓度大的边作为移动方向。

1.2 信息素自适应更新策略

每次搜索结束后,对每只蚂蚁的信息素按式(4)(5)(6)进行更新:

式中:m为蚂蚁总个数;ρ为信息挥发率;τij为蚂蚁在本次循环中留在路径(i,j)上的信息量;Δτij为本次循环中所有经历过路径(i,j)的蚂蚁留在该路径上的信息量的增量;Q为一个常数(表示蚂蚁循环一周所释放的总信息量);Lk为第k只蚂蚁在本次循环中所走路径的长度。这种信息更新规则正反馈性能强,能够提高系统收敛速度。

ρ反应整个蚁群系统的进化状态,它的大小直接关系到蚁群算法的全局搜索能力及收敛速度。当ρ过大时,也会影响到算法的随机性能和全局搜索能力;反之,通过减小信息素挥发度ρ虽然可以改善该问题,但又会使算法的收敛速度降低。

为了使蚁群始终能够在“探索”和“利用”之间保持平衡,使算法在具有较强的全局搜索能力的同时避免出现停滞状态,文献[5-[6]]都采用了不同的自适应调整方法动态调整ρ值,以提高算法全局搜索能力,快速收敛于较优解。本文的改进算法中选用简单而有效的自适应策略来调整ρ,其调整公式为

式中:ξ∈(0,1)为挥发因子调节系数;ρmin为ρ的最小值。算法初期赋予ρ较大的值,信息正反馈的作用占主导地位,以前搜索过的路径被选择的可能性较大,收敛速度比较快,但也很容易陷入局部最优解。后期逐渐降低ρ的值,信息正反馈的作用会逐渐减至较弱,那些从未被搜索到的路径信息素增大,搜索的随机性就增强,提高了全局搜索能力,但又会影响蚁群算法收敛速度。所以,为其设置一个最小值,防止了ρ过小而降低算法的收敛速度。通过对挥发系数这种自适应地改变,既可以提高解的全局性,又可以保证收敛的速度。

1.3 公共路径处理规则

上述自适应策略有效地提高了蚁群算法的全局搜索能力,使得算法能够较快地收敛到一些较优解,但从较优解到最佳解的进化所需时间较长,本文利用基于公共路径寻优的方法加快寻优速度。该方法是在文献[7]基础上提出的改进策略。文献[7]将数百次迭代后反复走过的路径设为必经过边,以降低算法的运算时间,但是蚁群算法容易陷入局部最优,最终所求得的可能为局部最优解,降低了算法的准确性。

根据该思想本文提出一种新的改进策略,将蚁群分为两组分别以不同的方法寻径。第一组按基本蚁群算法查找全局最优路径,第二组利用公共路径寻优。蚂蚁寻径时由于信息素的作用,一定会有一些较短并重复经过的路径段,出现如图1所示的情况,两只蚂蚁a1和a2会走过相同的路径段。但是,在改进算法中求解这种公共路径是有条件的,仅求取当前最优与次优解的公共路径,
这些公共路径有极大的可能是更优解路径或全局最优解的组成部分,为第二组蚂蚁提供了良好的寻径方向。另外,将当前公共路径保存在结构体中,第二组蚂蚁利用公共路径去寻优时,可减少算法求解的工作量,以牺牲一定空间复杂度的方式来换取更少的时间复杂度。在所有蚂蚁寻径结束后,统一修改信息素的值,供蚁群下一次寻径使用,更新当前最优与次优解。公共路径为算法在寻径过程中提供了良好的导向,使得在算法停滞前易于发现更好的路径,并逐渐趋向最优路径解,并可以减少大量的重复运算,提高算法收敛速度。算法的求解过程如图2所示。


图3为改进算法求解Eil51实例得到的路径图。图3(a)和(b)分别为第i次迭代得到的最优与次优路径,找到公共路径(见图3(c)),作为下一次迭代中第二组蚁群必经过的边。当求取了公共路径后,算法的后续运行实质上是从处于非公共路径的城市中构造一条最短路径将它们和公共路径相连组成一条回路,这样就避免了寻径过程中的许多重复运算,当算法迭代一定次数后,最优解与次优解的公共路径很有可能是实际最优解的组成部分,所以又给了算法一个良好的方向导向。使得在算法停滞前易于发现更好的路径。由图3(c)和(d)可以看到,改进算法最终找到了非常接近实际最优路径的解,而且这个解里包含了大部分的公共路径。

图1 一定迭代次数后出现的重复路径Fig.1 Repeated paths at a particular iteration
图2 一次迭代中的蚁群寻径流程图Fig.2 Flowchart of looking for paths in an iteration
图3 改进算法求得的路径Fig.3 Routes found by proposed algorithm
1.4 算法步骤

Step1 初始化:Nmax_A←蚁群算法允许迭代最大次数;m←蚂蚁个数;NA←1,蚁群算法迭代计数器;蚁群信息素τij←C;Δτij←0。

Step2 将蚁群分成两组,第一组按公式(1)和(2)进行状态转移,生成蚁群路径解。

Step3 更新最优和次优解,并找到最优解和次优解的公共路径。

Step4 第二组利用得到的公共路径寻径,将公共路径作为必经过的边,非公共路径上的城市按式(1)(2)进行状态转移与公共路径连成一条回路,生成蚁群路径解。

Step5 两组蚁群所得最优解如果小于当前最优解,更新最优和次优解,转Step7;如果大于当前最优解,转Step6。

Step6 如果小于当前次优解,更新次优解。

Step7 按式(4)(5)和(6)更新信息素。

Step8 NA←NA+1,如果NA>Nmax_A转Step9,否则转Step2。

Step9 输出最优路径和最优路径的长度。

2 实验结果与分析

为了更好地说明该算法的有效性,选用国际上通用的TSPLIB测试库中的Eil51实例进行测试。实验仿真环境:1.60 GHz主频的Intel处理器,1 G内存,仿真软件Microsoft Visual C++6.0。实验中蚂蚁数量m=51/1.5=34,参数α=1.0、β=3.0、q0=0.5,.

信息素挥发因子初始值ρ0设为0.9,挥发因子调节系数ξ设为0.98,ρmin设为0.5。图4是本文改进算法连续运行4次的收敛过程图,算法在600次之后基本收敛,最差收敛到430,最好收敛到428。图5是算法连续运行15次的结果图,所得最长路径值为433,最短路径值为427,路径均值为428。

本文以Eil51为例比较了几种算法的性能,结果如表1所示。其中,ACS算法每次迭代3000次;ShyiMing Chen与ChihYao Chien提出的方法内层遗传算法迭代100次,外层蚁群算法迭代30次,每代120只蚂蚁;改进的混合蛙跳算法每一代蛙有510只,外层迭代50次。

表1中给出了不同算法的平均解与最优解相对TSPLB库中已知Eil51最优解(426)的偏差百分比PDav和PDbest,图6和图7将各算法针对Eil51实例求得的平均值与已知最优解偏差和运行时间做了一个直观的比较。
PDav和PDbest具体描述如下:

从表1、图6和图7可知,本算法在迭代次数较少的情况下,算法的性能优于或接近所列出的对比算法,从而进一步验证了算法的有效性。

图4 改进算法的收敛过程图Fig.4 Convergence process map of proposed algorithm
图5 改进算法运行15次结果图Fig.5 Results of proposed algorithm after
running 15 times
表1 本文算法与其他算法的比较Table 1 Comparison between proposed algorithm
and other algorithms
图6 不同算法的平均解与已知最优解的偏差Fig.6 Percentage deviations of average solution to
best known solution for different methods
图7 不同算法的平均运行时间Fig.7 Average running time of different methods
3 结束语

本文算法采用信息素挥发因子自适应调整机制调节算法收敛速度,避免过度集中在某些较优的路径上。并通过加强算法对公共路径的利用使算法尽量减少寻径过程中的重复运算,降低蚁群算法的运算时间,而且有助于跳出局部最优,增强了算法的全局寻优能力。实验结果表明,改进算法在迭代次数相对较少的情况下,求得的解优于或接近所列出的其他算法,平均解与已知最优解偏差为0.46%,最优解与已知最优解偏差为0.23%,较好地适用于求解TSP问题。

参考文献
[1] Dorigo M, Maniezzo V, Colorni A. Ant system: optimization by a colony of cooperating agents[J]. IEEE Transaction on Systems, Man, and Cybernetics, Part B: Cybernetics, 1996, 26（1）: 29-41. [本文引用:1]
[2] Dorigo M, Gambardella L M, Middendorf M, et al. Guest editorial: special section special section on ant colony optimization[J]. IEEE Transaction on, Evolutionary Computation, 2002, 6（4）: 317-319. [本文引用:1]
[3] Stutzle T, Hoos H H. Max-min ant system[J]. Future Generation Computer Systems, 2000（16）: 889-914. [本文引用:1]
[4] Malisia A R, Tizhoosh H R. Applying opposition- based ideas to the ant colony system[C]∥2007 IEEE Congress on Swarm Intelligence Symposium, Hono-lulu, HI, 2007: 182-189. [本文引用:1]
[5] Duan H B, Zhang X Y, Wu J, et al. Max-min adaptive ant colony optimization approach to multi-UAVs coordinated trajectory replanning in dynamic and uncertain environments[J]. Journal of Bionic Engineering, 2009, 6（2）: 161-173. [本文引用:0] [JCR: 1.023] [CJCR: 0.38]
[6] Yu B, Yang Z Z, Yao B Z. An improved ant colony optimization for vehicle routing problem[J]. Euro- pean Journal of Operational Research, 2009, 196（1）: 171-176. [本文引用:0] [JCR: 1.815]
[7] Tseng S P, Tsai C W, Chiang M C, et al. A fast ant colony optimization for traveling salesman problem[C]∥2010 IEEE Congress on Evolutionary Computation, Barcelona, 2010: 1-6. [本文引用:0]
[8] 罗雪晖, 杨烨, 李霞. 改进混合蛙跳算法求解旅行商问题[J]. 通信学报, 2009, 30（7）: 130-134.
Luo Xue-hui, Yang Ye, Li Xia. Modified shuffled frog-leaping algorithm to solve traveling salesman problem[J]. Journal on Communications, 2009, 30（7）: 130-134. [本文引用:0] [CJCR: 1.119]
[9] Masutti T A S, Castro L N D. A self-organizing neural network using ideas from the immune system to solve the travelling salesman problems[J]. Information Sciences, 2009, 179（10）: 1454-1468. [本文引用:0]
[10] Chen S M, Chien C Y. Solving the traveling sales-man problem based on the genetic simulated annealing ant colony system with particle swarm optimization techniques[J]. Expert Systems with Applications, 2011（38）: 14439-14450. [本文引用:0] [JCR: 2.203]