基于改进蚁群算法求解最短路径和tsp问题

《基于改进蚁群算法求解最短路径和tsp问题》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、万方数据第君蕊耜期2010年4月计算机技术与发展v01．20N()．4cC}MPlrrERnC刖010(、YAND帆l01)MENTApr．2叭O基于改进蚁群算法求解最短路径和TSP问题宋世杰，刘高峰，周忠友，卢小亮(内江师范学院数学与信息科学学院，四川内江641112)摘要：为了能高效地求解最短路径和TSP问题，利用速度恒定的蚂蚁群，行走最短路径的蚂蚁首先达到终点这个基本原理，提出了一种改进的蚁群算法。因为只要有一个蚂蚁达到终点，算法停止，所以该算法避免了蚂蚁往返爬行所消耗的时间。针对一定规模的最短路径和TSP问题，设置足够量的蚂蚁群，通过该算法能较快地求出全局最优解或

2、者能很好逼近最优解的近似解，算法的时间复径杂度是线性级的，迭代次数较少，而且该算法是并行处理的。通过实验仿真，结果表明算法是可行有效的。关键词：蚁群算法；最短路径；TSP问题；并行性中围分类号：TPl83文献标识码：A文章编号：1673—629X(2010)04—0144—04AnImpr0VedAntColonyAlgorithmSolVingtheShortestPathandTSPProblemsoNGSh¨ie，LIUQ恰feng，ZHOUZhong—you，UJXia争liallg(sch∞l0fMathematbandInfomati∞，N两iangNI)nn

3、alCollege，N蜘iang641112，China)Al葛tr叠d：Inord盯toeffid∞tly鲥vet11e宣horte吼pathandTSPpr0_blefn，∞∞rdingtothe∞nscantspeedofant∞咖，thepath0nw}lichtheantfi哪托瓤h∞thedestinati0Ilistheshortest．Animp∞删ant∞lonyalg嘶thmisp∞posed．Ifananth勰∞Ilie、^edthedestinat；on，thea190^thrn蚰0pped。3D出e蛔^thrnhas狮idedthetin砖tha

4、t锄协伽tandk肌ecrawl．Fbfthecerta洫s嗣esIDrt酋tp8thandTSPprobl锄。t}砖alg谢th锄obtajnt}圯glDbaloptimal90111tionoranapproximate30lutionWhichisgr∞tlycI∞e∞theoptimal30lutbn，anditst．m℃唧Iexi锣isIine盯．Ith皓le翳ita胃tiol坞andthisa丑驴dthmispa瑚lelpm痢ng．S．mulat两re踟k3}髓鸭thatthis蛔rithrnisfe商bleandeffecti豫．Key帅r凼：肌t∞blya

5、Ig丽thm；shortestpathpmbl酮；TSP；paralleli锄O引言随着社会的不断发展，最短路径问题已广泛应用于交通运输、物流配送、网络分析、管道铺设、厂区选址与布局等与生产实践息息相关的问题。以交通运输为例，搜索城市路网中两点间的最短路径就显得极其重要。但在实际运用中发现，当城市路网结点过多时经典算法就会导致计算量急剧增加，搜索开销相当大，效率很低。蚁群算法是由意大利学者&rigo等人于20世纪90年代初期通过模拟自然界中蚂蚁集体寻径的行为而提出的一种基于种群的启发式随机搜索算法[卜4l，蚁群算法具有并行性、鲁棒性、正反馈性等特点。蚁群算法最早成功应用于

6、解决著名的旅行商问题(TSP)，收稿日期：2009一08—02；修回日期：2009—10一30基金项目：四川省教育科研计划项目(07ZB043)作者简介：宋世杰(1987一)，男．四川成都人，研究方向为线性规划；刘高峰，硕士。讲师，研究方向为启发式算法。以及二次分配问题(Q心)、车间任务调度问题(JsP)、图的着色问题、网络路由等许多复杂的组合优化问题[5～81。目前，蚁群算法在求解最短路径和TSP问题时容易陷入局部最优、迭代次数多、时间复杂度高【9q引。文中利用速度恒定的蚂蚁群，行走最短路的蚂蚁首先达到终点这个基本原理，在问题空间中同时构造问题的多个解，很好地解决了蚁群

7、算法在求解最短路径和TsP问题的局限性。1蚁群算法的基本原理生态学家发现蚂蚁在寻找食物时总是可以找到食物源到巢穴之间的最短路径，这是因为蚂蚁在搜寻食物源时。能在其走过的路径上释放一种蚂蚁特有的信息素，可以将信息传递给其它蚂蚁并影响其对路径的选择。当蚂蚁碰到一个还没有走过的路口时就随机地挑选一条路径前行，并释放与路径有关的信息素，通常万方数据第4期宋世杰等：基于改进蚁群算法求解最短路径和TsP问题·145·蚂蚁会以较大概率选择信息素浓度高的路径，并加强该路径的信息素浓度，当越来越多的蚂蚁选择信息素浓度高的路径，而其它路径上的信息