蚁群算法

《蚁群算法》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、优化理论与应用——蚁群算法目录一．蚁群算法简介3二．基本蚁群算法模型41.蚁群算法的生物学模型42.蚁群算法的公式介绍63.基本蚁群算法的实现步骤9三．蚁群算法的特征101.算法的优点102.算法的缺陷11四．算法的发展与展望12一．蚁群算法简介蚁群算法(antcolonyoptimization,ACO)，又称蚂蚁算法，是一种用来在图中寻找优化路径的机率型算法。它由MarcoDorigo于1992年在他的博士论文中提出，其灵感来源于蚂蚁在寻找食物过程中发现路径的行为。蚁群算法是一种随机搜索算法，它建立在对自然界里蚂蚁群落的集体出外寻找食物的行为上的研究

2、，模拟出真实的蚁群共同寻找食物的全过程。自然界的蚂蚁在觅食过程中，能在其经过的路径上分泌一种具有气味的化学物质，称为信息素（Pheromone），蚂蚁间通过这种信息素来进行信息传递，并指导自己的运动方向。蚂蚁在走过的路径上留下信息素，同时信息素随着时间的消逝会逐渐挥发，信息素浓度越高的路径吸引的蚂蚁越多，而在其中一条寻找食物的道路上走过的蚂蚁越多，那么这条寻找食物的道路上，蚂蚁留下的信息素也就越多，后来蚂蚁选择该路径的概率也就越大，从而增加了这条道路被选择的可能性。随着时间的推移，蚂蚁就会集中到信息素浓度最大的一条路径上，而这条路径就是从蚁巢到食物源的最

3、短路径。通过仿真模拟实际蚂蚁的觅食行为而提出的蚁群算法在许多相当困难的组合优化问题的求解中体现了极强的寻优能力和较好的性能。其思想在于由若干个蚂蚁共同实践道路，通过在各个答案路途上遗留信息素提高寻找食物的质量，进而使该寻找食物路径为最佳路线的目的。蚁群算法在很多领域上都可以应用，利用蚁群算法可以求得TSP问题的最短路径。而且蚁群算法可以与其他智能算法结合，使其具有更大的应用价值。从蚁群算法提出到现在，无论是在理论还是在实践等各个方面都取得了长足的科研进展，近些年来各个行业对蚁群算法的研究成果都是在稳步的增长中。蚁群算法的应用范围几乎涉及到各个优化领域，而

4、且还出现了蚁群算法的仿生硬件。蚁群算法已经显示出强大的生命力和广阔的发展前景。二．基本蚁群算法模型1.蚁群算法的生物学模型前面已经介绍过蚁群算法来源于自然界的蚂蚁的觅食行为。下面我们用图来解释蚂蚁是如何在寻找食物过程中搜索出既是最短也是最佳路线的。如图2.1就是蚂蚁在寻找食物过程中从蚁穴到食物点之间的路途。图2.1蚂蚁寻食的初始状态假定这时候在蚁穴和食物点之间，突然出现阻断物将路途阻断（即图2.2），这时候选择是件困难的事情，因为没有以前的任何信息.留给这个去寻找食物的蚂蚁。所以蚁群的蚂蚁就会向左向右各一定的比率选择路线（即图2.3），但是由于肯定有一各

5、选择的路线是短的，那么这些选择短路线的蚂蚁就会更早的寻找到食物，同样，他们返回的路线也是短的，这样就总是提前返回蚂蚁穴。慢慢的，在寻找食物的过程中，短路线上的蚂蚁就会越来越多，那么它们在这条短路线上所留下的信息也就会越来越多，循环下来的结果就是蚁群中的所有蚂蚁都会选择这个距离短的线路，如图4.4所示。图2.2初始路径被障碍物阻拦图2.3蚂蚁绕过障碍物的左右觅食图2.4蚂蚁选择距离短的线路觅食2.蚁群算法的公式介绍TSP问题又称为旅行商问题，是数学领域中著名问题之一。假设有一个旅行商人要拜访n个城市，他必须选择要走的路径，路径的限制是每个城市只能拜访一次，

6、而且最后要回到原来出发的城市。那么计算出来的路程就是路径的选择目标在所有之中的那个最小的。在TSP问题中，城市数目称为该问题的阶数。我们通过蚂蚁算法求解平面上履行商问题，来说明基本蚁群算法的原理。蚂蚁k(k=1,2,3....n)在运动过程中，运动转移的方向由各条路径上的信息量浓度决定。为方便记录可用tabuk(k=1,2,3....n)来记录第k只蚂蚁当前已走过的所有节点，这里可以称存放节点的表为禁忌表；这个存放节点的集合会随着蚂蚁的运动动态的调整。在算法的搜索过程中，蚂蚁会智能地选择下一步所要走的路径。设m表示蚂蚁总数量，用dij表示节点i和节点j之

7、间的距离,表示在t时刻ij连线上的信息素浓度。在初始时刻，m只蚂蚁会被随机地放置，各路径上的初始信息素浓度是相同的。在t时刻，蚂蚁k从节点i转移到节点j的状态转移概率为 其中，表示蚂蚁k下一步可以选择的所有节点，C为全部节点集合；α为信息启发式因子，在算法中代表轨迹相对重要程度，反映路径上的信息量对蚂蚁选择路径所起的影响程度，该值越大，蚂蚁间的协作性就越强；β可称为期望启发式因子，在算法中代表能见度的相对重要性。是启发函数，在算法中表示由节点i转移到节点j的期望程度，通常可取。在算法运行时每只蚂蚁将根据(2-1)式进行搜索前进。在蚂蚁运动过程中，为了避免

8、在路上残留过多的信息素而使启发信息被淹没，在每只蚂蚁遍历完成后，要对残留信息进行