蚁群算法简介

蚁群算法简介科科I技l论I坛蚁群算法简介闰大勇 (国防科学技术大学，湖南长沙 410001) 摘要：介绍了一种求解复杂优化问题的启发式算法——蚁群算法，并列举了其在部队物流管理中的应用案例。该方法通过模拟蚁群对“信息素”的控制和利用进行搜索食物的过程，达到求解最优结果的目的。它具有智能搜索、全局优化、稳健性强、易与其它方法结合等优点，适用于解决组合优化问题，包括运输路线优化问题。关键词：蚁群算法；运输路线优化；模型 1概述昆虫在群落一级上的合作基本上是自发组织的，在许多场合中...

科科I技l论I坛蚁群算法简介闰大勇 (国防科学技术大学，湖南长沙 410001) 摘要：介绍了一种求解复杂优化问题的启发式算法——蚁群算法，并列举了其在部队物流管理中的应用案例。该方法通过模拟蚁群对“信息素”的控制和利用进行搜索食物的过程，达到求解最优结果的目的。它具有智能搜索、全局优化、稳健性强、易与其它方法结合等优点，适用于解决组合优化问题，包括运输路线优化问题。关键词：蚁群算法；运输路线优化；模型 1概述昆虫在群落一级上的合作基本上是自发组织的，在许多场合中尽管这些合作可能很简单，但它们却可以解决许多复杂的问题，蚁群算法就是利用群集智能解决组合优化题的典型例子。蚁群算法(Ant Colony Algorithm，ACA)是由意大利学者 M．Dorigo，V．Maniezzo，A．Colorni等人在20世纪 90年代初首先提出来的，它是继模拟退火算法、遗传算法、禁忌搜索算法、人工神经络算法等启发式搜索算法以后的又一种应用于组合优化问题的启发式搜索算法。蚁群算法不仅能够智能搜索、全局优化，而且具有稳健性、正反馈、分布式计算、易与其它算法结合等特点。利用正反馈原理，可以加快进化过程；分布式计算使该算法易于并行实现，个体之间不断进行信息交流和传递，有利于找到较好的解，不容易陷入局部最优；该算法易与多种启发式算法结合，可改善算法的性能；由于稳健性强，故在基本蚁群算法模型的基础上进行修改，便可用于其它问题因此，蚁群算法的问世为诸多领域解决复杂优化问题提供了有力的工具。 2蚁群算法的基本原理蚁群系统本来是生物学家为更好揭示昆虫的交互作用而提出的一种昆虫自组织模式151。尽管建立这种模式的初衷是为了帮助人们去理解这类昆虫的复杂行为，蚂蚁也不可能从这些解释中获益，但是数学及计算机方面的专家和工程师却把这种超越生物本身的模型转化成了一项有用的优化和控制算法——蚁群算法，也称蚁群系统(ACS)，蚁群优化(ACO)是该系统的核心内容，其原理可大致描述如下：蚂蚁属于群居昆虫，个体行为极其简单，而群体行为却相当复杂。相互协作的一群蚂蚁很容易找到从蚁巢到食物源的最短路径，而单个蚂蚁则不能。此外，蚂蚁还能够适应环境的变化，例如在蚁群的运动路线上突然出现障碍物时，它们能够很快地重新找到最优路径。人们通过大量的研究发现，蚂蚁个体之间是通过在其所经过的路上留下一种可称之为 “信息素”(pheromone)的物质来进行信息传递的。随后的蚂蚁遇到信息素时，不仅能检测出该物质的存在以及量的多少，而且可根据信息素的浓度来指导自己对前进方向的选择。同时，该物质随着时间的推移会逐渐挥发掉，于是路径的长短及该路径上通过的蚂蚁的多少就对残余信息素的强度产生影响，反过来信息素的强弱又指导着其它蚂蚁的行动方向。因此，某一路径上走过的蚂蚁越多，则后来者选择该路径的概率就越大。这就构成了蚂蚁群体行为表现的一种信息正反馈现象。蚂蚁个体之间就是通过这种信息交流达到最快捷搜索到食物源的目的。 3蚁群算法模型为模拟蚂蚁的行为，以求解 N个城市的 TSP问题为例。已知有 N个城市，寻找一条访问两个城市之间的最短路径。设蚁群中蚂蚁数量为m，d ：1，2，⋯，N)表示城市 i和j之间的路径长度，此处选用的是无向图G(N，E)，即 d。．=dj ．N是城市个数，E是城市的连通的边的集合。设 B．m表示t时刻位于城市 i的蚂蚁个数，则有 m =Z Bl(0 i=1 Tij(t)表示 t时刻在 ij连线边 e(i,j)J2残留的信息量。初始时刻，在各条路径上的信息量相等，设 T (0)=c(c为常数，通常取为 0)。蚂蚁 k(k=1，2， ⋯ ，m)在运动过程中，根据各条路径上的信息量决定转移方向，t时刻蚂蚁 k由位置 i转移到 i 的概率 pkig0由下式表示：钒：{ 一⋯ 其中，allowedk={N—tabukl表示蚂蚁 k下一步允许选择的城市，而 tabuk表示第 k个蚂蚁的禁忌表，tabu (s)表示禁忌表中第 s个元素；，表示由城市 i转移到城市 i的期望程度f又称可见度)，可根据某种启发式算法具体确定，当． >O 时，表示邻域i处蚂蚁按概率 P。移至邻域 j的概率；当-q。 ≤0时，邻域 i的蚂蚁做邻域搜索，其搜索半径(或步长)为 r；ct、B分别表示蚂蚁在运动过程中所积累的信息及启发式因子在蚂蚁选择路径中所起的不同作用，它们是控制信息激素强度与可见度的相对重要性的参数。可见，转移概率是可见度和t时刻信息激素强度的权衡。与真实蚂蚁系统不同，人工蚁群系统具有一定的记忆功能，用 tabu (k：l，2，⋯，m)记录蚂蚁 k目前已走过的城市。随着时间的推移，以前留下的信息激素逐渐消逝。设信息激素的保留系数为 p(0 总结展望目前，蚁群算法思想在启发式方法范畴内已逐渐成为一个独立的分支，在有关国际会议上多次作为专题加以讨论。但是，蚁群算法还不像其它的启发式算法那样已形成系统的分析方法和具有坚实的数学基础。参数的选择更多的是依靠实验和经验，没有定理来确定。而且它的计算时间偏长，国内外的有关研究仍停留在实验探索阶段，但从当前的应用效果来看，这种模仿自然生物的新型系统寻优思想无疑具有十分光明的前景，更多深入细致的工作还有待于进一步展开。参考文献 [1]段海滨，王道波，朱家强等．蚁群算法原理及应用研究的进展lJI．控制与决策，2004．『21张纪会，徐心和．一种新的进化算法——蚁群算法IJ1．系统工程理论与实践，1999．【3】陈东庆．蚁群算法在军事物流配送中的应用研究『D1．大连理工大学硕士学位论文，2005． [4]马良，姚俭，范炳全．蚂蚁算法在交通配流中的应用『J1_科技通报，20o3． [5]李士勇．蚁群算法及其应用[M】．哈尔滨：哈尔滨工业大学出版社，2004，9．责任编辑：温雪梅 (上接 182页) 重大实绩，可以说好戏连台，先是“规律说”，接着是“文献交流说”，“知识交流说l’’‘‘文献信息交流说”，轮番登场，接着是“信息管理说”，“中介说”，“新技术说”，但无论哪一种学说，都没有形成气候、形成流派，进而去充实、完善各自的学说理论体系。因此，要想走向世界，融人世界图书情报体系乃至领导世界潮流，必须形成中国自己的学术流派，完善自己的理论体现，才能在 2l世纪乃至不远的将来在世界图书情报体系中占有一席之地。责任编辑：温雪梅一 50—

                    本文档为【蚁群算法简介】，请使用软件OFFICE或WPS软件打开。作品中的文字与图均可以修改和编辑，
                    图片更改请在作品中右键图片并更换，文字修改请直接点击文字进行修改，也可以新增和删除文档中的内容。 
 该文档来自用户分享，如有侵权行为请发邮件ishare@vip.sina.com联系网站客服，我们会及时删除。

                    [版权声明] 本站所有资料为用户分享产生，若发现您的权利被侵害，请联系客服邮件isharekefu@iask.cn，我们尽快处理。

                    本作品所展示的图片、画像、字体、音乐的版权可能需版权方额外授权，请谨慎使用。

                    网站提供的党政主题相关内容(国旗、国徽、党徽..)目的在于配合国家政策宣传，仅限个人学习分享使用，禁止用于任何广告和商用目的。
                

下载需要：免费已有0 人下载

立即下载

蚁群算法简介

你可能还喜欢