动态跃迁转移蚁群算法
第31卷
o1．3l
第1期
№ l
计 算 机 工 程
Com puter Engineering
2005年 1月
January．
2005
· 人工智能及识别技术 · 文章编号：l000_3428(2005)0l—ll67一l2 文献标识码：A 中图分类号：TP301．6
动 态跃迁转移蚁群算法
胡 勇
(南京师范大学计算机系，南京 210097)
摘 要 ：给出了 一利，改进的蚁群算法 ，该算法对蚂蚁初始位置选择 上进行优化 ，能较大地提高进化速 度，并且还通过动态地 调整跃迁转移概
率，减少 r停滞，加快 lr收敛逑度 实验表明对于某些TSP问题，实验结果优于 国外最新的成果
关健词 ：模拟进化算法；蚁群算法；旅行商问题；动态跃迁转移
An Ant Colony Algorithm Based 0n Dynamic Transition
HU Yong
(Department ofCompute~Science．Nanjing Normal University．Nanjing 2 1 0097)
[Abstract l This paper pl oposes a dynamic transition ant colony algorithm．The experiments demonstrate that the evokltion Call be quickened alld the
computational precision can be cffectivcb，improved through adopting the dynamic transition method Some experiments I‘esult 011 the dynamic transition
algorithm arc better than some latcst algorithm
【Keywordsl Simulated cw)lutionm y algorithm；Ant colon)algorithm；TSP；Dynamictransition
人们从生物的特性中受到启发 ，提出了许多用以解决复
杂优化问题的新方法，并成功地应用于实际问题。特别发现
蚂 蚁群 落在进行合作 时基 本上是 自组织 的，蚁群 算法 (ant
colony algorithm，ACA)就是在这一基础研究上 由意大利学
者M．Dorigo，V．Maniezzo，A．Colorni等人首先提出来的一
利z新型的模拟进化算 。。 ，该算法是 一种利用计算机模拟蚁
群活动的启发式搜索算法 ，呵对组合优化问题进行求解。用
该算法求解TSP问题?、分配问题 ‘、j0b—shop调度问 ，取
得 了 ·系列较好的实验结果。因此，蚁群算法逐渐引起了一
些研究者 的关注 ，并用该算法来解决实际问题，如求解连续
空间优化问题 5。尽管此算法被成功地应用解决 多利z组合优
化问题，但该算法也存在进化速度较慢、进化过程容易停滞
的缺陷。例如一些研究者提出的杂交算法 】、最大最小算
法 ‘等，尽管这些算法比原 先的算法有 了改进 ，但杂交算法
采用无方向随机杂交，杂交效率低 ，提高速度不 明显 ；最大
最小算法只是通过对信息素的大小进行限制，算法停滞的可
能性仍然较大。本文从另一个角度出发，采用动态跃迁转移
的方法，对蚂蚁选择城市 (也是选择路径)进行 优化，使
得算法能减少停滞，加快收敛速度 。
l基本蚊群算法的原理
基本蚁群算法通过模 拟生物 界中的蚂蚁搜索 食物 的过
程，也就是通过人工蚂蚁之间的信息交流与相互协作最终找
到从蚁穴到食物源的最短路径 ，这种算法被称为 “人工蚁群
算法”。为了说明人工蚁群算法的原理 ，先简要介绍一下蚂
蚁搜索食物的具体过程 ：
蚂蚁之间通过?种 叫 “外激素”的物质进行交流 ，正女f】
M．Dorigo等人在文献[I】中指 出的 ：蚁群算法的最大的特点
是蚁群中的蚂蚁采用 “外激素”为媒介的间接的异步的联系
方式。蚂蚁在行动 (寻找食物或者寻找回巢 的路径)中，会
在它们经过的地 方留下 “外激素”。这些物质能被同一蚁群
中后来的蚂蚁感受到，并作为一种信号影响后到者的行动
(具体表现在后到的蚂蚁选择有这些物质的路径的可能性，
比选择没有这些物质的路径的可能性大得多，选择较短的路
径的可能性比选择较长的路径的可能性也大得多)， 后刨
者 留下的外激素会对原有 的外激素进行加强，并如此循环
去，最后几乎所有的蚂蚁集中到～ 条最短或接近最短的路径
上。因此，由大量蚂蚁组成的蚁群的集体行为便表现出一种
信息正反馈现象：某一路径 上走过的蚂蚁越多，则后来者选
择该路径的概率就越大。蚂蚁个体之问就是通过这种信息的
交流达到搜索食物的 目的。
2基本蚁群系统模型及其实现
为 了便于理解 ，以求解平面 kn个城市的TSP问题(O，
1，?，n一1表示城市序号)为例说明蚁群系统模型。n个城 市
的TSP问题就是 寻找通过n个城市各 。。次 目．最后回到出发点
的最短路径。之所以选择TSP问题，一万面因为蚁群算法最
初用于求解TSP问题，便于比较 ，另 ’方面，TSP是典型的
组合优化难题 ，常常用来验证某．一算法的有效性。对于其它
问题，可以对此模型稍作修改便可应 用 ‘。虽然它们从形式
上看略有不同，但基本原理是相同的，鄙是通过模拟蚁群行
为到达优化之 目的。
为模拟实 际蚂蚁的行 为，首 先引进如下记号：设m是蚁
群中蚂蚁的数量， (I_．．一1，2，?，n)表示城市i和城市j之间的
土
距离，bi(，)表示t时刻位于城市i的蚂蚁的个数 ， b {fJ．f ，?
，= I
表示t时刻在ij连线上残留的信息量。制始时刻，各条路径 上
信息量相等 ，设 (0) C(C为常数)蚂蚁k(k=I 2一，m)在运
动过程 中，根据各条路径上的信息量决定转移 方向，P (r)表
示在tlt~ J蚂蚁k由位置i转移到位置 的概率。
p ft) 髋 n，，。， ec
0．otherwise
作者简介：胡 勇 (I973一)
定稿 日期：2003．II-14
男，讲师，t研方向为智能控制
E·mail： hu3 ong(dninu cdu．cn
— l67—
维普资讯 http://www.cqvip.com
其中，allowed k {O，1，?，n一1}-tabuk表示蚂蚁k下一步允许选
择的城市，与实际蚁群不同，人工蚁群系统具有记忆功能，
tab~(k 1 2 一，11"1)用以记录蚂蚁k当前所走过 的城市，集合tabu
随着进化过程作 动态调整。Q，13分别表示蚂 蚁在运动过程
中所积累的信息及启发式因子，它们在蚂蚁选择路径中所起
的不同作用。 表示由城市戳 移到城市j期望程度，对于TSP
问题，一般可设为城市i转移到城市j的距离的倒数。
随着时间的推移，以前留下的信息逐渐消逝，用参数 1．P
表示信息消逝程度 ，经过n个时刻 ，蚂蚁完成一次循 环，各
路径 上信息量要根据下式作调整
Ar ∑A r
△r：表示第 k只蚂蚁在本次循环中留在路径 上的信息
量 ，△ 也表示本次循环中路径U上的信息量的增量。
△ ： 』 - 蚁经过f， (4) l
0 ．otherwise
其中，Q是常数，L^表示第k只蚂蚁在本次循环中所走路径的
长度．在初始时刻 ， f (o)=C(常量 ) ，△ =0(i I_o，1，? ，
n一1)。根据具体算法的不同， f (t)，△ (t)及 P (t)的表达
形式可以不同，要根据具体问题而定。M．Dorigo曾给 出3种
不 同 模 型 ， 分 别 称 之 为 ant—cycle system ， ant—quantity
system，ant—density system 。。它们的差别在于表达式(4)的不
同。在ant—quantity system模型中，
△ f ： { ，若第职蚂lit蚁'尢 间经过c『 (5)
0 ，。ther~ isP
在ant—density system模 型中，
=
只蚂 。
㈤
它们的区别在于后两种模型中利用的是局部信息 ，而前
者利用的是整体信息。
3改进的蚊群算法 ．
经过仿真实验发现 ，随着仿真蚂蚁经过一段 时问的运
行，路径上的信息素会逐步集中于较短的路径上，而这很可
能是局部的最短路径 ，也就是算法可能 已陷入局部的最优解
而停滞 ，不能得到全局的最优解 。因此 ，为了能减少停滞 ，
可以动态的增加搜索的多样性，也就是随着信息素残留增
加 ，蚂蚁局部选择可能性加大，而通过增加搜索 的多样性 ，
可以减少停滞。具体方法是，在采用局部和全局混合模型 的
基础上，根据停滞的时间，动态 调整 q ，值，即停滞的时间越
长，q c，的值会被动态地减少 ，停滞的时间越短 ，q0的值会
被动态地加大的办法来优化求解性能。对于算法中的其它的
参数如c，Cl，B，P，可以用实验方法确定其最优组合，
停止条件可以用固定进化代数或者当进化趋势不明显时便停
止计算。另外在蚂蚁的起始城市的选择上，将蚂蚁分配到较
偏远的城市里，减少蚂蚁较长路径的反复，实验证明通过采
一 168一
用 以上策略，可 以有效地提高优化的迷度 ，降低停滞的町能
性 ，从而提高优化的效果。下l百f就是该改进的蚁群算法：
begin
初始化过程 ：
nc ：：0 ；
tao[i]D】：：C；
tabu[k]=~ ；
for(nc=0；nc
{将一群蚂蚁随机地放在较偏远的周边fl~'JambicatCit}rNum个城
市里，并设置它们的tabu[k][O]；
Ibr(index=0：index
个 数 +／
{
for(I‘=O：k
{ q=rand() l_0／RAN D
—
MAX；／ 产生0～l的 随机数(
if(q
选择城市 j，使得tao[sl[il／elsl[iI最人
．
i∈ {0，l，? ，n—I}tabu[k1／ 当前城市 为s
else
根据公式 (I)的概率选择城市i；
}
把所选择的城市序号加到 tabu[k]中／+(动态调整集合 tabu[k])；
利 用公 式 (5) 调整tao[i][j]：／ 局 部调整 ／
j
确定本次循环中找到的最佳路径：
利 用公 式 (4) 调整tao[i][i]；／+全 局调整 ／
if(finCounter>( CounterIJine+I) sTOPI INE) 如果停滞代数越
多，动态调整 q。值 ／
{
long pAttentmtion；
nnCountcrLine=(intXnl1CounIer／ST0PLlNE)：
pAttenuation=finCounter；
pAttenuation=pAIIenLIaIi0n／ST0PI』1N E：
q0=attenuation[pAttenuation]；
}
}
输出最佳路径及最佳结果
end
4实验结果
分别以eil51的TSP问题为例， 一方面选择国际上最新 的
蚁群算法 ，另一方面用本文的改进算法实验 ，并将结果比较
如个下 (表 I)：
表1以51个城市的eil51 TSP问题两种算法实验结果
算 法 进化100t"~时 最短路径长度 收敛进化的代数 说明
的路径长度
ACS 585．2I3 433．4『l I80 文献I51
ACS+NN 5lO．3l5 429．452 I224 文献f51
EA+NN 482．356 430 32I 1032 文献[5】
本文算法 428．127 4I6．525 957
根据上面的实验可知本文的算法在解决TSP问题时，收
敛效果要好于其它的算法 ，特别是运行初剃的收敛速度非常
快，最后能得到较好的解。
5结论
本文提 出改进的蚁群 算法 ，町以有效地减少基本蚁群算
法中容易停滞 的缺陷 ，同时加快了收敛速度 ，有利于实际运
(下转第1 7I页)
维普资讯 http://www.cqvip.com
表4标准PSO，GA和H I’SO对不 同维数的
G rim,rnnk函数5O次优化试验结果
Func 3 G riewank
维数 周期 ． 适应度 PSO GA HPSO
(x 10 1 (× 10 )
20() 均 值 3 7l 5 1 095 4 807
方差 3 853 0 554 3 6l9
IO l 000 均 值 64 6I1 l 472 6()875
_}i蠢 31 OI 5 ()43I 33^89
() ()()() 均 恤 7 332 156 34 I 5l
方差 23 147 l 952 27 3O0
3() 3()00 均 值 5 475 1 76I 3 09t)5
。 }i瓷 9 O35 l 932 6 3 338 5
表5标准PSO，GA和H I’SO对不 同维数的
Rastdgin函数5O次优化试验结果
I2LIlle 4 Rastrigin
维数 周期 适 应度 l SO aA HI S0
200 均 值 0 084 5 0 l67 0
方差 O O67 I (]I 83 0
l() l 000 均 值 3 86I 6 7l9 I 486×l0
，r差 l I1 8 l l 89 3 389×10
20 2 000 均 值 I6 98l l 8 83 l 664
方差 4 464 8 66() l l 79
30 3 000 均谯 40 0l 9 37 83 f J 297
4试验结果与分析
在肘多模函数Rastrigin进行优化时，随着维数的增高，
大量 的局 部 极值 点 的 引入 ，使 PSO的 性 能 逐 渐 下降 。
Griewank函 数 相 于 Sphere 数 加 入 了 噪 音 项
几cos((xi一1)／4i)，随着维数的增7Jll，该项趋于0，适应度函
数 问趋千平滑 ，NRIz在维数较低和维数较高tl,]'PSO都能 同
ItPSO‘‘样有很好 的优化性 能。显示出PSO在搜索空间中局
部极值点较 少的情况下 良好的局部寻优能力。而HI SO在各
种情况都显 l{很强的优化能力。
4、图5是HPSO~：IIPSO对50维Rosenbrock函数和50维
Rastrigin函数进行 优化 的适应度和 多样性 的对 比。以HPSO
达到优化要求作为终止 (即输出适应度值和 目标值的误差小
r10’)。如图所示 ，随着多样性 的降低 ，PSOq~怏陷入 早
熟收敛。而HPSO的适应度在不断调整 ，使种群的在收缩 与
扩张之问保持协调，保证 整个优化过程持续收敛。
(上接第l68页)
用 。但是蚁群 算法研究的时间还不 长，多数成果都只是基
J 人量实验 的数据分析 ，蚁群算法的数学理论基础 还不 坚
实 ，其中的各利t参数选择比较复杂 ，所以算法的理论问题 还
仃很多问题有待进一步研究 。
参考文献
Colomi A．Dorigo M，Maniezzo V．Distributed Optimization by Ant
Colonies．ProcI st European ConfArtificial Life．Pans，France：Elsevier，
I99I：I34．I42
，L _ E
．
． ． PS0 Dj Ve ：
露 蠹 ’ 一PS0 F● ne5 ’ 美 l F _衄目 ； li
； l；i
篓 ! S； i! 砻 ! ! { 毫：
f ：
1 i ； 蚕
鏊 ‘
懑
L‘ 冀 i； i 、。、 -{
? 每 黔搿
一
意
图4 H PSO，I'SOllg50维Roscnbrock函数优化适应度和多样性
喜
l 50
图5 HPSO，PSO对5O维Rastrigin函数优化适应度和多样性
5结论
本文通过对标准PSO算法 的信息传j塑结构 以及种群多样
性变化进行分析 ，提 出 ]'I-IPSO算法对 标准PSO算法进行 改
进 ，该算法引入了交叉算子干¨多样性控制I大l子。仿真试验 表
明，HPSO在群体信息传递 结构和对种群多样性协调的控 制
方面有了改进 ，在单模和多模函数优化 题 ，以及在高维的
情况下，都显示 出良好的性能。
参考文献
I Kennedy J．Eberhart R C．Particle Swal‘m Optimization Pt’oc．IEEE
International Conference on Nctu’al NctxxOl’ks．1EEE Service Cente r，
l995．VI：l942 l948
2 Van den Bergh F．An Analysis of Pat’tide Sxx L!I n1 Optimizcrs．[Phd
thesis]，200I-I I
3 Kennedy J．Small-W orlds and Mega—Minds：I cots ofNeighborhoc~i
Fopology on Particle Swarm Performance 【】roc 0f the I 999 Congress
of Evolutionary Com putation．I 999．3：I 93 1-1 938
4 Riget J． Vesterstroem J S．A D iversity Guidcd Particle SwarIll
Optimizer—the ARPSO．Technical Repot‘t No 2002—02 Univcl sit', ol’
Aarhus．EVA Lif ， 2002
2 Colom i A．Dorigo M ．M anie72o V．A i1 Invcstigation ot‘Som e P roper．
ties ol’an Ant Algorithm ．Proc PI SN’92． I 992：509．520
3 Colorni A，Dorigo M，Maniezzo V，ct al Ant S)’stein fo r’Job—shop
Scheduling Belgian Joumal ol’0Dcrations Rcscm ch and Statistic
Computing Science，J 994，34fJ)：39—53
4 Cheng—Fa T．Chun—wci T．A Nc、、，Approach l{1I-Solving Large Trave—
Iing Salesman Problem Using Evolutionary Ant Rules．IEEE．2002
5 Stutzl T．Hoos H．The MAX．M IN Ant System and lJocal Search f"or the
Travel；ng Salesman Problem．In l roc ICI C97 1 997 IEEE 4th Int
Conf．Evolutionary Computation．f997：309．3 i4
维普资讯 http://www.cqvip.com
动态跃迁转移蚁群算法.pdf
