（系统工程专业论文）基于模拟退火的粒子群改进算法的研究与应用.pdf

华北电力人学硕十学位论文 摘要 粒子群优化算法是一种简单有效的随机全局优化技术。但是，该算法也存在容易陷 入局部极值，进化后期的收敛速度慢和精度低等缺点。对于粒子群优化算法的参数的设 定，以往大都采用经验数据，没有具体的理论依据。本文针对算法的这些问题提出一种 基于模拟退火的新型粒子群优化算法，利用模拟退火来优化粒子群算法的参数，使得粒 子群优化算法的参数随着优化算法的进行而不断改变，以适应需要优化的问题。通过测 试函数，证实了该种算法能够克服粒子群自身的一些缺点，与以往的算法相比，提高了 收敛速度和精度。最后，本文将改进后的粒子群优化算法应用到求解约束优化问题、求 解非线性方程组问题和热工过程辨识中，并取得了很好的应用效果。 关键词：粒子群，模拟退火，约束优化问题，非线性方程组，热工过程辨识 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 l g o r i t h mi sas i m p l es t o c h a s t i cg l o b a lo p t i m i z a t i o n t e c h n i q u e b u tt h i sa l g o r i t h mh a ss o m ed e m e r i t s ，s u c h 弱r e l a p s i n gi n t ol o c a le x t r e m u m ，s l o w c o n v e r g e n c ev e l o c i t ya n dl o wc o n v e r g e n c ep r e c i s i o ni nt h el a t ee v o l u t i o n a r y t h ep a r a m e t e r s o ft h ep s oa l g o r i t h ma r ea l w a y sb a s e do ne x p e r i e n c ew i t h o u tt h e o r i e si nt h ep a s t t or e s o l v e t h e s ep r o b l e m s ，ac o m p o s i t 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 mb a s e do ns i m u l a t e d a n n e a l i n gi sp r o p o s e di nt h i sp a p e r t h ep a r a m e t e r so fp 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 m a r eo p t i m i z e db yt h es i m u l a t e da n n e a l i n g ，s ot h a ti tc a na l t e rw i t ht h ea l g o r i t h m i cp r o c e s st o a d a p tt ot h eo b j e c t t h er e s u l t so fe x p e r i m e n tc l e a r l yd e m o n s t r a t et h ei m p r o v e dp e r f o r m a n c e s o ft h ep r o p o s e dp s oa l g o r i t h m f i n a l l y ，t h em o d i f i e dp s oa l g o r i t h mw a sa p p l i e dt ot h e c o n s t r a i n e d o p t i m i z a t i o np r o b l e m ，t h es o l v i n g n o n l i n e a r e q u a t i o n s a n dt h e s y s t e m i d e n t i f i c a t i o no ft h e r m a lp r o c e s s ，a n di tw a sp r o v e de f f e c t i v e l yt h a tt h ep r o p o s e dp s oi nt h i s p a p e ri se f f e c t i v ea n da p p l i c a b l e l i uh a n j i e ( s y s t e me n g i n e e r i n g ) d i r e c t e db yp r o f l u oy i 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 na 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 ，c o n s t r a i n e d o p t i m i z a t i o np r o b l e m ，n o n l i n e a re q u a t i o n s ，s y s t e mi d e n t i f i c a t i o no ft h e r m a lp r o c e s s 3 2洲0洲川7，川9 ，1y 华北电力人学硕十学位论文 目录 摘要i a b s t r a c t i 第一章引言1 1 1 选题背景及意义1 1 1 1 现j 丕1 1 1 2 选题背景1 1 1 3 研究的意义3 1 2 国内外研究动态4 1 2 1p s o 算法的理论研究4 1 2 2p s o 算法的改进方法研究。4 1 2 3p s o 算法的应用研究5 1 3 论文的主要工作内容一5 第二章粒子群优化算法理论分析7 2 1 基本粒子群优化算法。7 2 1 1 基本原理7 2 1 2 算法流程9 2 1 3 全局模式与局部模式1 0 2 1 4 同步模式与异步模式1 l 2 2 标准粒子群优化算法1 2 2 2 1 带惯性权重的粒子群优化算法1 2 2 2 2 带收缩因子的粒子群优化算法1 3 2 3 标准粒子群优化算法的收敛性分析1 3 2 4 粒子群优化算法的参数分析1 5 2 4 1 群体规模1 6 2 4 2 最大速度1 6 2 4 3 学习因子16 2 4 4 惯性权重1 7 2 4 5 迭代终止条件1 7 2 5 离敞二进制粒子群优化算法1 7 2 6 小结18 第三章基于模拟退火的粒子群优化算法的改进研究1 9 3 1 粒子群优化算法的改进分析1 9 i 华北电力人学硕十学位论文 3 2 模拟退火算法2 0 3 2 1 固体退火原理2 0 3 2 2 模拟退火算法2 0 3 2 3 模拟退火算法的特点2 2 3 3 基于模拟退火的复合粒子群改进算法( c p s o s a ) 。2 3 3 3 1 改进算法的基本原理2 3 3 3 2 改进算法的基本流程2 4 3 3 3 改进算法的测试函数实验2 6 3 4 小结。3 0 第四章粒子群改进算法在求解约束优化问题中的应用3 l 4 1 约束优化问题31 4 2 粒子群改进算法求解约束优化问题3 3 4 2 1 约束条件的处理3 3 4 2 2 粒子的比较准则3 3 4 3 约束优化问题的数值实验。3 4 4 3 1 测试函数一3 4 4 3 2 测试函数二3 5 4 3 3 测试函数三3 6 4 4 j 、结3 6 第五章粒子群改进算法在求解非线性方程组中的应用3 7 5 1 非线性方程组的数学模型3 7 5 2 非线性方程组的一般解法3 8 5 2 1 不动点迭代法3 8 5 2 2 牛顿法3 9 5 3 粒子群改进算法求解非线性方程组4 0 5 3 1 与求解非线性方程组等价的优化问题4 0 5 3 2 求解非线性方程组的步骤4 1 5 4 数值试验4 1 5 4 1 非线性方程组一4 2 。 5 4 2 非线性方程组二一4 3 5 4 3 与实际问题相关的非线性方程4 4 5 5 小结4 4 第六章粒子群改进算法在热工过程辨识中的应用4 5 6 1 引言4 5 6 2 系统辨谚 的基本原理4 6 i i i 华北电力人学硕+ 学位论文 6 3 基于改进粒子群优化算法的热工过程辨识4 7 6 3 1 热工过程对象模型4 7 6 3 2 基于c p s o s a 算法的过程辨识的原理4 8 6 3 3 过程辨识算法的编码设计5 0 6 4 仿真实验5 0 6 4 1 已知模型的辨识5 0 6 4 2 利用现场数据的辨识5 2 6 5 小结5 5 第七章总结与展望5 6 7 1 论文总结5 6 7 2 研究展望。5 7 参考文献5 8 致 射6 2 在学期间发表的学术论文和参加科研情况6 3 i v 华北电力人学硕十学位论文 1 1 选题背景及意义 1 1 1 概述 第一章引言 在自然科学、社会科学以及人们的同常生活中广泛存在着大量的求最小或最大 的问题，即所谓的最优化问题。特别是近代，在管理科学、计算机科学、分子物理 学和生物学以及超大规模集成电路设计、代码设计、图象处理和电子工程等科技领 域中，大量的组合优化问题需要解决。随着科学技术尤其是计算机技术的不断发展， 以及数学理论与方法向各学科和各应用领域更广泛更深入的渗透，最优化理论及技 术在社会的诸多方面起着越来越大的作用。而最优化理论及技术的研究核心就是优 化算法的研究及应用。随着优化对象在复杂化和规模化等方面的提高，基于严格机 理模型的传统优化方法在实施方面变得越来越困难。2 0 世纪8 0 年代初期，应运而 生了一系列现代优化计算方法，这些算法在一些实际问题中的成功应用，使得科学 工作者投入了大量的精力和热情去研究算法的模型、理论和应用效果。近年来，基 于群体智能理论的一些新兴的优化算法的研究成为研究者关注的焦点，粒子群优化 算法正是其中之一。 粒子群优化( 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 选题背景 ( 1 ) 研究的基础一一群体智能 2 0 世纪9 0 年代科学家们提出群体智能方法，该方法一直受到广泛的关注。群 体智能源于对自然界社会性生物的群体行为的模拟。自然界具有社会性质的生物群 体中，个体与个体之间存在着一些互动行为，如群居的个体以集体的力量行进、御 敌等，单个的个体只能完成简单的任务，而由单个个体组成的群体却能完成复杂的 任务，这种无智能的群体通过合作表现出的智能行为就称之为群体智能( s w a r m i n t e l l i g e n c e ，s i ) 【lj 。例如，蜜蜂采蜜、筑巢，蚂蚁觅食等。而从群居生物互相合作 进行工作中得到启迪，研究其中的原理，并以此原理来设计新的求解问题的算法被 称为群智能算法。目i j i ，群体智能研究领域的最受关注的算法主要是蚁群优化算法 ( a n tc o l o n yo p t i m i z a t i o n ，a c 0 ) 和粒子群优化( 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 ) 华北电力人学硕十学位论文 算法。a c o 算法是对蚂蚁群落觅食过程的模拟，已经成功应用于许多领域的优化问 题。而p s o 算法最初是对鸟群觅食过程的模拟，后来的研究发现它是一种很好的优 化工具。 ( 2 ) 粒子群优化算法的产生与发展 粒子群优化算法最早是在1 9 9 5 年由美国的k e n n e y 和e b e r h a r t 提出，其基本的 模型同遗传算法相类似，是一种基于迭代的优化工具。但是在算法的实现过程中， 没有遗传算法的交叉变异操作，而是以粒子对于空间中最优粒子的追随进行解空间 的搜索。因此，p s o 算法的优点在于流程简单易实现。算法从出现至今，已被迅速 地应用于函数优化、神经网络训练、模糊系统控制、数据聚类以及原有的一些遗传 算法的应用领域。作为一种新颖的优化搜索算法，在过去的这十几年的研究中，研 究者的大部分精力主要集中在对算法的结构和性能的改善，如参数的设置、粒子的 多样性、种群的结构以及和其他算法的融合。 ( 3 ) 模拟退火算法的产生与发展 模拟退火算法( s i m u l a t e da n n e a l i n g ，s a ) 最早的思想由m e t r o p o l i s 在l9 5 3 年 提出，到了1 9 8 3 年k i r k p a t r i c k 才成功的将其应用在组合最优化问题。模拟退火算 法是模拟高温金属降温的热力学过程，将固体加热至温度充分高，再让其慢慢冷却。 加温时，固体内部粒子随温度升高变为无序状，内能增大，而徐徐冷却时粒子渐趋 有序，在每个温度都达到平衡态，最后在常温时达到基态，内能减为最小1 2 j 。s a 算 法起初主要是应用在n p 完全问题中，如货郎担问题、最大截面问题、0 1 背包问题、 独立集问题、图着色问题和调度问题等。经过几十年的研究，算法本身已经有了很 好的理论基础。目前，该算法已近在自然科学、工程技术和管理等诸多领域得到了 很好的应用。 ( 4 ) 带约束的优化问题 约束优化问题( c o n s t r a i n e do p t i m i z a t i o np r o b l e m s ，简称c o p s ) 是一类广泛存 在于实际工程中但又较难求解的问题，因而对其研究具有十分重要的理论和实际意 义。目前，求解约束优化问题的算法有很多，按照性质大体可分为两类：确定性的 算法和随机性的算法。确定性的算法通常是基于梯度的搜索方法，如投影梯度法、 简约梯度法、各类外点及内点惩罚函数法、l a g r a n g i a n 法和序列二次规划法等。随 机性的算法主要包括进化算法( e v o l u t i o n a r ya l g o r i t h m s ，简称e a s ) 、模拟退火 ( s i m u l a t e da n n e a l i n g ，简称s a ) 算法、禁忌搜索( t a b us e a r c h ，简称t s ) 、遗传算法 ( g e n e t i c a l g o r i t h m ，简称g a ) 、粒子群优化算法等。近几年，随着智能算法的发展， 以随机性的算法来解决带约束的优化问题已经成为了研究的趋势。 ( 5 ) 非线性方程组的求解 非线性问题是现代数学的主要研究课题之一，随着科学技术和计算机技术的高 速发展使得解决这类问题的成为可能。而非线性方程组的求解则是这类问题中最基 2 华北电力人学硕十学位论文 本的问题，许多学者对非线性方程组在理论和数值计算方面都做了大量的研究，但 对其求解仍是一个难题【3 】。求解非线性方程组的问题在生命科学、水利科学、电路 和电力系统计算、非线性力学、非线性规划等众多领域中有着广泛和重要的应用， 它的研究和发展一直得到广泛的关注，并产生了许多有效的方法。 解决该问题的传统方法主要有牛顿法及其改进的方法、最速下降法、共轭梯度 法、变度量法、降维法等求解方法【4 】，但这些方法普遍比较麻烦，要求方程组有较好 的解析性质，计算量大，不容易用计算机实现。因此，近几年人们提出了一些新的 基于智能优化算法求解方法。这些方法具有大范围收敛、对方程的本身要求不严格 和对初始点的选取不敏感等特点，非常适合复杂的非线性方程组问题的求解。 ( 6 ) 关于热工过程的系统辨识 要定量地、准确地分析一个受控系统特性，首先要了解和掌握受控系统的数学 模型。由于古典和现代控制方法的应用很大程度上依赖于结构已知的系统数学模 型，因此提出怎样确定系统的数学模型及其参数的问题，即所谓的系统辨识问题。 通过实验或系统的运行，得到有关系统模型的信息，经过计算处理，可以得到系统 的数学模型。 热工过程对象都是复杂的设备和系统，它们的数学模型相当复杂，采用理论方 法获得其数学模型相当困难。在工程上，主要借助于系统辨识( 试验建模) 方法来 获得可靠的被控对象数学模型。辨识是根据受控系统或受控过程的输入输出数据， 在一类模型中确定出一个在某种意义下最能代表该系统或该过程特性的数学模型。 根据被控对象施加试验信号，及所用分析方法的不同，系统辨识的方法有很多种。 当前实际使用的多是传统的阶跃响应法( 飞升曲线法) 、脉冲响应法( b o d e 图法) ， 新近发展起来的基于智能算法的辨识越来越受到人们的关注，如遗传算法、蚁群算 法等。本文选取改进后的粒子群优化算法进行热工过程辨识的研究。 1 1 3 研究的意义 粒子群优化算法( p s o ) 具有深刻的群体智能背景，有较强的并行性和通用性； 算法简单、操作方便，既适合科学研究，又特别适合工程应用。因此，p s o 已经成 为一种重要的优化工具并成功地应用各个领域。与其他全局优化算法一样，算法在 实际应用中也有一些不尽如人意的问题。其中最主要的是它在求解高维复杂优化问 题时易产生早熟收敛、收敛速度慢、全局寻优能力差等问题。由于算法的发展历史 尚短，数学理论基础相对薄弱，对于算法中参数的设定大都凭借经验选取，缺乏成 熟理论。针对这些问题，本文展开研究，力求在对算法的研究中能够改进算法的不 足之处，使得算法能够得到更好的应用。 华北电力人学硕士学位论文 1 2 国内外研究动态 自p s o 提出以来，由于它的计算快速性和算法本身的易实现性，引起了国际上 相关领域众多学者的关注和研究，成为国际演化计算界和工程优化界的研究热点。 目前己被“国际演化计算会议 ( c o n g r e s so ne v o l u t i o n a r yc o m p u t a t i o n ，c e c ) 列为讨 论专题之一例。 根据对国内外关于粒子群算法研究的相关文献以及进化算法领域的发展趋势 的分析，主要有以下几个研究方向：算法的理论研究、算法的改进方法研究以及算 法的应用研究。 1 2 1 p s o 算法的理论研究 到目前为止，p s o 算法的分析方法还很不成熟和系统，存在许多不完善和未涉 及到的问题。关于p s o 算法的理论研究，人们关心的是粒子之间是如何相互作用 与运动而最终达到全局优化的。与相对鲜明的生物社会特性基础相比，p s o 的数学 基础显得比较薄弱，缺乏深刻且具有普遍意义的理论分析。因此，对数学基础的研 究非常重要，p s o 算法理论研究主要包括粒子运动轨迹研究、算法收敛性研究和粒 子群分布与演化研究等方面。如何利用有效的数学1 ：具对p s o 算法的运行行为、收 敛性及计算复杂性进行分析足目前的研究热点之一。文献 6 】中利用微分方程和差分 方程为工具对单个粒子的运动轨迹进行研究，发现单个粒子其轨迹是各种正弦波的 随机的叠加组合。文献 7 1 2 】中关于p s o 算法的收敛性研究比较多的集中在一些简 化条件下，采用的主要是动态系统理论进行分析。文献 1 3 采用f o k k e r - p l a n c k 方程 和l a n g e v i n 方程对p s o 算法的运行机理有比较深入的分析研究。 1 2 2p s o 算法的改进方法研究 p s o 算法的改进研究可以说是该算法研究最重要的分枝，其内容十分丰富，主 要有参数的改进、拓扑结构的改进以及与其他算法的结合等方面。 对p s o 参数的研究，主要针对惯性因子w ，学习因子c 。和c 2 ，其中对p s o 参数 取值的改进技术中研究最多的是关于惯性因子w 的。w 首先是由s h i 等在文献 7 中 提出，它表明粒子原先的速度能在多大程度上得到保留，体现了局部搜索能力和全 局搜索能力的比例关系。之后，s h i 等又提出按照线性递减规律改变惯性因子w 。 为了改善算法的收敛速度和对多维空f n j 的精细搜索能力，c h a t t e r j e e 等在文献 14 】中 提出非线性惯性因子的p s o 。 p s o 的拓扑架构主要是分为全局模型和局部模型。k e n n e d y 首先提出了l o c a l 版的p s o t l 5 1 ，一定程度上摆脱了基本g l o b a l 版p s o 易于陷入局部最优解的缺点。 4 华北电力人学硕+ 学位论文 k e n n e d y 和m e n d e s 又近一步对粒子群的拓扑结构作了研究，引入邻域拓扑的概念 来调整邻域的动态选择，同时引入社会信念将空间邻域与邻域拓扑中的环拓扑相结 合以增加邻域间的信息交流，提高群体多样性【1 6 - l 引。 p s o 算法和其它优化算法的结合是当前p s o 改进研究的热点，例如，在p s o 中引入g a 的选择、交叉、变异算子，在e p 中借用p s o 中“速度的概念指导 变异操作等。a n g e l i n e 将选择算子引入p s 0 中，选择每次迭代后的较好粒子复制到 下一代，以保证每次迭代的粒子群都具有良好的性能，这种改进算法在对某些单峰 函数的优化上取得良好效果【1 9 】。l o v b j e r g 等提出带交叉算子的p s o ，在粒子群每次 迭代后，按几率在粒子间交换各维，通过交叉来生成更优秀的粒子，这个交叉概率 是用户确定的，与粒子的适应值无关【2 0 1 。h i g a s h i 等提出带变异算子的p s o ，引入 变异算子来增强群体多样性，避免陷入局部最优1 2 。高鹰等人则引入免疫机制的概 念，提高粒子群的多样性和自我调节能力，以增强粒子的全局搜索能力【2 2 1 。b a s k a r 、 s h i 等人各自提出了自己的协同p s o 算法，通过使用多群粒子分别优化问题的不同 维、多群粒子协同优化等办法来对基本p s o 算法进行改进尝试【2 3 】【2 4 1 。除了以上的 混合算法之外，还出现了量子p s o 、耗散p s o 、自适应p s o 、小生境p s o 等混 合改进算法，也有研究者在某些问题的优化上采取p s o 与模拟退火优化算法相结合 的办法【2 5 1 。 ， p s o 改进算法各有自己的优缺点，它们均引入了一些新的参数，在改进算法性 能的同时也一定程度上增加了算法的复杂性，应用价值也受到相应限制。 1 2 3p s 0 算法的应用研究 p s o 的优势在于算法的简洁性、易于实现，没有很多参数需要调整，且不需要 梯度信息。所以p s o 一经提出就引起了广泛的关注，其应用已经扩展到很多领域， 如：函数的优化、神经网络训练、工程中优化问题的解决等等。目f i i ，国内也有越 来越多的学者关注的应用，但是相对来说，国内的研究还在起步阶段，大多是对算 法综合和算法的实际工程应用方面的研究。 算法的有效性必须在应用中才能体现，尽管p s o 算法已经在一些领域得到了 很好的应用，但是在其他一些应用领域都还处于研究阶段，因此，广泛开拓其应用 领域，对深化研究算法也非常有意义。 1 3 论文的主要工作内容 本论文的主要工作内容分为以下两个方面： ( 1 ) 理论研究 介绍粒子群算法的基本原理，分析算法的优势和不足，总结以往粒子群算法中 5 华北电力大学硕+ 学位论文 几种具有代表性的改进策略。本文通过对已有的p s o 的理论研究，提出了一种基于 模拟退火思想的改进粒子群优化算法。利用模拟退火算法有其在寻找全局极值方面 的优越性，来改善p s o 易陷入局部极值点的缺陷。 该改进算法是一种基于模拟退火的粒子群复合优化算法。p s o 算法中参数的设 定，往往是根据实际的问题，通过大量的试验，凭借研究经验做出选择。在该改进 算法中，将p s o 算法中的参数的取值也作为一个优化问题，在p s o 算方法的优化 过程中，同时运用模拟退火思想对p s o 的参数本身进行优化，使得p s o 的参数能 随着算法的进行自适应的改变。 ( 2 ) 应用研究 本文的应用研究主要是求解带约束条件的优化问题、求解非线性方程组的问题 以及热工过程的系统辨识三个方面。文中将运用c + + 语言和m a t l a b 语言对改进 算法进行编程仿真，通过对于改进粒子群算法在这三个方面的应用研究以及计算机 仿真，可以验证改进算法的在应用方面的有效性。 6 华北电力人学硕十学位论文 第二章粒子群优化算法理论分析 粒子群优化算法( 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 算法通过群体中微粒间的合作与竞争而产生的群体智 能指导优化搜索，算法具有通用性较强、全局寻优的特点。本章主要介绍p s o 算法 的原理、流程，并对算法的参数及收敛性进行理论分析。 2 1 基本粒子群优化算法 生物群体内个体间的合作与竞争等行为产生的群体智能，往往能给某些特定的 问题提供高效的解决方法。鸟类在搜索食物的过程中，个体与个体之间可以进行信 息的交流和共享，每个成员可以得益于所有其他成员的发现和飞行经历。当食物源 不可预测的零星分布时，这种协作带来的优势很明显，起决定性作用远大于对食物 的竞争带来的劣势。p s o 算法正是源于这种对鸟群觅食行为的研究。l9 9 5 年， k e n n e d y 和e b e r h a r t 发现鸟群在飞行过程中经常会突然改变方向、散开、聚集， 其行为不可预测，但其整体总保持一致性，个体与个体间也保持着最适宜的距离。 通过对类似生物群体的行为的研究，提出了粒子群优化算法。 2 1 1 基本原理 粒子群优化算法采用速度一位置搜索模型。基于该模型的粒子在解空间的搜索 如图2 1 所示。每个粒子代表解空间的一个候选解，解的优劣程度由适应度函数决 定。速度决定粒子在搜索空间单位迭代次数的位移。其中，适应函数根据优化目标 定义。p s o 中基本概念定义如下： 粒子定义：p s o 中以粒子( p a r t i c l e ) 为基本的组成单位，代表解空阳j 的一个候选 解。设解向量为d 维变量，则当算法迭代次数为t 时，第f 个粒子z 可表示为 玉- 【。，2 ，】。其中，表示第f 个粒子在第k 维解空间中的位置，即第i 个候选解中的第k 个待优化变量。 种群定义：粒子种群( p o p u l a t i o n ) 由朋个粒子组成，代表所个候选解。经过t 次 迭代产生的种群p o p ( t ) = k ，j r 2 ，x 。) 】。其中，葺”为种群中的第f 个粒子。 粒子速度定义：粒子速度表示粒子在单位迭代次数位置的变化，代表解变量的 粒子在d 维空阳j 的位移u = 【u 。n ，u ：，耐】，其中，n 为第f 个粒子在解空间第 k 维的速度。 适应度函数定义：适应度函数( f i t n e s sf u n c t i o n ) 山优化目标决定，用于评价粒子 的搜索性能，指导粒子种群的搜索过程。算法迭代停止时适应度函数最优的解变量 7 华北电力大学硕十学位论文 即为优化搜索的最优解。 个体极值定义：个体极值b = ( 辟。，b ：，砌) 是单个粒子从搜索初始到当前迭代 对应的适应度最优的解p b e s t 。 全局极值定义：全局极值以= ( 终，p g ：，) 是整个粒子种群从搜索开始到当前 迭代对应的适应度最优的解g b e s t 。 图2 - 1p s o 算法的粒了位置更新示意图 p s o 首先初始化为一群随机粒子( 随机解) ，然后通过迭代搜索最优解。在每一 次迭代中，粒予通过个体极值与全局极值更新自身的速度和位置，具体公式如下【2 6 】： 皑“) - 嵋+ c l ( 硝一硝) + c 2 r 2 ( 蟛一端) 硝+ 。) - 硝+ 屹“ ( 2 1 ) ( 2 2 ) 、r 2 是介于 0 ，l 】之问的随机数，c l 、c 2 为正的加速常数( a c c e l e r a t i o nc o n s t a n t s ) ， 也称为学习因子。t 为迭代的次数。速度( 一。，。) ，圪。为速度上限。通过式 ( 2 1 ) 求得后，当v , d 。时，取= ；当 一时，取= 一。 式( 2 1 ) 中的速度由三部分组成，第一部分是粒子先前的速度，也就是记忆项， 说明了粒子目前的状态，起到了平衡全局和局部搜索的能力；第二部分是“认知 ( c o g n i t i o n ) ”部分，表示粒子自身的思考，它使粒子飞向自身曾经发现的最优位 置：第三部分为“社会( s o c i a l ) ”部分，体现了粒子问的信息共享与相互合作，它 引导粒子飞向粒子群中的最优位置。因此，这三个部分共同决定了粒子的空问搜索 能力。 在每一次迭代过程中个体极值p b e s t 和全局极值g b e s t 的更新公式如下( 以求最 小值为例) ： 华北电力人学硕十学位论文 2 1 2 算法流程 ip t = 西，i f 厂( 而) 厂( 鼽) 【p t 。b ，o t h e r w i s e l b = 所，i f ( 见) 0 时，特征值为两个实根，此时的系统不稳定。 当a = 0 时， = 五= l ，则系统处于临界稳定状态。 当 0 时，其特征根为两个复根，如要使系统稳定，则特征根的幅值应小于l ， 则应该满足，由此可以推出：w 0 。 总结上述分析得出算法的收敛区域为 w 0 ，2 w 一矽+ 2 0 ( 2 1 7 ) 平面示意图见图2 - 4 。当w 和缈在上述收敛区域取值，无论任何初始位置和初始 速度，粒子将收敛到极值点。 图2 - 4 根据矩阵g 分析得出的p s o 算法收敛区域 2 4 粒子群优化算法的参数分析 算法参数是影响算法性能和效率的关键，如何确定最优参数使算法性能最佳本 身就是一个极其复杂的优化问题。p s o 算法最大的优点就是算法简单，收敛速度快， 算法中没有太多需要调节的参数，所以粒子群算法成为目自i 群体智能算法研究中的 热点。对于不同的优化问题，在取得最优结果时参数的设置往往是不完全相同的。 不论在基本粒子群优化算法还是标准粒子群优化算法中，都有一些参数需要设定， 下面对其进行全面的分析： 华北电力人学硕十学位论文 2 4 1 群体规模 p s o 算法的群体规模是个整型参数。当很小的时候，陷入局优的可能性很大。 显然越大，相互协同搜索的粒子就越多，更能发挥的搜索能力。然而，群体过大将 导致计算时间大幅增加，并且当群体数目增长至一定水平时，再增长将不再有显著 的作用。目前，一般的文献中大都取3 0 到5 0 左右 3 q 。在文献 3 2 】中，s h i 和e b e r h a r t 认为，“p s o 对种群大小不敏感”。他们得出的结论是在给定精度下所需迭代次数的 平均值。当粒子数大于5 0 时，种群的大小对于性能的影响不明显，但当粒子数小 于5 0 时，可发现种群大小对性能还有较大影响。从计算复杂度分析，种群粒子数 多时，将需要计算更多的评价函数，从而增加算法的计算时间，但同时也增加算法 的可靠性。所以，在选取粒子规模大小时，应综合考虑算法可靠性和计算时间。对 通常问题5 0 个粒子己足够，对于较复杂问题可根据具体问题选取粒子规模多于5 0 的粒子数。 2 4 2 最大速度 最大速度圪。，决定粒子在一次迭代中最大的移动距离。圪。若较大，探索能力增 强，但是粒子容易飞过最好解。圪。，较小时，丌发能力增强，但是容易陷入局部最 优。一般来说，最大速度圪。，的选择不应该超过粒子的搜索空间的宽度。在文献 3 3 】 中指出，只要在合理的范围内，最大速度对算法性能的影响不明显。但是，对于多 峰函数而言，圪。不能过小，否则会影响粒子的全局搜索能力，一旦算法陷入局部 极值则无法跳出。另外，有分析和实验表明，设定心。，的值可以通过惯性权重的调 整来实现。目前，在很多的实验中，基本上对圪。，进行初始设定以后固定不变，一 般将圪。设定为每维变量的取值范围，而不必细致地选择与调节。 2 4 3 学习因子 在p s o 算法中，学习因子c i 、c 2 是控制粒子向自我历史经验和群体最优个体学 习的因子，从而控制向群体内或邻域内的最优点靠近。与惯性权重作用类似，学习 因子也能起到平衡局部搜索与全局探索能力，因此也可以把学习因子c i 、c 2 看成是 粒子飞向个体极值p b e s t 和全局极值g b e s t 的加速权重。 当c i = 0 ，c 2 0 时，粒子自身没有“认知”能力，亦即“只有社会”的模型。在 这种情况下，由于粒子问的相互作用，算法有能力到达新的搜索空间，且收敛速度 更快，但是对复杂问题，比标准粒子算法更容易陷入局部最优。 当c i 0 ，c ，= 0 时，粒子间没有社会信息共享，亦即“只有认知”的模型。这 时由于个体之间没有交互作用，一个规模为m 的群体等价于川个粒子的单独运动， 1 6 华北电力人学硕十学位论文 因而得到解的几率非常小。 在很多的研究中，通常设c l = c 2 = 2 ，后来c l e r c 推导出c t = c e = 2 0 5 ，也有研究 者认为c i 应与c 2 不等【2 7 】，并由试验得出c i = 2 8 ，c 2 = 1 3 。实际上这些研究也仅仅局限 于部分问题的应用，无法推广到所有问题领域。在以往的研究中，c i 、c 2 的取值一 般都是在 o ，4 】范围内。 2 4 4 惯性权重 惯性权重w 是标准p s o 中非常重要的参数。前面已经作了说明，惯性权重w 可 以用来控制p s o 算法的开发和探索的能力，它的大小决定的粒子的当前速度受到以 前速度的影响程度，它将直接影响粒子的全局和局部搜索能力。惯性权重取值较大 时，全局寻优能力强，局部寻优能力弱。若惯性权重参数太大，粒子群可能错过最 优解，导致算法不收敛，或者不能收敛到最优解。选择一个合适的w 可以平衡全局 和局搜索能力，这样可以以较少的迭代次数找到最优解。惯性权重的选择一般分为 常数和时变两种，随着p s o 算法的不断改进，很多研究中都采用时变的惯性权重。 前面提到的线性递减惯性权重是一种最为常用的方法。大量的实验发现w 的值在 【0 9 ，0 2 】之间平均来说算法会有比较好的性能，并且w 的值线性的从1 4 减少到0 要 比用固定的好。这是因为算法以一个较大的惯性权重开始可以找到比较好的范围， 后来用较小的惯性权重可以获得较好的局部搜索能力【3 4 】。事实上，不同的求解问题， 其惯性权重的取值范围会有所不相同。另一方面，在很多文献中都提出了自适应惯 性权重的p s o ，对于不同的优化对象，其自适应的原则不相同，取得的优化效果也 就不尽相同，因此，惯性权重的取值和自适应原则是在已有的【0 9 ，0 2 】的基础上， 根据具体优化的问题，进行具体的调整。 2 4 5 迭代终止条件 迭代的终止条件的设定通常是根据具体的优化问题来决定，同时还应考虑到算 法的优化质量和搜索效率等多方面的性能。算法的终止条件一般设为达到最大迭代 次数或达到需要的计算精度要求占时，算法停止迭代，输出优化结果。 2 5 离散二进制粒子群优化算法 原始的p s o 主要是针对连续空i 日j 的优化问题进行设计的，目f j i 的算法研究也主 要是是针对连续型的优化问题。1 9 9 7 年，为了解决工程实际中的组合优化问题， k e n n e d y 和e b e r h a r t 提出了p s o 算法的离散二进制版【35 1 ，把位置表示为离敞型的0 和l ，速度表示成一个位串转变成l 的概率，既是把求得的速度通过一个s i g m o i d 华北电力大学硕十学位论文 函数转化成区间 0 ，l 】之间的值，其具体表示如下： 蹰( ) = 丽1 啪删= 世帮“。“” ( 2 1 8 ) ( 2 1 9 ) 式中r e 0 ，1 为均匀分布的随机数。通过这种方式，可以将妇( f ) 限制在集合 0 ，1 ) 中。需要说明的是，在基本粒子群算法中( f ) 表示速度，能够对当前位置勃( f ) 的 方向和位置随机产生一定的影响，使得算法在给定区域上进行搜索。而在二进制编 码的粒子群算法中，( f ) 仪表示一个概率，即粒子的每一维分量的取值以踞( ( f ) ) 的概率取l ，以l s i g ( v ，d ( t ) ) 的概率取0 。这样，可以定义每一位的改变概率： p ( h ) = s i g ( y 耐) ( 1 一s i g ( 1 ，耐) ) ( 2 2 0 ) 为了防止s i g m o i d ( x ) 函数饱和，可以将( f ) 限制在【4 0 ，+ 4 o 2 _ f 日j 。 二进制算法解决用二进制编码表示解空| 日j 的优化问题，使得应用范围扩展到离 散空问，特别是一些组合优化问题。 2 6 小结 本章详细地介绍了粒子群优化算法的基本原理，分析了算法流程，还进一步分 析了标准粒子群优化算法，重点研究了算法的参数选择，着重分析了种群大小、惯 性权重、学习因子等参数对算法性能的影响。对这些参数规律的认识，有