蚁群算法

优化理论与应用——蚁群算法目录一．蚁群算法简介...........................................................................................................................3二．基本蚁群算法模型...................................................................................................................41.蚁群算法的生物学模型........................................................................................................42.蚁群算法的公式介绍............................................................................................................63.基本蚁群算法的实现步骤....................................................................................................8三．蚁群算法的特征.......................................................................................................................91.算法的优点............................................................................................................................92.算法的缺陷..........................................................................................................................11四．算法的发展与展望.................................................................................................................12一．蚁群算法简介蚁群算法(antcolonyoptimization,ACO)，又称蚂蚁算法，是一种用来在图中寻找优化路径的机率型算法。它由MarcoDorigo于1992年在他的博士论文中提出，其灵感来源于蚂蚁在寻找食物过程中发现路径的行为。蚁群算法是一种随机搜索算法，它建立在对自然界里蚂蚁群落的集体出外寻找食物的行为上的研究，模拟出真实的蚁群共同寻找食物的全过程。自然界的蚂蚁在觅食过程中，能在其经过的路径上分泌一种具有气味的化学物质，称为信息素（Pheromone），蚂蚁间通过这种信息素来进行信息传递，并指导自己的运动方向。蚂蚁在走过的路径上留下信息素，同时信息素随着时间的消逝会逐渐挥发，信息素浓度越高的路径吸引的蚂蚁越多，而在其中一条寻找食物的道路上走过的蚂蚁越多，那么这条寻找食物的道路上，蚂蚁留下的信息素也就越多，后来蚂蚁选择该路径的概率也就越大，从而增加了这条道路被选择的可能性。随着时间的推移，蚂蚁就会集中到信息素浓度最大的一条路径上，而这条路径就是从蚁巢到食物源的最短路径。通过仿真模拟实际蚂蚁的觅食行为而提出的蚁群算法在许多相当困难的组合优化问题的求解中体现了极强的寻优能力和较好的性能。其思想在于由若干个蚂蚁共同实践道路，通过在各个答案路途上遗留信息素提高寻找食物的质量，进而使该寻找食物路径为最佳路线的目的。蚁群算法在很多领域上都可以应用，利用蚁群算法可以求得TSP问题的最短路径。而且蚁群算法可以与其他智能算法结合，使其具有更大的应用价值。从蚁群算法提出到现在，无论是在理论还是在实践等各个方面都取得了长足的科研进展，近些年来各个行业对蚁群算法的研究成果都是在稳步的增长中。蚁群算法的应用范围几乎涉及到各个优化领域，而且还出现了蚁群算法的仿生硬件。蚁群算法已经显示出强大的生命力和广阔的发展前景。二．基本蚁群算法模型1.蚁群算法的生物学模型前面已经介绍过蚁群算法来源于自然界的蚂蚁的觅食行为。下面我们用图来解释蚂蚁是如何在寻找食物过程中搜索出既是最短也是最佳路线的。如图2.1就是蚂蚁在寻找食物过程中从蚁穴到食物点之间的路途。图2.1蚂蚁寻食的初始状态假定这时候在蚁穴和食物点之间，突然出现阻断物将路途阻断（即图2.2），这时候选择是件困难的事情，因为没有以前的任何信息.留给这个去寻找食物的蚂蚁。所以蚁群的蚂蚁就会向左向右各一定的比率选择路线（即图2.3），但是由于肯定有一各选择的路线是短的，那么这些选择短路线的蚂蚁就会更早的寻找到食物，同样，他们返回的路线也是短的，这样就总是提前返回蚂蚁穴。慢慢的，在寻找食物的过程中，短路线上的蚂蚁就会越来越多，那么它们在这条短路线上所留下的信息也就会越来越多，循环下来的结果就是蚁群中的所有蚂蚁都会选择这个距离短的线路，如图4.4所示。图2.2初始路径被障碍物阻拦图2.3蚂蚁绕过障碍物的左右觅食图2.4蚂蚁选择距离短的线路觅食2.蚁群算法的公式介绍TSP问题又称为旅行商问题，是数学领域中著名问题之一。假设有一个旅行商人要拜访n个城市，他必须选择要走的路径，路径的限制是每个城市只能拜访一次，而且最后要回到原来出发的城市。那么计算出来的路程就是路径的选择目标在所有之中的那个最小的。在TSP问题中，城市数目称为该问题的阶数。我们通过蚂蚁算法求解平面上履行商问题，来说明基本蚁群算法的原理。蚂蚁k(k=1,2,3....n)在运动过程中，运动转移的方向由各条路径上的信息量浓度决定。为方便记录可用tabuk(k=1,2,3....n)来记录第k只蚂蚁当前已走过的所有节点，这里可以称存放节点的表为禁忌表；这个存放节点的集合会随着蚂蚁的运动动态的调整。在算法的搜索过程中，蚂蚁会智能地选择下一步所要走的路径。设m表示蚂蚁总数量，用dij表示节点i和节点j之间的距离,表示在t时刻ij连线上的信息素浓度。在初始时刻，m只蚂蚁会被随机地放置，各路径上的初始信息素浓度是相同的。在t时刻，蚂蚁k从节点i转移到节点j的状态转移概率为其中，表示蚂蚁k下一步可以选择的所有节点，C为全部节点集合；α为信息启发式因子，在算法中代表轨迹相对重要程度，反映路径上的信息量对蚂蚁选择路径所起的影响程度，该值越大，蚂蚁间的协作性就越强；β可称为期望启发式因子，在算法中代表能见度的相对重要性。是启发函数，在算法中表示由节点i转移到节点j的期望程度，通常可取。在算法运行时每只蚂蚁将根据(2-1)式进行搜索前进。在蚂蚁运动过程中，为了避免在路上残留过多的信息素而使启发信息被淹没，在每只蚂蚁遍历完成后，要对残留信息进行更新处理。由此，在t+n时刻,路径(i,j)上信息调整如下在式中，常数）（1,0表示信息素挥发因子,表示路径上信息量的损耗程度,的大小关系到算法的全局搜索能力和收敛速度，则可用1代表信息素残留因子,表示一次寻找结束后路径(i,j)的信息素增量。在初始时刻,表示第k只蚂蚁在本次遍历结束后路径(i,j)的信息素。由于信息素更新策略有所不同，有三种不同的基本蚁群算法模型，分别记为“蚁周系统”(Ant-Cycle)模型、“蚁量系统”(Ant-Quantity)模型及“蚁密系统”(Ant-Density)模型，三种模型求解方式存在不同。（1）“蚁周系统”(Ant-Cycle)模型（2）“蚁量系统”(Ant-Quantity)模型（3）“蚁密系统”(Ant-Density)模型从上边各公式可以看出三种模型的主要区别是：“蚁量系统”和“蚁密系统”中，信息素是在蚂蚁完成一步后更新的，即采用的是局部信息；而在“蚁周系统”中路径中信息素是在蚂蚁完成一个循环后更新的，即应用的是整体信息。在一系列标准测试问题上运行的实验表明，“蚁周系统”算法的性能优于其他两种算法。因此，对蚂蚁系统的研究正朝着更好地了解“蚁周系统”特征的方向发展。3.基本蚁群算法的实现步骤我们采用的是信息素延迟更新方式。算法实现步骤如下：1．参数初始化，设置城市间初始信息量。2．分配蚂蚁到各个城市上，修改蚂蚁禁忌表tabu。3．根据选择概率公式（2-1）计算各城市间移动概率。4．每个蚂蚁k(k=1,2,…,M)根据移动公式选择城市j并前进，修改蚂蚁禁忌表tabu。5.若蚂蚁遍历完所有城市则执行第6步，否则执行第4步。6．计算每只蚂蚁所走的回路距离，根据公式2-2、公式2-3、公式2-4计算并更新各城市间信息素τ。7.若满足循环条件则结束循环并产生结果同时输出，要不就删除每个蚂蚁的禁忌表而且跳回到第二步。三．蚁群算法的特征1.算法的优点（1）该算法其实是一种可以单独运行的计算方法。组织的两个基本分类，其区别在于，组织力或组织指令来自于哪里，是从system的里面还是来自于system的外皮，如果在system里面的是自组织，那么可以知道system外部的就是非自组织，在取得空间的、time或者，功能结构的方式，system也不存在受到其它的干扰，这样我们就能把系统当成是自我组织的。这样在不受到其它干扰的情况下单独运算就让整个系统规则了。（2）蚁群算法是一种正反馈的算法。寻找食物的蚂蚁之所以找到那条最佳线路，其根本原因就是不断的有之前的蚂蚁在摸索中积累了大量的信息，这样信息素的积累就产生了一个正反馈的过程。对蚁群算法来说，刚开始时候各个线路都是均衡的也很稳定，但是如果中央处理部位的差错，造成了每个单独线路上轨迹浓度不相同，蚂蚁构造的答案就分出了好坏，那么整个算法给中央处理器回复的方式就是那条最佳线路上经过时候留下更多的信息素，这些后来增加的信息素给了其他蚂蚁更强的信号，使大量蚂蚁从这条路线经过，这个正反馈的过程就让刚开始线路的差异开始放大，同时整个蚁群的重心也就向这条最佳线路偏移。（3）粗硬性是蚁群算法所特有的较强特性。普通计算方法对开始阶段的路线要求就很高，蚁群算法就刚刚相反，就是蚁群算法得到答案的过程不是从最开始就选择出比较好的线路，同时寻找过程也不用再进行额外的人工调整。还有一点，蚁群算法只有三、四个参数，相当简单，方便把蚁群算法快速使用在别的类型的组合优化问题上。（4）从基本上来看，蚁群算法只是一个简单的并行类算法。开始时每只蚂蚁寻找食物的路线只有一条，后面的蚂蚁只是靠前面的蚂蚁留下的信息素，来进行联系。那么这个蚁群算法我们就只能当做一个多项代理的分布式系统，，不光让算法的可靠性增加，也让这个算法可以进行整个蚁群的全部搜索能力。2.算法的缺陷（1）这种算法可能花费漫长的时间进行寻找。蚂蚁群落中每一个单独的蚂蚁运动都不是有序的，蚂蚁虽然通过遗留下来的信息素找到那个寻找食物的最佳路线前进，可是如果群体数量很多时，那么就不易在少量的时间内从大量没有次序的寻找食物的路线里挑出一条又好又快的路线。其实这是由于在发展的开始阶段，每个寻找食物路线上的蚂蚁们留下的信息素差别不大，因为还在摸索阶段，走那条线路的蚂蚁数量还很平均，不过在不断有走过那条最佳路线的蚂蚁将信息不断反馈到其它蚂蚁，那么在那条最佳线路上的蚂蚁就会逐渐增多，这样也要通过一定的时候慢慢的在这条最佳线路上积累大量的蚂蚁留下的信息，才能使这条线路区别于其它寻找食物的线路，一直到所有的蚂蚁只走这一条线路，那么这个过程就需要相当的时间来积累。（2）这里我们所分析的蚁群算法只是很粗糙的模拟蚁群寻找食物的过程，现实生活里蚂蚁寻找食物的过程肯定是要复杂的多，比如增加蚂蚁搬运食物的距离和