改进的蚁群算法及其在TSP中的应用研究
2004年 lO月
第25卷第 lO期
通 信 学 报
JOURNAL OF CHINA INSTn1J1E OF COMMUNICATIONS
Vl01．25 No．1O
October 20o4
改进的蚁群算法及其在 TSP中的应用研究
孙力娟 ，王良俊 ，王汝传 1,2
(1．南京邮电学院 计算机科学与技术系，江苏 南京 210003；
2．南京大学 计算机软件新技术国家重点实验室，江苏 南京 210093)
摘 要：提出一种改进的蚁群算法，其核心是应用遗传算法对蚁群算法的4个控制参数( ，，、
)进行优化，以及运用MMAS(max—min ant system)进行寻径，新算法具有全局搜索能力强的
特点。对旅行商问题 (TSP)的仿真实验结果表明：新算法的优化质量和效率都优于传统蚁群算法
和遗传算法。
关键词：蚁群算法：遗传算法；旅行商问题
中图分类号：TP913 文献标识码：A 文章编号：1000-436X(2004)10—01 ll一06
Research of using an" proved ant colony algorithmResearcn OI U n improvea ant colony algorithm
to solve TSP
SUN Li-juan ，WANG Liang-jun。，WAN G Ru—chuan ，
(1．DepartmentofComputerScience andTechnology,NanjhagUniversityofPostsandTelecommunications。Nanjing 210003，China；
2．State Key Laboratory for Novel Software Technology at Nanjing University,N柚jing 210093，China)
Abstract：An improved an t colony algorithm was proposed，whose cores were that using the genetic
algorithm(GA)to optimize the control parameters of the ACA(a、 、P、q0)and applying MMAS to
routing．The new algorithm (ACAGA)is characterized by good global search capability．We use it to
solve TSP (traveling salesman problem)．Simulation results show that ACAGA is superior to
conventional ACA an d GA in quality an d efficiency．
Key words：an t colony algorithm；genetic algorithm；TSP
1 引言
近年来，启发式智能优化方法愈来愈引起人们的关注。如：模拟退火、遗传算法、蚁群
算法等，它们是解决NP问题的有效工具。
蚁群算法 (ACA，ant colony algorithm) ' 是意大利学者Marco Dorigo等提出的一种仿
生寻优算法。参加寻径的蚂蚁通过留在链路上的信息素交互来选择新的路由，从而达到寻优
的目的。其主要特点是：本身是一个增强型学习系统，具有分布式的计算特性，具有很强的
收稿日期：2004—01—06；修订日期：2004—07—15
基金项目：国家自然科学基金资助项目 (70271050)；江苏省自然科学基金资助项目 (BK2003105)；江苏省
高技术研究计划资助项 目 (BG2004004)；江苏省计算机信息处理技术重点实验室基金资助项 目 (kjs03061
和kjs04)
维普资讯 http://www.cqvip.com
通 信 学 报 2004焦
顽健性，易于与其它优化算法融合。但是蚁群算法在解决大型优化问题时，存在搜索空间和
时间性能上的矛盾，易出现过早收敛于非全局最优解以及计算时间过长的弱点；而且决定蚁群
算法性能的4个控制参数( P、qo)的取值缺乏理论支持，影响了算法的性能。
遗传算法 (GA，genetic algorithm)【3 是美国Michigan大学的John Holland教授等人于
1975年提出的模拟自然界中生物遗传机制的随机搜索算法，它是基于染色体层面进行各种遗
传优化操作。GA 在本质上是一个群体迭代算法，它从一组随机的初始群体出发，由目标函
数 (适应度函数)对其进行评价，根据 “优胜劣汰”的竞争原则，通过选择、交叉、变异等
优化过程，产生性能更优的下一代群体，不断重复，直到获得满意的结果。GA 的特点是：
具有全局搜索能力，具有潜在的并行型，具有较强的顽健性，计算过程简单，能很好地解决开发
最优解和探寻搜索空间的矛盾，具有可扩展性，易于和其它算法结合。但GA算法对于系统中的
反馈信息利用不充分，当求解到一定范围时会做大量的无效迭代。
目前，将蚁群算法与遗传算法相融合来解决 NP问题，已取得了较好的效果【4 。文献[4】采
用遗传算法对 ACA的 3个参数 ( 、 、qo)进行优化，并在 TSP问题中进行验证。由于文
中对锨 默认值， 、P、q0的取值是相对于 一个比值，所以无法实现 ACA4个参数(
P、qo)组合的全局寻优，也就无法求得TSP问题的全局最优解。
MMAS[71是通过对各条链路上信息素值的限制来控制蚂蚁的寻径行为，从而有效地防止
蚂蚁过早地陷入局部最优解。
本文对遗传算法和蚁群算法的机理和性能进行了研究，将两种算法融合，提出一种新算法
ACAGA，采用遗传算法来优化蚁群算法中的 4个控制参数( P、qo)，并运用 MMAS改
进传统蚁群算法的寻径行为，实现对搜索空间高效、快速的全面寻优。文中将其应用于求解TSP
问题，仿真结果显示 ACAGA能获得比传统遗传算法和传统蚁群算法更好的全局搜索性能。
2 蚁群算法的优化原理
自然界中的蚂蚁，在寻找食物或遇到障碍物时，总能找到一条从食物到蚁巢或绕过障碍
物的最优路径。原因在于，蚂蚁运动中会在所经过的路径上释放出信息素 (pheromone)，后
续蚂蚁可根据前面蚂蚁遗留下来的信息素选择下一条要走的路径。一条路径上的信息素越高，
说明这条路径被选中的次数越多，即路径的性能更优，后续蚂蚁选择这条路径的概率就更大，
由此构成一个学习信息的正反馈过程，从而逐渐逼近最优解，蚁群算法的原理正是基于此。
在蚁群算法中，每个蚂蚁根据状态转移规则来选择下一跳节点，信息素值的更新遵循全
局更新和局部更新两种规则u’ 。
(1)状态转移规则
在节点 f的第 k只蚂蚁选择下一节点 7的规则是
I J，otherwise
= r1、 I argmax{[ (f)】 ×[ }
ueJk(s-1)'if(q≤qo)
(f)=
其中， (f)表示两节点 i、J间的信息素值。 O)表示路径轨迹的相对重要性； ( O)是
路径能见度的相对重要性。
维普资讯 http://www.cqvip.com
第 lO期 孙力娟等：改进的蚁群算法及其在TSP中的应用研究
)={1，2，?，z)一tabUk(S)表示第k个蚂蚁下一步可以选择的节点集；
1
f=— ，cost(i, )表示节点 i、J间链路的费用大小。
COStLz，JJ
(2)信息素的全局更新规则
当m只蚂蚁成功地完成一次寻径过程后，将选出目标函数值最小的路由，用以完成全局
信息素的更新，使得较优解保留下来，对后继蚂蚁产生影响，加快收敛到最优解的速度。
设i、J为两个相邻节点，则有
(f+，z)÷-(1一 ) (f)+P× (f) ，
其中，变量Aro(t)是在 t时刻，节点i、J间链路上信息素的增加量
∽ ：j‘ st-l,if(i, g 卜 肼 【0
，
otherwise
信息素消逝因子(0< 1)；L 是目标函数， 。 是 的最小值，即最优目标函数值。
(3)信息素的局部更新规则
对于第k只蚂蚁，如果节点i、J是它所选择路径上的两个相邻节点，则有
(f)÷-(1一P)× (f)+P× (f) (4)
否则，不更新。其中，0
一 值，表示初始环境一致)¨】。
3 利用遗传算法改进蚁群算法 (ACAGA)及其在TSP中的应用
ACAGA (ant colony algorithm genetic algorithm)的基本思想是汲取两种算法的长处，优
势互补，在搜索空间和时间性能上取得平衡。算法的基本思路是采用 GA来优化 ACA中的4
个控制参数( P、qo)，运用 MMAS改进传统蚁群算法的寻径行为，实现对搜索空间高效、
快速的全面寻优。文中将其应用于求解 TSP问题。
ACAGA算法的伪代码如下：
for itera=O to Generation do
对参加进化的每个个体的变量 P、q0进行随机编码；
从个体中随机地选择 4个；
根据给出的4个变量的值，求适应度函数值，即4个个体分别进行ACA—TSP寻径：
① 初始化
t=0；(t是计时器)
NC：=O；(ⅣC是循环计数器)
对所有的边 ( )上的信息素赋初值to(t)=const， =0；
将4只蚂蚁随机地放置在 n个节点上；
② ：=l； (变量 s是蚂蚁k在一次寻径过程中走的步数)
for ：=l tO 4 dO
将第k只蚂蚁的初始节点放入数组 tabUk(S)；
)：={1，2，3?，z)一tabu ( )；( )是蚂蚁 k在第 S步时尚未经过的节点集合)
③ ：=件l；
fbr ：=1 to4do
维普资讯 http://www.cqvip.com
通 信 学 报 2004正
根据公式(1)、(2)选择蚂蚁k的下一跳节点-『；(蚂蚁k在t时刻处在节点f=tabu ( 一1))
将蚂蚁 k放置于节点-『，并将节点-『插入数组 tabuk(s)；
tabuk(S)： ；Jk(s)-=Jk(s-1)-j；
根据公式 (3)对链路进行局部信息素更新；
重复③ ，直到 s=n。
④ for足：=1 to 4 do
将蚂蚁 k从节点tabu (，z)移到tabu (1)；(蚂蚁回到初始节点，完成一次回路寻径)
计算蚂蚁k的路由长度 并比较其大小；
求得最短长度￡七e。 及其对应的 。 和tabM ；
根据公式 (4)，对链路进行全局信息素更新；
得到任一条边的信息素浓度值 (t-I-n)；
⑤ f：=f+，z；
NC：=ⅣC+1：
If(NC
Then f清空所有 tabu列表；
跳转到②；l
else
将寻径后的最短路径长度作为适应度函数；
从被选的4个个体中选出2个最优个体；
进行交叉和变异操作生成 2个子个体；
替代 4个个体中最差的2个，放入待进化的个体中；
end for
输出最优结果。
说明：对每一只参加GA运算的蚂蚁，其 4个参数 、 、P、qo进行 28bit编码，每一个参数
占用 7bit，其中：
— — 路径轨迹的相对重要度，在【0，127]间取值；
— — 路径能见度的相对重要度，在【0，127]间取值；
P——信息素的消逝因子，在【0，11间取值；
— — 寻径中开发最优解或探寻搜索空间的选择门限值，在【0，11间取值；
、 、 qo用以寻求最优解和搜索空间之间的平衡，P用于信息素的局部更新。当一次寻径过程
结束，应用最佳寻径蚂蚁的P参数进行全局信息素更新。适应度函数是蚂蚁寻径的路由长度。
4 实验仿真结果
TSP(traveling salesman problem)，又称为旅行商问题。简单地说，就是给定一组有限个
城市和它们两两之间的直达距离，寻找一个闭合的旅程，使刚好每个城市经过一次且总的旅
行距离最短。比如，Eil51是 51个城市的TSP问题；KorA100是 100个城市的TSP问题，每
个问题中城市的坐标位置都是固定和不同的。TSP问题理论上存在最优解，但在实际中还未
找到有效的方法来求得此值，只能逐渐向最优解逼近，即只能得到最接近理论最佳值的次优
解。由于 TSP是典型的NP问题，已成为研究优化算法的基准问题，用于测试、比较算法的
维普资讯 http://www.cqvip.com
第 l0期 孙力娟等：改进的蚁群算法及其在TSP中的应用研究
性能 m】。文中应用 ACAGA求解 TSP问题，并与其他优化算法进行比较，以测试其性能。
在本文的仿真实验中，设染色体数目population=20个，每一代中选取4个蚂蚁进行寻径，蚂
蚁寻径限定最大循环数 (NCM~x)为结束条件，NCMAx=IO00，遗传迭代次数Generation=20，交叉
因子 和变异因子P 分别设为0．6和0．05，ro=(，z·L^ )～，其中，，z是城市数，LM是路由长
度值嘲(比如eil51问题中，上 =511；lin318中，L~=54019)， 采用MMAS方法限制在[ ， x】 。
为了验证ACAGA的仿真结果，本文将 ACAGA分别与 GA、ACA所得结果及目前已知的
最佳路由结果进行比较。
文中首先实现 ACA算法的TSP仿真，其结果是在 Eil51和 Ei176问题中分别运行 10次，
KorA100中运行 5次，所得的最优值和平均值。GA的 TSP结果选 白文献[1】。目前 已知的最
佳路由结果选 白文献【9】。
仿真结果如表 1所示。
表 1 5个 TSP问题求解结果的比较
由表 1可知，ACAGA的结果与GA、ACA所得结果相比更接近最优解。图 1是51节点问题
应用ACAGA算法得到的最优解，和目前得到的最好解一致。图2、图3找到的解和最优解非常接
近，是其它算法易陷入的几个局部最优解，而
ACAGA算法有效地避免了陷入局部最优，结果
表明，在解决较少节点 TSP 问题时，ACA 和
ACAGA所得路由性能差不多，而在解决多节点
TSP问题时，ACAGA的结果明显优于ACA算
法所得结果，更加接近最佳值。这是由于 ACA
算法没有对信息素进行限制，容易出现过早收
敛，并且难以从局部最优解中跳出，从而无法得
到全局最优解。ACAGA很好地解决了这一问
题，由于采用MMAS能有效控制各链路上的信息素，
图2 ACAGA一次随机迭代求得的最好结果
([I I。427，eilS1问题)
图 1 ACAGA找到的最优路径( F_426，ell51问题)
既保留了优秀解又不会对后续蚂蚁的寻径影
图3 ACAGA一次随机迭代求得的最好结果
([ 431，el／51问题 )
维普资讯 http://www.cqvip.com
· ll6· 通 信 学 报 2004生
响过大；采用遗传算法对 4个控制参数不断进行优化，有利于扩大寻径空间，在搜寻空间探究和
反馈信息利用上取得平衡。由此可见，在解决多节点TSP问题时，ACAGA具有明显优势。
5 结论
本文提出了改进的蚁群算法，应用遗传算法对蚁群算法的 4个控制参数( P、q0)
进行优化，为参数的选择提供了理论依据，并且采用 MMAS对信息素进行限制，防止蚂蚁
过早陷入局部最优解。新算法力求在开发最好解和探究搜索空间上找到平衡点。对 TSP问题
的仿真实验表明，新算法的优化质量和效率都优于传统蚁群算法和遗传算法，接近理论最佳
值。新算法也可推广用于其他 NP问题的求解。
参考文献：
【1】 DORIGO M，GAMBARDELLA L M．Ant colony system：a cooperative learning approach to the ttraveling salesman problem[J】
IEEE Transactions on Evolutionary Computation，1997，l(1)：53—66．
【9】
【lO】
DORIGO M，MANIEZZO COLORNI A．The ant system：optimization by a colony of cooperating agents[J]．IEEE Transactions on
Systems，Man，and Cybernetics，1996，26(1)：1—13．
王小平，曹立明．遗传算法一理论、应用与软件实现【M】．西安：西安交通大学出版社，2002．
PILAT M L．WHITE Using genetic algorithms to optimize ACS TSP[A]．Proceedings of Ant Algorithms：Third International
Workshop，ANTS 2002[C]．Brussels，Belgium，2002．282—287．
丁建立，陈增强，袁著祉．遗传算法与蚂蚁算法的融合【J】．计算机研究与发展，2003，40(9)：1351—1356．
WHITE PAGUREK B，oppacher E ASGA：Improving the ant system by integration with genetic algorithms[A]．Proceedings of
the Third Annual Genetic Programming Conference[C]．Morgan Kaufmann，1998．610-617．
STUTZLE HOOS H H．MAX—MlN ant system[J]．Future Generation Computer System,2000，l6(8)：889—914．
ROSENKRANTZ D J，STEARNS R E，LEWIS P M．An analysis of several heuristics for the traveling salesman problem[J]．SIAM J
Comput，1977，6：563—581．
TSPLIB【EB／OL]．http：／／www．iwr．uni-heidelberg．de／groupsdcomopt／software／TSPLIB95／index．html，2003．
GAMBARDELLA L M，DORIGO M．Ant—Q：a reinforcement learning approach to the traveling salesman problem[A]．Proceedings
of ML一95，Twelfth Intern Conf on Machining[C]．Morgan Kaufmann．1995．252—260．
作者简介：
孙力娟 (1963一)，女，江苏南
京人，南京邮电学院副教授，博士
生，主要研究方向为计算机网络、
智能优化方法。
王汝传 (1943一)，男，安徽合
肥人，南京邮电学院教授、博士生
导师，主要研究方向为计算机软件、
计算机网络、信息安全、移动代理
和虚拟现实技术等。
王良俊 (1979一)，女，山东滨
州人，南京邮电学院硕士生，主要
研究方向为计算机网络技术。
2 3 4 5 6 7 8
维普资讯 http://www.cqvip.com
改进的蚁群算法及其在TSP中的应用研究.pdf
