求解复杂TSP问题的随机扰动蚁群算法

2020-12-21 来源：客趣旅游网

　2002年9月系统工程理论与实践第9期　

文章编号:100026788(2002)0920088204

求解复杂TSP问题的随机扰动蚁群算法

郝　晋1,石立宝2,周家启1

(1重庆大学电气工程学院,重庆400044;2.上海交通大学电子信息与电气工程学院,上海200030)

摘要:　针对基本蚁群算法,设计出一种新颖的随机扰动蚁群算法,并将其应用于求解复杂TSP问题Λ该算法包含了两个重要方面:一是提出了采用倒指数曲线来描述的扰动因子;二是设计出了相应的随机选择策略和扰动策略Λ数值模拟表明:该算法可以有效地克服基本蚁群算法的计算时间较长和容易出现停滞现象的缺陷,具有更好的全局搜索能力Λ此外,还对该算法中参数的取值范围及选取方法进行了研究和探讨Λ

关键词:　蚁群算法;随机;扰动策略;TSP问题

中图分类号:　TP18　　　　　　　　文献标识码:　A　　　

AnAntSystemAlgorithmwithRandomPerturbation

BehaviorforComplexTSPProblem

HAOJin,SHILi2bao,ZHOUJia2qi

(1.ElectricalEngineeringCollege,ChongqingUniversity,Chongqing400044,China;2.ElectronicInformationandElec2tricalEngineeringCollege,ShanghaiJiaotongUniversity,Shanghai200030,China)

Abstract:　BasedontheBasicAntSystem(BAS)algorithm,anovelAntSystemwithRandomPertur2bationBehavior(RPAS)ispresentedinthispaper,anditisappliedtosolvecomplexTSPproblem.Thenewalgorithmincludestwoimportantaspects:aperturbationfactorformulatedbyinverseexponentfunctionisdeveloped,ontheotherhand,correspondingtransitionstrategywithrandomselectionandperturbationbehaviorisdesigned.Numericalsimulationdemonstratesthatthenewalgorithmpossessesmorestrongglobaloptimizationcapability,andbringsaboutsomegoodresultsonreducingCPUtime,preventingsearchfrombeinginstagnationbehavior.Furthermore,numericareaandselectionmethodofparametersinthenewalgorithmareexploringlystudied.

Keywords:　antsystemalgorithm;random;perturbationstrategy;TSPproblem

1　引言

自20世纪50年代中期创立了仿生学以来,人们从生物进化的机理中受到启发,提出了许多用以解决复杂优化问题的方法,如基因算法、蚁群算法等Λ其中,蚁群算法(AntSystemalgorithm)是由意大利学者

[1]

M.Dorigo近几年才提出的一种新型的模拟进化算法Λ该算法即是模拟自然界中真实蚁群的觅食行为而

形成的一种模拟进化算法Λ它采用有记忆的人工蚂蚁,通过个体之间的信息交流与相互协作来找到从蚁穴到食物源的最短路径Λ目前蚁群算法在求解旅行推销商(TSP)、指派(assignmentproblem)、job2shop调度等优化问题中,得到了一系列较好的应用Λ

在M.Dorigo提出的基本蚁群算法(BasicAntSystem,BAS)中,给出了三种不同的模型,分别称为

[1]

Ant2CycleSystem,Ant2QuantitySystem,Ant2DensitySystem,它们之间的区别在于:后两种模型利用的是局部信息,而前者为整体信息,求解优化问题时性能较好,通常将其作为蚁群算法基本模型Λ众多研究已经证明蚁群算法具有很强的发现较好解的能力,这是因为该算法不仅利用了正反馈原理,在一定程度上加快进化进程,而且是一种本质并行算法[2,3]Λ但算法本身也存在一些缺陷,如搜索时间较长,而且容易出

收稿日期:2001203226

第9期求解复杂TSP问题的随机扰动蚁群算法89

现停滞现象等Λ本文对此问题进行了研究和探讨,提出了一种新颖的随机扰动蚁群算法(AntSystemwithRandomPerturbationBehavior,简称RPAS)Λ该方法带有一定的自适应性,且具有很强的随机扰动特性,并将其应用于求解复杂的TSP问题Λ数值仿真结果表明采用该法可以有效地提高算法的运算效率和计算精度Λ

2　随机扰动蚁群算法

