（计算机应用技术专业论文）粒子群算法的改进方法研究.pdf

西南交通大学硕士研究生学位论文第1 页 摘要 在很多实际问题中，例如经济、管理、军事、科学和工程设计等领域都会 涉及到优化问题，但是实际中遇到的许多科学、工程和经济问题呈复杂化、多 极化、非线性、强约束、建模困难等特点，这就使人们对科学技术提出了新的 和更高的要求，其中对高效的优化技术和智能计算的要求尤为迫切。 粒子群优化算法是源于对鸟群捕食行为的研究而发展的一种智能寻优算 法，该方法尤其适用于处理传统搜索方法解决不了的复杂和非线性问题。与遗 传算法类似的粒子群算法是一种基于群体的优化工具，系统初始化为一组随机 解，通过迭代搜寻最优值。但是粒子群算法并没有遗传算法用的交叉以及变异 操作，而是粒子( 潜在的解) 在解的共建过程中追随最优的粒子进行搜索。因此， 粒子群算法一经提出，就受到各国学者的关注，并形成一个研究热点。 本文在阅读了大量有关粒子群算法的文献的基础上，对标准的粒子群算法 研究和分析。在对前人成果的研究的基础上，找出了粒子群算法存在的缺陷即 早熟和易收敛，并针对这两个问题提出了解决的方法。通过上述的研究，提出 了两种改进的粒子群算法。 第一：对粒子群的拓扑模型进行研究。提出了一种核心主子群粒子群优化 算法，并在此基础上，提出了双层局部模式算法，将此算法应用到核心主子群 的粒子群优化算法中。增加了粒子的多样性。 第二：对粒子群算法的速度更新公式进行改进，加入了局部最佳粒子的参 考学习机制，使得粒子的参考学习因子由原来的2 个增加到现在的3 个。并将 核心主子群粒子群优化算法与公式改进的粒子群算法相融合。 最后在算法编程实现上引入了j a 、纶的多线程编程机制，在一定程度上改 善了算法的时间效率。为了验证算法的有效性，将改进的算法应用到求解非线 性方程组中，并取得了较好的实验效果。 关键词：粒子群；粒子群算法的早熟；粒子群算法的收敛；核心主子群 西南交通大学硕士研究生学位论文第1 i 页 a bs t r a c t i nm a n yp r a c t i c a lf i e l d s ，s u c ha se c o n o m i c s ，m a n a g e m e n t ，m i l i t a r y ，s c i e n t i f i c a n de n g i n e e r i n gf i e l d s ，t h e ya r er e l a t e dt oo p t i m i z a t i o np r o b l e m s a n dp r a c t i c a l l y t h ep r o b l e m si nt h o s ef i e l d sa r ev e r yc o m p l i c a t e d ，m u l t i p o l a r i z a t i o n ，n o n l i n e a r ， s t r o n gc o n s t r a i n t s ，a n d h a r dt om o d e l t h e r e f o r e ，t h e r e q u i r e m e n t s a b o u t o p t i m i z a t i o na r ei n c r e a s i n ga n du r g e n t 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 mo r i g i n a t ef r o mt h er e s e a r c ho naf l o c k o fb i r d sb e h a v i o r ，a n dt h e nd e v e l o p sa ni 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 ，t h i s m e t h o di se s p e c i a l l ys u i t a b l et ot h eh a n d i n go ft r a d i t i o n a ls e a r c hm e t h o d sw h i c h a nn o ts o l v et h ec o m p l e xa n dn o n l i n e a rp r o b l e m s a n dg e n e t i ca l g o r i t h mi s s i m i l a rt ot h ep a r t i c l es w a r ma l g o r i t h mw h i c hi sap o p u l a t i o n - b a s e do p t i m i z a t i o n t o o l ，t h es y s t e mi si n i t i a l i z e da sas e to fr a n d o ms o l u t i o n s ，t h r o u g ht h ei t e r a t i v e s e a r c hf o rt h eo p t i m a lv a l u e b u tt h ep a r t i c l es w a r mo p t i m i z a t i o nw h i c hh a sn o c r o s s o v e ra n dm u t a t i o na sg e n e t i ca l g o r i t h m ，t h ep a r t i c l et of o l l o wt h eo p t i m a li n t h eb u i l d i n gt os e a r c ht h es o l u t i o n t h e r e f o r e ，w h e nt h ep a r t i c l es w a r ma l g o r i t h m h a sb e e nf o u n d ，s c h o l a r sf r o mv a r i o u sc o u n t r i e sg i v et h e i ra t t e n t i o n ，a n df o r ma r e s e a r c hh o t s p o t i nt h i sp a p e r ，c o n s u l t e dal o to fl i t e r a t u r ea b o u tp 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 m ，a n d d i dr e s e a r c ha n d a n a l y s i s o nt h es 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 t h r o u g ht h er e s e a r c ho nt h ep r e d e c e s s o r s ，t h ep a p e rf o u n dt h ef l a w o fp 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 t h ef l a wi s p r e m a t u r ea n de a s yt o c o n v e r g e n c e ，f o rt h a tt h ep a p e rg i v et h es o l u t i o nt ot h et w oi s s u e s t h r o u g ht h i s r e s e a r c h ，t h ep a p e rg i v et w om o d i f i e dp a r t i c l es w a r ma l g o r i t h m s f i r s t ，t h et h e s i si n t r o d u c e st h er e s e a r c ho nt h et o p o l o g i c a lm o d e lo fp a r t i c l e s w a r m a n di tp r o p o s e st h ec o r eg r o u po fp 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 a n dt w o t i e rl o c a lm o d e la l g o r i t h m ，w h i c hi sa p p l i e dt ot h ec o r eg r o u po fp a r t i c l e s w a r mo p t i m i z a t i o n i ti n c r e a s e st h ep a r t i c l ev a r i a b i l i t y s e c o n d ，t h et h e s i si m p r o v e st h es p e e do fu p d a t i n gf o r m u l ao ft h ep a r t i c l e s w a r ma l g o r i t h m ，i n c l u d i n gt h el o c a lb e s tp a r t i c ea st h er e f e r e n c el e a r n i n g m e c h a n i s m ，m a k i n gt h el e a r n i n gf a c t o ro fp a r t i c l e sf r o m2t o3 a n di tm i x st h e c o r eo fg r o u pp a r t i c l es w a r ma l g o r i t h mw i t hi m p r o v e df o r m u l aa l g o r i t h m 西南交通大学硕士研究生学位论文第1 i i 页 f i n a l l y , t h et h e s i ss h o w e dt h ep r o g r a m m i n gu s i n gm u l t i t h r e a d i n gj a v a t o ac e r t a i ne x t e n t ，t h ei m p r o v e m e n to ft h et i m ei s e f f i c i e n c y t ov e r i f yt h e e f f e c t i v e n e s so ft h ea l g o r i t h m ，t h ei m p r o v e da l g o r i t h mi sa p p l i e dt os o l v e n o n l i n e a re q u a t i o n s t h er e s u l td e m o n s t r a t e st h a tt h ei m p r o v e m e n ti s v e r y e f f e c t i v e k e yw 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 ；p a r t i c l es w a r mo p t i m i z a t i o no fp r e m a t u r e ； p a r t i c l es w a r mo p t i m i z a t i o no fc o n v e r g e n c e ；c o r eg r o u 西南交通大学学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规定，同意学校保留并向国家有关 部门或机构送交论文的复印件和电子版，允许论文被查阅和借阅。本人授权西南交通大学可以将 本论文的全部或部分内容编入有关数据库进行检索，可以采用影印、缩印或扫描等复印手段保存 和汇编本学位论文。 本学位论文属于 1 保密口，在年解密后适用本授权书； 2 不保密影使用本授权书。 ( 请在以上方框内打“奶 学位论文作者签名：落袋，藿 日期：0 1 0 1 0 s 否f 指导柳虢依绑 日期：刃l 乡，乡( 西南交通大学硕士学位论文主要工作( 贡献) 声明 本人在学位论文中所做的主要工作或贡献如下： 第一，通过对标准粒子群算法的研究分析，对粒子群的拓扑模型进行了研究。提 出了一种核心主子群的粒子群改进算法，从而增加了粒子的多样性。 第二，对粒子群算法的全局模型和局部模型的算法进行研究，提出了双层局部模 型，并将其应用到改进的核心主子群粒子群优化算法中。 第三，在提出的核心主子群的粒子群算法的基础上，对粒子群的速度更新公式进 行了改进，加入了局部最佳粒子的参考学习机制，使得粒子的参考学习因子由原来的 2 个增加到现在的3 个。 第四，将核心主子群的粒子群算法与公式改进的粒子群算法相融合，通过实验验 证，取得了很好的实验效果。 最后，将标准粒子群算法、核心主子群粒子群优化算法和多学习因子的核心主子 群粒子群算法相结合的改进算法应用到求解非线性方程组中，实验证明，改进的算法 取得了较好的实验效果。 本人郑重声明：所呈交的学位论文，是在导师指导下独立进行研究工作所得的成 果。除文中已经注明引用的内容外，本论文不包含任何其他个人或集体已经发表或撰 写过的研究成果。对本文的研究做出贡献的个人和集体，均己在文中作了明确说明。 本人完全了解违反上述声明所引起的一切法律责任将由本人承担。 学位论文作者签名：韵袋、甏 日期：训o e 斟 西南交通大学硕士研究生学位论文第1 页 第1 章绪论 1 1 课题研究的背景与意义 长期以来，人们对优化问题一直都在进行研究和探索，而且优化问题一直 以来就是一个古老的课题。而英国的n e w t o n 和德国的l e i b n i t z 在微积分上的 发明，更进一步推动了优化问题的发展。随着历史的发展，人们对优化问题的 研究工作也不断的深入。但是，、由于社会历史条件的原因，优化问题的发展一 直受到限制。直到上个世纪中叶，由于计算机技术的不断发展和广泛的应用， 使得优化技术不仅成为了一种迫切的需要，而且成了求解最优解的有力的工 具。因此，优化理论和算法迅速发展起来，形成一门新的学科。 在求解优化问题的算法中，通常采用的是局部搜索算法。局部的搜索算法 一般采用迭代的方法来求解问题的解，迭代法也称为辗转法，是一种不断用 变量的旧值来递推新值的过程，跟迭代法相对应的是直接法( 或者称为一次解 法) ，即一次性解决问题，迭代法又分为精确迭代和近似迭代。迭代算法是用 计算机解决问题的一种基本方法。它利用计算机运算速度快、适合做重复性操 作的特点，让计算机对一组指令( 或一定步骤) 进行重复执行，在每次执行这组 指令( 或这些步骤) 时，都从变量的原值推出它的一个新值。迭代法的主要步骤 如下：首先，确定迭代变量。可以在解决的问题中用迭代算法，至少存在一个 直接或间接地不断由旧值递推出新值的变量，这个变量就是迭代变量。其次， 建立迭代关系式。所谓迭代关系式，指如何从变量的前一个值推出其下一个值 的公式( 或关系) 。迭代关系式的建立是解决迭代问题的关键，通常可以使用递 推或倒推的方法来完成。最后，对迭代过程进行控制。在什么时候结束迭代过 程? 这是编写迭代程序必须考虑的问题。不能让迭代过程无休止地重复执行下 去。迭代过程的控制通常可分为两种情况：一种是所需的迭代次数是个确定的 值，可以计算出来；另种是所需的迭代次数无法确定。对于前一种情况，可 以构建一个固定次数的循环来实现对迭代过程的控制，对于后一种情况，需要 进一步分析出用来结束迭代过程的条件。 局部搜索算法通常适用于求解小规模且定义非常明确的问题。在实际问题 的解决过程中，局部的搜索算法总是不能兼顾解的精度和执行的时间，总是达 不到令人满意的效果。因此，寻求一种适合于大规模并行且具有智能特征的算 法已经成为人们研究的目标和方向。 在过去的几十年，受生物体系启发而产生的计算方法不断涌现和发展，该 西南交通大学硕士研究生学位论文第2 页 领域的研究可统称为基于生物体系的计算，也就是从自然生物系统获得灵感， 抽象出有用的计算方法来解决诸多领域的复杂问题。如人工神经网络 ( a n n ) 【2 5 1 、混沌【6 8 】、遗传算法( g a ) 【9 - 11 1 、进化规则( e p ) t 1 2 15 1 、模拟退火 ( s a ) 【16 , 1 7 、禁忌搜索( t s ) 【18 2 1 】等。由于这些算法本身的直观性和自然机理，因 此通常我们把此类算法称为智能优化算法( i 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 s ) 。 粒子群优化算法是源于对鸟群捕食行为的研究而发展的一种智能寻优算 法，该方法尤其适用于处理传统搜索方法解决不了的复杂和非线性问题。与遗 传算法类似，粒子群算法是一种基于群体的优化工具，系统初始化为一组随机 解，通过迭代搜寻最优值。但是并没有遗传算法用的交叉以及变异操作，而是 粒子( 潜在的解) 在解的共建过程中追随最优的粒子进行搜索。由于它采用种群 的方式组织搜索，这使得它可以同时搜索空间内的多个区域，而且这种方式特 别适合大规模的并行计算，具有不受搜索空间的限制性条件( 如可微、连续、 单峰等) 的约束及不需要其它辅助信息( 如导数) 的特点。这种崭新的特点使得粒 子群算法不仅能获得较高的效率而且具有简单、易于操作和通用的特性。因此， 粒子群算法一经提出，立刻引起了进化计算等领域的学者们的广泛关注，并在 短短的几年时间里出现大量的研究成果，形成了一个研究热点。 1 2 国内外研究现状 粒子群优化( 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 ) 算法一经提出就吸引 了各国学者的注意，各种关于p s o 算法的理论与应用研究的成果不断涌现， 有力地推动了p s o 算法的研究。研究主要从下面两个方向开展：一个是从具 体优化的应用着手，根据具体情况，对算法进行改进，以满足应用要求；另外 一个是粒子群算法的理论方面着手，分析算法的收敛性能，提高算法的优化性 能。在算法的理论方面，研究发现粒子群算法存在早熟收敛现象和后期振荡现 象，很多学者致力于提高p s o 算法的性能，提出了各种改进的算法。 1 2 1 粒子群算法在国际上的发展 首先，为了加快收敛速度，提高算法的性能，对p s o 参数进行研究。对 于p s o 参数的研究，主要针对惯性因子彩，学习因子c ，和c ，其中对p s o 参 数取值的改进技术中研究最多的是关于惯性因子彩的取值问题。彩表明粒子原 先的速度能在多大程度上得到保留，体现了局部搜索能力和全局搜索能力的比 例关系。其类似于模拟退火中的温度，较大的彩可以增强p s o 的全局搜索能力， 而较小的国能加强p s o 算法的局部搜索能力【22 1 。因此，随着迭代次数的增加， 惯性因子倒应不断减小。目前对函的取值大致有三种取法：固定惯性因子取值 西南交通大学硕士研究生学位论文第3 页 法【2 3 , 2 4 】、线性自适应惯性因子取值法【2 5 , 2 6 】、非线性惯性因子取值法【2 7 。3 0 。原 始的p s o 算法可认为是惯性因子国为1 ；后来，s h i 等【2 5 , 2 6 】提出按照线性递减 规律改变惯性因子翻。 其次，基于拓扑结构的研究。p s o 算法有全局版本和局部版本，这两个版 本的差别在于粒子的领域不同，即与各粒子直接连接的粒子数不同。局部p s o 的粒子，邻域仅为其两边有限的几个粒子，而全局p s o 的邻域则为该群体所 有粒子。如此看来，全局p s o 可看成是局部p s o 的特殊情况。研究发现，全 局p s o 收敛较快，但易陷入局部最优，而局部p s o 可搜索到更优的解，但速 度稍慢。此外，为提高p s o 的性能，研究者又设计了许多不同的邻域结构。 s u g a n t h a n 在p s o 算法中引入了空间邻域的概念”1 1 ，将处于同一个空间邻域的 粒子构成一个子粒子群分别进行进化，并随着进化动态地改变选择阀值以保证 群体的多样性；k e n n e d y 3 2j 引入邻域拓扑的概念来调整邻域的动态选择，同时 引入社会信念将空间邻域与邻域拓扑中的环拓扑相结合以增加邻域间的信息 交流，提高群体多样性。 再次，p s o 算法由于其简单和解决问题的有效能力而被应用到很多的领 域。但在实际应用当中，也表现出了一些不尽人意的问题。这些问题中最主要 的是它容易产生早熟收敛、局部寻优能力较差等。实际上这些缺点也是几乎所 有随机算法的弊病。梯度法、爬山法、直接搜索法、模拟退火法等一些优化算 法却具有很强的局部搜索能力，而另一些含有问题域相关知识的启发式算法的 运行效率也比较高。可以说，大多数优化算法的全局搜索能力和局部搜索能力 单靠一种算法往往无法得到有效利用与平衡，从而影响了算法的求解精度和效 率。因此，如何合理结合不同算法的优点来构造新算法，对于实时性和优化性 同样重要的工程领域，具有很强的吸引力。自然地，人们想到了混合两种算法 或者多种算法在一个模型当中，尽量发挥各个算法的优点，从而形成了一个研 究混合算法的方向。因此，在p s o 算法搜索过程中融合其它优化算法的思想， 构成混合p s o 算法成为p s o 算法改进的最常见的思路。 总之，p s o 算法的优越性能吸引了许多学者的关注，并对其进行了大量的 研究工作，被广泛地应用于各个领域。但是由于p s o 算法提出的时间不长， 还存在许多有待改进和发展的地方。 1 2 2 粒子群算法在国内的发展 在我国，在粒子群优化算法的研究则是刚刚起步，深入的研究和应用还很 少，已经发表的论文也不是很多。p s o 算法的研究还有大量的研究工作要做， 主要的研究方向有下面几个方面： 西南交通大学硕士研究生学位论文第4 页 ( 1 ) 粒子群算法的改进 标准粒子群算法主要适用于连续空间函数的优化问题，如何将粒子群算法 应用于离散空间优化问题，特别是一类非数值优化问题，将是粒子群算法的主 要研究方向。另外，充分吸引其他进化类算法的优势，以改进p s o 算法存在 的不足也是值得研究的问题。 ( 2 ) 粒子群算法的理论分析 到目前为止，p s o 算法的分析方法还很不成熟，存在许多不完善之处。如 何利用有效的数学工具对p s o 算法的运行行为、收敛性以及计算复杂性进行 分析也是目前的研究热点之一。 ( 3 ) 粒子群算法与其他进化算法的比较研究 目前，进化算法的研究在理论和应用两方面都得到迅速发展，效果显著。 其中研究的比较成熟的有遗传算法、蚁群算法等，而粒子群算法是一个新兴的 群体智能算法，目前已成为进化算法的一个重要分支，如何从多方面比较各种 算法从而得到各自的特长和不足，如何吸引其他进化类算法的优势来弥补p s o 算法的不足也是当前研究的热点之一。 ( 4 ) 粒子群算法的应用 算法研究的目的是应用，如何将p s o 算法应用于更多领域，同时研究应 用中存在的问题也是值得关注的热点。 1 3 本文的研究内容 本文在研究了标准的粒子群( 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 v a 的多线程的编程机制， 从而在一定的程度上，改善了算法在时间上的效率。 第三，在提出的核心主子群的粒子群算法的基础上，对粒子群的速度更新 公式进行了改进，加入了局部最佳粒子的参考学习机制，使得粒子的参考学习 因子由原来的2 个增加到现在的3 个。 第四，将核心主子群的粒子群算法与公式改进的粒子群算法相融合，通过 实验验证，取得了很好的实验效果。 最后，将本文中提出的两个改进算法应用到求解非线性方程中，验证了算 西南交通大学硕士研究生学位论文第5 页 法的有效性。 1 4 本文的组织结构 第一章，前言，介绍了粒子群优化算法的研究背景与意义，国内外研究现 状，以及作者的研究内容、本文组织。 第二章，对标准的粒子群优化算法进行概述，首先对粒子群算法的产生背 景进行概述。然后对粒子群算法的基本原理和算法进行描述，并对算法的参数 进行了详细的分析。最后，对算法的流程进行总结并给出了算法的流程图。 第三章，基于第二章对标准的粒子群算法的研究和分析，提出了核心主子 群的智能优化算法。找出了粒子群算法存在的缺陷，提出了核心主子群的粒子 群优化算法，我们将s h i 和e b e r h a r t 对惯性权值的研究进行了融合，从而使得 改进的算法能够进行动态的区域搜索，利用惯性权值国的线性递减的特性，使 得搜索区域先增大后减小，使得最后主子群得到的最佳适应值更精确。最后， 在并行计算的启发下，利用面向对象的j a v a 编程语言提高算法时间效率。并 将改进的核心主子群的粒子群优化算法和标准的粒子群算法利用标准函数在 同等的条件下进行实验测试，结果证明改进的粒子群算法得到了更好的精度效 果。 第四章，在第三章改进的基础上，提出了一种多学习因子的粒子群算法与 核心主子群算法相结合的改进算法。将第三章中各个子群的最佳粒子的适应值 引入到了改进的公式中。并对多学习因子的粒子群算法收敛性进行分析。最后 利用4 个标准的测试函数将多学习因子的核心主子群结合的改进算法、核心主 子群粒子群优化算法和标准的粒子群算法进行试验对比。结果证明，多学习因 子的核心主子群结合的算法精确度又有了进一步的提高。 第五章，将本文研究的标准粒子群算法、核心主子群的粒子群优化算法和 多学习因子的核心主子群结合的算法应用到非线性方程组的求解中。不仅仅基 于上述所提到的三种算法，还参考以前改进算法的结果，实验表明改进的算法 还是得到了非常好的结果。 总结与展望，先对本文的工作进行总结，然后对将来进一步的研究工作进 行展望。 最后是参考文献、致谢及攻读硕士学位期间发表的论文。 西南交通大学硕士研究生学位论文第6 页 第2 章标准粒子群算法研究综述 2 1 标准粒子群算法介绍 粒子群算法( p s o ) 是由k e n n e d y 和e b e r h a r t 于1 9 9 5 年提出的一种仿生类算 法。该方法通过记忆与反馈机制实现了高效的寻优搜索。其基本思想是模拟飞 鸟的捕食过程，每个粒子在解空间中移动，各个粒子记录下自己曾搜索到的最 优点并记录下所有粒子所搜索到的全局最优点，粒子根据自身最优点及全局最 优点来更新自己的速度和位置。粒子群优化算法就是通过不断地对极值点的更 新而实现的智能算法。 2 1 1 粒子群算法的起源 自然界中各种生物体均具有一定的群体行为，而人工生命的主要研究领域 之一就是探索自然界生物的群体行为从而在计算机上构建其群体模型。虽然每 一个个体具有非常简单的行为规则，但群体的行为却非常复杂。鸟类的群集 ( f l o c k i n g ) 行为，如大雁飞行自动排成人字形、鸽子在飞行中几乎同时转弯、 蝙蝠在洞穴中快速飞行却互不相碰等引起了广大研究者的普遍关注，这种复杂 的行为很难仅仅用存在领导者的观点来解释，若假设每只鸟飞行中都遵循一定 的行为准则，当它们一起飞行交互时，就会表现出上述的智能行为。r e y n o l d s 基于上述思想，提出了b o i d ( b i r d o i d ) 模型用以模拟鸟类聚集飞行的行为【”】 。在这个模型中，每只人工鸟被称为一个b o i d ，每个b o i d 可感知周围一定范 围内其他b o i d 的飞行信息，此信息作为b o i d 决策机构的输入，结合其当前自 身的飞行状态( 空间位置，飞行方向矢量，飞行速度) ，做出下一步的飞行决策。 由b o i d 组成的系统惊人的表现出了集体的群集现象。在这个系统中，系 统运行完全依赖于自下而上的力量。系统的构成个体完全按照自身的规律运 动，但却使整个系统表现出了整体的秩序特征。随后在r e y n o l d s 的b o i d 模型 基础上，h e p p n e r 和g r e n a n d e r 进一步提出了鸟类群聚模拟【34 1 ，加入了鸟群受 到栖息地的吸引的特点。也就是说，在模拟的开始，鸟群逐渐形成群体并且以 无特定方向在空中飞行，直到有一只鸟飞越了栖息地，并且受到了栖息地的牵 引，那么其它的同伴将同时受到邻近伙伴与栖息地的影响，逐渐地降落在栖息 地。 受上述鸟群运动模型的影响，社会心理学博士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 23 1 。粒子群算法是一种演 西南交通大学硕士研究生学位论文第7 页 化计算技术，该算法中将鸟群运动模型中的栖息地类比于所求问题解空间中可 能解的位置，通过个体的信息传递，导引整个群体向可能解的方向移动，在求 解过程中逐步增加发现较好的解的可能性。群体中的鸟被抽象为没有质量和体 积的“微粒”，通过这些“微粒 间的相互协作和信息共享，使其运动速度受 到自身和群体的历史运动状态信息的影响，以自身和群体的历史最优位置来对 微粒当前的运动方向和运动速度加以影响，较好的协调微粒本身群体运动之间 的关系，以利于群体在复杂的解空间中进行寻优操作。 2 2 粒子群算法的原理 2 2 1 原始的粒子群优化算法 首先我们对粒子群算法中的一些基本概念作如下的介绍： 概念l ：粒子 类似于遗传算法中的染色体，p s o 中粒子为基本的组成单位，代表解空间 的一个候选解。 概念2 ：种群 粒子种群由m 个粒子组成，代表m 个候选解。 概念3 ：粒子速度 粒子速度表示粒子在单位迭代次数位置的变化即为代表解变量的粒子在n 维空间的位移。 概念4 ：适应度函数 一般由适应度函数由优化目标决定，用于评价粒子的搜索性能，指导粒子 种群的搜索过程。算法迭代停止时适应度函数最优的解变量即为优化搜索的最 优解。 概念5 ：个体极值 个体极值是单个粒子从搜索初始到当前迭代对应的适应度最优的解。 概念6 ：全局极值 全局极值是整个粒子种群从搜索开始到当前迭代对应的适应度最优的解。 在一个1 1 维搜索空间s r ”和由m 个粒子组成的种群中，第i 个粒子的位 置是用一个1 3 维向量表示的，即x i = ( x i 。，置：，以) 每个粒子的位置都代表所求 问题的一个候选解。这些解的好坏由适应度函数值决定，适应度函数值越好则 与之相关联的解就越好。适应度函数与目标函数有关系，一般要根据具体问题 设定。粒子的跳跃速度也是一个1 1 维向量，即_ = ( ，l ：，吃) 。第i 个粒子跳 跃过程中所遇到的最好位置是s 空间的一个点，可以表示为只= ( 晶，鼻：，岛) 。 西南交通大学硕士研究生学位论文第8 页 用只表示粒子群在前面跳跃过程中获得的种群最好位置的粒子， 名= ( 名。，忍：，) 表示种群最好粒子的位置，t 表示此时的循环次数。 根据k e n n e d y 博士和e b e r h a r t 博士最初提出的p s o 算法，粒子群中每个 粒子跳跃的速度和下一次的位置分别由公式( 2 1 ) 和( 2 2 ) 决定： v i ( f + 1 ) = v f ( f ) + c l 一( p f ( f ) 一一( r ) ) + c 2 r 2 ( p 。( t ) 一x f o ) ) ( 2 - 1 ) x f o + 1 ) = 一o ) + v f ( f + 1 ) ( 2 2 ) 其中i = 1 ，2 ，3 ，m ，加速常数c 1 ，c ，是p s o 算法中重要的参数，g 表 示微粒自身经验的认知能力，调节微粒飞向自身最好位置方向的前进步长，g 表示微粒社会经验的认知能力，调节微粒向全局最好位置前进的步长。n ，乃是 均匀分布在区间 0 ，1 】的随机数，主要是为了让粒子能够以等概率的加速度飞向 粒子本身最好位置和粒子全局最好的位置。t = l ，2 ，表示循环次数。 通常称式( 2 1 ) 和( 2 2 ) 为原始的粒子群优化算法公式。 2 2 2 标准的粒子群优化算法 在上述原始的粒子群优化算法中，式( 2 一1 ) 由三部分组成：第一部分为粒子 的上一次速度，而后两项分别为自身认知项和群体认知项。s h i 和e b e r h a r t 发 现如果没有后面的两项，粒子将保持初始速度不变飞向下一个位置，永远不会 停止，直到飞到边界上，这样的粒子就不可能停在最优位置上。如果没有第一 项，那么粒子的速度仅仅取决于粒子的自身认知项和群体认知项，粒子上一次 的速度也就没有了记忆性。假设在开始的时候，某个粒子刚好在整个粒子群最 好的位置上，那么这个粒子将保持这次的位置不变，直到出现新的一个最好的 位置来代替这个位置。同时，每个粒子将向自身最好的位置和群体最好的位置 方向飞去，一直到出现新的种群最好位置。因此，如果没有第一项，粒子很容 易陷入局部最优而产生早熟现象。这样的话，算法的性能在很大的程度上要依 靠初始化的值了。从某种意义上说，记忆项体现了粒子群算法的全局搜索能力。 所以在粒子群算法中如何体现和平衡局部搜索能力和全局搜索能力是非 常重要的。因此，s h i 和e b e r h a r t l 35 j 提出了具有惯性权重的标准粒子群算法。 他们引入了一个惯性权重o j 在记忆项，来起到权衡全局搜索能力和局部搜索能 力的作用。这时粒子的跳跃速度和下一次的位置分别由公式( 2 3 ) 和( 2 4 ) 决定： 1 ，f ( f + 1 ) = 铆f o ) + c 1 9 ( p f ( f ) 一x f ( f ) ) + c 2 r 2 ( p 譬( f ) 一x f 0 ) ) ( 2 3 ) x i o + 1 ) = x i ( t ) + v f i j f - 4 - 1 ) ( 2 4 ) 式( 2 3 ) 和( 2 4 ) 称为标准的粒子群算法公式。其中i = l ，2 ，3 ，m ，参 数国称为惯性权重，其余的参数与原始的粒子群算法表示的意义相同。 t = 1 2 ，表示粒子当前的迭代次数。 西南交通大学硕士研究生学位论文第9 页 2 2 3 标准粒子群算法的参数分析 若粒子的速度加速增加，粒子将跳出搜索区域；若粒子的速度迅速下降， 粒子几乎静止，粒子不能逃离局部极小点。以上三方面都有可能造成搜索失败。 为了避免上述不希望出现的状况，对粒子行为和参数的关系应作重点分析。 p s o 参数包括：群体规模m ，惯性权重0 9 ，加速常数c l ，c ，最大速度， 最大迭代次数t 。 ( 1 ) 最大速度， 微粒最大速率决定微粒在每一次循环中最大的移动距离。如果太 大，粒子可能会飞过最好解，甚至飞出求解范围；如果吒，太小，粒子不能跳 出局部，在局部区域之内进行足够的探索，导致陷入局部最小点。 ( 2 ) 惯性权重因子翻 惯性权重彩，控制着前一速度对当前速度的影响。彩可以对算法的全局搜 索能力和局部搜索能力进行平衡调整，因此，该参数对算法性能影响很大。仞 值越大，全局寻优能力越强，局部寻优能力越弱；否则，则局部寻优能力增强， 而全局寻优能力减弱。通常将迭代开始时的惯性权重0 9 设置较大，并在迭代过 程中逐渐减小。这样可以使微粒群优化算法更好地控制探索( e x p l o r a t i o n ) 与开 发( e x p l o i t a t i o n ) 之间的关系。 ( 3 ) 学习因子c 1 ，c ， 学习因子c l ，c ，( 也称为加速常数) 是调整微粒自身经验与社会( 群体) 经验 在其运动中所起作用的权重。较小的学习因子数值，可使微粒在远离目标区域 内振荡；而较大的学习因子数值可以使微粒迅速向目标区域移动，甚至又离开 目标区域。通常学习因子的取值为c ，= c ，= 2 。 在式( 2 3 ) 中，如果没有后面的两部分，即c 1 = c ，= o ，粒子将一直以当前的 速度飞行，直到到达边界。由于它只能搜索有限的区域，所以很难找到好解。 如果没有第一部分，即倒= o ，则速度只取决于粒子当前最好位置尸和种群 最好位置只，速度本身没有记忆性。假设在开始的时候，某粒子正好是整个粒 子群最好解的位置，那么该粒子的速度为0 ，这将保持粒子此次的位置不变，直 到出现新的一个最好点来代替。同时，每一个粒子将向自身最好点和整体最好 点的质心方向“飞翔 。因此可以想象，在没有第一项的情况下，p s o 的搜索 空间将在迭代中逐渐的衰弱。只有当全局最好点包含在初始搜索空间内的时 候，才有可能找到满意解。从另一个层面上来说，第一项内容使得粒子有一种 扩展搜索空间的能力，即开拓能力，是一种全局搜索能力的表现。 如果没有第二部分，即g = 0 ，则粒子没有认知能力，也就是“只有社会 的模型。在粒子的相互作用下，有能力到达新的搜索空间。它的收敛速度比标 西南交通大学硕士研究生学位论文第1 0 页 准p s o 算法更快，但对复杂问题，则比标准p s o 算法更容易陷入局部最优值 点。 如果没有第三部分，即c ，= 0 ，则粒子之间没有社会信息共享，也就是“只 有认知”的模型。因为个体间没有交互，一个规模为m 的群体等价于运行了r n 个单个粒子的运行，因而得到最优解的几率非常小。 2 2 4 标准粒子群算法的流程及流程图 标准粒子群算法的工作流程如下： ( 1 ) 初始化，设置加速常数c 1 和c ：，最大进化代数k ，将当前进化代数设 置为t = l ，在定义的空间s ”中随机产生m 个粒子x 1 ，x ：，x 。，组成初始种群x ( f ) ； 随机产生各粒子初始速度v ；，1 ，；，v ? ，组成速度位移矩阵v ( f ) 。 ( 2 ) 个体评价( 适应度评价) 。计算群体中各个个体的适应度。粒子群算法在 搜索进化过程中一般不需要其他外部信息，仅用评估函数值来评价个体或解的 优劣，并作为以后粒子群操作的依据。评估函数值又称为适应度值( f i t n e s s v a l u e ) 。 ( 3 ) 对每个粒子，将当前适应度值与其经历过的最好适应度值做比较，若 好于后者，则以当前的适应度值作为只，即以当前位置作为粒子所经历过的最 好位置，否则，尸不变。 ( 4 ) 把这一循环中得到的种群最好位置的适应度值与只比较，若好于后者， 则重新记录只的大小，否则只不变。 ( 5 ) 利用方程( 2 3 ) 和( 2 4 ) 分别重新计算每个粒子的速度和位置。 ( 6 ) 如满足终止条件( 通常为产生足够好的适应度值或达到一个预设最大代 数k ) 程序终止，否则转( 2 ) 。 标准粒子群算法的流程如图2 1 ： 西南交通大学硕士研究生学位论文第1 1 页 图2 1 ：标准粒子群算法的流程图 西南交通大学硕士研究生学位论文第1 2 页 第3 章核心主子群粒子群优化算法的研究 3 1 粒子群算法的缺陷综述 粒子群优化算法是种基于群体智能方法的演化计算技术。它以独特的搜 索机理，出色的收敛性能、简便的操作，在工程优化领域得到了广泛的应用。 但是在应用粒子群算法的优化过程当中，发现了粒子群算法也有很多缺陷，这 些缺陷也是随机搜索算法比较普遍的不足之处。 3 1 1 粒子群算法容易陷入局部最优解 基本p s o 算法依靠的是群体之间的合作和竞争，粒子本身没有变异机制， 因而单个粒子一旦受某个局部极值约束后本身很难跳出局部极值的约束，此时 需要借助其它粒子的成功发现。比如：粒子群优化算法容易陷入局部极小点， 导致优化结果得不到全局最优解。事实上，p s o 算法的寻优能力主要来自于粒 子之间的相互作用和相互影响。如果从算法中去除粒子之间的相互作用和相互 影响，则p s o 算法的寻优能力就变得非常有限。造成这种现象的原因有两个： 首先是待优化函数的性质，有许多测试函数是多峰函数、形状复杂，而粒子群 优化算法并不是从理论上严格证明收敛于任何类型函数的全局极值点，因此对 于复杂的测试函数，很可能难以得到满意的结果；其次是粒子群优化算法在运 行时，由于算法的参数设计或者粒子数选择不当等原因，使得在计算的过程中， 粒子的多样性迅速的消失，造成算法“早熟现象，从而导致算法不能收敛到 全局极值点。这两个因素总是紧密的纠缠在起，在算法的寻优过程中都起到 了关键的影响，在一个具体的问题中，很难确定到底是哪一个因素使得算法不 能收敛到全局极值点。 3 2 核心主子群粒子群算法的研究 3 2 1 基于岛屿模型的核心主子群粒子群算法 岛屿模型是一种重要的用于描述现实群体的经典模型，它可能是模拟自然 遗传分化群体的最简单的方式，但在产生其它群体遗传结构模型中起重要的作 用。该模型的理论结果仍广泛用于实际工作中。岛屿模型原始思想是由w r i g h t 在他的一篇具有历史意义的论文“e v o l u t i o ni nm e n d e l i a np o l u l a t i o n ”( 19 31 ) 提 出的，以后得到进一步发展1 3 引。 西南交通大学硕士研究生学位论文第13 页 岛屿模型将整个群体划分为几个子群体，各个子群体分布在各自的处理机 上进行子群体演化计算，各个处理机在适当时刻进行信息交换。在岛屿模型中， 将整个的粒子群划分为多个子群体，每个子群体在各自的种群内进行全局p s o 搜索，并产生群内的最佳粒子。每个子群体都作为个独立的子进程来进行。 并将各个子进程所得到的子群内的最佳粒子周期性的上报给主进程，形成一个 主子群。由形成的主子群选出全局的最佳的粒子广播给各个子进程，从而使各 个子进程参考全局最佳粒子进行演化。 在遵循粒子群算法建模的基础上，通过对岛屿模型的