资源描述：
《求解复杂tsp问题的随机扰动蚁群算法new》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、2002年9月系统工程理论与实践第9期 文章编号:100026788(2002)0920088204求解复杂TSP问题的随机扰动蚁群算法121郝 晋,石立宝,周家启(1重庆大学电气工程学院,重庆400044;2.上海交通大学电子信息与电气工程学院,上海200030)摘要:针对基本蚁群算法,设计出一种新颖的随机扰动蚁群算法,并将其应用于求解复杂TSP问题L该算法包含了两个重要方面:一是提出了采用倒指数曲线来描述的扰动因子;二是设计出了相应的随机选择策略和扰动策略L数值模拟表明:该算法可以有效地克服基本蚁群算法的计算时间较长和容易出现停滞现象
2、的缺陷,具有更好的全局搜索能力L此外,还对该算法中参数的取值范围及选取方法进行了研究和探讨L关键词:蚁群算法;随机;扰动策略;TSP问题中图分类号:TP18文献标识码:AAnAntSystemAlgorithmwithRandomPerturbationBehaviorforComplexTSPProblemHAOJin,SHILi2bao,ZHOUJia2qi(1.ElectricalEngineeringCollege,ChongqingUniversity,Chongqing400044,China;2.ElectronicInfo
3、rmationandElec2tricalEngineeringCollege,ShanghaiJiaotongUniversity,Shanghai200030,China)Abstract:BasedontheBasicAntSystem(BAS)algorithm,anovelAntSystemwithRandomPertur2bationBehavior(RPAS)ispresentedinthispaper,anditisappliedtosolvecomplexTSPproblem.Thenewalgorithminclude
4、stwoimportantaspects:aperturbationfactorformulatedbyinverseexponentfunctionisdeveloped,ontheotherhand,correspondingtransitionstrategywithrandomselectionandperturbationbehaviorisdesigned.Numericalsimulationdemonstratesthatthenewalgorithmpossessesmorestrongglobaloptimizatio
5、ncapability,andbringsaboutsomegoodresultsonreducingCPUtime,preventingsearchfrombeinginstagnationbehavior.Furthermore,numericareaandselectionmethodofparametersinthenewalgorithmareexploringlystudied.Keywords:antsystemalgorithm;random;perturbationstrategy;TSPproblem1 引言自20世纪
6、50年代中期创立了仿生学以来,人们从生物进化的机理中受到启发,提出了许多用以解决复杂优化问题的方法,如基因算法、蚁群算法等L其中,蚁群算法(AntSystemalgorithm)是由意大利学者[1]M.Dorigo近几年才提出的一种新型的模拟进化算法L该算法即是模拟自然界中真实蚁群的觅食行为而形成的一种模拟进化算法L它采用有记忆的人工蚂蚁,通过个体之间的信息交流与相互协作来找到从蚁穴到食物源的最短路径L目前蚁群算法在求解旅行推销商(TSP)、指派(assignmentproblem)、job2shop调度等优化问题中,得到了一系列较好的应
7、用L在M.Dorigo提出的基本蚁群算法(BasicAntSystem,BAS)中,给出了三种不同的模型,分别称为[1]Ant2CycleSystem,Ant2QuantitySystem,Ant2DensitySystem,它们之间的区别在于:后两种模型利用的是局部信息,而前者为整体信息,求解优化问题时性能较好,通常将其作为蚁群算法基本模型L众多研究已经证明蚁群算法具有很强的发现较好解的能力,这是因为该算法不仅利用了正反馈原理,在一定程度上[2,3]加快进化进程,而且是一种本质并行算法L但算法本身也存在一些缺陷,如搜索时间较长,而且容易
8、出收稿日期:2001203226©1995-2005TsinghuaTongfangOpticalDiscCo.,Ltd.Allrightsreserved.第9期求解复杂TSP问题的随机扰动
