蚁群优化算法在解决tsp问题中的应用

《蚁群优化算法在解决tsp问题中的应用》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、摘要根据蚂蚁生态学提出的蚁群算法是一种新颖的用于求解复杂组合优化问题的模拟进化算法,具有典型的群体智能特征,表现出较强的学习能力和适应能力。本文阐述了该算法的基本原理、算法模型和在TSP(TravelingSalesmanProblem，旅行商)问题中的具体应用过程,并对算法进行了总结和展望。关键词：蚁群算法，旅行商问题，外激素13目录摘要Ⅰ目录II第一章引言1第二章蚁群算法的基本原理和模型22.1蚁群算法的基本原理22.2蚁群算法的模型3第三章基于蚁群算法的TSP求解53.1TSP问题的描述53.2基于蚁群算法的TSP求解53.3蚁群算法的局

2、限性6第四章蚁群算法的改进84.1优选参数m84.2参数的调整84.3信息素的更新84.4信息素链表L和禁忌链表TL的构建9第五章改进的算法基本流程10第六章结论11参考文献12目录不要都使用黑体13第一章引言研究群居性昆虫行为的科学家发现，昆虫在群落一级上的合作基本上是自组织的，在许多场合中尽管这些合作可能很简单，但它们却可以解决许多复杂的问题。蚁群算法就是利用群集智能解决组合优化问题的典型例子。蚁群算法（AntColonyAlgorithm,ACA）是由意大利学者M.Dorigo，V.Mzniezzo，A.Colorni等人在20世纪90年

3、代初首先提出来的。它是继模拟退火算法、遗传算法、禁忌搜索算法、人工神经网络算法等元启发式搜索算法以后的又一种应用于组合优化问题的启发式搜索算法。蚁群算法不仅能够智能搜索、全局优化，而且具有稳健性A、鲁棒性B、正反馈、分布式计算、易与其它算法结合等特点。利用正反馈原理，可以加快进化过程；分布式计算使该算法易于并行实现，个体之间不断进行信息交流和传递，有利于找到较好的解，不容易陷入局部最优；该算法易与多种启发式算法结合，可改善算法的性能；由于鲁棒性强，故在基本蚁群算法模型的基础上进行修改，便可用于其它问题。因此，蚁群算法的问世为诸多领域解决复杂优化

4、问题提供了有力的工具。TSP问题，又称旅行商问题，就是一个销售商从n个城市中的某一城市出发，不重复地走完其余n﹣1个城市并回到原出发点，在所有可能的路径中求出路径长度最短的一条。它是组合优化中研究最多的问题之一，是一个经典的NP难题。第二章蚁群算法的基本原理和模型132.1蚁群算法的基本原理蚁群系统本来是生物学家为更好揭示昆虫的交互作用而提出的一种昆虫自组织模式。尽管建立这种模式的初衷是为了帮助人们去理解这类昆虫的复杂行为，蚂蚁也不可能从这些解释中获益，但是数学及计算机方面的专家和工程师却把这种超越生物本身的模型转化成了一项有用的优化和控制算法

5、!蚁群算法，也称蚁群系统（AntColonySystem,ACS）。蚁群优化（AntColonyOptimization,ACO）是该系统的核心内容，其原理可大致描述如下：蚂蚁属于群居昆虫，个体行为极其简单，而群体行为却相当复杂。相互协作的一群蚂蚁很容易找到从蚁巢到食物源的最短路径，而单个蚂蚁则不能。此外，蚂蚁还能够适应环境的变化，例如在蚁群的运动路线上突然出现障碍物时，它们能够很快地重新找到最优路径。人们通过大量的研究发现，蚂蚁个体之间是通过在其所经过的路上留下一种可称之为“信息素”（Pheromone）的物质来进行信息传递的。随后的蚂蚁遇到

6、信息素时，不仅能检测出该物质的存在以及量的多少，而且可根据信息素的浓度来指导自己对前进方向的选择。同时，该物质随着时间的推移会逐渐挥发掉，于是路径的长短及该路径上通过的蚂蚁的多少就对残余信息素的强度产生影响，反过来信息素的强弱又指导着其它蚂蚁的行动方向。因此，某一路径上走过的蚂蚁越多，则后来者选择该路径的概率就越大。这就构成了蚂蚁群体行为表现出的一种信息正反馈现象。蚂蚁个体之间就是通过这种信息交流达到最快捷搜索到食物源的目的。图1能更具体地说明蚁群系统的原理。图1蚁群优化系统示意图图中设A是蚁巢，E是食物源，H、C为障碍物，距离为d。由于障碍物

7、的存在，由A外出觅食或由E返回巢穴的蚂蚁只能经由H或C13到达目的地。假设蚂蚁以“1单位长度/R单位时间”的速度往返于A和E，每经过一个单位时间各有30只蚂蚁离开A和E到达B和D(图1a)。初始时，各有30只蚂蚁在B和D点遇到障碍物，开始选择路径。由于此时路径上无信息素，蚂蚁便以相同的概率随机地走两条路中的任意一条，因而15只选往C，15只选往H(图1b)。经过一个单位时间以后，路径BCD被30只蚂蚁爬过，而路径BHD上则只被15只蚂蚁爬过（因BCD距离为1而BHD距离为2），BCD上的信息量是BHD上信息量的两倍。此时，又有30只蚂蚁离开B和

8、D，于是各20只选择往C方向，而另外各10只则选往H(图1c)。这样，更多的信息素量被留在更短的路径BCD上。随着时间的推移和上述过程的重复，短路径上