为了便于理解,我们仍以求解平面上n个城市的TSP问题为例说明基本蚁群系统模型Ζ首先引进如下符号:设m是蚁群中蚂蚁的数量;dij(i,j=1,2,…,n)表示城市i和j城市之间的距离;Γij为dij的倒数,表示由城市i转移到城市j的期望程度;Σij(t)表示t时刻在路径ij上的信息量Ζ初始时刻,各条路径上的信息量相等,设Σij(0)=C(C为常数)Ζ蚂蚁k(k=1,2,…,m)在运动过程中依各条路径上的信息量决定移动方向;pij(k)表示蚂蚁k由城市i转移到城市j的转移概率[1]:

ΣΑij(t)Γij(t),j,s≠tabu(k)ΑΒ

(1)pij(k)=2Σis(t)Γis(t)

0,否则

式中,tabu(k)(k=1,2,…,m)为tabu表,用以记录蚂蚁k当前所走过的城市,它随着进化过程做动态调整,s表示蚂蚁k下一时刻所允许转移的城市,Α,Β分别表示蚂蚁在运动过程中所积累的信息及启发式因子在蚂蚁选择路径的过程中所起的不同作用Ζ随着时间的推移,以前留下的信息逐渐消逝,用参数Θ表示信息残留的程度Ζ经过n个时刻,蚂蚁完成了一次循环,各路径上的信息量要按下式作调整:

Σij(t+n)=Θ󰃖Σij(t)+∃Σij

∃Σij=

k=1

∃Σij(k)

Q,Lk

(2)

∃Σij(k)=

若蚂蚁k走过路径ij

否则

其中,Q是常数,Lk表示第k只蚂蚁在本次循环中所走过的路径长度,在初始时刻,∃Σij(k)=0Ζ参数Q,Α,

[1]

Β,Θ可以用实验方法确定其最优组合,设定最大进化代数作为停止条件Ζ2.1　RPAS的基本原理

蚁群算法的主要依据是信息正反馈原理和某种启发式算法的有机结合ΛBAS中的转移概率公式(1)

揭示了这一原理Λ它表明如果放到某条路径上的信息素越多且路径越短,那么该路径被蚂蚁选中的概率就越大,类似于遗传算法中的“轮盘赌”法Λ鉴于这样一层物理含义,本文设计如下更为简洁的转移策略(3):

(Σij(k)Γij(k))Χ,j|tabu(k)

(3)Cij(k)=

0,否则

(4)s=max(Cij(k))　所对应的城市

式中,Χ>0为扰动因子Ζ需要指出的是,公式(3)中的Cij(k)不再是“转移概率”,而是路径ij的“转移系数”,蚂蚁总是选择转移系数最大的路径,具有一定的确定性Ζ比较公式(1)和(3),经分析发现,当取固定值时与BAS相同,仍不可避免出现停滞现象,故本文提出采用可变的扰动因子Ζ考虑到:

1)蚂蚁个体的运动总是沿着转移系数最大的路径移动.当群体规模较大时,很难在短时间内从大量杂乱无章的路径中找出一条较好的封闭路径,因此在最初的几次迭代中,为加速算法的收敛,应取较大的值,才能使得较好的路径上的信息量明显高于其他路径上的信息量Ζ

2)若一直不变必将导致某一路径上的信息量远远高于其他路径上的信息量,而此路径不一定是最优的,导致随后的搜索出现停滞现象Ζ由此,在随后的搜索过程中适当减小的值一方面可以提高路径选择的多样性(即起到一定的扰动作用),另一方面可以使收敛趋于平缓Ζ

这里,我们设计了倒指数关系曲线来描述Χ:

Χ=a×eb󰃗,k=1,2,…,M;　a>0;b>0

(5)

90系统工程理论与实践2002年9月

式中,M表示最大迭代次数;a,b表示扰动尺度因子Ζ特别地,为不失随机性,令a=a′X,其中a’>0,X是(0,1)中均匀分布的随机数Ζ由式(5)可知,随着迭代次数的增大,Χ的值最终趋近于系数a,而系数b的大小决定了曲线趋近于系数a的快慢程度Ζ曲线如图1所示Ζ

考虑到BAS中易出现的停滞现象,我们采用随机选择策略,并在进化过程中动态的调整做随机选择的概率Ζ同时,为了防止最优的一条路径可能被漏选,对信息量最大的路径单独计算其概率Ζ最后,本文设计了如下的具有随机扰动特性的转移系数:

