（计算数学专业论文）混合粒子群算法及其应用研究.pdf

摘要 粒子群优化算法是智能优化算法的典型代表，它的特点是简单、收敛速度快，且所需领域 知识少。它可用于求解大部分的优化问题，并在经济与工程实践中表现出巨大潜力，已广泛应 用于神经网络、模糊系统控制、模式识别等多个领域。 本文介绍了粒子群优化算法的概况，针对粒子群优化算法参数的动态特性以及算法早熟收 敛、后期振荡现象等问题，提出了一些粒子群算法中惯性权重的改进策略，构造了几个性能较 好的基于粒子群优化的混合智能算法。 一、提出了两种动态惯性权重策略。一是提出指数动态改变的惯性权重，提高了粒子群算 法的收敛速度。二是利用适应度函数的变化来动态改变惯性权重，提出了一种自适应粒子群优 化算法，提高了算法的全局搜索能力和计算精度。 二、将其它优化策略融入粒子群优化算法中，构造出两种混合粒子群优化算法。一是构造了 一种将模拟退火策略融入惯性权重并且将粒子群算法和免疫算法相结合的算法，该算法有效地 避免了早熟现象的出现，并提高了全局寻优的能力；二是将对数权重和模拟退火策略融入粒子 群优化算法中，构造出混合粒子群优化算法。当算法陷入局部解时，融合模拟退火策略可使该 算法跳出局部极小，从而提高全局寻优能力。 三、提出两种求解组合优化问题的混合优化算法。针对约束优化问题，将混沌变异融合到 粒子群优化算法的搜索过程中，将惯性权重设置为零，可有效避免粒子陷入局部最优解，改善全 局搜索能力。针对旅行商问题，将模拟退火策略融合到粒子群算法中，来求解问题。仿真计算 表明，这两种算法都具有良好的计算效果。 关键词：智能计算，粒子群算法，免疫算法，混沌变异，模拟退火算法。 i i a b s t r a c t a st y p i c a lr e p r e s e n t a t i v eo fs w a r mi n t e l l i g e n c eo 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 n o s o ) i ss i m p l ei nc o n c e p t , f e wi np a r a m e t e r sa n de a s yi ni m p l e m e n t a t i o n p s oc a nb eu s e dt os o l v e v a r i o u so p t i m i z a t i o np r o b l e m sa n ds h o w sg r e a tp o t e n t i a l i t yi ne c o n o m ya n de n g i n e e r i n gp r a c t i c e n o w ，i th a sb e e n 丽d e l ya p p l i e di nm a n yo t h e ra r e a s ，s u c ha sa r t i f i c i a ln e u r a ln e t w o r k ，f u z z ys y s t e m c o n t r o la n dp a t t e mr e c o g n i t i o n t l l i sp a p e ri n t r o d u c e st h eg e n e r a ls t a t i o no fp s of i r s t l y a n dt h e n 。a i m i n gt ot h ep r o b l e m ss u c h a st h ed y n a m i cp a r a m e t e r , l o c a lc o n v e r g e n c e ，a n d t h e $ u r g ep h e n o m e n o ni na n a p h a s eo fp s o ，s e v e r a l m o d i f i e ds t r a t e g i e sf o rt h ei n e r t i aw e i g h tw h i c ha r cb e t t e rt h a nt h eb a s i cp s oa r cp r e s e n t e di n0 1 1 1 w o r k a n ds o m ep r o p e r t i e so ft h es t r u c t u r et h a np a r t i c l es w a r mo p t i m i z a t i o nb a s e do nt h eb e s to ft h e h y b r i di n t e l l i g e n ta l g o r i t h ma r ep r e s e n t e di nt h i sp a p e r 1 t w ok i n d so fd y n a m i c a l l yc h a n g i n gi n e r t i aw e i g h ta r ep r e s e n t e di nt h i sp a p e r o n ei se p s o a l g o r i t h mw i t ha ne x p o n e n t i a ld e c r e a s i n gi n e r t i aw e i g h tt h a ti m p r o v e dt h ec o n v e r g e n c er a t e o f 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 eo t h e ri sa na d a p t i v ei n e r t i aw e i g h tp s oa c c o r d i n gt ot h ef i m e s s v a l u ei sp r e s e n t e d , w h i c hc a nc h a n g et h ei n e r t i aw e i g h ta d a p t i v e l ya n dd y n a m i c a l l y t h en e w a l g o r i t h mc a ni m p r o v et h ec a p a c i t yo fg l o b a ls e a r c ha n dc a l c u l a t i o na c c u r a c yo fp a r t i c l e 娜a r n l o p t i m i z a t i o n 2 o t h e ro p t i m a ls t r a t e g i e sa r ec o m b i n e dw i t hp s ot oc o n s t r u c tt w oh y b r i dp s oa l g o r i t h m s t h e f i r s t ，t h es i m u l a t i o na n n e a l i n gs t r a t e g yi n t e g r a t e si n e r t i aw e i g h t , a n di m m u n i t ya l g o r i t h mw i l lu n i f y t h ep s oa l g o r i t h m t h i sa l g o r i t h mh a sa v o i d e dt h ep r e c o c i o u sp h e n o m e n o na p p e a r a n c ee f f e c t i v e l a n ds h a r p e n e dt h eo v e r a l ls i t u a t i o no p t i m i z a t i o na b i l i t y i na d d i t i o n ，ah y b r i dp a r t i c l es w a r m o p t i m i z a t i o ni sp r o p o s e d ，w h e r et h es i m u l a t e da n n e a l i n gi d e ai sc o m b i n e dw i t hp s o t h eh y b r i dp s o c a ne n h a n c et h ed i v e r s i t yo fs w a r ma n da v o i dt h ec o m m o nd e f e c to fp r e m a t u r ec o n v e r g e n c ew h e ni t i st r a p p e di nt h el o c a lo p t i m a s oi tc a ns t r e n g t h e nt h ea b i l i t yo fg l o b a ls e a r c h i n g 3 t w ok i n d so f h y b r i dp s oa l g o r i t h ma r ep r e s e n t e df o rc o m b i n a t o r i a lo p t i m i z a t i o np r o b l e m s i n v i e wo ft h er e s t r a i n to p t i m i z a t i o nq u e s t i o n ，t h ec h a o sv a r i a t i o ni n t e g r a t et h ep s o ，i nt h es e a r c h p r o c e s s t h ei n e r t i aw e i g h te s t a b l i s h m e n ti sz e r 0 a v o i d i n gt h ep a r t i c l ef a l l i n gi n t o t h ep a r t i a lo p t i m a l s o l u t i o ne f f e c t i v e l y , i m p r o v e st h eo v e r a l ls i t u a t i o ns e a r c ha b i l i t y i no r d e rt ot a c k l et h e 缸a v e l i n g s a l e s m a np r o b l e m a n o t h e rh y b r i dp s o 谢t is i m u l a t e da n n e a l i n gs t r a t e g yi sp r o p o s e d i ti ss h o w nb y n u m e r i c a lt e s tt h a tt h e s et w oa l g o r i t h m sa r em o r ee f f e c t i v e k e yw o r d s ：i n t e l l i g e n ta l g o r i t h m ；p a r t i c l es w a r mo p t i m i z a t i o n ；i m m u n i t ya l g o r i t h m ；c h a o s ； s i m u l a t e da n n e a l i n g i i l 独创性声明 本人声明所呈交的论文是我个人在导师指导下进行的研究工作及取得的研究成 果。尽我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其他人已经发 表或撰写过的研究成果，也不包含为获得宁夏大学或其它教育机构的学位或证书而使 用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中作了明确的 说明并表示了谢意。 研究生签名： 剀磁 时间：护i 年易月 l 关于论文使用授权的说明 本人完全了解宁夏大学有关保留、使用学位论文的规定，即：学校有权保留送交 论文的复印件和磁盘，允许论文被查阅和借阅，可以采用影印、缩印或扫描等复制手 段保存、汇编学位论文。同意宁夏大学可以用不同方式在不同媒体上发表、传播学位 论文的全部或部分内容。 ( 保密的学位论文在解密后应遵守此协议) 研究生签名： 专j 1 麟 聊虢氪琳 帆d 7 年占月日 慨少年多月乡同 宁夏人学硕卜论文第一章绪论 曼曼舅舅曼曼曼曼曼曼曼曼寡曼曼曼鼍曼曼曼i i i i i_ _ _ _ _ i 曼曼曼曼量曼蔓曼皇曼曼曼曼皇曼曼曼曼曼曼曼曼皇蔓量 第一章绪论 1 1 课题的研究背景和意义 优化技术是一种以数学为基础，用于求解各种经济与工程问题最优解的应用技术。最优化理 论与算法作为一个重要的科学分支，一直受到人们的高度重视，并在科学、经济以及工程领域发 挥着极为重要的作用。另外对于优化算法的改进与创新研究、拓宽算法领域、完善算法体系同样 具有重要作用。因此，优化理论与算法研究是一个同时具有理论意义和应用价值的重要课题。解 决优化问题的算法通常分为确定性和随机性两种。确定性算法如：单纯形法、牛顿法、共轭梯度 法、分枝定界法、动态规划法等【l 捌，这些算法是按照函数变化机理进行寻优的，其搜索效率较高， 过程可再现，但寻优结果和初值有关，通常对函数有可导要求，在处理人们所面对的高维、大规 模、非线性、不可微等特性的复杂问题时，很容易陷入局部最优点而无法得到最优化结果。因此 高效的优化技术成为科学工作者的研究目标之一。 随着人类生存空间的扩大以及认识与改造世界范围的拓宽，人类需要对客观世界的规律有更 全面深入的理解，所以人们从生命现象中得到启示，不断寻求、发明了许多智能优化方法来解决 复杂优化问题【3 5 1 。例如：遗传算法( g e n e t i c a l g o r i t h m ) ，它模拟了生物种群通过遗传和自然选择不 断进化的功能【l7 】；人工免疫系统( a r t i f i c i a l 血r l u n es y s t e m s ) ，它模拟了生物免疫系统的学习和认 知功能【3 州；蚁群优化( a n tc o l o n yo p t i m i z a t i o n ) 算法，它模仿了蚂蚁群体在路径选择信息传递方面 的行为【4 0 】；粒子群优化( p a r t i c l es w a r mo p t i m i z a t i o n ) 算法，其模拟了鸟群和鱼群觅食迁徙中个体 与群体协调一致的机理 3 , 4 1 , 4 2 1 ；群落选址算法( c o l o n yl o c a t i o na l g o r i t h m ) ，其模拟了植物群落的 形成机$ 1 j 4 3 , 4 6 ，它们都可在合理的时间内逼近复杂对象问题的最优解。这些算法的独特优点和机 制，引起了国内外学者的高度重视并掀起了该领域的研究热潮，且在许多领域得到了成功应用。 在优化领域，由于这些算法构造的直观性与自然机理，被称作为智能优化算法。 p s o 算法作为智能优化算法的一种，其最具吸引力的特征就是简单、易实现，没有很多参数 需要凋整和很强的全局优化能力。因而短期内得到很大发展，迅速得到了国际演化计算研究领域 的认可，并在很多领域得到应用，如电力系统优化、t s p 问题、神经网络训练、数字电路优化、 函数优化、交通事故探测、参数辨识等。p s o 算法是解决非线性连续优化问题1 7 j 、组合优化问题 h 和混合整数1 f 线性优化问题时的有效优化- 1 ：具，目前已经广泛应用于函数优化、神经网络训练、 模糊系统控制以及其他遗传算法领域。p s o 算法最初应用到神经网络训练上，在随后的应用中， p s o 算法又可以用来确定神经网络的结构。作为演化神经网络的例子，e b e r h a r t 等人已经成功用 p s o 来分析人类的盹金森综合症等颤抖类疾病i l 引。t a n d o n _ jp s o 米训练控制铣削过程的神经网 络【i9 1 。文献【2 0 l 中用改进的速度更新方程来训练模糊神经网络。p a r s o p o u l o s 等将p s o 用t 解决多 目标优化问剧2 8 ，2 巩见j 、最小最火化问题、整数规划问题和定位所有全局极值等问题。 但现阶段对粒子群优化算法的研究还不够完善，核心部分的参数选择仍然有很大争议。目前 许多对算法的改进，在提高了算法性能的同时，也增加了算法的运算复杂度，这不适合于对算法 收敛速度要求较高的戍川，冈此，选择粒子群优化算法为研究对象，找剑一种能够提高算法收敛 速度义不增加算法复杂度的改进方法是很有意义的。 p s o 优化算法在解决实际问题方面，还有很人的潜力，存在很人的发展空间。目前粒子群算 宁夏大学硕 ：论文第一章绪论 法越来越引起人们的关注，已成为国际上一个新的研究热点。 1 2 本文的研究目的和研究内容 1 2 1 本文的研究目的 虽然目前对粒子群优化算法( p s o ) 的研究和应用有了许多的成果，但是核心部分的参数选 择仍然有很大争议，许多改进的算法在提高性能的同时，也增加了运算的复杂度，因此粒子群优 化算法在理论上还很不完善，在应用的深度和广度上有待进一步加深和拓展，还存在很多局限性： ( 1 ) 粒子群优化算法主要应用在连续型实数的问题领域中，而离散型变量问题的领域应用很 少。 ( 2 ) 粒子群优化算法收敛速度快，特别是在算法的早期，但也存在着易早熟，易发散等缺点。 若加速因子、最大速度等参数太大，粒子可能错过最优解，算法不收敛；而在收敛的情况下，由 于所有粒子都向最优解飞去，所以粒子趋向同一化( 失去了多样性) ，使得后期收敛速度变慢， 同时算法收敛到一定精度时，无法继续优化。 ( 3 ) 由于基本粒子群优化算法依靠的是群体之间的合作与竞争，粒子本身没有变异机制，因 而单个粒子一旦受到局部极值约束后本身很难跳出局部极值的约束。试验指出在粒子群优化算法 的运行初始阶段，收敛速度比较快，运动轨迹呈正弦波摆动，但运行一段时间后，速度开始减慢 甚至停滞。当所有粒子的速度几乎为0 ，此时粒子群丧失了进一步进化的能力，可以认为算法执 行已经收敛。而在许多情况下( 如复杂的多峰值函数寻优) ，算法并没有收敛到全局极值，甚至 连局部极值也未必达到。这种现象被称为早熟收敛或停滞。 对于粒子群优化算法有待于解决的问题还很多： ( 1 ) 算法分析。粒子群优化算法在实际应用中被证明是有效的，但目前还没给出收敛性、收 敛速度估计等方面的数学证明，已有的工作还远远不够。 ( 2 ) 粒子群拓扑结构。不同的粒子群邻居拓扑结构是对不同类型社会的模拟，研究不同拓扑 结构的适用范围，对粒子群优化算法推广和使用有重要意义。 ( 3 ) 参数选择与优化。参数w , c ，c ：的选择分别关系粒子速度的三个部分：惯性部分，社会部 分和自身部分在搜索中的作用。如何选择、优化、和调整参数，使得算法既能避免早熟又能比较 快速地收敛，对工程实践有着重要意义。 ( 4 ) 与其它优化计算方法的融合。如何将其它优化方法的优点和粒子群优化算法的优点结合， 构造出有特色有实用价值的混合算法是当前算法改进的一个重要方向。 ( 5 ) 算法应用。算法的有效性必须在应硝中才能体现，广泛地开拓应用领域，也对深化研究 粒子群优化算法非常有意义。 针对粒子群优化算法的以上的局限性和有待解决的问题，本文展开了细致的研究，对基本粒 子群优化算法作了各式各样的改进，主要从以卜几个方面着手提高粒子群优化算法的性能：加快 算法的收敛速度，提高种群的多样性，算法停滞或陷入局部最优后的处理，与其它优化算法的结 合。对算法的改进不可避免地遇剑局部搜索速度与全局搜索能力之间的平衡问题，也是收敛速度 与搜索精度之间的权衡。 2 宁夏大学硕l 论文第一章绪论 1 2 2 本文的研究内容 本文对粒子群优化算法进行了改进和应用： 1 研究基本粒子群优化算法模型结构和机理，弄清加速常数和惯性权重参数的选择对算法 性能和实现效果的影响，探索粒子群优化算法的寻优和迭代机理以及早熟和振荡现象。算法参数 是影响算法性能和效率的关键。而粒子群优化算法的最重要参数是惯性权重，它影响算法的全局 搜索能力和局部搜索能力的平衡。固定惯性权重和线性递减惯性权重都不能克服粒子群算法的早 熟收敛和后期振荡问题，本文设计出指数递减动态改变惯性权重的粒子群优化算法和自适应调整 惯性权重的粒子群优化算法。从对典型函数的仿真试验数据中可以看出，这两种新的算法均能有 效的克服带有固定权重和线性权重粒子群算法的不足，提高了算法的计算性能。 2 针对粒子群优化算法存在早熟收敛的问题，本文提出将其它优化策略嵌入粒子群优化算 法中，以此构造混合粒子群优化算法。实验表明本文提出的融合免疫思想的混合粒子群优化算法、 带模拟退火策略的混合粒子群优化算法的性能都优于带线性递减权重的粒子群优化算法。 3 本文将粒子群优化算法应刚在组合优化领域。 以求解约束优化为例，将混沌变异和粒子群算法的优点有机地结合起来，有效地克服各自 的不足。而求解旅行商问题时，则将模拟退火策略融入粒子群算法中，取得了较好的结果。 1 3 本文的结构 第一章绪论。介绍本文的课题背景、意义，以及本文目的和内容。 第二章粒子群优化算法概述。 第三章两种动态调整惯性权重的粒子群优化算法。 第四章混合粒子群优化算法。 第五章粒子群优化算法在组合优化中的应用。 第六章研究工作总结及展望。 3 宁夏人学硕 ：论文 第二章粒了群优化剪法概述 第二章粒子群优化算法概述 2 1 粒子群算法介绍 2 1 1 基本思想与原理 粒子群优化算法( p s o ) 是一种集群优化算法，其起源于对一个简单社会模型的仿真。它 是受鸟群群体运动行为方式启发而提出的一种具有代表性的集群智能的方法。研究者发现鸟群 在飞行过程中经常会突然改变方向、散开、聚集，其行为通常为不可预测，但其整体总能保持 一致性，个体与个体之间也保持着最适宜的距离。通过对类似生物群体的行为研究，发现生物 群体中存在着一种社会信息共享机制，它为群体的进化提供了一种优势，这也是粒子群优化算 法形成的基础。 设想这样一个场景：一群鸟在随机搜寻食物。在这个区域里只有一快食物，所有的鸟都不 知道食物在哪里，但是它们知道自己当前的位置离食物还有多远。那么找到食物的最优策略是 什么呢? 最简单有效的方法是搜寻目前离食物最近的鸟的周围区域。粒子群优化算法从这种模 型中得到启示并用于解决优化问题。粒子群优化算法中，每个优化问题的潜在的解都是搜索空 间中的一只鸟，称之为“粒子”。所有的粒子都有一个由被优化的函数决定的适应值，每个粒子 还有一个速度决定它们飞行的方向和距离。然后粒子们就追随当前的最优粒子在解空间中搜索。 粒子群优化算法初始化为一群随机粒子( 随机解) ，然后通过迭代找寻最优解。在每一次迭代中， 粒子通过跟踪两个极值来更新自己。第一个就是粒子本身找到的最优解，这个解称为个体极值： 另一个是整个种群目前找到的最优解，这个极值是全局极值。另外也可以不用整个种群而是其 中一部分作为粒子的邻居，那么在所有邻居中的极值就是局部极值，用局部极值来代替全局极 值。这样根据是采用全局极值还是局部极值，粒子群优化算法可分为全局版和局部版。 上述思想可抽象为，在一个d 维的目标搜索空间中，由m 个没有体积的粒子组成一个群落， 第i 个粒子表示为一个d 维向量x i = ( 工f l 而2 ，如) ，f = 1 , 2 ，m ，即第i 个粒子在d 空间的位 置。将石；代入一个日标函数就可以计算出其适应值，根据适应值的大小衡量x 。的优劣。第i 个 粒子的“飞翔”速度也是一个d 维向量，记为l = o n ，：，) 。记第i 个粒子迄今为止搜索 到的最好位置为e = ( p 舯p i 2 c 9 p 渺) ，也称为p 蛔。整个粒子群迄今为止搜索到的最好位置 0 = ( p 覃l p ，p s o ) ，也称为g 细。 k e n n e d y 和e b e r h a r t 最早提出粒子群优化算法采用下面的公式对粒子操作【l 】： 1 ，耐( t + 1 ) = v 耐( t ) + c 1 1 ( p 村o ) 一妇( ，) ) + c 2 ，2 切窖d ( t ) 一石耐( f ) j ( 2 1 ) x i d ( t + 1 ) = x 坩( t ) + y 甜( t + 1 ) ( 2 2 ) 其中d = 1 ，2 ，d ，f = 1 ，2 ，m ，_ ，l 为种群规模：，吃为均匀分布y o ，l 】之间的随机数：c 。，c ：为加 速度限定冈子，分别调节向全局最优粒子和个体最优粒子方向匕行的步长，合适的取值可加快 收敛且不易陷入局部最优，通常取2 ； 1 | 时，取卜村i = ，假设搜索空间的d 维定义 4 宁夏大学硕f ：论文 第二章粒了群优化算法概述 为【啊一，+ _ 一】，则通常一= h d 。 o 1 j 1 0 ；此后，s l l iy 义增设了惯性权重因子w ( i 艘砸aw o i g h t ) ，将( 2 1 ) 式改变为： ，埘( f + 1 ) = w v 甜( f ) + c i ( p 甜( f ) 一x s , ( t ) ) + c 2 r 2 k p ( f ) 一如( f ) j ( 2 3 ) 由( 2 3 ) 、( 2 2 ) 式组成的迭代算法被认为是基本p s o 算法。 式( 2 3 ) 的第一部分为粒子的先前的速度；第二部分为“认知( c o g n i t i o n ) ”部分，表示 粒子本身的思考；第三部分为“社会( s o c i a l ) ”部分，表示粒子间的信息共享与相互合作。 “认知”部分可由t h o m d i k e 的“影响法则( 1 a wo f e f f e c t ) ”的解释，即一个得到加强的随 机行为在将来更有可能出现。这里的行为即“认知”，并假设获得正确的知识是得到加强的，这 样一个模型假定粒子被激励着去减小误差 “社会”部分可由b a i l d u m 的代理加强概念的解释。根据该理论的预期，当观察者观察到 一个模型在加强某一行为时，将增加它施行该行为的几率，即粒子本身的认知将被其它粒子所 模仿。 2 1 2 算法流程 粒子群优化算法运行时初始化一群粒子( 群体规模为m ) ，包括随机位置和速度；并根据 适应函数计算评价每个粒子的适应度；接着，将每个粒子的适应值与其经历过的最好位置p 胁的 适应值作比较，如果较好，则将其作为当前的最好位置p 细；对每个粒子，将其适应值与全局 所经历的最好位置g 细的适应值作比较，如果较好，则重新设置g 蛔的索引号；根据方程( 2 3 ) 、 ( 2 2 ) 变化粒子的速度和位置。图2 1 给出了算法的具体流程 图2 1 基本粒子群优化算法流程图 5 宁夏大学硕l ：论文第二章粒了群优化算法概述 曼詈鼍曼鼍曼曼皇曼曼 _ 一m 一一i i i； 一一一i 一一 ；i l l 鼍皇量曼曼曼皇曼甍曼曼舅 2 1 3 参数分析 粒子群算法参数包括：群体规模肌，惯性权重w ，加速常数c 。，c ：，最大速度y o ，最大代 数g 一。 ( 1 ) 最大速度 决定当前位置与最好位置之间的区域的分辨率( 或精度) 。如果太高，粒子可能会 飞过好解；如果y o 太小，粒子不能在局部区域外进行足够的探索，导致陷入局部优值。 该限制有三个目的： 1 ) 防止计算溢出； 2 ) 实现人工学习； 3 ) 决定问题搜索空间的力度。 ( 2 ) 权重因子 在粒子群算法中有三个权重因子：惯性权重w ，加速常数c 。，c ：。惯性权重w 使粒子保持运 动惯性，使其有扩展搜索空间的趋势，有能力探索新的区域。加速常数c 。，c ：代表将每个粒子推 向p 蛔和g 蛔位置的统计加速项的权重。低的值允许粒子在被拉回之前可以在目标区域外徘徊， 而高的值则导致粒子突然的冲向或越过目标区域。 如果没有后两部分，即c = c 2 = 0 ，粒子将一直以当前的速度飞行，直) u ) i u 达边界。由于 它只能搜索有限的区域，所以很难找到好解。 如果没有第一部分，即m ，= 0 ，则速度只取决于粒子当前位置和其历史最好位置 p 蛔和g 蛔，速度本身没有记忆性。假设一个粒子位于全局最好位置，它将保持静l = 。而其它 粒子则飞向它本身最好位置p 胁和全局最好位置g 胁的加权中心。在这种条件下，粒子群将收 缩到当前的全局最好位置，更像一个局部算法。 在加上第一部分后，粒子有扩展搜索空间的趋势，即第一部分有全局搜索能力。这也使得 w 的作用为针对不同的搜索问题，调整算法全局搜索能力的平衡。 如果没有第二二部分，即c 。= 0 ，粒子没有认知能力，也就是“只有社会( s o c i a l 吣n l y ) ”的 模型。在粒子的相互作用下，有能力到达新的搜索空间。它的收敛速度比标准的更快，但对于 复杂问题，则比较容易陷入局部最优值点。 如果没有第三部分，即c ，= 0 ，则粒子之间没有社会信息共享，也就是“只有认知 ( c o g n i t i o n - o n l y ) ”的模型。因为没有交互，一个规模为历的群体等价丁运行了朋个单个粒子的 运行，因而得到解的儿率非常小。 早期的试验将w 固定为1 0 ，c ，c ：l 古l 定为2 0 ，冈此成为唯一需要调整的参数，通常殴 为每维变化范围的1 0 - 2 0 。 引入惯性权重w 可消除对的需要，因为它们的作用都是维护全局和局部搜索能力的平 衡。这样，当。，增加时，可通过减小w 米达到平衡搜索。而w 的减小可使所需的迭代次数变 小。从这个意义上看，可将v 。i 司定为饵维变量的变化范闱，只对w 进行调节。 对全局搜索，通常的好方法是往前期有较高的探索能力以得剑合适的种子，而在后别有较 高的开发能力以加快收敛速度。为此可将w 设为随时间线性减小，如由0 9 到0 4 。 试验表明，c ，c ：为常数时可得到较好的解，但不一定必须为2 。c l e r c 引入收缩因子k 来 6 宁夏人学硕卜论文第二章粒了群优化算法溉述 保障收敛性 y 搿= 衄v 甜+ c p l r l ( p 讨一x i d ) + 伊2 r 2 ( p 一一x t d ) 】 ( 2 4 ) 式中：k 2 f ：丽2 ，伊2 纯+ 仍，矽 4 。这对应于式( 2 3 ) 中的特殊的参数组合，其中鬈 即一种收矾，p 2 限制的w ，而c l = 却l ，c 2 = 坳2 。 整个求解过程中，惯性权重w 、加速常数c ，和c ：以及最大速度y | 纰共同维护粒子对全局和 局部搜索能力的平衡。这四个算法参数的设置与具体问题密切相关，目前比较常用的方法是针 对具体求解问题，利用充分的试验来确定。 通过对粒子群算法参数效能的统计分析，由方差分析数据可知惯性权重w 、加速常数c 。和c ， 三个参数对算法整体性能的影响都是显著的。而惯性权重w 的作用更为显著，在o 3 w 0 5 的 范围内，能获得比较一致的迭代次数均值，且在此范围内进行更细致的单因子方差分析进一步 证明较小的惯性权重能够提高算法速率。 通过对c ，的单因子方差分析，在1 6 s c 。1 8 范围内具有比较一致的算法迭代次数。c l 对算 法的影响是很小的，这也证明在整个群体搜索空间的过程中，个体加速特性的改变对算法整体 特性的影响是比较弱的。因此在改善算法性能时，c 。不必作为优先考虑的冈素。 通过对单因子方差分析可知，c ，的变化对算法优化效能有显著的影响。这个结果在此证明 了粒子间信息共享与相互合作的重要性。因此，在优化效果要求较高的应用中，应优先考虑调 整c 的设置水平，以改变粒子间相互影响的程度，从而提高每个个体察觉其他个体信念的能力， 实现更好的适应性调整。 2 2 粒子群优化算法的收敛性分析 2 2 1 实验分析 试验表明在算法运行的开始阶段收敛速度极快，运动轨迹呈正弦波摆动，但是到了一定程 度速度就开始减慢甚至停滞。一般来说，当所有粒子速度均为o ，这时即可认定算法已经收敛。 在对复杂的单模态和多模态函数的多组测试实验中可以发现，基本粒子群优化算法中的绝大多 数粒子迭代一千次后速度与0 已经非常接近( 通常可达e 7 ) ，这时算法实际上已经停滞，而此 时通常与已知的全局极值有很大差距，甚至连局部极值也难以达剑。 现在将注意力集中剑种群最优粒子上。在当前时刻，促使最优粒子移动的“动力”是速度 方程中的惯性部分，冈为最优粒子的当前位置与最好位置及种群的最好位置相同。经过这一时 刻，最优粒子在惯性的作用- 卜继续移动，一种可能性是种群找到了一个新的全局最优位置( 其 它粒子有可能成为最优粒子) ：另一种可能性是种群并朱找到更好的位置( 实验发现这种情况在 迭代中后期更可能发生) ，特别是最优位置台：一段时间内没有得到更新，在这段时间内最优粒子 的速度住惯性冈子( w l ，否则算法将无法收敛) 的作h j 卜将迅速降低剑接近0 的值。 在上面的分析中，最优粒子的速度在选代中后期将降低剑接近o 的值，这也使其它粒子较 容易追赶上最优粒子。当所有粒子的位置基本一致时，整个种群将住惯性闪子的作用。卜继续移 动。由于w 0 时，算法将收敛。 8 宁夏大学硕i j 论文第二章粒了群优化算法概述 !mi,=一 一i i i ii 皇曼舅 ( 3 ) 谐振荡 在算法收敛前，如果动态矩阵a 的特征值都是复数，则粒子将在平衡点附近成谐振荡。等 价于方程( 2 1 0 ) 的两个根都是复数，因而有： w 2 + c 2 2 w e 一2 c + 1 0 ( 2 1 1 ) ( 4 ) 锯齿状 当动态矩阵a 的两个特征值( 不论是实数还是复数) 中至少一个含有负的实数部，则粒子 将在平衡点附近呈锯齿状态。这等价于：w o 或w c + l 0 。值得注意的是，锯齿形态可能与 谐振荡一起出现。 2 2 3 收敛性证明 在粒子群算法中，假定p 甜( f ) ，p 州( f ) 是常数， 即p 埘= p ( f ) ，p 一= p 一( f ) 并令 氟= c 。_ ，如= c ：r 2 。由公式( 2 2 ) 和( 2 3 ) 消去速度相关的参数，则： ( f + 1 ) = ( 1 + w 一磊一九) o ) 一( f 一1 ) + 办p 耐+ 九p 一 ( 2 1 2 ) 其中，初始条件为： x f d ( 0 ) = 【厂( 一1 ，1 ) 母r ；v 甜( 0 ) = u ( 一l ，1 ) 1 ，一 ( 2 1 3 ) 【，( 一1 ，1 ) 是【一u 】区间正态分布的随机数。 工讨( 1 ) = 0 一死一九) 工耐( o ) + w x 甜( o ) + 办p 甜+ 以p 一 ( 2 1 4 ) 工甜( 2 ) = ( 1 + w 一办一九) 工_ ( 1 ) 一w x 坷( o ) + 硪p 讨+ 办p 一 ( 2 1 5 ) 公式( 2 1 2 ) 的矩阵形式为： mr rh 工刊 仁旧 公式( 2 1 6 ) 中系数矩阵的特征多项式为： ( 1 一；t x w 一五( 1 + w 一办一九) + ) ( 2 1 7 ) 该特征多项式存在三个根： 丑= l 口耐：兰型车纽 ( 2 1 8 ) 耽：生型警 ( 2 1 9 ) 其中，= 、i o + w - o , 一2 ) 2 - 4 w 。 冈为口，均为公式( 2 1 6 ) 系数矩阵的特征多项式的根，所以公式( 2 1 2 ) 可写为： j 甜( t ) = k l + 足2 口0 + 七3 筋 ( 2 2 0 ) 如果( 1 + w 一死一纠) 2 4 w ，则，口，为实数；如果( 1 + w - - 妒i 一2 ) 2 l 时，熙x ( f ) 不存在，即粒子的轨迹是发散的； 当l 口i i l 且0 绷 脚上的多项式函数优化问题，并将二进制粒子群优化算法( b p s o ) 与局部爬山搜索策略 想结合，给出了一种求解s a t 问题的新算法：基于局部爬山搜索的改进二进制粒子群优化算法( 简 称i b p s o ) 。文献【1 3 】针对全局版粒子群的早熟和局部版粒子群的最优位置信息利用率低的问题， 提出简约粒子群算法，该算法使用速度松弛迭代策略，使粒子不必频繁更新速度，当粒子速度 有利于适应度进一步提高时，就在下一个迭代周期内维持该速度，这有利于提高良好速度信息 的利用率，减小算法的计算量，加快运算的收敛速度。同时，利j j 精英集团策略，使多个最优 位置信息在种群内充分共享，有效地控制了种群多样性，避免了早熟现象，通过大量的数值实 验证明，简约粒子群算法具有更强的寻优能力和更高的稳定性，且计算量比较小。文献【1 4 】针 对惯性权值线性递减粒子群算法( l d w ) 不能适应复杂的非线性优化搜索过程的问题，提出了一 种动态改变惯性权的自适应粒子群算法( d c w ) 。对儿种典型函数的测试结果表明，d c w 算法 的收敛速度明显优- l d w 算法，收敛精度也有所提高。文献【1 5 】提出了一种新的基丁群体适应 度方差白适应变异的粒子群优化算法，a m p s o ) 。该算法在运行过程中根据群体适应度方筹以及 当前最优解的人小来确定当前最佳粒子的变异概率，变异操作增强了粒子群优化算法跳出局部 最优解的能力。对儿种典型函数的测试结果表明：新算法的全局搜索能力有了显著提高，并且 宁夏大学硕f ：论文第二章粒f 群优化算法概述 能够有效避免早熟收敛问题。文献0 0 将自然进化过程中的群体灭绝现象引入微粒群算法。该 混合算法在微粒位置和速度更新之后，按一个预先定义的灭绝间隔重新初始化所有微粒的速度。 实验表明群体灭绝机制可改善微粒群算法的性能，但混合算法会受灭绝间隔的影响，为此可考 虑使用自适应调整间隔的方法。文献 2 2 1 根据耗散结构的自组织性，提出种耗散微粒群优化 算法( d p s o ) 。该算法通过附加噪声持续为微粒群引入负熵，从而使群体不断进化。文献 2 7 】 针对基本p s o 算法存在易陷入局部最优点的缺点，提出了一种新型的p s o 算法一混合变异 粒子群算法。在每次迭代中，符合变异条件的粒子，以多种变异函数方式进行变异，而这些变 异函数被赋予了一定概率，概率的划分取决于特定的优化问题。文献【3 l 】提出了一种改进的粒 子群优化算法，在该算法中，为了增加算法的实用性，将粒子群优化的思想与传统的k 均值算 法相结合，其优点是能够跳出局部极值。实验结果表明提出的方法在聚类准确性和收敛程度方 面都优于传统基于划分的聚类算法。k e n n e d y 和e b e r h a r t 提出了二进制粒子群优化算法p 引，二进 制粒子群优化算法便于表示本身有二进制特性问题。 ( 三) 与其它进化计算技巧结合：文献【2 3 】将进化规划中使用的竞赛选择方法引入p s o 算法。 该混合算法根据个体当前位置的适应度，将每个个体与其它k 个个体相比较，然后依据比较结 果对整个群体进行排序，用微粒群中最好一半的当前位置和速度替换最差一半的位置和速度， 同时保留每个个体所记忆的个体最好位置。虽然混合p s o 算法与基本p s o 算法的差异很小， 但是选择方法的引入使得混合算法成为一种更具开发力的搜索机制。文献【2 4 】将p s o 传统的速 度和位置更新规则与进化计算的繁殖与子种群的思想结合起来