蚁群算法简述及实现.doc
《蚁群算法简述及实现.doc》由会员分享,可在线阅读,更多相关《蚁群算法简述及实现.doc(6页珍藏版)》请在咨信网上搜索。
1、蚁群算法简述及实现1 蚁群算法的原理分析蚁群算法是受自然界中真实蚁群算法的集体觅食行为的启发而发展起来的一种基于群体的模拟进化算法,属于随机搜索算法,所以它更恰当的名字应该叫“人工蚁群算法”,我们一般简称为蚁群算法。M.Dorigo等人充分的利用了蚁群搜索食物的过程与著名的TSP问题的相似性,通过人工模拟蚁群搜索食物的行为来求解TSP问题。蚂蚁这种社会性动物,虽然个体行为及其简单,但是由这些简单个体所组成的群体却表现出及其复杂的行为特征。这是因为蚂蚁在寻找食物时,能在其经过的路径上释放一种叫做信息素的物质,使得一定范围内的其他蚂蚁能够感觉到这种物质,且倾向于朝着该物质强度高的方向移动。蚁群的集
2、体行为表现为一种正反馈现象,蚁群这种选择路径的行为过程称之为自催化行为。由于其原理是一种正反馈机制,因此也可以把蚁群的行为理解成所谓的增强型学习系统(Reinforcement Learning System)。引用M.Dorigo所举的例子来说明蚁群发现最短路径的原理和机制,见图1所示。假设D和H之间、B和H之间以及B和D之间(通过C)的距离为1,C位于D和B的中央(见图1 (a)。现在我们考虑在等间隔等离散世界时间点(t=0,1,2)的蚁群系统情况。假设每单位时间有30只蚂蚁从A到B,另三十只蚂蚁从E到D,其行走速度都为1(一个单位时间所走距离为1),在行走时,一只蚂蚁可在时刻t留下浓度为
3、1的信息素。为简单起见,设信息素在时间区间(t+1,t+2)的中点(t+1.5)时刻瞬时完全挥发。在t=0时刻无任何信息素,但分别有30只蚂蚁在B、30只蚂蚁在D等待出发。它们选择走哪一条路径是完全随机的,因此在两个节点上蚁群可各自一分为二,走两个方向。但在t=1时刻,从A到B的30只蚂蚁在通向H的路径上(见图1 (b)发现一条浓度为15的信息素,这是由15只从B走向H的先行蚂蚁留下来的;而在通向C的路径上它们可以发现一条浓度为30的信息素路径,这是由15只走向BC的路径的蚂蚁所留下的气息与15只从D经C到达B留下的气息之和(图1 (c)。这时,选择路径的概率就有了偏差,向C走的蚂蚁数将是向H
4、走的蚂蚁数的2倍。对于从E到D来的蚂蚁也是如此。(a) (b) (c)图1 蚁群路径搜索实例这个过程一直会持续到所有的蚂蚁最终都选择了最短的路径为止。这样,我们就可以理解蚁群算法的基本思想:如果在给定点,一只蚂蚁要在不同的路径中选择,那么,那些被先行蚂蚁大量选择的路径(也就是信息素留存较浓的路径)被选中的概率就更大,较多的信息素意味着较短的路径,也就意味着较好的问题回答。2人工蚁群算法描述蚁群算法可以看作为一种基于解空间参数化概率分布模型(Parameterized Probabilistic Model)的搜索算法框架 (Model-based search algorithms)。在蚁群算
5、法中,解空间参数化概率,模型的参数就是信息素,因而这种参数化概率分布模型就是信息素模型。在基于模型的搜索算法框架中,可行解通过在一个解空间参数化概率分布模型上的搜索产生,此模型的参数用以前产生的解来更新,使得在新模型上的搜索能够集中在高质量的解搜索空间内。这种方法的有效性建立在高质量的解总是包含好的解构成元素的假设前提下。通过学习这种解构成元素对解的质量的影响有助于找到一种机制,并通过解构成元素的最佳组合来构造出高质量的解。一般来说,一个记忆模型的搜索算法通常使用以下两步迭代来解决优化问题:1)可行解通过在解空间参数化概率分布模型上的搜索产生。2)用搜索产生的解来更新参数化概率模型,即更新解空
6、间参数化概率分布的参数,使得在新模型上的参数搜索能够集中在高质量的解搜索空间内。在蚁群算法中,基于信息素的解空间参数化概率模型(信息素模型)以解构造图的形式给出。在解构造图上,定义了一种作为随机搜索机制的人工蚁群,蚂蚁通过一种分布在解构造图上被称为信息素的局部信息的指引,在解构造图上移动,从而逐步的构造出问题的可行。信息素与解构造图上的节点或弧相关联,作为解空间参数化概率分布模型的参数。由于TSP问题可以直接的映射为解构造图(城市为节点,城市间的路径为弧,信息素分布在弧上),加之TSP问题也是个NP难题,所以,蚁群算法的大部分应用都集中在TSP问题上。一般而言,用于求解TSP问题、生产调度问题
7、等优化问题的蚁群算法都遵循下面的统一算法框架。算法1:求解组合优化问题的蚁群算法设置参数,初始化信息素踪迹While(不满足条件时)dofor蚁群中的每只蚂蚁for每个解构造步(直到构造出完整的可行解)1)蚂蚁按照信息素及启发式信息的指引构造一步问题的解;2)进行信息素局部更新。(可选)endforendfor1)以某些已获得的解为起点进行邻域(局部)搜索;(可选)2)根据某些已获得的解的质量进行全局信息素更新。endwhileend在算法1中,蚂蚁逐步的构造问题的可行解,在一步解的构造过程中,蚂蚁以概率方式选择信息素强且启发式因子高的弧到达下一个节点,直到不能继续移动为止。此时蚂蚁所走过的路
8、径对应求解问题的一个可行解。局部信息素更新针对蚂蚁当前走过的一步路径上的信息素进行,全局信息素更新是在所有蚂蚁找到可行解之后,根据发现解的质量或当前算法找到的最好解对路径上的信息素进行更新。3 蚁群算法与其他搜索算法比较3.1 蚁群算法与进化算法比较近年来,遗传算法(GA)、进化规划(Evolutionary Planning)、进化策略(Evolutionary Strategies)在理论和应用上发展迅速、效果显著并逐渐走向了融合,形成了一种新颖的模拟进化的计算理论,统称为进化计算(Evolutionary Computation)。因此我们可以用进化计算作为代表与蚁群算法进行比较,从另一
9、个角度来认识蚁群算法,加深对蚁群算法的理解。蚁群算法与进化计算的相似之处有两点:首先,两种算法均采用群体表示问题的解;其次,新群体通过包含在群体中与问题相关的知识来生成。两者的主要区别在于进化计算中所有问题的的知识都包含在当前群体中,而蚁群算法中代表过去所学的知识保存在信息素的踪迹中。3.2 蚁群算法与模拟退火算法比较从模拟退火算法的搜索策略可以看出蚁群算法和模拟退火算法(SA)从本质上来讲是一致的。SA对某个“固体的”一个微观状态i计算其能量Ei的过程与蚂蚁的一次“周游”一样,都是对解空间的一次采样;“退火”与“分泌信息素”都是利用积累信息来增强对子空间的搜索;而“Metropolis准则”
10、和“随机状态转移规则”类似,都是使算法能够跳出局部最优,在一定范围内接受恶化解,搜索新的子空间。因此,SA已经非常成熟的收敛性研究对分析设置蚂蚁规模参数和信息素分布策略对最终解质量的影响有很大的借鉴意义。对于SA的收敛性分析一般分两种情况,齐次Markov链和非齐次Markov链。齐次Markov链的分析结果告诉我们,在任意温度t,SA都达到平衡分布的情况下,当t0时,SA将收敛于全局最优。也就是说,在任意温度t,SA都要遍历整个解空间。那么,如果我们保留sA采样后的当前全局最优解,则即使在任何温度t,SA都会收敛于全局最优。换句话说,对于蚁群算法,如果蚂蚁数量(规模)足够多,能够保证对解空间
11、的遍历,那么即使不用信息素,也能保证全局收敛。不过这种方法显然就是一种盲目随机搜索,没有任何实际的应用价值。对于非其次Markov链的SA,即在某个固定温度t,采样次数有限,而t将无限趋近于0的情况下,结论告诉我们当控制参数序列满足一定条件时,SA才收敛于整体最优解集。其更直接的表述方式是:控制参数t的衰减量与在温度t下的采样数之间存在一种均衡:t的衰减量越大,则在温度艺下的采样数就必须越多;反之,若t的衰减量缓慢,则在每个温度下SA只需进行少量采样。那么。从蚁群算法的角度可以看到:因为蚂蚁的规模实际上影响的只是信息素更新的频率,所以当规模设置较大时,每次更新信息素时,可以以较快的速度拉大不同
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 算法 简述 实现
1、咨信平台为文档C2C交易模式,即用户上传的文档直接被用户下载,收益归上传人(含作者)所有;本站仅是提供信息存储空间和展示预览,仅对用户上传内容的表现方式做保护处理,对上载内容不做任何修改或编辑。所展示的作品文档包括内容和图片全部来源于网络用户和作者上传投稿,我们不确定上传用户享有完全著作权,根据《信息网络传播权保护条例》,如果侵犯了您的版权、权益或隐私,请联系我们,核实后会尽快下架及时删除,并可随时和客服了解处理情况,尊重保护知识产权我们共同努力。
2、文档的总页数、文档格式和文档大小以系统显示为准(内容中显示的页数不一定正确),网站客服只以系统显示的页数、文件格式、文档大小作为仲裁依据,个别因单元格分列造成显示页码不一将协商解决,平台无法对文档的真实性、完整性、权威性、准确性、专业性及其观点立场做任何保证或承诺,下载前须认真查看,确认无误后再购买,务必慎重购买;若有违法违纪将进行移交司法处理,若涉侵权平台将进行基本处罚并下架。
3、本站所有内容均由用户上传,付费前请自行鉴别,如您付费,意味着您已接受本站规则且自行承担风险,本站不进行额外附加服务,虚拟产品一经售出概不退款(未进行购买下载可退充值款),文档一经付费(服务费)、不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
4、如你看到网页展示的文档有www.zixin.com.cn水印,是因预览和防盗链等技术需要对页面进行转换压缩成图而已,我们并不对上传的文档进行任何编辑或修改,文档下载后都不会有水印标识(原文档上传前个别存留的除外),下载后原文更清晰;试题试卷类文档,如果标题没有明确说明有答案则都视为没有答案,请知晓;PPT和DOC文档可被视为“模板”,允许上传人保留章节、目录结构的情况下删减部份的内容;PDF文档不管是原文档转换或图片扫描而得,本站不作要求视为允许,下载前自行私信或留言给上传者【快乐****生活】。
5、本文档所展示的图片、画像、字体、音乐的版权可能需版权方额外授权,请谨慎使用;网站提供的党政主题相关内容(国旗、国徽、党徽--等)目的在于配合国家政策宣传,仅限个人学习分享使用,禁止用于任何广告和商用目的。
6、文档遇到问题,请及时私信或留言给本站上传会员【快乐****生活】,需本站解决可联系【 微信客服】、【 QQ客服】,若有其他问题请点击或扫码反馈【 服务填表】;文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“【 版权申诉】”(推荐),意见反馈和侵权处理邮箱:1219186828@qq.com;也可以拔打客服电话:4008-655-100;投诉/维权电话:4009-655-100。