蚁群算法简述课件

《蚁群算法简述课件》由会员分享，可在线阅读，更多相关《蚁群算法简述课件（36页珍藏版）》请在金锄头文库上搜索。

1、蚁群算法简述,1.蚁群算法的提出 2.蚁群算法的特征 3.蚁群算法的数学模型 4.蚁群算法的模型类型 5.蚁群算法的优缺点 6.蚁群算法所解决的问题 7.蚁群算法的应用 8.蚁群算法的研究方向（发展方向）,1.蚁群算法的提出,算法的提出 蚁群算法（Ant Colony Optimization, ACO），又称蚂蚁算法一种用来在图中寻找优化路径的机率型算法。 它由Marco Dorigo于1992年在他的博士论文“Ant system: optimization by a colony of cooperating agents”中提出，其灵感来源于蚂蚁在寻找食物过程中发现路径的行为。最早用于

2、解决著名的旅行商问题(TSP , traveling salesman problem)。,1.蚁群算法的提出,概念原型 各个蚂蚁在没有事先告诉他们食物在什么地方的前提下开始寻找食物。 当一只找到食物以后，它会向环境释放一种挥发性分泌物pheromone (称为信息素,该物质随着时间的推移会逐渐挥发消失，信息素浓度的大小表征路径的远近)来实现的，吸引其他的蚂蚁过来，这样越来越多的蚂蚁会找到食物。 有些蚂蚁并没有象其它蚂蚁一样总重复同样的路，他们会另辟蹊径，如果另开辟的道路比原来的其他道路更短，那么，渐渐地，更多的蚂蚁被吸引到这条较短的路上来。 最后，经过一段时间运行，就可能会出现一条最短的路径

3、被大多数蚂蚁重复着。,1.蚁群算法的提出,基本原理 蚁群算法是对自然界蚂蚁的寻径方式进行模似而得出的一种仿生算法。 蚂蚁在运动过程中，能够在它所经过的路径上留下一种称之为外激素(pheromone)的物质进行信息传递，而且蚂蚁在运动过程中能够感知这种物质，并以此指导自己的运动方向，因此由大量蚂蚁组成的蚁群集体行为便表现出一种信息正反馈现象：某一路径上走过的蚂蚁越多，则后来者选择该路径的概率就越大。,1.蚁群算法的提出,简化的蚂蚁寻食过程 蚂蚁从A点出发，速度相同，食物在D点，可能随机选择路线ABD或ACD。假设初始时每条分配路线一只蚂蚁，每个时间单位行走一步，本图为经过9个时间单位时的情形：走

4、ABD的蚂蚁到达终点，而走ACD的蚂蚁刚好走到C点，为一半路程。,1.蚁群算法的提出,本图为从开始算起，经过18个时间单位时的情形：走ABD的蚂蚁到达终点后得到食物又返回了起点A，而走ACD的蚂蚁刚好走到D点。,1.蚁群算法的提出,假设蚂蚁每经过一处所留下的信息素为一个单位，则经过36个时间单位后，所有开始一起出发的蚂蚁都经过不同路径从D点取得了食物，此时ABD的路线往返了2趟，每一处的信息素为4个单位，而 ACD的路线往返了一趟，每一处的信息素为2个单位，其比值为2：1。 寻找食物的过程继续进行，则按信息素的指导，蚁群在ABD路线上增派一只蚂蚁（共2只），而ACD路线上仍然为一只蚂蚁。再经过

5、36个时间单位后，两条线路上的信息素单位积累为12和4，比值为3：1。 若按以上规则继续，蚁群在ABD路线上再增派一只蚂蚁（共3只），而ACD路线上仍然为一只蚂蚁。再经过36个时间单位后，两条线路上的信息素单位积累为24和6，比值为4：1。 若继续进行，则按信息素的指导，最终所有的蚂蚁会放弃ACD路线，而都选择ABD路线。这也就是前面所提到的正反馈效应。,1.蚁群算法的提出,人工蚁群算法 基于以上蚁群寻找食物时的最优路径选择问题，可以构造人工蚁群，来解决最优化问题，如TSP问题。 人工蚁群中把具有简单功能的工作单元看作蚂蚁。二者的相似之处在于都是优先选择信息素浓度大的路径。较短路径的信息素浓度

