一种基于蚁群算法的TSP问题分段求解算法.pdf

《一种基于蚁群算法的TSP问题分段求解算法.pdf》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、第24卷第12期计算机学报Vol.24No.122001年12月CINESEJ.C0MPUTERSDec.2001一种基于蚁群算法的TSP问题分段求解算法吴斌史忠植(中国科学院计算技术研究所智能信息处理开放实验室北京100080D摘要群居性昆虫行为的研究为计算机科学家提供了设计分布式控制和优化算法的有力方法.对以蚁群算法为代表的群集智能研究已经逐渐成为一个研究热点.该文首先在蚁群算法的基础上提出了相遇算法9提高了蚁群算法蚂蚁一次周游的质量9然后将相遇算法与采用并行策略的分段算法相结合9提出一种基于蚁群算法的TSP问题分段求解算法.实验结果表明该算法有较好的有效性.关键词蚁群算法9

2、组合优化9旅行商问题9并行策略9群集智能中图法分类号:TP18AHAHtoloHyAlgorithmBasedPartitioHAlgorithmforTSPWUBinSIZhong-Zhi(Ke}laborator}offntellzgencefnformatzonProcesszng9fnstztuteofcomputzngtechnolog}9chzneseacacem}ofsczences9Bezjzng100080DAbstraCt0ptimiZationalgorithmsinspiredbymodelsofco-operativefoodretrievalinant

3、shavebeenunexpectedlysuccessfulandbecomeknoWninrecentyearsasAntColony0ptimiZation(AC0D.Asanovelcomputationalapproach9sWarmintelligencesystemssuchasantsystemhavebecomeahotresearchdomain.ThispaperproposesameetingalgorithmandapartitionalgorithmforTSPbasedontypicalantalgorithms.Themeetingalgorith

4、mimprovestheanttouringguali-ty9itprovidesgoodinitialtouringresultsforlocaloptimiZationontheconditionofloWiterationtimes.CombiningWithasimpleparalleliZationstrategythepartitionalgorithm9thispapergetssomegoodexperimentresultsonTravelingSalesmanProblems.Themainideaofmeetingal-gorithmisthattherea

5、retWoantsinatouringinsteadofoneantintypicalantalgorithms.ThetWoantsstartatouringfromasamecity9andchoosecitiesfromdifferentdirections.Bysharingasametabulist9theymeetatthemiddleofatouring.ExperimentresultsshoWsthetWo-anttouringisslightlyshorterthantheone-anttouring.BasedontheshortertouringbytWo

6、antsontheconditionofloWiterationtimes9aparalleliZationstrategyisdeveloped.Itisthepartitional-gorithm.TheWholepathispartedintoseveralsegments9thenadaptedmeetingalgorithmisa-gainappliedonthesegments.ThreeTSPinstancesareusedinthispaper.TheyareST70(70citiesD9KroB150(fromTSPLIBDandCC144(Chinese144

7、citiesD.Comparingthebestresultsavailable678.59(fromthebestpathprovidedbyTSPLIBD926130(fromTSPLIBDand30354.3(byGAD9someexperimentresultsonthesynthesiZedalgorithmofmeetingalgorithmandparti-tionalgorithmareratherbetter.Theyare677.1096926127.35an