（计算数学专业论文）改进的粒子群优化算法.pdf

两北大学硕二【：学位论文 摘要 粒子群算法( 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 ) 是一种新兴的演化算法。 该算法是由j k e n n e d y 和r c e b e r h a r t 于1 9 9 5 年提出的一种基于群智能的随机 优化算法。因其概念简单、参数较少、易于实现等特点，自提出以来已经受到国 内外研究者的高度重视并被广泛应用于许多领域。 本文给出了几种改进的粒子群算法，主要工作概述如下： 第一，由于基本粒子群算法随机性较强，使其存在易陷入局部最优导致的收 敛变慢、精度低等问题。本章针对此问题，提出一种改进算法，将基本粒子群算 法粒子行为基于个体极值点和全局极值点变化为基于个体极值中心，并且按一定 概率选择其他粒子的个体极值点，使粒子能够获得更多信息来调整自身状态。本 文提出的粒子群算法，在相关的基准( b e n c h m a r k ) 函数的数值实验中表现出了 令人满意的优化性能。 第二，提出一种飞行时将自适应调整的粒子群算法。该算法在粒子群进化过 程中根据进化代数增大自适应的调整粒子的飞行时间，从而克服了传统粒子群算 法中粒子飞行时间固定为1 导致的粒子在迭代后期搜索性能下降的困难。 关键词：粒子群算法群智能约束优化惯性权重收敛性 两北火学硕上学位论文 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 ) i sanewe v o l u t i o n a r yc o m p u t a t i o n t e c h n i q u e ，i n s p i r e db ys w a r mi n t e l l i g e n c eo fb i r df l o c k i n g ，i tf i r s t i n t r o d u c e db yj k e n n d e ya n dr c e b e r h a r ti n1 9 9 5 p s oi 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 ，s oi th a sa t t a c hg r e a t i m p o r t a n c et or e s e a r c h e r sh o m ea n da b r o a da n df o u n da p p lic a t io n sinm a n y a r e a ss i n c ei t si n t r o d u c e d s e v e r a lc l a s s e so fi m p r o v e dp s oarep r o p o s e di nt h i sp a p e r t h em a i n w o r k so ft h ed is s e r t a ti o ncanb es u m m a r iz e da sf o ll o w s ： f i r s t ，p s oa l g o r it h mr a n d o m n e s siss t r o n g e r ，t oi m p r o v et h ep s o a l g o r i t h mw h i c hi san ewp o p u l a t i o nb a s e do p t i m i z a t i o na l g o r i t h ma g a i n s t t r a p p i n gi n t ol o c a lm i n i m a ，s l o w i n gc o n v e r g e n c ea n dl o wa c c u r a c y a m o d i f i e dp s oa l g o r i t h mi sp r o p o s e d anewv e c t o rn a m e dt h ea v e r a g el o c a l b e s tp o s i t i o ni sp r o p o s e dt or e p l a c et h el o c a lb e s to ft h et r a d i t i o n a l v e l o c i t y ，a n dt h eg l o b a lb e s tp o s i t i o ni sr e p l a c e db yt h el o c a lb e s t p o s i t i o no fo t h e rp a r t i c l e s o n ep a r t i c l ec a na c q u i r em o r ei n f o r m a t i o n o ft h eo t h e r st oa d j u s ti t sm o v e m e n t t h er e s u l t ss h o wt h ee f f e c t i v e n e s s o ft h ep r o p o s e dm e t h o d s e c o n d ，am o d i f i e dp s oa l g o r i t h mw i t hf l y i n gt i m ea d a p t i v ea d j u s t e d i sp r o p o s e d t h ef l y i n gt i m eo fe v e r yp a r t i c l ei nt h i sa l g o r i t h mi s a d a p t i v ea d j u s t e di ns p a c ew i t ha d d i t i o no ft h ee v o l u t i o n a r yg e n e r a t i o n s ： t h u s ，t h ea l g o r i t h mo v e r c o m e st h ed i f f i c u l t yo ft h et r a d i t i o n a lp s ot h a t t h ep a r t i c l e sa b i l i t yo fs e a r c h i n gi sd e c r e a s i n gd u r i n gt h el a s tt i m e o fi t e r a t i o n ，w h i c hi sc a u s eb yt h ef l y i n gt i m eo fe v e r yp a r t i c l ei sf i x e d o no n e 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 s w a r mi n t e l l i g e n c e c o n v e r g e n c e i n e r ti aw e i g h tc o n s t r a i no p t i m i z a t i o n l i 西北大学学位论文知识产权声明书 本人完全了解学校有关保护知识产权的规定，即：研究生在校攻 读学位期间论文工作的知识产权单位属于西北大学。学校有权保留并 向国家有关部门或机构送交论文的复印件和电子版。本人允许论文被 查阅和借阅。学校可以将本学位论文的全部或部分内容编入有关数据 库进行检索，可以采用影印、缩印或扫描等复制手段保存和汇编本学 位论文。同时，本人保证，毕业后结合学位论文研究课题再撰写的文 章一律注明作者单位为西北大学。 保密论文待解密后适用本声明。 学位论文作者签名：王蝼指导教师签名： 纠年多月凋护存石月 西北大学学位论文独创性声明 本人声明：所呈交的学位论文是本人在导师指导下进行的研 究工作及取得的研究成果。据我所知，除了文中特别加以标注和 致谢的地方外，本论文不包含其他人已经发表或撰写过的研究成 果，也不包含为获得西北大学或其它教育机构的学位或证书而使 用过的材料。与我一同工作的同志对本研究所做的任何贡献均已 在论文中作了明确的说明并表示谢意。 学位论文作者签名：躲 、厂 如口! 年6 月日 西北大学硕士论文 引言 群体智能算法( s w a r mi n t e l l i g e n c e a l g o r i t h m ，s i a ) 的研究开始于2 0 世纪9 0 年代，其基本思想是模拟自然界生物的群体行为来构造随机优化算法仉”l ，通常 单个自然界的生物不是智能的，但是整个生物群体却表现出处理复杂问题的能 力，群体智能算法就是模仿这些生物的团体行为并把它应用于人工智能问题中， 其中粒子群优化算法( 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 ) 就是群体智能算法的 一种，它是由美国社会心理学家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 在1 9 9 5 年提出的，其基本思想是对鸟群、鱼群的觅食过程中的迁徙和聚集的行 为模拟，并利用了生物学家f r a n k h e p p n e r 的生物群体模型i 6 i 。p s o 算法是一 种基于群体智能的随机优化技术，相对于遗传算法而言，二者都是基于群体的迭 代搜索，但是p s o 算法没有交叉、变异算子，粒子群优化算法是通过个体之间 的协作来搜寻最优解，它利用了生物群体中信息共享的思想，其概念简单，易于 事项，同时又有深刻的智能背景，即适合科学研究，又特别适合工程应用。因此， p s o 算法一提出，就引起了众多学者的关注，并在短短几年的时间出现了大量的 研究成果【7 , s l 。 本文共分五章，内容安排如下： 第一章简要介绍粒子群算法模型的背景及基本原理。同时给出了粒子群算 法两种最常见的数学描述，并介绍了近年来粒子群算法的几种改进。最后介绍了 粒子群算法在现实问题中的应用。 第二章介绍了基本的粒子群算法、随机性算法的收敛准则以及粒子群算法 的收敛性。 第三章基本粒子群算法存在易于陷入局部最优导致的收敛精度低和不易收 敛等缺点，提出了一种改进的粒子群算法，并对改进的算法作了理论分析和数值 仿真。 第四章为了改善粒子群优化算法的搜索性能，提出了一种飞行时间自适应 调整的粒子群算法，并对改进算法做了数值仿真。 第五章总结全文，并提出了进一步需要解决的问题。 两就大学碗上论文 第一章粒子群算法 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 ) 是由k e n n e d y 和 e b e r h a r t 等人于1 9 9 5 年提出的一类模拟群体( s w a m ) 智熊行为的优化算法。 这类算法的仿生基点是：群集动物( 如蚂蚁，鸟、鱼等) 通过群聚面有效的 爨食窝遴避逡稳。在这类嚣俸懿动秘皆，每个令髂懿行失楚建立在群体行为静基 础之上的，即在整个群体巾信息是麸亭的，而且程个体之间存在着信息的交换与 协终。如在蚁群中，当每令个体发现食糖之后，它褥通过接皴或纯学镶号来招募 闻伴，使整个群落找到食源；在鸟群的飞行中。每只鸟在初始状态下娥乎随机位 鬣，且朝各个方向随机飞行，但随着时间推移，这些初始处乎随机状态的鸟通过 赣重学习( 藤器缳踪) 鑫缀织豹聚集戏一个令套豹群落，莠叛耱霹豹逮菠赣着稳 嗣的方向飞行，最终整个群落聚集在同一位置食源。这魑群集动物所表现的 键施常称为“嚣体智能”，它可表述终：一组相嚣之闯可以避行直接逶讯或间接 通讯( 通过改变局部环境) 的主体，能够通过合f # 对问题进行分布求解。换言之， 组无智能的盘体通过合作表现出错能行为特征。粒子群优化算法就悬以模拟鸟 懿群集餐笺笼耱薤，浚求熬连续交鬃傀纯羯瑟蔻旁系戆一耱倪苇| ：霎法。 1 2 粒予群算法基零原理 粒子群优化算法是蕊于群体的演化算法 1 6 i 蛸1 ，其思想_ 来源于人工生命和演 化誊 算理论。r e y n o l d s 对鸟群飞季亍的疆究发现，鸟仅仅是逡踪它有袋数量戆邻 屠，但最终的整体结果怒整个鸟群好像在一个中心的控制乏下，即复杂的全局 行为是由简单规则的相曩作用引起的。 p s o ( 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 的一 个蒸本穰念。凌粒子群黪法中，每令稳铑海题静霹行瓣都楚羧索空蠡唾鹣一只鸟， 2 西北大学硕士论文 我们把它称之为“粒子”( p a r t i c l e ) 或“主体”( a g e n t ) 。所有粒子都有一个 被目标函数决定的适应值，并且每一个粒子还有一个速度矢量来决定下一个时刻 该粒子位置。与其他算法的不同之处在于粒子群算法依靠了各个粒子之间信息的 交换，从而每个粒子根据自己的经验和整个粒子群的共享信息来决定它下一个位 置。具体地说，每个粒子通过自己的经验和整个粒子群的最好位置或者它的邻域 中最好的位置来调整速度方向，从而使得每个粒子飞向最优位置。优化搜索正是 在由这样一群随机初始化形成的粒子而组成的一个群体，以迭代的方式进行的。 1 1 1 原始粒子群算法 基本的粒子群算法中，粒子群有n 个粒子组成，每个粒子的位置代表优化问 题在d 维搜索空间中潜在的解。粒子根据如下3 条原则来更新自身状态： ( 1 ) 保持自身惯性； ( 2 ) 按自身的最优位置来改变状态； ( 3 ) 按群体的最优位置来改变状态。 假设在一个d 维的目标搜索空间中有n 个粒子，每个粒子的位置表示一个潜 在的解。用五一“l ，而2 ，场) ，i 一1 ，2 ，一表示第i 个粒子的位置向量，其中 he 1 。，】，d e 1 , d l 。将x ；带入目标函数f ( x ) 就可以计算出其适应值( x ；) ， 根据适应值的大小即可衡量z ；的优劣。用k 一“。，坼：，) ，i - l 2 ，厅表示 第i 个粒子飞行的速度向量，用层一( n l ，p j 2 ，肋) ，i - 1 ，2 ， 表示第i 个粒 子迄今为止搜索到的最好位置，也称为个体极值p 。用只一0 p | 2 ，p 罩d ) 表 示整个粒子群迄今为止搜索到的最优位置，也称为全局极值g 。由文献 4 4 知，所有粒子i 根据下面公式来更新自己的速度和位置： - + c l ( p 甜一x i d ) + c 2 ，2 p 州叫i d ) ( 卜1 ) 】- x w + v “ i l 2 ，厅d 一1 ，2 ，d ( 1 2 ) 其中c l 和c 2 为学习因子，通常为正常数，学习因子使粒子具有自我总结和向 群体中优秀个体学习的能力，从而向自己的历史最优点以及群体内或邻域内历 史最优点靠近，c l 和c 2 通常都等于2 ，不过在文献中也有其他的取值；与r 2 为 3 西托天学顼士论文 翡个独立豹髓枫效，都服从o l 之裁静均匀分布；另羚为了控测鼍和形跃出边界， 需要用x 。和p k 来控制a 公式( 卜1 ) 巾主要逶避三部分来访算粒子薪的速发：粒孑上一次豹速度，当 前位置与自己簸好位置之间的距离，当前位置与群体最好倥鬣之间的距离。而公 式( 卜2 ) 是计算粒子新的能覆。通过这两个公式，就能决定下一步粒予的运动位 嚣。弩戳垂黼2 1 形象袭零： 圈2 h 粒予嚣算法壤理演霹圈 如果从社会学的角度来看明，公式( 1 - 1 ) 的第一部分称为记忆项，液示上次 速度大小和方向的影响；公式( 卜1 ) 第二部分称为自身认知项，是从当前点指向 歉予自己最好位置静一个矢量，表承粒子的动偌来源于鸯纛检验的部分；公式 ( 1 1 ) 第三部分称为群体认知项，是一个从当前点指向群体域好点的一个矢量， 爱浚了粒子耀貉羁会终弱知识夔共事。粒子裁是遴过自己夔经验窥固转巾最好戆 缀验来决定下次的运动。这点与人类的决策锻类似，人们通常也是通过综合自 己的信息和从外部环境得到的信息来f # 出决策的。 1 1 。2 标准鞍子群算法 因为公式( 卜1 ) 中由三部分构成【撕l ：第一部分是粒子的上次速度，也就是 记忆顼，瑟瑟瓣顼分鬟憝自身谖舞矮秘群体莰熊矮。s h i 耪e b e r h a r t 发瑗懿莱 没有后面的两项，粒子将保持初始速度不变飞向下一个位鬣，永远不会停止，直 戮飞舞边界上。这样的粒子裁不可怒蓐在最撬德经置上。 另一方面在公式( 1 - 1 ) 中如采没宥记忆项，那么粒子的遴度仅仅取决与粒子 的自身认知项和群体认知项，速度没了记忆性。假设在开始的时候，某个粒子正 辩程整个粒予群最好豹您黉土，那么这今粒子将缳持这次懿袋置不交，麓翻出理 4 西北大学硕士论文 新的一个最好的位置替代这个位置。同时，每个粒子将向自身最好的位置和群体 最好的位置方向飞去。在这种情况下，粒子群的每个粒子逐渐地向当前最好的位 置飞去，直到出现新的最好位置，然后粒子群又向这个位置飞去。所以可以发现 没了记忆项，粒子群算法的搜索空间在迭代中逐渐衰退，这就和局部搜索算法很 类似了。只有当全局最好的位置包含在初始的搜索空间的时候，才有可能找到最 优位置。这样的话，算法性能在很大程度上要依靠初始化值了。这就是说明没有 了记忆项，粒子群算法实际上只具备了局部搜索能力。从另一方面来说，记忆项 体现了粒子群算法的全局搜索能力。 所以在粒子群算法中如何体现和平衡局部搜索能力和全局搜索能力就是非 常重要的。于是基于前面原始的粒子群算法，s h i 和e b e r h a r t ! “l 提出了具有惯 性权重的标准粒子群算法。他们引入了一个惯性权重w 在记忆项，以起到权衡全 局搜索能力和局部搜索能力。惯性权重m ，可以是一个固体的数，也可以在算法运 行中按某种规律变化。于是公式( 1 - 1 ) 和( 1 - 2 ) 可以修改成为以下两个新的公式： - + c 1 ( p “一h ) + c 2 ，2 ( p 一- x u ) ( 卜3 ) o _ _ z u + 1 0 f - 1 2 ，打d - 1 2 ，d ( 1 4 ) w 为非负数，控制前一速度对当前速度的影响，w 较大时，前一速度影响较 大，全局搜索能力较强，w 较小时，前一速度影响较小，局部搜索能力较强。通 过调整w 大小来跳出局部极小值。 终止条件根据具体问题取最大迭代次数或粒子群搜索到得最优位置满足的 预定最小适应阈值。 1 1 3 粒子群算法流程 p s 0 算法具体实现步骤： s t e p1 ：( 初始化)随机生成n 个粒子，构成初始粒子群s ( o ) t t x ( 0 ) ，矿( o ) ， y ( o ) ( 墨( o ) ，z 。( 0 ) ) ，y ( o ) 一似( o ) ，k ( 0 ) ) ；置k ：2 0 ； s t e p2 ：( 个体评价) 计算每个粒子的适应值，记五 ) - ，“弛) ) ( i l 2 , ，厅) ； s t e p3 ：( 种群演化) 3 1 计算p ) 及g 仲) 西北大学硕士论文 ( 1 ) 求出p 。作) 及p 一，即f ( e i ”- r a i n f i ( k ) ； ( 2 ) 求出p 罅) 及g ，即f ( p j 0 ) ) - r a i n f ( p j 0 ) ) - r a i n p h 3 2 更新x ； ) 和咋 ) 对每个粒子毛 ) t t ) ，v i ( k ) ，令 + 1 ) 一m o ) + c l r , c o “( 七) 一屯仲) ) + c 2 r 2 ( p 一 ) 一 ) ) ( 七+ 1 ) 峨甜( 七) + ( 七) i 一1 2 ，厅d - 1 ，2 ，d 从而生成下一代粒子群体s ( k + 1 ) 一tx ( k + 1 ) ，y o + 1 ) ， s t e p4 ：( 终止检验) 若终止条件满足，则停机并输出x ( k + 1 ) 中最优位置作 为近似解；否则， 置k ：= k + l ，转步2 。 粒子群算法的流程图如下： 初始化粒子群 计算各个粒子的适应值 根据粒子的适麻值更新t , b e s t ，g b e s t 根据公式( 卜3 ) 和公式( 1 - 4 ) 更新粒子群 的速度和位置 达到停止准则 是 结束，输出最后结果 粒子群算法流程图 团 6 两北大学硕士论文 1 3 粒子群算法的研究进展 自k e n n e d y 和e b e r h a r t 提出p s o 算法，吸引了不少研究者。s h i 等引入惯性 权重形成了目前的p s o 基本算法，并对p s o 模型中参数选择做了详尽阐述。 k e n n e d y t 9 1 及s u g a n t h a n t ”1 分别从邻域算子角度分析了p s o 算法性能，c l e r c t l l i 等 给出了p s o 算法比较完整的理论分析，文献【1 2 】比较了p s o 与标准g a 的差别。 上述研究表明，p s o 在迭代早期性能优异，但在几个实际优化问题中当逼近最优 解时表现不尽人意。由于很多研究员对粒子群算法进行了各种各样的改进，并把 各种创新的思想也不断的融入p s o 算法中。 目前，对粒子群算法的改进主要体现在以下几个方面；增加惯性权重和收敛 因子；依据一定的标准为整个群体或某些粒子的状态两重新赋值；与进化计算技 巧结合；使用新的位置和速度更新公式和新的群体组织机构。本节重点讨论一些 比较典型的p s o 算法改进方法及其效果。 1 2 1 粒子群算法的改进 带收敛因子粒子群算法 为了控制粒子群的收敛性，很多学者引进不同的参数。c l e r c ( 1 9 9 9 ) i u i 对 粒子群算法的数学理论研究发现可以引进一个参数约束因子。约束因子可以起 到和惯性权重一样的作用。c l e r c1 1 3 1 1 4 1 的p s o 算法两个基本公式可以修改为如下； - 0i x ( v u + c l r l ( p “一】0 ) + c 2 r 2 ( p 一+ 工甜) ) ( 1 5 ) 其中新引入的约束因子z 可以用下面的公式计算出来： z 瓦而2 ( 1 6 7 其中妒一c l + c 2 ，妒 4 通过数值实验发现一般情况下妒设为4 1 ，则z 就可以由公式( 1 - 6 ) 计算得 到为0 7 2 9 。实验结果表明，与使用惯性权重的粒子群算法相比，使用收敛因子的 粒子群优化算法有更快的收敛速度。其实只要恰当的选取h ，、c t 、c ：的值，两种 算法是一样的，因此带收敛因子的粒子群优化算法可被看作带惯性权重的算法的 7 西北大学硕士论文 一个特例。同时这也说明，恰当选择算法的参数值可以改善算法的性质 杂交( h y b r i d ) 粒子群算法 杂交p s o 组合了进化计算与p s o 的思想。a n g e l i n e 利用p s o 机理和通常为 进化计算所用的自然选择机理如g a ，最早提出了一种杂交p s o 一- h s ( h y b r i d s w a r m ) 。其原理采用了进化计算中锦标赛选择方法：每个粒子将其当前位置上的 适应度与其他k 个粒子的适应度比较，记下最差的一个得分，然后整个粒子群以 分值高低排队。在此过程中，不考虑粒子的个体极值p 妇。群体排序完成后，用 适应值高的一半粒子的位置和速度取代另外一半适应值低的粒子的位置和速度， 但是保持后面一半粒子个体最优值不变。这样构成的粒子群模型在提高收敛速度 的同时保证了全局搜索能力。通过b e n c h m a r k 函数的数值实验发现，杂交粒子群 算法比原始粒子群算法有更好的性能。 l o v b j e r g 等迸一步提出了基于繁殖和子群的杂交p s o 模型。它们在繁殖过 程中引入了繁殖概率来代替适应度。每次迭代时，依据繁殖概率在粒子群中选取 一定数量的粒子放入一个池中，池中粒子随机两两进行繁殖，产生数目相同的后 代粒子，用后代粒子代替父母代粒子，使种群数目保持不变。后代粒子的位置由 父母位置的算术。交叉”得到： c 豇d l ( j j ) - p p a r e n t i ( x f ) + 0 一p ) 。p a r e n t 2 ( x j ) ( 1 7 ) c 豇d 2 ( x j ) _ p 。p a r e n t 2 ( x j ) + ( 1 一p ) p a r e n t l ( x i ) ( 1 8 ) 其中p 是均匀分布在o - 1 之问的随机数。而c h i l d 和p a r e n t 分别是指孩子粒子和 父母粒子的位置，后代的速度向量由父母的速度向两之和归一化后得到： c h i l d - 阶簇糍篇l 卵州形) i m 。， child：阶竺榴篙i朋mt2(1-10)parent p a r e n t 7 l 形) +2 形x ” o 杂交粒子群算法与原始粒子群算法的唯一区别在于粒子群在进行速度和位 置的更新后还要进行交叉操作，并用产生的后代粒子取代双亲粒子。交叉操作使 后代粒子继承了双亲粒子的优点，这在理论上加强了对粒子问区域的搜索能力。 例如两个双亲粒子均处于不同的局部最优区域，那么两者交叉产生的后代粒子往 8 西北丈学硕上论文 往能够摆脱局部最优，从而获得改进的搜索结果。数值实验结果表明杂交粒子群 算法比原始粒子群算法搜索速度更快，收敛精度更高。 离散二进制粒子群优化算法 基本p s o 是用于实值连续空间的优化技巧，然而许多实际问题是组合优化问 题，因而文献 1 9 提出一种离散形式的p s o 。在二进制空间中，粒子的移动是通 过翻转位置实现的，而粒子的速度描述了每次迭代改变的位数，或某粒子在t 和 t + 1 时刻的取值之间的海明距离。离散二进制p s o 的速度和位置更新公式为： 1 + c t r l q 甜一善疆) + 2 r 2 ( p 硝) f ，( ，2 s ( ) ) t h e n 1 1 e b ex - 1 0 其中，s o “。i 焉；1 f 瓦_ ) 奠j s i g m 。1 0 函数，r 2 为o 1 3 之间的随机数口速 度分量决定了位置取1 或0 的概率，越大，则取1 的概率越大。在 离散形式中，仍保留了p ，呲它起限制取1 或0 的最终概率的作用。 1 2 2 粒子群算法的应用 p s o 之所以具有吸引力的原因之一是它只有很少的参数需要调整，而且算法 只需要作细微调整即可广泛应用于不同场合。p s o 最直接的应用是解决大多数优 化问题，包括多目标优化和带约束优化问题。解决多目标优化问题的方法有：动 态邻域策略、用p a r e t o 统治概念决定粒子飞行方向、以及用s i g m a 方法寻求粒 子的最佳局部向导等。 另一更为广泛的应用是进化人工神经网络。p s o 不仅用于训练网络的权重， 而且进化网络的结构 2 0 l 。此外，在国内的一些刊物上，t 已经出现了用p s o 算法 解决整数规划【2 2 l 、非线性规划1 2 3 , 2 4 1 、多目标优化1 2 5 l 、t s p 问题1 2 6 1 等优化问题 的文章。此外，p s o 算法在系统辨识l 卅、神经网络训练等方面，也有着广泛的 应用。 9 西北= 学硕i ：论文 第二章粒子群算法收敛性分析 本章介绍了基本粒子群的原理和随机性算法的收敛准则，并进一步给出了粒子群算法 的全局和局部收敛性判据。 2 1 随机算法的收敛准则 因为粒子群算法属于随机算法，为了给出粒子群算法的收敛性分析，首先给 出随机性算法的收敛准则。本节主要参考文献 4 的内容。有关概念如下： 定义2 1 1 设有一个以集合为元素的非空类窍，如果它满足下列条件，就称 为口一域： q 3 。 如果e j 蕊j - 1 , 2 , ，贝 i u e ，3 如果e e 3 ，则e 。g 。其中，q 为全集，表示e 的补集。 定义2 1 2 设爿是定义在非空类，上的集函数，并满足条件： 对任意的e e l ，都有： 0 s ( 占) + 如果驴j ，则p ) - 0 b e ，1 ，一1 ，2 ，贝, j u e ，e l ，且最n e ，- 庐，v k ，j ，那么： p ( u ) 一芝慨) f - 1 k - 1 则我们说“是z 上的一个测度，若将式( 2 5 ) 改为： 0 u ( e 、s 1 我们称其为概率测度。 - 5 ) ( 2 - 6 ) 设q 为任意集合，是q 的子集组成的仃一域，是$ 上的概率测度，称三 1 0 两北大学硕：t 论文 元组 ( q ，韪p ) 为概率空问。 为了具体给出随机算法的收敛准则，下面给出其基本框架； 随机选择初始点z 。e s ，并冠七1 0 。 在样本空间( r “，口，心) 上生成向量磊。 计算缸+ 1 一d ( z t ，氕) ，选择段+ l ，令k 1 _ i + 1 ，并转步骤。 其中，俾“，b ，心) 表示算法在第七代的概率空间，以为口上的概率测度，口 为的某个子集的盯一域。d 为算法的迭代方式，用以产生下一个个体。 定义2 1 3 设肼为r 4 的子集，若它满足下列条件，则称为概率测度纵的 支撑集。 纨似t ) - 1 任取点列p 。k 二肘。，对于任意收敛的子列；】；二，有昱器y ；m t 。 若，且满足，则有j l f t 。 为了保证随机算法的有效性，应保证d 所产生的新的个体应优于当前的个 体，因此，随机算法应满足下列假设： 假设2 1 1f ( d ( z ，亭) ) f ( z ) ，并且如果亭s ，则 ，( d ( z ，亭) ) s ，( z ) 随机算法的全局收敛意味着序列 ，( z i ) 应收敛于妒。其中： 妒。i n f v v ( z e s l f ( ：) t 曲，o ，由于l e b e s g u e 测度v i ，o ) t ，0 ，因此 可以避免病态情形。例如： 下列问题： r a i n ，o ) ，x s r ” 但在该情况下，可能出现病态形式，比如取函数： 西北大学硕士论文 ，l 盎器 这样，函数，的最优值为，( 1 ) i 一1 0 ，但这个点是一个间断点，其测度为0 ， 所以对于进化算法而言，几乎不可能搜索到全局最优解。 定义2 1 4 定义算法的一可接受区域如下： 凡一 z e s l f ( z ) 0 ，则有： ( 1 _ 俐) ) _ o 其中，以0 ) 是由测度心所得到的一的概率。 下面利用假设2 1 1 、假设2 1 2 ，给出随机算法全局收敛的一个充要条件。 定理2 1 1 假设目标函数，为可测函数，区域s 为可测子集，并且假设 2 1 1 、假设2 1 2 满足，设k 】矗为算法所生成的解序列，则： 舢l i m l l z k 也卜1 其中，l q z i 也】为第k 步算法生成的解钆r e 的概率。 证明：由假设2 1 1 ，如果2 i e r 。或者缸r 。，则对任意的k k ，有 z k ，风，从而； p ( z i b ) 一1 一e ( z t s 、月，) 苫1 一n ( 1 一段僻，) ) t - o 取极限，并考虑到心为概率测度，则： l 乏舰砟i r 。) 之1 一熙j = 【( 1 氆( r ，) ) + f + 工舟 西北大学硕e 论文 由假设2 2 知”删) ) l 0 因此氰 1 1 i r ap ( z je r f ) 之1 - 0 - 1 + * 证毕。 定理2 1 1 给出了随机算法全局收敛的充要条件，以下考虑局部收敛准则： 定义2 1 5 局部收敛算法是指对于测度序列缸i k 二，支撑集序列似女】孟， 除了有限个集合外，都有界且m ic s 。 按照定义，局部收敛算法的支撑集序列满足以下关系： v ( sn m ) v ( s ) 因此，局部收敛算法应满足以下假设： 假设2 1 3 对于任意的z o e s ，存在y 叫 叩 0 ，使得： p i “p ( d q ，亭) ，r 。) p ( a ，6 ) ， c a ，6 由假设2 1 3 有： p ( z 1 r f ) 2 叩 西北大学硕j ：论文 p ( z 2 也) 2 智p 0 l e r 。) 叩2 这样继续p 次可得：p ( z ，r f ) r 1 9 进而：p 0 印r 。) 一1 一以2 扣硭r ，) 1 - 0 - 1 ) 由假设2 1 1 ，2 l ，。2 ，2 ，1e l o 稠t ： p ( z 扣“也) 2 1 一( 1 一印，) 其中f o ，1 ，p 一1 。这表明解序列在印与 + 1 ) p 之间满足假设2 1 3 ，由 于：( 1 一叩9 ) 一0 ，因此定理得证。 2 2 粒子群算法的收敛性 本节来讨论粒子群算法的收敛性问题。通过考虑其是否满足假设2 1 1 、假 设2 1 2 和假设2 1 3 的条件，再由上一节中定理2 1 1 、定理2 1 2 给出其全 局收敛性及局部收敛性分析。本节主要参考文献e 4 3 5 。 定理2 2 1 基本粒子群算法满足假设2 1 1 。 矾定义函数d 为：蚓一p 惚装魄 其中，符号g ( h ) 表示基本粒子群算法的更新： x i t t - 1 ) i g 似馥) 一g l ( j ) + 9 2 ( ) + 9 3 ( x a ) g l ( h ) _ 并谴+ 聊砖 其中 9 2 0 琥) m c l _ ( m 一) 9 3 0 疆) - c 2 r 2 ( p s k 一工砖) 表示第七代时的粒子f 的位簧，按照这里定义的函数d ，基本粒子群算法 满足假设2 1 1 。 定理2 2 2 基本粒子群算法不满足假设2 1 2 证明：如果假设2 1 2 成立，则等同于证明基本粒子群算法满足下式： 1 4 两北大学硕士论文 t s u m f 上 i - 1 其中，m j j 表示算法第七代时粒子f 的支撑集。由于： ( f + 1 ) i p ) + 。l 厂h o x p “o ) 一( f ) ) + c 2 ( f p 庐o ) 一( f ” x i s o + 1 ) - 工打( f ) + v t t + 1 ) x ( t + 1 ) 一j p ) + y ( f ) 一x ( t x 痧1 + 晚) + + 弓晚 则： 一x q ) + w ( x ( t ) - x ( t - 1 ) ) - x ( t x , , , + 晚) + + 弓九 一( 1 + ，一九一九) j ( f ) 一w x ( t 一1 ) + p 妒1 + 名九 其9 - 氟一c l ，1 0 ) ；九i c 2 r 2 q ) ，因而对于第t 代时粒子f 来说，有： m i , t - ( 1 + 一魂一九k ，i , k - 1 一w x i ，j , k - 2 + a p + 九乓 - x j , i q + f f x j ，弘- 1 一x i ，j , t 一2 ) + 魂( p 一黾，_ 1 ) + 九( 弓一x i , - 1 ) ( 2 - 8 ) 其中：x i d , t - 1 表示粒子f 在第七代时的第j 维分量的值显然肘谴，表示一个咖， 屯由所确定的超矩形，其中一个端点为妈i 九- 0 ，另一个是磊ic 1 ，疵i c 2 。 当m a x ( c l l p 一而，”i ，c 2 k 一而肼。1 ) t0 5 d i a m ， ) 成c f 时，显然有： l 似啦n s ) t p 岱) 一其中d i a m j 拶) ，表示s 在第，维分量的长度。由于 而- 掣，因此2 觋l f j 上。o 。从而随着迭代此次数七的增加。v ( 肘址) c ，+ c ， 呻+ 在不断减少，其v ( u 肘啦) 并也在减少。从而v ( u m 址n s ) t v 岱) ，这表明存在 整数t ，使得当七，七时，存在集合爿c s ，使得乒l 皓口) 一o ，这表明基本粒 子群算法不满足假设2 1 2 。 由于基本粒子群算法满足假设2 1 1 ，不满足假设2 1 2 ，因此不是全局收 敛的。 两北大学硕士论文 第三章改进的粒子群算法 3 1 引言 本章针对基本粒子群算法存在易于陷入局部最优导致的收敛精度低和不易 收敛等缺点，提出一种新的改进算法并对新的改进算法做了数值实验，实验结 果表明，改进的粒子群算法防止算法陷入局部最优的能力和收敛解的稳定性都有 了明显的增强。 3 。2 改进的粒子群优化算法 基本粒子群算法存在易陷入局部最优导致的收敛变慢、精度低等问题，影响 收敛速度的主要原因在于它的随机性较强，使寻优过程沦为“半盲目”的状态， 从而减缓了收敛速度。本章针对此问题，将基本粒子群算法粒子行为基于个体极 值点和全局极值点变化为基于个体极值中心，并且按一定概率选择其他粒子的个 体极值点，使粒子能够获得更多信息来调整自身状态。实验结果表明，新算法在 稳定性和收敛性上优于基本粒子群算法。 3 2 1 对个体极值( p 。) 的改进 在基本的p s o 中，每个粒子根据只和只两个量来更新自己的速度和位置， 各粒子由于受巴的影响，很快收敛到弓附近如果巴是一个局部极值，则整个 粒子群陷入局部最优，很难跳出只的束缚去发现全局最优解。由文献 3 8 知， 粒子群算法在进化初期收敛比较快，随着进化代数的增长，容易陷入局部最优， 失去了得到全局最优的能力。之所以产生上述现象是因为粒子在搜索中只能对 只和附近的区域进行详细搜索，并没有考虑到粒子群中最佳个体之外的其他 粒子所包含的信息。在实际的生物进化过程中，个体除了总结自身的实践经验和 向最优个体的学习之外，也常常模拟其他同伴的行为，尤其是在进化的初期，这 种模拟行为在个体的学习中应处于主导地位。 基于在群体搜索食物的过程中，群体中的每个个体可以从群体的新发现和群 1 6 两北犬学硕士论文 体巾的所有其他个体豹经验中受益的思想。本文设 一弛掰的改进豹计算格式。 对基本粒予群中的个体极值p o 避行如下改进： - ，i ，砟2 ，尹，彗) ，一l 2 , ，疗 其中岛- ( p l ，+ p 2 ，+ + p 町) 择 ，- 1 ，2 ，d ( 3 一1 ) 改进后的遮度更新操作： 一哪+ c i r l ( p - x 鲥) + c 2 r ：州嘞 ( 3 - 2 ) 将基本鞍子群算法中的p 。改为p 掰t 有以下几方面优势：从信息爨角度说， 新算法中每个粒子借鉴了其它粒子盼经验，也就怒说粒子利用筻多信意求决策自 己的行为；从行为方式上讲，粒子不辩在群最优j 和自身最优之问进行搜索，而是 夜群最霞帮较予最霞孛心穰萋之阕避移援索，改邈惹靛粒子嚣算法豹蟹必方式不 同予基本粒予群，部分粒予会在个体平均极值和全局极值之间进行邻域搜索，而 且，在收敛过程中，个体警局极值和全局极值的位置不断放粒子搜索接近，使褥 算法最终得阻收敛。 3 2 2 对全局极值( p 耐) 的改进 在逶纯避程中，粒子按定的概率，要么离娥傥个体学习，要么向笈袍个俸 学习。在进化的初期，粒子以较大的概率向种群中的其他粒予的历史最优学习， 瑟农嚣期，赠孩较大豹概搴是当翦全弱最霞令棼学习，这棒趣强了对整令空舞豹 搜索，从而增加了发现全粥最优解的机会。选择策略如下：在第t 代的进化过程 中，照枫产缴一个0 到1 之阎均匀分森的随机数r ，按公式( 3 - 3 ) 计算冠。如 果，r ，则从粒子群中除自身和最佳的粒子之外，随机选撵个粒予，以该粒 予嬲最优位鬟，记隽代替公式( 3 2 ) 中的尹砖，即按公式( 3 4 ) 瓣当翦粒 予的速度进行更新；否则按公式( 3 - 2 ) 进行更新。 冠- t g o ( 3 3 ) 一+ q r i ( p , d 一粕) + c 2 r 2 ( p 榭吖“) ( 3 - 4 ) 上妓孛t 隽当簸进化代数；g 一为最太进化代数；p 。是扶葜他粒子豹最中随机 1 7 薛托大学硕士论文 选撵的且不答予墨 3 2 3 新算法流程 步l ：( 初始化) 随机生娥n 个粒子，构成初始粒子群s o ) 一苫( o ) ，y ( o ) 其中 x ( o ) 一c 墨( o ) 爿。( 0 ) ) ，r ( o ) - 以( o ) k ( o ) ) ：鬣k ：= o ； 步2 ：( 个体谔徐) 计算每个粒子豹邂应僮，记五毡) t 歹瓴馥势( i 一1 ，2 ，弹) ； 步3 ：( 种群演化) 3 1 计算p 。髂) 及g 。0 ) ( 1 ) 袋窭藏承) 及a 一，瑟，( 辫咎势咿五辑) ； ( 2 ) 求出玫o ) 及g 妇，即( p 。体) ) i r a i n f f r ；( k ) ) 。呻n p 一 ( 3 ) 辩基本粒予群中的个体檄值p 。送行如下改避； 只- 巍毪转) 对每个粒予文琏) - t 鼍啦) ， ) 令 l 辑+ 骛一辨0 转) c 式h 咎一毛l 承努+ c 2 ，2 榭谚) 一3 套转势 x z ( k + 1 ) 喇甜(