（计算机应用技术专业论文）微粒群优化算法的改进研究与应用.pdf

西南交通大学硕士研究生学位论文第l 页 摘要 2 0 世纪以来，群体智能的诞生使优化领域得到了很大的发展，学者在研 究生物群体行为时候得到了启示，提出了许多基于群体智能的算法，微粒群优 化算法就是其中的一种。它是一种基于群体搜索策略的自适应随机算法，由于 算法简单、参数较少、实现简单的特点，因此该算法被提出后得到了国内外许 多学者的关注，逐渐成为一个新的研究热点。已经广泛应用于神经网络、函数 优化、参数优化、数据挖掘、图像处理、信号处理、模式识别等领域并取得了 良好的效果，有着广阔的应用前景。 本文的主要工作总结归纳为以下几方面： 。首先，对微粒群优化算法的理论基础和研究现状作了简要的介绍，分析了 粒子群优化算法的原理、算法流程以及算法的特点，对算法参数的选择做了详 细的研究，并进行了相应的仿真实验。 其次，针对标准微粒群算法收敛速度较慢、收敛精度低、易陷入局部最优 的问题，将方差聚集的思想、平均极值、停滞变异策略等引入了微粒群优化算 法，用方差聚集思想改进现有的参数，根据粒子的自适应度值进行排序。通过 控制惯性权重因子大小，使同一代中的粒子具有不同的惯性权重因子值，因此 每个粒子具有不同的更新公式，将平均极值引入和变异策略引入是为了增加了 粒子的多样性，增强微粒群优化算法计算后期的全局寻优能力。通过仿真实验， 验证了优化后的算法具有良好的全局寻优能力和收敛速度。 再次，将改进后的微粒群优化算法应用到矢量量化码书设计当中。在分析 了码书设计中经典算法l b g 的性能之后，通过仿真实验说明了l b g 算法的缺 点，包括对初始码书敏感和容易陷入局部最优。因此将本文的改进算法引入， 利用微粒群优化算法的全局寻优能力来改进l b g 算法的缺点。本文研究了基 于码书和基于划分的两种微粒群码书设计方式。通过仿真实验，用改进算法优 化的l b g 算法计算的码书，不仅性能得到了提高，算法的稳定性也增强了。 降低了算法对初始码书的依赖程度。 关键词微粒群算法；平均极值；种群方差；矢量量化；码书； 西南交通大学硕士研究生学位论文第1i 页 a b s tr a c t s i n c et h e2 0 t hc e n t u r y , t h eo p t i m i z a t i o nd o m a i nh a sd e v e l o p e dq u i c k l yd u et o t h eb i r t ho fs w a r mi n t e l l i g e n c e s o m es c i e n t i s t so b t a i n e dt h ee n l i g h t e n m e n ti nt h e r e s e a r c ho ft h eb i o l o g ys w a r mb e h a v i o r , a n dp r o p o s e dm a n ya l g o r i t h m si n c l u d 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 ( p s o ) a l g o r i t h mw h i c hb a s e do nt h es w a r m i n t e l l i g e n c e p s oi sap o p u l a t i o n - b a s e d ，s e l f - a d a p t i v es e a r c ho p t i m i z a t i o nt e c h n i q u e t h em a i nt r a i to fp s oi ss i m p l ei np r i n c i p l e ，f e wi nt u n i n gp a r a m e t e r s ，s p e e d yi n c o n v e r g e n c ea n de a s y i n i m p l e m e n t a t i o n s ot h ep s oa l g o r i t h mi m m e d i a t e l y a t t r a c t st h es c h o l a r s c l o s ea t t e n t i o ns i n c ei ti sb i r t h g r a d u a l l y , i tb e c o m e sa h o t s p o ti nt h ee v o l u t i o n a r yc o m p u t a t i o nf i e l d n o wt h ep s o i su s e df o rt h et r a i n i n g o fn e u r a ln e t w o r k s f u n c t i o n so p t i m i z a t i o n ，t h ep a r a m e t e ro p t i m i z a t i o n ，d a t a m i n i n g ，i m a g ep r o c e s s i n g ，s i g n a lp r o c e s s i n g ，p a t t e r nr e c o g n i t i o na n d s oo n s o m e p a r t i c e sa r ed o n ea n dr e s u l t ss h o w t h a ti th a sg o o dp e r f o r m a n c e ，s oi t sw i d e l yu s e d n em a i nw o r k so f t h ep a p e rc a nb es u m m a r i z e da sf o l l o w s ： f i r s t ，r n l i sp a p e rm a k e sab r i e fi n t r o d u c t i o no ft h eb a s i c 血e o r i e sa n dp r e s e n t d e v e l o p m e n to fp s o n ep s 0 sf l o wa n dc h a r a c t e r i s t i c sa r ei n t r o d u c e di nd e t a i l ， a n dt h ep a r a m e t e r so fp s oa r ea n a l y z e d ，a l s os o m es i m u l a t i o n sa r eg i v e ni nt h i s p a p e r s e c o n d ，t h ep r o b l e m so ft h es t a n d a r dp s 0a r es l o wc o n v e r g e n c e ，1 0 wa c c u r a c y a n de a s yt of a l li n t ol o c a lo p t i m u m t h ei d e ao fg a t h e r i n gt h ev a r i a n c e ，t h ea v e r a g e m a x i m u ma n dm u t a t i o ns t r a t e g ya r ej o i n e di np s o u s i n gt h ev a r i a n c et oi m p r o v e t h ee x i s t i n gp a r a m e t e r s ，s o r t i n gp a r t i c l e sa c c o r d i n gt ot h ep a r t i c l e s f i t n e s sv a l u e ， t h ep a r t i c l e so ft h es a m eg e n e r a t i o ns h o u l dh a v ed i f f e r e n tv a l u e so fi n e r t i aw e i g h t f a c t o r , a n dt h e yh a v ed i f f e r e n tu p d a t ef o r m u l a a v e r a g em a x i m u ma n dm u t a t i o n s t r a t e g y i st oi n c r e a s et h ed i v e r s i t yo fp a r t i c l e s ，t oe n h a n c et h ep s oc a p a c i t y o p t i m i z a t i o n 乃es i m u l a t i o ns h o w st h a to p t i m i z e da l g o r i t h mh a sg o o dg l o b a l o p t i m i z a t i o na b i l i t ya n dc o n v e r g e n c es p e e d t h i r d ，t h ei 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 na l g o r i t h mi sa p p l i e dt ot h e v e c t o rq u a n t i z a t i o nt e c h n i q u ei nt h i sp a p e r 1 1 1 ep e r f o r m a n c eo ft h el b ga l g o r i t h m w h i c hi sac l a s s i c a la l g o r i t h mi nv e c t o rq u a n t i z a t i o ni sa n a l y z e d ，t h es i m u l a t i o n i l l u s t r a t e st h a tl b g a l g o r i t h mh e a v i l yd e p e n d so nt h ei n i t i a lc o d eb o o k ，a n de a s yt o 西南交通大学硕士研究生学位论文 第1 li 页 l _ _ l 。一一_ 一 f a l li n t ol o c a lo p t i m u m p s o sg l o b a lo p t i m i z a t i o no fc a p a c i t yi su s e dt oi m p r o v e t h el b gf l g o f i t h m i nt h i sp a p e r ，t w ot y p e so fp a r t i c l es w a r mc o d e b o o kd e s i g n t h a t a r eb a s e do i lt h ec o d eb o o k sa n dd i v i d e da r es t u d i e d 1 1 1 ei m p r o v e da l g o r i t h m s s i m u l a t i o nr e s u l t ss h o wt h a tt h ei m p r o v e m e n tl b ga l g o r i t h mo p t i m i z a t i o nh a s b e r e rp e r f o r m a n c 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 ；t h ea v e r a g em a x i m u m o fs w a l t l l ； v a r i a n c eo fs w a r m ；v e c t o rq u a n t i z a t i o n ；c o d e b o o k 西南交通大学 学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规定，同意学校 保留并向国家有关部门或机构送交论文的复印件和电子版，允许论文被查阅和 借阅。本人授权西南交通大学可以将本论文的全部或部分内容编入有关数据库 进行检索，可以采用影印、缩印或扫描等复印手段保存和汇编本学位论文。 本学位论文属于 1 保密口，在年解密后适用本授权书； 2 不保密彩使用本授权书。 ( 请在以上方框内打“4 ) 学位论文作者签名：办l 坎 指导老师签名 日期：彳。哆 日期 夕 一 醅n 西南交通大学学位论文创新性声明 本人郑重声明：所呈交的学位论文，是在导师指导下独立进行研究工作所 取得的成果。除文中已经注明引用的内容外，本论文不包含任何其他个人或集 体已经发表或撰写过的研究成果。对本文的研究做出贡献的个人和集体，均已 在文中作了明确的说明。本人完全意识到本声明的法律结果由本人承担。 本学位论文的主要创新点如下： 论文在研究微粒群优化算法参数对粒子轨迹影响的基础上，将方差聚集， 惯性系数控制因子，群体平均值和保持活性策略等思想引入微粒群算法。通过 仿真实验验证了优化后的算法具有更好的全局寻优能力。结合矢量量化中l b g 算法的缺点，把改进后的算法引入l b g ，两者相混合形成一个混合算法，通 过两种不同的粒子编码方式，将其应用于图像压缩编码中的码本设计，通过仿 真实验验证，混合后的算法具有一定的有效性和实用性。 参双 3 z 9p 西南交通大学硕士研究生学位论文第1 页 第1 章绪论 1 1 本文的研究背景和意义 优化技术是一种以数学为基础，用于解决各种工程优化问题的应用技术。 随着计算机技术的发展和日益的普及，使优化问题的研究成为一种迫切的需 要。因此优化理论和算法迅速的发展起来，形成了一个重要的学科分支，一直 受到人们的广泛关注。至今已经出现在线性规划、整数规划、非线性规划、几 何规划、动态规划、模式识别、神经网络、数据挖掘、资源调度等许多应用当 中。优化算法的研究自从上世纪八十年代开始得到了发展，特别是一些新颖的 有别于传统的优化算法的到了迅速的发展，人工神经网络( a n n ) 用于模拟人脑 的组织结构；遗传算法( g a ) 借鉴了自然界优胜劣汰的进化思想；模拟退火 ( s a ) 思路来源于物理学中固体的退火过程。蚁群算法( a c o ) 的思想来自于蚂 蚁的运动行为。这些算法的共同特点就是都是通过模拟或是揭示某些自然界的 现象和过程而得到启示和发展。这些通常被称做为智能优化算法( i n t e l l i g e n t o p t i m i z a t i o na l g o r i t h m s ) 【2 】。 微粒群算法的理论背景是基于“人工生命”，其中有一个重要的部分利用 生物技术来研究计算问题，粒子群优化算法的诞生来源于一种生物一社会系 统，该生物一社会系统的研究集中于简单个体组成的群落与环境之间的关系， 以及个体之间的互动行为【，4 】。群居个体以集体的力量进行觅食、御敌，单个个 体只能完成简单的任务，而由单个个体组成的群体却能完成复杂的任务，这种 群体所表现出来的“智能”，称为群体智能( s w a r mi n t e l l i g e n c e ，s i ) t , l 。目前比较 流行的群体智能算法有三种：蚁群算法、微粒群优化算法、人工鱼群算法。群 体智能的主要特点有以下几个：( 1 ) 合作性，合作性不但有行为上的支持还有 信息的交换与共享。( 2 ) 分布性，每个个体是呈分散状态的，没有对群体中的 个体行为进行集中控制。这样虽然个体的信息是部分的，但通过个体间的信息 交流，整个群体的信息却是完整的，因此群体行为往往可以达到全局最优。这 个特点与计算机网络的工作环境非常类似。( 3 ) 鲁棒性，因为群体中个体具有 分布性，没有集中的控制，所以，不会因为其中的一个或者几个个体的原因而 西南交通大学硕士研究生学位论文第2 页 影响整个全局的问题，这样的系统更具有鲁棒性( r o b u s t ) 更加稳定。( 4 ) 自适 应性和快速性，群体中每个个体的行为能力都很简单，区区的几条规则就可以 描述，但这些行为对环境变化都有自适应性和快速性，能根据环境的变化做出 快速的反应。以上四个特点为寻找问题的最优解提供了快速可靠的基础，为系 统的复杂性研究以及n p 问题提供了新的方法。 微粒群优化算法( 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 ) ，又被称作粒子群优化 算法，是群体智能算法的一种；它源于鸟群捕食行为的研究【q 。一群鸟在飞行 过程中搜寻食物，如果在活动区域中只有一块食物，则搜寻目前食物最近的鸟 的周围区域就是找到食物的简单而有效的策略。每只鸟所做的都是追踪它的有 限邻居，而最终得到的整个结果是整个鸟群都好像在一个中心的控制下完成相 对复杂的觅食活动。微粒群算法就是从这种模型中得到启示，并用来解决优化 问题。由于该算法的收敛速度快，需要设置的参数少，且容易实现，能有效的 解决复杂优化问题，因此在函数优化、模式识别、神经网络、信号处理、决策 和模拟、多目标问题的优化、数据分类、系统设计等很多领域都得到了广泛的 应用。粒子群算法已经显示出它强大的生命力和进一步发展的潜力，并越来越 受到研究者们的关注。不过，对微粒群算法的应用研究虽然已进行了较长一段 时间，但存在着很大的拓展空间，可以从很多方面对其进行改进。所以对微粒 去优化算法的研究还是有一定得现实意义。 量化是数据压缩中常用的一种技术，它分为标量量化和矢量量化【7 】。矢量 量化是利用相邻采样之间的相关性，在量化时用输出集合中最匹配的一组输出 值来代替一组输入采样值。由于矢量量化能有效的利用矢量中各个分量之间的 线性依赖性、非线性依赖性、概率密度和矢量的维数，所以能够最大限度地除 去数据之间的冗余度，有效的压缩数据。矢量量化( v e c t o rq u a n t i z a t i o n ，v q ) 是语音识别、语音编码和图像压缩的关键技术。它具有压缩比大、编码速度快 等优点，其重要性在实际的应用逐渐显示出来。所以展开对矢量量化技术的研 究，有一定的现实意义。 码书设计是矢量量化中的首要问题，是一个非常困难的组合优化问题，已 经证明是一个完全n p 问题【7 】。l b g 是一种经典的矢量量化技术，通过参考文 献，针对l b g 算法的缺陷，将改进粒子群优化算法引入其中，形成粒子群改 进的l b g 算法，通过在图像压缩方面的仿真实验，给出了优化后算法的效果 西南交通大学硕士研究生学位论文第3 页 与性能分析，得出结果可以看出，优化后的算法具有更好的效果。所以，本课 题具有一定的实际价值。 1 2 微粒群优化算法国内外的研究现状与发展 微粒群优化算法最早由心理学研究者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 年共同提出的，是一种群体智能优化算法i s 。他 同遗传算法类似，也是通过个体间协作和竞争实现全局搜索。粒子群优化算法 初始化为一群随机的粒子，通过迭代计算在搜索空间内完成寻优，它没有遗传 算法的选择、交叉以及变异算子，而是粒子在解空间追随最优的粒子进行搜索。 由于微粒群算法本身具有的概念简单性和易于实现性，在短期内得到很大发 展，迅速引起了国际上相关领域众多学者的广泛关注和研究，并在很多领域得 到应用。目前，粒子群优化算法的研究大致可分为以下几个领域：算法的原理 研究、算法的改进研究以及算法的应用研究1 9 。 ( 1 ) 微粒群优化算法的原理研究 即粒子之间是如何相互作用与运动而最终达到全局优化的，与相对鲜明的 生物社会特性基础相比，粒子群优化算法的数学基础显得相对薄弱，缺乏深刻 且具有普遍意义的理论分析。因此，对数学基础的研究非常重要，如粒子运动 轨迹研究、算法收敛性研究和粒子群分布与演化研究等等。文献f 1 0 1 利用微分 方程和差分方程为工具对单个粒子的运动轨迹进行研究发现：单个粒子其轨迹 是各种正弦波的随机的叠加组合。关于微粒群算法的收敛性研究比较多的集中 在一些简化条件下的结果，采用的主要工具是动态系统理论，其它还有采用集 合论的方法来研究此问题】。文献 1 2 采用f o k k e r - p l a n c k 方程和l a n g e v i n 方 程对微粒群算法的运行机理有比较深入的分析研究。 ( 2 ) 微粒群优化算法的改进研究 微粒群优化算法的改进研究可以说是微粒群算法研究的最要分支，其内容 十分庞大，但多数改进方案是基于其它的优化算法的结合。- 微粒群算法由于其简单和解决问题的有效能力而被应用到很多的领域。但 在实际应用当中，也表现出一些不尽人意的问题。这些问题中最主要的是它容 易产生早熟收敛，局部寻优能力较差等。实际上这些缺点也是所有随机算法的 西南交通大学硕士研究生学位论文第4 页 弊病。梯度法、爬山法、直接搜索法、模拟退火法等一些优化算法却具有很强 的局部搜索能力，而一些含有问题域相关知识的启发式算法的运行效率也比较 高。可以说，大多数优化方法的全局搜索能力和局部搜索能力单靠一种算法往 往无法得到有效利用和平衡，从而影响了算法的求解精度和效率。因此，如何 合理结合不同算法的优点来构造新算法，对于实时性和优化性同样重要的工程 领域，具有很强的吸引力。自然地人们想到了混合两种算法或者多种算法在一 个模型里面。尽量发挥各个算法的优点，从而形成了一个研究混合算法的方向。 因此。在微粒群算法搜索过程中融合入其他的优化方法的思想，构成混合粒子 群算法成为p s o 算法改进的最常见的思路。 a n g e l i n a 将选择算子引入p s o 中，选择每次迭代后的较好粒子复制到下 一代，以保证每次迭代的粒子群都具有较好的性能，这种算法对某些单峰函数 效果良好【1 3 】。文献 1 4 】在粒子群每次迭代后，按几率在粒子间交换各维，通过 交叉来生成更加优秀的的粒子，算法对某些多峰值函数效果比较好。h i t a c h i 等 人分别提出了自己的变异算法，基本思路均是希望通过引入变异算子跳出局部 极值点的吸引，从而提高算法的全局搜索能力，得到较高的搜索成功率【- s 1 。高 鹰等人引入免疫机制的概念，提高粒子群的多样性和自我调节能力，以增强粒 子的全局搜索能力【1 6 】。b a s k a r 等人提出了自己盼协同算法，通过使用多群粒子 分别优化问题的不同维，多群粒子协同优化等办法来对基本粒子群算法进行改 进尝试。 除以上的混合算法之外，还出现了量子p s o 、模拟退火p s o 、耗散p s o 、 自适应p s o 等混合改进算法，也有采取与基于梯度的优化方法相结合的办法。 大多数混合粒子群算法，相对于标准微粒群优化算法，可以说在性能上都有不 同程度的提高，但是，也存在一些问题，如，其算法的理解复杂度和实现复杂 度往往较高，从而对算法的工程应用造成了较大的障碍。因此，从工程应用的 角度分析，如何合理选择惯性权重等参数，使得算法既能避免早熟又能比较快 速地收敛，又能有效地控制算法的理解复杂度和实现复杂度，对工程实践有着 重要意义。 ( 3 ) 微粒群优化算法的应用研究 算法的有效性必须在应用中才能体现，尽管p s o 算法已经在一些领域得 了很好的应用，但是在其他一些应用领域都还处于研究阶段，因此，广泛地开 西南交通大学硕士研究生学位论文第5 页 拓的应用领域，也对深化研究算法非常有意义。p s o 在系统设计、分类、模式 识别、信号处理、机器人技术应用、决策制定、模拟和证明等领域的应用，大 量的学者和工程技术人员也进行了一系列的研究。 本文主要内容集中在微粒群优化算法研究的第二和第三个方面。针对微粒 群的基本缺点，进行了较为简单的改进。然后将其应用在图像压缩编码当中。 1 3 矢量量化码书设计算法的国内外研究现状 矢量量化的基本理论早在二十世纪六七十年代已经有人关注，而在二十世 纪八十代开始逐步完善起来。矢量量化是分组量化的一种，受到广泛注意和使 用的分组量化方法。1 9 8 0 年，由l i l l d e ，b u z o 和研a y 提出l b g 算法，将矢 量量化技术推向了高潮，并得到了广泛的应用。在2 0 多年历程中，学者们在 以下五方面对矢量量化技术展开研究：( 1 ) 矢量量化器的研究；( 2 ) 矢量量化码 书设计算法研究；( 3 ) 矢量量化码字搜索算法研究；( 4 ) 矢量量化码字索引分 配算法研究；( 5 ) 矢量量化的应用研究； 本文主要集中在码书设计算法方面的研究。一种直观有效地并且经典的算 法就是l b g 算法。l b g 算法的观念清晰、算法理论严密并且比较容易实现。 但是l b g 算法也存在几个比较明显的缺陷：第一，在每次迭代的最佳的划 分阶段，从码书中搜索训练矢量的最近码字需要大量的存储空间和繁琐的计 算。第二，l b g 算法对初始码书比较敏感和比较容易陷入局部最优。第三， 码书的自适应能力不强。针对以上的缺陷，已经涌现出了大量的相关改进算法， 大体上可以分为以下几类。 ( 1 ) l b g 算法的改进：为了获得更好的初始码书，文献 2 0 】中提出了一种 改进初始化的技术。为了获得更好的码书性能和收敛速度，文献 2 1 】提出了成 对最邻近码书设计算法( p a i r w i s en e a r e s t n e i g h b o r , p n n ) 。明显的减少了计算的 复杂度，但是最后得出码书的性能比l b g 差。文献 2 2 】提出了基于快速胞腔划 分的改进分裂法矢量量化码书设计算法减少了运算时间。 ( 2 ) 基于全局优化技术的码书设计：码书设计的最终目标是得到训练矢量 集的最佳划分。所以可以采用全局优化技术来进行码书设计以提高码书的性 能。目前已经有学者将遗传算法、蚁群算法、模拟退火、禁忌搜索等引入到码 西南交通大学硕士研究生学位论文第6 页 书设计当中1 2 3 - 2 6 1 ，取得了比l b g 算法性能高的码书。 ( 3 ) 基于模糊聚类理论的设计算法：上面各种矢量量化码书设计算法都是 将每个训练矢量根据一定的准则分配给单个聚类，而忽略了训练矢量属于其它 聚类的可能性，导致算法局部最优或强烈依赖于初始码书。因此文献 2 7 将模 糊理论引入到码书设计当中。文献【2 8 】提出的模糊矢量量化算法( f u z z yv e c t o r q u a n t i z a t i o n ，f v q ) ，对初始码书的依赖度比较小，性能比l b g 好，但是运算时 间还是较多。这一类改进算法的缺点就是计算量比较大运行时间比较长。 1 4 本文的主要研究内容与章节安排 本文的主要研究内容分布于以下各章节之中： 第一章，绪论：介绍了本文的研究背景与意义，研究的内容的现状和今后 的发展趋势，同时给出了本文的章节内容安排。 第二章，微粒群优化算法：是对微粒群优化算法的介绍和分析，主要介绍 微粒群优化算法的基本原理，算法的数学描述和计算步骤，并介绍了几种经典 的改进模型，并对微粒群优化算法的参数的进行了详细的分析与探讨，通过仿 真实验给出了各个参数对优化算法的性能影响。 第三章，微粒群算法的改进研究：首先介绍了现有的几种比较经典的改进 算法和模型，在参考文献和分析算法的基础之上重点介绍本文对微粒群优化算 法的改进思想，包括引入方差聚集思想来改进参数，根据粒子的适应值排序来 改变惯性权重因子，同一代的粒子有不同的惯性权重，采用平均极值和变异策 略来增加种群的多样性，是优化算法后期的收敛加快，增强全局寻优能力。并 通过对经典的测试函数进行仿真实验，给出了改进后优化算法在各个方面的性 能效果。 第四章，微粒群优化算法的应用，首先分析了矢量量化技术的基本原理， 分析了比较经典的矢量量化算法l b g 的性能和优缺点，提出改进微粒子优化 算法优化l b g 算法，通过对图像压缩的仿真实验，给出改进后算法的性能分 析。说明改进后的算法具有良好的性能。 第五章，总结与展望，针对论文的研究内容作出总结，指出还需要解决的 问题和进一步的研究方向。 西南交通大学硕士研究生学位论文第7 页 第2 章微粒群优化算法 2 1 基本微粒群算法 2 1 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 5 。微粒群优化算法( 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 ) 是一种集群优化算法，起源于对一个简单化社会模型的仿真。它是受到 鸟群群体运动行为方式启发而提出的一种具有代表性的群体智能方法。研究者 发现鸟群在飞行过程中经常会突然改变方向、散开、聚集，其行为通常不可预 测，但其整体总能保持一致性，个体与个体间也保持着最适宜的距离。通过对 类似生物群体的行为的研究，发现生物群体中存在着一种社会信息共享机制， 它为群体的进化提供了一种优势，这也是微粒群优化算法形成的基础。 微粒群算法与其他演化算法的相似之处，也是根据对环境的适应度将群体 中的个体移动到好的区域，不同之处在于它不像其他演化算法那样对个体使用 演化算子，而是将每个个体看作寻优空间中的一个没有质量没有体积的微粒， 根据个体与群体的飞行经验的综合分析结果来动态调整飞行速度。微粒群优化 算法从群体行为模型中得到启示并用于解决各种复杂的优化问题，在微粒群优 化算法的整个寻优搜索过程中，所有粒子的适应值( f i m e s sv a l u e ) 取决于所选 择的优化函数的值，并且每个粒子都具有以下几类信息，粒子当前所处位置， 粒子当前飞行速度，到目前为止粒子本身所发现的最优位置( p b e s t ) ，可视为粒 子的自身飞行经验，p b e s t 也就是粒子本身所找到的最优解，这个解称为个体 极值；到目前为止整个种群中所有粒子发现的最优位置( g b e s t ) ( 曲e s t 是p b e s t 中的最优值) ，这可视为粒子群的同伴共享飞行经验，g b e s t 称为全局极值。于 是各个粒子的运动速度受到自身和群体的历史运动状态信息影响，并以自身和 群体的历史最优位置来对粒子当前的运动方向和运动速度加以影响，这样就很 好的协调了粒子自身运动和群体运动之间的关系。 西南交通大学硕士研究生学位论文第8 页 2 1 2 基本微粒群优化算法的数学描述 p s o 算法是基于群体的优化方法，根据对环境的适应度，将群体中的个体 向好的区域移动。在p s o 系统中，每个备选解被称为一个粒子( p a r t i c l e ) ，多个 粒子共存，合作寻优。每个粒子根据自身经验和群体的最佳经验在问题空间中 向更好的位置飞行，搜索最优解。在每一次迭代中，粒子通过跟踪个体极值和 全局极值来更新自己。p s o 算法的数学过程表示如下： 假设搜索空间是d 维的，n 表示粒子的总数，粒子群中第i 个粒子的位置 表示为z ( 薯。，x j 2 - - d ) ，第i 个粒子的速度表示为形( v 。，v ：) 。第i 个粒子 迄今为止搜索的最好的位置记为乞删( 6 f 。，勿：6 耐) 。整体粒子迄今搜索到的最好 位置表示为p g ( p g l ，p9 2 ，p g d ) 。对于每一代粒子，它的第d 维按如下公式变化： 杉d ( f + 1 ) = d ( f ) + c l r a n d o ( b , d x t d o ) ) + c ：a n d ( ) ( p g , l 一o ) ) ( 2 1 ) o + 1 ) = x j d o ) + 屹+ 1 ) ( 2 2 ) 其中1 i n ，l d d ； c l 和乞称为学习因子，是一个常数，用来调节 向和p g 方向飞行的步长，r a n d ( ) 表示0 到1 之间的随机数。通常q - - - - t ? 2 = 2 广 粒子群的规模n 也可以根据搜索空间的维数d 用下列公式来求得： = 1 2 + 2 d( 2 - 3 ) 假设搜索空间的第d 维定义为 一髟一，髟一 ，屹一= k x x d m , ，k 【o 1 ，1 】。 2 屹一又? ? 一) 、 (2-4) 【v , d = 一v d 懈，( 一屹麟) ( 2 - 4 ) 式中，对粒子的速度v 进行最大限制。如果当前粒子在某一维的速度 分量超过该维的最大速度限制，则按公式( 2 - 4 ) 取边界值。 粒子的运动由( 2 1 ) 、( 2 2 ) 方程共同作用。粒子的运动速度增量与其历 史飞行经验和群体飞行经验相关，并受最大飞行速度的限制。这样的运动模式 可以用于各类寻优问题的求解。在图2 1 中，以二维空间为例描述了粒子根据 公式( 2 1 ) 、( 2 2 ) 从位置s k 向s k + 1 移动的原理。 西南交通大学硕士研究生学位论文第9 页 图2 - 1粒子移动原理 从社会学的角度来考虑公式( 2 1 ) 等号右边，其中的第一部分表示粒子 对当前自身运动状态的信任，依据自身以往速度进行惯性运动；第二部分为认 知部分，表示粒子本身的思考，来源于自身的经验。第三部分是社会部分，表 示粒子问的信息共享与相互合作，即粒子的运动来源于群体中其他粒子经验的 部分，它通过认知模仿了较好同伴的运动。粒子的移动原理见图2 1 。 2 1 3 微粒群算法的基本步骤与流程 微粒群优化算法的主要计算步骤如下： ( 1 ) 初始化，设定加速常数c ，和岛，最大进化迭代次数瓦一将当前 进化代数置为t = l ，设置种群规模大小为n ，粒子维数为d ，在允 许的范围内，对每个粒子随机的给定j 个初始位置和初始速度。 每个粒子的p b e s t 设置为其初始位置，p b e s t 中最好的值设为g b e s t 。 ( 2 ) 根据目标函数，计算出每个粒子的适应值。 ( 3 ) 对于每个粒子，将步骤2 中计算出的粒子的适应值与其经历的最 好位置p b e s t 进行比较，如果优于p b e s t ，则将其作为当前最好的 位置。 ( 4 ) 对每个粒子，将它的适应值p b e s t 与群体所经历的最好位置g b e s t 进行比较，如果优于g b e s t ，则用该粒子的适应值取代种群原有的 西南交通大学硕士研究生学位论文第10 页 最优适应g b e s t ，同时用该粒子的位置取代群体最优粒子的位置。 ( 5 ) 根据方程( 2 1 ) 和( 2 2 ) 更新每个粒子的速度和位置；对于每 个粒子的速度进行越界检查，确保粒子的速度在l 叱一，屹一】之 阎，对每个粒子进行位置越界检查，确保粒子位置在【- 虬一， 髟一】之间。 ( 6 ) 检查终止条件是否满足，或是否达到最大迭代次数，若是则终止 计算，输出相关的结果。否则返回步骤2 0 。 微粒群优化算法的流程图如图2 - 2 ： 图2 - 2 微粒群算法的流程图 西南交通大学硕士研究生学位论文第”页 2 1 4 全局模式与局部模式 微粒群优化算法根据对邻近粒子的定义不同，微粒群优化算法分为全局模 式和局部模式。对于全局模式的p s o 算法来说，邻近粒子指整个粒子群体； 对于局部模式的p s o 算法来说，邻近粒子仅指几个拓扑相邻或空间相邻的粒 子。 在微粒群优化算法中，当把整个种群定义为同伴时，算法被称为全局版 ( g l o b a lv e r s i o n ) 的微粒群优化算法，当同伴仅指种群中的一部分粒子时，称为 局部版( 1 0 c a lv e r s i o n ) 的微粒群优化算法。也就是说，在全局版本的p s o 算法中， 粒子跟踪两个极值，自身极值p b e s t 和种群全局极值g b e s t ；而在局部版本的 p s o 算法中，指粒子除了追随自身极值p b e s t 之外，不跟踪全局极值g b e s t ，而 是追随拓扑近邻粒子当中的局部极值l b s e t 。在该版本中，每个粒子需记录自 己和它所在局部的最优值，而不需要记录整个群体的最优值。局部模式的粒子 群优化将公式( 2 1 ) 更新为( 2 5 ) v 0 ( t + 1 ) = v 口o ) + ( p 6 9 s 毛( f ) 一吃( f ) ) + 吃( 三6 s p 气( f ) 一勘) ) ( 2 - 5 ) 通过上面对两种不同版本算法的比较可以看出，由于局部版的p s o 算法 允许粒子与其邻域内粒子比较当前搜索到的最优位置，从而相互之间施加影 响，即便其值比种群最好值要差，该影响可以使较差个体进化为较好的个体。 而全局版的p s o 算法中所有粒子都能够信息共享，所以粒子向当前最优解收 敛的趋势非常明显，因而全局模型通常搜索到最优值的速度比局部版的p s o 算法要快。但由于全局版的p s o 算法中所有粒子都迅速趋向与同一最优值， 因而全局模型比局部模型更易陷入局部极小，出现“早熟”现象。 2 1 5 同步模式与异步模式 微粒群优化算法可以按粒子更新的方式分为同步模型( s y n c h r o n i z a t i o n ) 和 异步( a s y n c h r o n i z a t i o n ) 模型。同步模型是指在每一次迭代中，所有粒子都并行 同步更新自身位置和速度后再从中选择种群最优粒子作为9 6 p 盯，如图2 3 所 示。而微粒群优化算法中的异步模型是指当粒子群中的任何一个粒子更新后， 都要与种群中的最优粒子进行比较，及时更新种群最优粒子的信息，如图2 - 4 西南交通大学硕士研究生学位论文第12 页 所示。通过实验仿真发现，在多数情况下，异步模型比同步模型能更快地找到 问题的最优解1 2 9 。 队 黔嘴训 一 更新读取 一 时 图2 - 3p s o 同步模式描述 啪群 一 更新读取 “r 图2 - 4p s o 异步模式描述 2 1 6 微粒群算法的特点 公共信息 公共信息 微粒群算法与其他优化算法相比具有以下特点： ( 1 ) 微粒群算法的收敛速度快，算法简单、易于描述而且容易编程实现， 需要调整的参数较少。 ( 2 ) 虽然微粒群算法在数学上还没有成熟的收敛性分析方法，但是它却 能比传统算法更快的解决实际工程中的连续空间优化问题。目前， 微粒群算法已成功应用到包括神经网络训练和函数优化等各种连续 问题中。 ( 3 ) 微粒群算法在计算优化问题时，不需要目标函数的梯度信息，它已 经被证明是解决许多全局优化问题的有效方法。 ( 4 ) 微粒群算法具有并行性，其搜索过程是从一个解的集合开始而不是 从单一的可能解开始。这种并行性提高了算法的性能和求解效率， 西南交通大学硕士研究生学位论文第13 页 使得微粒群算法在求解相同问题时要比一般的优化算法速度更快。 2 2 经典的微粒群优化算法模型 基本粒子群算法提出以后，引起了许多学者对基本微粒群算法进行改进， 其中比较有名的也是常用的几种模型如下： 2 2 1 带惯性权重系数的微粒群优化算法 在文献 3 0 】中，s h i 等人对式( 2 1 ) 做了如下的改动： o + 1 ) = 屹( f ) + q 翮d ( ) ( 一x 丘t ( t ) ) + c 2 r a n d ( ) ( p s a 一( f ) ) ( 2 - 6 ) 其中c o 是非负数，称为惯性权重系数( i n e r t i aw e i g h t ) 。惯性权重c o 是用来 控制粒子以前速度对当前速度的影响的，即粒子对自己以前速度的信任。它将 影响粒子的全局和局部搜索能力。较大国的值有利于全局搜索探索能力，较小 的有利于局部搜索开发能力。选择一个合适的国值可以平衡全局和局部搜索 能力，即平衡算法的收敛速度和收敛精度，这样可以以最少的迭代次数找到最 优解。 对全局搜索，通常的好方法是在前期有较高的探索能力以得到合适的解， 而在后期有较高的开发能力以加快收敛的速度。因此可以将设置成随着迭代 次数增加而线性减少，ys h i 和r c e b e r h a r t 的仿真实验结果也表明线性减 少取得了较好的实验结果。最初建议的取值范围为 0 ，1 4 ，但是实验结果 表明当取值在 0 8 ，1 2 ，算法的收敛速度更快，而当 1 2 时，算法则较 多地陷入局部极值。在文献 3 1 】中，惯性权重国的计算公式如公式( 2 7 ) 所 示： 国( t ) = 。一i 7 竺( 。一。；。) ( 2 7 ) 国( ) 2 。一i 7 了_ _ ( 。a 。一。i 。) l 么，j 坦“ l l r ， 其中m a x i t e r 最大的迭代次数，i t e r 为当前的迭代次数，q 嘣为最大的惯 性权重系数，。为最小的惯性权重系数。这是一般的惯性权重线性减少的方 法。在文献 3 2 当中也做了些非线性的改进，提出了基于模糊系统的惯性权重 的动态调整和针对动态优化问题的随机惯性权重等方法心”。这些改进算法虽然 西南交通大学硕士研究生学位论文第14 页 提高了收敛速度并且在单峰值函数问题上取得了更高的性能，但是在解决多峰 值函数问题时，容易陷入局部最优并且实现也比较困难。所以选取合适的惯性 权重系数c o 很重要，可以权衡粒子的全局搜索能力和局部搜索能力，提高算法 的效率。 2 2 2 带收缩因子的微粒群优化算法 为了提高算法的收敛速度，c l e r c 等人在标准的p s o 算法的基础上引入 了收缩因子( c o n s t r i c t i o nf a c t o r ) 的概念1 3 3 3 4 。其模型如下： v j ( f + 1 ) = k ( v l ，( f ) + c l r l ( p ，( f ) 一x ，( f