（基础数学专业论文）非线性动态调整惯性权重的粒子群算法.pdf

q 1 参 ! ： ： at h e s i si nf u n d a m e n t a lm a t h e m a t i c s ap a r t i c l es w a r m o p t i m i z a t i o na l g o r i t h mw i t h n o n l i n e a r d y n a m i c a l l ya d ju s t i n gi n e r t i a w e i g h t b yg u ol u y a n s u p e r v i s o r ：a s s o c i a t e p r o f e s s o rz h a n gw e i n o r t h e a s t e r nu n i v e r s i t y m a y 2 0 0 8 一i illii ，。；1曩洚1一1曩? j，。i，。，奄 w虢=|毒x_扩”嚣。锄啭j，鬻；， 誊 。 t f|”撬麓0挚譬t2喾， 女 ： “一。；一川、叫，、， 融 k _ 。孵 争j r 磅。 i独创性声明 本人声明，所呈交的学位论文是在导师的指导下完成的。论文中取得 的研究成果除加以标注和致谢的地方外，不包含其他人已经发表或撰写过 的研究成果，也不包括本人为获得其他学位而使用过的材料。与我一同工 作的同志对本研究所做的任何贡献均已在论文中作了明确的说明并表示谢 = 士! 二 思。 学位论文作者签名：静碧彦 日期：弘厂。召绎1 冈 学位论文版权使用授权书 本学位论文作者和指导教师完全了解东北大学有关保留、学位论文的 规定：即学校有权保留并向国家有关部门或机构送交论文的复印件和磁盘， 允许论文被查阅和借阅。本人同意东北大学可以将学位论文的全部或部分 内容编入有关数据库进行检索、交流。 作者和导师同意网上交流的时间为作者获得学位后： 半年口一年口一年半口两年圈 学位论文作者签名：郝兽竞 签字日期：细碑1 月 l 一-一 -心r： 函 4 j 沁 l - r 形一 ? fr 一 ，；董 一，璃，_配一；， 一 谚 够h一舢 j，吣西 东北大学硕士学位 声，j l 粒子群算法 - & 算法，是一种智 到研究者的高度重视，被广泛应用于许多领域 基本粒子群算法的突出优点是早期收敛速度特别快，缺点是局部搜索能力差，使 得算法后期收敛速度缓慢，求解精度降低另外，不同问题的局部与全局搜索能力的 比例关系是不同的 s h i y 提出的带有惯性权重的粒子群算法，在某种程度上解决了局部搜索能力弱的 问题该算法提高了求解精度目前，设置惯性权重的方法有多种，被广泛应用的是 s h iy 和rce b e r h a r t 提出的线性递减惯性权重( l d w ) 但是，带线性递减惯性权重 的粒子群算法( l d w p s o ) 也有不足：一，算法的收敛速度低这是因为它的惯性权重 值与粒子无关，从而导致粒子搜索过程的智能性降低；二，需要预测最大迭代次数但 实际上在求解一个问题时，最大迭代次数往往是难预测的，它既影响算法的惯性权重 值，又影响算法的适应性 本文提出一种非线性动态调整惯性权重的粒子群算法( n d w p s o ) ，这种非线性动 态调整使惯性权重与粒子有关，它依粒子的适应值的变化自动地调整其大小，从而使 得粒子搜索过程的智能性增加，算法的收敛速度因此有很大的提高此外，该算法也 不需要预测最大迭代次数，适应性强 ， 本文对粒子群算法的四个典型函数进行了仿真实验，测试结果表明，n d w p s o 算 u 法效果很好，搜索结果精度很高，特别是其收敛速度较被广泛应用的l d w p s o 算法有 ， 很大的提高 关键词：粒子群算法；惯性权重；非线性；收敛速度；最大迭代次数 i i 冀， 、 - ) 。 ， 一 一 东北大学硕士学位论文 ap 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 w i t hn o n l i n e a r d y n a m i c a l l ya d ju s t i n gi n e r t i aw e i g h t a b s t r a c t 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 ) w h i c hi sab i o n i ce v o l u t i o n a r ya l g o r i t h mi sf i r s t i n t r o d u c e db yjk e n n d e ya n dr ce b e r h a r ti n1 9 9 5 i ti si n t e l l i g e n c ea l g o r i t h m i t sc o n c e p ti s s i m p l e ，e a s yi ni m p l e m e n t a t i o n , a n dh a sf e w e rp a r a m e t e r a sar e s u l t ，i th a sa t t a c h e dg r e a t i m p o r t a n c ea n dh a sw i d e l yu s e di nm a n ya r e a ss i n c ei ti si n t r o d u c e d t h ee a r l yc o n v e r g e n c es p e e do ft h e e l e m e n t a r yp a r t i c l es w a r mo p t i m i z a t i o ni s p a r t i c u l a r l yf a s t ，b u t i th a sas h o r t c o m i n gt h a tt h ec a p a b i l i t yo fs e a r c hi sb a da n dt h es o l u t i o n p r e c i s i o nr e d u c e s o nt h eo t h e rh a n d ，f o rd i f f e r e n tp r o b l e m s ，t h e r es h o u l db ed i f f e r e n t b a l a n c e sb e t w e e nt h el o c a ls e a r c ha b i l i t ya n dg l o b a ls e a r c ha b i l i t y ai n e r t i aw e i g h t i sb r o u g h ti n t op a r t i c l es w a r m o p t i m i z a t i o nb ys h iy i ts o l v e st h e s h o r t c o m i n go fp a r t i d es w a r mo p t i m i z a t i o n a tp r e s e n t ，t h e r ea r em a n ym e t h o d st oe s t a b l i s h i n e r t i aw e i g h t a m o n gt h e m ，t h es t r a t e g yo fl i n e a rd e c r e a s i n gi n e r t i aw e i g h ti sw i d e l ya p p l i e d w h i c hi sp r o p o s e db ys h iya n dr ce b e r h a r t t h a ti sc a l l e dap a r t i c l es w a r mo p t i m i z a t i o n w i t ht h es t r a t e g yo fl i n e a rd e c r e a s i n gi n e r t i aw e i g h t b u tt h el d w p s o a l g o r i t h ma l s oh a st h e d e f i d e n c y f i r s t l y , t 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 mi sl o w t h ei n e r t i aw e i g h th a s n o t h i n gt od ow i t ht h ep a r t i c l e t h u s ，t h ei n t e l l i g e n c ef a c t o ro ft h ep a r t i c l es e a r c hp r o c e s s d e c r e a s e s e c o n d l y ，l d w p s oa l g o r i t h mn e e d st of o r e c a s tt h em a x i m u mn u m b e r so f i t e r a t i o n s f o rd i f f e r e n tp r o b l e m s ，t h em a x i m u mn u m b e r so fi t e r a t i o n si sd i f f e r e n t ，a n d d i f f i c u l tt of o r e c a s t t h a ta f f e c t st h ea d j u s t m e n tf u n c t i o no ft h ea l g o r i t h m 。t h i sa r t i c l e p r o p o s e s ap a r t i c l es w a r m o p t i m i z a t i o na l g o r i t h m w i t hn o n l i n e a r d y n a m i c a l l ya d j u s t i n g ( n d w p s o ) w h i c hi sr e l a t e dw i t hi nt h ep o s i t i o na d a p t a t i o nv a l u e ， a n dh a s t h ec a p a b i l i t yo fa d j u s t i n gt h es i z ea u t o m a t i c a l l ya c c o r d i n gt oa d a p t a t i o nv a l u e w i t h i n e r t i aw e i g h t ，t h ei n t e l l i g e n tf a c t o ro ft h ep a r t i c l es e a r c hp r o c e s si se n o u g h ，t h ec o n v e r g e n c e r a t eo fa l g o r i t h mi se n h a n c e d ，t h ef o r c a s to ft h em a x i m u mi t e r a t i o n sn u m b e r sc a nb ec a n c e l e d i i i a b s t r a c t 东北大学硕士学位论文 a n dt h ea l g o r i t h mi ss t r o n g e r t h e a l g o r i t h m s o fl d w p s oa n dn d w p s oa r et e s t e d u s i n gf o u rw e l l k n o w n b e n c h m a r kf u n c t i o n ，t h er e s u l ti n d i c a t et h a tt h ea c c u r a c yo fc o n v e r g e n c eo fl d w p s 0i s b e r e rt h a nn d w p s oa n dt h ec o n v e r g e n c es p e e do fn d w p s o i s s i g n i f i c a n t l ys u p e r i o rt o l d w p s 0 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 ；i n e r t i aw e i g h t ；n o n l i n e a r ；t h em a x i m u mn u m b e r so f i t e r a t i o n s i v + ， 1 噜 ， 1 一 1 2 粒子群算法的研究现状2 1 3 本文主要工作。5 第2 章粒子群算法7 2 1 基本粒子群算法7 2 1 1 算法原理。7 2 1 2 基本概念7 2 1 3 数学模型8 2 1 4 算法：9 2 1 5 算法的社会行为分析一1 0 2 i 6 算法特点1 1 2 2 标准粒子群算法。1 2 2 2 1 带惯性权重的粒子群算法1 2 2 2 2 带收敛因子的粒子群算法1 3 2 2 3 算法比较。1 4 2 3 惯性权重的取值范围。1 4 第3 章非线性动态调整惯性权重的粒子群算法1 7 3 1 非线性动态调整惯性权重的粒子群算法1 7 3 1 1 数学模型1 7 3 1 2 算法1 8 3 2 收敛性分析1 9 第4 章仿真2 3 4 1 参数仿真2 3 4 1 1 种群规模2 3 4 1 2 比例系数和学习因子2 6 目录 东北大学硕士学位论文 4 2 算法仿真2 9 第5 章总结与展望3 5 参考文献。3 7 致谢。4 1 3 7 1 、 州 j 奄 ： 碜 i v 6 东北大学硕士学 1 1 粒子群算法的产生背景 自然界中各种生物体，如鱼群、鸟群等，具有一定的群体行为人工生命的主要 研究领域之一就是探索自然界生物的群体行为，构建群体行为模型，在计算机上对生 物的群体行为进行仿真，最终将有效的仿真模型应用到与生物的群体行为相类似的优 化问题的求解上 虽然每个个体具有非常简单的行为规则，但群体的行为却非常复杂，如鸟群， r e y n o l d s 对这种类型的群体行为按以下三条规则进行建模，并基于所建模型，建立起 生物的群体行为算法 。 ( 1 ) 飞离最近的个体，以避免碰撞( 生存性) ； ( 2 ) 尽量与临近伙伴的平均方向一致( 目的性) ； ( 3 ) 尽量朝伙伴的中心移动( 群聚性) f r a n kh e p p n e r 的鸟类模型在反映群体行为方面与其他模型有许多共同之处，不同 之处在于：鸟类被吸引飞向栖息地鸟类遵循生存性、目的性、群聚性三条规则确定 自己的飞行方向( 即飞向目标) 和飞行速度( 实际上每一只鸟都试图停在鸟群中而又不 相互碰撞) ，起初，每只鸟在空中的飞行比较分散，均无特定飞行目标，直到有一只鸟 飞到栖息地，其它鸟也逐渐地跟着飞向栖息地，自然地就形成了鸟群 b o y d 和r i c h e r s o n 在研究人类的决策过程时，提出了个体学习和文化传递的概念 根据他们研究的结果，人们在决策过程中将使用两类重要的信息：一是自身的经验， 二是他人的经验，即人们根据自身的经验和他人的经验进行决策 已经找到栖息地的鸟引导它周围的鸟飞向栖息地，增加了整个鸟群都找到栖息地 的可能性，这符合信念的社会认知性 如何保证鸟降落在栖息地而不降落在其它地方，这就是信念的社会性及智能性 寻找一类问题的解的过程与鸟类寻找栖息地的过程很类似jk e n n e d y 和rc e b e r h a r t 受他们早期对许多鸟类的群体行为研究的启发，借鉴生物学家f r a n kh e p p n e r 的鸟类被吸引飞向栖息地的行为模型，并结合人类决策行为对该模型进行修正，于 1 - 第1 章引言 东北大学硕士学位论文 1 9 9 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 ) 【1 1 1 2 粒子群算法的研究现状 自粒子群算法提出以来，国际上相关领域的众多学者给予了很大的关注和积极的 研究，他们的研究方向大致为算法改进、算法分析以及算法应用 1 算法改进 对粒子群算法的改进主要体现在以下几个方面：( 1 ) 增加惯性权重和收敛因子； ( 2 ) 更新位置和速度状态量；( 3 ) 构造p s o 混合算法；( 4 ) 使用新的进化公式；( 5 ) 新的群体组织结构 ( 1 ) 增加惯性权重和收敛因子 由于对不同问题算法全局搜索能力和局部搜索能力有不同的要求，所以算法全局 搜索能力和局部搜索能力之间平衡关系最好可以调整为此，文献【2 】提出了一种修正 算法，在基本p s o 算法的速度更新公式中引入惯性权重，它决定了粒子先前速度对 当前速度的影响程度，从而起到调节算法全局搜索和局部搜索能力的作用为进一步 提高算法性能，文献 2 l j 丕提出了自适应调整权重策略，即随迭代的进行线性减少惯性 权重的值这使得算法在迭代初期探索能力较强，可以不断搜索新的可行解的区域， 开发能力逐渐增强，使算法可以在可能最优解周围精细搜索这是目前使用最广泛的 p s o 算法形式然而搜索过程是一个非线性的复杂过程，让惯性权重线性过渡的方法 并不能正确反映真实的搜索过程因而，文献【3 】给出了一种用模糊规则动态调整惯性 权重方法，通过对当前最好性能的评价，对惯性权重指定相应的隶属度函数和模糊推 理规则，确定惯性权重的增量实验表明，与惯性权重线性减少的p s o 相比，模糊自 适应有类似或更好的结果文献【4 】给出了一种惯性权重随着迭代代数余弦减少的方 法，也取得了良好的效果文献【5 】提出了一种带收敛因子的粒子群算法实验表明， 与使用惯性权重的粒子群优化算法相比，使用收敛因子的粒子群优化算法有更快的收 敛速度，其实只要恰当选取参数值，两种算法是一致的所以，带收敛因子的粒子群 算法可以看作是惯性权重粒子群算法的特例 ( 2 ) 更新位置和速度状态量 粒子的状态量包括粒子的位置和速度为了刺激群体持续进化，避免群体早熟收 2 誊、 籼 矗 东北大学硕士学位论文 = 第1 章引言 敛和停滞现象，很多研究者指出可依据一定标准为整个群体或某些粒子的状态量重新 一t 。嘻 4 ：。+ ：j 赋值，以维持群体多样性，使算法可持续进化文献【6 】描述的是自适应粒子群算法， 用新粒子替换不活泼粒子，来保持群体多样性如果非全局最优粒子与全局最优粒子 ( 处在全局最优位置的粒子) 之间适应度差值的绝对值连续小于事先定义的临界常数的 次数达到一定值，则该非全局最优粒子就被视为不活泼的粒子，会被一个新的粒子替 换文献【7 】将自然进化过程中的群体灭绝现象引入粒子群算法该混合算法在粒子 位置和速度更新之后，按一个预先定义的灭绝间隔重新初始化所有粒子的速度实验 表明群体灭绝机制可改善粒子群算法的性能，但混合算法会受灭绝间隔的影响为此 可考虑使用自适应调整间隔的方法文献【8 】提出一种带粒子空间扩展的粒子群算法 ( s e p s o ) ，尝试在粒子开始聚集时增加群体多样性由于粒子在聚集时会发生碰撞现 象，所以该算法为每个粒子赋一个半径值，以检测两个粒子是否会碰撞，如果会，则 采取措施让它们弹离文献【9 】根据耗散结构的自组织性，提出一种耗散粒子群算法 ( d p s o ) 该算法通过附加噪声持续为粒子群引入负熵，从而使群体不断进化 ( 3 ) 构造p s o 混合算法 + ， ：畚 7 ， 粒子群算法和其它优化算法的结合是改进研究的热点之一 ，谑 文献【1 0 】将进化规划中使用的竞赛选择方法引入p s o 算法该混合算法根据个体， 当前位置的适应度，将每个个体与其它k 个个体相比较，然后依据比较结果对整个群 体进行排序，用粒子群中最好一半的当前位置和速度替换最差一半的位置和速度，同 时保留每个个体所记忆的个体最好位置虽然混合p s o 算法与基本p s o 算法的差异 很小，但是选择方法的引入使得混合算法成为一种更具开发力的搜索机制文献【1 1 】 将遗传算法( g a ) 中常用的变异引入p s o 算法以预定概率选择变异个体，并以高斯分 布规律确定它们的新位置这样，在算法初始阶段可以进行大范围搜索，然后在中后 阶段通过逐渐减少高斯变异率( 如从1 0 线性减少到0 ) 来改善搜索效率与原有p s o 算法相比，该算法更易跳出局部最优解，因而在求解多峰函数优化问题时表现出了更 好的性能文献【1 2 】将p s o 传统的速度和位置更新规则与进化计算的繁殖和子种群的 思想结合起来，形成具有繁殖和子种群的混合p s o 算法算法以概率p b 标记要进行 繁殖的个体，然后从标记的个体中随机选择两个个体进行交叉，生成子个体，如此反 复，直到被标记的个体均被选择为止交叉算子可以使后代粒子继承父代的优良特性， 3 - 第1 章引言 东北大学硕士学位论文 允许粒子探测两个父代个体之间的搜索空间，拓展了搜索空间，若交叉的两个粒子位 于不同次优峰，则可逃离局部最优解，从而有助于得到更好的解另外，该算法还通 过引入子种群来维持算法解的多样性，避免陷入局部最优解不同子种群之间的相互 作用仅是它们父代个体之间的繁殖，并保证子种群大小恒定 另外，还出现了一些量子p s o 、基于模拟退火的p s o 、自适应p s o 等混合改进算 法，以及求解约束优化问题的p s o 等 ( 4 ) 使用新的进化公式。 文献【1 3 】提出一种多阶段p s o 算法( m u l t i p h a s ep a r t i c l es w a r mo p t i m i z a t i o n ， m p s o ) 其主要思想是将粒子群分组，并让群体在算法不同阶段有不同的暂时搜索目 标，这些目标使粒子移离或移向迄今为止自身或全局的最好位置，可防止粒子陷入局 部最优解文献 1 4 1 提出一种保证收敛的粒子群优化算法( g u a r a n t e e dc o n v e r g e n c e p a r t i c l es w a r mo p t i m i z e r , g c p s o ) 该算法为目前找到的全局最好粒子引入新的速度 和位置更新公式，并在新的速度和位置更新公式中引入一个比例因子，如果算法连续 成功地找到更好的全局最好粒子，则增大比例因子值；如果算法连续失败的次数达到 一定值，则减小比例因子值；如果连续成功或失败的次数未达到指定域值，就保持比 例因子值不变比例因子项的加入使得算法可在围绕全局位置的一个区域内进行随机 搜索，搜索区域大小由参数比例因子值决定实验表明，在使用较小粒子群规模时( 如 1 0 个) ，g c p s o 可得到比原始p s o 更好的或类似的结果在文献 1 5 1 中可找到g c p s o 保证收敛到局部最优值的证明，但是无论g c p s o 还是p s o 均不能保证一定会收敛到 全局最优值 ( 5 ) 新的群体组织结构 社会心理学研究表明，人们的态度、信仰和行为倾向于朝同伴的方向变化，他们 会根据自己所处群体的规范选择自己的意见和行为，即人们通常模拟所在群体的典型 行为和信仰，而不一定是某个特定个体的行为文献 1 6 1 根据此信息提出使用簇分析 改进p s o 算法的性能文献【1 7 】用该算法训练积单元神经网络实验表明当使用恰当 的群体数( 即恰当的划分因子k ) 时，c p s o 的性能优于带惯性权重的p s o 算法，但是 c p s o 有明显的“启动延迟”( s t a r t u pd e l a y ) 问题，即在迭代初期优化速度较慢，当k 值越大时这个问题越明显 4 舡 0 f 尊 收敛性方面，到目前为止，标准粒子群算法只得到一些简单结果 3 算法应用 粒子群算法已有多方面应用 ( 1 ) 神经网络训练：p s o 算法最早应用于人工神经网络的训练中，主要包括3 个 方面的应用：连接权重、网络拓扑结构及传递函数、学习算法 ( 2 ) 参数优化：p s o 已广泛应用于各类连续问题和离散问题的参数优化例如， 在模糊控制器的设计、机器人路径规划、信号处理和模式识别等问题上均取得了不错 的效果 ( 3 ) 组合优化：p s o 已被应用于解决t s p 、v r p 以及车间调度等组合优化问题 ( 4 ) 其他应用：除了以上领域外，p s o 在多目标优化、自动目标检测、生物信号 识别、决策调度、系统辨识以及游戏训练等方面也取得了一定的成果 本节还参考了文献【1 8 2 0 1 3 本文主要工作 本文分五个部分：第一部分介绍粒子群算法产生、研究状况及应用领域；第二部 分将介绍基本粒子群算法，标准粒子群算法，惯性权重取值范围的确定：第三部分将 介绍非线性动态调整惯性权重的粒子群算法；第四部分将对非线性动态调整惯性权重 的粒子群算法中的种群、学习因子、比例系数三个参数的取值进行函数测试，以确定 该算法参数的合理取值范围；对非线性动态调整惯性权重的粒子群算法进行测试，检 验算法的可行性和有效性；第五部分为全文总结 - 5 、乞 | 东北大学硕士学位论文 第2 章粒子群算法 第2 章1 粒子群算法 粒子群算法是对鸟群觅食行为模拟的仿生智能算法，已成功运用在神经网络训练 和函数优化问题上 2 1 基本粒子群算法 2 1 1 算法原理 在粒子群优化算法中，优化问题的每个潜在解都相当于是搜索空间中的一只鸟， 被抽象为没有质量和体积的“粒子 ( p a r t i c l e ) 粒子在搜索空间中以一定的速度飞行， 且速度可以根据粒子本身的飞行经验和同伴的飞行经验动态调整每个粒子都有一个 适应值( f i t n e s sv a l u e ) ，并且知道自己到目前为止的最好位置( p b 黜f ) ( 即个体最优位置) 和当前的位置，这可以看作是粒子自己的飞行经验此外，每个粒子还知道到目前为 止整个群体中所有粒子的最好位置( g b e s t ) ( 即全局最优位置) ，这可以看作是粒子同伴 的经验每个粒子将使用下列信息更新自己的当前位置 ( 1 ) 粒子的当前位置和速度； ( 2 ) 当前位置与自己最好位置之间的距离； ( 3 ) 当前位置与群体最好位置之间的距离 优化搜索就是在这样一个随机初始化所形成的粒子种群中以迭代的方式进行的 2 1 2 基本概念 粒子：指解空问的一个解 种群规模：种群中的粒子数目，而种群是指由粒子组成的集合 粒子速度：指代表解的粒子在一次迭代中的位移 适应度函数：一般是由优化目标所决定的非负函数，用于评价粒子的搜索性能， 指导粒子种群的搜索过程适应度函数的值称为适应值适应度函数值最优( 最小值 或最大值) 的解即为优化搜索的最优解 个体最优位置：指单个粒子从开始到当前迭代为止，搜索到的适应值最优的解在 解空间中所处的位置 7 第2 章粒子群算法东北大学硕士学位论文 全局最优位置：指整个粒子种群从开始到当前迭代为止，搜索到的适应值最优的 解在解空间中所处的位置 2 1 3 数学模型 设在一个n 维空间中，有膨个粒子组成一个群体，其中第f 个粒子在咒维空间里 的位置表示为置一 ，薯：，) ，飞行速度表示为k 一化。，u ：，v m ) ，则粒子群算法的 进化方程可描述为 ( f + 1 ) ；( f ) + c 1 阳n d o ( p 髓( f ) 一( f ) ) + c ：r a n d o x ( p 贴( f ) 一( f ) ) ， ( 2 1 ) x a ( t + 1 ) 一( f ) + ( f ) ( 2 2 ) 在式( 2 1 ) 和( 2 2 ) 中，f = 1 ，2 ，3 ，m ，k l2 ，3 ，n ；o ) ：第f 个粒子在第t 次迭代 时的飞行速度的第k 维分量；风( t ) ：第f 个粒子在第t 次迭代时的最好位置p b e s t 的第 k 维分量；p 肚( t ) ：在第f 次迭代时的群体最好位置g b e s t 的第k 维分量；c 1 ，c 2 ：学习 因子；r a n d 0 ：在( o ，1 ) 上服从均匀分布的随机函数另外，需要对置和k 加以限制， 使得一x sx is x 一，一。sks 1 算法参数的确定 ( 1 ) 种群规模m ：粒子种群规模的选择应视具体问题而定，一般建议设置粒子规 模为2 0 - - 5 0 种群规模的增大可以增加算法的稳定性，但同时也会增加更多的计算时 间 ( 2 ) 粒子的长度咒：问题解空间的维数 ( 3 ) 粒子的最大速度1 2 1 】：粒子的速度在空间中的每一维上都有一个最大速度 限制值，用来对粒子的速度进行控制一般由用户自己设定，是一个非常重要的 参数，如果值太大，粒子也许会飞过优秀区域；另一方面，如果值太小，粒 子可能无法对局部最优区域以外的区域进行充分的探测，即无法移动足够远的距离跳 出局部最优达到空间中更佳的位置，可能会陷入局部最优通常取 一y x 。缸( o 1 4 收敛因子可以有效搜索不同的区域，能得到高质量的解后来研究还发现，设定 最大速度限制可以提高该算法的性能【2 3 】从数学上分析，只要恰当选取参数值，带收 敛因子的粒子群算法与带有惯性权重的粒子群算法是一致的带收敛因子的粒子群算 一1 3 第2 章粒子群算法 东北大学硕士学位论文 法可以看作是惯性权重粒子群算法的特例 2 2 3 算法比较 上述几种都是带有惯性权重的粒子群算法，都较基本粒子群算法有很好的搜索性 s h iy 提出的带有惯性权重的粒子群算法的惯性权重刚开始都取固定常数，后来， s h iy 发现动态的惯性权重有更好的搜索性能 l d w p s o 在运算中线性减少权重c o ，一定程度上会导致搜索后期收敛速度的降 低，从而影响算法的全局收敛性能另外，p s o 在实际搜索过程中是非线性的且是高 度复杂的，致使惯性权重线性递减的策略不能反映实际的优化搜索过程 收敛因子的p s o 算法是以另一种方式逐渐减小缈，一旦算法进入局部极值点领域 内就很难跳出，极易收敛到局部极值点 模糊权重与线性递减权重的p s o 测试结果显示，后者不知道应该降低t o 的合 适时机，而前者自适应模糊控制器不能预测使用什么样的更合适，虽说可以动态地 调节全局和局部搜索能力，但由于须知道c b p e 删。和c b p e 懈等，使得模糊权重法在 实现上较为困难，因而无法广泛使用 2 3 惯性权重的取值范围 惯性权重是粒子群算法中的一个重要参数，为了研究惯性权重取值对粒子群优化 算法的影响，本文对以下粒子群算法的5 个经典测试函数做权重测试 ( 1 ) s p h e e r 函数： ) = t 荟x i 2 ，( - 5 1 2 , 5 1 2 ：) ( 2 ) r o s c n b r o c k i 函：，2 ( z ) 一骞( 1 0 0 ( 一毛2 ) 2 + ( 薯一1 ) 2 ) ，五( - 2 0 4 8 ，2 0 4 8 ) ( 3 ) r a s t r g r i n 函数：s 3 ( x ) - ( 薯2 l o c o s ( z a x i ) + 1 0 ) ，t ( - 5 1 2 ，5 1 2 ) ( 4 ) g d e w a n k 函数：厶( z ) ；面石善1 薯2 一取c 。s ( 啬) + 1 ，毛( 一6 0 0 ，6 0 0 ) 6，schaffer函数：兀o)2瓦兰0三筠00 0 1 一o 5 ，誓( 一加o ，1 。o ) l ( 1 + 1 五+ 矗1 1 1 4 ， 气 b q 每， ， 0 ， 东北大学硕士学位论文第2 章粒子群算法 研究对以上5 个函数优化效果的影响，实验中惯性权重分别取0 1 、0 2 、0 3 、0 4 、 0 5 、0 6 、0 7 、0 8 、0 9 、1 这1 0 个固定的数，c 1 ，c ，均取常数2 ，种群规模为3 0 ，粒子最 大速度一y x 一，y = o 2 ，每个函数运a ? 3 0 次 1 实结验果 ( 1 ) 对于s p h e e r 函数，实验结果表明，除惯性权重取o 8 、0 9 、1 外，其它固 定权重算法都能搜索到最优值0 ，并且从0 1 到o 7 随着惯性权重值的增大，搜索到 最优值的概率也越大，特别是在为0 4 、0 5 、0 6 、0 7 时，达优率达到了1 ，说明此 时算法有较强的局部搜索能力 ( 2 ) 对于r o s e n b r o c k 函数，实验结果表明，给定的固定权重都不能搜索到精确 最优值但是，当为0 4 、o 5 、0 6 、0 7 时，算法搜索到的平均最优值与最优值比较 靠近；当为0 9 、1 时，算法搜索到的平均最优值与最优值相差很大；为0 1 和0 2 时，搜索到的平均最优值略好于0 9 和1 ，但比其他的差 ( 3 ) 对于r a s t r g r i n 函数，实验结果表明，对于取定的这1 0 个固定惯性权重值， 运行3 0 次搜索到的平均最优值都很差相比较而言，取0 5 、o 6 、o 7 、o 8 这四个固 定权重时，搜索得到的平均最优值好于其他几个固定权重值 ( 4 ) 对于g r i e w a n k 函数，实验结果表明，给定的固定权重都没有找到精确最优值 g o 为0 8 、0 9 、1 时搜索得到的平均最优值很差，而其他几个固定权重值得到的平均最 优值与最优值都比较靠近特别是从0 2 到o 7 得到的平均最优值都很好 ， ( 5 ) 对于s c h a f f e r 函数，实验结果表明，对于所有给定的固定权重都找不到函 数的精确最优值除为1 外，当惯性权重取其它几个值时，搜索到的平均最优值几 乎是一样的，接近最优值 2 总结 对上述5 个经典测试函数的测试结果表明，总体上当惯性权重c o 取从o 2 到0 7 这个范围内的数时，函数的搜索性能比较好特别是缈取o 7 时，所有的测试函数得 到的平均最优值都是最好的补充实验结果表明0 7 取0 7 5 结果也不错 因此，惯性权重在0 2 - - 0 7 5 这个范围内，算法的搜索性能较好 1 5 ， 譬，一 0 ， - 一 粒子群算法 s h iy 提出的带有惯性权重的粒子群算法，在一定程度上解决了基本粒子群算法局 部搜索能力弱的问题，并且提高了求解精度目前，设置惯性权重的方法有多种，被 广泛应用的是s h iy 和rce b e r h a r t 提出的线性递减惯性权重( l d w ) 但是，带有线 性递减惯性权重的粒子群算法( l d w p s o ) 也有不足：一，算法的收敛速度低这是因 为它的惯性权重值与粒子无关，从而导致粒子搜索过程的智能性降低；二，需要预测 最大迭代次数但实际上在求解一个问题时，最大迭代次数往往是难预测的，因而它 将影响算法的惯性权重值，以及算法的适应性 对此，本文提出一种非线性动态调整惯性权重的粒子群算法( ap a r t i c l es w a r m o p t i m i z a t i o na l g o r i t h mw i t hn o n l i n e a rd y n a m i c a l l ya d j u s t i n gi n e r t i aw e i g h t ，n d w p s o ) 3 1 非线性动态调整惯性权重的粒子群算法 3 1 1 数学模型 为解决线性递减惯性权重存在的问题，结合上一章对惯性权重取值范围的实验结 果，这里提出一种非线性动态调整惯性权重策略，取 1 0 3 ， ( 3 1 ) 其中f 表示第f 个粒子，f 表示迭代次数；( v g ( f ) ) 表示到第f 次迭代为止，全局最优位 置的适应值；，( 置( f ) ) 表示在第次迭代中，第f 个粒子的适应值 该惯性权重与粒子有关，它依粒子适应值的变化自动调整大小，从而使得粒子搜索 过程的智能性增加 这样经非线性动态调整惯性权重后的粒子速度和位移更新公式变为 ( t + 1 ) = n ) v i k ( t ) + c lx r a n d o x ( p i k ( f ) 一靠( f ) ) + c ：x r a 以d o p 醇( t ) - x 。k ( f ) ) ( 3 2 ) - 1 7 第3 章非线性动态调整惯性权重的粒子群算法 东北大学硕士学位论文 ( t + 1 ) = ( f ) + ( t ) ( 3 3 ) 3 1 2 算法 非线性动态调整惯性权重的粒子群算法： s t e p l ：初始化一群粒子( 群体规模为m ) ，包括随机位置和速度，设定v 一) ，缸， 速度； 芝，乏三芝，位置： 三，x r a i n s x i k 。 ； 、 i z 。缸 苫 s t e p 3 ：对每个粒子，将其当前位置的适应值与其经历过的最好位置p b e s t 的适应值 比较，如果当前位置的适应值优，则将当前位置设置为当前的最好位置p b e s t ；否则， s t e p 4 ：对每个粒子，将其当前最好位置的适应值与全局经历过的最好位置g b e s t 的 适应值比较，如果当前最好位置的适应值优，则将当前最好位置作为全局最好位置 g b e s t ；否则，全局最好位置g b e s t 不变； s t e p 5 ：在每一次迭代中，粒子的速度和位置根据式( 3 2 ) 和式( 3 3 ) 更新，并计算其 s t e p 6 ：检查终止条件是否满足若满足，则寻优结束；否则，将返回s t e p 2 继续搜 该算法的终止条件为相邻两个迭代全局最优位置适应值的差小于一个事先给定的 很小的正数，即i ，( 以( f ) ) 一厂( p 。( f 一1 ) ) 卜这样就避免了设置最大迭代次数，算法的 1 8 一 萝 ， 1 、 曩 1 - “i “9 、， 初始化粒子群 l f 计算每个粒子的适应值 土 根据粒子的适应度值更新个体最优位置与全局最优位置 上 根据式( 3 2 ) 和( 3 3 ) 更新粒子的速度和位置 ， 乇= ：= 、 n 弋：少、 。j 上y 输出结果 图3 1 非线性动态调整惯性权重的粒子群算法流程图 f i g 3 1t h ep r o c e s sc h a r to ft h ep a n 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 mw i t hn o n l i n e a rd y n a m i c a l l y a d j u s t i n gi n e r t i aw e i g h t 3 2 收敛性分析 为分析非线性动态调整惯性权重的粒子群算法的收敛性，这里首先分析带有惯性权 重的粒子群算法的收敛性 定义3 1 设粒子群中任意粒子f 在f 时刻的位置为五( t ) ，x 为搜索空间内任意给 定的位置，若 l i m 。x i ( t ) = x ， f + 则称粒子f 收敛，且收敛到z 该定义表明，粒子的收敛是指粒子最终停留在搜索空间内某一位置 一1 9 由于算法的速度更新公式中的第二项和第三项