蚁群算法的原理及其应用

蚁群算法的原理及其应用 蚁群算法的原理及其应用 第18卷第2期 2005年第2期 潍坊教育学院 JOURNALOFWEIFANGEDUCATIONALCOLLEGE Vo1.18No.2 Jun.2005 蚁群算法的原理及其应用 王芳 (华北电力大学计算机科学与 工程 路基工程安全技术交底工程项目施工成本控制工程量增项单年度零星工程技术标正投影法基本原理 学院.河北保定071003) 摘要:蚁群算法是优化领域中新出现的一种仿生进化算法.该算法采用分布式并行 具有较强 计算机制, 的鲁棒性;但有搜索时间较长,易陷入局部最优解的缺点.本文首先讲述蚁群算法的来源和基本原理,然后讨 论蚁群算法的几种改进策略,并简单介绍近年来蚁群算法在许多新领域中的发展应用,最后对今后进一步研 究的方向作了展望. 关键词:蚁群算法;蚂蚁;信息素;优化 中图分类号:TP338文献标识码:A文章编号:1009—2080(2005)02--OO7O—O3 1引言 蚁群算法是群体智能的典型实现,是一种基于种群寻优 的启发式搜索算法.自从M,Dorigo等意大利学者在1991年 首先提出蚁群算法(AntColonySystem.ACS)以来,这种新型 的分布式智能模拟算法已逐渐引起人们的注意并得到广泛的 应用. 蚁群算法不仅能够智能搜索,全局优化,而且具有鲁棒 性,正反馈,分布式计算,易与其它算法结合等特点.M,Dori— go等人将蚁群算法先后应用于旅行商问题(TSP).资源二次 分配问题(QuadraticAssignmentProblem,QAP)等经典优化 问题,得到了较好的效果.在动态环境下,蚁群算法也表现出 高度的灵活性和健壮性,如在集成电路布线 设计 领导形象设计圆作业设计ao工艺污水处理厂设计附属工程施工组织设计清扫机器人结构设计 ,电信路由控 制,交通建模及规划,电力系统优化及故障分析等方面都被认 为是目前较好的算法之一. 2蚊群算法的基本原理 M,Dorigo等人在观察蚂蚁的觅食习性时发现,全盲的蚂 蚁总能找到巢穴与食物源之间的最短路径.蚁群算法的提出 就是借鉴和吸收了现实世界中这种蚂蚁集体寻径的行为特 征:经研究发现,蚂蚁在觅食过程中分泌一种称之为信息紊 (pheromone)的物质,这种物质会随着时间而挥发蚂蚁能利 用信息紊作为媒介与其它蚂蚁进行信息沟通.一条路径上留 下的信息紊浓度的大小与这条路径上通过的蚂蚁数成正比, 当通过的蚂蚁越多,则留下的信息紊就越多,从而导致后来蚂 蚁选择该条路径的概率提高.这样,没有视觉能力的蚂蚁在上 述过程中展现出一种协作的自催化行为能力,蚂蚁正是基于 这种原理建立最短的移动路径.值得指出的是,这种合作基本 上是自组织的,而且每个蚂蚁智能体很简单,蚂蚁群体之所以 能够完成如此复杂的功能,就是"简单规则中的智能涌现" 最初,研究者从实际蚁群引申出"蚁群系统"的概念,建立 这种模式的初衷是为了帮助人们去理解这类昆虫的复杂行 为,后来数学及计算机方面的专家和工程师把这种超越生物 本身的模型转化成了一项有用的优化和控制算法——蚁群算 法,也称为蚁群系统.蚁群算法中对蚂蚁个体的描述大致为: 2.1个体(单个人工蚁)的行为极其简单.而通过个体问 的相互协作,群体行为相当复杂,能完成复杂的任务; 2.2个体不是全盲.而且有一定的记忆能力; 2.3个体能够适应环境的变化. 为了具体说明蚁群系统的原理,下面举出人工蚁群路径 搜索的例子(如图,略). 图(略)中.设A是蚁穴.B是食物源,path1和path2为从 蚁穴绕过障碍物到食物源的两条路径,且设path1的路径长度 为2个单位.path2的路径长度为1个单位.AC,DB的长度远 小于一个单位,忽略不计(如图1(a)所示略).假设每个时间单 位有3O只蚂蚁分别从A,B出发,蚂蚁的行走速度都为1(每单 位时间行走1单位长度),且每只蚂蚁可在时刻t留下浓度为1 的信息素.为了简单起见.只考虑在等间隔离散时间点(t一0, 1.2,…)的蚁群系统情况;且假设信息紊在时刻(t+0.5)瞬时 完全挥发;t:0时刻无任何信息紊. 那么,t一0时刻从A出发的3O只蚂蚁第一次到达C点, 它们随机选择路径,可认为沿两条路径行走的蚂蚁各为15 只.但是经过1个时间单位后,path1上的信息紊浓度为15;而 由于path2较短,在一个时间单位里.沿path2由A到B和由B 到A的蚂蚁分别为15只,所以path2上的信息紊浓度总数为 3O.那么t一1时刻,从A出发到达C点的蚂蚁就会倾向于选择 较短的路径path2,也就是说,将有三分之二的蚂蚁选择 path2对于从B点出发的蚂蚁也会有同样的情况 随着时间的推移和上述过程的重复,路径path2上的信息 紊将以更快的速度增长,于是便会有越来越多的蚂蚁选择了 收稿日期:200S一06—1S 作者简介:王芳(1981~),女(汉族),山东青州人,华北电力大学计算机科学与工程学 院,硕士学位研究生 70 2005年第2期王芳:蚁群算法的原理及其应 path2.以致最终完全选择短路径path2. 通过上面的例子.可以这样理解蚁群算法的基本思想:当 一 只蚂蚁在给定点进行路径选择.被先行蚂蚁选择次数越多 的路径.被选中的概率越大.该算法的主要特点可表述如下: (1)蚂蚁群体行为表现出正反馈过程通过反馈机制的调 整.可对系统中的较优解起到一个自增强的作用.从而使问题 的解向着全局最优的方向演变,最终能有效地获得全局相对 较优解. (2)蚁群算法是一种本质并行的算法.个体之间不断进行 信息交流和传递.有利于较好解的发现.并在很大程度上减 少了陷于局部最优的可能. (3)蚂蚁之间没有直接联系.而是通过路径上的信息索进 行信息的传递.也就是间接通讯. 3对蚁群算法的改进 虽然传统的蚁群算法具有很强的全局寻优解的能力.但 也存在一些缺陷.例如:该算法的搜索时间过长,大部分计算 时间被用于解的构造;在执行过程中容易出现停滞现象,当问 题规模较大时存在陷入局部最优的可能性等.因此.研究者对 传统的蚁群算法进行了很多改进研究.下面介绍两种有代表 性的改进 方法 快递客服问题件处理详细方法山木方法pdf计算方法pdf华与华方法下载八字理论方法下载 . 3.1最大最小蚁群系统 最大最小蚁群系统(Max,MinAntSystem.MMAS)是 德国学者T.Stuetzle和H.Hoos提出的.是最具有贪婪式寻优 特征的改进蚁群算法.目的在于防止过早的算法停滞现象. 如果信息索过度集中到几条较好的路径上.而其他路径 由于长时间没有蚂蚁经过,信息索逐渐挥发并趋近于零,那么 这些路径就最终不再有蚂蚁经过.这种情况下,有可能丧失寻 求最佳路径的机会,此时就出现停滞的现象.MMAS就是针 对这种现象.对算法中信息索的浓度引入最大值和最小值限 制:当某条路径上的信息索浓度大于所设定的上限.则强制其 为上限值;相反.则令其为下限值.通过设定信息索的上下限, 一 方面避免了某条路径上的信息索浓度远大于其它路径的信 息索浓度,从而有效降低了过早停滞的可能.另一方面.不会 因为某些路径的信息索浓度过低而丧失发现新路径的可能. 有研究实验表明.对于要求迭代次数较多的问题求解过 程.MMAS算法与传统的蚁群算法相比,在寻找解的有效性 方面和防止算法的过早停滞方面具有更好的效果.但是,需要 说明的是.仅采用最大最小信息索浓度的限制还不足以在较 长的时间里持久消除停滞现象,因此.可以对其进行进一步改 进.例如,在该算法中引入信息索的平滑机制等. 32动态蚁群算法 与传统的蚁群算法相比,动态蚁群算法的改进主要如下: 3.2.1在应用于求解旅行商问题时,传统的蚁群算法是 依据信息索和启发函数来选择目标城市的,这两个因子对路 而动态蚁群算法在迭代过程中. 径选择的影响力度是固定的. 选择目标城市时引入动态因子. 3.2.2在传统的蚁群算法中,对信息索的强度没有限制. 其挥发因子是一个常数.因而有陷入局部最优的可能.而动态 蚁群算法中设置动态变化的挥发因子.信息索浓度越高.则挥 发因子越大;浓度越低.挥发因子越小.通过限制.信息索的浓 度不可能无限增大.也不可能为零. 这样.由于目标城市的动态选择和信息索挥发因子的动 态性,动态蚁群算法有力地减少进化停滞现象. 4蚁群算法的应用 蚁群算法能够将问题求解的快速性,全局优化特性和有 限时间内答案的合理性结合起来.因此对于能够直接转化为 路径优化问题的组合类寻优问题.能取得比较理想的效果. 4.1大规模集成电路的线网布局 在大规模集成电路的线网布局中,需要根据电路和工艺 的要求完成芯片上单元或功能模块的布局,然后实现它们之 间的互连.此问题可看作是寻找一个网格平面上两端点之间 绕过障碍的最短路径问题.线网上的每个Agent根据启发策 略.像蚂蚁一样在开关盒网格上爬行,所经之处便设置一条金 属线.历经一个线网的所有引脚之后.线网便布通了.应用蚁 群算法,可以找到成本最低,最合理的线网布局.而且由于其 本身的并行性.比较适合于解决此类问题. 4.2通信网络路由 近年来.许多学者将蚁群算法应用于通讯领域,特别是通 信网络中的路由问题.通信网络的路由是通过路由表进行的. 在每个节点的路由表中.对每个目的节点都列出了与该节点 相连的节点,当有数据包到达时.通过查询路由表可知下一个 将要到达的节点.网络信息的分布性,动态性,随机性和异步 性与蚁群算法非常相似,都是利用局部信息发现解,间接通讯 方式和随机状态的转换Dorigo.DiCaro和Gambardella首先 将蚁群算法应用于网络路由问题.并称这种算法为AntNet. 4.3蚁群算法在电力系统中的应用 电力系统优化是一个复杂的系统工程.它包括无功优化, 经济负荷分配,电网优化及机组最优投入等一系列问题,其中 很多是高维,非凸,非线性的优化问题.其中.机组最优投入问 题是寻求一个周期内各个负荷水平下机组的最优组合方式及 开停机 计划 项目进度计划表范例计划下载计划下载计划下载课程教学计划下载 ,使运行费用最小.利用状态,决策及路径概念,将 机组最优投入问题设计成类似旅行商问题的模式.从而可方 便地利用蚁群算法来求解.还有人将蚁群算法编入水力发电 规划能源管理软件.可很好地节约能源.此外.对于电力系统 中的故障检测,蚁群算法也表现出较好的应用前景.由于故障 地点的估计信息来自保护继电器和电路断路器,那么对所有 故障部分的估计可以看作是一个组合优化问题. 蚁群算法适合处理此类组合优化问题.因为整个算法过 程没有任何监督,并且个体之间可以并行处理,但对于蚁群算 法在实际应用中的可靠性问题还需进一步探讨. 5结束语 蚁群算法是一种原理相对简单的新兴仿生进化算法,在 许多领域已展现出它的优势和魅力.首先,它易于控制陷入局 部最优的情况.能以很大的概率找到全局最优解;其次,具有 贪婪启发式算法的特征使系统在搜索过程的早期就找到可以 接受的解答;再次,由于其本质上的并行性.蚁群算法并行实 71 2O05年第2期王芳:蚁群算法的原理及其应用 现成为一个研究方向,这将j}常适合于巨量并行机. 蚁群算法把每个个体看作一个Agent.体现的是"群体智 能"的模式,每个个体具有相同的特性和能力.并通过信息素 彼此通讯.有些研究已在考虑给个体赋予一定的智能,例如赋 予学习能力,或者对蚂蚁进行分工,这是蚁群算法的一个发展 方向.另外.由于蚁群算法是以分布式的协同优化计算方式为 参考文献: 特征的,所以,对算法的并行机实现和协同运算机理也应该是 一 个研究的方向. 总之.蚁群算法作为一种新兴研究领域.处于人工生命与 运筹学的交叉位置,将会得到不断深入的研究,其模型将会更 丰富.也将相应的得到更加广泛的应用. [1]温文波.杜维.蚁群算法概述[J].石油化工自动化,2002,(1):19—22. [23马良.项培军.蚂蚁算法在组合优化中的应用[J3.管理科学.2001.4(2):32—36. E33侯云鹤,熊信艮,吴耀武等.基于广义蚁群算法的电力系统经济负荷分配[J3.中 国电机工程,2003,23(3):59—64. [43李有梅,王文剑,徐宗本.关于求解难组合优化问题的蚁群优化算法[J3.计算机 科学.2002.29(3):115—118. [53刘士新.宋健海,唐加福.蚁群最优化——模型,算法及应用综述[J].系统工 程,2004,19(5):496—502. [63胡娟,王常青,韩伟,全智.蚁群算法及其实现方法研究[J].计算机仿 真.2004,21(7):1lO一114. [7]MDorigoandLMGambardella.AntColonySystem:ACooperativeLearningApproachtotheTravellingSalesmanProb. 1em[J].IEEETransactionsonEvolutionaryComputations,1997,1(1):53—66. AntColonyAlgorithmTheoryandItsApplication WangFang (TheDepartmentofComputerScience&Engineering,NorthChinaElectricPowerUniversity,BaodingHebei071003) Abstract:Antcolonyalgorithmisanovelcategoryofbionicalgorithmforoptimizationproblems.Par— allelcomputationmechanismisadoptedinthisalgorithm.Ithasstrongrobustnessandiseasytocombine withothermethodsinoptimization,butithasthelimitationofstagnation,andiseasytofallintolocalop— timums.Firstly,thebasicprincipleofantcolonyalgorithmisintroduced.Then.aseriesofschemesonim— provingtheantcolonyalgorithmarediscussed,andthenewapplicationsarealsoprovided.Finally,some remarksonthefurtherresearchanddirectionsarepresented. Keywords:antcolonyalgorithm;ant;pheromone;optimization(Translator:MissWangFang) (上接第69页)' 三,新课标推动积累和运用同步进行 "学以致用",语文教学的根本目的也是为了应用.学生的 语文素养水平,除了体现在日常生活和其他科目的学习上,更 主要,更直接地体现在学生的作文中.作文是学生认识水平和 语言文字表达能力的综合体现,也是学生语文紊养的最好检 验. 但是长期以来,作文受应试教育的束缚,存在着忽视文源 的培养.立意的挖掘,专一训练技巧的现象.甚至为了应付考 试,引导学生"抄文","套文",这种脱离生活实际的纯文字训 练,使 小学 小学生如何制作手抄报课件柳垭小学关于三违自查自纠报告小学英语获奖优质说课课件小学足球课教案全集小学语文新课程标准测试题 作文走进了死胡同,切断了作文的生命线.要改变 这种状况.必须象新课标所要求的"作文要从内容人手,要引 导学生接触自然,接触社会","要做到观察,思维,表达密切结 合",将认识与表达统一起来,只有这样.才能真正达到作文是 表情达意的工具的境界,成为学生终生受用的基本功.笔者在 一 次系列作文训练中,围绕着提高认识与训练表达进行了如 72 下教学: 第一次,一看"钢笔",认识其外形及构造,进行《我眼中的 钢笔》的作文练习.第二次再看"钢笔",联系自己的生活,认识 钢笔的用途,进行《我和钢笔》的作文练习.第三次又看"钢 笔",认识钢笔的几点精神:竭尽全力,鞠躬尽瘁的精神;团结 一 致,共同协作的精神;忠于职守,任劳任怨的精神……进行 《我学钢笔》的作文练习.这样三看,三想,三写作文,学生认识 由表及里,由物到人,层层递进,做到了开源济流,认识和表达 共同发展.经常这样训练,就能逐步培养学生留心观察和分析 周围事物的能力,养成观察和思考的习惯,找到写作材料的来 源,提高学生认识与表达的能力,提高其语文素养. 总之,师生语文素养的提高是水乳交融,不可分割的.没 有教师的熏陶,传授,讲解和训练,学生的语文素养是不会从 自发走向自觉的;而对学生的指导和传授同样也激励着教师 更深入地理解和领会,激励教师博览群书,提高自己的文学素 养.新课标的实施,为这一"教学相长"提供了契机.