（计算机应用技术专业论文）信息交互与处理微粒群算法.pdf

中文摘要 微粒群算法是受自然界动物群体行为启发而产生的一种群体智能优化算法，其 生物学依据是同物种间信息的交互共享有利于物种生存。但标准微粒群算法中微粒 共享的信息较少，仅限于群体历史经验。因而本文借鉴被动c o n g r e g a t i o n 微粒群算法， 通过拓展信息交互的方式，增强信息处理的能力，对微粒群算法的算法结构进行了 改进。 被动c o n g r e g a t i o n 微粒群算法在标准微粒群算法的基础上，增加一随机选择的微 粒作为第二个共享信息来源，从而在一定程度上提高了算法的效率，但由于信息的 随机性导致该算法不太稳定。针对被动c o n g r e g a t i o n 微粒群算法的不足，本文将近邻 个体中的当前最优位置作为信息交互因子，然后结合环型和小世界模型将其引入标 准微粒群算法中，提出了近邻个体交互微粒群算法。该算法中的每_ 个体都与其近 邻个体进行频繁的信息交换，且近邻成员的当前状态对该个体下一步运动有显著影 响，从而较为符合生物学的研究成果。仿真实验表明其性能明显优于被动c o n g r e g a t i o n 微粒群算法，尤其对于多峰高维测试函数。 近邻个体交互微粒群算法通过增加邻域内个体间的信息共享程度，能较好的提 高算法性能，但个体历史经验、群体历史经验及邻域内当前最优位置的信息在某些 时刻具有一定的重复，从而影响了信息的吸收。为进一步改善近邻个体交互微粒群 算法的性能，本文以个体邻域当前共享信息来替代个体历史经验，仅保留群体历史 经验和个体邻域当前位置共享信息，提出了邻域共享微粒群算法。实验结果说明它 能较大幅度的提高算法性能。 微粒群算法模拟了鸟群、鱼群等动物群体的觅食行为，而动物在觅食过程中总 是倾向于以更小能量消耗获取更多的食物资源，以达到觅食能效最大。因此本文结 合将动物最优觅食规则引入微粒群算法，提出了最优觅食微粒群算法。该算法将群 体成员间的适应值差别与其距离的比值作为个体觅食能效，并设定个体趋向于当前 觅食能效吸引力最大的位置。仿真结果说明了此策略的有效性。 关键词：微粒群算法；近邻个体交互；环型拓扑；小世界邻域；邻域共享信息； 最优觅食原则；高维多峰函数 a b s t r a c t a sap o p u l a t i o n b a s e di n t e l l i g e n to p t i m i z a t i o na l g o r i t h m ，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 ) s i m u l a t e st h ea n i m a ls o c i a l b e h a v i o r sa c c o r d i n gt ot h e i n f o r m a t i o ns h a r i n ga m o n gp a r t i c l e s h o w e v e r , d u et ot h el i m i t e dg r o u p h i s t o r i c a l e x p e r i e n c e ，t h ep e r f o r m a n c e o fs t a n d a r d p a r t i c l e s w a r m o p t i m i z a t i o n ( s p s o ) i sn o ta l w a y sw e l l t h e r e f o r e ，i n s p i r e db yt h ep a r t i c l e s w a r mo p t i m i z a t i o nw i t hp a s s i v ec o n g r e g a t i o n ( p s o p c ) ，t h i sp a p e rp r o v i d e s s e v e r a lv a r i a n t sb ye n h a n c i n gt h ei n f o r m a t i o ni n t e r a c t i o na n dp r o c e s s i n g c a p a b i l i t i e s a san o v e lv a r i a n t ，p s o p ci m p r o v e st h ep e r f o r m a n c eb ya d d i n gan e w s t o c h a s t i ci n f o r m a t i o ns o u r c ep a r t i c l e h o w e v e r , t h es t a b i l i t yi sn o tv e r yw e l l d u et ot h i sa d d i t i o n a lr a n d o m n e s s t h e r e f o r e ，t oi m p r o v et h ep s o p c ，t h i s p a p e rp r o p o s e s n e a r e s tn e i g h b o ri n t e r a c t i o np a r t i c l es w a r mo p t i m i z a t i o n ( n n i p s o ) ，t a k i n gt h eb e s tc u r r e n tp o s i t i o na m o n gn e a r e s tn e i g h b o r s a s i n f o r m a t i o ni n t e r a c t i o nf a c t o ri nn e i g h b o r h o o d ( i n c l u d i n gr i n ga n ds m a l l w o r l dm o d e lt o p o l o g y ) ，w h i c hp r o v i d e saf r e q u e n t l ye x c h a n g ew i t hi t s n e a r e s tn e i g h b o r si no r d e rt og e ti n f o r m a t i o nf a s t e ra n dm o r ea c c u r a t e l y t h e e x p e r i m e n t a lr e s u l t si n d i c a t et h a tt h ea b o v ev e r s i o ni s m o r ee f f i c i e n c yt h a n t h r e eo t h e rf a m o u sm o d i f i c a t i o n s ，e s p e c i a l l yo nh i g hd i m e n s i o n a lm u l t i m o d a l f u n c t i o n s n e a r e s tn e i g h b o ri n f o r m a t i o ni n t e r a c t i o nr e s u l t si nt h es h a r i n go f i n f o r m a t i o ni nn e i g h b o r h o o d ，m o r e o v e r , i n d i v i d u a l sm a y b e n e f i t st h ec u r r e n t f i n d i n g sa n dp r e v i o u se x p e r i e n c eo fo t h e rg r o u pm e m b e r s s u g g e s t e db y t h e a b o v e ，t h i sp a p e rr e p l a c e st h ei n d i v i d u a le x p e r i e n c eb yt h en e a r e s tn e i g h b o r i n t e r a c t i o nf a c t o ri nn n i p s o ，a n dp r o p o s e st h en e i g h b o r h o o ds h a r i n g p a r t i c l e s w a r mo p t i m i z a t i o n ( n s p s o ) t oi m p r o v et h e p e r f o r m a n c eo f n n i p s o s i m u l a t i o nr e s u l t sv e r i f yt h ee f f i c i e n c yo fn s p s o p s oi sas i m u l a t i o no fg r o u pf o r a g i n gp r o c e s s ，i nw h i c ha n i m a l st e n dt o g e tm o r ef o o de n e r g ya tl e s sc o s tt om a x i m i z et h ef o r a g i n ge n e r g ye f f i c i e n c y m a n ym o d i f i c a t i o n so fp s o h a v eb e e np r o p o s e ds of a r , h o w e v e r , t h e yd i d n t i i i a p p l yt h ea b o v eo p t i m a lf o r a g i n gr u l e t h e r e f o r e ，t h i sp a p e r d e f i n e sf o r a g i n g e n e r g ye f ! f i c i e n c ya st h er a t i ob e t w e e nf i t n e s sd i f f e r e n c ea n dd i s t a n c eo ft w o i n d i v i d u a l sa n dp u t sf o r w a r dt h eo p t i m a lf o r a g i n go p t i m i z a t i o n ( o f p s o ) ，i n w h i c he a c hp a r t i c l et r e n d st oi t sl a r g e s te n e r g ye f f i c i e n c yl o c a t i o na m o n g n e i g h b o r sa tt h es a m ei t e r a t i o n t h e s i m u l a t i o nr e s u l ts h o w st h es t r a t e g y i m p r o v e st h ep e r f o r m a n c eo fp s 0s i g n i f i c a n t l y k e y w o 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 n ；n e a r e s tn e i g h b o ri n t e r a c t i o n ； 硒n gt o p o l o g y ；s m a l lw o r l dn e i g h b o r h o o d ；n e i g h b o rs h a r i n gi n f o r m a t i o n ； o p t i m a lf o r a g i n gr u l e ；h i g hd i m e n s i o n a lm u l t i m o d a lf u n c t i o n s i v 声明尸叫 本人郑重声明：所呈交的学位论文，是本人在指导教师的指导下， 独立进行研究所取得的成果。除文中已经注明引用的内容外，本论文 不包含其他个人或集体已经发表或撰写过的科研成果。对本文的研究 做出重要贡献的个人和集体，均已在文中以明确方式标明。本声明的 法律责任由本人承担。 作者签名：盗l 兰羞日期：a 鱼鳗：鱼生：幺显 关于学位论文使用权的说明 本人完全了解太原科技大学有关保管、使用学位论文的规定，其 中包括：学校有权保管、并向有关部门送交学位论文的原件、复印 件与电子版；学校可以采用影印、缩印或其它复制手段复制并保存 学位论文；学校可允许学位论文被查阅或借阅；学校可以学术交 流为目的，复制赠送和交换学位论文；学校可以公布学位论文的全 部或部分内容( 保密学位论文在解密后遵守此规定) 。 作者签名：盛a 当 日期：a 鱼q 翌：鱼生么显 导师签名： 日期： 第一章引言 第一章引言 1 1 最优化方法 从数学角度说，最优化方法是求最值的方法，就是在一组约束为不等式或者等 式的前提下，使目标函数达到最大或最小【l 】o 一般来讲，最优化方法就是为了达到最 优化目标所提出的各种解决办法。随着社会生产发展要求的不断提高，科学技术尤 其是计算机技术的发展，数学方法与理论必将广泛深入渗透到各个学科和应用领域。 最优化方法及其理论必将起到越来越重要的作用。 最优化方法用来解决最优化问题的。最优化问题可分为多种类型：以约束情况 为依据可分为约束优化问题与无约束优化问题；以目标个数为依据可以分为单目标 问题与多目标问题；以问题性质为依据可分为确定性优化问题和模糊性优化问题， 以变量性质为依据分为连续变量与离散变量优化问题；以极值个数为依据可以分为 单峰优化问题和多峰优化问题；以函数关系为依据可分成线性优化问题与模糊性优 化问题等。优化问题的一般形式可写为： m i l l 咖= ( x )( 1 1 ) 其中x s = 肛ig ，( x ) 0i = 1 ，d ) ( 1 2 ) x 是d 维优化变量；妒= f ( x ) 是目标函数，g ，( x ) 是约束函数，它们都是定义在x 上 的实值函数。s 称为约束域。通常最大优化问题可转化为最小优化问题：咖= 一厂( x ) ； 对于约束条件& ( x ) 0 也可转化为一g ，( x ) 0 ，所以上述式子描述的优化问题具有 一般性。 当g ，( x ) o ，江1 ，m 所限制的为整个d 维欧氏空间，即尺d 时，上述优化问题 简化为无约束全局最小优化问题，也就是： m i n 驴= 厂( x )( 1 3 ) 其中xsrd ( 1 4 ) 当x 仅是约束域空间空间的子集即x bcs r d 时，上述无约束全局优化问题就 成为无约束局部最小优化问题。如无特别说明本文下面章节提到的优化问题均为无 约束全局最小优化问题。 优化问题的求解一般有确定性的和随机的两种优化算法。一般确定性算法是从 给定的一个初始点开始，依据一定的规则寻找下一个使得目标函数得到改善的更优 解，直至满足条件为止。n e w t o n r a p h s o n 法、共轭梯度法、 b r o y d e n - f l e t c h e r - g o l d f a r b - s h a n n 法、f l e t c h e r - r e e v e s 法、p o l a r - r i b i e r e 法、 1 信息交互与处理微粒群算法 d a v i d o n f l e t c h e r - p o w e r 法都是确定性优化算法。所有这些确定优化算法均对目标函 数有一定的解析性质要求，例如n e w t o n r a p h s o n 法除要求目标函数连续可微外还要 求它的一阶导数连续。但是工业生产和科学领域的大量实际问题大都是动态的，多 峰的、非线性的或者不具有任何导数信息。这些复杂优化问题用传统确定性算法难 以解决。为了克服这一困难，高效的优化算法成为科学工作者的研究目标之一。当 前科学技术多学科相互交叉渗透、相互影响，在计算机科学领域更为突出。研究者 通过模拟某些自然现象和过程提高优化算法性能。这些算法包括遗传算法【2 j 、进化规 划【3 】、进化策略4 1 。模拟退火算法【5 1 、禁忌搜索6 1 、群体智能算法( 蚁群算法【7 】，微 粒群算法【8 9 】，人工蜂群算法【1 0 1 ，人工鱼群算法【1 1 , 1 2 1 ) 等，它们的思想和内容涉及生物 进化、物理学、数学、人工智能等多个方面。由于这些算法构造的直观性及其内含 的自然机理，因此通常被称为智能优化算法。它们的出现为解决复杂问题提供了新 的思路和手段。 1 1 1 遗传算法 遗传算法【2 】是模拟达尔文生物进化论的自然选择和遗传学机理的生物进化过程 的搜索最优解的方法，它最初由美国m i c h i g a n 大学j h o l l a n d 教授于1 9 7 5 年首先提 出来的。遗传算法的操作对象为一组二进制串。算法从代表问题可能的潜在解集的 一个种群开始，第一代种群产生之后，按照优胜劣、汰适者生存的规则，逐代演化 产生出越来越好的近似解，在每一代，根据问题域中个体的适应值大小选择个体， 并借助于自然遗传学的遗传算子进行组合交叉和变异，产生出代表新的解集的种群。 这个过程会使种群像自然进化一样的后代种群比前代更加适应于环境，最后一代种 群中的最优个体解码后作为问题近似最优解。遗传算法已经广泛应用于人工生命、 图象处理、生产调度问题、自动控制、机器人学、遗传编码和机器学习等方面。 1 1 2 进化策略 进化策略【4 】是由德国柏林工业大学的i r e c h e n b e r g 和h p s c h w e f e l 等在2 0 世纪 6 0 年代初提出的。原始的演化策略是种群中只包含一个单独个体且只使用变异操作。 它与遗传算法的不同就是进化策略直接在空间上进行遗传操作，着重的是子代与父 代的比较选择。 1 1 3 进化规划 美国科学家l a w r e n c ej f o g e l 等人在2 0 世纪6 0 年代最早提出了进化规划【3 】。其 在求解连续参数优化问题时与进化策略区别很小。进化规划仅使用变异与选择算子， 而不使用重组算子。对父代个体采用基于正态分布的变异操作进行变异，生成相同 2 第一章引言 数量的子代个体，这一点与进化策略的变异相类似。 1 1 4 模拟退火算法 模拟退火算法【5 j 来源于固体退火原理：将固体加温至充分高，再让其逐渐冷却， 加温时，固体内部粒子随温升变为无序状，内能增大，而逐渐冷却时粒子渐趋有序， 在每个温度都达到平衡态，最后在常温时达到基态，内能减为最小。根据m e t r o p o l i s 准则，粒子在温度t 时趋于平衡的概率为e a e ( k t ) ，其中e 为温度t 时的内能，a e 为其改变量，k 为b o l t z m a n n 常数。用固体退火模拟组合优化问题，将内能e 模拟为 目标函数值f 温度t 转化为控制参数t ，即得到解组合优化问题的模拟退火算法： 由初始解i 和控制参数初值t 开始，对当前解重复“产生新解_ 计算目标函数差_ 接 受或舍弃”的迭代，并逐步衰减t 值，算法终止时的当前解就是所得近似最优解，这 是基于蒙特卡罗迭代求解法的一种启发式随机搜索过程。退火过程由冷却进度表 ( c o o l i n gs c h e d u l e ) 控制，包括控制参数的初值t 及其衰减因子t 、每个t 值时的迭代 次数l 和停止条件s 。 1 2 群体智能算法 群体智能算法是模拟自然界生物的群体行为来构造随机优化算法。群体智能算 法的研究开始于上世纪9 0 年代初，常见的群体智能算法有蚁群算法、人工蜂群算法、 人工鱼群算法、微粒群算法。 1 2 1 蚁群算法 蚁群算法又称蚂蚁算法【| 7 1 ，是一种用来在图中寻找优化路径的概率算法。它由 m a r c od o r i g o 7 1 于1 9 9 2 提出的，其思想来源于蚂蚁在寻找食物过程中发现路径的行 为。在寻找食物的过程中，蚂蚁会不断释放信息素。蚂蚁多的地方信息素也多，假 设从蚁窝通向食物点有两条路，开始的时候，同样数量的蚂蚁走这两条路。当蚂蚁 沿着一条路到达终点以后会马上返回来，这样，短路径上的蚂蚁来回一次的时间就 短，那么相同时间内重复的次数多，因而在单位时间里会有更多的蚂蚁走过短路径， 留下的信息素自然也会多，自然会吸引更多的蚂蚁过来，从而留下更多的信息 素；但是长路径与此相反。最后越来越多的蚂蚁聚到短路径上来，近似最短路 径就找到了。 1 2 2 人工蜂群算法 蜜蜂是群居社会性昆虫，虽然单个昆虫的行为极其简单，但是由简单个体所组 成的群体却表现出极其复杂的行为。真实的蜜蜂种群能够在任何环境下，以极高的 信息交互与处理微粒群算法 效率从食物源( 花朵) 中采集花蜜。蜜蜂群具有三型分- t - 蜂王，雄蜂，工蜂。蜂王的 任务是产卵，分泌的蜂王物质激素可以抑制工蜂的卵巢发育，并且影响蜂巢内的工 蜂的行为。雄蜂的任务是和处女王交配后繁殖后代，雄蜂不参与酿造和采集生产。 工蜂的任务主要是采集食物、哺育幼虫、泌蜡造巢、泌浆清巢、保巢攻敌等工作。 在工蜂在采集食物过程中也存在分工：侦查蜂和跟随蜂。侦查蜂外出寻找食物，找 到后回巢通过不同类型的舞蹈将食物信息( 食物源丰富程度与食物距离方位信息) 传给巢内工蜂，工蜂按照食物源的收益对其进行分析从而决定是否成为此侦查蜂的 跟随者。受上述工蜂的分工合作及其外界环境交流后能自发地选择完成觅食的这一 过程的规律的启发，土耳其e r e i y e s 大学教授k a r a b o g a 在2 0 0 5 年提出了人工蜂群算法 【1 0 1 。它的主要特点是不需要了解问题的特殊信息，只需要对问题进行优劣的比较， 通过人工蜂个体的局部寻优行为，最终在群体中使全局最优值突现出来，有着较快 的收敛速度。 1 2 3 人工鱼群算法 鱼群均具有觅食、聚集、追尾行为现象，其中觅食行为：一般情况下鱼在水中 随机游动，当发现食物时，则会逐渐向食物多的方向快速游去；聚群行为：鱼在游动过 程中为了保证自身的生存和躲避危害会自然地聚集成群，追尾行为：当鱼群中的一 条或几条鱼发现食物时，其临近的伙伴会尾随其快速到达食物点。人工鱼群算法【l l ，1 2 】 通过构造人工鱼来模仿鱼群的觅食，聚集及追尾行为从而实现寻优。 微粒群算法在下一节中做详细介绍 1 3 微粒群算法 受早期对鸟类群体行为研究的启发，美国社会心理学家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 利用生物学家f r a n kh e p p n e r 的生物群体模型【1 3 】在1 9 9 5 年提 出了微粒群算法 8 。 1 3 1 微粒群算法 本论文将讨论如下的数值优化问题： m i n f ( x ) ，x 卜x 。，x 瑚，】“r d( 1 5 ) 微粒群算法是一种群体智能优化算法，将鸟群中的每只鸟看作是d 维搜索空间 中的一个无质量、无体积的微粒( p a r t i c l e ) ，并在搜索空间中飞行；它将搜索空间中 微粒f 目前已经发现的食物最丰富点看作个体历史最优位置z = ( p 订，p 眨p d ) ，将 目前群体已经发现的食物最丰富的位置看作群体最优位置乞= ( p g l p 9 2 p g ) 。每 4 第一章引言 个微粒都具有位置和速度两个变量，若设x ，( ，) = ( x ，( f ) ，x ，：( ，) ，x d ( ，) ) 为微粒f 在第f 代的位置，k ( ，) = ( v “f ) ，v ，：( 吐，d ( r ) ) 表示微粒，在第，代的速度。微粒群算法的进 化方程如下： v c ，o + 1 ) = v ( f ) + c l ，( f ) 一x ，o ) ) + c 2 厂2 幻( f ) 一x ，o ) ) ( 1 6 ) x 口( f + 1 ) = x p o ) + v l ，o + 1 ) ( 1 7 ) 其中，下标扩代表微粒f 的第歹维，c ，与c ：为加速常数，_ ，：是0 与1 之间相互 独立的均匀分布的随机数。为保证算法稳定性，算法规定了最大速度上限v 一，即 v di v 一。 本文所述的优化问题均为最小优化问题，所以设厂( x ) 为最小化目标函数。则p 和0 由下式确定： 尸mj 尸( 一1 ) 厂( x 俐厂( p ( 一1 ) ) ”7 【x ，( f ) f ( x 以) ) 厂( o 一1 ) ) 足( f ) p l ( f ) ，最( f ) 只( f ) j ( 1 8 ) ( 足( ，) ) = r a i n 杪( 鼻( r ) ) ，厂( 忍( f ) ) 厂( 只( f ) ) 其中n 为群体规模。 1 3 2 标准微粒群算法流程 s t e p l 种群初始化：设定群体规模，各微粒的初始位置均匀分布在 _ x 一，x r ( 测试函数的定义空间) ，设定最大速度上限，速度向量则均匀分布在 - - t , m m ，1 ，一r 中，个体历史最优位置鼻等于各微粒初始位置，群体最优位置只为适应 值最好的微粒所对应的位置，f = 0 ； s t e p 2 参数初始化：设置惯性权重c o ，加速度系数q ，c ：； s t e p 3 根据方程( 1 6 ) 计算微粒下一代的速度；按照公式i1 ，打i ，一对速度进行 限制； s t e p 4 根据方程( 1 7 ) 计算微粒下一代的位置并对其进行修正，f = f + 1 ； s t e p 5 计算每个微粒的适应值； s t e p 6 依据公式( 1 8 ) 更新每个微粒的历史最优位置和群体最优位置只； s t e p 7 如果没有达到结束条件，则返回s t e p 3 否则，输出最优结果。 信息交互与处理微粒群算法 1 3 3 微粒群算法的研究背景和现状 为了提高算法计算效率，y s h i 等将惯性权重引入微粒群算法引。实验证明大的 惯性权重可以群体偏向全局搜索，而小的惯性权重使微粒群进行局部搜索；惯性权 重从0 9 线性递减到o 4 能够取得良好效果。以后的诸多改进多以此为标准，所以称 上述改进为标准微粒群算法( s t a n d a r dp s o ，s p s o ) i l 4 。 惯性权重可以有效调整微粒的搜素速度。有关惯性权重的调整除上述所述的线 性调整外还有y s h i 和r c e b e r h a r t ，提出的基于模糊系统的惯性权重的动态调整 ( f i w ) i s 】；r e i j e r s 提出的机惯性权重策略( w ) 【16 】；动态改变惯性权重的自适应策 略( d c w ) t 1 7 】；非线性减小惯性权重的策略【1 s 】。其中f i w 策略需要专家知识建立模糊 规则；实现难度较大；r i w 策略被用于求解动态系统。c 1 e r c 【1 9 j 提出了将收缩因子引 入微粒群算法，该因子可以有效地控制参数，以确保算法收敛。如能正确地选择收 缩因子，就可以不用考虑最大速度上限对速度的影响。碌 微粒群算法的其他系数也可以调节微粒的全局与局部搜索能力。为进步加快 算法收敛速度a s a n g ar a t n a w e e r a l 2 0 】等提出了加速系数随时间变化的改进微粒群算法 ( p s ow i t ht i m e v a r y i n g a c c e l e r a t i o nc o e f f i c i e n t s ，t v a c ) ：在搜索过程中加大社会系 数逐渐以增加个体对群体历史信息的利用，降低个体认知系数以减少个体经验的作 用；从而使群体最终达到更好的位置。基于动物个体的差异性，利用微粒当前适应 值的大小调整各微粒参数设置，蔡星娟等【2 1 】提出了个性化微粒群算法。 微粒群算法有两种不同版本【2 2 】：全局最优模型与局部最优模型。在全局最优模 型中，整个算法以该微粒为吸引子，使所有微粒将最终收敛于该位置。这样，如果 在进化过程中，该最优解得不到有效的更新，则微粒群将出现类似于遗传算法中的 早熟现象。而局部模型采用多吸引子代替全局最优模型中的单一吸引子，可以部分 克服此问题。微粒的邻域结构影响算法性能，不同的邻域结构可以在微粒之间实现 不同程度的信息共享。k e n n e d y 和m e n d e s l 2 3 系统地分析了不同的种群拓扑结构对p s o 算法效能的影响，如：影响种群结构的节点间最短平均距离，节点连接方式、拓扑 结构、以及节点聚合问题与具体优化问题的相关性等问题，发现邻域结构非常影响 算法的性能，而且最佳拓扑形式因问题而定。s u g a n t h a n 2 4 】引入了一种动态改变的邻 域算子，优化初始阶段邻域为个体自身，随着迭代次数的增长，邻域范围逐渐扩大 至整个群体，一定程度上避免了过早收敛，获得了较标准微粒群算法更好的效果。 p e e r 等瞳5 3 针对g b e s t 、l b e s t 以及v o nn e u m a n n 等邻域结构提出了一种保证收敛的微粒 6 第一章引言 群算法，通过比较得出：对于单峰优化函数，邻域连接越多搜索效果越好，而对于 多峰函数优化，则一般情况下，邻域连接越少搜索性能越好。夏小翔、曾建潮等啪1 提出了一种基于元胞自动机的小生境微粒群算法。受小世界模型启发，王芳穆华 平乜8 1 分别将将小世界模型、无标度网络应用于微粒群算法。 从个体信息交互及处理角度看，为了提高信息的利用率，m o n s o n 2 9 , 3 0 1 借鉴 k a l m a n 滤波的形式，提出了一种卡尔曼微粒群算法：个体过滤获取的位置及速度信 息，并利用滤得的信息来调整微粒的移动方向。曾建潮等【3 l j 提出的广义微粒群算法 则从生物学角度对微粒群算法进行有益的扩充。受动物群体内部信息共享机制【3 2 】的 启发，s h e 掣3 3 】在s p s o 中增加了一个随机选择的微粒位置作为第三个信息来源， 提出了带有被动c o n g r e g 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 nw i t h p a s s i v ec o n g r e g a t i o n ，p s o p c ) ，对标准微粒群算法进行了结构调整。 r i g e t 3 4 】将“吸引”( a t t r a c t i v e ) 和“扩散”( r e p u l s i v e ) 两个算子引入微粒群算 法，它们可以动态地调整“勘探 与“开发”比例，从而能更好地提高算法效率。 为了提高算法多样性，减慢算法的收敛速度，k e n n e d y 等提出了f i p s o 3 5 j 利用了： 个体仅能其感知其邻域范围内个体，从而最终使微粒到达邻域内同伴的加权位置； 利用生物界中物种发现生存密度过大时会自动分家迁移的习性，h e 等【3 6 】引入群体逃 逸行为以提高微粒群的多样性。j 。j l i a n g 了7 】提出了针对多峰函数全局优化的综合学习 微粒群算法，个体可从群体中的任一成员处获取信息，将收敛中心替换成任意个体 的历史最优位置，有效增加了种群多样性，但是缺乏优化的针对性。 o z c a n 和m o h a i l 【3 8 】首先对微粒群算法的行为进行了分析并给出了收敛公式，针 对上述收敛公式，m c l e r c 3 9 】分别采用代数方法、解析分析和状态空间对微粒算法的 运行轨迹进行分析，并给出了各微粒的收敛点位置。j i a n g 4 0 m 】等将微粒群中的每一 微粒的运动轨迹看作随机过程，得到更为完整的结果。v a nd e nb e r g h 4 3 】首先证明了 微粒群算法的收敛性：标准微粒群算法既不是全局收敛算法，也不是局部收敛算法。 v i s a k a nk a d i r k a m a n a t h a i l 等对微粒群算法进行了稳定性分析，并给出了算法稳定的 充分条件m j 。 混合策略可以弥补标准微粒群算法的缺陷，提高其局部搜索能力。例如与蚁群 算法的混合策略【4 5 】与模拟退火算法的混合策略【4 6 】。 微粒群算法具有概念简单，便于实现：需要调整的参数少，计算速度快，收敛 能力强的特点，而且只需要计算函数值，不需要目标函数的梯度信息。所以现已应 用于多目标优化 4 7 , 4 8 】，水印技术【4 9 1 ，调度问题【5 0 ，5 1 1 和神经网络训练【5 2 】等领域中。 7 信息交互与处理微粒群算法 1 3 4 本文主要完成的工作 将微粒群算法中的微粒看作可进行信息交互与处理的智能体，提出了信息共享 微粒群算法；并在此框架下将以最小能量消耗获取最大食物收益的最优觅食规则引 入其中，提出了最优觅食微粒群算法。本文的主要内容有： 第二章：详细介绍了标准微粒群算法的生物学背景。并从生物学信息共享角度， 分析了三算法s p s o ，t v a c ，p s o p c 。 第三章：将近邻个体信息交互因子引入微粒群算法中，提出了近邻个体交互微 粒群算法( n n i p s o ) ，并讨论了其在环型拓扑和小世界模型下的性能，仿真结果证 明了其有效性。 第四章：通过分析近邻个体交互微粒群算法的种群多样性和收敛速度，发现个 体历史最优和近邻个体信息交互因子在同时保证种群多样性。而且从生物学角度来 说：近邻个体信息交互的结果就是邻域内个体间信息共享，个体信息交互因子就是 信息共享因子。而且动物个体可从群体成员的当前发现和先前经验中受益。所以本 文尝试以信息共享因子( 也就是个体交互因子) 取代n n i p s o 中的个体历史最优， 保留群体历史最优提出了邻域共享微粒群算法( n s p s o ) 。实验结果发现，其在高维 多峰问题上的性能大大提高。 第五章：探讨了最优觅食理论在微粒群算法改进中的应用，着重于信息共享之 后的个体的信息处理机制：个体趋向对其来说能效最高的同伴。仿真结果证明了它 的可行性。 8 第二章微粒群算法的生物学背景 第二章微粒群算法的生物学背景 微粒群算法是受自然界中动物群体行为启发而产生的一种随机优化算法。动物 群体( 鸟群、鱼群、昆虫群等) 行为具有稳定的群体组织和时空完整性：群体作为 一个整体不断活动，并在活动过程中保持一定的形状和密度t 3 2 1o 对于群体动物，群 体行为有利有弊但总的来说还是利大于弊。它们是如何聚集，并一起行动的? 自 然选择产生的群体行为模式强调群体个体形态的相似性、行为上的一致性，而且都 遵循相同的规则 3 3 3 。本文拟从觅食过程中动物群体内部信息共享与处理机制为背景 依据，分析并改进微粒群算法。 2 1 群体生活的动物 自然界中动物的食物一般并非均匀分布，有的呈簇状分布，有的呈斑块分布。 但不管食物如何分布与总量多少，群体成员更容易发现食物丰富的区域。同时由于 群体成员众多，个体通过群体可以捕获其单独无法发现或处理的食物。同时处于群 体中，个体平均觅食效率也比单独的个体多。 在群体移动过程中，当其中某个成员发现捕食者时，能快速通过信息传递通知 其他个体，这样可以有效躲避敌害；即使在与捕食者正面相遇时，群体中的个体由 于形态、行为的相似性，也能有效迷惑捕食者，减小被捕食的危险1 5 3 1 0 对于警戒和 觅食是互相排斥的那些物种，例如鸟类，因为个体保持警惕的平均时间会随着群体 规模的增大而减小，因此群体成员会保持一个很高的觅食速度 5 3 o 图2 1 走雁飞行 f i 9 2ig e e s e f l y 求偶交配动物群体形成的原因之一。在繁殖期，群体聚集为成员提供了更 多与异性接触的机会，可方便个体估计其他成员的交配时机，以便群体尽可能同步 产卵受精。这对于那些依靠大量产卵( 如鱼类，蛙类) 才能存活的个体而言作用更 9 一 h - r - r t t t 一1 信息交互与处理微粒群算法 加明显。 生活在群体( 特别是鸟群) 中的个体在运动中借助群体优势( 如图2 1 所示) ， 比单独的个体在一定程度上能降低运动过程中的能量消耗，提高能量利用率。例如： 鸟群v 型编队鸟类并肩排成一排，翼尖对翼尖地飞行，所消耗的能量比单独飞行时 消耗的少。这个节约率，经研究大约是2 2 0 , o 至7 0 5 4 - 5 7 。 许多恒温的物种( 如南极帝企鹅，美洲野牛) 在寒冷的季节聚集有利于保持一 定的体温。一些昆虫聚集对保持温度也是很重要的，例如蜜蜂聚集在一起可将白天 的热量一直保持到晚上；聚集还可减少水分的流失，例如潮区内的无脊椎动物的聚 集【3 2 】。动物聚集形成群体还有其他优势，在此不再赘述。 群体中的个体在享受群体优势的同时，也在付出代价。其中包括资源( 食物、 氧气、阳光等) 的同伴竞争；还有个体自由度( 例如运动、捕食、避敌) 的减小； 群体内个体必须忍受代谢废物和病原体还有群体同伴的寄生效应；而且在大型群体 中，群体成员至少在一个方向上遮挡了其相邻个体的视野，这样个体可能不能及时 发现捕食者或则食物资源【3 2 1 。 既然群体生活有利有弊，那么为什么群体现象如此普遍? 总的来说，个体的聚 集在一起形成群体在一定程度上还是利大于弊：群体促进了其成员的生存与繁衍。 而动物群体生活的大部分优势是通过便利的信息共享与处理选择机制实现的。 2 2 动物群体成员间的信息交互与处理机制 动物都有自身的多种感觉器官( 眼、鼻、口、耳、侧线、皮肤等) ，各感觉器官 感知刺激的种类有异，感知距离、强度不同。同时动物大脑也具有一定的记忆功能。 因此群体成员从外部环境、群体成员、还有自身与群体经验三方面获取信息。 以大规模鸟群为例：一只鸟不可能对群体中的每个同伴都给予同样的关注，而 且是在覆盖很大范围的巨大鸟群中，个体必须对其它成员进行局部感知并过滤这些 感知。鸟群中的成员认识到三个类别：本身、两到三个近邻个体、鸟群的其他个体 【5 8 ，5 9 】 o b r i a np a r t r i d g e 对鱼群的空间关系进行研究【5 9 j 发现：与鱼群中的远距离成员相比， 一条鱼受其近邻个体的影响更强烈。群体中的一个成员受到其他成员影响的程度与 它和其他成员距离的平方或者立方成反比例【5 引。所以，群体中成员对其近邻个体关 注较多。成员作为整体的群体的关注也较多。在群体动物感知中，不管采取哪种感 知形态，相邻者都是个体感知外界信息的重要来源。因此相邻个体间的信息共享普 1 0 第二章微粒群算法的生物学背景 遍存在于群体之中，其有助于群体感知环境变化，及时调整自身状态。 鱼群通常被看作是一种自私的种群，其中的个体总是想设方设法获取群体生 活的大部分优势，而不关心临近个体的相关利益i “1 。这是因为动物具有趋利避害的 本能，总是趋向以更小代价获得更大利益。而动物群体成员与其近邻个体的信息共 享交互最频繁，那它会被附近的优秀个体所吸引，并趋向对其来说利益代价比值更 高的优秀个体。所谓优秀个体在觅食动物群体中指的是占据食物更丰富位景的个体。 如果群体中的个体一旦占据了此优越位置，除非它发现了其他更好的位置或者被迫 离开，否则将继续占据此位置。 综上所述：在动物群体的觅食过程中，个体会与其近邻同伴进行频繁的信息交 互并趋向对其来说利益代价更高的优秀个体位置。这对群体动物具有重要的生存意 义。 2 3 群体动物仿真 微粒群算法是基于简单社会环境的仿真：把智能体( a g e n t ) 看作能够防止碰撞 的鸟，并且原本是用来图形模拟优美而且变幻不定的鸟群飞行【9 】。简单社会环境的仿 真中比较突出的是r e y n o l d s l 5 8 l 和h e p p n e r 与g - r e n a n d e r 1 3 捌提出的两个模型。 图22 鸟群齐飞 f i g2 2b i r d s f l y t o g e t h e r 其中1 9 8 7 年r e y n o l d s 提出了b o i d ( b i r d - o i d ) 模型模拟的是鸟类的聚集飞行过程。 在这个模型中，个体的行为只和它周围近邻个体有关，它只需遵循以下3 条规则雠l ： ( 1 ) 避免碰撞( c o l l i s i o n a v o i d a n c e ) ：避免和近邻个体相碰撞。 ( 2 ) 速度一致( v e l o c i t ym a t c h i n g ) ：与邻近个体平均速度保持一致。 ( 3 ) 向中心聚集( f l o c k c e n t e r i n g ) ：向近邻个体平均位置移动。 而h e p p n e r 、g r e n a n d e r ( 1 9 9 0 ) 蝴提出的模型如下： 信息交互与处理微粒群算法 咖心) = ( r 。m 。+ 凡，+ 曩。删) a t + d p ( t ) v ( f ) = d u 心) ， i = 1 , 2 ，刀 ( 2 1 ) 这里u i ( ，) = ( x i ( t ) ，只( f ) ) 是个体i 在时刻，的位置，瓦。代表了朝向吸引中心( 归巢 区域或食物丰富地点) 的趋势，比代表了相邻成员速度一致的趋势，。删代表 了相邻个体间信息的交互共享；d p ( t ) 为随机均匀分布的向量3 2 1 。 鸟群如何实现群体的协作同步，为大家接受的是h e p p n e r 的观点【1 3 ，6 2 】：群体行 为是个体都遵循的相同运动规则的涌现特性。鸟群行为的同步性被看作是个体试图 维持它们自身与其近邻者之间最优位置【9 1 。上述的两个仿真均强调了近邻成员间当 代位置信息交互的重要性。 2 4 微粒群算法( p s o ) 受动物群体成员交互行为的启发，并利用r e y n o l d s 5 s 1 和h e p p n e