6、高，所以能够最终被所有蚂蚁选择，也就是最终的优化结果。 两者的区别在于人工蚁群有一定的记忆能力，能够记忆已经访问过的节点。同时，人工蚁群再选择下一条路径的时候是按一定算法规律有意识地寻找最短路径，而不是盲目的。例如在TSP问题中，可以预先知道当前城市到下一个目的地的距离。,1.蚁群算法的提出,1) 标有距离的路径图 2) 在0时刻，路径上没有信息素累积，蚂蚁选择路径为任意 3) 在1时刻，路径上信息素堆积，短边信息素多与长边，所以蚂蚁更倾向于选择ABCDE,2.蚁群算法的特征,蚁群算法采用了分布式正反馈并行计算机制, 易于与其他方法结合, 并具有较强的鲁棒性。 （1）其原理是一种正反馈机制或称

7、增强型学习系统；它通过信息素的不断更新达到最终收敛于最优路径上； （2）它是一种通用型随机优化方法；但人工蚂蚁决不是对实际蚂蚁的一种简单模拟，它融进了人类的智能； （3）它是一种分布式的优化方法；不仅适合目前的串行计算机，而且适合未来的并行计算机； （4）它是一种全局优化的方法；不仅可用于求解单目标优化问题，而且可用于求解多目标优化问题； （5）它是一种启发式算法；计算复杂性为 O(NC*m*n2)，其中NC 是迭代次数，m 是蚂蚁数目，n 是目的节点数目。,2.蚁群算法的特征,下面是对蚁群算法的进行过程中采用的规则进行的一些说明。 范围 蚂蚁观察到的范围是一个方格世界，蚂蚁有一个参数为速度半

8、径（一般是3），那么它能观察到的范围就是3*3个方格世界，并且能移动的距离也在这个范围之内。 环境 蚂蚁所在的环境是一个虚拟的世界，其中有障碍物，有别的蚂蚁，还有信息素，信息素有两种，一种是找到食物的蚂蚁洒下的食物信息素，一种是找到窝的蚂蚁洒下的窝的信息素。每个蚂蚁都仅仅能感知它范围内的环境信息。环境以一定的速率让信息素消失。 觅食规则 在每只蚂蚁能感知的范围内寻找是否有食物，如果有就直接过去。否则看是否有信息素，并且比较在能感知的范围内哪一点的信息素最多，这样，它就朝信息素多的地方走，并且每只蚂蚁都会以小概率犯错误，从而并不是往信息素最多的点移动。蚂蚁找窝的规则和上面一样，只不过它对窝的信息

9、素做出反应，而对食物信息素没反应。,2.蚁群算法的特征,移动规则 每只蚂蚁都朝向信息素最多的方向移，并且，当周围没有信息素指引的时候，蚂蚁会按照自己原来运动的方向惯性的运动下去，并且，在运动的方向有一个随机的小的扰动。为了防止蚂蚁原地转圈，它会记住刚才走过了哪些点，如果发现要走的下一点已经在之前走过了，它就会尽量避开。 避障规则 如果蚂蚁要移动的方向有障碍物挡住，它会随机的选择另一个方向，并且有信息素指引的话，它会按照觅食的规则行为。 信息素规则 每只蚂蚁在刚找到食物或者窝的时候撒发的信息素最多，并随着它走远的距离，播撒的信息素越来越少。 根据这几条规则，蚂蚁之间并没有直接的关系，但是每只蚂蚁

10、都和环境发生交互，而通过信息素这个纽带，实际上把各个蚂蚁之间关联起来了。比如，当一只蚂蚁找到了食物，它并没有直接告诉其它蚂蚁这儿有食物，而是向环境播撒信息素，当其它的蚂蚁经过它附近的时候，就会感觉到信息素的存在，进而根据信息素的指引找到了食物。,2.蚁群算法的特征,基本蚁群算法流程图（详细）,1. 在初始状态下，一群蚂蚁外出，此时没有信息素，那么各自会随机的选择一条路径。2. 在下一个状态，每只蚂蚁到达了不同的点，从初始点到这些点之间留下了信息素，蚂蚁继续走，已经到达目标的蚂蚁开始返回，与此同时，下一批蚂蚁出动，它们都会按照各条路径上信息素的多少选择路线(selection)，更倾向于选择信息

11、素多的路径走（当然也有随机性）。3. 又到了再下一个状态，刚刚没有蚂蚁经过的路线上的信息素不同程度的挥发掉了(evaporation)，而刚刚经过了蚂蚁的路线信息素增强(reinforcement)。然后又出动一批蚂蚁，重复第2个步骤。每个状态到下一个状态的变化称为一次迭代，在迭代多次过后，就会有某一条路径上的信息素明显多于其它路径，这通常就是一条最优路径。,3.蚁群算法的数学模型,一般蚁群算法的框架主要有三个组成部分： 蚁群的活动； 信息素的挥发； 信息素的增强； 主要体现在转移概率公式和信息素更新公式。,3.蚁群算法的数学模型,蚁群算法数学模型 在路径搜索过程中，蚂蚁会根据路径上信息素的多

