蚁群算法的基本原理与改进

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,单击此处编辑母版文本样式,第二级,*,*,单击此处编辑母版标题样式,蚁群算法的基本原理与改进,蚁群算法,蚁群算法(ant colony alogrithm)是一种模拟进化算法。,蚁群算法（又称为人工蚁群算法）是由意大利学者M.Dorigo，V.Mahiezzo，A.Colorni等人受到人们对自然界中真是蚁群集体行为的研究成果的启发而首先提出来的。这个算法的主要目的是在图中寻找优化路径的机率算法。,蚁群算法最早是为了解决TSP问题（即旅行商问题）。,TSP问题的要求：,路径的限制是每个城市只能拜访一次；,最后要回到原来出发的城市。,求得的路径路程为所有路径之中的最小值。,概念原型,各个蚂蚁在没有事先告诉他们食物在什么地方的前提下开始寻找食物。,当一只找到食物以后，它会向环境释放一种挥发性分泌物pheromone (称为信息素,该物质随着时间的推移会逐渐挥发消失，信息素浓度的大小表征路径的远近)来实现的，吸引其他的蚂蚁过来，这样越来越多的蚂蚁会找到食物。,有些蚂蚁并没有象其它蚂蚁一样总重复同样的路，他们会另辟蹊径，如果另开辟的道路比原来的其他道路更短，那么，渐渐地，更多的蚂蚁被吸引到这条较短的路上来。,最后，经过一段时间运行，就可能会出现一条最短的路径被大多数蚂蚁重复着。,基本原理,蚁群算法是对自然界蚂蚁的寻径方式进行模似而得出的一种仿生算法。,蚂蚁在运动过程中，能够在它所经过的路径上留下一种称之为外激素(pheromone)的物质进行信息传递，而且蚂蚁在运动过程中能够感知这种物质，并以此指导自己的运动方向，因此由大量蚂蚁组成的蚁群集体行为便表现出一种信息正反馈现象：某一路径上走过的蚂蚁越多，则后来者选择该路径的概率就越大。,假设以下条件：,每个时间单位有30只蚂蚁（A-B）,每个时间单位有30只蚂蚁（E-D）,蚂蚁过后留下的外激素为1,初始时刻，路径无信息存在且位于B和E可以随机选择路径,HD = HB = 1,CD = CB = 0.5,图中的数字表示距离,假设以下条件：,每个时间单位有30只蚂蚁（A-B）,每个时间单位有30只蚂蚁（E-D）,蚂蚁过后留下的外激素为1,初始时刻，路径无信息存在且位于B和E可以随机选择路径,HD = HB = 1,CD = CB = 0.5,备注：,D-H D-C,B-H B-C,图中数字表示蚂蚁的个数,假设以下条件：,每个时间单位有30只蚂蚁（A-B）,每个时间单位有30只蚂蚁（E-D）,蚂蚁过后留下的外激素为1,初始时刻，路径无信息存在且位于B和E可以随机选择路径,HD = HB = 1,CD = CB = 0.5,备注：,D-H D-C,B-H B-C,图中数字表示蚂蚁的个数,下面以TSP为例说明基本蚁群算法模型。,首先将m只蚂蚁随机放置在n个城市，位于城市i的第k只蚂蚁选择下一个城市j的概率为:,蚂蚁算法求解TSP,其中：,表示边（,i,，,j,）上的信息素浓度；,是启发信息，,d,是城市,i,和,j,之间的距离；,和,反映了信息素与启发信息的相对重要性；,表示蚂蚁,k,已经访问过的城市列表。,当所有蚂蚁完成周游后，按以下公式进行信息素更新。,蚂蚁算法求解TSP,其中：,为小于1的常数，表示信息的持久性。,其中：,Q,为常数；,l,k,表示第,k,只蚂蚁在本次迭代中走过的路径，,L,k,为路径长度,。,求解TSP算法步骤,初始化随机放置蚂蚁，为每只蚂蚁建立禁忌表tabu,k,，将初始节点置入禁忌表中;,迭代过程,k=1,while k=ItCount do (执行迭代),for i = 1 to m do (对m只蚂蚁循环),for j = 1 to n - 1 do (对n个城市循环),根据式(1)，采用轮盘赌方法在窗口外选择下一个城市j;,将j置入禁忌表,蚂蚁转移到j;,end for,end for,计算每只蚂蚁的路径长度;,根据式(2)更新所有蚂蚁路径上的信息量;,k = k + 1;,end while,输出结果,结束算法.,基本蚁群算法流程,1. 在初始状态下，一群蚂蚁外出，此时没有信息素，那么各自会随机的选择一条路径。,2. 在下一个状态，每只蚂蚁到达了不同的点，从初始点到这些点之间留下了信息素，蚂蚁继续走，已经到达目标的蚂蚁开始返回，与此同时，下一批蚂蚁出动，它们都会按照各条路径上信息素的多少选择路线(selection)，更倾向于选择信息素多的路径走（当然也有随机性）。,3. 又到了再下一个状态，刚刚没有蚂蚁经过的路线上的信息素不同程度的挥发掉了(evaporation)，而刚刚经过了蚂蚁的路线信息素增强(reinforcement)。然后又出动一批蚂蚁，重复第2个步骤。每个状态到下一个状态的变化称为一次迭代，在迭代多次过后，就会有某一条路径上的信息素明显多于其它路径，这通常就是一条最优路径。,蚁群算法,采用了分布式正反馈并行计算机制, 易于与其他方法结合, 并具有较强的鲁棒性。,（1）其原理是一种正反馈机制或称增强型学习系统；,它通过信息素的不断更新达到最终收敛于最优路径上；,（2）它是一种通用型随机优化方法；,但人工蚂蚁决不是对实际蚂蚁的一种简单模拟，它融进了人类的智能；,（3）它是一种分布式的优化方法；,不仅适合目前的串行计算机，而且适合未来的并行计算机；,（4）它是一种全局优化的方法；,不仅可用于求解单目标优化问题，而且可用于求解多目标优化问题；,（5）它是一种启发式算法；,计算复杂性为,O,(NC*m*n,2,)，其中NC 是迭代次数，m 是蚂蚁数目，n 是目的节点数目。,下面是对蚁群算法的进行过程中采用的规则进行的一些说明。,范围,蚂蚁观察到的范围是一个方格世界，蚂蚁有一个参数为速度半径（一般是3），那么它能观察到的范围就是3*3个方格世界，并且能移动的距离也在这个范围之内。,环境,蚂蚁所在的环境是一个虚拟的世界，其中有障碍物，有别的蚂蚁，还有信息素，信息素有两种，一种是找到食物的蚂蚁洒下的食物信息素，一种是找到窝的蚂蚁洒下的窝的信息素。每个蚂蚁都仅仅能感知它范围内的环境信息。环境以一定的速率让信息素消失。,觅食规则,在每只蚂蚁能感知的范围内寻找是否有食物，如果有就直接过去。否则看是否有信息素，并且比较在能感知的范围内哪一点的信息素最多，这样，它就朝信息素多的地方走，并且每只蚂蚁都会以小概率犯错误，从而并不是往信息素最多的点移动。蚂蚁找窝的规则和上面一样，只不过它对窝的信息素做出反应，而对食物信息素没反应。,移动规则,每只蚂蚁都朝向信息素最多的方向移，并且，当周围没有信息素指引的时候，蚂蚁会按照自己原来运动的方向惯性的运动下去，并且，在运动的方向有一个随机的小的扰动。为了防止蚂蚁原地转圈，它会记住刚才走过了哪些点，如果发现要走的下一点已经在之前走过了，它就会尽量避开。,避障规则,如果蚂蚁要移动的方向有障碍物挡住，它会随机的选择另一个方向，并且有信息素指引的话，它会按照觅食的规则行为。,信息素规则,每只蚂蚁在刚找到食物或者窝的时候撒发的信息素最多，并随着它走远的距离，播撒的信息素越来越少。,根据这几条规则，蚂蚁之间并没有直接的关系，但是每只蚂蚁都和环境发生交互，而通过信息素这个纽带，实际上把各个蚂蚁之间关联起来了。比如，当一只蚂蚁找到了食物，它并没有直接告诉其它蚂蚁这儿有食物，而是向环境播撒信息素，当其它的蚂蚁经过它附近的时候，就会感觉到信息素的存在，进而根据信息素的指引找到了食物。,一般蚁群算法的框架主要有三个组成部分：,蚁群的活动；,信息素的挥发；,信息素的增强；,主要体现在转移概率公式和信息素更新公式。,蚁群的规模和停止规则,蚁群大小:,一般情况下蚁群中蚂蚁的个数不超过TSP图中节点的个数。,终止条件:,1 给定一个外循环的最大数目，表明已经有足够的蚂蚁工作；,2 当前最优解连续K次相同而停止，其中K是一个给定的整数，表示算法已经收敛，不再需要继续；,3 目标值控制规则，给定优化问题（目标最小化）的一个下界和一个误差值，当算法得到的目标值同下界之差小于给定的误差值时，算法终止。,蚁群算法的优点,蚁群算法与其他启发式算法相比，在求解性能上，具有很强的鲁棒性（对基本蚁群算法模型稍加修改，便可以应用于其他问题）和搜索较好解的能力。,蚁群算法是一种基于种群的进化算法，具有本质并行性，易于并行实现。,蚁群算法很容易与多种启发式算法结合，以改善算法性能。,蚁群算法存在的问题,TSP问题是一类经典的组合优化问题，即在给定城市个数和各城市之间距离的条件下，找到一条遍历所有城市且每个城市只能访问一次的总路程最短的路线。蚁群算法在TSP问题应用中取得了良好的效果，但是也存在一些不足：,（1）如果参数设置不当，导致求解速度很慢且所得解的质量特别差。,（2）基本蚁群算法计算量大，求解所需时间较长。,（3）基本蚁群算法中理论上要求所有的蚂蚁选择同一路线，该线路即为所求的最优线路；但在实际计算中，在给定一定循环数的条件下很难达到这种情况。,另一方面，在其它的实际应用中，如图像处理中寻求最优模板问题，我们并不要求所有的蚂蚁都找到最优模板，而只需要一只找到最优模板即可。如果要求所有的蚂蚁都找到最优模板，反而影响了计算效率。,蚁群算法收敛速度慢、易陷入局部最优。蚁群算法中初始信息素匮乏。,蚁群算法一般需要较长的搜索时间，其复杂度可以反映这一点；而且该方法容易出现停滞现象，即搜索进行到一定程度后，所有个体发现的解完全一致，不能对解空间进一步进行搜索，不利于发现更好的解。,算法改进,下面是一些最常用的,变异蚁群算法,1.精英蚂蚁系统,全局最优解决方案在每个迭代以及其他所有的蚂蚁的沉积信息素。,2.最大最小蚂蚁系统（ MMAS）,添加的最大和最小的信息素量 max ， min ，只有全局最佳或迭代最好的巡逻沉积的信息素。所有的边缘都被初始化为max并且当接近停滞时重新初始化为max。,3.蚁群系统,蚁群系统已被提出。,4.基于排序的蚂蚁系统（ ASrank ）,所有解决方案都根据其长度排名。然后为每个解决方案衡量信息素的沉积量，最短路径相比较长路径的解沉积了更多的信息素。,5.连续正交蚁群（COAC）,COAC的信息素沉积机制能使蚂蚁协作而有效地寻解。 利用正交设计方法，在可行域的蚂蚁可以使用增大的全局搜索能力和精度，快速、高效地探索他们选择的区域。 正交设计方法和自适应半径调整方法也可推广到其他优化算法中，在解决实际问题施展更大的威力。,Thank you ！,