蚁群算法简述PPT课件.ppt
《蚁群算法简述PPT课件.ppt》由会员分享,可在线阅读,更多相关《蚁群算法简述PPT课件.ppt(38页珍藏版)》请在咨信网上搜索。
1、蚁群算法简述n1.蚁群算法的提出n2.蚁群算法的特征n3.蚁群算法的数学模型n4.蚁群算法的模型类型n5.蚁群算法的优缺点n6.蚁群算法所解决的问题n7.蚁群算法的应用n8.蚁群算法的研究方向(发展方向)11.蚁群算法的提出n算法的提出蚁群算法(Ant Colony Optimization,ACO),又称蚂蚁算法一种用来在图中寻找优化路径的机率型算法。它由Marco Dorigo于1992年在他的博士论文“Ant system:optimization by a colony of cooperating agents”中提出,其灵感来源于蚂蚁在寻找食物过程中发现路径的行为。最早用于解决著名
2、的旅行商问题(TSP,traveling salesman problem)。21.蚁群算法的提出n概念原型各个蚂蚁在没有事先告诉他们食物在什么地方的前提下开始寻找食物。当一只找到食物以后,它会向环境释放一种挥发性分泌物pheromone(称为信息素,该物质随着时间的推移会逐渐挥发消失,信息素浓度的大小表征路径的远近)来实现的,吸引其他的蚂蚁过来,这样越来越多的蚂蚁会找到食物。有些蚂蚁并没有象其它蚂蚁一样总重复同样的路,他们会另辟蹊径,如果另开辟的道路比原来的其他道路更短,那么,渐渐地,更多的蚂蚁被吸引到这条较短的路上来。最后,经过一段时间运行,就可能会出现一条最短的路径被大多数蚂蚁重复着。3
3、1.蚁群算法的提出n基本原理蚁群算法是对自然界蚂蚁的寻径方式进行模似而得出的一种仿生算法。蚂蚁在运动过程中,能够在它所经过的路径上留下一种称之为外激素(pheromone)的物质进行信息传递,而且蚂蚁在运动过程中能够感知这种物质,并以此指导自己的运动方向,因此由大量蚂蚁组成的蚁群集体行为便表现出一种信息正反馈现象:某一路径上走过的蚂蚁越多,则后来者选择该路径的概率就越大。41.蚁群算法的提出n简化的蚂蚁寻食过程蚂蚁从A点出发,速度相同,食物在D点,可能随机选择路线ABD或ACD。假设初始时每条分配路线一只蚂蚁,每个时间单位行走一步,本图为经过9个时间单位时的情形:走ABD的蚂蚁到达终点,而走A
4、CD的蚂蚁刚好走到C点,为一半路程。51.蚁群算法的提出本图为从开始算起,经过18个时间单位时的情形:走ABD的蚂蚁到达终点后得到食物又返回了起点A,而走ACD的蚂蚁刚好走到D点。61.蚁群算法的提出假设蚂蚁每经过一处所留下的信息素为一个单位,则经过36个时间单位后,所有开始一起出发的蚂蚁都经过不同路径从D点取得了食物,此时ABD的路线往返了2趟,每一处的信息素为4个单位,而 ACD的路线往返了一趟,每一处的信息素为2个单位,其比值为2:1。寻找食物的过程继续进行,则按信息素的指导,蚁群在ABD路线上增派一只蚂蚁(共2只),而ACD路线上仍然为一只蚂蚁。再经过36个时间单位后,两条线路上的信息
5、素单位积累为12和4,比值为3:1。若按以上规则继续,蚁群在ABD路线上再增派一只蚂蚁(共3只),而ACD路线上仍然为一只蚂蚁。再经过36个时间单位后,两条线路上的信息素单位积累为24和6,比值为4:1。若继续进行,则按信息素的指导,最终所有的蚂蚁会放弃ACD路线,而都选择ABD路线。这也就是前面所提到的正反馈效应。71.蚁群算法的提出n人工蚁群算法基于以上蚁群寻找食物时的最优路径选择问题,可以构造人工蚁群,来解决最优化问题,如TSP问题。人工蚁群中把具有简单功能的工作单元看作蚂蚁。二者的相似之处在于都是优先选择信息素浓度大的路径。较短路径的信息素浓度高,所以能够最终被所有蚂蚁选择,也就是最终
6、的优化结果。两者的区别在于人工蚁群有一定的记忆能力,能够记忆已经访问过的节点。同时,人工蚁群再选择下一条路径的时候是按一定算法规律有意识地寻找最短路径,而不是盲目的。例如在TSP问题中,可以预先知道当前城市到下一个目的地的距离。81.蚁群算法的提出n1)标有距离的路径图n2)在0时刻,路径上没有信息素累积,蚂蚁选择路径为任意n3)在1时刻,路径上信息素堆积,短边信息素多与长边,所以蚂蚁更倾向于选择ABCDE92.蚁群算法的特征n蚁群算法采用了分布式正反馈并行计算机制,易于与其他方法结合,并具有较强的鲁棒性。n(1)其原理是一种正反馈机制或称增强型学习系统;它通过信息素的不断更新达到最终收敛于最
7、优路径上;n(2)它是一种通用型随机优化方法;但人工蚂蚁决不是对实际蚂蚁的一种简单模拟,它融进了人类的智能;n(3)它是一种分布式的优化方法;不仅适合目前的串行计算机,而且适合未来的并行计算机;n(4)它是一种全局优化的方法;不仅可用于求解单目标优化问题,而且可用于求解多目标优化问题;n(5)它是一种启发式算法;计算复杂性为 O(NC*m*n2),其中NC 是迭代次数,m 是蚂蚁数目,n 是目的节点数目。102.蚁群算法的特征下面是对蚁群算法的进行过程中采用的规则进行的一些说明。n范围蚂蚁观察到的范围是一个方格世界,蚂蚁有一个参数为速度半径(一般是3),那么它能观察到的范围就是3*3个方格世界
8、,并且能移动的距离也在这个范围之内。n环境蚂蚁所在的环境是一个虚拟的世界,其中有障碍物,有别的蚂蚁,还有信息素,信息素有两种,一种是找到食物的蚂蚁洒下的食物信息素,一种是找到窝的蚂蚁洒下的窝的信息素。每个蚂蚁都仅仅能感知它范围内的环境信息。环境以一定的速率让信息素消失。n觅食规则在每只蚂蚁能感知的范围内寻找是否有食物,如果有就直接过去。否则看是否有信息素,并且比较在能感知的范围内哪一点的信息素最多,这样,它就朝信息素多的地方走,并且每只蚂蚁都会以小概率犯错误,从而并不是往信息素最多的点移动。蚂蚁找窝的规则和上面一样,只不过它对窝的信息素做出反应,而对食物信息素没反应。112.蚁群算法的特征n移
9、动规则每只蚂蚁都朝向信息素最多的方向移,并且,当周围没有信息素指引的时候,蚂蚁会按照自己原来运动的方向惯性的运动下去,并且,在运动的方向有一个随机的小的扰动。为了防止蚂蚁原地转圈,它会记住刚才走过了哪些点,如果发现要走的下一点已经在之前走过了,它就会尽量避开。n避障规则如果蚂蚁要移动的方向有障碍物挡住,它会随机的选择另一个方向,并且有信息素指引的话,它会按照觅食的规则行为。n信息素规则每只蚂蚁在刚找到食物或者窝的时候撒发的信息素最多,并随着它走远的距离,播撒的信息素越来越少。根据这几条规则,蚂蚁之间并没有直接的关系,但是每只蚂蚁都和环境发生交互,而通过信息素这个纽带,实际上把各个蚂蚁之间关联起
10、来了。比如,当一只蚂蚁找到了食物,它并没有直接告诉其它蚂蚁这儿有食物,而是向环境播撒信息素,当其它的蚂蚁经过它附近的时候,就会感觉到信息素的存在,进而根据信息素的指引找到了食物。122.蚁群算法的特征n基本蚁群算法流程图(详细)1.在初始状态下,一群蚂蚁外出,此时没有信息素,那么各自会随机的选择一条路径。2.在下一个状态,每只蚂蚁到达了不同的点,从初始点到这些点之间留下了信息素,蚂蚁继续走,已经到达目标的蚂蚁开始返回,与此同时,下一批蚂蚁出动,它们都会按照各条路径上信息素的多少选择路线(selection),更倾向于选择信息素多的路径走(当然也有随机性)。3.又到了再下一个状态,刚刚没有蚂蚁经
11、过的路线上的信息素不同程度的挥发掉了(evaporation),而刚刚经过了蚂蚁的路线信息素增强(reinforcement)。然后又出动一批蚂蚁,重复第2个步骤。每个状态到下一个状态的变化称为一次迭代,在迭代多次过后,就会有某一条路径上的信息素明显多于其它路径,这通常就是一条最优路径。133.蚁群算法的数学模型n一般蚁群算法的框架主要有三个组成部分:1.蚁群的活动;2.信息素的挥发;3.信息素的增强;n主要体现在转移概率公式和信息素更新公式。143.蚁群算法的数学模型n蚁群算法数学模型在路径搜索过程中,蚂蚁会根据路径上信息素的多少及距离启发信息进行节点间的转移。蚂蚁在时刻由节点转移到节点的状
12、态转移概率如式所示:153.蚁群算法的数学模型另外,为了避免残留信息素过多引起残留信息淹没启发信息,在每只蚂蚁走完一步或者完成对所有n个元素的遍历后,要对残留信息进行更新处理。由此,t+n时刻在路径(i,j)上的信息量可按如下规则进行调整其更新规则如下式所示:由于信息素更新策略的不同,以及城市规模取值在适当范围时,全局搜索能使之得到更优的解,因此采用全局信息素更新规则,形式如下:式中,Q表示蚂蚁循环一周,且在一定程度上影响算法收敛速度的信息素总量;Lk表示本次循环中,蚂蚁k所走路段的长度。163.蚁群算法的数学模型n蚁群的规模和停止规则n蚁群大小:一般情况下蚁群中蚂蚁的个数不超过TSP图中节点
13、的个数。n终止条件:1 给定一个外循环的最大数目,表明已经有足够的蚂蚁工作;2 当前最优解连续K次相同而停止,其中K是一个给定的整数,表示算法已经收敛,不再需要继续;3 目标值控制规则,给定优化问题(目标最小化)的一个下界和一个误差值,当算法得到的目标值同下界之差小于给定的误差值时,算法终止。174.蚁群算法的模型类型根据信息素更新策略的不同,M.Dorigo 曾提出3 种不同的基本蚁群算法模型,其差别在于kij(t)求法的不同,即:nAnt-Cycle 模型nAnt-Quantity 模型nAnt-Density 模型其中Ant-antity 模型和Ant-Density 模型利用的是局部信
14、息;而Ant-Cycle 模型利用的是整体信息,在求解TSP 时性能较好,因此通常采用Ant-Cycle 模型作为蚁群算法的基本模型。182024/3/19 周二194.蚁群算法的模型类型nAnt-Cycle模型n式中,Q表示信息素强度,它在一定程度上影响算法的收敛速度;Lk表示第k只蚂蚁在本次循环中所走路径的总长度。204.蚁群算法的模型类型nAnt-Quantity模型n Ant-Density模型 214.蚁群算法的模型类型n区别后两个式子中利用的是局部信息,即蚂蚁完成一步后更新路径上的信息素;而第一个式中利用的是全局信息,即蚂蚁完成一个循环后更新所有路径上的信息素,在求解TSP时性能较
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 算法 简述 PPT 课件
1、咨信平台为文档C2C交易模式,即用户上传的文档直接被用户下载,收益归上传人(含作者)所有;本站仅是提供信息存储空间和展示预览,仅对用户上传内容的表现方式做保护处理,对上载内容不做任何修改或编辑。所展示的作品文档包括内容和图片全部来源于网络用户和作者上传投稿,我们不确定上传用户享有完全著作权,根据《信息网络传播权保护条例》,如果侵犯了您的版权、权益或隐私,请联系我们,核实后会尽快下架及时删除,并可随时和客服了解处理情况,尊重保护知识产权我们共同努力。
2、文档的总页数、文档格式和文档大小以系统显示为准(内容中显示的页数不一定正确),网站客服只以系统显示的页数、文件格式、文档大小作为仲裁依据,平台无法对文档的真实性、完整性、权威性、准确性、专业性及其观点立场做任何保证或承诺,下载前须认真查看,确认无误后再购买,务必慎重购买;若有违法违纪将进行移交司法处理,若涉侵权平台将进行基本处罚并下架。
3、本站所有内容均由用户上传,付费前请自行鉴别,如您付费,意味着您已接受本站规则且自行承担风险,本站不进行额外附加服务,虚拟产品一经售出概不退款(未进行购买下载可退充值款),文档一经付费(服务费)、不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
4、如你看到网页展示的文档有www.zixin.com.cn水印,是因预览和防盗链等技术需要对页面进行转换压缩成图而已,我们并不对上传的文档进行任何编辑或修改,文档下载后都不会有水印标识(原文档上传前个别存留的除外),下载后原文更清晰;试题试卷类文档,如果标题没有明确说明有答案则都视为没有答案,请知晓;PPT和DOC文档可被视为“模板”,允许上传人保留章节、目录结构的情况下删减部份的内容;PDF文档不管是原文档转换或图片扫描而得,本站不作要求视为允许,下载前自行私信或留言给上传者【胜****】。
5、本文档所展示的图片、画像、字体、音乐的版权可能需版权方额外授权,请谨慎使用;网站提供的党政主题相关内容(国旗、国徽、党徽--等)目的在于配合国家政策宣传,仅限个人学习分享使用,禁止用于任何广告和商用目的。
6、文档遇到问题,请及时私信或留言给本站上传会员【胜****】,需本站解决可联系【 微信客服】、【 QQ客服】,若有其他问题请点击或扫码反馈【 服务填表】;文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“【 版权申诉】”(推荐),意见反馈和侵权处理邮箱:1219186828@qq.com;也可以拔打客服电话:4008-655-100;投诉/维权电话:4009-655-100。