一种改进的自适应蚁群算法求解tsp问题

《一种改进的自适应蚁群算法求解tsp问题》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、总第244期计算机与数字工程Vo1．38No．22010年第2期Computer＆DigitalEngineering11一种改进的自适应蚁群算法求解TSP问题占志刚张求明张盛意王康(中国地质大学(武汉)计算机学院武汉430074)摘要文章提出了一种改进的蚁群算法，其核心是限制单步路径上的蚂蚁数目，当该路径上的信息素达到一定浓度时，人为的迫使蚂蚁改换路径，从而更好的全局寻优，避免算法陷入局部极优，并使用2-Opt方法对路径进行优化。对旅行商问题(TSP)的实验结果表明：新算法的优化结果和效率都优于基本蚁群算法。关键

2、词蚁群算法；信息素；2-Opt；旅行商问题中图分类号TP18；TP301AnImprovedAdaptiveAntColonyAlgorithmforSolvingTSPZhanZhigangZhangQiumingZhangShengyiWangKang(SchoolofComputer，ChinaUniversityofGeosciences，Wuhan430074)AbstractAnimprovedantcolonyalgorithmisproposed，whosecoreistolimitthenumbe

3、rofantsonthesingle-steppath，whenthepheromoneonthepathreachesacertainconcentration，weforcetOchangepathsofants，SOthenewalgo—rithmhavegoodcapabilityinglobalsearch，avoidfallinginlocalbest，andtheroutesareoptimizedby2-Optmethodwhenallantshavefoundeffectiveroute．Thet

4、estsforTSPproblemshowthatthenewalgorithmissuperiortoconventionalACAinqualityandefficiency．KeyWordsantcolonyalgorithm，pheromone，2-Optmethod，TSPClassNIImberTP18：TP301人要在，z个城市贩卖自己的物品，TSP问题就是寻1引言找该商人通过个城市各一次并回到出发城市的蚁群算法同其它生物仿生算法一样，受自然界最短回路。中真实生物(蚂蚁)的集体行为(觅食)的启发而发该

5、文在基本蚁群算法的基础上，采用蚂蚁信息展起来的一种基于群体智能的模拟进化算法，它是素的最优路径更新机制，限制单步路径上的信息素由意大利学者DorigoM．等人[2]在1992年最先提浓度与全局环路上信息素浓度的比例，较好地回避出来的。他们充分利用蚁群搜索食物的过程与旅算法陷入局部极优。行商问题(TSP)的相似性，解决了TsP问题，取得2基本蚁群算法(ACA)了很好的结果L1]。十几年来，人们对蚁群算法进行了广泛深入的研究[7瑚]，并将其成功应用于多种实用于寻找最短路径的蚁群算法来源于蚂蚁觅际问题[]。食的群体行为。

6、单个的蚂蚁没有智能，只能简单的经典TSP(Travellingsa】e5manproblem)问题随机游荡，一旦单只蚂蚁找到食物，它就会返回巢在通信领域和交通领域等的网络设计中有着重要中通知同伴，并且在沿途路径上释放“信息素”(外的意义。TSP问题是经典的NP难问题，假设某商激素pheromone)作为蚁群前往食物所在地的标收稿日期：2009年1O月24日，修回日期：2009年l1月21日作者简介：占志刚，男，硕士研究生，研究方向：智能计算。张求明，男，博士，副教授，研究方向：智能计算，智能信息处理。张盛意，男，研

7、究方向：数据挖掘。l2占志刚等：一种改进的自适应蚁群算法求解TSP问题第38卷记。如果两只蚂蚁同时找到食物，并且采取不同的．i，蚂蚁k在此次循环中经过城市i和城市J路线回巢，那么比较长的路线上的信息素味道会比△一l0，否则较淡，蚁群会沿着另一条更近的路线前往食物所在地。蚁群算法设计虚拟的蚂蚁，模拟蚂蚁的觅食行(5)其中：Q为表示信息素强度的常数，表示蚂蚁k为，让他们摸索不同的路线，并留下随着时间逐渐在本次循环中所经过路径的总长度。消失的虚拟“信息素”，根据“信息素”较浓的路径较算法初始进化次数NC一0，蚂蚁随机初始

8、起短的原则，寻找最短路径。始城市，依据状态转移概率选择下一城市，当所有在基本蚁群算法[3]中，以TSP问题为例，设有蚂蚁依次经过所有城市后回到起始城市为一次进n个城市，m只蚂蚁，采用d(，J一1，2，⋯，，z)表示化，评价每只蚂蚁通过的路径长度，并记录最短路城市i到城市J之间的距离，(f)表示在时刻t城径，更新所有路径上的信息素，转入下次循环：NC市i和城市