Σij(k)=max(Σis(k)),　s|

tabu(k)

tabu(k)tabu(k)

图1　倒指数关系曲线

(Σij(k)Γij(k))Χ,

Cij(k)=

(Σij(k))ΑΓij(k),(Σij(k)Γij(k))Χ,0,

Σij(k)=Σis(k)-max(Σis(k))　且UΦpms|Σij(k)=Σis(k)-max(Σis(k))　且U>pms|

(6)

否则

式中,Χ为具有倒指数的扰动因子;pm(0,1)称为随机变异率;U是(0,1)中均匀分布的随机数Ζ

该公式表明,某次迭代过程中某只蚂蚁有若干条路径可选,对于信息素密度最大的那一条路径,应用转移系数公式(3),而对于其它的可选路径,采用随机选择方式Ζ该公式是确定性选择与随机选择相结合的产物,确定性选择导致蚂蚁总是选择转移系数最大的路径,随机选择导致计算转移系数时具有较强的随机性,正是两者的共同作用才使RPAS具有更强的全局搜索能力Ζ2.2　参数选取

,Θ,Q,r0,a,b是非常重要的参数,其选取对于计算的结果影响较大Ζ参数Α表示某一RPAS算法中Α

路径的信息量对蚂蚁选择路径的影响程度,参数Q的大小决定路径上信息量的更新程度,对于不同的网络,它们取值差别较大,难以确定其最佳的取值范围Ζ变量Θ×Σ的物理含义为残留的信息素密度,即需要忘记一部分过去积累的信息,以便更好地利用最新的信息Ζ所以,若Θ取值过小,则不能很好地利用过去积累的信息,若Θ很大,则不能达到信息素密度有效更新的目的Ζ对于上述参数,目前解析法还难以确定其最佳组合Ζ这里,我们通过大量的数字仿真来进行参数的优化设置Ζ本文仍以典型的TSP问题为例对RPAS进行了分析,总结出了参数选取方法,并进一步确定了某些参数最佳取值范围,该方法同样也适用于其它问题Ζ

2.2.1　参数的选取方法

一般,蚁群算法的参数可通过反复试凑得到,显然这对算法的计算效率和收敛性将产生不利影响Ζ为此,本文通过大量的数字仿真总结出一种较有效的参数选取方法Ζ具体步骤如下:

1)大量实验发现:参数Α和Q值对算法的计算进程影响较大,取值范围也较大;参数Θ和pm对算法的计算进程的影响相对较小,其取值相对固定(在0-1之间)Ζ因此,我们首先随机设定一组Θ和pm的值(在0-1之间),来调整Α和Q,得到较理想的解,称之为“粗调”Ζ

2)在基本确定和值之后,反过来调整Θ和Pm,寻找更优的解,称之为“细调”Ζ此后,在“细调”得到Θ和Pm的基础上,再进行“粗调”得到更好的Α和Q值,如此反复,最终确定出一组较为理想的参数组合Ζ

这种方法是在对不同的TSP问题进行大量的数值仿真的基础上总结出来的,具有一定的普遍意义Ζ2.2.2　参数的取值范围

按前述方法,我们得到了以下参数的取值范围Ζ1)当Α和Q同时取较大或较小的值时(如Α>100,Q>1000或Α<0.5,Q<1)不能得到较理想的解Ζ2)前已述及,Θ的取值不宜过小或过大Ζ图2.是以bayes29TSP(29个城市,406条线路)问题为例,说明了Θ的最佳取值范围Ζ从该图可以看出,当Θ<0.1时,Θ失去调节作用;当Θ>0.9时,将导致收敛于较差解Ζ本文建议Θ的取值范围为0.1-0.9Ζ

3)扰动尺度因子a为一常数a′与0和1之间均匀分布随机数的乘积,其中a′的取值范围为1-10;b的取值范围为1-5,本文推荐以下几组(a′,b)较优的组合:(3,2),(4,3),(5,2)Ζ

第9期求解复杂TSP问题的随机扰动蚁群算法91

3　RPAS在求解TSP问题中的应用

