收稿日期:2009-03-30 修回日期:2009-04-07
第26卷 第8期
计 算 机 仿 真
2009年8月
文章编号:1006-9348(2009)08-0089-03
基于粒子群优化的蚁群算法在TSP 中的应用
柴宝杰1
,刘大为
2
(1.牡丹江师范学院,黑龙江牡丹江157012;2.中国石油信息技术服务中心,北京100007)
摘要:结合粒子群算法的问题,提出用混合蚁群算法来求解著名的旅行商问题。问题的核心是应用粒子群算法对蚁群算法的控制参数:启发式因子、信息素挥发系数、随机性选择阈值进行优化,以及运用蚁群系统算法寻找最短路径。新算法对于蚂蚁算法中的参数调整大大减低,减少了大量盲目的实验,力求在开发最优解和探究搜索空间上找到平衡点。对旅行商问题的仿真实验表明,新算法的优化质量和效率都优于传统蚁群算法和遗传算法,接近理论最佳值。新算法也可推广用于其他NP 问题的求解。
关键词:蚁群算法;蚁群系统;粒子群算法;旅行商问题中图分类号:TP30116 文献标识码:A
Appli ca ti on of an An t Colony A lgor ith m i n TSP Ba sed on Parti cle Swarm
CHA IBao -jie 1
,L I U Da -wei
2
(1.Mudanjian Teacher πs College,M udanjiang Heil ongjiang 157012,China;2.China Petr oleu m I nfor mati on Technol ogy Service Center,Beijing 100007,China )
ABSTRACT:Combined with the idea of the particle s war m op ti m izati on (PS O )algorith m,the ant col ony op ti m iza 2
ti on (AC O )algorith m is p resented t o s olve the well known traveling sales man p r oble m (TSP ).The core of this algo 2rith m is using PS O t o op ti m ize the contr ol para meters of ACO which consist of heuristic fact or,pher omone evaporati on coefficient and the threshold of st ochastic selecti on,and app lying ant col ony system t o r outing .The ne w algorith m ef 2fectively overcomes the influence of contr ol para meters of ACO and decreases the nu mbers of useless experi m ents,ai 2m ing t o find the balance bet w een exp l oiting the op ti m al s oluti on and enlarging the search s pace .Si m ulati on results show that the ne w algorith m has better op ti m izati on quality and efficiency than the traditi onal ant col ony algorith m and the genetic algorith m.The ne w algorith m can als o be generalized t o s olve other NP p r oblem s .
KE YWO RD S:Ant col ony algorith m;Ant col ony syste m;Particle s war m algorith m;Traveling sales man p r oble m
1 引言
近年来,启发式智能优化方法愈来愈引起人们的关注,
它们是解决NP 问题的有效工具。
蚁群算法[1,2]是模拟真实蚁群觅食过程寻求最短路径的原理,由意大利学者M.Dorigo 等人首先提出的一种仿生智能优化算法。参加寻径的蚂蚁通过留在链路上的信息素交互来选择新的路由,从而达到寻优的目的。其主要特点是:一个增强型学习系统,具有分布式的计算特性,具有很强的鲁棒性,易于与其它优化算法融合。但是蚁群算法在解决大型优化问题时,存在搜索空间和时间性能上的矛盾,易出现
过早收敛于非全局最优解以及计算时间过长的弱点;而且决
定蚁群算法性能的3个控制参数启发式因子β、信息素挥发系数ρ、随机性选择阈值q 0的取值缺乏理论支持,影响了算法的性能。针对以上问题,许多学者提出若干改进算法,如Dorigo 和Gambardella 提出的蚁群系统(Ant Col ony Syste m,
ACS )[3]
,Stutzle 和Hoos 提出了最大-最小蚂蚁系统(M ax -M in Ant Syste m,MMAS )[4]
等。
粒子群优化算法(Particle S war m Op ti m izati on,PS O )源于对鸟群捕食行为的研究,由Kennedy 和Eberhart [5]共同提出的一类模拟群体智能的优化算法。与其它进化算法类似,PS O 采用“群体”与“进化”的概念,主要依据个体的适应值大小进行操作。它的特点是:概念简单、容易实现,并且依赖经验参数较少。目前已成功地用于求解多种优化问题[6],尤其是函数优化。
—
98—
本文对蚁群算法和粒子群算法的机理和性质进行了研究,将两种算法融合,提出一种新算法ACSPS O。初期采用粒子群算法生成蚁群算法中的3个控制参数β,ρ,q
,后期采用ACS算法改进传统蚁群算法的寻径行为。新算法克服了蚁群算法参数的影响,使算法中的参数调整大大降低,减少了大量盲目的实验,实现了对搜索空间高效、快速的全面寻优。文中将其应用于求解TSP问题,仿真结果显示ACSPS O能获得比传统遗传算法和传统蚁群算法更好的全局搜索性能。
2 粒子群算法基本原理
PS O模拟鸟群的捕食行为,假设一群鸟在只有一块食物的区域内随机搜索食物,所有的鸟都不知道食物的位置,但它们知道当前位置与食物的距离。最简单有效的方法是搜寻目前离食物最近的鸟的周围区域。PS O从这种模型中得到启示,并将其用于解决优化问题。PS O中每个优化问题的解都是搜索空间中的一只鸟,称之为“粒子”。所有的粒子都有一个由被优化的函数所决定的适应值,对于每个粒子,还有一个速度决定它们飞翔的方向和距离,然后粒子们就追随当前的最优粒子在解空间中搜索。PS O初始化为一群随机粒子(随机解),然后通过迭代找到最优解。在每一次迭代中,粒子通过跟踪两个“极值”更新自己,一个是粒子本身所找到的最优解,称为个体极值pbest;另一个极值是整个种群目前找到的最优解,该极值是全局极值gbest。另外,也可以不用整个种群而只用其中一部分为粒子的邻居,那么在所有邻居中的极值就是局部极值。在找到这两个最优值时,每个粒子根据如下公式更新自己的速度和新的位置:
v
k+1=w v
k
+c1r1(pbest
k
-x
k
)+c
2
r2(gbest
k
-x
k
)(1)
x
k+1
=x
k
+v
k+1
(2)
其中:v
k 为第k步粒子的速度向量;x
k
为第k步粒子的位置;
pbest k为第k步粒子本身所找到的最好解的位置;gbest k为第
k步整个种群目前找到的最好解的位置;w表示惯性权重;c1调节微粒飞向自身最好位置方向的步长,c
2
调节微粒向全局
最好位置飞行的步长,c
1
,c2通常在0～2间取值;r1～U(0, 1),r2～U(0,1)为两个相互独立的随机函数;每一维粒子的
速度都被限制于一定范围内,即v
k ∈[-v
max
,v max]。如果v k
>v max时,v
k =v max;如果v
k
<-v max时,v
k
=-v max。
3 蚁群算法的优化原理
蚁群的觅食行为是一个重要而有趣的行为。据昆虫学家的观察和研究,发现蚂蚁有能力在没有任何可见提示下找出从蚁穴到食物源的最短路径,并且能随环境变化适应性地搜索新的路径,产生新的选择。虽然单个蚂蚁的行为极其简单,但由大量的蚂蚁个体组成的蚂蚁群体却表现出极其复杂的行为,能够完成复杂的任务。
蚂蚁在觅食走过的路径上释放一种蚂蚁特有的分泌物———信息素(Pher omone)。蚂蚁个体之间正是通过这种信息素进行信息传递,从而能相互协作,完成复杂任务。在一定范围内蚂蚁能够察觉到这种信息素并指导它的行为,当一些路径通过的蚂蚁越多,则留下的信息素轨迹(trail)也就越多,招致后来更多的蚂蚁选择该路径的概率也越高,于是越发增加了该路径的信息素强度,由此构成一个学习信息的正反馈过程,从而逐渐逼近最优路径,蚁群算法的原理正是基于此。
在ACS算法中,每个蚂蚁根据状态转移规则来选择下一个城市,信息素值的更新遵循全局更新和局部更新两种规则[3]。
3.1 状态转移规则
在ACS算法中,蚂蚁使用伪随机比率选择规则选择下一个城市。即在城市i的第k只蚂蚁选择下一城市j的规则是
j=
arg max
u∈allo w ed k
{τiu(t)?[ηiu]β},如果q≤q0,
J,否则
(3)
其中q
∈(0,1)为常数,q∈(0,1)为随机数,τ
iu
(t)表示城市i,u间的信息素值,β表示启发式因子的相对强弱。如果生
成的随机数q小于等于常数q
,则按式(3)选取可行城市,否则按式(4)来选择下一个城市。
p k ij(t)=
τ
ij
(t)[η
ij
]β
∑
s∈allo w k
τ
is
(t)[η
is
]β
,如果j∈a llo w ed k,
0,否则,
(4)
其中allo w ed
k
为蚂蚁k当前的可行城市集。
3.2 局部信息素更新
局部信息素更新的作用是使已选的边对后来的蚂蚁具有较小的影响力,从而使蚂蚁对没有被选中的边有更强的探索能力。在ACS算法中,当蚂蚁从城市i转到城市j后,边(i,j)上的信息素按式(5)进行更新:
τ
ij
=(1-ξ)?τij+ξ?τ0(5)
其中τ
为常数,ξ∈(0,1)为可调参数。
3.3 全局信息素更新
针对全局最优解所属的边按式(6)进行更新:
τ
ij
(t+1)=(1-ρ)?τ
ij
(t)+ρ?Δτgb
ij
(6)
Δτgb
ij
=
1/L gb,如果边(i,j)包含在最优路径中,
0,否则,
其中L gb为当前最好解的长度,ρ∈(0,1)为信息素挥发系数。
4 混合蚁群优化算法
蚁群算法和粒子群算法都是基于群智能的算法。蚁群算法擅长解决离散优化问题,而PS O擅长连续问题的优化。在TSP中,蚁群算法是离散优化问题,但算法的控制参数是连续变化的。ACSPS O(ant col ony syste m particle s war m op ti2 m izati on)的基本思想是汲取两种算法的长处,优势互补。算
法采用PS O来优化蚁群算法中的三个控制参数(β,ρ,q
),运用ACS算法改进传统蚁群算法的寻径行为,实现对搜索空间高效、快速的全面寻优。
—
9
—
解TSP的混合蚁群算法ACSPS O如下:
PS O初始化:
随机选择4个粒子(particle),每个粒子包含三个参数β,ρ,q
,组成一个3×4的随机数组。其中β在[0,15]随机
取值,ρ和q
在[0,1]随机取值。
f or It=1t o MaxIt_PS O do
ACS初始化:
对任意的边(i,j),信息素初值τ
ij (t)=const,Δτ
ij
=0;
将4只包含各自参数的蚂蚁随机地放置在n个结点上,
根据各自的变量值,求适应度函数值,即4只蚂蚁分别进行下面的ACS寻径:
for Nc=1t o Max Nc_ACS do
f or k=1t o4do
对每一只包含各自参数(β,ρ,q
)的蚂蚁运行ACS:
按式(3)、(4)进行状态转移,寻找路径;
对经过的边,按式(5)进行局部信息素更新;
记录每个蚂蚁的结果。
end f or
对当前最好解的路径按式(6)进行全局信息素更新。
end f or
将寻径后的每个蚂蚁的最短路径长度作为相应粒子的适应度函数值;
使用PS O算法,按式(1),(2)更新每个粒子的速度和位置,即更新每个粒子的3个参数;
end for
最后输出全局最优TSP路径值和全局最优参数β,ρ,q
。5 实验仿真结果
TSP(traveling sales man p r oble m),又称为旅行商问题。简单地说,就是给定一组有限个城市和它们两两之间的直达距离,寻找一个闭合的旅程,使刚好每个城市经过一次且总的旅行距离最短。TSP问题理论上存在最优解,但在实际中还未找到有效的方法来求得此值,只能逐渐向最优解逼近,即只能得到最接近理论最佳值的次优解。由于TSP是典型的NP问题,已成为研究优化算法的基准问题,用于测试、比较算法的性能[7,8]。文中应用ACSPS O求解TSP,并与其他优化算法进行比较,以测试其性能。
在本文的仿真实验中,选取4个蚂蚁进行寻径,蚂蚁寻径限定最大循环数(Max Nc_ACS)为结束条件,Max Nc_ACS= 400,τ0=(n?L nn)-1,其中,n是城市数,L nn是路由长度
值[7]。信息素τ采用MMAS方法限制在[τ
m in
,τmax][4]。AC2 SPS O算法总的迭代次数,即PS O迭代次数MaxIt_PS O=100, c1=1.8,c2=1.8。
为了验证ACSPS O的TSP仿真结果,本文将ACSPS O在eil51,eil76和kr oA100问题中分别运行10次,得到路径长度和控制参数的最优值和平均值,并与遗传算法(G A)和ACS 的结果进行比较。G A和ACS的TSP结果来自文献[3]。目前已知的最优结果来自文献[8]。
表1 3个TSP问题求解结果的比较
eil51eil76kr oA100
G A42854521761
ACS42653821282
ACSPS O42653821282
最优解42653821282
由表1可知,ACSPS O的结果比G A所得结果更接近最优解,与ACS所得的最优解相近。但ACS算法参数事前设定,是多次实验相比较,得到的一个结果。这对于一个未知的优化问题是不可能的,因为它的参数是未知的,需要大量的运算,才能比较出一个相对较好的参数,且易陷入局部最优。ACSPS O很好的解决了这一问题,它随机产生初始控制参数,在优化解的同时,采用PS O对3个控制参数不断地进行连续优化选择,表2、3列出了这些控制参数的优化平均值和最优值。
表2 ACSPS O参数优化平均值和平均路径长度
平均β平均q0平均ρ平均路径长度eil51619211015953015109430138
eil7641792101681601403454118
kr oA10081058601592301363521536
表3 ACSPS O参数最优值和最优路径长度
最优β最优q0最优ρ最优路径长度eil51517993017261013052426
eil76615168016848010837538
kr oA10081324501539001351021310
从表中数据可以看出,对每一个TSP问题而言,产生最优解或较好解的控制参数不惟一,没有一个确切的参数值可以保证生成最优解。表2、3中优化得到的控制参数值可以代替Dorigo和Ga mbardella给出的控制参数[3],即β=2,q
= 0.7,ρ=0.2,为解决其它的TSP问题,提供了一种新的选择,有利于蚁群算法在优化问题中的推广和应用。而且这种参数优化的过程扩大了寻径空间,力求在探索搜索空间和反馈信息利用上取得平衡。由此可见,ACSPS O具有明显优势。
6 结论
蚁群算法和粒子群算法都是基于群集智能的算法。前者是对蚂蚁群落食物采集过程的模拟,粒子群算法(PS O)也是起源于简单社会系统的模拟,模拟鸟群觅食的过程。蚁群算法擅长解决离散优化问题,而PS O擅长连续问题的优化。从当前的应用效果来看,这种模仿自然生物的新型系统寻优思想无疑具有十分光明的前景。(下转第136页)
—
1
9
—
D I B CR算法能有效地提高无线网络的性能。
5 小结
经过以上的性能对比,可以看出CA-D I B CR的性能明显优于不具备信道感知能力的E BA,而且在误帧率较高的恶劣通信环境下,吞吐量、平均分组错误概率以及分组平均延迟等性能指标均有显著的改进。可见,本文提出的信道预约和信道感知相结合的方法是改善无线网络性能的有效手段,因为信道预约改善了分组冲突问题而信道感知则改善了信道中的误帧问题。
参考文献:
[1] Sunil Kumar,V ineet S Raghavan,J ing Deng.Medium Access
Contr ol p r ot ocols f or ad hoc wireless net w orks:A survey[J].Ad
Hoc Net w orks,2006,4:326-358.
[2] Jaehyuk Choi,Joon Yoo,Sunghyun Choi and Chongkwon Ki m.
EBA:An Enhancement of the I EEE802111DCF via D istributed
Reservati on[J].I EEE Transacti ons on Mobile Computing,July/
August2005,4(4):378-390.
[3] Daji Q iao,Sunghyun Choi and Kang G Shin.Goodput Analysis
and L ink Adap tati on for I EEE802111a W ireless LAN s[J].I EEE
Transacti ons on Mobile Computing,2002,1(4).
[4] Peter P Pha m,Sylvie Perreau,runa Jayasuriya.Ne w Cr oss-Layer
Design App r oach t o Ad Hoc Net w orks Under Rayleigh Fading[J].
I EEE Journal on Selected A reas in Communicati ons,112005,23
(1):28-39.
[5] V Kumar and R V Raja Kumar.Perfor mance Analysis of a Finite
Word Length I m p lemented CCK Mode m with Rake Receiver for
WLAN Syste m[J].I EEE,2005.
[6] Putti pong Mahasukhon,M ichael He mpel,Ha m id Sharif,Ting
Zhou,S ong Ci,H siao-Hwa Chen.BER Analysis of802111b
Net w orks underMobility[J].I CC2007p r oceedings,2007. [7] 刘乃安.无线局域网(WLAN)—原理、技术与应用[M].西安:
西安电子科技大学出版社,2004.
[8] J G Pr oakis.D igital Communicati ons,4th-ed[M].Ne w York,
NY:McGra w H ill,2000.
[9] Chur ong Chen and Choi Look La w.Thr oughput Perfor mance Anal2
ysis and Experi m ental Evaluati on of I EEE802111b Radi o L ink
[J].I C I CS,
2007.
[作者简介]
唐文照(1985-),女(汉族),湖北省天门市人,硕
士研究生,主要研究领域为无线多媒体通信网络。
李 波(1971-),男(汉族),陕西省西安市人,教
授,博士研究生导师,主要研究领域为无线多媒体
通信网络。
张 蕊(1985-),女(汉族),甘肃省天水市人,硕士研究生,主要研究领域为无线多媒体通信网络。
(上接第91页)
本文将蚁群系统的协作效应与粒子群算法的进化效应相结合,初期采用粒子群算法生成蚂蚁个体的3个参数(β,ρ,q
),并不断进行优化,后期采用蚁群算法寻径。既为参数的选择提供了依据,又采用ACS对信息素进行限制,防止蚂蚁过早陷入局部最优解。新算法克服了参数选择对蚁群算法性能的影响,减少了大量盲目的实验,力求在开发最好解和探究搜索空间上找到平衡点。对TSP的仿真实验表明,新算法的优化质量和效率都优于传统蚁群算法和遗传算法,接近理论最佳值。新算法也可推广用于其他NP问题的求解。
参考文献:
[1] M Dorit os,V Maniezz o,A Col orni.Positive feedback as a search
strategy[R].Technical91-016,D i parti m ent o di Elettr onica,
Politecnico diM ilano,I T,1991.
[2] M Dorigo,G D Car o.Ant algorithm s f or discrete op ti m izati on[J].
A rtificial L ife,1999,5(3):137-172.
[3] M Dorigo,L M Ga mbardella.Ant col ony syste m:a cooperative
learning app r oach t o the traveling sales man p r oble m[J].I EEE
Transacti ons on Evoluti onary Computati on,1997,1(1):53-66.
[4] T Stutzle,H H Hoos.Max-m in ant syste m[J].Future Generati on
Computer Syste m,2000,16(8):889-914.[5] R C Eberhart,J Kennedy.A ne w op ti m izer using particles s war m
theory[C].Pr oc Sixth I nt Sy mposium on M icr o Machine and Hu2 man Science,Nagoya,1995139-43.
[6] K E Pars opoul os,M N V rahatis.Recent App r oaches t o Gl obal Op2
ti m izati on Pr oble m s Thr ough Particle S war m Op ti m izati on[J].N atural Computing,2002,1(2-3):235-306.
[7] D J Rosenkrantz,R E Stearns,P M Le wis.An analysis of several
heuristics for the traveling sales man p r oble m[J].SI A M J Comput,
1977,6:563-581.
[8] L M Ga mbardella,M Dorigo.Ant-Q:a reinforce ment learning
app r oach t o the traveling sales man p r oble m[A].Pr oceedings of ML-95,T welfth I ntern Conf on Machining[C].Morgan kauf2 mann,1995.252-
260.
[作者简介]
柴宝杰(1971-),男(汉族),黑龙江牡丹江市人,
讲师,主要研究领域为算法分析。
刘大为(1974-),男(蒙族),工程师,主要研究领
域为高性能数据库。
—
6
3
1
—