一种求解TSP问题的改进蚁群算法

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

1、第8第期计算机技术与发展Vo1．18NO．122008年12月O0ⅣUTERTE(O10(YANDDFⅦLoPMENTDec．2008一种求解TSP问题的改进蚁群算法王娟，王建(中国工程物理研究院计算机应用研究所，四川绵阳621900)摘要：针对基本蚁群算法存在收敛速度慢，易陷于局部最优解等缺点，提出了一种求解旅行商(P)问题的改进蚁群算法。通过在基本蚁群算法中提出保留最优解和引入个体差异策略的改进方法，有效地抑制了算法收敛过程中的停滞现象，提高了全局搜索能力和解的质量。TSPLIB的实例验证了该改进算法的有效性。关

2、键词：蚁群算法；旅行商问题；最优解；个体差异策略中图分类号：TP301．6文献标识码：A文章编号：1673—629x(20o8)12—0050一o3AnImprovedAntColonyAlgorithmforSolvingTSPProblemWANGJuan，WANGJian(ComputerApplicationInstitute，ChinaAcademyofEngineeringPhysics，Mianyang621900，China)Abstract：Introducesanimprovedantcolony

3、algorithmtosolvethetravelingsalesamnproblem(TSP)forreducingthedeficiencyoftradi*tionalantalgorithmforslowconvergenceandlocaloptimalsolution．Theimpmvedantcolonyalgorithmwhichintroducesreservingoptimalsolutionandindividualvariationtotraditionalantalgorithmcanconq

4、uerstagnationandoptimizesolution．ThesimulationexperimentshowsthevalidityforthisimprovedalgorithminTSPLIB．Keywords：antcolonyalgorithm；travelingsalemaanprobl~n；optimalsolution；individualvariationO引言文中在研究基本蚁群算法的基础上，提出了保留旅行商问题(Travelingsalesmanproblem，TSP)是最优解和引入个体

5、差异策略的两点改进方法，有效抑一个典型的组合优化问题，是一个NP难问题，其可能制了收敛过程中的停滞现象，提高了算法的搜索能力。的路径数目与城市数目成指数型增长，所以一般很难TSPLIB中Att48、St70和Ei176问题的实例求解结果精确地求出其最优解。目前，人们在如何解决这个问表明改进的蚁群算法具有良好的性能。题方面已经做出了大量的研究，包括：遗传算法、禁忌搜索算法、模拟退火算法等，且都取得了一定的成果。1基本蚁群算法求解TSP问题20世纪90年代，意大利学者M．Dorigo，V．Maniezzo和TSP问题是指

6、对于给定的个城市集合(1，2，⋯，A．Colomi等人从生物进化的机理中受到启发，通过Tt)，找到一条经过每一个城市一次且回到起点的最小模拟自然界蚂蚁寻径的行为，提出了一种全新的模拟花费的封闭环路。其目标函数是：进化——蚁群算法。该算法具有较强的鲁棒性、较好minD=d(i，i+1)+d(：r／，1)的全局优化能力和分布式计算能力，同时还易于与其他方法相结合，特别适合于求解困难的组合优化问题。其中，(i，J)(i，J=1，2，⋯，)表示城市i和之间但基本蚁群算法也存在一些缺陷，如：搜索时间长、易的距离。陷入局部最优和

7、出现停滞现象。针对这些缺点，人们基本蚁群算法求解TSP问题[]可以简单地表述对基本蚁群算法做了各种改进研究，比较典型的有蚁如下：假设将只蚂蚁随机地放置在T／个城市上，初始群系统(AntColonySystem，ACS)和MAX～MIN蚂蚁时刻城市间每一条边的信息素r(0)相等，每只蚂蚁系统。禁忌表tabu中的第一个元素设为其初始城市，在搜索过程中，蚂蚁将根据城市间的距离di，=1，2，⋯，收稿日期：2008—03—18T1)和城市间边上信息素强度决定下一个要访问的城基金项目：中国工程物理研究院面上基金资助项目(200

8、60324)作者简介：王娟(1974一)，女，陕西渭南人，硕士，工程师，研究方市，砖为t时刻蚂蚁k(k：1，2，⋯，D1)由城市i到城向为人工智能、软件工程。市J的转换概率：第l2期王娟等：一种求解TSP问题的改进蚁群算法·5l·得了很大的进展，大量结果证明了算法的有效性和在某些领域的优势。但是，蚁群算旦法也有一些缺陷。例_{0，[!·]￡：)