为了检验RPAS中随机扰动策略的性能,本文对gr24(24个城市,276条线路)、bayes29(29个城市,406条线路)以及gr48(48个城市,1128条线路)TSP问题进行了计算,并将其分别与BAS进行比较,参数设置见表1,仿真结果见表2Λ图3给出了解算bayes29TSP问题过程中两种算法分别取较好参数时的最好解的收敛曲线Λ表1中环境参数都是针对各自较好的环境参数Λ对于如此选择的参数,我们在PII400微机,VisualC++环境下运行BAS、RPAS,进化代数设为50代(以上各例可见阿根廷Univer2sidadNacional大学学者PabloMoscato提供的TSPBIB网页).

表1　环境参数设置

TSP242948

BAS

RPAS

a′

a=10,Q=10,Pm=0.4

图2　Θ对于最短路径的敏感度曲线

1.01.51.5

5.04.04.0

0.50.60.6

QΑ

10.010.010.0

QΘ

0.850.850.80

pmb

505050

101050

0.40.40.2

555

222

表2　两种方法的计算结果比较(最大迭代次数均为50次)

　　由图3可以看出,基本算法在经过几次迭代后便陷入停滞状态,且计算结果较差,而改进后的算法由于具有很强的随机扰动特性,有效地避免了停滞现象的发生Λ计算结果说明了RPAS较BAS具有更好的全局优化能力,及更高的搜索效率,证明了该方法的有效性Λ

TSP242948

BAS

RPAS

时间(秒)

5852

最短路径

129821805494

时间(秒)

2535

最短路径

127820425265

图3　两种算法的收敛进程

4　结语

本文提出了采用倒指数曲线来描述的扰动因子,并且设计了随机选择策略和扰动策略,构造出一种新

(下转第136)

136系统工程理论与实践2002年9月

5　结论

在实际的投资综合决策中,往往存在着这样或那样的确定性和模糊性因素,这都会直接影响到决策者的合理决策Λ灰色系统理论正是研究和解决此类问题的一种合理可行的方法,本文尝试性地将灰色关联度理论应用到实际工程中Λ分析表明,文中提出的模型概念清晰、逻辑合理,充分利用了系统的决策信息,是分析不确定投资决策问题的比较有效的方法Λ

参考文献:

[1]　邓聚龙.灰色控制系统(第二版)[M].武汉:华中理工大学出版社,1993.307-323.

[2]　胡志根.基于模糊预测的工程造价估算模型研究[A].模糊技术与应用选编(3)[C].北京:北京航空航天大学出版

社,1998.340-345.

[3]　王梅.投资项目综合评价及企业筹资风险分析、理论、方法及其应用研究[D].南京:河海大学,1995.62-78.[4]　杨剑波.多目标决策方法与应用[M].长沙:湖南出版社,1996.60-88.[5]　刘飞,等.制造系统工程(第二版)[M].北京:国防工业出版社,2000.125-133.

[6]　眭凌.基于不确定性方法的防洪项目投资决策综合评价模型研究[D].武汉:武汉大学,2002.32-49.

(上接第91页)

颖的随机扰动蚁群算法(RPAS),并将其应用于求解复杂TSP问题Λ该算法可以有效地克服基本蚁群算法的计算时间较长和容易出现停滞现象的缺陷,具有更好的全局搜索能力,且运算速度和计算精度都得到了较大程度的提高Λ此外,本文还对RPAS算法的参数选取作了研究和探讨,总结出了具有普遍意义的参数选取方法ΛRPAS不仅可以应用于求解复杂TSP问题,同样也可应用于其它工程领域Λ

参考文献:

[1]　.Antsystem:optiMarcoDorigo,VittorioManiezzo,AlbertoColornimizationbyacolonyofcooperatingagents[J].

IEEETransactionsonSystem,ManAadcybernetics2PartbCybernetics,1996,26(1),29-41.[2]　张纪会,高齐圣,徐心和.自适应蚁群算法[J].控制理论与应用,2000,17(1),1-3.

[3]　张纪会,徐心和.一种新的进化算法——蚁群算法[J].系统工程理论与实践,1999,3,84-87.[4]　吴庆洪,张纪会,徐心和.具有变异特征的蚁群算法[J].计算机研究与发展,1999,36(10),1240-1245.[5]　马良,蒋馥.度限制最小树的蚂蚁算法[J].系统工程学报,1999,14(3),211-214.

因篇幅问题不能全部显示，请点此查看更多更全内容

查看全文

全部栏目

求解复杂TSP问题的随机扰动蚁群算法