（计算数学专业论文）微粒群优化算法的改进及其应用.pdf

摘要 粒子群优化算法是智能优化算法的典型代表，它的特点是简单、收敛速度快，所需领域知识 少，且可用于求解大部分的优化问题，并在经济与工程实践中表现出巨大潜力，所以已被广泛应 用于神经网络、模糊系统控制、模式识别等多个领域。 本文介绍了粒子群优化算法的概况，针对粒子群优化算法参数的动态特性以及算法早熟收 敛、后期振荡现象等问题，提出了一些粒子群算法中惯性权重的改进策略，构造了几个性能较好 的基于粒子群优化的混合智能算法。 首先，提出了三种动态改变惯性权重的策略。一是利用了适应度聚度和空间位置聚度，引入 一个自适应惯性权重，结合了速度松弛迭代策略，构造了一种带有速度松弛迭代策略的白适应粒 子群优化算法；二是利用适应值函数的变化来动态改变惯性权重，产生了另外一个自适应粒子群 优化算法；三是利用种群分布熵和粒子聚集度，构造了一个自适应惯性权重，由此来增强粒子群 优化的全局搜索能力。从典型函数的仿真试验数据中可以得出，这三种自适应惯性权重的粒子群 优化算法均能有效克服带有固定权重和线性权重粒子群算法的不足，并且提高了算法的收敛速度 和精度，提高了算法的全局寻优能力。 其次，将模拟退火策略嵌入粒子群优化算法中，构造出混合粒子群优化算法。当算法陷入局 部解时，融合模拟退火策略可使该算法跳出局部极小，从而提高全局寻优能力。通过典型的函数 测试表明，此种混合粒子群优化算法的性能都优于带线性递减权重的基本粒子群优化算法。 第三，提出求解o - l 背包问题的融合贪婪算法的混合粒子群优化算法和提出求解旅行商问题 的融合模拟退火策略的粒子群优化算法，使所得到的结果都优于求解该问题的标准粒子群优化算 法。 关键词：智能计算，粒子群优化，全局优化，贪婪算法，模拟退火算法 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 ) a s t y p i c a lr e p r e s e n t a t i v eo fs w a l t i ii n t e l l i g e n c e o p t i m i z a t i o ni 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 s ，a n de a s yi ni m p l e m e n t a t i o n d u et o i t sf a s tc o n v e r g e n c es p e e da n da d v a n t a g e so f n e e d i n gl e s si n f o r m a t i o no ft h ep r o b l e m s ，i t s 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 s o ，i th a sb e e nw i d e l ya p p l i e di nm a n y o 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 ，蛔s y s t e mc o n t r o la n d p a t t e r nr e c o g n i t i o n t h 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 o f 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 ha st h e d 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 dt h es 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 eb e t t e rt h a nt h eb a s i cp s oa r ep r e s e n t e di n0 1 1 1 w o r k f i r s t , t h r e ek 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 b a s e do nf i m e s s v a l u ea g g r e g a t i o nd e g r e ea n ds p a c ep o s i t i o na g g r e g a t i o nd e g r e e ，an e wp a r t i c l es w a r n lo p t i m i z a t i o n a l g o r i t h mw i t hr e l a x a t i o nv e l o c i t y - u p d a t es t r a t e g ya d a p t i v ei n e r t i aw e i g h ti sp r o p o s e d a na d a p t i v e i 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 sv a l u ei s p 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 t a d a p t i v e l ya n dd y n a m i c a l l y w eg e ta n o t h e ra d a p t i v ep 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 mw i t h p o p u l a t i o n - d i s t r i b u t i o n - e n t r o p ya n ds p a c ep o s i t i o na g g r e g a t i o nd e g r e e t h en u m e r i c a lt e s ts h o w st h a t t h et h r e ek 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 tc a l lo v e r c o m et h ed i s a d v a n t a g e so ft h ef i xi n e r t i a w e i g h ta n dt h el i n e a rw e i g h t ，i m p r o v et h es p e e do fc o n v e r g e n c ea n dt h ep r e c i s i o no fc o m p u t a t i o n a l ， s t r e n g t h e n t h ea b i l i t yo fg l o b a ls e a r c h i n g 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 mo 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 s c o m b i n e dw i t hp s o t h eh y b r i dp s oc 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 n l o nd e f e c t o 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 f g l o b a ls e a r c h i n g w ec a ns e et h a tt h eh y b r i dp s oi sb e t t e rt h a nt h el i n e a r l yd e c r e a s i n gw e i g h tp s of r o m $ o m et y p i c a lf t m c d o m f i n a l l y , c o m b i n e dw i t hg r e e d ys t r a t e g y , an e wh y b r i dp a r t i c l es w a h l lo p t i m i z a t i o ni sp r o p o s e df o r s o l v i n gt h eq u a d r a t i co - 1k n a p s a c kp r o b l e m i no r d e rt ot a c k l et h et r a v e l i n gs a l e s m a np r o b l e m a n o t h e r h y 蜥dp s ow i t hs 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 yn u m e r i c a lt e s tt h a tt h e s et w o a l g o r i t h m sa r em o t 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 tc o m p u t 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 b a lo p t i m i z a t i o n ，g r e e d y a l g o r i t h m ，s i m u l a t e da n n e a l i n g i i i 独创性声明 本人声明所呈交的论文是我个人在导师指导下进行的研究工作及取得的研究成 果。尽我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其他人已经发 表或撰写过的研究成果，也不包含为获得宁夏大学或其它教育机构的学位或证书而使 用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中作了明确的 说明并表示了谢意。 研究生签名：时间：年月 日 关于论文使用授权的说明 本人完全了解宁夏大学有关保留、使用学位论文的规定，即：学校有权保留送交 论文的复印件和磁盘，允许论文被查阅和借阅，可以采用影印、缩印或扫描等复制手 段保存、汇编学位论文。同意宁夏大学可以用不同方式在不同媒体上发表、传播学位 论文的全部或部分内容。 ( 保密的学位论文在解密后应遵守此协议) 研究生签名： 导师签名： 致j 、 昆历 时间：年月日 时i b 1 ：d 多年莎月日 廿午勿 宁夏大学硕 j 论文第，章绪论 1 1 课题的研究背景和意义 第一章绪论 优化技术是一种以数学为基础，用于求解各种经济与工程问题最优解的应用技术。最优化理 论与算法作为一个重要的科学分支，一直受到人们的高度重视，并在科学、经济以及工程领域发 挥着极为重要的作用。另外对于优化算法的改进与创新研究、拓宽算法领域、完善算法体系同样 具有重要作用。因此，优化理论与算法研究是一个同时具有理论意义和应用价值的重要课题。解 决优化问题的算法通常分为确定性和随机性两种。确定性算法如：单纯形法、牛顿法、共轭梯度 法、分枝定界法、动态规划法等u 卫，这些算法是按照函数变化机理进行寻优的，其搜索效率较高， 过程可再现，但寻优结果和初值有关，通常对函数有可导要求，在处理人们所面对的高维、大规 模、非线性、不可微等特性的复杂问题时，很容易陷入局部最优点而无法得到最优化结果。因此 高效的优化技术成为科学工作者的研究目标之一。 随着人类生存空间的扩大以及认识与改造世界范围的拓宽，人类需要对客观世界的规律有更 全面深入的理解，所以人们从生命现象中得到启示，不断寻求、发明了许多智能优化方法来解决 复杂优化问题口5 1 。例如：遗传算法( g e n e t i c a l g o r i t h m ) ，它模拟了生物种群通过遗传和自然选择不 断进化的功能u 7 1 ；人工免疫系统( a r t i f i c i a li m m u n es y s t e m s ) ，它模拟了生物免疫系统的学习和认 知功能汹1 ；蚁群优化( a n t c o l o n y o p t i m i z a t i o n ) 算法，它模仿了蚂蚁群体在路径选择信息传递方面 的行为m 1 ；粒子群优化( p a r t i c l es w a r mo p t i m i z a t i o n ) 算法，其模拟了鸟群和鱼群觅食迁徙中个体 与群体协调一致的机理d 4 “捌；群落选址算法( c o l o n yl o c a t i o na l g o r i t h m ) ，其模拟了植物群落的 形成机制倒，它们都可在合理的时间内逼近复杂对象问题的最优解。这些算法的独特优点和机 制，引起了国内外学者的高度重视并掀起了该领域的研究热潮，且在许多领域得到了成功应用。 在优化领域，由于这些算法构造的直观性与自然机理，被称作为智能优化算法。 粒子群优化( p s o ) 算法是其中较新的一种智能优化算法。它同遗传算法类似，是一种基于迭 代的优化工具，此系统初始化为一组随机解，通过迭代搜索得到最优值。粒子群优化算法同遗传 算法等其他智能优化算法相比，其概念简单、收敛速度快、易实现，并且需要调整的参数少。目 前粒子群算法越来越引起人们的关注，已成为国际上一个新的研究热点。 1 2 本文研究目的和研究内容 1 2 1 本文研究目的 虽然目前对粒子群优化算法( p s o ) 的研究和应用有了许多的成果，但是核心部分的参数选 择仍然有很大争议，许多改进的算法在提高性能的同时，也增加了运算的复杂度，因此粒子群优 化算法在理论上还很不完善，在应用的深度和广度上有待进一步加深和拓展，还存在很多局限性： ( 1 ) 粒子群优化算法主要应用在连续型实数的问题领域中，而离散型变量问题的领域应用很 少。 ( 2 ) 粒子群优化算法收敛速度快，特别是在算法的早期，但也存在着阶段低，易发散等缺点。 宁夏人学硕i ：论文第一章绪论 曼曼舅曼曼曼寰曼! 曼皇曼! ! 曼蔓皇曼曼曼量曼曼曼曼曼曼曼皇曼曼皇曼曼曼曼! 皇mi 一n n l 舅 若加速因子、最人速度等参数太大，粒子可能错过最优解，算法不收敛；而在收敛的情况下，由 于所有粒子都向最优解飞去，所以粒子趋向同化( 失去了多样性) ，使得后期收敛速度变慢， 同时算法收敛到一定精度时，无法继续优化。 ( 3 ) 由于基本粒子群优化算法依靠的是群体之间的合作与竞争，粒子本身没有变异机制，因 而单个粒子一旦受剑局部极值约束后本身很难跳出局部极值的约束。试验指出在粒子群优化算法 的运行初始阶段，收敛速度比较快，运动轨迹呈正弦波摆动，但运行一段时间后，速度开始减慢 甚至停滞。当所有粒子的速度几乎为0 ，此时粒子群丧失了进一步进化的能力，可以认为算法执 行已经收敛。而在许多情况下( 如复杂的多峰值函数寻优) ，算法并没有收敛到全局极值，甚至 连局部极值也未必达到，这种现象被称为早熟收敛或停滞。 对于粒子群优化算法有待于解决的问题有以下几个方面： ( 1 ) 算法分析。粒子群优化算法在实际应用中被证明是有效的，但目前还没给出收敛性、收 敛速度估计等方面的数学证明，已有的工作还远远不够。 ( 2 ) 粒子群拓扑结构。不同的粒子群邻居拓扑结构是对不同类型社会的模拟，研究不同拓扑 结构的适用范围，对粒子群优化算法推广和使用有重要意义。 ( 3 ) 参数选择与优化。参数w , c 。，c ：的选择分别关系粒子速度的3 个部分：惯性部分，社会部 分和自身部分在搜索中的作用。如何选择、优化、和调整参数，使得算法既能避免早熟又能比较 快速地收敛，对工程实践有着重要意义。 ( 4 ) 与其它优化计算方法的融合。如何将其它优化方法的优点和粒子群优化算法的优点结 合，构造出有特色有实用价值的混合算法是当前算法改进的一个重要方向。 ( 5 ) 算法应用。算法的有效性必须在应用中才能体现，广泛地开拓应用领域，也对深化研究 粒子群优化算法非常有意义。 针对粒子群优化算法的以上的局限性和有待解决的问题，本文对基本粒子群优化算法作了一 些改进，以加快算法的收敛速度，提高种群的多样性，从而增强算法全局寻优能力。 1 2 2 本文的内容 本文对粒子群优化算法进行了改进和应用，具体内容如下： 1 主要介绍了粒子群优化算法的背景、意义、研究现状及基本思想， 性和机理，研究粒子群优化中惯性权重地构造。 2 把模拟退火算法中具有突跳性的动态特点，融入到粒子群算法中， 略的混合粒子群优化算法。 3 把粒子群优化算法应用到求解o - l 背包问题和旅行商问题中。 1 2 3 本文的结构 第一章绪论。介绍本文的课题背景、意义，以及本文目的和内容。 第二章粒子群优化算法的概述。 2 以及对算法的动态特 构造融合模拟退化策 宁夏大学硕f j 论文第章绪论 第三章三种动态调整惯性权重的粒子群优化算法。 第四章融合模拟退火策略的混合粒子群优化算法。 第五章粒子群优化算法在离散领域的应用。 第六章研究工作总结及展望。 3 宁夏大学硕 学位论文第一：审粒了群优化算法概述 苎曼皇i i - - _ i i 曼曼曼曼曼曼曼! ! 曼 第二章粒子群优化算法概述 2 1 基本粒子群算法 2 1 1 基本思想与原理 粒子群优化算法【3 】是1 9 9 5 年由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 提出的，是一种集群优化算 法，其起源于对一个简单社会模型的仿真。它是受鸟群群体运动行为方式启发而提出的一种具有 代表性的集群智能的方法。研究者发现鸟群在飞行过程中经常会突然改变方向、散开、聚集，其 行为通常为不可预测，但其整体总能保持一致性，个体与个体之间也保持着最适宜的距离。通过 对类似生物群体的行为的研究，发现生物群体中存在着一种社会信息共享机制，它为群体的进化 提供了一种优势，这也是粒子群优化算法形成的基础。 设想这样一个场景：一群鸟在随机搜寻食物。在这个区域里只有一快食物，所有的鸟都不知 道食物在哪里，但是它们知道自己当前的位置离食物还有多远。那么找到食物的最优策略是什么 呢? 最简单有效的方法是搜寻目前离食物最近的鸟的周围区域。粒子群优化算法从这种模型中得 到启示并用于解决优化问题。粒子群优化算法中，每个优化问题的潜在的解都是搜索空间中的一 只鸟，称之为“粒子”。所有的粒子都有一个由被优化的函数决定的适应值，每个粒子还有一个 速度决定它们飞行的方向和距离。然后粒子们就追随当前的最优粒子在解空间中搜索。粒子群优 化算法初始化为一群随机粒子( 随机解) ，然后通过迭代找寻最优解。在每一次迭代中，粒子通 过跟踪两个极值来更新自己。第一个就是粒子本身找到的最优解，这个解称为个体极值；另一个 是整个种群目前找到的最优解，这个极值是全局极值。另外也可以不用整个种群而是其中一部分 作为粒子的邻居，那么在所有邻居中的极值就是局部极值，用局部极值来代替全局极值。这样根 据是采用全局极值还是局部极值，粒子群优化算法可分为全局版和局部版。 上述思想可抽象为，在一个d 维的目标搜索空间中，由m 个没有体积的粒子组成一个群落， 第i 个粒子表示为一个d 维向量x i = ( 而l ，而2 ，) ，i = 1 , 2 ，m ，即第i 个粒子在d 空间的位置。 将z ；代入一个目标函数就可以计算出其适应值，根据适应值的大小衡量x ；的优劣。第i 个粒子的 “飞翔”速度也是一个d 维向量，记为k = “。，啊2 ，) 。记第f 个粒子迄今为止搜索到的最好 位置为只= ( p n ，p 舶，p ，也称为p 细。整个粒子群迄今为止搜索到的最好位置 名= ( p - l ，p 9 2 ，p 掌d ) ，也称为g 蛔。 k e n n e d y 和e b e r h a r t 最早提出粒子群优化算法采用下面的公式对粒子操作： ，埘( f + 1 ) = v d ( f ) + c l r l ( p 埘( f ) 一x i d ( ，) ) + c 2 ，2 ( ( p ( f ) 一o ) ) 石日( f + 1 ) = ( f ) + v h ( f + 1 ) ( 2 1 ) ( 2 2 ) 其中d = l ，2 ，d ，i = 1 ，2 ，m ，r n 为种群规模；1 ，2 为均匀分布于【o ，1 1 之间的随机数；c l , c 2 为加速 度限定因子，分别调节向全局最优粒子和个体最优粒子方向飞行的步长，合适的取值可加快收敛 且不易陷入局部最优，通常取2 ； i v d i 时，取i v 耐l = v m ，假设搜索空间的d 维定义为 4 j 。夏人学硕 j 学位论文第一章粒了群优化算法概述 皇曼鼍曼曼皇皇曼曼曼m n i , ni i 曼曼曼皇曼曼皇皇曼皂曼曼曼兰! ! 曼曼曼曼兰皇! 曼曼曼 - x d 。，+ 一】，则通常v d 一= 奴d 。，0 1 k 1 0 ；此后，s h i y 又增设了惯性权重因子w ( i n e r t i a w e i g h t ) ，将( 2 1 ) 式改变为： v 耐o + 1 ) = w v 埘o ) + c i ( p 甜( f ) 一x 甜( r ) ) + c 2 ，2 k p 暑d ( f ) 一工讨( f ) j ( 2 3 ) 由( 2 3 ) 、( 2 2 ) 式组成的迭代算法被认为是基本p s o 算法。 式( 2 3 ) 的第l 部分为粒子的先前的速度；第2 部分为“认知( c o g n i t i o n ) ”部分，表示粒 子本身的思考：第3 部分为“社会( s o c i a l ) ”部分，表示粒子问的信息共享与相互合作。 “认知”部分可由t h o m d i k e 的“影响法则( 1 a wo fe f f e c t ) ”的解释，即一个得到加强的随 机行为在将来更有可能出现。 “社会”部分可由b a n d u r a 的代理加强概念的解释。根据该理论的预期，当观察者观察到一 个模型在加强某一行为时，将增加它施行该行为的几率，即粒子本身的认知将被其它粒子所模仿。 2 1 2 算法步骤 粒子群优化算法运行时初始化一群粒子( 群体规模为m ) ，包括随机位置和速度；并根据适 应函数计算评价每个粒子的适应度；接着，将每个粒子的适应值与其经历过的最好位置p 衙的适 应值作比较，如果较好，则将其作为当前的最好位置p 胁；对每个粒子，将其适应值与全局所经 历的最好位置g 蛔的适应值作比较，如果较好，则重新设置g 蛔的索引号；根据方程( 2 3 ) 、( 2 2 ) 变化粒子的速度和位置。图2 1 给出了算法的具体流程。 图2 1 基本粒子群优化算法流程图 5 宁夏夫学硕 ：学位论文第二二章粒子群优化箅法慨述 ! i i i i =o 曼蔓曼曼曼! 曼 2 1 3 参数分析 粒子群算法参数包括：群体规模m ，惯性权重w ，加速常数q ，c ：，最大速度y o ，最大代数 g 一。 ( 1 ) 最大速度 决定当前位置与最好位置之间的区域的分辨率( 或精度) 。如果太高，粒子可能会 飞过好解；如果y o 太小，粒子不能在局部区域外进行足够的探索，导致陷入局部优值。 该限制有3 个目的： 防止计算溢出； 实现人工学习： 决定问题搜索空间的力度。 ( 2 ) 权重因子 在粒子群算法中有三个权重因子：惯性权重w ，加速常数c 。，c ：。惯性权重w 使粒子保持运 动惯性，使其有扩展搜索空间的趋势，有能力探索新的区域。加速常数c 。，c ：代表将每个粒子推向 p 蛔和g 蛔位置的统计加速项的权重。低的值允许粒子在被拉回之前可以在目标区域外徘徊，而 高的值则导致粒子突然的冲向或越过目标区域。 如果没有后两部分，即c 。= c ：= 0 ，粒子将一直以当前的速度飞行，直到到达边界。由于它 只能搜索有限的区域，所以很难找到好解。 如果没有第1 部分，即w = o ，则速度只取决于粒子当前位置和其历史最好位置p 蛔和g 姗， 速度本身没有记忆性。假设一个粒子位于全局最好位置，它将保持静止。而其它粒子则飞向它本 身最好位置p 翮和全局最好位置g 蛔的加权中心。在这种条件下，粒子群将收缩到当前的全局最 好位置，更像一个局部算法。 在加上第l 部分后，粒子有扩展搜索空间的趋势，即第l 部分有全局搜索能力。这也使得w ， 的作用为针对不同的搜索问题，调整算法全局搜索能力的平衡。 如果没有第2 部分，即c 。= 0 ，粒子没有认知能力，也就是“只有社会( s o c i a l - o n l y ) ”的 模型。在粒子的相互作用下，有能力到达新的搜索空间。它的收敛速度比标准的更快，但对于复 杂问题，则比较容易陷入局部最优值点。 如果没有第3 部分，即c ，= 0 ，则粒子之间没有社会信息共享，也就是“只有认知 ( c o g n i t i o n - o n l y ) ”的模型。因为没有交互，一个规模为m 的群体等价于运行了m 个单个粒子的 运行，因而得到解的几率非常小。 早期的试验将w 固定为1 0 ，c i , c ：固定为2 0 ，因此成为唯一需要调整的参数，通常设 为每维变化范围的1 0 0 a - - 2 0 。 引入惯性权重w 可消除对的需要，因为它们的作用都是维护全局和局部搜索能力的平 衡。这样，当增加时，可通过减小w 来达到平衡搜索。而w 的减小可使所需的迭代次数变小。 从这个意义上看，可将 ，一。固定为每维变量的变化范围，只对w 进行调节。 对全局搜索，通常的好方法是在前期有较高的探索能力以得到合适的种子，而在后期有较高 的开发能力以加快收敛速度。为此可将w 设为随时间线性减小，如由0 9 到0 4 。 试验表明，c 。，岛为常数时可得到较好的解，但不一定必须为2 。c l e r c 引入收缩因子k 来保 6 宁夏人学硕 = 学位论文第二章粒了群优化算法慨述 曼曼曼曼皇曼鼍曼鼍曼皇鼍i ii 曼皇曼曼曼! 曼曼! ! 曼曼曼皇曼曼! 曼曼曼! 曼曼曼曼曼舅曼曼 障收敛性 v d = k 【v 耐+ 妒1 1 ( p 耐一x 耐) + 妒2 吃( p 耐一j 甜) 】 ( 2 4 ) ， 式中：k = 广 = r ，伊= 纪+ 仍，妒 4 。这对应于式( 2 3 ) 中的特殊的参数组合，其中k 1 2 一缈一、妒2 4 妒l ii 即一种收仍，妒2 限制的w ，而c 1 = 却l ，c 2 = j 缈2 。 整个求解过程中，惯性权重w 、加速常数c 。和c ：以及最大速度吃。共同维护粒子对全局和局 部搜索能力的平衡。这四个算法参数的设置与具体问题密切相关，目前比较常用的方法是针对具 体求解问题，利用充分的试验来确定。 算法参数分析( 6 3 , 6 1 1 文献用统计分析中的方差分析法对粒子群算法参数效能进行统计分 析，结果表明在算法的可调参数中，惯性权重w 、加速常数c ，和c ：三个参数对算法整体性能的影 响都是显著的。而惯性权重w 的作用更为显著，在0 3 w 0 5 的范围内，能获得比较一致的迭代 次数均值，且在此范围内进行更细致的单因子方差分析进一步证明较小的惯性权重能够提高算法 速率。 通过对c 的单因子方差分析，在1 6 c 。s 1 8 范围内具有比较一致的算法迭代次数。c 。对算法 的影响是很小的，这也证明在整个群体搜索空间的过程中，个体加速特性的改变对算法整体特性 的影响是比较弱的。因此在改善算法性能时，c 不必作为优先考虑的因素。 通过对的单因子方差分析可知，c ，的变化对算法优化效能有显著的影响。这个结果在此证明了粒 子间信息共享与相互合作的重要性。因此，在优化效果要求较高的应用中，应优先考虑调整c ，的 设置水平，以改变粒子间相互影响的程度，从而提高每个个体察觉其他个体信念的能力，实现更 好的适应性调整。文献通过试验结果分析了种群规模、最大速度、惯性权重和加速常数对算 法性能的影响。 2 2 粒子群优化算法的收敛性分析 2 2 1 实验分析 有试验表明在算法运行的开始阶段收敛速度极快，运动轨迹呈正弦波摆动，但是到了一定程 度速度就开始减慢甚至停滞。一般来说，当所有粒子速度均为o ，这时即可认定算法已经收敛。 在对复杂的单模态和多模态函数的多组测试实验中可以发现，基本粒子群优化算法中的绝大多数 粒子迭代一千次后速度与o 已经非常接近( 通常可达e 7 ) ，这时算法实际上已经停滞，而此时通 常与已知的全局极值有很大差距，甚至连局部极值也难以达到。 现在将注意力集中到种群最优粒子上。在当前时刻，促使最优粒子移动的“动力”是速度方 程中的惯性部分，因为最优粒子的当前位置与最好位置及种群的最好位置相同。经过这一时刻， 最优粒子在惯性的作用下继续移动，一种可能性是种群找到了一个新的全局最优位置( 其它粒子 有可能成为最优粒子) ：另一种可能性是种群并未找到更好的位置( 实验发现这种情况在迭代中 后期更可能发生) ，特别是最优位置在一段时间内没有得到更新，在这段时间内最优粒子的速度 在惯性因子( w ，其中，p 可以是p i 或以。所以，p 时可以重新定 义为： p ；。卜! 堡坐! 堕 ( 2 5 )p i 七一= 一z ) ， 。 c i + c 2 通过公式( 2 5 ) 可将等式( 2 3 ) 简化为： 2 v 甜+ c ( p g a m ) 其中c = ( c l + c ：) 2 。从速度与位置更新公式中可以看到粒子的每一维都是独立地变化， 维的影响。不失一般性，算法模型还可以进一步简化为仅有l 维情形： v ( t + 1 ) = 从“f ) + c ( p 一f ) ) 工( f + 1 ) = 工( f ) + “f ) 以上两式写成矩阵形式为： y ( t + 1 ) = a y ( t ) + 却 撕珊= 譬c 耻圈。 在离散时间动态系统理论中，y o ) 是由粒子位置和速度组成的粒子状态， 8 ( 2 6 ) 不受其它 ( 2 7 ) ( 2 8 ) ( 2 9 ) 彳是动态矩阵，它 宁夏大学硕f j 学f 节论文第二审粒了：群优化算泫概述 的性质决定了粒子的行为，p 是外部输入，用来使粒子趋向特定位置。 ( 1 ) 平衡点 平衡点是系统在缺少外部刺激时所保持的一种状态，任何平衡点一定要满足一个显而易见的 条件，在本文就是对于任意t ，满足y ( t + 1 ) = y ( t ) 。对应于公式( 2 9 ) ，应该有x ( t ) = p ，v ( t ) = 0 。 很明显，处在平衡点时所有粒子的速度都应为o ，而且整个粒子群此时应该处在吸引点p 上。 ( 2 ) 收敛域 在初始阶段整个粒子群没处在平衡点，当前的问题是粒子群如何进入平衡状态( 也就是算法 何时收敛) 以及粒子如何在空间中搜索。在离散时间系统理论中，粒子的时间行为取决于动态矩 阵a 的特征值。矩阵a 的特征值d ，p 2 ( 可以是实数也可以是复数) 也就是以下方程的根： e 2 一( w c + 1 ) e + w = o ( 2 1 0 ) 公式( 2 9 ) 的平衡点保持稳定的充要条件是矩阵a 的两个特征值的数量值小于l 。在这种情 况下，粒子群最终将稳定在平衡点处，此时基本粒子群算法将收敛。由公式( 2 1 0 ) 可推导出， 当w o , 2 w c + l 0 时，算法将收敛。如图2 2 ( a ) 所示，收敛域是图中的三角区域内。也 就是说，粒子最终收敛在平衡点位置当且仅当算法的参数选择在图中三角形的区域内。 ( 3 ) 谐振荡 在算法收敛前，如果动态矩阵么的特征值都是复数，则粒子将在平衡点附近成谐振荡。等价 于方程( 2 1 0 ) 的两个根都是复数，因而有： m ，2 + c 2 2 w c 一2 c + 1 0( 2 1 1 ) 相应的谐振荡区域如图2 2 ( b ) 所示。 ( 4 ) 锯齿状 当动态矩阵彳的两个特征值( 不论是实数还是复数) 中至少一个含有负的实数部，则粒子将 在平衡点附近呈锯齿状态。这等价于：w f l x i ( t - l ” ( f + 1 ) = ( t ) ，如果鲰 ( t ) s f ( x i ( t - 1 ) ) 其中【，以) 按式( 2 3 ) 和式( 2 2 ) 相继执行更新粒子速度和位置，然后计算粒子的适应度， 更新粒子的全局最优值和个体最优值。 步骤5 ：根据( 3 2 2 ) 、( 3 2 4 ) 、( 3 2 6 ) ，分别计算h ，只w 。 步骤6 ；将迭代次数t 置为t = t + l ，并执行步骤3 。 步骤7 ：输出当前的全局最优值和它对应的适应值。 3 2 4 数值试验和结果分析 采用经典函数( 见表3 11 ) 来测试a p s 0 1 算法，l d w - p s o 算法和d c w - p s o 算法，在a p s 0 1 算法和d c w - p s o 算法运行试验中，取w = o 4 ，m = o 2 ，粒子数为3 0 ，c l = c 2 = 1 7 ，l d w - p s o 算法运行试验中粒子数为3 0 ，c i = c ：= 1 7 。每个函数d c w - p s o 算法和l d w - p s o 算法分别运行 2 0 次，结果取平均最优适应值( 函数值) ，具体结果比较见表3 1 2 、表3 1 3 、表3 1 4 、表3 1 5 、 表3 1 6 。每个函数分别运行2 0 次，画出每个函数的平均最优适应值( 函数值) 进化曲线图。 1 7 宁夏人学硕i ：学位论文第二三章三种动态调整惯r 丰权露的白适应粒了群优化铮法 表3 1 l 经典测试函数 l o 正( x ) = 【l o o ( 蕾+ 。- g ) 2 + ( 五- 1 ) 2 】，毛e - 5 1 2 ，5 1 2 ，全局极小函数值为0 踊衢蛐数删一o 5 一篇端喃州删嘴翮大函数 1 0 r a s t r i g i n 函数 工( 曲= ( # - 1 0 e o s ( 2 x x , ) + 1 0 ) ，e - l o ，1 0 ，全局极小函数值为0 扭i 酬州础函数z c 功= 志善# 一尊c 。s l 啬f + 毛 - 1 0 0 , 1 0 0 】，全局极小函数值为。 1 0 0 o 1 0 3 5 4 2 3 9 1 。1 0 - 4o 1 0 0 12 5 9 4 8 1 0 40 0 9 1 55 9 6 3 3 1 0 。4 2 0 0 o1 5 0 3 要 1 0 0 c 正5 0 0 0 5 01 0 0 t o 三 订 器 。 量 芷 图3 1 1 石( 力平均最优适应值进化曲线 图3 1 2l ( x ) 平均最优适应值进化曲线 宁夏大学硕l ：学位论文第三尊三种动态湘整惯性杖苣的自适应粒了群优化学法 i o 表3 1 3( 功= 【1 0 0 ( 玉+ l - x 3 2 + ( 葺一1 ) 2 1 ，薯卜5 1 2 ，5 1 2 】平均最优适应值( 函数值) o j 日 o c _ k 表3 1 4 厂( 石) = 0 5 一 s i n 2 ( # + ) 一0 5 百而而面i 歹 五，五【- 1 0 ，1 0 】平均最优函数值 。 三 g 譬 s c 图3 1 3a ( x ) 平均最优适应值进化曲线 图3 1 4 五( 工) 平均最优适应值进化曲线 1 9 宁夏人学硕卜学化论文第i 审i 种动态渊整惯性权蕈的 j 适应粒了群优化算法 1 0 表3 1 5 ( j ) = ( # - 1 0 c o s ( 2 n x i ) + 1 0 ) ，工，卜1 0 ，l o 】平均最优适应值( 函数值) 1 1 01 0 i i 表3 1 6 删2 志善# 一珥倒“墨 - 1 0 0 , 1 0 0 ，_ 平均最优适应值涵数值 迭代 次数 l d w 巾s od c w p s oa p s 0 1 平均晟优适应 值 最小值 平均最优 最小值 适应值 平均最优 最小值 适应值 1 0 00 7 1 2 15 9 2 4 9 1 0 7o 0 0 0 85 2 2 3 7 1 0 r 61 0 2 5 5 1 0 73 5 3 5 0 1 0 母 。 三 g 器 暑 芷 酏5 几) = 而1 著1 0 乒舆c 。蚓+ 薯 - 1 0 0 , 1 0 0 】，平均最髓应值进化曲线 。j 。夏大学硕f j 学化论文第i 章二i 种动态调整惯件权露的自适心粒了群优化算法 表3 1 73 种算法测试函数迭代5 0 0 次的平均c p u 时间 a p s o i 与l d w - p s o 、d c w - p s o 算法比较，图3 1 1 3 1 5 可以看出，a p s 0 1 算法比较稳定， 收敛速度和收敛精度优于l d w - p s o 算法和d c w - p s o 算法，而且在所有迭代次数中，取得的平 均最小值都优于l d w - p s o 算法和d c w - p s o 算法。从表3 1 7 可以看到，在五个函数中，每个函 数迭代5 0 0 次所用的平均c p u 时间示- a p s o l 算法所用的平均c p u 时间大约是d c w - p s o 算 法所用的平均c p u 时间的一半，a p s 0 1 算法大大减小了计算量，加快运算的收敛速度，提好了 算法的性能。 3 3 自适应惯性权重( i i ) 3 3 1 自适应惯性权重策略( 1 1 ) 的描述 大量试验证明，粒子群优化算法无论是早熟收敛还是全局收敛，粒子群中的粒子都会出现“聚 集”现象。要么所有粒子聚集在某一特定位置，要么聚集在某几个特定位置，这主要取决于问题 本身的特性以及适应度函数的选择。粒子位置的一致等价于各粒子的适