（电工理论与新技术专业论文）改进的粒子群优化算法及应用研究.pdf

重庆大学高校教师硕士学位论文 英文摘要 a b s t r a c t p a r t i c l es w a r m o p t i m i z a t i o n i sa p 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 e s e a r c h o p t i m i z a t i o nt e c h n i q u e a sak i n do f 刚啪i n t e l l i g e n c e ，p s o ，s i m p l ei np r i n c i p l e s ， f e wi np a r a m e t e r s , f a s ti nc o n v e r g e n c er a t ea n ds oo n , h a sp r o v e nt ob eap o w e r f u l g l o b a lo p t i m i z a t i o nm e t h o da n ds h o wg r e a tp o t e n t i a li np r a c t i c e b u tn e i t h e rt h e t h e o r e t i c a la n a l y s i sn o ra p p l i c a t i o ni sn o tc o m p l e t e l yn l a t i l 舷l 钮v m gm a n yq u e s t i o n s t 0b er e s e a r c h e d t o d a y , i m p r o v e m e n t so fp s o 自e q l 】e 妇t l ya d o p tm i x e da l g o r i t h m so i k eq 蚯m i z c d c o m b i n a t i o no f 誉触a l g o r i t h r 璐a n dp s o ) , w h i c hi m p r o v e , t h ep e r f o r m a n c eo ft h e a l g o r i t h n l ，y e tm a k e st h ea l g o r i t h mm o l ec o m p l e x t h e 础o r e t h ec h o i c eo f p s oa l g o r i t h m b a s e do no p t i m i z a t i o no f o p e r a t i o n a ld m r a c t e r i s t i c sf r o mi t so w n a n a l y s i s , w h i c hi m p r o v e s t h eo v e r a l lp c d 0 i m a r 娣o ft h ea l g o r i t h mt of i n das i n g l ep s o a l g o r i t h m , i sm i l i n g f i l l b a s e do nt h ef i m d a m e m a li s s u eo fp s oa n dp s ob e h a v i o ra n a l y s i s , an e wa l g o r i t h mi s p r o p o s e di nt h ec o l l r s eo f0 1 戚埘l d 茁t h ev a r i a n c ew i t ht h ei d e a l so f t h ep a r t i c l e st o d e t e r m i n et h eb e s td y l m m i cc h a n g ei n e r t i aw e i g h t , t h ep a r t i c l es w a r mo p t i i i l i z 碰o n a l g o r i t h me l l h a l a e , et h ea b i l i t yt oj u m po u to fal o c a lo p t i m a ls o l u t i o n i tc a nl f f f o c t i v d y p r e v e n tp r e m a t u r ec o n v e r g e n c e , m a k i n ga l g o r i t h m e a s i e ra n d e a s yt om a k e i na d d i t i o n , t h es t u d yo f p s oa l g o r i t h ma p p l i c a t i o ni sa l li m p o f t a mr e s e a r c hf i e l d n l i s p a p e rw i l li n t r o d u t xt h ep s oa l g o r i t h m sa p p l i c a t i o ni nt h ed e s i g no f t h eu n i v e r s i t yl i b r a r y d e c i s i o ns u p p o r ts y s t e m b o o kp u r c h a s eq u a l i t ya f f e c t st h eq u a l i t yo fl i b r a r yc o l l e c t i o nc o n s t r u c t i o n d i r e c t l ya n dl a r g e l yd e t e r m i n e st h eo v c 删us 口v i c el e v e lo fu n i v e r s i t yl i b r a r i e s i nr e c e n t y e a r s , l i b r a r yp r o c u r e m e n ts u b j e c t i v eb l i n d n e s sh a sc a u s e dt h ew a s t eo f r e s o 嘲i nv i e w o ft h i ss i t u a t i o n , t h ec o m b i n a t i o no fa r t i f i c i a li n t e l l i g e n c et e c h n o l o g y , b o o kt h e o r e t i c a l k n o w l e d g eo fc o m p u t e rt e c h n o l o g ya n dd e c i s i o ns u p p o r ts y s t e m t o s l 单p 矾t h e e s t a b l i s h m e n to ft h eh l x a r yp o l i c yi sv e r yn 龋哪b o o kp u r d m e s , i no r d e rt om a k e l i m i t e df u n d st om e e tt h en e e d so fr e a d e r s , b u d d i n gq u a l i t yb o o k sp u r c h a s ed i s i o n s u p p o r ts y s t e m ，i sv i t a li nd e s i 豳h i g hq i m 晦托a d e 绉d e m a n da n df l o w 剃y s i s a l g o r i t h mu t i l i t ym o d e l o nt h eg r o u n do f r e a d e rd e m a n d sa n dd e m a a da n a l y s i sm o d e l b a s e d0 1 1t h ec l a s s i f i c a t i o n , i m p l i c i td e m a n dm o d e lt h ed u m p s t e r - s h a f e r t h e o r yi su s e dt o s y n t h e s i z ev a r i o u se s l i m a t e sa n dt og i v eas e l e c t i o ne v a l u a t i o nm o d e lt on 鞠妇sd e m a n d , t h e nr o - h s eo fm a t h e m a t i c a lm o d e l i n g , a n de s t a b l i s ht h eq u a n t i t yo fb o o k sa v a i l a b l ef o r i i 重庆大学高校教师硕士学位论文 英文摘要 p u r c h a s ei nd r c n l a t i o nx n e c t e c lt h ee f f e c t i v e n e s so f 也em a t h e m a t i c a lm o d e la tl a s t , t h e a l g o r i t h mw a sd e s i g n e db a s e do nt h em o d e lp s oa l g o r i t h m k e y w 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 a m e w ra d a p t a t i o n , c i r c i l l a t i i l ga v a i l d u p l i c a t ea m o u n to p t i m u l l ld e c i s i o n i i i 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作及取 得的研究成果。据我所知，除了文中特别加以标注和致谢的地方外，论文 中不包含其他人已经发表或撰写过的研究成果，也不包含为获得重废太堂 或其他教育机构的学位或证书而使用过的材料。与我一同工作的同志对本 研究所做的任何贡献均已在论文中作了明确的说明并表示谢意。 学位论文作者签名：张节乞 签字日期：劢d 7 年1 月堀日 学位论文版权使用授权书 本学位论文作者完全了解重庆太堂有关保留、使用学位论文的 规定，有权保留并向国家有关部门或机构送交论文的复印件和磁盘，允许 论文被查阅和借阅。本人授权重麽去堂可以将学位论文的全部或部 分内容编入有关数据库进行检索，可以采用影印、缩印或扫描等复制手段 保存、汇编学位论文。 保密() ，在年解密后适用本授权书。 本学位论文属于， 不保密( v ) 。 ( 请只在上述一个括号内打“4 ”) 学位论文作者签名：2 移举乞 签字日期：叼年f 月鹋日 导师签名：包溺 签字日期：加口7 年广月歹日 重庆大学高校教师硕士学位论文 1 绪论 1 绪论 1 1 研究的背景 1 1 1 优化问题及其特点 优化技术是一种以数学模型为基础，用于求解各种工程问题优化解的应用技 术，它作为一个重要的科学分支一直受到人们的广泛重视，并在诸多工程领域得 到迅速推广和应用，如系统控制、人工智能、模式识别、生产调度、计算机工程 等等。实现控制过程和决策的最优化，对提高生产效率与效益、节省资源具有重 要的作用，同时，优化方法的理论研究对改进算法性能、拓宽算法应用领域、完 善算法体系同样具有重要作用因此，优化理论与算法的研究是个同时具有理 论意义和应用价值的重要课题【1 1 鉴于实际工程问题的复杂性、约束性、非线性、建模困难等特点，寻求具有 智能特征的算法已成为有关学科的一个主要研究目标和引人注目的研究方向。粒 子群算法( 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 优化算法运用于图书采购优化决策 1 1 2 研究的应用背景及意义 图书采购为高校图书馆服务工作提供物质基础，图书采购的质量直接影响了 馆藏质量，从而在很大程度上决定着高校图书馆的整体服务水平目前，高校图 书馆的采访决策存在两种不同观点【2 l ，一是学科专家选书制度，这一观点认为学 科专家选书制度为世界上最先进的决策模式，是发展的必然方向。如美国、德国 等国家高校图书馆的选书决策都要求既有学科专长又有图书馆学位的高级馆员担 当；二是教师选书制度由教师选购专业性强的文献弥补选书人员的知识缺陷， 提高文献在教学、科研中的作用这两种决策方法都有其优点，但在图书馆的具 体实践运作过程中也遇到不少困难：首先图书馆选书人员的素质较发达国家要 低，具备理想知识结构的人员为数尚少，另外教师大部分精力和专业有限，且对 图书馆馆藏结构及经费配置缺乏全面的了解；最重要的是，这两种方式过分依赖 决策者个人的学识、智慧和经验进行决策，容易造成人为的资金浪费及文献利用 率低下近年来，图书馆图书采购的主观盲目性造成的资源浪费和资金的综合效 益最大化之间的冲突日益明显鉴于这种情况，许多图书馆成立了选书委员会、 学术委员会等组织，且从多渠道收集图书采购信息、读者需求信息，但由于没有 一个科学、客观的计算、分析手段，无法得到合理的决策信息，因而将决策支持 重庆大学高校教师硕士学位论文 1 绪论 系统引入图书采访工作中，将决策过程中的定量计算与定性分析进行有机的结 合，以使有限的图书采购资金综合效益最大化的呼声日益高涨。“高校图书馆有 必要建立采访决策支持系统，以帮助采访人员更好地完成文献采访工作，在这种 需求的拉动下，结合人工智能技术、计算机技术和图书采访理论等知识建立决策 支持系统( d s s ) 辅助图书馆决策就显得十分必要郴l 。采访决策支持系统的研究 和实现为图书馆图书采购、经费分配提供了科学的参考和决策依据，使得采购工 作更趋合理性和科学性，既能最大限度地满足教学和科研的需要，又能在一定程 度上避免盲目购书的现象，在大部分高校还比较依赖主观选书的今天，有较大的 经济和社会效益。 本研究是重庆工商大学校内项目基于多实例的图书采购决策模型的深化 和延续。 1 2 国内外研究现状 由于粒子群算法本身具有的概念简单性和易于实现性，在短期内得到很大发 展，迅速引起了国际上相关领域众多学者的广泛关注和研究，并在很多领域得到 应用。目前，粒子群优化算法的研究大致可分为以下几个领域：算法的原理研究、 算法的改进研究以及算法的应用研究 ( 1 ) 粒子群优化算法的原理研究 即粒子之间是如何相互作用与运动而最终达到全局优化的，与相对鲜明的生 物社会特性基础相比，p s o 的数学基础显得相对薄弱，缺乏深刻且具有普遍意义的 理论分析因此，对数学基础的研究非常重要，如粒子运动轨迹研究、算法收敛 性研究和粒子群分布与演化研究等等。文献【4 】利用微分方程和差分方程为工具对 单个粒子的运动轨迹进行研究发现：单个粒子其轨迹是各种正弦波的随机的叠加 组合关于粒子群算法的收敛性研究比较多的集中在一些简化条件下的结果，采 用的主要工具是动态系统理论。其它还有采用集合论的方法来研究此问题啊文献 【6 】采用f o l c k e r - p l a n c k 方程和l a n g e v i n 方程对粒子群算法的运行机理有比较深入 的分析研究。 ( 2 ) 粒子群优化算法的改进研究 粒子群优化算法的改进研究可以说是p s o 算法研究的最重要的分枝，其内容 十分庞大，但大多数改进方案都基于与其它优化算法的结合 p s o 算法由于其简单和解决问题的有效能力而被应用到很多的领域。但在实 际应用当中，也表现出了一些不尽人意的问题。这些问题中最主要的是它容易产 生早熟收敛、局部寻优能力较差等实际上这些缺点也是几乎所有随机算法的弊 病梯度法、爬山法、直接搜索法、模拟退火算法等一些优化算法却具有很强的 2 重庆大学高校教师硕士学位论文 1 绪论 局部搜索能力，而另一些含有问题域相关知识的启发式算法的运行效率也比较 高。可以说，大多数优化方法的全局搜索能力和局部搜索能力单靠一种算法往往 无法得到有效利用与平衡，从而影响了算法的求解精度和效率。因此，如何合理 结合不同算法的优点来构造新算法，对于实时性和优化性同样重要的工程领域， 具有很强的吸引力自然地，人们想到了混合两种算法或者多种算法在一个模型 当中，尽量发挥各个算法的优点，从而形成了一个研究混合算法的方向因此， 在p s o 算法搜索过程中融合其他优化方法的思想，构成混合p s o 算法成为p s o 算法改进的最常见的思路。 a n g e l i n a 将选择算子引入p s o 中，选择每次迭代后的较好粒子复制到下一 代，以保证每次迭代的粒子群都具有较好的性能，这种算法对某些单峰函数效果 良好1 7 j 文献【8 】在粒子群每次迭代后，按几率在粒子间交换各维，通过交叉来生 成更优秀的粒子，算法对某些多峰函数效果较好。h i g a s h i 等人分别提出了自己的 变异算法，基本思路均是希望通过引入变异算子跳出局部极值点的吸引，从而提 高算法的全局搜索能力，得到较高的搜索成功率网。高鹰等人则引入免疫机制的 概念，提高粒子群的多样性和自我调节能力，以增强粒子的全局搜索能力i 。 b a s k a r 等人提出了自己的协同算法，通过使用多群粒子分别优化问题的不同维， 多群粒子协同优化等办法来对基本算法进行改进尝试【l i 】 除以上的混合算法之外，还出现了量子p s o 、模拟退火p s o 、耗散p s o 、自 适应p s o 等混合改进算法，也有采取与基于梯度的优化方法相结合的办法。 大多数混合粒子群算法，相对于标准粒子群，可以说在性能上都有不同程度 的提高，但是，也存在一些问题，如，其算法的理解复杂度和实现复杂度往往较 高，从而对算法的工程应用造成了较大的障碍因此，从工程应用的角度分析， 如何合理选择惯性权重等参数，使得算法既能避免早熟又能比较快速地收敛，又能 有效地控制算法的理解复杂度和实现复杂度，对工程实践有着重要意义 ( 3 ) 算法应用研究 算法的有效性必须在应用中才能体现，尽管p s o 算法已经在一些领域得到了 很好的应用，但是在其他一些应用领域都还处于研究阶段，因此，广泛地开拓的 应用领域，也对深化研究算法非常有意义。 p s o 的优势在于算法的简洁性，易于实现，没有很多参数需要调整，且不需 要梯度信息。所以p s o 一经提出就引起了广泛的关注，其应用已经扩展到很多领 域：如，复杂多峰非线性函数的优化 t 2 j 3 j 4 , 1 16 ，朔，神经网络的权值训练 i i g , 1 9 , 2 0 , 2 n ，电力系统的优化茹州，等等 函数优化应用 3 重庆大学高校教师硕士学位论文1 绪论 许多实际的工程问题本质上是函数优化问题或者可以转化为函数优化问题进 行求解，对于函数优化已经有一些成熟的解决方法如遗传算法等，但是对于超高 维、多局部极值的复杂函数而言，遗传算法往往在优化的收敛速度和精度上难以 达到期望的要求。 a n g d i n e 经过大量的实验研究发现，粒子群优化算法在解决一些典型的函数 优化问题时，能够取得比遗传算法更好的优化结果【埘。这就说明粒子群优化算法 在解决实际问题时同样具有很好的应用前景。 通过对p s o 算法的研究可以发现，与遗传算法类似，应用p s o 解决优化问 题有两个重要步骤：问题解的编码和适应性函数的选择。应用p s o 算法进行函数 优化不仅可以避免选择、交叉、变异等进化操作，而且可以大大简化上述两个步 骤。s h i 与e b e r h a r t 的实验证明，对大多数的非线性标准测试函数，p s o 在收敛 速度和解的精度上均较遗传算法有一定的改善【”l 。 人工神经网络训练应用 人工神经网络是模拟大脑分析过程的简单数学模型人工神经网络技术根据 所掌握的生物神经网络机理的基本知识，按照控制工程的思路和数学描述方法， 建立相应的数学模型，并采用适当算法，有针对性地确定数学模型的参数( 如连接 权值、阙值等) ，以便获得某个特定问题的解。目前已成功用于解决组合优化、故 障诊断、模式识别等问题。 采用一定的优化算法进行神经网络的训练能够提高神经网络的自学习和自组 织的能力。目前，优化算法对神经网络的训练主要集中在网络连接权重和网络拓 扑结构上。神经网络的训练问题属于超高维的优化问题。常用的反向传播( b p ) 算 法难以克服局部最优问题，而遗传算法由于其复杂的进化操作，优化速度缓慢。 研究表明，p s o 是一种很有潜力的神经网络训练算法，p s o 搜索速度较快而且可 以得到比较好的优化结果，克服了上述两种算法的缺点t 嘲 粒子群优化方法在电力系统中的应用 粒子群优化方法在电力系统中主要应用于电力系统规划、运行与控制等领 域。文献1 2 2 j 研究了p s o 算法在输电网络扩展规划中的应用，以投资回收效益、 设备成本( 包括传输线、铁塔、变电站、开关设备、变压器、补偿设备等) 和电 能损耗费用之和最小为目标函数，建立了扩展输电网的最小费用模型，设计了基 于p s o 的求解算法文献1 2 3 1 综合考虑了诸如发电机组的爬坡率限制、禁止运行 区域和系统网络损失等更多的非线性约束条件，使应用p s o 算法解决的负荷经济 分配问题更接近于实际电力系统的运行情况。文献1 2 4 将p s o 算法应用于电力系 统负荷模型的参数辨识中，将其与遗传算法进行对比，得出了p s o 算法在计算时 间、全局优化性方面均比遗传算法有明显优势的结论。 l 重庆大学高校教师硕士学位论文 1 绪论 p s o 在系统设计、分类、模式识别、信号处理、机器人技术应用、决策制 定、模拟和证明等领域的应用，大量的学者和工程技术人员也进行了一系列的研 究。 1 3 研究内容 本文主要研究内容如下： ( 1 ) 粒子群优化算法的改进研究 p s o 算法和许多其它优化算法一样，也存在一些控制参数，如何选取这些参 数，对提高算法的收敛速度和寻优精度致关重要特别是对于一些复杂的优化问 题，它们往往要求算法的运算复杂度不能太大，算法迭代次数尽可能少，但目前 许多改进粒子群算法，其算法的理解复杂度和实现复杂度往往较高，从而对算法 的工程应用造成了较大的障碍。针对这种情况，作者拟在对粒子群优化算法特性 分析的基础上，研究一种不显著增加算法理解复杂度和实现复杂度为前提的，能 提高算法综合性能的控制参数( 如惯性权重等) 的选取方案，使改进后的粒子群 算法既有较强的全局搜索能力，避免早熟，又能保持较强的局部搜索能力，从而 提高寻优的总体质量和效率。 ( 2 ) 遴选图书需求优先度评价算法研究 图书馆能否吸引读者，主要取决于读者对书籍的需求是否能在图书馆得到满 足一个优秀的图书馆，不但要尽量满足读者的现实需求，还应当充分分析挖 掘、预测乃至激发读者的潜在需求。因此，进行遴选图书需求优先度评价是合理 采购图书的重要前提。针对这个问题，作者拟研究并建立读者需求模型，并拟利 用d - s 证据理论建立遴选图书需求优先度评价算法模型。 ( 3 ) 改进后的粒子群算法在图书采访决策中的应用研究 粒子群优化算法的应用是粒子群优化算法研究的一个很重要的方面本文拟 研究并建立以遴选图书流通需求效用最大化为目标、图书采购资金为核心约束条 件的图书投资效益最大化模型，并拟利用改进的粒子群算法，设计遴选图书采购 复本量决策模型 5 重庆大学高校教师硕士学位论文 2 基本粒子群优化算法 2 基本粒子群优化算法 本章对粒子群优化算法的产生背景、基本概念、数学模型以及算法步骤、应 用领域等进行了简单介绍 2 1 概述 长久以来，人们向往着设计的人工系统像自然系统那样健壮，高效灵活。具有 适应性、自组织和再生能力。近几十年来，一些新颖的优化算法，如人工神经网 络、遗传算法及蚁群算法、粒子群算法等通过模拟或揭示某些自然现象或过程而 得到发展，其思想和内容涉及数学、生物进化、人工智能、神经科学和量子统计 学等方面，为解决复杂工程问题提供了新的思路和手段。这些算法独特的优点和 机制，引起了国内外学者的广泛重视并掀起了该领域的研究热潮，且在许多领域 得到了成功应用。在优化领域，由于这些算法构造的直观性与自然机理，被称作 为智能优化算法1 2 5 , 2 6 , 2 7 。 在这些智能优化方法中，有一类是模拟某些群体的智能行为，虽然群体中的 个体仅具有简单的智能，但通过个体与个体和个体与环境的信息交流以及个体的 简单行为，从而使群体表现出复杂的自组织、分布式控制、可扩展、健壮的智能 体，实现对空间的高效搜索。也就是说，群体智能可以在适当的进化机制引导下 通过个体交互以某种突现形式发挥作用，这是个体的智能难以傲到的 在群体智能优化算法的框架下，大量基于不同物理背景的算法纷纷被提出， 如，遗传算法，粒子群算法等，并进行了广泛的应用尝试。 粒子群算法( 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 0 ) ，是一种基于群体智 能的进化计算方法是由p s o 由k e n n e d y 和e b e r h a r t 博士于1 9 9 5 年提出 2 s 2 9 。 p s o 的基本概念源于对鸟群捕食行为的研究：一群鸟在随机搜寻食物，在这个 区域里只有一块食物，所有鸟都不知道食物在哪里但是他们知道当前的位置离 食物还有多远那么找到食物的最优策略是什么昵? 最简单有效的就是搜寻目前 离食物最近的鸟的周围区域。p s o 从这种模型中得到启示并用于解决优化问题。 在p s o 中，每个优化问题的潜在解都是搜索空间中的一只鸟，称之为“粒子”，即 问题的解空间对应于搜索空间粒子群。所有的粒子都有一个由被优化的问题 ( 如，函数) 决定的适应值，每个粒子还有一个速度决定他们飞翔的方向和距 离。然后粒子群们就追随当前的最优粒子在解空间中搜索。p s o 初始化为一群随 机粒子也就是随机解，然后通过迭代找到最优解在每一次迭代中，粒子通过跟 踪“两个极值”来更新自己。第一个就粒子本身所找到的最优解，这个解称为个体 6 重庆大学高校教师硕士学位论文2 基本粒子群优化算法 极值，另一个极值是整个种群目前找到的最优解，这个极值是全局极值。另外也 可以不用整个种群而是用其中一部分作为粒子的邻居，那么在所有邻居中的极值 就是局部极值。 p s o 一经提出，立刻引起了进化计算领域学者们的广泛关注，形成一个研究 热点，目前己广泛应用于函数优化、神经网络训练、模式分类、模糊控制等领 域，取得了较好的效果。 2 2 原始粒子群优化算法的基本概念 为了更好地描述粒子群优化算法，在此作如下定义 3 0 , 3 1 j ： 定义l 粒子 类似于遗传算法中的染色体，p s o 中粒子为基本的组成单位，代表解空间的 一个候选解 定义2 种群 粒子种群由n 个粒子组成，代表n 个候选解。 定义3 粒子速度 粒子速度表示粒子在单位迭代次数位置的变化即为代表解变量的粒子在d 维 空间的位移 定义4 适应度函数 一般由适应度函数由优化目标决定，用于评价粒子的搜索性能，指导粒子种 群的搜索过程。算法迭代停止时适应度函数最优的解变量即为优化搜索的最优解 定义5 个体极值 个体极值是单个粒子从搜索初始到当前迭代对应的适应度最优的解。 定义6 全局极值 全局极值是整个粒子种群从搜索开始到当前迭代对应的适应度最优的解。 2 3 粒子群优化算法的一般数学模型 如前所述，粒子群算法的基本思想是1 3 2 1 ：用随机解初始化一群随机粒子，然 后通过迭代找到最优解。在每一次迭代中，粒子通过跟踪两个“极值”来更新自己： 第一个就是粒子本身所找到的最好解，即个体极值( p b e s t ) ，另一个极值是整个粒 子群中所有粒子在历代搜索过程中所达到的最优解( g b e s t ) ，即全局极值，在找到 这两个最好解后，接下来是p s o 中最重要的“加速”过程，每个粒子不断地改变其 在解空间中的速度，以尽可能地朝p b e s t 和g b e s t 所指向的区域“飞”去基本的粒 子群模型由一个m 维变量空间内n 个粒子( ( 位置，速度) ：= ( x ：，) 组成的群体构 成，表示为： 7 重庆大学高校教师硕士学位论文 2 基本粒子群优化算法 x ：= g ：，x ：，x ，x k ) 1 v j t = c ，畦，w ，v 二) ( 2 1 ) ( 2 2 ) 式中，扣l ，2 ，n ，n 为粒子群中粒子的个数；j = l 幺m ，m 为解向量的维 数；t 是进化代数。粒子根据如下的式( 2 3 ) 和式( 2 4 ) 来更新自己的速度和位置。 v ；“= v ：+ c l r a n d l 恼b e s t ；- x ；j + c 2 r a n d 2 b b c s t ：x ；) ( 2 3 ) x = x ：+ v ， ( 2 4 ) v ；：、v = “分别表示第i 个粒子在j 维方向上的当前速度和修正后的速度； x ：、x 分别为第i 个粒子在j 维方向上的当前坐标和修正后的坐标；c l 、睨是 加速系数，分别调节向全局最好粒子和个体最好粒子方向飞行的最大步长； 出s t 是第i 个粒子在第j 维的个体极值点的位置，g b e s t ：是到第t 代为止，所有 粒子在第j 维的全局极值点的位置；r a n d l 和r a n d 2 为两个在【o ，l 】范围内变化的 随机函数 2 4 粒子群优化算法的设计步骤和算法流程 设计步骤： ( 1 ) 确定问题的表示方案 粒子群算法在求解问题时，其首要步骤是将问题的解从解空间映射到具有某 种结构的表示空间，即用特定的编码表示问题的解，这和遗传算法是类似的。粒 子群算法的大部分研究均集中在数值优化领域中，其位置一速度计算模型使用于 具有连续特征的问题函数，因此，目前算法大多采用实数向量的编码方式，以粒 子的位置向量来表示问题的解。 ( 2 ) 确定优化问题的评价函数 在求解问题时，必须根据问题的具体特征，选取适当的目标函数来计算适应 值，适应值是唯一能够反映并引导优化过程不断进行的参量 ( 3 ) 选择控制参数 粒子群算法的控制参数通常包括粒子种群数量、算法执行的最大代数、惯性 权重系数其他一些辅助控制参数，如粒子位置和速度的控制范围等。 ( 4 ) 选择粒子群模型 目前，粒子群算法己经发展了多种位置速度计算模型，如惯性权重p s o 模 型、二进制p s o 模型等等，在求解不同类型优化问题时，不同p s o 模型的优化 性能也有差异 ( 5 ) 确定算法的终止准则 8 重庆大学高校教师硕士学位论文2 基本粒子群优化算法 与其他进化算法一样，p s o 算法中最常用的终止准则时预先设定一个最大的 迭代次数，或者当搜索过程中解的适应值在连续多少代后不再发生明显改变时， 终止算法 标准p s o 的算法流程如下： s t e pl ：设定加速常数c l ，和c 2 ，最大进化代数等参数，将当前进化代数置 为t = l ，初始化一群微粒( 群体规模为n ) ，包括随机位置和速度； s t e p2 ：评价每个微粒的适应度； s t e p3 ：对每个微粒，将其适应值与其经历过的最好位置p b e s t 作比较，如果较 好，则将其作为当前的最好位置p b e s t ； s t e p4 ；对每个微粒，将其适应值与全局所经历的最好位置g b e s t 作比较，如 果较好，则重新设置g b e s t ； s t e p5 ：根据方程( 2 3 ) 和( 2 4 ) 变化微粒的速度和位置； s t e p6 ：检查结束条件，若满足，则结束寻优，如未达到结束条件( 通常为 足够好的适应值或达到一个预设最大代数1 ) ，则返回s t e p2 从上述粒子群优化算法寻优过程可以看出其有如下特性：粒子群中的群体随着 时间的变化而进行空间位置的计算；粒子群中的群体对环境中的品质因素做出响 应，这种品质因素是通过p s o 中每个粒子的最好位置和种群中的最优粒子来反映 的；粒子群通过一定方式( t i p 通过对个体最优粒子的记忆和对全局最优粒子的学习的 方式) 分配这种响应而体现出种群的多样性，仅仅当粒子群中的最优粒予发生改变 时，粒子群中粒子的行为才发生改变，这正体现出了粒子群的稳定性和适应性。 图2 i 原始粒子群优化算法流程 r i 9 2 1p r 蚰a r yp m i d e $ w $ a r mo p t i m i z a t i o nf l o w 9 重庆大学高校教师硕士学位论文 2 基本粒子群优化算法 2 5 惯性权重因子的引入 为了更好的控制算法的探测和开发能力( 探测指粒子在较大程度上离开原先 的寻优轨程，偏到新的方向进行；开发则指粒子在较大程度上继续原先的寻优轨 程进行细部搜索。) ，s h i 在式( 2 3 ) 中引入了惯性权重w ，引入惯性权重因子 后，公式( 2 3 ) 、( 2 4 ) 就变为：口3 捌 = w w + c i r a n d l 吣s t ；- x + c 2 r a n d 2k b e s t ：一x 0 ( 2 5 ) x f = x ：+ v ， ( 2 6 ) 显见，惯性权重w 描述了粒子上一代速度对当前代速度的影响，控制其取值 大小可调节p s o 算法的全局与局部寻优能力w 值较大，全局寻优能力强，局 部寻优能力弱，反之，则局部寻优能力增强，而全局寻优能力减弱。刚开始惯性 权重为常数，但后来的试验发现，动态惯性权值能够获得比固定值更为好的寻优 结果。动态惯性权值可以在p s o 搜索过程中线性变化，亦可根据p s o 性能的某 个测度而动态改变 惯性权重的引入，可从不同的角度调整算法全局和局部搜索能力，使p s o 算 法的性能得到了很大提高，也使p s o 算法得以比较成功地应用于很多实际问题。 重庆大学高校教师硕士学位论文 3 粒子群优化算法的改进 3 改进的粒子群优化算法 本章首先对粒子群算法的根本问题和粒子群行为特性进行了较为详细分析研 究，在此基础上，提出了一种改进的粒子群优化算法。该算法在运行过程中根据 群体适应度方差与理想方差的比较来动态改变确定当前最佳粒子的惯性权值，以增 强粒子群优化算法跳出局部最优解的能力，避免早熟收敛问题，同时不引入其它算 法概念，算法的理解复杂度、实现复杂度得到有效控制 3 1 粒子群优化算法的根本问题 ( 1 ) 粒子群优化算法容易陷入到局部极值点中，导致得不到全局最优解。这 主要是由于算法的参数设计不恰当等原因导致的在计算的过程中，粒子的多样性 迅速的消失，从而造成算法“早熟”针对这类问题的改进措施基本思路一般是： 对粒子群的多样性设置某些指标，随着计算的进行，实时监测这些指标，一旦这 些指标超过某个事先设定的临界值，则对整个群体实施确某种操作，比如按指定 的概率重新初始化，以达到改善群体的多样性，克服早熟的问题 ( 2 ) 粒子群优化算法的收敛速度比较慢。在解决实际问题时，通常需要在一 定的时间内达到相应的精度，如果耗费很长的计算时间来得到一个可行解，有时 是不值得的。造成这种问题的原因是粒子群优化算法并没有很充分的利用计算过 程中得到的信息，在每一步迭代中，仅仅利用了全局最优和个体最优的信息，此 外，算法本身没有比较充分的优选机制，以淘汰比较差的待选解，从而导致算法 收敛速度较慢要解决这方面的问题，可以吸收进化算法的优点，在粒子的操作 中，加入繁殖、变异和优选算子，以加快算法的收敛速度 针对p s o 的不足，基于不同的策略，已产生了大量改进的粒予群优化算法。 这些改进算法虽然各有千秋，但从其根本来说，大多数改进方案都基于与其他优 化算法的结合，在实际应用当中，也出现了一些不尽如人意的地方：许多粒子群 优化算法的改进，是以大幅度提高算法理解和实现的复杂度为代价的，这就使得 粒子群优化算法失去了一些诱人的核心优点，如理解的简单性、实现的简洁性 等，这对该算法的大面积工程应用是极其不利的因此，以上述改进粒子群算法 的基本思路为出发点，寻找尽量简单有效的改进粒子群算法，是十分必要和有意 义的。 重庆大学高校教师硕士学位论文3 粒子群优化算法的改进 3 2 粒子群优化算法早熟行为及其判定 粒子群优化算法相对于遗传算法等进化算法，没有选择、交叉与变异等操 作，每个粒子按照粒子本身的搜索经验和其他粒子的搜索经验来调整自己的飞行 速度，算法结构相对简单，运行速度很快，但在运行过程中，如果某粒子发现一 个当前最优位置，其他粒子将迅速向其靠拢。如果该最优位置为一局部最优点， 粒子群就无法在解空间内重新搜索，于是算法陷入局部最优，这就是所谓的早熟 收敛现象。 为了克服早熟收敛，下面分析早熟特征及收敛判断机制。由粒子群算法中粒 子行为特征可以看出，粒子群优化算法无论是早熟收敛还是全局收敛，粒子群中 的粒子都会出现“聚集”现象，文献0 6 1 给出了粒子位置一致性等价于其适应度相 同的结论，因此，根据粒子群中所有粒子适应度的整体交化可以跟踪粒子群的状 态，可以以此作为早熟收敛判断的主要条件。设粒子群的粒子数目为n ，最为第i 个粒子的适应度，为粒子群目前的平均适应度，0 2 为粒子群的群体适应度方 差，则可把0 2 定义为； 如喜1 引2 口2 = l 掣 f 越ii ( 3 1 ) 其中f 的作用是限制0 2 的大小，其取值可采用如下公式： 厂= m a x l ，m a x 瞻_ ，- 哪i i ( 3 2 ) l _ g ” 也就是说，群体适应度方差反映了粒子群中所有粒子的“聚集”程度。方差越 小，则粒子群的“聚集”程度就越大，若在粒子群算法进化到某代时聚集度非常 大，而此时并不满足算法结束条件，则“聚集”将使群体失去多样性陷入了早熟状 态，故当0 2 较小时，需进行早熟处理。 但是，在优化过程中，粒子群的“聚集”，也是一种正常现象，我们要克服 的，只是其过早的“聚集”，在算法后期，粒子群的“聚集”不但没有害处，反而有 助于深度优化。因此，作者认为对0 2 的限制，其值应该是递减的，也就是对粒子 群“聚集”的容忍应当是逐渐放宽的，由此提出如下的期望矿曲线： o 。2 = b ：。- a 乙x t t _ y + ( a ：_ 一。乙x 2 t ，t 。) + o 乙 ( 3 3 ) 该曲线是一条开口向上的递减凹抛物线，式中：t i 。为最大允许迭代次数；t 为 当前的迭代次数；d 。2 一删0 2 。分别是初始方差值和进化到最大允许迭代次数的取 值。 重庆大学高校教师硕士学位论文 3 粒子群优化算法的改进 o k t a 乙 圈3 1 期望方差轨迹示意图 f i 9 3 1f i g u r eo f t h ea 【p ：c 乇e dv i 蛳t r a j e c t o r y 3 3 粒子群优化算法的行为特性分析 粒子群优化算法中的参数有很多，包括粒子种群数n 、最大速度v 。、最大 位置) ( f 。、惯性权值w ，自身认知系数c l ，和社会系数c 2 ，其中后三种参数通常 对算法具有更重要的影响。下面主要分析这三个参数的影响问题。 为了分析方便，下面再次给出标准粒子群算法公式： w ”= w w + c l r a n d l ( p b e s t ：- x + c 2 r a n d 2b b e s t ：一x d ( 3 4 ) x 1 = x ：+ v ：“ ( 3 5 ) 公式( 3 4 ) 中的第一部分可称为记忆项，表示某粒子当代速度的大小和方向 对下代粒子的影响；公式( 3 4 ) 中的第二部分一般称为自身认知项，是某粒子从 当前点指向此粒子自身最好点的一个矢量，表示粒子的动作来源于自本身经验的 部分；公式( 3 4 ) 中的第三部分一般称为群体认知项，是一个从当前点指向种群 最好点的一个矢量，反映了粒子间的协同合作和知识的共享。粒子就是通过对自 身经验和群体中最好的经验的认同来决定下一步的运动，显然，这与人类的决策 行为特性是相似的：人们通常也是通过综合自身已有的信息和从外界得到的信息 来做出决策。 如果进化方程中仅含有记忆和自身认知部分，即c 尹o ，则称之为“只有认知” 的模型口7 l ，亦即 v ：”= w v ；4 - c l r a n d 。l p b c s 吒一x ；j ( 3 6 ) 那么，一般来说，算法的性能就会变差，其主要原因是不同的粒子间缺乏信 息交流，即没有社会信息共享粒子问没有信息的交互，使得个规模为n 的粒 子群体优化等价于运行了n 个单个粒子独自优化，显然得到最优解的概率非常小 阅 重庆大学高校教师硕士学位论文 3 粒子群优化算法的改进 若速度进化方程中认知部分仅包含群体认知部分，即c l = o ，则称之为“只有 社会”的模型田j ，也即 v ：钉= w v ：+ c 2 r a n d 2 l g b e s t ：x ：j ( 3 7 ) 粒子缺乏对自身经验的认知，在对群体最优位置点的向心力作用下，有能力 到达新的搜索空间，虽然它的收敛速度比基本粒子群算法更快，但对于复杂问 题，则更加大早熟的危险，更容易陷入局部最优点【3 羽。 如果公式( 3 4 ) 中没有后两项，则变为：“= 形t ，粒子将保持在相同 的速度和大小“飞翔”至下一个点，直至达到边界值这样的p s o 实际上变成了一 个纯随机搜索算法，显然很难得到满意解。 如果公式( 3 4 ) 没有第一项，则变为： v f l = c l r a n d li p b e s t ：一x ；j + c 2 r a n d 2i g b e s t ：- x ：j ( 3 8 ) 那么“飞翔”粒子的速度仅仅取决于粒子的当前位置和它们最好的历史位置。 速度自身是没有记忆性的。假设在开始的时候