（应用数学专业论文）群智能算法及其应用研究.pdf

摘要 摘要 群智能算法是一种新型的仿生类进化算法，主要包括蚁群优化算法和粒子群 算法群智能算法具有较强的鲁棒性，采用分布式计算机制，并且易于实现，已 在众多领域得到了广泛的应用本文主要围绕蚁群优化算法和微粒群算法的理论 及其应用，就如何求解大规模旅行商( t r a v e l i n gs a l e s m a np r o b l e m ，t s p ) 问题、连 续性优化问题、约束优化问题、无线传感器网络路由优化问题进行了研究本文 的主要工作概括如下： 1 针对大规模t s p 问题，提出了一种基于模块度分簇的改进蚁群算法该算法 首先借鉴网络中的分簇原理，基于模块度的分簇算法将t s p 问题中的城市划 分为若干个簇，降低了问题的维数，并提出模块度的概念来度量所得到的簇结 构和实际t s p 问题网络匹配的程度；其次，基于信息素扩散的改进蚁群算法 求解簇间的连接顺序，即求解分簇得到的小规模t s p 问题的最优解，在基于 信息素扩散的改进蚁群算法中，从多方面模拟真实蚂蚁的行为，定义了新的信 息素扩散挥发规则，增强了蚂蚁之间的合作，使其快速找到最优解，同时增加 扰动因子避免其陷入局部最优解，并且分析了其全局收敛性，实例测试结果表 明了算法的有效性；然后，构造了求解簇内最短路径的基于信息素扩散的改进 蚁群算法；最后，将所有簇内和簇间的解按照一定的规则组成了原t s p 问题 的解仿真实验结果表明该算法适合求解大规模t s p 问题，与已有算法相比， 解的质量和收敛速度均有了较明显的提高 2 针对蚁群算法在连续空间函数优化中应用的瓶颈，提出了一种蚁群混合算法求 解连续空间问题，定义了新的蚁群信息素更新规则、蚁群在解空间的寻优方式 和蚁群行进策略为了克服蚁群算法搜索时间过长，易陷于局部最优等缺点， 在搜索过程中嵌入了改进的a l o p e x 算法，该算法具有快速搜索和摆脱局部最 优解的能力，实验结果表明了蚁群混合算法的有效性 3 针对标准微粒群算法不能保证全局收敛性问题，提出了一种随机混合微粒群算 法在随机微粒群算法中，将惯性权重设置为零，减少了关键参数对算法性能 的影响，提高了算法的通用性；在保证算法全局收敛性的同时，结合a l o p e x 算法重新生成停止进化粒子的位置，有效地避免了算法因单一搜索机制引起地 停滞现象将该算法应用于复杂多维函数，取得了较好的效果，为解决较复杂 的函数优化问题提供了一种可行的方法 4 针对约束优化问题，提出了一种基于协同进化的微粒群算法该算法在标准微 粒群算法的基础上，采用“保留最优，调节部分”的确定型选择策略，利用 摘要 进化中个体之间的差异，提出协同算子公式，引导进化方向，使个体之间 相互利用信息，更新微粒的位置进化方程；同时，提出基于不可行度的约 束处理方法，根据不可行度和不可行度阀值提出新的竞争选择准则，并由 此给出新的适应值函数引导群体加强对约束边界的搜索基于典型的约束 优化问题的实验结果表明：该算法可行有效，尤其对解决复杂问题表现出 较优的性能 5 研究了蚁群算法在无线传感器网络路由协议中的应用无线传感器网络路 由协议的一个重要目标就是要合理高效地使用网络中各传感器节点的能量 延长网络寿命文中提出了一种基于蚁群算法的无线传感器网络分簇路由 协议该方法首先利用网络自身拓扑结构，基于模块度的分簇算法得到一 个稳定的簇结构，无需每轮循环都构造簇，从而节省了构造簇的开销；其 次，根据每个簇内节点的剩余能量以及簇内节点的分布情况，给出了新的 簇头选择函数；然后，提出基于蚁群算法的簇间多跳路由算法，该算法以 如何均衡传输路径上消耗的能量和簇头节点的剩余能量为出发点，制定了 新的蚂蚁转移概率和信息素更新规则，通过实验仿真，并与已有较好算法 相比较，验证了算法的有效性 关键词：群智能算法蚁群优化算法微粒群算法大规模t s p 问题连续空 间函数优化约束优化问题无线传感器网络路由协议 a b s t r a c t a b s t r a c t s w a r mi n t e l l i g e n c ea l g o r i t h mi sa na l g o r i t h m i ca p p r o a c h , i n s p i r e db yt h ef o r a g i n g b e h a v i g ro ft h e r e a l a n i m a l s ，w h i c hh a db e e na p p l i e d t om a n yp r o b l e m s t h e d i s s e r t a t i o nf o c u s e so nt h ep r i n c i p l e s ，t h e o r y , a n da p p l i c a t i o n so fa n tc o l o n y o p t i m i z a t i o na l g o r i t h m ( a c o ) a n dp a r t i c l es w a r mo p t i m i z a t i o n ( p s o ) ，e s p e c i a l l y , a n i n - d e e pa n ds y s t e m i cs t u d yo nh o wt oi m p r o v et h eb a s i ca c o a n dp s oa l g o r i t h m ， p a r a l l e li m p l e m e n t a t i o no fa c o a n dp s o ，s o l v i n gt h ep r o b l e m ss u c ha sl a r g es c a l et s p a n dc o n t i n u o u ss p a c eo p t i m i z a t i o n ，c o n s t r a i n e do p t i m i z a t i o n , w i r e l e s ss e n s o rn e t w o r k r o u t i n gp r o t o c 0 1 t h em a i nw o r k sc a nb es u m m a r i z e da sf o l l o w s ： 1 t ot a c k l et h el a r g es c a l et s p , a na n tc o l o n ya l g o r i t h mi np h e r o m o n ed i f f u s i o n m o d e lb a s e do nm o d u l a r i t yc l u s t e r i n gi sp r o p o s e d f i r s t l y , t h el a r g es c a l et s pi s d i v i d e di n t os e v e r a lc l u s t e r i n gb a s e do nm o d u l a r i t ym e a s u r e s e c o n d l y , a l lt h e c l u s t e r i n gw i l lb es o l v e di np a r a l l e l i z a t i o nb ya ni m p r o v e da n tc o l o n ya l g o r i t h m b a s e do nt h ep h e r o m o n ed i f f u s i o nm o d e l ，t h i sa l g o r i t h mf o r m u l a t et h en e wr u l eo f p h e r o m o n ed i f f u s i o n ，a n d ad i s t u r b a n c em e c h a n i s mi sa d d e dt oa n tc o l o n y o p t i m i z a t i o nf o ri m p r o v i n gt h en e wa l g o r i t h m s p e r f o r m a n c e t h es i m u l a t i o no f t s pp r o b l e ms h o w st h a tt h i sa l g o r i t h mh a sas a t i s f i e dg l o b a lc o n v e r g e n c e l a s t l y , a l lt h es o l u t i o n so fe a c hc l u s t e r i n gw i l lb em e r g e di n t ot h es o l u t i o no ft h el a r g e s c a l et s pb ys o m er u l e s s i m u l a t i o nr e s u l t ss h o wt h a tt h ec o n v e r g e n c eo ft h e p r o p o s e da l g o r i t h mh a sb e e ni m p r o v e d 2 ah y b r i do p t i m i z a t i o na l g o r i t h m ，i nw h i c ha l o p e xa l g o r i t h mi se m b e d d e di n t ot h e i m p r o v e da n tc o l o n yo p t i m i z a t i o na l g o r i t h m ，i sp r o p o s e df o rs e a r c h i n gc o n t i n u o u s s p a c eo p t i m i z a t i o n i nt h ea l g o r i t h m ，t h en e wp h e r o m o n eu p d a t i n gr u l ea n dt h e m o v i n gs t r a t e g yo fa n t sa r ed e f i n e d t h ea l g o r i t h mi s w i t ht h er a p i ds e a r c h c a p a b i l i t yo ft h ei m p r o v e da l o p e xa l g o r i t h ma n dt h eg o o ds e a r c hc h a r a c t e r i s t i c so f t h ei m p r o v e da n tc o l o n yo p t i m i z a t i o na l g o r i t h m s i m u l a t i o nr e s u l t ss h o wt h a tt h e a l g o r i t h mi se f f e c t i v e 3 a h y b r i da l g o r i t h mi sp r o p o s e db yc o m b i n i n gp a r t i c l es w a r mo p t i m i z a t i o n ( p s o ) w i t ha l o p e xa l g o r i t h mt h a ti sas t o c h a s t i co p t i m i z a t i o nm e t h o d ，f o rs o l v i n g c o n s t r a i n e do p t i m i z a t i o np r o b l e m s i nt h ea l g o r i t h m ，i n e r t i aw e i g h ti sz e r o ，a n dt h e p o s i t i o no ft h ep a r t i c l ew h o s ee v o l u t i o nh a sb e e ns t o p p e di sp r o d u c e db ya l o p e x a l g o r i t h mt oi m p r o v et h eg l o b a l s e a r c ha b i l i t y s i m u l a t i o nr e s u l t ss h o wt h a tt h e a l g o r i t h mi se f f e c t i v e a b s t r a c t 4 5 ac o - e v o l u t i o n a r yp a r t i c l es w a r mo p t i m i z a t i o na l g o r i t h mt os o l v ec o n s t r a i n e d o p t i m i z a t i o np r o b l e m si sp r o p o s e d f i r s t l y , a n e wc o e v o l u t i o n a r yp s o ( c p s o ) i s c o n s t r u c t e d i nt h ea l g o r i t h m ，ad e t e r m i n i s t i cs e l e c t i o ns t r a t e g yi sp r o p o s e dt o e n s u r et h ed i v e r s i t yo fp o p u l a t i o n m e a n w h i l e ，b a s e do nt h et h e o r yo fe x t r a p o l a t i o n ， t h ei n d u c t i o no fe v o l v i n gd i r e c t i o ni se n h a n c e db ya d d i n gac o e v o l u t i o n a r ys t r a t e g y , i nw h i c ht h ep a r t i c l e sm a k ef u l lu s eo ft h ei n f o r m a t i o ne a c ho t h e rb yu s i n g g e n e - a d j u s t i n ga n da d a p t i v ef o c u s - v a r i e dt u n i n go p e r a t o r s e c o n d l y , i n f e a s i b l e d e g r e es e l e c t i o nm e c h a n i s mi su s e dt oh a n d l et h ec o n s t r a i n t s an e ws e l e c t i o n c r i t e r i o ni sa d o p t e da st o u r n a m e n tr u l e st os e l e c ti n d i v i d u a l s a l s o ，t h ei n f e a s i b l e s o l u t i o ni sp r o p e r l ya c c e p t e da st h ef e a s i b l es o l u t i o nb a s e do nad e f i n e dt h r e s h o l d o ft h ei n f e a s i b l ed e g r e e t h i sd i v e r s i t ym e c h a n i s mi sh e l p f u lt og u i d et h es e a r c h d i r e c t i o nt o w a r d st h ef e a s i b l er e g i o n o u ra p p r o a c hw a st e s t e do ns i xp r o b l e m s c o m m o n l y u s e di nt h el i t e r a t u r e t h er e s u l t so b t a i n e da r er e p e a t e d l yc l o s e rt ot h e t r u eo p t i m u ms o l u t i o nt h a nt h eo t h e rt e c h n i q u e s t om a k ee f f i c i e n t l yu s eo ft h el i m i t e de n e r g yr e s o u r c eo ft h ew i r e l e s ss e n s o r n e t w o r k ( w s n ) a n dp r o l o n gt h el i f e t i m ei sa l li m p o r t a n tp r o b l e mi nt h es t u d yo ft h e w s n a ne n e r g ye f f i c i e n tr o u t i n ga l g o r i t h mb a s e do na n tc o l o n yo p t i m i z a t i o nf o r w i r e l e s ss e n s o rn e t w o r ki sp r e s e n t e d t h ea l g o r i t h mf o r m sac l u s t e r i n gs t r u c t u r e b a s e do nr e a ln e t w o r ks t r u c t u r eo fw i r e l e s ss e n s o rn e t w o r kf i r s ta n dw eu s ean e w p a r a m e t e r - m o d u l a r i t ym e a s u r et oe v a l u a t ew h e t h e rt h ec l u s t e r i n gf i t sf o r t h er e a l n e t w o r ks t r u c t u r e b a s e do nt h ea b o v es t e a d yc l u s t e rs t r u c t u r e ，w h e nw es e l e c tt h e c l u s t e rh e a di ne a c hc l u s t e r , t h er e s i d u a le n e r g yo ft h en o d e sa n dt h ee n e r g y d i s t r i b u t i n gi nt h ec l u s t e ra r eb o t hc o n s i d e r e d t h ea l g o r i t h mc o n s t r u c t san o v e l p r o b a b i l i s t i cm o d e l ；t h em o d e lc o n s i d e r sb o t ht h eo v e r h e a do nt h er o u t ea n dt h e r e s i d u a le n e r g yo ft h en o d e s i m u l a t i o nr e s u l t ss h o wt h a tc o m p a r e dw i t ho t h e r a l g o r i t h m sl i k el e a c h ，o u ra p p r o a c hi sa b l et oo b t a i nam o r er e a s o n a b l ea n d s t e a d yd i s t r i b u t i o no fc l u s t e r i n g ，a n dc a l le f f e c t i v e l yp r o l o n gt h es e n s o rn e t w o r k 1 i f e t i m e k e y w o r d s ：s w a r mi n t e l l i g e n c ea l g o r i t h m a n tc o l o n yo p t i m i z a t i o np a r t i c l es w a r m o p t i m i z a t i o nl a r g e s c a l et s pc o n t i n u o u s s p a c eo p t i m i z a t i o n c o n s t r a i n e do p t i m i z a t i o nw i r e l e s ss e n s o rn e t w o r kr o u t i n gp r o t o c o l 独创性声明 本人声明所呈交的论文是我个人在导师指导下进行的研究工作及取得的研究 成果。尽我所知，除了文中特别加以标注和致谢中所罗列的内容以外，论文中不 包含其他人已经发表或撰写过的研究成果；也不包含为获得西安电子科技大学或 其它教育机构的学位或证书而使用过的材料。与我一同工作的同志对本研究所做 的任何贡献均已在论文中做了明确的说明并表示了谢意。 申请学位论文与资料若有不实之处，本人承担一切相关责任。 本人签名： 关于论文使用授权的说明 本人完全了解西安电子科技大学有关保留和使用学位论文的规定，即：研究 生在校攻读学位期间论文工作的知识产权单位属西安电子科技大学。本人保证毕 业离校后，发表论文或使用论文工作成果时署名单位仍然为西安电子科技大学。 学校有权保留送交论文的复印件，允许查阅和借阅论文；学校可以公布论文的全 部或部分内容，可以允许采用影印、缩印或其它复制手段保存论文。( 保密的论文 在解密后遵守此规定) 本人签名：丞! 盘亟 导师签名：日期趟：! 兰：勿 第一章绪论 第一章绪论 1 1引言 从上世纪6 0 年代以来，模拟生物进化过程并以此开发求解复杂优化问题的有 效算法越来越受到人们的广泛关注进化计算【i 巧1 ( e v o l u t i o n a r yc o m p u t a t i o n ，e c ) 就是由此而发展起来的一种启发式算法，它包括遗传算法( g e n e t i ca l g o r i t h m s ， g a ) 、进化规划( e v o l u t i o n a r yp r o g r a m m i n g ，e p ) 、进化策略( e v o l u t i o n a r ys t r a t e g i e s ， e s ) 和遗传编程( g e n e t i cp r o g r a m m i n g ，g p ) 等主要进化理论进化计算的具体实现 方法与形式称为进化算法( e v o l u t i o n a r ya l g o r i t h m ，e a ) ，虽然进化算法具有多 个代表性的重要分支，但是它们的进化形式和原理却不尽相同 近十余年来，群智能算法( s w a r mi n t e l l i g e n c ea l g o r i t h m ) 作为一种新型的仿 生类进化算法已成为众多研究者的关注焦点生物学家观察研究发现，群居昆虫 群体可以看作是一个分布式系统，虽然系统中的每个个体都非常简单，智能也不 高，但是整个系统却呈现出一种高度结构化的群体组织，使个体能协同工作，完 成一些远远超出单个个体能力负荷的复杂工作群智能算法就是模拟自然界生物 群体的这种行为而构造的随机搜索方法目前，该研究领域有两种主要算法：蚁 群优化算法( a n tc o l o n yo p t i m i z a t i o n ，a c o ) t 6 】和微粒群算法( p a r t i c l es w a r m o p t i m i z a t i o n ，p s o ) t 7 1 群智能算法具有较强的鲁棒性，采用分布式计算机制，并 且算法实现简单，在组合优化、网络路由、函数优化、数据挖掘、机器人路径规 划、无线传感器网络性能优化等领域获得了广泛的应用，并取得了较好的效果已 有研究结果表明群智能算法为解决许多应用问题提供了新的途径和方法 本章首先阐述两种典型的群智能算法，即蚁群优化算法和微粒群算法的思想 起源和算法模型，然后评述这两种群智能算法的发展现状，最后介绍本文的主要 工作 1 2 蚁群优化算法 1 2 1 蚁群觅食的生物学行为 自然界中蚁群的自组织行为很早就引起了昆虫学家的注意1 0 ，1 d e n e u b o u r g 及其合作者设计了“双桥实验1 6 ，1 2 , 13 1 ，用以模拟蚁群的觅食行为该实验采用一个 双桥连接蚁穴和食物源第一个实验中，桥的两个分支长度相同，如图1 1 ( a ) 所示最 2群智能算法及其应用研究 初，两条分支均不存在信息素，蚂蚁以相同的概率随机选择某一分支，并独立地 释放信息素由于随机波动的存在，选择某一分支的蚂蚁数量可能会多于另一分 支，导致此分支的信息素浓度较另一分支高，由此又会促使更多的蚂蚁再次选择 这一分支，释放更多的信息素，从而使此分支的信息素浓度变得更高，反复进行 这一过程，最终大部分蚂蚁都集中到某一条分支路径上值得注意的是，d e n c u b o u r g 等对此实验重复多次，统计结果表明，蚁群最终选择某一分支的概率大约为5 0 此 实验较好地显示了蚁群觅食的自组织行为，最终出现的宏观有序结构，即蚁群向 某一分支集中的现象，源于蚂蚁个体之间的局部多重交互作用；同时，此自组织 行为需要依赖随机波动的存在，而这种波动经自催化和正反馈机制得以扩大，最 终形成蚁群的自组织行为 ( a ) 两条分支具有相同的长度( b ) 两条分支具有不同的长度 图1 1 双桥实验的设置【1 2 】 第二个实验中，桥上的两个分支长度不同，如图1 1 ( b ) 所示最初，两条分支 均不存在信息素，蚂蚁以相同的概率随机选择某一分支，并独立地释放信息素由 于选择短分支的蚂蚁首先到达食物源并返回蚁穴，于是释放到短分支上的信息素 早于并多于长分支路径，这将增大后续蚂蚁选择短分支的概率，形成正反馈机制， 最终大部分蚂蚁都会选择短分支路径g o s s 等【1 2 】基于此实验现象构建了一个模 型假定在某个瞬间时刻，和鸭分别为选择过双桥上第一、第二分支的蚂蚁个 数，那么一只蚂蚁选择第一分支的概率如式( 1 1 ) 所示 胪万 ( 1 1 ) 胪百高可希万 u j 而选择另一个分支的概率为： p 2 = 1 一a ( 1 2 ) 式中k 和h 为两个待估计参数，用来匹配真实实验数据为了求得参数k 和h ，通 过蒙特卡罗模拟证实【】，当k 2 0 ，h 2 时，公式( 1 1 ) 与实验数据相一致 在第二个实验中( 两座桥的长度不相等) ，绝大多数蚂蚁选择较短的桥，随机波 第一章绪论3 动的影响大大减少，主要是s t i g m e r g y ，差异路径长度( d i f f e r e n t i a lp a t hl e n g t h ) 、正反 馈等机制占主导地位【1 5 】同时，据实验观察，并不是所有蚂蚁都选择较短分支， 仍有小部分蚂蚁会选择较长分支，此可用自组织理论中的波动扩大要素予以解释， 是一种所谓的“路径探索( p a t he x p l o r a t i o n ) ”行为，这一点可以为算法设计提供仿生 意义的指导 上述两个实验，均是基于信息素的间接交流机制，进而实现蚁群自组织行为， d o r i g o 等将这种间接交流机制称之为“s t i g m e r g y ，并定义为【1 5 】：社会昆虫群体用 于协调它们行为的一种独特的间接交流方式 除了能够找到蚁穴和食物源之间的最短路径外，蚁群还有极强的适应环境的 能力，如图1 2 所示，在蚁群经过的路线上突然出现障碍物时，蚁群能够很快重新 找到新的最优路径 n e s tf o o d n ：叫 海：砌 。麟+ 埘霹j i “ 麟7 一、缸 考+ 一燃：堪一 ：缸 簟 ( c ) ( d ) ( a ) 蚁群在蚁穴和食物源之间的路径上移动；( b ) 路径上出现障碍物，蚁群以同样的概率向左、 右方向行进；( c ) 较短路径上的信息素以更快的速度增加；( d ) 所有的蚂蚁都选择较短的路径 图1 2 蚁群的自适应行为【6 l 1 2 2 蚁群优化算法的思想起源 通过研究蚁群觅食的群体行为，意大利学者d o r i g om a c r o 等t 8 1 于1 9 9 1 年在巴 黎召开的第一届欧洲人工生命会议上最早提出了蚁群算法的基本模型；1 9 9 2 年 d o r i g om a c r o 又在其博士论文中进一步阐述了蚁群算法的核心思想吲 4 群智能算法及其应用研究 像蚂蚁这类群居昆虫，虽然没有视觉，却能找到由蚁穴到食物源的最短路径， 原因是什么呢? 虽然单个蚂蚁的行为极其简单，但由这样的单个简单个体所组成 的蚂蚁群体却表现出极其复杂的行为，能够完成复杂的任务，不仅如此，蚂蚁还 能够适应环境的变化，例如：在蚂蚁运动路线上突然出现障碍物时，蚂蚁能够很 快重新找到最优路径蚂蚁是如何完成这些复杂任务的呢? 仿生学家经过大量的 研究发现，蚂蚁个体间通过一种称之为“信息素( p h e r o m o n e ) ”的物质进行信息传递， 从而能够相互协作，完成复杂的任务因此，蚁群的集体行为表现为一种信息正 反馈现象：某条路径上经过的蚂蚁数越多，其上留下的信息素的迹也就越多( 当 然，随时间的推移会逐渐蒸发掉一部分) ，后来蚂蚁选择该路径的概率也越高，从 而更增加了该路径上信息素的强度这种根据其他蚂蚁所释放的化学物质信息来 影响蚂蚁群体的路径选择的行为方式正是a c o 算法的灵感来源 a c o 算法就是从自然界中真实蚂蚁觅食的群体行为得到启发而提出的，其实 很多观点都来源于真实蚁群【6 1 ，算法中一群简单的人工蚂蚁通过信息素( 一种分布 式的数字信息，与真实蚂蚁释放的信息素相对应) 进行间接通讯，并利用该信息 和与问题相关的启发式信息逐步构造问题的解因此a c o 算法中所定义的人工蚂 蚁与真实蚂蚁存在一定的异同 人工蚂蚁具有双重特性：一方面，它们是真实蚂蚁的抽象，具有真实蚂蚁的 特性；另一方面，它们还有一些真实蚂蚁不具备的特性，这些新的特性使人工蚂 蚁在解决实际优化问题时，具有更好地搜索较好解的能力 人工蚂蚁与真实蚂蚁具有如下共同点1 6 1 6 】： ( 1 ) 存在一群相互协作的个体与真实蚁群一样，a c o 算法由一群人工蚂蚁组 成，人工蚂蚁之间通过同步异步协作来寻找问题的最优解虽然单只人工蚂蚁可 以构造出问题的解，但只有当多只人工蚂蚁通过相互协作，才能发现问题的最优 ( 次优) 解 ( 2 ) 使用信息素的迹和s t i g m e r g y 机制如真实蚂蚁一样，人工蚂蚁通过改变所 访问过的问题的数字状态信息( 在a c o 算法中被称为信息素) 来进行间接的协 作在a c o 算法中，信息素是人工蚂蚁之间进行交流的唯一途径另外，a c o 算 法还用到了蒸发机制，这一点对应于真实蚂蚁中信息素的蒸发现象蒸发机制使 蚁群逐渐忘记过去的历史，使后来的蚂蚁在搜索中较少地受过去较差解的影响， 从而更好地指导蚂蚁的搜索方向 ( 3 ) 随机状态转移策略如真实蚂蚁一样，人工蚂蚁也是按照概率决策规则从 种状态转移到另一种邻接状态其中的概率决策规则是与问题相关信息和局部 环境信息有关的函数在状态转移过程中，人工蚂蚁与真实蚂蚁都只用到了局部 信息，没有使用前瞻策略来预见将来的状态因此，所使用的策略在时间和空间 上是局部的 第一章绪论5 ( 4 ) 搜索最短路径人工蚂蚁和真实蚂蚁具有相同的任务，即以局部移动的方 式构造出从原点到目的点之间的的最短路径 人工蚂蚁与真实蚂蚁具有如下不同点【6 】： ( 1 ) 人工蚂蚁具有一定的记忆能力，能够记住其过去的行为状态 ( 2 ) 人工蚂蚁存在于一个离散的空间中，它们的移动是从一个状态到另一个 状态的转换 ( 3 ) 人工蚂蚁存在于一个与时间无关联的环境中 ( 4 ) 人工蚂蚁释放信息素的数量是其生成解的质量的函数 ( 5 ) 人工蚂蚁更新信息素的时机依赖于特定的问题例如，有的问题中人工蚂 蚁仅在找到一个解之后才更新路径上的信息素，而有的问题中人工蚂蚁每作出一 步选择就更改信息素，但无论哪种方法，人工蚂蚁都不是完全盲从的，它受到问 题空间特征的启发 ( 6 ) 为了改善算法的优化效率，可以给人工蚂蚁增加一些真实蚂蚁所不具备的 特性，例如简单预测、在局部优化过程中相互交换信息等 1 2 3 蚂蚁系统的模型 蚁群在觅食过程中总能找到蚁穴和食物源之间的最短路径受其启发，意大 利学者m d o r i g o ，v m a n i e z z o ，和a c o l o m i 8 9 】提出了一种新型的模拟进化 算法蚂蚁系统( a n ts y s t e m ，a s ) a s 算法是第一个a c o 算法，被称为基 本a c o 算法 a s 算法主要包括两个基本阶段：适应阶段和协作阶段在适应阶段，各候 选解根据积累的信息不断调整自身结构，路径上经过的蚂蚁越多，信息素数量越 大，则该路径越容易被选择，时间越长，信息素数量越少；在协作阶段，候选解 之间通过信息交流，以期望产生性能更好的解 为了能够清楚的理解蚂蚁系统的数学模型，仍以求解平面上t 个城市的旅行 商问题( t r a v e l i n gs a l e s m a np r o b l e m ，t s p ) 1 6 为例说明 一般地，t s p 问题可描述如下： 设c = c ic 2 ，c n ) 为刀个城市的集合，l = 乞i c i ，c j c 是c 中元素两两连接 的集合，t s p 问题可以用一个带权完全图g = ( c ，l ) 来描述，t s p 问题的目的是 从g 中找出长度最短的h a m i l t o n i a n 圈， 问且只访问一次的最短的一条封闭曲线 即找出对c = c 1c 2 ，巳) 中珂个城市访 t s p 问题分为对称型和非对称型在对 称型t s p 问题中，有略= 叱，v ，q ，勺c ( i ，= 1 ，2 ，甩) ，吒是乞的长度；而在 非对称t s p 问题中，至少存在一对q ，勺c ( i ，= l ，2 ，1 ) ，使吒叱 首先引进如下记号：设朋是蚁群中蚂蚁的数量，d 驴( f ，j = l ，2 ，刀) 表示城市f 6 群智能算法及其戍用研究 和城市，之间的距离，b i ( t ) 表示t 时刻位于城市i 的蚂蚁的个数，则有 m = ：。6 ：f ( t ) 乃o ) 表示f 时刻在城市f ，- ，连线上残留的信息量初始时刻，各 条路径上信息量相等，设f ；，( o ) = c ( c 为常数) 每一个简单蚂蚁个体有以下特性： ( 1 ) 蚂蚁根据以城市距离和连接边上信息素数量为变量的概率函数选择下一 个城市 ( 2 ) 规定蚂蚁走合法路线，除非周游完成，不允许转到已访问城市，由禁忌 表控制( 设t a b u 。( 后= 1 ，2 ，肌) 表示第k 个蚂蚁的禁忌表) ( 3 ) 蚂蚁完成周游后，在每一条访问过的边上留下信息素 蚂蚁系统可以简单表述如下：在0 时刻进行初始化过程，蚂蚁放置在不同的 城市，每一条边都有一个初始信息素强度f 。( o ) ；每一只蚂蚁的禁忌表的第一个元 素设置为它的开始城市；然后，每一只蚂蚁从城市i 移动到城市，根据两个期望 措施的概率函数选择移动城市在n c 次循环后，所有蚂蚁都完成了一次周游， 它们的禁忌表将被填满；此时，计算每一个蚂蚁k 所走的路径总长度厶，r ：依 据信息素更新规则进行更新，而且，由蚂蚁找到的最短路径( 即 r a i n 厶，k = l ，2 ，m ) 将被保存，所有禁忌表将被置空；重复这一过程直到周游 计数器达到最大( 用户定义) 周游巳。，或者所有蚂蚁都走同一路线，后一种 情况被成为停滞状态如果算法在n c 次循环后结束，蚂蚁算法的复杂度为 口( c ，z ) 蚂蚁k ( k = 1 , 2 ，m ) 在运动过程中，根据各条路径上的信息量决定转移方 向p ：( f ) 表示在t 时刻蚂蚁k 由城市礴专移到城市，的概率： 露：j 【 乃( r ) 口 ( r ) 卢 ( r ) 。h ( r ) 卢 j e a l l o w e d k ，j a l l o w e d k 0 ， o t h e r w i s e ( 1 3 ) 其中：r l 。为先验知识或称为能见度，在t s p 问题中为城市i 转移到城市，的启发 信息，一般取7 7 。= l d “口为在路径( f ，) 上残留信息的重要程度；卢为启发信息 的重要程度；算法中的蚂蚁与大自然中的真实蚂蚁不同，具有记忆功能， a l l o w e d i = 一t a b u i ，是一组城市；t a b u i ( k = l ，2 ，m ) 用以记录蚂蚁k 当前所走过的城市，称为禁忌表，集合t a b u 。随着进化过程作动态调整 随着时间的推移，以前留下的信息素逐渐消逝，用参数p 表示信息素消逝程 度，蚂蚁完成一次循环以后，各路径上的信息量要作以下调整 准则l ( 局部调整准则) ：局部调整是指每只蚂蚁在建立一个解的过程中进 行，经过h 个时刻，两个城市之间的局部信息素数量要根据下式作调整： 第一章绪论 7 r 驴o + ) = ( 1 一f ) f 驴o ) + 善f 。 ( 1 4 ) = ( 1 5 ) 刀i l n i n 式中：，孝【o ，1 】，k 是两个最近城市之间的距离 准则2 ( 全局调整准则) ：只有生成了全局最优解的蚂蚁才有机会进行全局 调整，全局调整规则为： f o + 1 ) = 0 - p ) f o ) + p f ( 1 6 ) a r 妒= a r ； i = 1 ( 1 7 ) 其中，a r ：表示第k 只蚂蚁在本次循环中留在路径驴上的信息量，a r o 表示本次循 环中路径i j 上的信息量的增量一般设置周游次数计数器n c ，当达到设定值时结 束，最短路径m i n t 厶，( k = 1 ，2 ，m ) d o r i g om a c r 0 1 6 给出了不同的蚂蚁系统模型，分别称为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 模型它们的差别在于f ：o ) 的求法不同 在a n t c y c l e 模型中： 瞄：悟 当第职蚂蚁在时刻琊h l 之峪勘时 ( 1 8 ) 1 0 ， 其他 式中：q 是信息素强度，它影响算法的收敛速度；l 。是第k 只蚂蚁在本次循环中 所走路径的长度 在a n t - q u a n t i t y 模型中： 瞄：垮当第舢蚁在嗽此和f + 1 之间经过删 ( 1 9 ) 【0 ， 其他 在a n t d e n s i t y 模型中： 叫= 偿嚣只蚂蚁在时亥此秕“之间经过拊 ( 1 1 0 ) 模型比较：式( 1 9 ) 和式( 1 1 0 ) 和j 用的是局部信息；而式( 1 8 ) 中利用的是整体信 息在一系列标准测试问题上运行的实验结果表明，基于a n t c y c l e 模型的蚁群算 法的性能优于其他两种模型算法 群智能算法及其应用研究 1 2 4 改进的蚁群优化算法 虽然a s 算法具有较强的全局寻优能力，在很多领域获得了广泛的应用，但 也存在一些缺陷，例如： 与其他的寻优算法相比较，a s 算法的搜索时间过长一般地，蚁群算法 的时间复杂度为o ( n c 1 1 2 ml ，n c 为循环次数，大部分的时间被用于解的构造 在a s 算法的执行过程中容易出现停滞现象蚁群算法中搜索进行到一定 的程度后，所有蚂蚁个体发现的解趋于一致，此时，即使使用随机搜索策略，也 不可能在解空间中进一步搜索，这样就存在陷入局部极小的可能性，不利于发现 更好的解原因在于信息素轨迹更新规则中不被选用的弧段上的信息素轨迹和选 中的弧段上的信息素轨迹的差异会变的越来越大，而蚂蚁始终沿着信息素轨迹高 的弧段爬行，这就导致当前不被选用的弧段今后被蚂蚁选择的概率变的越来越小， 进而使算法在某些局部最优解附近徘徊，出现停滞现象 针对以上问题，许多学者提出了若干改进的蚁群优化算法，如m d o r i g o 提 出的蚁群系统( a n tc o l o n ys y s t e m ，a c s ) d 7 、德国学者s t u t z l e 等【1 8 】提出的最大 最小蚂蚁系统( m a x m i na n ts y s t e m ，m m a s ) 等 ( 1 ) 蚁群系统 a c s 算法在a s 算法的基础上作了以f 三点改进： 在a c s 算法中，将a s 算法中的转移概率准则改为可得到多样性解的新 准则，如下所示 ，：t a r g m a x