蚁群算法及其在求解旅行商问题中的应用.pdfVIP

ISSN 1009-3044 E-mail：eduf@dnzs．net．cn Compu~rKnowledgeandTechnology电脑知识与技术 http：／／www．dnzs．net．cn Vo1．10，No．7，March2014 Teh+86—55165690964 蚁群算法及其在求解旅行商问题中的应用 米永强 (宁夏大学数学计算机学院，宁夏 银川I750021) 摘要：蚁群算法是一种求解组合优化问题较好的方法。在蚁群算法的基本原理基础上，以旅行商问题为例，介绍了该算法 求解TSP的数学模型及具体步骤 ，并通过仿真实验与粒子群优化算法等方法比较分析，表明了该算法在求解组合优化问 题方面具有 良好的性能。 关键词：蚁群算法；组合优化；旅行商问题 ；粒子群优化算法 中图分类号：TP18 文献标识码：A 文章编号：1009—3044(2014)07—1505—03 AntColonyAlgorithm andItsApplicationinSolvingtheTravelingSalesmanProblem M IYong——qiang (SchoolofMathematicsandComputerScience，NingxiaUniversity，Yinchuan750021，China) Abstract：Antcolonyalgorithm isakindofgoodmethodstOsolvethecombinatorialoptimizationproblems．Basedonthebasic principleofantcolonyalgorithm，fortravelingsalesmanproblem asanexamplethispaper，thispaperintroducedthemathematical modelofthealgorithm tOsolveTSPandspecificsteps，throughthesimulationexperimentsandcomparativeanalysiswithparticle swarm optimizationalgorithm andothers，itshowedthealgorithm hasgoodperformanceinsolvingcombinatorialoptimization problems． Keywords：antcolonyalgorithm ；combinatorial optimization；travelingsalesmanproblem ；particleswarlTloptimization 1概述 旅行商问题(TravelingSalesmanProblem，TSP)是一类典型的NP难问题 ，有着重要的应用前景。其大致描述为：旅行商从某城市 出发，要走遍n个城市，且每个城市只许走一次，最后又回到原出发的城市，该如何选择一条旅行路线使其旅行的总距离最小。 意大利学者M．Dorigo等人在20世纪90年代初受到 自然界真实蚁群集体行为的启发提出了一种新型优化算法一蚁群算法 (antcolonyalgorithm，ACA)，并将该算法率先应用于求解旅行商问题(TSP)，取得了很好的效果。基于蚁群算法具有较强的鲁棒性且 易与粒子群优化算法 、模拟退火算法等其他算法结合的优点，其引起了许多研究者的注意，并将其应用于通信、交通、电力等领域， 从而解决了一些复杂的组合优化问题。 2蚁群算法求解TSP问题 2．1蚁群算法的基本原理 生物学家通过观察及研究发现 ，蚂蚁觅食是一种群体性行为，而并不是单只蚂蚁寻找食物源。蚂蚁在寻找食物源的过程中会 在其经过的路线上释放一种信息素，并且蚂蚁在运动中能够感知其他蚂蚁释放的这种物质浓度。而蚂蚁选择路线的概率取决于 该路线的信息素浓度 ，浓度越高的路径意味着选中的概率就越大，从而该路线上的信息素浓度也会被加强，蚂蚁群体正是靠着这 种内部机制找到了从巢穴通往食物源的最短路线。蚁群算法从该模型中受到启发而提出并用于求解优化问题。 2．2基于蚁群算法求解TSP的数学模型