12、少及距离启发信息进行节点间的转移。蚂蚁在时刻由节点转移到节点的状态转移概率如式所示：,3.蚁群算法的数学模型,另外，为了避免残留信息素过多引起残留信息淹没启发信息, 在每只蚂蚁走完一步或者完成对所有n个元素的遍历后, 要对残留信息进行更新处理。由此, t+n时刻在路径(i,j) 上的信息量可按如下规则进行调整其更新规则如下式所示： 由于信息素更新策略的不同, 以及城市规模取值在适当范围时，全局搜索能使之得到更优的解，因此采用全局信息素更新规则，形式如下： 式中，Q表示蚂蚁循环一周，且在一定程度上影响算法收敛速度的信息素总量；Lk表示本次循环中，蚂蚁k所走路段的长度。,3.蚁群算法的数学模型,蚁

13、群的规模和停止规则 蚁群大小: 一般情况下蚁群中蚂蚁的个数不超过TSP图中节点的个数。 终止条件: 1 给定一个外循环的最大数目，表明已经有足够的蚂蚁工作； 2 当前最优解连续K次相同而停止，其中K是一个给定的整数，表示算法已经收敛，不再需要继续； 3 目标值控制规则，给定优化问题（目标最小化）的一个下界和一个误差值，当算法得到的目标值同下界之差小于给定的误差值时，算法终止。,4.蚁群算法的模型类型,根据信息素更新策略的不同, M. Dorigo 曾提出3 种不同的基本蚁群算法模型,其差别在于kij (t)求法的不同,即: Ant - Cycle 模型 Ant - Quantity 模型 An

14、t - Density 模型 其中Ant - antity 模型和Ant - Density 模型利用的是局部信息; 而Ant- Cycle 模型利用的是整体信息, 在求解TSP 时性能较好, 因此通常采用Ant - Cycle 模型作为蚁群算法的基本模型。,4.蚁群算法的模型类型,Ant-Cycle模型 式中，Q表示信息素强度，它在一定程度上影响算法的收敛速度；Lk表示第k只蚂蚁在本次循环中所走路径的总长度。,4.蚁群算法的模型类型,Ant-Quantity模型 Ant-Density模型,4.蚁群算法的模型类型,区别 后两个式子中利用的是局部信息，即蚂蚁完成一步后更新路径上的信息素；而第一

15、个式中利用的是全局信息，即蚂蚁完成一个循环后更新所有路径上的信息素，在求解TSP时性能较好，因此通常采用第一个模型作为蚁群算法的基本模型。,4.蚁群算法的模型类型,下面是一些最常用的变异蚁群算法 1.精英蚂蚁系统 全局最优解决方案在每个迭代以及其他所有的蚂蚁的沉积信息素。 2.最大最小蚂蚁系统（ MMAS） 添加的最大和最小的信息素量 max ， min ，只有全局最佳或迭代最好的巡逻沉积的信息素。所有的边缘都被初始化为max并且当接近停滞时重新初始化为max。 3.蚁群系统 蚁群系统已被提出。 4.基于排序的蚂蚁系统（ ASrank ） 所有解决方案都根据其长度排名。然后为每个解决方案衡量信

16、息素的沉积量，最短路径相比较长路径的解沉积了更多的信息素。 5.连续正交蚁群（COAC） COAC的信息素沉积机制能使蚂蚁协作而有效地寻解。 利用正交设计方法，在可行域的蚂蚁可以使用增大的全局搜索能力和精度，快速、高效地探索他们选择的区域。 正交设计方法和自适应半径调整方法也可推广到其他优化算法中，在解决实际问题施展更大的威力。,5.蚁群算法的优缺点,蚁群算法的优点： 蚁群算法与其他启发式算法相比，在求解性能上，具有很强的鲁棒性（对基本蚁群算法模型稍加修改，便可以应用于其他问题）和搜索较好解的能力。 蚁群算法是一种基于种群的进化算法，具有本质并行性，易于并行实现。 蚁群算法很容易与多种启发式算法结合，以改善算法性能。,5.蚁群算法的优缺点,蚁群算法存在的问题： TSP问题是一类经典的组合优化问题，即在给定城市个数和各城市之间距离的条件下，找到一条遍历所有城市且每个城市只能访问一次的总路程最短的路线。蚁群算法在TSP问题应用中取得了良好的效果，但是也存在一些不足： （1）如果参数设置不当，导致求解速度很慢且所得解的质量特别差。 （2）基本蚁群算法计算量大