（计算数学专业论文）应用蚁群算法求解函数所有极值.pdf

应用蚁群算法求解函数所有极值 计算数学专业 研究生：刘卉指导教师：庞朝阳 摘要蚁群算法是继模拟退火、遗传算法、禁忌搜索等之后的又一启发式智能 优化算法，它是由意大利学者m d o r i g o 等人首次提出，并广泛应用于求解一 系列组合优化问题，如：旅行商问题，二次分配问题，车辆路径问题和图着色 问题等，这些应用充分显示了它在解决复杂离散优化问题方面的优越性。连续 空间函数优化问题也是蚁群算法的研究课题之一，多峰函数优化又是函数优化 的一个重要方面，但目前蚁群算法对该问题的研究主要是集中在求解函数的最 大( 小) 值，对求解函数所有极值方面的研究却很少。鉴于此，本文正是将蚁 群算法应用到求解函数所有极值方面，主要研究内容如下： ( 1 ) 综述了蚁群算法的发展过程、生物学机理及其研究现状，详细介绍了 基本蚁群算法模型及它的具体实现步骤。 ( 2 ) 详细介绍了用于求解函数所有极值的蚁群算法。首先研究了将蚁群算 法应用到求解函数所有极值时所表现出来的新特性，即蚁群经过若干次邻近区 间转移后，有的区间不含蚂蚁，有的区间会聚集一些蚂蚁。一般蚂蚁聚集的区 间正是包含极值点的区间。然后利用这个新特性设计了求解函数所有极值的蚁 群算法，该算法的特点是，只将蚂蚁聚集的区间进行再次细化，重新搜索极值 点，直到细化后的区间长度足够小时才停止算法。实验表明，本文算法不仅能 找出函数的所有极值点，而且求解精度高，速度快，稳定性好。 ( 3 ) 为了使本文算法便于理解，本文详细介绍了改进算法的数据结构和具 体代码。 关键词：蚁群算法，多峰函数优化 a p p l i c a t i o no f a n tc o l o n yo p t i m i z a t i o nf o rs e a r c h i n g a l lf u n c t i o ne x t r e m u m m a j o r ：c o m p u t a t i o n a lm a t h e m a t i c s p o s t g r a d u a t e ：l i uh u is u p e r v i s o r ：p a n gc h a o y a n g a b s tr a c t a n tc o l o n yo p t i m i z a t i o n ( a c o ) i sa n o t h e r i n t e l l i g e n to p t i m a l a l g o r i t h ma f t e rt h es i m u l a t e da n n e a l i n g ，t h eg e n e t i ca l g o r i t h m s ，a n dt h et a b us e a r c h e r e ，w h i c hi sf i r s t l yp r o p o s e db yi t a l i a ns c h o l a rm d o r i g oa n dh i sc o l l e a g u e s n o w i th a sb e e na p p l i e dt os o l v eas e r i e so fc o m b i n a t i o no p t i m i z a t i o np r o b l e m sw i d e l y ， s u c ha st r a v e l i n gs a l e s m a np r o b l e m ，q u a d r a t i ca s s i g n m e n tp r o b l e m ，v e h i c l e r o u t i n gp r o b l e m ，g r a p hc o l o r i n gp r o b l e ma n ds oo n t h e s ea p p l i c a t i o n ss h o w e d t h a ta c oh a sg r e a t s u p e r i o r i t y i ns o l v i n gc o m p l i c a t e dd i s c r e t eo p t i m i z a t i o n p r o b l e m s t h ea p p l i c a t i o no nc o n t i n u o u sf u n c t i o no p t i m i z a t i o np r o b l e m si sa n o t h e r r e s e r c ht o p i cf o ra c o ，a n dt h em u l t i - m o d a lf u n c t i o no p t i m i z a t i o ni sa l li m p o r t a n t a s p e c to ff u n c t i o no p t i m i z a t i o n h o w e v e r , t h es t u d yo fa c o o nt h i st o p i ci sm a i n l y f o c u s e do ns o l v i n gt h em a x i m u m ( m i n i m u m ) v a l u eo fag i v e nf u n c t i o nc u r r e n t l y a n da l lt h em u l t i p l ev a l u e si sp o o rs oi nt h i st h e s i s ，a c oi sa p p l i e dt os e a r c ha l lt h e f u n c t i o ne x t r e m u m t h em a i nr e s e a r c hc o n t e n t sa r ea sf o l l o w ： ( 1 ) d e v e l o p m e n t ，b i o l o g i c a lm e c h a n i s ma n dc u r r e n tr e s e a r c hs i t u a t i o no fa n t c o l o n yo p t i m i z a t i o na l ei n t r o d u c e d m o r e o v e r , t h em o d e l i n gc o u r s ea n dr e a l i z i n g s t e p sa r ei n t r o d u c e di nd e t a i l ( 2 ) a c of o rf i n d i n ga l lt h em u l t i p l ev a l u e so ff u n c t i o ni si n 仃o d u c e di nd e t a i l an e wf e a t u r ec a nb es e e nw h e na c ow a sa p p l i e dt of i n d i n gm u l t i p l eo p t i m ao fa m u l t i m o d a lf u n c t i o n t h en e wf e a t u r ei s t h a t ，t h r o u g ha n t s t r a n s f e r e n c e t o n e i g h b o ri n t e r v a l ss e v e r a lt i m e s ，t h e r ei sn oa n ti ns o m ei n t e r v a l s ，a n dal o to fo r i i s e v e r a la n t si no t h e ri n t e r v a l s g e n e r a l l ys p e a k i n g ，t h ei n t e r v a l si nw h i c ha n t sa r e d i s t r i b u t e da r ej u s tt h ei n t e r v a l sw h i c hc o n t a i ne x t r e m ev a l u e s f i r s t l y , t h ea u t h o r s t u d i e dt h en e wf e a t u r e t h e nb a s e dt h en e wf e a t u r e ，t h i sp a p e rp r e s e n t san o v e la n t c o l o n ya l g o r i t h mt of i n da l lt h em u l t i p l ev a l u e so ff u n c t i o n t h ec h a r a c t e r i s t i co f t h ea l g o r i t h mi st h a to n l yt h e i n t e r v a l si nw h i c ha n t sa r ed i s t r i b u t e da l et h i n n e d a g a i ni no r d e rt os e a r c hf o re x t r e m ev a l u e s i ft h et h i n n e di n t e r v a l sa r es m a l l e n o u g h ，t h ea l g o r i t h mw i l ls t o p e x p e r i m e n t ss h o wt h a tt h ea l g o r i t h mp r e s e n t e di n t h i sp a p e rc a nf i n do u ta l lt h em u l t i p l eo p t i m ao fag i v e nm u l t i m o d a lf u n c t i o n e s p e c i a l l y ，t h en e wa l g o r i t h mi sn o to n l yo fh i g hp r e c i s i o n ，b u ta l s oo ff a s t c o n v e r g e n c ea n do fg o o ds t a b i l i t y ( 3 ) i no r d e rt ou n d e r s t a n dt h ea l g o r i t h mp r e s e n ti nt h i sp a p e re a s i l y , t h ed a t a s t r u c t u r ea n dt h ep r o c e d u r ec o d eo ft h ea l g o r i t h ma r ei n t r o d u c e di nd e t a i l k e y w o r d s ：a n tc o l o n yo p t i m i z a t i o n ；m u l t i m o d a lf u n c t i o no p t i m i z a t i o n i 四川师范大学学位论文独创性及 使用授权声明 本人声明：所呈交学位论文，是本人在导师廑塑姻熬援指导下，独 立进行研究工作所取得的成果。除文中已经注明引用的内容外，本论文不 含任何其他个人或集体已经发表或撰写过的作品或成果。对本文的研究做 出重要贡献的个人和集体，均已在文中以明确方式标明。本声明的法律结 果由本人承担。 本人承诺：已提交的学位论文电子版与论文纸本的内容一致。如因不 符而引起的学术声誉上的损失由本人自负。 本人同意所撰写学位论文的使用授权遵照学校的管理规定： 学校作为申请学位的条件之一，学位论文著作权拥有者须授权所在大 学拥有学位论文的部分使用权，即：1 ) 已获学位的研究生必须按学校规定 提交印刷版和电子版学位论文，可以将学位论文的全部或部分内容编入有 关数据库供检索；2 ) 为教学、科研和学术交流目的，学校可以将公开的学 位论文或解密后的学位论文作为资料在图书馆、资料室等场所或在有关网 络上供阅读、浏览。 本人授权中国科学技术信息研究所将本学位论文收录到中国学位论 文全文数据库，并通过网络向社会公众提供信息服务。 ( 保密的学位论文在解密后适用本授权书) 学位论文作者签名： 纠算 i 签字日期：刃。年4 - 月彦日 9 r r t p日 皿n g 车月 城 中 孙 降 师 玑 勋 脯毒r整 第一章绪论 1 1 蚁群算法产生的生物学背景 在昆虫的世界里，如蚂蚁、蜜蜂等，虽然它们的个体行为非常简单，但是 它们却可以通过集体的力量进行觅食、筑巢、御敌、迁徙、清理巢穴等复杂而 神奇的活动。这种群体所表现出来的“智能 称为群智能 1 。这种群智能引 起了许多学者的关注，人们通过对昆虫世界群智能的模拟，提出了一系列仿生 算法，如：遗传算法、蚁群算法、微粒群算法等。这些包括蚁群算法在内的仿 生算法在解决一些传统的实际问题，特别是复杂的组合优化问题方面显示出了 强大的生命力和良好的发展前景。 仿生学家通过对蚁群的长期观察发现，尽管单个蚂蚁的智能非常有限，但 是由这些智能简单的个体组成的蚁群却具有高度的社会组织性，它们联合起来 的力量远远超过蚂蚁的个体能力。在观察蚁群的觅食行为时发现，蚂蚁总是在 巢穴周围做一些无规则的运动，一旦发现食物以后，并不是立刻食用，而是想 办法将食物运回自己的巢穴，如果食物体积和质量都很小，在该蚂蚁的能力承 受范围之内，它就会自己搬运食物，否则，它就会返回蚁穴搬救兵。在它往返 的过程中，它就会在路上留下一定的外激素，又称信息素，信息素的强度和蚂 蚁所走的路径的长短，食物源的质量和数量等都有一定的比例关系，留在路径 上的信息素对其它蚂蚁选择路径的时候有一定的影响作用。一般情况下，蚂蚁 总是偏向于选择信息素强度较大的路径。当然，并不是所有的蚂蚁都会选择留 有信息素的路径，也有一些蚂蚁选择其它的路径，并且留下相应的信息素，这 样，整个蚁群就形成了一种信息素正反馈机制，即当某一条路径上经过的蚂蚁 较多的时候，这条路径上留有的信息素就会越多，后来的蚂蚁选择该条路径的 概率就很大，蚁群中的个体之间就是通过信息素互相交流，随着时间的推移， 所有蚂蚁都会在从蚁穴到食物源之间的最短路径上行进，从而达到了快速高效 觅食的目的。 蚁群算法正是受自然界中真实蚁群觅食行为的启发而产生的一种应用于 解决复杂组合优化问题的仿生优化算法，这里所说的蚁群算法，更确切说应该 是“人工蚁群算法 。人工蚂蚁是从自然界中的真实蚂蚁中抽象出来的，人工 蚂蚁除了具有真实蚂蚁的交流、通讯、正反馈以及依概率进行状态转移机制外， 还有自己的一些特点，例如：有一定的记忆能力，不完全盲从，并且在信息素 更新时可以依赖于特定的问题等。当然，为了提高算法的效率，我们可以为人 工蚂蚁多增加一些在真实蚂蚁中不存在的性能，如：进行局部优化，简单未来 预测等。 1 2 蚁群算法的研究现状 蚁群算法是在2 0 世纪9 0 年代由意大利学者m d o r i g o 等人提出一种仿 生优化算法【2 】，“作为一种新型的启发式算法，蚁群算法最早应用于解决t s p 问题 3 ，4 ，后来又成功应用于解决其它的一些组合优化问题，如：车辆路径问 题( 冲) 5 】、车间调度问题( j s p ) 6 、图着色问题( g c p ) 7 】、二次分配问题 ( q a p ) 8 等。相对于其它智能算法，蚁群算法有它自身的优点：采用分布式并 行计算机制、易于与其他算法结合，并且具有较强的鲁棒性等优点，但同时也 存在一些缺陷，例如：搜索时间长、易出现停滞现象等。” 9 针对这些缺陷， 国内外的许多学者提出了一系列改进的蚁群算法。m d o r i g o 和 l m g a m b a r d e l l a 等提出了a n t q 算法 1 0 】，该算法对选择策略进行了改进， 采用确定性选择和随机选择相结合的选择策略，在搜索的过程中动态调整选择 概率，除此之外，该算法还引入局部信息素更新体制。之后，m d o r i g o 和 l m g a m b a r d e l l a 又在最早的蚁群算法，即蚁群系统( a s ) 的基础上提出了a n t c o l o n ys y s t e m ( a c s ) 1 1 】，作为a n t - q 算法的特例，尽管该算法在求解t s p 问题上和a s 性能相同，但其实现起来更为简单。为了克服a s 基本蚁群算 法可能出现的停滞现象，t s t i i e z l e 1 2 1 4 】等提出了最大最小蚂蚁系统 ( m a x m i na n ts y s t e m ，简称m m a s ) ，该算法设置了信息素的上下限，还引入了 一种信息素平滑机制，使蚂蚁具有搜索新的解空间的能力，从而避免了早熟收 敛现象。目前对蚁群算法的理论研究主要集中在对算法的收敛性和运行时间的 研究上，w j g u t j a h r 1 5 首次对蚁群算法的收敛性进行了证明。t s t i i e z l e 和 m d o r i g o 1 6 】证明了在两个不同条件下，最广泛的a c s 和m m a s 蚁群算 法的收敛性。2 0 0 9 年，庞朝阳等 1 7 】从一个新的视角研究了蚁群算法的收敛性， 即蚁群算法熵收敛研究，为蚁群算法的收敛性研究开辟了新视野。2 0 0 8 年， 2 w j g u t j a h r 【1 8 ，1 9 】对蚁群算法的时间复杂度进行了分析，提出了一些关于蚁 群算法运行时间的理论结果，接着庞朝阳等 2 0 1 也在这方面进行了尝试。蚁群 算法不仅应用于解决离散优化问题，也同样应用于连续域的优化问题，由于最 初的蚁群算法思想起源于离散型的网络路由问题，因此在将蚁群算法应用于连 续空间一般函数优化问题时，需要将连续的空间转换为离散型的，g a b i l c h e v 等 2 1 】最早提出一种连续蚁群算法，随后就被其他一些学者应用，m m a t h u r 等 2 2 应用蚁群算法求解不同类型的连续函数优化问题，适合求解大规模的优化 问题；j d r 6 0a n dp s i a r r y 2 3 提出了一种用于解决连续域多峰值函数优化的蚁 群算法，该算法引入了分层结构和沟通渠道，被称为连续交互式蚁群算法 ( c o n t i n u o u si n t e r a c t i n ga n tc o l o n ya l g o r i t h m ，c i a c a ) ；m r j a l a l i 等 2 4 提 出了一种用于求解连续域水库优化调度问题的多态蚁群算法；k s o c h a 和 m d o r i g o 2 5 给出了将蚁群算法拓展到连续域空间时的一些具体实施方案和 结果，并与其它一些应用于连续域优化问题的算法进行了比较，分析了算法的 效率和稳健性。目前国内许多学者也将蚁群算法应用于解决函数优化问题，并 且取得了一定的成果，其中李艳君等 2 6 1 提出了一种用于连续域优化问题求解 的自适应蚁群算法，该算法借鉴了遗传算法中的编码策略和混合算法中的区域 搜索思想；汪镭、吴启迪等 2 7 1 将离散域蚁群算法中的“信息量留存过程拓 展为连续域中的“信息量分布函数，并提出了应用于连续函数寻优问题的改 进蚁群算法；陈岐、沈洁等1 2 8 在利用蚁群算法求解连续空间函数优化问题时， 将解空间划分成若干子区域，蚁群每次迭代时，先根据信息量求出解所在的子 区域，然后再在该子域内确定解的具体值；高尚等 2 9 1 提出了一种基于网格划 分策略的连续域蚁群优化算法，该算法根据问题的性质事先估计出各个变量的 取值范围，并在变量所在的区域内打网格，蚂蚁寻优时，就是在各网格点之间 移动，并留下相应信息素；杨勇等 3 0 提出了一种嵌入式确定性搜索蚁群算法 用于求解连续域优化问题；王柳毅和熊伟清 3 1 提出了一种用于解决多峰函数 优化的二进制蚁群算法，将并行化引入算法，算法性能良好；段海滨等 3 2 提 出了一种自适应连续域蚁群算法，该算法是基于网格划分策略的。 1 3 本文研究目的与意义 优化问题在我们的实际生活中大量存在，目前，虽然传统的数学规划理论 成功地解决了一些优化问题，但当实际工程问题的复杂度增加时，传统的优化 方法便难于解决这些问题，因此一些适合于大规模并行计算的启发式智能优化 算法应运而生，诸如遗传算法( g a ) 、模拟退火算法( s a ) 、神经网络算法( n n ) 、 禁忌搜索算法( t s ) 等，对于不同的类型的组合优化问题，每一种算法都表现出 自身的优缺点，都面临着时间性能和优化性能的双重挑战。 蚁群算法( a c o ) 是继这些智能化算法以后的又一种应用于解决组合优化 问题的启发式搜索算法。相对于离散空间的优化问题，将蚁群算法应用到连续 域空间的优化问题的研究起步较晚，因此有良好的发展前景。 函数优化是连续域优化问题的一个倍受关注的研究点。在应用蚁群算法求 解连续空间函数优化问题时，国内外的许多学者都做了许多尝试，取得了很好 的成果，但是大多数研究是寻求目标函数的全局最优解，对于求解局部最优解， 即函数的所有极值方面的研究却很少。而在许多实际优化问题中，不仅需要在 可行域内寻找目标函数的多个全局最优解，往往还需要找到多个局部最优解， 用来供决策者参考，提出解决方案，这类问题一般称为多峰函数优化问题。寻 找多峰函数的所有极值点具有广泛的应用价值，日益受到人们的关注。受实际 需求的驱动，国内外许多学者将现有的智能优化算法加以改进，用于解决多峰 函数优化问题，但是很少有人将蚁群算法应用到该问题上。本文正是将蚁群算 法进行改进用于解决多峰函数优化问题。在将连续空间转换为离散型的时候， 以一维函数为例，将定义域区间分成若干相等的小区间，这样就把连续的空间 离散化，然后在离散的每个小区间内放置一只蚂蚁，蚂蚁的每个位置就可以看 作是离散域中的一些点，蚂蚁就在这些离散的点之间移动，先大致确定极值点 所在的区域，然后将这些区域反复细化，直到细化后的区间足够小。该划分方 法同样可以拓展到高维空间，例如：对于二维空间，可将定义域划分成一些小 平面区域，对于三维空间，可将定义域划分成一些小立方体。 1 4 本文主要工作 蚁群算法是智能优化领域的一个热门研究领域，本文首先介绍了蚁群算法 的产生和发展，概括了基本蚁群算法原理和模型，然后重点对基本蚁群算法进 行一些改进，并将其应用到连续空间求解函数所有极值问题上。本文主要完成 4 的研究工作及内容安排如下： 第一章介绍了蚁群算法产生的生物学背景及其研究现状，提出了本文的研 究目的和意义。 第二章详细介绍了基本蚁群算法，包括基本蚁群算法的原理、数学模型以 及具体实现步骤。 第三章对应用蚁群算法求解函数所有极值的算法进行了介绍，首先介绍了 算法的基本思想，接着对算法模型进行详细分析，然后介绍了算法的具体实现 过程，最后通过一些仿真算例证明了算法的有效性。实验表明，本文算法不仅 能找出函数的所有极值点，而且求解精度高，效率高，稳定性好。 第四章对本文算法的实现做了详细的介绍，先给出了改进算法的伪代码描 述，然后对伪代码中的两个部分分别进行了具体的代码描述和详细的数据结构 介绍。 第五章对本文整个工作进行总结，指出了本文算法的不足之处，并针对蚁 群算法的研究现状，指出了今后的研究方向。 第二章基本蚁群算法介绍 2 1 蚁群算法的基本原理 仿生学家经过长期研究发现，蚂蚁的单个个体行为非常简单，但是组成蚁 群以后却能表现出惊人的自组织行为。蚁群有一个很重要的特点，就是蚁群在 搜索食物的过程中，总能找到一条通往食物源和蚁穴之间的最短路径。蚁群算 法是基于自然界中蚂蚁觅食行为而产生的，下面我们先简单介绍一下蚂蚁觅食 的具体过程。 在自然界中，蚂蚁虽然没有视觉，几乎是盲的，但在搜索食物时，却总能 通过互相交流合作，找到一条食物源和蚁穴之间的最短路径。事实上，蚂蚁在 搜索食物的过程中，能在其走过的路径上释放一种信息素，所释放信息素的量 和其所走路径的长度成反比，即蚂蚁走的路径越短，留在路径上的信息素就越 多；反之，蚂蚁走过的路径越长，所留信息素就会越少。这些信息素对其它蚂 蚁还有该蚂蚁本身以后选择路径的时候都有一定的指导作用，一般地说，蚂蚁 总是倾向于选择信息素浓度更高的路径运动。故当某一条路径上经过的蚂蚁数 目越多时，该路径上所有蚂蚁留下的信息素浓度就会很大，后来的蚂蚁选择这 条路径的概率就会越大，随着越来越多的蚂蚁选择该路径，该路径的信息素的 强度就会逐步被增加，这种选择过程便形成了一种信息素正反馈机制，蚂蚁能 够快速搜索到食物，靠的就是这种正反馈机制。 事实上，蚁群除了能找到食物源和蚁穴之间的最短路径之外，还有很强的 适应坏境的能力。例如当在原来的最短路径之间突然出现了一个障碍物的时 候，原来所找的最短路径已经不可通行了，这时，蚁群就会重新进行路径搜索， 试图寻找最短路径。开始时，蚂蚁随机选择一条路径前行，并在其所走的路径 上留下相应浓度的信息素，用来指导后来蚂蚁的运动，后来的蚂蚁经过障碍物 时，一般会选择信息素浓度较高的路径前行，随着时间的推移，通过蚁群的正 反馈机制，蚁群同样可以找到一条新的从巢穴到食物源的最短距离。 2 2 基本蚁群算法数学模型 为了便于理解，现用求解平面上万个城市的t s p 问题为例来说明基本 6 蚁群算法模型【9 】。 假设将m 只蚂蚁随机放在刀个城市上，丸表示城市i 和城市，之 间的距离，互以) 表示f 时刻城市f 和城市，连线上的信息量，即路径 ( f ，_ ，) 的信息量。初始时刻，各条路径上信息量相等，设( o ) = c ( c 为一个正 常数) ，蚂蚁k ( 七= 1 , 2 ，z ) 在运动过程中根据各条路径的信息量决定其转 移方向。这里用禁忌表t a b u 。( k = 1 , 2 ，所) 来记录蚂蚁k 当前所走过的城 市，集合t a b u 。随着蚁群进化过程做动态调整。露( f ) 表示t 时刻蚂蚁k 由城市f 转移到城市，的状态转移概率 露( f ) =揣，轴踟喊 p 。， 0 ，否则 其中，a l l o w e d 。表示蚂蚁k 下一步允许选择的城市集合，则 a l l o w e d k = c - t a b u t ) ，口为信息启发因子，为期望启发因子， r u ( t ) 为启发函数，对于某个确定的t s p 问题，r l u ( t ) 是一个常数。其表达式如 下： 啪) = 玄 其中，以表示城市f 和城市之间的距离，且 吒= ( 鼍一) 2 + ( 咒一乃) 2 其中，( 薯，乃) 和( 工，y ，) 分别是城市i 和城市j f 的坐标。 为了避免路径上信息素的无限积累，导致某路径上残留的信息素过多 而淹没启发信息，在每只蚂蚁走完一步或者一个循环结束后，要对路径上 的信息素进行更新处理。由此，在t + l 时刻，路径( f ，) 上的信息量可 按如下规则调整 z u ( t + 1 ) = ( 1 一p ) 乃o ) + 乃( f ) ( 2 - 2 ) 乃( f ) = 苟( f ) ( 2 3 ) 其中，p 是信息素挥发系数，则l p 是信息素残留因子，且p ( 0 , 1 ) 。 乃( f ) 表示本次循环中路径( f ，力上的信息素增量，初始时刻信息素的增 量为0 ，即a r , j ( o ) = o 。露( f ) 为第k 只蚂蚁在本次循环中留在路径 7 ( f ，) 上的信息素。 这里，根据信息素不同的更新策略，即露( f ) 的不同求法将蚁群算 法模型分为以下三种：a n t c y c l e 模型、a n t q u a n t i t y 模型和a n t d e n s i t y 模型 ( 1 ) a n t - c y c l e 模型： 晡归垮若第识蚂蚁在t 和t + 1 之间经过( “) ( 2 4 ) l0 ，否则 式中， 厶表示第k 只蚂蚁在第t 次循环中所走路径的总长度。 ( 2 ) a n t - q u a n t i t y 模型 嘲沪睁若第职蚂蚁氆秕“之间经过瓴力 【0 ，否则 ( 3 ) a n t - d e n s i t y 模型 苟( r ) = 号：喜盖七只蚂蚁在和件1 之间经过“ 以上各式中，q 均表示信息素强度，是一个常数。在这三个模型中， a n t q u a n t i t y 模型和a n t - d e n s i t y 模型是当蚂蚁走完一步后更新其所走路 径上的信息素，是局部信息素更新。而a n t c y c l e 模型则是蚂蚁完成一个 循环后更新所有路径上的信息素，利用的是整体信息素更新。我们通常采 用a n t - c y c l e 模型作为蚁群算法的基本模型 9 。 2 3 基本蚁群算法实现过程 以a n t - c y c l e 模型为例来说明基本蚁群算法的具体实现步骤 9 】： s t e p l ( 初始化) 设定算法迭代次数n c = 0 ，设置最大循环次数为 c 腿，设置路径( f ，) 初始时刻的信息量t , j ( o ) = c ( c 为常数) ，信息素 q ，且初始时路径“，j ) 上的信息素增量为0 ，即a r , j ( o ) = 0 。 s t e p 2 算法的迭代过程 w h i l e ( n c 0 ，蚂蚁a k 就可以转 移到其邻近区间j ，；否则，蚂蚁不向其转移。设用a l l o w e d 。表示蚂蚁 a t ( k = 1 甩) 下一步可以转移的子区间的集合。 用彬( t ) 表示第t 次循环蚂蚁q 从子区间i i 转移到子区间l 的概率，模仿基本蚁群算法，定义蚂蚁a 。的转移概率如下： 硝( f ) =掣一砒嘲 p 。， 0 ，否则 式中，口为信息启发式因子，夕为期望启发式因子。乃为子区间i 的信 息量，如果蚂蚁咏依概率从子区间转移到了子区间，那么蚂蚁以 当前所在的子区间就为。 3 2 3 信息素更额 如果蚂蚁鲰依概率从子区间厶转移到了子区间，那么蚂蚁a k 就 会在区间，留下信息素，所留信息素的量用7 ( f ) 表示，则 f ( f ) = c j ( 厂( 鼍) 一厂( x ，) ) ( 3 - 2 ) 式中，c l 是一个正常数。厂( 薯) 一f ( x s ) 越大，蚂蚁a k 留下的信息素就越多， 就越吸引其他蚂蚁向区间，转移。 所有转移到区间，的蚂蚁都要留下相应的信息素，假设在第t 次循 环，有q 只蚂蚁转移到了区间，记这q 只蚂蚁为气，气，它们 留在区间，的信息素总和为a t ，( f ) ，则 乃o ) = 。p ；。a ，( j p o ) ( 3 - 3 ) 所有蚂蚁根据式( 3 1 ) 完成一次邻近区间转移后，要对信息素进行更新处 理。区间，的信息量彳，更新为 z j ( t + 1 ) = ( 1 - p ) f f ( f ) + f7(f)(3-4) 式中，p 为信息素挥发系数，因此1 一p 是信息素残留因子。 3 2 4 缩小蚁群搜索空间 函数值较小的区间含有的信息素会较多，更容易吸引蚂蚁向其转移。经过 一些循环，当所有蚂蚁都停止转移的时候，蚁群分布就会出现这样的特点：所 有蚂蚁都分布在极值点较小的区间，而其他区间则没有蚂蚁，即含有蚂蚁的区 间包含极小值点。取出这些包含蚂蚁的区间，并将这些区间重新细化，在下一 次循环时，让蚁群在这些区间重新搜索极小值点。如此循环下去，蚁群的搜索 范围就会越来越小，当细化后的区间足够小的时候，所有蚂蚁就会停留在极值 点附近，蚂蚁所停留的区间的中点位置就是极值点的位置。 蚁群的分布特点见图3 ： 1 6 图3 蚁群分布特点：经过一些循环以后，有的区间含有蚂蚁，有的区 间蚂蚁蚂蚁。下次搜索的时候只搜索只含有蚂蚁的区间，这样，蚁群搜 索空间就会减小。 3 3 算法实现 本文定义的算法的具体实现步骤如下： s t e p l ( 初始化) 将问题的定义域，b 进行胛等分，设等分后的各区 间的长度为万，停止门限为。在每个区间的中部放置一只蚂蚁，初始化各 区间的初始信息量瓦( 0 ) ，信息素增量瓦= 0 。 s t e p 2w h i l e ( 8 ) 1 7 s t e p 2 1 ：所有蚂蚁根据式( 3 1 ) 进行邻近区间转移。 s t e p 2 2 ：根据式( 3 2 ) 、( 3 - 3 ) 、( 3 4 ) 进行信息素更新。 s t e p 2 3 ：当所有蚂蚁都不再进行邻近区间转移时，更新蚁群的搜索范 围，即只将蚁群最终聚集的区间进行细化( 设细化后的区间个数为n 1 ) 。计 算细化后的区间长度，并将其赋值给万。 s t e p 3 结果输出。蚂蚁最终聚集的子区间就是含极值点的子区间，该子区 间中间位置即为极值点位置。 值得注意的是，如果x 是多维变量，将向量的每一维变量看作一个区间， 进行等分。这些各自等分的区间结合起来就构成了一些小空间，在这些等分空 间的中间位置各放置一只蚂蚁，重复上述搜索过程进行搜索，这个多维空间的 所有极值点就会被找到。 3 4 仿真算例 本文选取了五个函数进行实验( 本文算法的实现环境是d e l l 笔记本 d 5 2 0 ，c p u1 6 6g h z ) ，主要从以下几个方面对算法有效性进行验证：1 ) 所 求解的精度；2 ) 是否可以找到函数的所有极值点；3 ) 算法的稳定性。其中算例 l 是一维函数的极大值寻优，算例2 、算例3 、算例4 是一维函数的极小值寻 优，算例5 是二维函数的极大值寻优。实验中各参数设置为：c o n s t = 1 0 ，口= 1 ， p = l ，c l = o 5 ，p = 0 7 ，= 0 0 0 0 1 在验证解的精度的时候，解的误差用，表示 r = ri 丝巡| 1 1 0 0 l j f ( x o ) i j 式中，( x o ，f ( x o ) ) 是函数y = f ( x ) 的理论极值，o o ，f ( x 。) ) 是本文算 法计算出的函数极值，即实验值。实现过程所用时间是进行1 0 0 次独立实验所 需时间的平均值。 算例1 1 8 y = s i n 6 ( 5 1 z x + 0 5 ) ， x 【0 ，l 】 该函数在定义域范围内有六个极大值，其中有五个是全局最大值，最大值 为1 ，各峰值间隔相等，高度相等。实验时，初次搜索时设置划分小区间数 以= 2 0 ，再次搜索时设置划分小区间数n l = 1 0 。表1 和图4 表示算例1 的所有 极值点，实现过程仅用0 7 1 0 6 秒。 表1 算例1 实验结果 极值点 理论值( 而，f ( x o ) ) 实验值( xv 0 ，他i o ) ) 误差( ) r 0 0 6 6 8 3 2 3 6 4 ，0 0 6 6 8 2 7 1 7 5 ， 12 1 e - 0 6 10 9 9 9 9 9 9 9 7 9 0 2 6 2 9 1 0 7 9 5 ， 0 2 6 2 9 1 4 9 7 5 ， 21 3 e - 0 6 l0 9 9 9 9 9 9 9 8 7 0 4 5 8 9 8 9 2 2 7 ， 0 4 5 8 9 9 0 4 7 5 ， 31 o e - 0 7 l0 9 9 9 9 9 9 9 9 9 0 6 5 5 0 6 7 6 5 8 ， 0 6 5 5 0 6 6 1 7 5 ， 42 o e - 0 7 l0 9 9 9 9 9 9 9 9 8 0 8 5 11 4 6 0 9 0 ，0 8 5 11 4 8 5 5 0 ， 55 o e 0 7 10 9 9 9 9 9 9 9 9 5 l ，0 9 9 9 9 9 8 4 0 0 ， 60 0 1 4 5 0 1 4 7 8 2 2 1 1 80 1 4 7 8 0 0 6 5 4 通过表l 可以看出，在所有求得的极大值中，只有位于边界位置的解误差 较大。因为本文算法所取极值点是蚂蚁最终聚集的子区间的中点位置，所以在 端点处的极值必然存在一定误差。对于这类极值点，可以直接代入端点处的值 求得。 t 9 图4 横坐标表示函数的定义域，纵坐标表示函数值，星号 表示本文算法所寻极小值点。可以看出本文算法能找出所 有极小值点。 算例2 y = ( x + 1 ) ( x + 2 ) ( x + 3 ) ( x + 4 ) ( 工+ 5 ) + 5 x 一5 ，0 】 实验时，初次搜索时设置划分小区间数刀= 3 0 ，再次搜索时划分小区间 数，l l = 1 0 。表2 和图5 表示算例2 的所有极值点，实现过程仅用0 5 2 8 0 秒。 表2 算例2 实验结果 极值点 理论值( x o ，f ( x o ) )实验值 t o y f ( xv 0 ) ) 误差( ) ， 5 0 0 0 0 0 0 0 0 0 0 0 0 0 0 ，4 9 9 9 9 9 8 9 3 3 3 3 3 3 3 ， 5 1 2 e 一0 0 4 1 5 0 0 0 0 0 0 0 0 0 0 0 0 0 0 5 o 0 0 0 2 5 5 9 9 9 4 3 1 0 3 5 4 3 9 1 2 2 5 5 9 0 2 3 4 3 5 4 3 9 1 5 4 9 1 6 6 6 6 7 1 9 1 e - 0 0 9 2 3 5 8 1 3 0 3 3 7 4 4 1 7 0 8 3 5 8 1 3 0 3 3 7 4 4 8 5 6 5 一1 3 5 5 5 6 7 1 3 1 8 4 1 7 3 1 3 5 5 5 7 0 0 0 8 3 3 3 3 3 。1 2 0 e - 0 0 8 3 1 3 6 8 5 6 7 7 9 1 5 5 1 1 6 1 3 6 8 5 6 7 7 9 1 7 1 5 0 0 图5 横坐标表示函数的定义域，纵坐标表示函数值， 星号表示本文算法所寻极小值点。 算例3 y = ( x + 2 ) c o s ( 9 x ) + s i n ( 7 x )x 【o ，4 】 实验时，初次搜索时设置划分小区间数n = 9 5 ，再次搜索时划分小区间 数，l l = 1 0 。表3 和图6 表示算例3 的所有极值点，实现过程仅用0 9 0 3 0 秒。 表3 算例3 实验结果 极值点 理论值( j c 0 ，f ( x o ) )实验值( x 。，f ( x 1 0 ) ) 误差( ) r 0 0 0 0 0 0 0 0 0 0 0 0 0 0 。 0 0 0 0 0 013 4 7 3 6 8 4 2 。5 3 9 e - 0 0 4 2 0 0 0 0 0 0 0 0 0 0 0 0 02 o 0 0 0 1 0 7 7 8 8 0 0 3 2 1 0 3 8 7 6 2 4 2 3 5 7 4 7 3 9 。 0 3 8 7 6 2 0 0 6 31 5 7 8 9 7 9 7 e - 0 0 8 2一1 8 3 0 0 3 9 4 9 6 0 2 2 4一1 8 3 0 0 3 9 4 9 4 5 6 3 0 5 1 0 3 4 9 1 2 5 4 8 3 1 5 7 8 1 0 3 4 9 0 8 6 5 2 6 31 5 8 ， 6 9 8 e 一0 0 8 3一2 1 9 6 5 0 0 4 5 2 9 4 1 2 5一2 1 9 6 5 0 0 4 5 1 4 0 7 1 8 1 7 2 7 8 7 3 3 0 6 4 1 7 0 9 1 7 2 7 8 7 4 9 0 5 2 6 3 1 6 9 8 2 e 一0 0 9 4- 4 1 3 5 9 7 0 1 2 1 2 1 5 3 0一4 1 3 5 9 7 01 2 0 8 0 9 2 7 2 4 4 8 8 8 0 0 1 7 8 1 3 4 7 2 4 4 8 8 8 4 1 8 9 4 7 3 6 8 。 6 。5 5 e 一0 0 8 5一5 4 3 4 2 7 4 6 5 3 9 7 2 0 2 一5 4 3 4 2 7 4 6 5 0 4 1 0 0 9 3 1 6 0 6 4 0 3 2 5 3 0 5 3 9 。 3 1 6 0 6 4 0 3 7 8 9 4 7 3 7 1 1 7 e 0 1 1 6一5 2 1 7 9 3 4 6 0 2 8 6 1 4 4一5 217 9 3 4 6 0 2 8 6 0 8 3 3 8 4 4 9 3 2 6 3 7l3 2 8 2 3 8 4 4 9 3 4 3 3 6 8 4 211 ， 1 2 7 e 0 0 8 7一4 8 6 0 6 8 8 6 3 1 9 9 7 3 7一4 8 6 0 6 8 8 6 3 1 3 8 2 2 3 2 l 图6 横坐标表示函数的定义域，纵坐标表示函数值，星号表 示本文算法所寻极小值点。 算例4 y = 5 e m 5 。s i n ( 3 0 x ) + e 慨s i n ( 2 0 x ) + 6 ， x o ，8 】 该目标函数具有多个局部极小值点，各极值点之间间隔很小，对优化变量 的取值十分敏感，并且各个峰值高度不等，因此具有一定的代表性。参数设置： 咒= 4 8 0 ，n l = 1 0 。表4 和图7 表示算例4 的所有极值点，实验用时4 3 4 1 1 秒。 表4 算例4 实验结果 极值点 实验值 o ，八x o )