蚁群算法简述.pptx
《蚁群算法简述.pptx》由会员分享,可在线阅读,更多相关《蚁群算法简述.pptx(36页珍藏版)》请在得力文库 - 分享文档赚钱的网站上搜索。
1、会计学1蚁群算法简述蚁群算法简述1.蚁群算法的提出蚁群算法的提出n n算法的提出蚁群算法(Ant Colony Optimization,ACO),又称蚂蚁算法一种用来在图中寻找优化路径的机率型算法。它由Marco Dorigo于1992年在他的博士论文“Ant system:optimization by a colony of cooperating agents”中提出,其灵感来源于蚂蚁在寻找食物过程中发现路径的行为。最早用于解决著名的旅行商问题(TSP,traveling salesman problem)。第1页/共36页1.蚁群算法的提出蚁群算法的提出n n概念原型概念原型各个蚂蚁
2、在没有事先告诉他们食物在什么地方的前提下开始寻找食物。各个蚂蚁在没有事先告诉他们食物在什么地方的前提下开始寻找食物。当一只找到食物以后,它会向环境释放一种挥发性分泌物当一只找到食物以后,它会向环境释放一种挥发性分泌物pheromone(pheromone(称为信息素称为信息素,该物质随着时间的推移会逐渐挥发消失,信息素浓度的大小表征路径的远近该物质随着时间的推移会逐渐挥发消失,信息素浓度的大小表征路径的远近)来实现的,来实现的,吸引其他的蚂蚁过来,这样越来越多的蚂蚁会找到食物。吸引其他的蚂蚁过来,这样越来越多的蚂蚁会找到食物。有些蚂蚁并没有象其它蚂蚁一样总重复同样的路,他们会另辟蹊径,如果另开
3、辟有些蚂蚁并没有象其它蚂蚁一样总重复同样的路,他们会另辟蹊径,如果另开辟的道路比原来的其他道路更短,那么,渐渐地,更多的蚂蚁被吸引到这条较短的路上来。的道路比原来的其他道路更短,那么,渐渐地,更多的蚂蚁被吸引到这条较短的路上来。最后,经过一段时间运行,就可能会出现一条最短的路径被大多数蚂蚁重复着。最后,经过一段时间运行,就可能会出现一条最短的路径被大多数蚂蚁重复着。第2页/共36页1.蚁群算法的提出蚁群算法的提出n n基本原理基本原理蚁群算法是对自然界蚂蚁的寻径方式进行模似而得出的一种蚁群算法是对自然界蚂蚁的寻径方式进行模似而得出的一种仿生算法。仿生算法。蚂蚁在运动过程中,能够在它所经过的路径
4、上留下一种称之为蚂蚁在运动过程中,能够在它所经过的路径上留下一种称之为外激素外激素(pheromone)(pheromone)的物质进行信息传递,而且蚂蚁在运动过程中的物质进行信息传递,而且蚂蚁在运动过程中能够感知这种物质,并以此指导自己的运动方向,因此由大量蚂能够感知这种物质,并以此指导自己的运动方向,因此由大量蚂蚁组成的蚁群集体行为便表现出一种信息正反馈现象:某一路径蚁组成的蚁群集体行为便表现出一种信息正反馈现象:某一路径上走过的蚂蚁越多,则后来者选择该路径的概率就越大。上走过的蚂蚁越多,则后来者选择该路径的概率就越大。第3页/共36页1.蚁群算法的提出蚁群算法的提出n n简化的蚂蚁寻食过
5、程简化的蚂蚁寻食过程蚂蚁从蚂蚁从A A点出发,速度相同,食物在点出发,速度相同,食物在DD点,可能随机选择路线点,可能随机选择路线ABDABD或或ACDACD。假设初。假设初始时每条分配路线一只蚂蚁,每个时间单位行走一步,本图为经过始时每条分配路线一只蚂蚁,每个时间单位行走一步,本图为经过9 9个时间单位时的情形:个时间单位时的情形:走走ABDABD的蚂蚁到达终点,而走的蚂蚁到达终点,而走ACDACD的蚂蚁刚好走到的蚂蚁刚好走到C C点,为一半路程。点,为一半路程。第4页/共36页1.蚁群算法的提出蚁群算法的提出本图为从开始算起,经过本图为从开始算起,经过1818个时间单位时的情形:走个时间单
6、位时的情形:走ABDABD的蚂蚁的蚂蚁到达终点后得到食物又返回了起点到达终点后得到食物又返回了起点A A,而走,而走ACDACD的蚂蚁刚好走到的蚂蚁刚好走到DD点。点。第5页/共36页1.蚁群算法的提出蚁群算法的提出假设蚂蚁每经过一处所留下的信息素为一个单位,则经过假设蚂蚁每经过一处所留下的信息素为一个单位,则经过3636个时间单位后,所有个时间单位后,所有开始一起出发的蚂蚁都经过不同路径从开始一起出发的蚂蚁都经过不同路径从DD点取得了食物,此时点取得了食物,此时ABDABD的路线往返了的路线往返了2 2趟,每趟,每一处的信息素为一处的信息素为4 4个单位,而个单位,而 ACDACD的路线往返
7、了一趟,每一处的信息素为的路线往返了一趟,每一处的信息素为2 2个单位,其比个单位,其比值为值为2 2:1 1。寻找食物的过程继续进行,则按信息素的指导,蚁群在寻找食物的过程继续进行,则按信息素的指导,蚁群在ABDABD路线上增派一只蚂蚁(共路线上增派一只蚂蚁(共2 2只),而只),而ACDACD路线上仍然为一只蚂蚁。再经过路线上仍然为一只蚂蚁。再经过3636个时间单位后,两条线路上的信息素单个时间单位后,两条线路上的信息素单位积累为位积累为1212和和4 4,比值为,比值为3 3:1 1。若按以上规则继续,蚁群在若按以上规则继续,蚁群在ABDABD路线上再增派一只蚂蚁(共路线上再增派一只蚂蚁
8、(共3 3只),而只),而ACDACD路线上仍路线上仍然为一只蚂蚁。再经过然为一只蚂蚁。再经过3636个时间单位后,两条线路上的信息素单位积累为个时间单位后,两条线路上的信息素单位积累为2424和和6 6,比值为,比值为4 4:1 1。若继续进行,则按信息素的指导,最终所有的蚂蚁会放弃若继续进行,则按信息素的指导,最终所有的蚂蚁会放弃ACDACD路线,而都选择路线,而都选择ABDABD路路线。这也就是前面所提到的正反馈效应。线。这也就是前面所提到的正反馈效应。第6页/共36页1.蚁群算法的提出蚁群算法的提出n n人工蚁群算法人工蚁群算法基于以上蚁群寻找食物时的最优路径选择问题,可以构造人工蚁基
9、于以上蚁群寻找食物时的最优路径选择问题,可以构造人工蚁群,来解决最优化问题,如群,来解决最优化问题,如TSPTSP问题。问题。人工蚁群中把具有简单功能的工作单元看作蚂蚁。二者的相似之人工蚁群中把具有简单功能的工作单元看作蚂蚁。二者的相似之处在于都是优先选择信息素浓度大的路径。较短路径的信息素浓度高,处在于都是优先选择信息素浓度大的路径。较短路径的信息素浓度高,所以能够最终被所有蚂蚁选择,也就是最终的优化结果。所以能够最终被所有蚂蚁选择,也就是最终的优化结果。两者的区别在于人工蚁群有一定的记忆能力,能够记忆已经访问两者的区别在于人工蚁群有一定的记忆能力,能够记忆已经访问过的节点。同时,人工蚁群再
10、选择下一条路径的时候是按一定算法规律过的节点。同时,人工蚁群再选择下一条路径的时候是按一定算法规律有意识地寻找最短路径,而不是盲目的。例如在有意识地寻找最短路径,而不是盲目的。例如在TSPTSP问题中,可以预先问题中,可以预先知道当前城市到下一个目的地的距离。知道当前城市到下一个目的地的距离。第7页/共36页1.蚁群算法的提出蚁群算法的提出n n1)1)标有距离的路径图标有距离的路径图标有距离的路径图标有距离的路径图n n2)2)在在在在0 0时刻,路径上没有信息素累积,蚂蚁选择路径为任意时刻,路径上没有信息素累积,蚂蚁选择路径为任意时刻,路径上没有信息素累积,蚂蚁选择路径为任意时刻,路径上没
11、有信息素累积,蚂蚁选择路径为任意n n3)3)在在在在1 1时刻,路径上信息素堆积,短边信息素多与长边,所以蚂蚁更倾向于选择时刻,路径上信息素堆积,短边信息素多与长边,所以蚂蚁更倾向于选择时刻,路径上信息素堆积,短边信息素多与长边,所以蚂蚁更倾向于选择时刻,路径上信息素堆积,短边信息素多与长边,所以蚂蚁更倾向于选择ABCDEABCDE第8页/共36页2.蚁群算法的特征蚁群算法的特征n n蚁群算法蚁群算法采用了分布式正反馈并行计算机制采用了分布式正反馈并行计算机制,易于与其他方法结合易于与其他方法结合,并具有较强的鲁棒性。并具有较强的鲁棒性。n n(1 1)其原理是一种正反馈机制或称增强型学习系
12、统;)其原理是一种正反馈机制或称增强型学习系统;)其原理是一种正反馈机制或称增强型学习系统;)其原理是一种正反馈机制或称增强型学习系统;它通过信息素的不断更新达到最终收敛它通过信息素的不断更新达到最终收敛于最优路径上;于最优路径上;n n(2 2)它是一种通用型随机优化方法;)它是一种通用型随机优化方法;)它是一种通用型随机优化方法;)它是一种通用型随机优化方法;但人工蚂蚁决不是对实际蚂蚁的一种简单模拟,它融进但人工蚂蚁决不是对实际蚂蚁的一种简单模拟,它融进了人类的智能;了人类的智能;n n(3 3)它是一种分布式的优化方法;)它是一种分布式的优化方法;)它是一种分布式的优化方法;)它是一种分
13、布式的优化方法;不仅适合目前的串行计算机,而且适合未来的并行计算机;不仅适合目前的串行计算机,而且适合未来的并行计算机;n n(4 4)它是一种全局优化的方法;)它是一种全局优化的方法;)它是一种全局优化的方法;)它是一种全局优化的方法;不仅可用于求解单目标优化问题,而且可用于求解多目标优不仅可用于求解单目标优化问题,而且可用于求解多目标优化问题;化问题;n n(5 5)它是一种启发式算法;)它是一种启发式算法;)它是一种启发式算法;)它是一种启发式算法;计算复杂性为计算复杂性为 O O(NC*m*n(NC*m*n2 2),其中,其中NC NC 是迭代次数,是迭代次数,m m 是蚂蚁数目,是蚂
14、蚁数目,n n 是目的节点数目。是目的节点数目。第9页/共36页2.蚁群算法的特征蚁群算法的特征下面是对蚁群算法的进行过程中采用的规则进行的一些说明。下面是对蚁群算法的进行过程中采用的规则进行的一些说明。n n范围范围范围范围蚂蚁观察到的范围是一个方格世界,蚂蚁有一个参数为速度半径(一般是蚂蚁观察到的范围是一个方格世界,蚂蚁有一个参数为速度半径(一般是3 3),那么它能),那么它能观察到的范围就是观察到的范围就是3*33*3个方格世界,并且能移动的距离也在这个范围之内。个方格世界,并且能移动的距离也在这个范围之内。n n环境环境环境环境蚂蚁所在的环境是一个虚拟的世界,其中有障碍物,有别的蚂蚁,
15、还有信息素,信息素有蚂蚁所在的环境是一个虚拟的世界,其中有障碍物,有别的蚂蚁,还有信息素,信息素有两种,一种是找到食物的蚂蚁洒下的食物信息素,一种是找到窝的蚂蚁洒下的窝的信息素。每个两种,一种是找到食物的蚂蚁洒下的食物信息素,一种是找到窝的蚂蚁洒下的窝的信息素。每个蚂蚁都仅仅能感知它范围内的环境信息。环境以一定的速率让信息素消失。蚂蚁都仅仅能感知它范围内的环境信息。环境以一定的速率让信息素消失。n n觅食规则觅食规则觅食规则觅食规则在每只蚂蚁能感知的范围内寻找是否有食物,如果有就直接过去。否则看是否有信息素,在每只蚂蚁能感知的范围内寻找是否有食物,如果有就直接过去。否则看是否有信息素,并且比较
16、在能感知的范围内哪一点的信息素最多,这样,它就朝信息素多的地方走,并且每只蚂并且比较在能感知的范围内哪一点的信息素最多,这样,它就朝信息素多的地方走,并且每只蚂蚁都会以小概率犯错误,从而并不是往信息素最多的点移动。蚂蚁找窝的规则和上面一样,只不蚁都会以小概率犯错误,从而并不是往信息素最多的点移动。蚂蚁找窝的规则和上面一样,只不过它对窝的信息素做出反应,而对食物信息素没反应。过它对窝的信息素做出反应,而对食物信息素没反应。第10页/共36页2.蚁群算法的特征蚁群算法的特征n n移动规则移动规则移动规则移动规则每只蚂蚁都朝向信息素最多的方向移,并且,当周围没有信息素指引的时候,蚂蚁会按照自己原来运
17、每只蚂蚁都朝向信息素最多的方向移,并且,当周围没有信息素指引的时候,蚂蚁会按照自己原来运动的方向惯性的运动下去,并且,在运动的方向有一个随机的小的扰动。为了防止蚂蚁原地转圈,它会记住动的方向惯性的运动下去,并且,在运动的方向有一个随机的小的扰动。为了防止蚂蚁原地转圈,它会记住刚才走过了哪些点,如果发现要走的下一点已经在之前走过了,它就会尽量避开。刚才走过了哪些点,如果发现要走的下一点已经在之前走过了,它就会尽量避开。n n避障规则避障规则避障规则避障规则如果蚂蚁要移动的方向有障碍物挡住,它会随机的选择另一个方向,并且有信息素指引的话,它会按如果蚂蚁要移动的方向有障碍物挡住,它会随机的选择另一个
18、方向,并且有信息素指引的话,它会按照觅食的规则行为。照觅食的规则行为。n n信息素规则信息素规则信息素规则信息素规则每只蚂蚁在刚找到食物或者窝的时候撒发的信息素最多,并随着它走远的距离,播撒的信息素越来越每只蚂蚁在刚找到食物或者窝的时候撒发的信息素最多,并随着它走远的距离,播撒的信息素越来越少。少。根据这几条规则,蚂蚁之间并没有直接的关系,但是每只蚂蚁都和环境发生交互,而通过信息素这个根据这几条规则,蚂蚁之间并没有直接的关系,但是每只蚂蚁都和环境发生交互,而通过信息素这个纽带,实际上把各个蚂蚁之间关联起来了。比如,当一只蚂蚁找到了食物,它并没有直接告诉其它蚂蚁这儿纽带,实际上把各个蚂蚁之间关联
19、起来了。比如,当一只蚂蚁找到了食物,它并没有直接告诉其它蚂蚁这儿有食物,而是向环境播撒信息素,当其它的蚂蚁经过它附近的时候,就会感觉到信息素的存在,进而根据信有食物,而是向环境播撒信息素,当其它的蚂蚁经过它附近的时候,就会感觉到信息素的存在,进而根据信息素的指引找到了食物。息素的指引找到了食物。第11页/共36页2.蚁群算法的特征蚁群算法的特征n n基本蚁群算法流程图(详细)1.在初始状态下,一群蚂蚁外出,此时没有信息素,那么各自会随机的选择一条路径。2.在下一个状态,每只蚂蚁到达了不同的点,从初始点到这些点之间留下了信息素,蚂蚁继续走,已经到达目标的蚂蚁开始返回,与此同时,下一批蚂蚁出动,它
20、们都会按照各条路径上信息素的多少选择路线(selection),更倾向于选择信息素多的路径走(当然也有随机性)。3.又到了再下一个状态,刚刚没有蚂蚁经过的路线上的信息素不同程度的挥发掉了(evaporation),而刚刚经过了蚂蚁的路线信息素增强(reinforcement)。然后又出动一批蚂蚁,重复第2个步骤。每个状态到下一个状态的变化称为一次迭代,在迭代多次过后,就会有某一条路径上的信息素明显多于其它路径,这通常就是一条最优路径。第12页/共36页3.蚁群算法的数学模型蚁群算法的数学模型n n一般蚁群算法的框架主要有三个组成部分:1.1.蚁群的活动;2.2.信息素的挥发;3.3.信息素的增
21、强;n n主要体现在转移概率公式和信息素更新公式。第13页/共36页3.蚁群算法的数学模型蚁群算法的数学模型n n蚁群算法数学模型在路径搜索过程中,蚂蚁会根据路径上信息素的多少及距离启发信息进行节点间的转移。蚂蚁在在路径搜索过程中,蚂蚁会根据路径上信息素的多少及距离启发信息进行节点间的转移。蚂蚁在时刻由节点转移到节点的状态转移概率如式所示:时刻由节点转移到节点的状态转移概率如式所示:第14页/共36页3.蚁群算法的数学模型蚁群算法的数学模型另外,为了避免残留信息素过多引起残留信息淹没启发信息另外,为了避免残留信息素过多引起残留信息淹没启发信息,在每只蚂蚁走完一步或者完成对所在每只蚂蚁走完一步或
22、者完成对所有有n n个元素的遍历后个元素的遍历后,要对残留信息进行更新处理。由此要对残留信息进行更新处理。由此,t+n,t+n时刻在路径时刻在路径(i,j)(i,j)上的信息量可按如下规则进上的信息量可按如下规则进行调整其更新规则如下式所示:行调整其更新规则如下式所示:由于信息素更新策略的不同由于信息素更新策略的不同,以及以及城市规模取值在适当范围时,全局搜索能使城市规模取值在适当范围时,全局搜索能使之之得到更优的解,得到更优的解,因此采用因此采用全局信息素更新规则,形式如下:全局信息素更新规则,形式如下:式中,式中,QQ表示蚂蚁循环一周,且在一定程度上影响算法收敛速度的信息素总量;表示蚂蚁循
23、环一周,且在一定程度上影响算法收敛速度的信息素总量;LkLk表示本次循表示本次循环中,蚂蚁环中,蚂蚁k k所走路段的长度。所走路段的长度。第15页/共36页3.蚁群算法的数学模型蚁群算法的数学模型n n蚁群的规模和停止规则蚁群的规模和停止规则n n蚁群大小蚁群大小:一般情况下蚁群中蚂蚁的个数不超过一般情况下蚁群中蚂蚁的个数不超过TSPTSP图中节点的个数。图中节点的个数。n n终止条件终止条件:1 1 给定一个外循环的最大数目,表明已经有足够的蚂蚁工作;给定一个外循环的最大数目,表明已经有足够的蚂蚁工作;2 2 当前最优解连续当前最优解连续K K次相同而停止,其中次相同而停止,其中K K是一个
24、给定的整数,表示算法已经收敛,不再需是一个给定的整数,表示算法已经收敛,不再需要继续;要继续;3 3 目标值控制规则,给定优化问题(目标最小化)的一个下界和一个误差值,当算法得到目标值控制规则,给定优化问题(目标最小化)的一个下界和一个误差值,当算法得到的目标值同下界之差小于给定的误差值时,算法终止。的目标值同下界之差小于给定的误差值时,算法终止。第16页/共36页4.蚁群算法的模型类型蚁群算法的模型类型根据信息素更新策略的不同根据信息素更新策略的不同,M.Dorigo,M.Dorigo 曾提出曾提出3 3 种不同的基本蚁群种不同的基本蚁群算法模型算法模型,其差别在于其差别在于k kij ij
25、(t)(t)求法的不同求法的不同,即即:n nAnt-Cycle Ant-Cycle 模型模型n nAnt-Quantity Ant-Quantity 模型模型n nAnt-Density Ant-Density 模型模型其中其中Ant-antity Ant-antity 模型和模型和Ant-Density Ant-Density 模型利用的是局部信息模型利用的是局部信息;而而Ant-Ant-Cycle Cycle 模型利用的是整体信息模型利用的是整体信息,在求解在求解TSP TSP 时性能较好时性能较好,因此通常采用因此通常采用Ant Ant-Cycle-Cycle 模型模型模型模型作为蚁群
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 算法 简述
限制150内