（计算机软件与理论专业论文）微粒群算法在动态优化中的应用研究.pdf

中文摘要 现实世界中大量的优化问题往往是动态的，其优化参数、约束条件、优化目标 等是时变的。这些动态优化问题要求算法能准确检测出环境发生变化的时刻，以及 对变化后的环境做出及时有效的响应。这是评价动态优化问题中算法性能的主要依 据，也是算法应用于动态优化问题中遇到的难题。微粒群算法模型简单、鲁棒性好， 是一种适于求解非线性复杂问题的有效方法。所以，改进微粒群算法的优化模型， 使之更适应时变的优化问题，具有实际的工程意义。为此，本论文着重研究了微粒 群算法适合于求解动态问题的一些特点，并对其进行改进。提高了算法对动态环境 的跟踪、检测和响应能力。 首先为提高微粒群算法对于动态环境变化的检测和响应能力，随机抽样选取多 个侦查微粒，通过其适应值信息的变化来检测环境是否变化；同时引入混沌变异的 响应策略。但是由于该算法只要检测到环境发生变化就响应，浪费了大量的计算机 资源，同时频繁的响应使算法的收敛速度大大降低。随后又对其进行了改进，引进 种群多样性来自适应控制变异频率。基于高维单模动态环境的仿真结果表明，该改 进算法能更精确检测环境的变化，并对环境变化做出更迅速及时的响应。 然后针对微粒群算法在复杂多模动态优化问题中的应用，提出了新的改进微粒 群优化模型。该模型利用混沌序列使种群均匀分布，提高算法进化初期的优化性能； 根据环境的抽象模型是时变的特点，用前后两时刻环境的不同抽象模型去评价同一 时刻的群体，通过判断不同的环境模型对同一代群体评价所得全局最好位置和全局 最优适应值的变化信息来判断环境是否变化；同时，利用种群多样性和微粒的当前 位置与下一时刻环境抽象模型中的全局最好位置的距离作为响应依据，和改进的重 设进化方向的方法想结合，不仅能够及时的跟踪变化后的极值点，而且能很好的保 持开发和探索的平衡，使微粒群算法的优化性能有进一步的提高。 关键词：微粒群算法；动态环境；混沌；种群多样性。 a b s t r a c t m a n yo p t i m i z a t i o np r o b l e m sa r e o f t e nd y n a m i ci nr e a lw o r l d ，t h e i r o p t i m i z a t i o np a r a m e t e r s ，c o n s t r a i n t s ，o p t i m i z a t i o n o b j e c t i v e se t ca r e t i m e v a r y i n g t h e s ep r o b l e m sr e q u i r e o p t i m i z a t i o na l g o r i t h m t od e t e c t c h a n g e sa c c u r a t e l y a ta l lt i m e sa n dr e s p o n s et i m e l y a f t e re n v i r o n m e n t c h a n g e s t h e s et w oa s p e c t sa r et h em a i nf o u n d a t i o n st oe v a l u a t ea l g o r i t h m s p e r f o r m a n c ei nd y n a m i ce n v i r o n m e n ta n da l s ot h e m a i nh a n d l e st oa p p l y a l g o r i t h mt od y n a m i co p t i m i z a t i o n p 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 m m o d e li ss i m p l e ，g o o da n dr o b u s t i ti sa l le f f e c t i v em e t h o dt os o l v ec o m p l e x ， n o n l i n e a rp r o b l e m s t h e r e f o r e ，i m p r o v i n g p a r t i c l es w a r mo p t i m i z a t i o n a l g o r i t h mm o d e la n dm a k i n gi t m o r ea d a p t i v et ot i m e _ v a r y i n go p t i m i z a t i o n p r o b l e ma r ep r a c t i c a l l ys i g n i f i c a n tt oe n g i n e e r i n ga p p l i c a t i o n s t o t h i se n d ， t h i sd i s s e r t a t i o nf o c u s e so nt h ec h a r a c t e r i s t i c so fp a r t i c l es w a r ma l g o r i t h m w h i c ha r es u i t a b l ef o rs o l v i n gd y n a m i co p t i m i z a t i o np r o b l e m ，a n dm a k e s t h e mi m p r o v e d ，t h e ni m p r o v e st h ea l g o r i t h m sc a p a b i l i t y o ft r a c k i n g ， d e t e c t i o na n dr e s p o n s ef o rc h a n g e si nd y n a m i ce n v i r o n m e n t f i r s t l v ，f o ri m p r o v i n g p 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 m s c a p a b i l i t yo f d e t e c t i o na n dr e s p o n s ef o rc h a n g e s ，t h ed i s s e r t a t i o ns e l e c t ss o m e d e t e c t i v ep a r t i c l e sa tr a n d o m ，t h r o u g ht h ec h a n g e si n f o r m a t i o n o ft h e i rf i t n e s s t od e t e c tc h a n g e si ne n v i r o n m e n t ；a tt h es a m et i m e ，c h a o t i cm u t a t i o nh a s b e e ni n t r o d u c e da sr e s p o n d e ds t r a t e g y h o w e v e r ，b e c a u s eo ft h ea l g o r i t h m r e s p o n d st o of r e q u e n t l y ，w a s t i n g al o to fc o m p u t e rr e s o u r c e s ，a l s or e s p o n d i n g t o of r e q u e n t l ym a k e st h ec o n v e r g e n c er a t eo ft h ea l g o r i t h mg r e a t l yr e d u c e d f o l l o w i n g i ti n t r o d u c e ss w a r md i v e r s i t yt oc o n t r o lt h er e s p o n d e df r e q u e n c y a d a p t i v e l y t h es i m u l a t i v er e s u l t so fs i n g l e m o d eh i g h d i m e n s i o n a ld y n a m i c e n v i r o n m e n ts h o wt h a tt h ei m p r o v e da l g o r i t h mc a nd e t e c tc h a n g e sm o r e a c c u r a t e l y ，a n dr e s p o n dm o r eq u i c k l y l a t e r f o rm u l t i m o d ec o m p l e xd y n a m i co p t i m i z a t i o np r o b l e m s ，t h e d i s s e r t a t i o n p r o p o s e s a ni m p r o v e dp a r t i c l es w a r mo p t i m i z a t i o n m o d e l i i i 上h r o u g nu s m gc h a o t i cs e q u e n c e st om a k es w a l n qd i s t r i b u t i n ge v e n l y ，t h e nt h e a i g o r i t h m sp e r f o r m a n c eh a sb e e ni m p r o v e di n e a r l ye v o l u t i o n a r y f o rt h e c n a r a c t e r i s t i c so fa b s t r a c td y n a m i ce n v i r o n m e n tm o d e la r et i m e v 哪i n g ，t h e d l s s e r t a t i o nu s e sd i f f e r e n ta b s t r a c te n v i r o n m e n tm o d e l si n d j 旋r e n tt i m et o e v a l u a t ep a r t i c l e si ns a m et i m e ，t h r o u g ht h e c h a n g e si n f o m a t i o no fg l o b a i b e s tj o c a t l o na n dg l o b a lb e s tf i t n e s st od e t e r m i n e c h a n g e si ne n v i r o m l l e m a t t h es a m et l m e ，t h ed i s s e r t a t i o nu s e ss w a r m d i v e r s i t ya n dt h ed i s 切n c eb e 帆e e n p a r t l c l e sc u r r e n tp o s i t i o na n dt h eg l o b a lb e s tl o c a t i o ni nn e x tm o m e n t a sa r e s p o n d e dc o n d i t i o n t h e s ec o m b i n ew i t ht h em e t h o do f i m p r o v e dr e s e t t i n 2 e v o l u t i o n a l o r i e n t a t i o n ，n o to n l yb ea b l et ot r a c ke x t r e m ep o i n ta r e rt h e c n a n g e st l m e l y ，b u ta l s ot om a i n t a i nag o o db a l a n c eb 咖e e n e x p l o i t a t i o n a n de x p l o r a t i o n s ot h a tp a r t i c l e s w a r mo p t i m i z a t i o na l g o r i t h mh a sb e e n t u r t n e ri m p r o v e df o rc o m p l e x d y n a m i co p t i m i z a t i o np r o b l e m s k e y w 。r d s ：p 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 m ；d y n a m i ce n v i r o m l l e m ； c h a o s ；s w a r md i v e r s i t y i v 声明尸明 本人郑重声明：所呈交的学位论文，是本人在指导教师的指导下， 独立进行研究所取得的成果。除文中已经注明引用的内容外，本论文 不包含其他个人或集体已经发表或撰写过的科研成果。对本文的研究 做出重要贡献的个人和集体，均已在文中以明确方式标明。本声明的 法律责任由本人承担。 作者签名：日期： 关于学位论文使用权的说明 本人完全了解太原科技大学有关保管、使用学位论文的规定，其 中包括：学校有权保管、并向有关部门送交学位论文的原件、复印 件与电子版；学校可以采用影印、缩印或其它复制手段复制并保存 学位论文；学校可允许学位论文被查阅或借阅；学校可以学术交 流为目的，复制赠送和交换学位论文；学校可以公布学位论文的全 部或部分内容( 保密学位论文在解密后遵守此规定) 。 作者签名： 日期： 导师签名：盈垫 隰 竺2 ， 第一章绪论 第一章绪论 1 1 选题背景及研究意义 近年来，系统科学的科研领域正从无生命系统向有生命系统扩展，特别是基于 生物信息系统的智能算法已成为人工智能领域的一个重要研究内容。这一领域的研 究突出体现了现代科学发展的多层次、多学科和多领域相互渗透、相互交叉和相互 促进的特点，对控制理论、信息科学和计算机的发展具有重要意义，同时也为工程 实践人员提供了许多富有成效的技术和方法。近年来，随着优化技术应用范围的扩 大，大量动态环境优化( d e o ：d y n a m i ce n v i r o n m e n to p t i m i z a t i o n ) i h - 题急需要有效的 优化算法来解决。譬如：温室控制、城市规划、项目管理、证券投资、学校课程表安 排、车间调度等，这些常因为环境变化、人员变动、效率要求等，他们的决策方案 需作相应变化。这类动态优化问题对优化技术的应用提出了极高的要求，已有的优 化算法在求解中极难呈现出算法的有效性和实时性。因此，寻求适合解决此类问题 的优化算法显得尤为重要。虽然大量改进的遗传算法( g a ：g e n e t i ca l g o r i t h m s ) 在 动态环境优化领域得到了一定的应用，但其自身存在许多难以解决的问题( 如早熟收 敛、随机漫游、控制参数的选择等) ，使得其对d e o 问题的应用带来极大的不便以及 存在难以克服的缺点。 微粒群优化( p s o ：p a r t i c l es w a r mo p t i m i z a t i o n ) 算法是一种极具潜力的群智能 优化算法，由美国社会心理学家j a m e sk e n n e d y 和电气工程师r u s s e l le b e r h a r t 于 1 9 9 5 年共同提出，算法容易理解、易于实现、鲁棒性好，具有较强的自组织、自学 习、和自适应能力，是一种适于求解复杂问题的新方法。特别是其本质的并行性、 自组织性及自适应性，使其具有能克服遗传算法很多不足的优越性。 微粒群算法在静态优化问题中的应用已得到了广泛的研究，这方面的理论和方 法已趋于成熟。与静态优化问题相比，动态优化问题的研究更具有实际的系统工程 意义。因此尝试将微粒群算法用于动态优化问题的求解，探寻算法在动态环境下的 求解性能是群智能算法的趋势，目前在这方面已经做了一些研究，但理论体系还不 够完整。 为此，本论文分析了不同的动态优化问题的特性。根据这些特性，设计出适合 的解决方案，提出相应的算法模型，研究算法在各种常见动态环境中的动态性能。 通过实验验证和算法比较，得出求解动态优化问题的性能良好的改进微粒群算法。 本论文的研究，将会进一步拓展微粒群算法的理论研究和应用范围，同时对群智能 微粒群算法在动态优化中的应用研究 优化算法的研究，将具有一定实际意义和参考价值。 1 2 动态环境中的优化算法研究现状 对于动态问题，只有抽象出算法的运行环境才能对其进行优化。以现实中的动 态问题为原型，抽象出的环境模型就是动态环境模型，对这些动态环境的优化也就 是对动态问题的优化。所以动态优化一般指的就是在动态环境中进行的算法优化。 对于动态环境中优化算法的研究应追溯到六十年代末期，经历了漫长的发展时期， 至今尚未成熟。总结下来，主要是以下三个方面。 1 2 1 动态环境中的进化算法 进化算法( e a ：e v o l u t i o n a r ya l g o r i t h m s ) 是根据达尔文生物进化论中“优胜劣汰， 适者生存”的思想以及孟德拉的遗传学理论而产生的一种智能算法。生物进化过程是 通过适应外界环境和保持自身优良品种之间的矛盾推动的，因此e a 是一种较适合于 处理动态环境优化问题的算法。f o g e l 1 】等首次将e a 应用于动态环境优化，至今经历 了几十年的发展。近年来已出现了相当多的动态环境进化算法，这些算法主要是通 过增加或修改基本遗传算法( s g a ：s i m p l eg e n e t i ca l g o r i t h m s ) 的一些算子，然后获得 改进的遗传算法，并将其应用于动态优化问题。这个方向已取得了很好的成绩，但 由于遗传算法本身的局限性，使其发展受到阻碍。按照算法设计的不同目的，可分 为以下几种： ( 1 ) 基于群体多样性的进化算法 群体多样性是进化算法自适应跟踪环境变化的重要因素。基于基本遗传算法设 计，通过修改算子，使算法能自适应地跟踪环境的变化、降低进化群体中个体的共 性，有助于增强个体的多样性，克服原有遗传算法易于出现局部最优现象。此类算 法中典型的代表算法为c o b b 【2 】提出的摆动变异遗传算法( t h g a ：t r i g g e r e d h y p e r m u t a t i o n ) ，该算法对不同环境下连续优化问题跟踪效果较好，但不易于解决非 连续函数优化问题。继摆动变异遗传算法被提出解决动态优化问题之后， g r e f e n s t e t t e 4 l 针对t h g a 求解某些特殊动态特性的优化问题的局限性，提出了随机迁 移遗传算法( r i g a ：r a n d o mi m m i g r a n t sg a ) ，此方法仅依靠随机插入少量新个体来维 持群体的多样性，对于插入的个体数目在算法中往往很难确定，若插入的个体数过 少，很难提高算法对新环境的搜索性能，若插入的个体数过多，会使算法陷入随机 漫游，几乎需对整个初始群体重新评价，消耗算法较多的评价时间，降低算法的收 敛速度。更近来，a r a g o n 5 1 等将迁移和超变异机制组合，设计了一种属于动态环境 2 第一章绪论 优化的遗传算法，为动态环境优化问题建立了一种初步研究框架，促进了动态环境 优化算法的研究。虽然对所测试问题的搜索效果较好，但其算子模块的设计未能体 现算法的自适应性，只是将各算子简单组合，故其需要大量的测试问题进一步验证。 ( 2 ) 基于记忆的进化算法 通过增加记忆模块，每进入个新环境，算法都将其保存的成功信息直接传递 给下一环境，从而加速新环境的优化速度。b r a n k e 在文献【6 中综述了各种记忆方法， 其可分为两类：( 1 ) 显型记忆法：显型记忆法最突出的特点是设计专门的存储模块保存 较好个体，当算法进入下一环境时，被保存的个体直接插入新环境的初始群中，从 而加快算法的收敛速度，典型的算法为，b e n d t s e n 1 0 】等于2 0 0 2 年提出的动态记忆 g a ( d m g a ：d y n a m i cm e m o r yg e n e t i ca l g o r i t h m ) 及近来y a n g 【7 1 将记忆和随机迁移算 子组合而获得的记忆增强g a ，此类算法对最优值呈周期变化的优化问题有较好的跟 踪环境能力，而对最优值呈非周期变化的动态优化问题，则其记忆细胞可能会引导 算法向错误的方向搜索；( 2 ) 隐型记忆法；算法主要是通过个体的编码来记忆较好的个 体，其中典型的方法为二倍体法【8 】，该类算法由于增加染色体的编码长度，增大了解 的存储空间，对于高维的动态优化问题不易处理，且收敛速度较慢 ( 3 ) 基于多种群的进化算法 这类算法的主要思想是将整个群体分成若干个小子群，每个子群在其对应的区 域内独自地搜索，同时保存各自区域内较好的个体( 局部最优解) ，然后将每个子群的 最优个体组合便得到全局最优个体( 全局最优解) ，同时，依靠各子群的分布来保持群 体多样性较为典型的方法是漂移平衡法( s b g a ：s h i f t i n gb a l a n c eg e n e t i c a l g o r i t h m ) t 9 1 ，此类算法是将整个群体分成若干小的子群和一个中心子群，这些小子 群在己出现最优值的区域搜索，探测最优值的再次出现，而中心子群远离这些小的 子群，它的任务是探索新的峰出现，也即相当于保持群体多样性和算法白适应记忆， 小子群对以前出现过的区域记忆，中心子群探测新峰值的出现，同时避免算法陷入 局部最优现象由此可见，此方法适合于解决多模态动态优化问题，但其子群的划分 准则及大小需要先验性知识才能恰当地确定 ( 4 ) 基于动态多目标的进化算法 近来，动态多目标进化算法己倍受人们关注，b i n g u l t l l 】利用模糊推理系统控制 s g a 中交叉和变异概率，获得一种实用于动态环境优化的g a 解决动态多目标优化 ( d m o ：d y n a m i cm u l t i o b j e c t i v eo p t i m i z a t i o n ) 1 商7 题，其对问题的收敛性较好，可是所 获p a r e t o 面分布较不均匀，主要是因为在算法中需要建立恰当的模糊规则； 3 微粒群算法在动态优化中的应用研究 a m a t o 【1 2 】借鉴生物进化过程中个体匈的竞争及无性繁殖机制设计一种动态群体的在 线进化算法并用于动态多目标优化问题的求解，实验论证了其能自动地跟踪问题的 变化，但由于算法在每一代只有一个个体参与进化，使得算法收敛速度相当慢，特 别是算法在处理新环境的优化问题时，其所获效果较差。 1 2 2 动态环境中的微粒群优化算法 微粒群算法在静态优化问题方面己取得广泛应用，然而，从近年来的资料文献 可以看出，对动态环境中微粒群优化算法的研究在国内外还处于初级阶段，而且理 论体系还很不成熟。首先将基本微粒群算法应用于动态环境的是e b e r h a r t 和 c a r l i s l e 1 3 , 1 5 】，结果证明对于变化频率小而且变化步长不大的动态系统，基本微粒群 算法可以跟踪动态极值，并且能够收敛到全局极值。但是对于那些变化频率大，变 化步长大的动态系统，基本微粒群算法将会跟踪失败。后来e b e r h a r t 和x i a o h u ih u e l 4 j 将基本微粒群算法做了改进，提出了自适应p s o ( a p s o ：a d a p t i v ep s o ) ，该算法通 过检测全局极值相隔几代是否变化来检测环境是否变化，为了检测准确，后来又提 出不仅检测全局极值，还检测次全局极值。对于响应变化后的环境，他们采用在环 境变化后集中对整个微粒群进行全部或者部分的初始化，以此来提高微粒的多样性， 使微粒在搜索空间内不产生聚集，提高微粒适应环境的能力。但是他们的这种思想 是在环境变化，全局最好适应值应该也随之变化这种假设情况下才成立，有些变化 系统不一定是这样变化的。在响应方面他们采用初始化所有的微粒或者部分微粒， 这不但不能利用种群当前时刻的空间分布信息，而且盲目的随机初始化有可能导致 微粒收敛速度慢或者不收敛。c a r l i s l e 和d o z i e r 1 6 】利用在每一代都为微粒群体设置感 应微粒来检测环境的变化，对于响应他们采用同样的方法。但是他们的这种思想是 在当环境变化后感应微粒的位置也发生变化的假设情况下成立，这就会出现同样的 检测和响应缺陷。针对以上改进方法在动态系统中表现的不足，h a r d i n 和r a g a d e 1 7 j 提出了另一种跟踪动态极值的方法，该方法无须设置特别的微粒去检测环境，也不 需要检测相隔几代的全局最好极值，而是对基本微粒群进化公式的位置更新采取变 异操作，这样不但节省处理特殊微粒的时间而且减低了程序执行的复杂度。但是如 果变异率掌握不当就会产生种群混乱，后果可想而知。h uj i n g 1 8 1 提出了一种全新的 检测和响应方法，对于检测环境变化，利用个体微粒的自身信息，环境发生变化后， 其对应的适应值也可能发生相应的变化。当某一微粒进化的前后代位置接近，但其 对应的适应值却发生显著变化，基本可以推测环境发生了变化，和以往的设置感应 4 第章绪论 微粒和检测全局最优艮的方法有很大区别，但是这也只是能够大致的判断环境是否 变化。对于响应环境变化采用了基于种群多样性的微粒逃逸行为，这在一定程度上 摆脱了重设微粒的缺陷。 除了进化算法和微粒群优化算法用于动态环境优化问题外，同时也出现相当多 的其它算法用于动态环境优化问题的研究，如2 0 0 4 年m a r c of a r i n a 等将梯度搜索算 法与进化机制结合提出一种动态多目标邻域搜索算法【1 9 】，该文的重点不在于其算法 的研究，而在于设计了不同类型的用于检测动态多目标优化算法性能的测试问题。 1 3 本文的主要研究内容和方法 1 3 1 本文的主要研究内容 为了研究和提高微粒群算法在动态优化中的动态性能，本论文拟从以下几个方 面展开研究： ( 1 ) 分析典型的动态优化问题，选择动态优化问题的标准测试函数 现实世界中的动态优化问题极其复杂，目前对动态优化问题的研究，大都是根 据优化问题的静态评价函数构造简单的动态环境。选择逼近实际动态问题特征和复 杂性的测试函数，是决定算法泛化能力的根本因素。因此，为提高算法在实际动态 环境下的求解性能，选择合理有效的动态环境作为算法动态优化性能的研究基础是 极其必要的。 ( 2 ) 研究算法对动态环境变化的检测方法。 根据动态环境的特征，利用微粒群本身固有的信息，研究粒子对环境变化的感 知能力以及粒子与环境的信息交互方式，使算法能有效地检测环境的变化，以便能 够对变化后的环境做出及时的处理。 ( 3 ) 研究算法对环境变化的响应方法。 当环境发生了变化，研究微粒群体的行为方式，使粒子能跟踪环境的变化规律， 从而有效的跟踪动态优化问题极值的变化。 ( 4 ) 研究动态优化过程中如何保持算法开发和探测之间的平衡，从而提高算法 在动态环境下的全局优化性能。 1 3 2 研究拟采用的方法 针对上述的研究内容，本论文采用理论分析和仿真实验相结合的研究方法： 1 、理论分析： ( 1 ) 了解动态优化的问题特征，选择合适的标准测试函数。 微粒群算法在动态优化中的应用研究 ( 2 ) 针对不同的动态问题，提出可行的检测环境变化方案。 ( 3 ) 找到更好的微粒进化方式，使其更有效的跟踪环境的变化。 ( 4 ) 对于保持多样性，引进合适的排斥因子。 ( 5 ) 对于平衡开发和搜索，可以对整个种群进行微粒的重新组配，对拥有不同 信息的微粒进行不同的处理。 ( 6 ) 基于仿真实验，分析算法的鲁棒性及动态优化性。 2 、仿真实验： ( 1 ) 利用v i s u a lc + + 6 0 程序开发环境，编写改进算法的程序。 ( 2 ) 利用m a t l a b 进行仿真实验。 1 4 本文的组织结构 本文主要分析了自适应微粒群( a p s o ：a d a p t i v ep s o ) 算法在动态环境中性能的 不足，构造了适用于环境变化的新型改进微粒群算法。通过一系列理论研究和仿真实 验，论证了改进后的算法不仅适用于动态环境的变化，而且是有效且实用的。各章的 内容提要如下： 第二章对微粒群算法进行了较为系统地探讨，详细地介绍了标准p s o 算法的算法 原理、算法流程等，并介绍了几种常见的动态优化问题的标准测试函数。 第三章针对原有环境检测方法的局限性，提出了改进的环境检测方法，同时将种 群多样性和混沌变异相结合来响应环境的变化。在高维的单模态动态环境中对算法进 行了仿真实验，验证了该方法的有效性。 第四章根据均匀布种的思想，利用混沌初始化种群代替随机初始化种群；根据环 境的抽象模型是时变的特点，用前后两时刻环境的不同抽象模型去评价同一时刻的群 体，通过判断全局最好位置和全局最优适应值的变化信息来判断环境是否变化；同时， 利用种群多样性和微粒的当前位置与下一时刻全局最好位置的距离作为响应依据，和 改进的进化方向重设方法想结合，不仅能够及时的跟踪变化后的极值点，而且能很好 的保持开发和探索的平衡，使微粒群算法的优化性能有进一步的提高。 第五章总结与展望。回顾了本文完成的主要工作，列出了下一步的研究方向，展 望了动态环境下微粒群算法的发展前景。 6 第二章微粒群算法研究综述 第二章微粒群算法综述 2 1 群智能算法简介 最初，计算机学者受社会性昆虫行为的启发，产生了一系列对于传统问题的新 的解决方法，这些研究后来就形成了专门体系一群智能。群智昵( s w a r mi n t e l l i g e n c e ) 中的群体( s w a r m ) 指的是“一组相互之间可以进行直接通信或者间接通信( 通过改变局 部环境) 的主体，这组主体能够合作进行分布问题求解”。而所谓群智能是指“无智能 的主体通过合作表现出智能行为的特性”。群智能在没有集中控制并且不提供全局模 型的前提下，为寻找复杂的分布式问题的解决方案提供了基础。 群智能的优点是群体中相互合作的个体是分布式的，这样更能够适应当前网络 环境下的工作状态；没有中心的控制与数据，这样的系统更具有鲁棒性，不会由于 某一个或者某几个个体的故障而影响整个问题的求解；可以不通过个体之间直接通 信而是通过非直接通信进行合作，这样的系统具有更好的可扩充性；由于系统中个 体的增加而增加的系统的通信开销在这里十分小；系统中每个个体的能力十分简单， 这样每个个体的执行时间比较短，并且实现也比较简单，具有简单性。因为具有这 些优点，虽说群集智能的研究还处于初级阶段，并且存在许多困难，但是可以预言 群智能的研究代表了以后计算机研究发展的一个重要方向。在计算智能领域有两种 基于群智能的算法，蚁群算法( a n tc o l o n yo p t i m i z a t i o n ) 年n 微粒群算法( p a r t i c l es w a r m o p t i m i z a t i o n ) 。 蚁群算法最早是由c o l o m i 在9 0 年代提出的【2 1 1 ，该算法模拟了蚂蚁群对食物的 采集过程。算法最初随机地选择路径，通过蚂蚁的记忆、信息素以及集体活动，使 搜索变得有规律，并逐渐逼近直至最终达到全局最好解。蚁群算法已成功应用于组 合优化、车间作业调度、网络路由选择等领域【2 2 1 。 微粒群优化算法是由e b e r h a r t 博士和k e n n e d y 博士发明。源于对鸟群捕食的行 为研究。微粒群算法同遗传算法类似，是一种基于迭代的优化工具。系统初始化为 一组随机解，通过迭代搜寻最优值。目前已广泛应用于函数优化，神经网络训练， 模糊系统控制以及其他遗传算法的应用领域。微粒群优化算法也是起源对简单社会 系统的模拟，晟初设想是模拟鸟群觅食的过程，但后来发现微粒群算法是一种很好 的优化工具。 7 微粒群算法在动态优化中的应用研究 2 2 微粒群算法描述 2 2 1 微粒群算法简介 微粒群算法，又称粒子群优化( p 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 ) 算法，是 1 9 9 5 年由美国社会心理学家k e n n e d y 和电气工程师e b e r h a r t 1 卅共同提出的一种进化 计算技术，来源于对一个简化动物社会模型的模拟。其中“群( s w a r m ) ”符合m m m i l l o n a s t 2 0 】在开发应用于人工生命( a r t i f i c i a ll i f e ) 的模型时所提出的群体智能 的5 个基本原则。“粒子( p a r t i c l e ) ”是一个折衷的选择，因为既需要将群体中的 成员描述为没有质量、没有体积的个体，同时也需要描述他们的速度和加速状 态。 p s o 算法最初是为了图形化的模拟鸟群优美而不可预测的运动。而通过对 动物社会行为的观察，发现群体对信息的社会共享提供一个演化的优势，并以 此作为开发算法的基础。通过加入近邻的速度匹配、并考虑了多维搜索和根据 距离的加速，形成了p s o 的最初版本。之后引入了惯性权重w 来更好的控制开 发( e x p l o i t a t i o n ) 和探索( e x p l o r a t i o n ) ，形成了标准版本。 2 2 2 微粒群算法原理 p s o 算法是基于群体的，根据对环境的适应度将群体中的个体移动到好的 区域。然而它不对个体使用演化算子，而是将每个个体看作是d 维搜索空间中 的一个没有质量、没有体积的微粒( 点) ，在搜索空间中以一定的速度飞行， 这个速度根据它本身的飞行经验和同伴的飞行经验来动态调整。第f 代第f 个微 粒表示为x 。( f ) = ( x t l ( r ) ，x 。2 ( f ) ，x d ( f ) ) 。它经历过的最好位置( 有最好的适应值) 记为p ，( f ) = ( p n ( f ) ，p ，2 ( r ) ，p 仍( ，) ) ，也称为p 6 删( r ) 。在群体所有微粒经历过的最 好位置的索引号用符号g 表示，即p 。( ，) ，也称为g 。吲( f ) 。第f 代微粒f 的速度用 ( f ) = ( ，。l ( f ) ，2 ( 叽，d ( ，) ) 表示。对每一代，它的第d 维( 1 d d ) 根据如下方 程进行变化： v o ) = w v 口( f ) + c j r l ( p o ) 一x p ( f ) ) + c 2 r 2 ( p 日( t ) 一z ( ，) ) ( 2 1 ) x ，o + 1 ) = x “( t ) + v 口( f + 1 ) ( 2 2 ) 其中w 为惯性权重( i n e r t i aw e i g h t ) ，c l 和c 2 为加速常数( a c c e l e r a t i o nc o n s t a n t s ) ， 和，2 为两个在 0 ，1 范围里变化的随机值。此外，微粒的速度被一个最大速度 l z m a x 所限制。如果当前对微粒的加速导致它的在某维的速度v 耐超过该维的最 大速度v d ，则该维的速度被限制为该维最大速度v m 麒d 。 第二章微粒群算法研究综述 对公式( 2 1 ) ，第一部分为微粒先前行为的惯性，第二部分为“认知 ( c o g n i t i o n ) ”部分，表示微粒本身的思考：第三部分为“社会( s o c i a l ) ”部分，表示 微粒间的信息共享与相互合作。“认知”部分可以由t h o m d i k e 的效应法贝t j ( l a wo f e f f e c t ) 所解释，即一个得到加强的随机行为在将来更有可能出现。这里的行为 即“认知”，并假设获得正确的知识是得到加强的，这样的一个模型假定微粒被 激励着去减小误差。“社会”部分可以由b a n d u r a 的替代强化( v i c a r i o u s r e i n f o r c e m e n t ) 所解释。根据该理论的预期，当观察者观察到一个模型在加强某 一行为时，将增加它实行该行为的几率。即微粒本身的认知将被其它微粒所模 仿。p s o 算法使用如下心理学假设：在寻求一致的认知过程中，个体往往记住 自身的信念，并同时考虑同事们的信念。当其察觉同事的信念较好的时候，将 进行适应性地调整。 2 2 3 标准微粒群算法流程如下 s t e p l 初始化一群微粒( 群体规模为m ) ，包括随机的位置和速度； s t e p 2 评价每个微粒的适应度； s t e p 3 对每个微粒，将它的适应值和它经历过的最好位置p 。删的作比较，如果 较好，则将其作为当前的最好位置p 。删； s t e p 4 对每个微粒，将它的适应值和全局所经历最好位置g 胁的作比较，如果 较好，则重新设置g 。吲的索引号； s t e p 5 根据方程( 2 1 ) 和( 2 2 ) 变化微粒的速度和位置； s t e p 6 如未达到结束条件( 通常为足够好的适应值或达到一个预设最大代数 g m a x ) ，回到s t e p 2 ) 。 2 2 4 标准微粒群算法参数分析 p s o 参数包括：群体规模坍，惯性权重w ，加速常数c 1 和c 2 ，最大速度 v m a x ，最大代数g m a x 。v m a x 决定在当前位置与最好位置之间的区域的分辨 率( 或精度) 。如果vm a x 太高，微粒可能会飞过好解，如果v m a x 太小，微粒 不能进行足够的探索，导致陷入局部优值。该限制有三个目的：防止计算溢出； 实现人工学习和态度转变；决定问题空间搜索的粒度。惯性权重w 使微粒保持 运动的惯性，使其有扩展搜索空间的趋势，有能力探索新的区域。加速常数c 1 和 f 2 代表将每个微粒推向p 。鲫和g 姗位置的统计加速项的权重。低的值允许微粒 9 微粒群算法在动态优化中的应用酽究 在被拉回来之前可以在目标区域外徘徊，而高的值导致微粒突然的冲向或者越 过目标区域。 如果没有后两部分，即c l = c 2 = 0 ，微粒将一直以当前的速度飞行，直到到 达边界。由于它只能搜索有限的区域，将很难找到好的解。如果没有第一部分， 即w = 0 ，则速度只取决于微粒的当前位置、它们的历史最好位置p 胁，和群体的 全局最好位置g 胁，微粒本身没有记忆性。假设一个微粒位于全局最好位置， 它将保持静止。而其它微粒则飞向它本身最好位置p 。吲和全局最好位置g 。删的加 权中心。在这种条件下，微粒群将统计的收缩到当前的全局最好位置，更像是 一个局部算法。在加上第一部分后，微粒有扩展搜索空间的趋势，即第一部分 有全局搜索的能力。这也使得w 的作用为针对不同的搜索问题，调整算法全局 和局部搜索能力的平衡。如果没有第二部分，即c l = 0 ，则微粒没有认知能力， 也就是“只有社会( s o c i a l o n l y ) ”的模型。在微粒的相互作用下，有能力到达新的 搜索空间。它的收敛速度比标准版本更快，但是对复杂问题，比标准版本更容 易陷入局部优值点。如果没有第三部分，即c 2 = 0 ，则微粒之间没有社会信息共 享，也就是“只有认失n ( c o g n i t i o n o n l y ) ”的模型。因为个体间没有交互，一个规模 为m 的群体等价于m 个单个微粒的运行。因而得到解的几率非常小。 2 2 5 微粒群算法与其它进化算法的比较 1 、微粒群算法与遗传算法( g a ) 的比较 遗传算法是基于生物进化理论的原理发展起来的一种广为应用的、高效的随机 搜索与优化的方法。其主要特点是群体搜索策略和群体中个体之间的信息交换，搜 索不依赖于梯度信息。它是在7 0 年代初期由美国密执根( m i c h i g a n ) 大学的霍兰 ( h o l l a n d ) 【2 4 】教授发展起来的 遗传算法最初被研究的出发点不是为专门解决最优化问题而设计的，它与进化 策略、进化规划共同构成了进化算法的主要框架，都是为当时人工智能的发展服务 的。近几年来，遗传算法主要在复杂优化问题求解和工业工程领域应用方面，取得 了一些令人信服的结果，所以引起了很多人的关注。在发展过程中，进化策略、进 化规划和遗传算法之间差异越来越小。遗传算法成功的应用包括：作业调度与排序、 可靠性设计、车辆路径选择与调度、成组技术、设备布置与分配、交通问题等等。 微粒群和遗传算法有很多共同之处：两者都随机初始化种群；都使用适应值来 评价系统；而且都根据适应值来进行一定的随机搜索；两个系统都不是保证一定找 1 0 第二章微粒群算法研究综述 到最优解。但是，p s o 没有遗传操作如交叉( c r o s s o v e r ) 矛d 变异( m u t a t i o n ) ，而是根据 自己的速度来决定搜索；同时粒子还有记忆；两者信息共享机制也很不相同。 2 、微粒群算法与演化规划的比较1 2 5 j 作为进化计算方法，p s o 算法与演化规划很相似。然而，p s o 算法中的微粒只朝 一些根据群体经验认为是好的方向飞行，而不像演化规划中通过随机函数变异到任 何方向。也就是说，p s o 算法执行的是有“意识( c o n s c i e n c e ) ”的变异【2 6 1 。从理论上 讲，演