（计算数学专业论文）关于粒子群算法改进的研究.pdf

西北人学硕士学位论文 摘要 粒子群优化算法就是智能优化算法中的一种重要方法，该算法源于对鸟群和鱼群运 动行为的模拟其特点是简单需调整参数较女收敛速度快且易于实现，在目标函数优化 神经网络训练工程实践中表现出巨大潜力 本文给出了几种改进的粒子群算法，主要工作如下： 第弋为了提高粒子群算法的全局收敛性，构造了两种改进的粒子群算法，算法一是 对当前个体极值进行随机变异，算法二是先对当前粒子进行随机变异，然后把变异后的 结果就作为该粒子的下一代两种算法的目的是增强粒子群算法跳出局部最优解的能 力通过典型函数的测试结果表明新算法在收敛速度和收敛精度方面均明显优于标准粒 子群算法和文献 3 5 】的算法，提出的新算法有效避免了早熟收敛问题，具有较强的全局 收敛能力 第二为了改善粒子群优化算法的搜索性能，提出了一种带步长因子的粒子群算法 ( p s ow i t hs t e p s - p s o ) ，对原始粒子群算法( p s o ) 作了改进，通过每次更新粒子的位置 时加入了步长因子，从而克服了原始粒子群算法中步长因子为1 导致的粒子在迭代中后 期搜索性能下降的困难本文提出的的新算法，在几个基准函数的数值实验中表现出令人 满意的优化性能 关键词：粒子群优化；群体智能；惯性因子：变异算子；步长因子 些! ! 查兰堡主堂堡堡苎 s u b j e c t o i lm o d i f i e dp 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 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 na l g o r i t h mi so n ek i n do fi m p o r t a n ti n t e l l i g e n to p t i m i z a t i o n m e t h o d s ，i n s p i r e db ys w a n ni n t e l l i g e n c eo f b i r df l o c k i n ga n df i s hs c h o o l i n g i t sc h a r a c t e r i s t i c s a r e s i m p l ea n do n l y af e wp a r a m e t e r st ob e a d j u s t e d ，f a s tc o n v e r g e n c ea n de a s y i m p l e m e n t a t i o n i ts h o w sg r e a tp o t e n t i a li nt h et a r g e tf u n c t i o no p t i m i z a t i o n ，n e u r a ln e t w o r k t r a i n i n ga n de n g i n e e r i n gp r a c t i c e s e v e r a lk i n d so fi m p r o v e dp s oa r ep r o p o s e di nt h i s p a p e r t h em a i nw o r k so ft h e d i s s e r t a t i o nc a nb es u m m a r i z e da sf o l l o w s ： f i r s t ，i no r d e rt oi m p r o v eg l o b a lc o n v e r g e n c eo fp s o ，t w oi m p r o v e dp s o a l g o r i t h m sa r e p u tf o r w a r d o n ei sd o i n gr a n d o mv a r i a t i o nt ot h ec u r r e n ti n d i v i d u a le x t r e m ev a l u e t h eo t h e r i sd o i n gr a n d o mv a r i a t i o nt ot h ec u r r e n tp a r t i c l ea n dt h e np u tt h er e s u h so fv a r i a t i o na st h e n e x tg e n e r a t i o no ft h ep a r t i c l e t w oa l g o r i t h m sa r ed e s i g n e dt oj u m po u to ft h el o c a lo p t i m a l s o l u t i o n s e v e r a lt y p i c a lf u n c t i o n st e s tr e s u l t ss h o wt h a tt h en e wa l g o r i t h m s o nt h e c o n v e r g e n c er a t ea n da c c u r a c ya r es i g n i f i c a n t l yb e t t e rt h a ns t a n d a r dp a r t i c l es w a r ma l g o r i t h m a n dt h el i t e r a t u r e 3 5 】a l g o r i t h m t h en e w a l g o r i t h m sa r ee f f e c t i v eo na v o i d i n gt h ep r e m a t u r e a n dc o n v e r g e n to ng l o b a ls e a r c h s e c o n d ，i no r d e rt oi m p r o v et h ep s oa l g o r i t h ms e a r c hp e r f o r m a n c e ，a na d v a n c e dp s o a l g o r i t h mw i t hs t e pf a c t o ri sp u tf o r w a r d ，t h eo r i g i n a lp a r t i c l es w a r l na l g o r i t h m ( p s o ) h a s b e e ni m p r o v e di ne a c hu p d a t e dp a r t i c l e sp o s i t i o nt oa d da s t e pf a c t o r t h u s ，t h ea l g o r i t h m o v e r c o m e st h ed i f f i c u l t yo ft h e o r i g i n a lp s ot h a tt 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 s d e c r e a s i n gd u r i n gt h el a s tt i m eo f i t e r a t i o n ，w h i c hi sc a u s e db yt h es t e pf a c t o ro fe v e r yp a r t i c l e i sf i x e do no n e 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 so f t h e p r o p o s e dm e t h o d 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 i n e r t i af a c t o r v a r i a t i o n o p e r a t o rs t e pf a c t o r l i 西北大学学位论文知识产权声明书 本人完全了解西北大学关于收集、保存、使用学位论文的规定。 学校有权保留并向国家有关部门或机构送交论文的复印件和电子版。 本人允许论文被查阅和借阅。本人授权西北大学可以将本学位论文的 全部或部分内容编入有关数据库进行检索，可以采用影印、缩印或扫 描等复制手段保存和汇编本学位论文。同时授权中国科学技术信息研 究所等机构将本学位论文收录到中国学位论文全文数据库或其它 相关数据库。 保密论文待解密后适用本声明。 学位论文作者签名：二蝉指导教师签名： 学位论文作者签名：扣矗蔓 l 指导教师签名： 洲年6 月( 均侔6 月f 严日 西北大学学位论文独创性声明 本人声明：所呈交的学位论文是本人在导师指导下进行的研究工作及取得的研究 成果。据我所知，除了文中特别加以标注和致谢的地方外，本论文不包含其他人已经 发表或撰写过的研究成果，也不包含为获得西北大学或其它教育机构的学位或证书而 使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中作了明确 的说明并表示谢意。 学位论文储躲“音 训留年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 0 ) 是1 9 9 5 年由美国普 渡大学的k e n n e d y 博士和e b e r h a r t 博士提出的1 4 1 ，该算法与蚁群算法【l 2 】( a n t c o l o n yo p t i m i z a t i o n ，a c o ) 相似，是一种基于群体智能( s w a r mi n t e l l i g e n c e ， s i ) 的优化算法脚，它是受鸟群和鱼群群体运动的行为方式启发而得到的l s , g l 。 p s o 算法作为一种新的进化算法，可用于解决大量非线性、不可微和多峰值的复 杂优化问题，并已广泛应用于科学和工程领域m ，如：函数优化，神经网络训练， 模式分类，模糊系统控制等【6 】，在实际中被证明是有效的。与基于达尔文“适者 生存，优胜劣汰”的进化思想不同，p s o 算法是通过个体之间的协作来寻找最 优解，每个个体( 粒子) 都被赋予一个随机速度并在整个问题空间中流动，个体 ( 粒子) 具有记忆功能，个体( 粒子) 进化不是通过遗传算子而是通过个体( 粒 子) 之间的合作和竞争来实现的。它利用了生物群体中信息共享会产生进化优势 的思想，其运算简单，易于实现。因此，p s o 算法一提出，就引起了演化计算等 领域的学者们的广泛关注。 本文共分为五章，具体章节安排如下： 第一章介绍了群体智能以及粒子群算法的背景和基本理论，给出了粒子群 算法的发展现状及其在现实问题中的应用，最后分析了粒子群算法的研究方向。 第二章给出了基于随机算法收敛准则的粒子群算法收敛性分析。 第三章为了提高粒子群算法的全局收敛性，提出了两种改进的粒子群算法， 并对新算法作了理论分析和数值仿真。 第四章为了改善粒子群优化算法的搜索性能，提出了一种带步长因子的粒 子群算法，并对改进的算法作了数值仿真。 第五章对本文工作进行了总结，并给出粒子群算法今后工作的研究方向。 最后是参考文献、致谢、以及作者在硕士学习阶段的科研情况。 西北大学硕士学位论文 第一章粒子群算法概论 1 1 群体智能 1 1 1 什么是群体智能 群体智能方法是在2 0 世纪9 0 年代提出的，一直受到广泛的关注。群体智能 致力于对自然界社会性生物的群体行为进行模拟，发展高效的优化算法用于解决 科学计算、社会经济以及工程应用等领域的实际问题。 群体智能方法诞生来源于某种生物社会系统，该生物社会系统的研 究集中于简单个体组成的群落与环境之间的关系，以及个体之间的互动行为。群 居个体以集体的力量进行觅食、御敌等，单个个体只能完成简单的任务，而由单 个个体组成的群体却能完成复杂的任务，这种群体所表现出来的“智能”，就称 之为群体智能( s w a r mi n t e l l i g e n c e ，s i ) 。例如，蜜蜂采蜜、筑巢，蚂蚁觅食等。 而从群居生物互相合作进行工作中得到启迪，研究其中的原理，并以此原理来设 计新的求解问题的算法被称为群智能算法。在计算智能领域中主要有两种基于群 体智能的算法，一种是蚁群算法m ( a n tc o l o n yo p t i m i z a t i o n ，a c o ) ，它是对蚂 蚁群落觅食过程的模拟，已经成功运用在很多离散优化问题上；另一种是粒子群 优化算法”，是1 9 9 5 年提出的，是一种最新的群体智能技术。 1 1 2 群体智能的特点 ( 1 ) 群体中相互合作的个体是分布的，这样更能够适应当前网络环境下的 工作状态； ( 2 ) 没有中心的控制和数据，这样的系统更具有鲁棒性，不会由于某个或 者某几个个体的故障而影响整个问题的求解； ( 3 ) 可以不通过个体之间直接通信而是通过非直接通信进行合作，这样的 系统具有个别更好的可扩展性； ( 4 ) 系统中每个个体的能力十分简单，这样每个个体的执行时间比较短， 并且实现也比较简单，具有简单性。 群体智能技术的应用领域已扩展到多目标优化、数据分类、模式识别、生物 系统建模、信号处理、决策支持以及仿真和系统辩识等方面m 1 ”4 ”。 西北大学硕士学位论文 因此，群体智能理论及其应用研究具有相当重要的学术意义和现实价值，已 成为国际上的研究热点之一，它也将是计算机研究发展的一个重要方向。目前国 际上有大量的杂志和会议发表群体智能理论研究及应用的相关成果，其中国际顶 级杂志包括：i e e et r a n s a c t i o no ne v o l u t i o n a r yc o m p u t a t i o n ( i e e e ) ，e v o l u t i o n a r y c o m p u t a t i o n ( m i t p r e s s ) ，n a t u r a lc o m p u t a t i o n ( s p r i n g e r ) 等；国际顶级学术 会议主要有：i e e es w a r mi n t e l l i g e n c es y m p o s i u m ，s p e c i ms e s s i o no ns w a r m i n t e l l i g e n c eo f 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 ，a n tc o l o n yo p t i m i z a t i o na n d s w a r mi n t e l l i g e n c e 等。 1 2 粒子群算法的起源背景 粒子群优化算法( 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 3 粒子群算法的基本理论 在p s o 算法中，每个优化问题的潜在解都可以想象成d 维搜索空间上的一 个点( 鸟) ，我们称之为粒子( p a r t i c l e ) ，所有粒子都有一个被目标函数决定的适 应值，每个粒子还有一个速度来决定他们飞行的方向和距离。然后粒子们就在解 空间中搜索最优位置。具体地说，每个粒子是根据自己的飞行经验和整个粒子群 目前的最优位置来调整飞行的速度，从而使每个粒子飞向最优位置。 1 3 1 原始粒子群优化算法 在p s o 算法中，首先须初始化一群随机的粒子，然后通过迭代找到最优解。 西北大学硕士学位论文 假设在一个d 维搜索空间中，p s o 算法初始化为m 个随机粒子。在每一次迭代 过程中，粒子通过跟踪两个极值来更新自己【4 1 ：第一个就是粒子本身目前所找到 的最优解，叫做个体极值p 6 ，可以看作是粒子自己的飞行经验；另一个极值是 整个粒子群目前所找到的最优解，叫做全局极值9 6 ，可以看作群体经验。 第f 个粒子的位置记为 = ( 而，玉：，) ，i = l ，2 ，m ：第f 个粒子的“飞翔” 速度记为v j = ( y f l ，u ：，) ：第f 个粒子迄今为止搜索到的个体极值表示为 p b , = ( 融。，p b , ，p ) ；整个粒子群中，所有粒子迄今为止所搜索到的全局极 值表示为g b = ( g 岛，g 岛，g b o ) ，粒子就是根据自己的经验和群体的经验来决定 下一步的运动的。由文献知，每个粒子就是按照下面公式来更新自己的速度 和位置的： 略1 = 咭+ c a ( p b 吉一) + c 2 r ( 耐一) ( 1 - 1 ) 搿1 = + 略1 ( 1 - 2 ) 式中： f _ 1 ，2 ，川，m 是群体中的粒子数； d = 1 ，2 , - - - , d ，d 是解空间的维数，即自变量的个数； k = l ，2 ，l 是迭代次数； 苟表示第k 次迭代粒子i s 置矢量的d 维分量； 诟表示第七次迭代粒子f 速度矢量的d 维分量； p 砧表示第k 次迭代粒子f 个体最好位置矢量( p b ) 的d 维分量； g 嘭表示前七次迭代粒子群最好位置( 曲) 矢量的d 维分量； c 1 和c 2 为学习因子，通常为正常数，分别调节向加和g b 方向飞行 的步长，学习因子使粒子具有向自我总结和群体中优秀个体学习的 能力，他们通常都取2 ； 蜀和r 是介于 0 ，1 】区间的随机数； 西北大学硕士学位论文 “。，。】，根据实际问题来确定粒子的取值范围； - 缸，v m 。】，速度的最大值v m 。根据粒子的取值区间长度来 确定。 由上两式可知，粒子f 的新的速度的计算主要由三部分决定：粒子f 前一次的 速度屹，粒子f 当前位置与自己历史最好位置之间的距离( p 碓一k ) ，粒子f 当 前位置与群体目前最好位置之间的距离( g 砧一t ) 。通过这两个公式，就可以 确定出粒子i 的新位置。粒子移动原理可由图1 3 1 表示： 图1 - 3 1 ：粒子群移动原理图 f i g 1 3 1m o v i n gp r i n c i p l eo f p a r t i c l e s 如果从社会学的角度来看呻l ，公式( 1 - 1 ) 的第一部分为粒子的先前速度， 称为记忆项；第二部分为“认知( c o g n i t i o n ) ”部分，表示粒子自身的经验；第 三部分为“社会( s o c i a l ) ”部分，表示粒子问的信息共享与相互合作，它引导粒 子飞向粒子群中的最优位置。公式( 1 - 1 ) 的第一项对应多样化( d i v e r s i f i c a t i o n ) 的特点，第二项、第三项对应于搜索过程的集中化( i n t e n s i f i c a t i o n ) 特点，因此 这三项之间的相互平衡和制约决定了算法的主要性能。 1 3 2 算法的基本流程 p s o 的具体实现步骤如下： 西北大学硕士学位论文 步骤1 、在初始化范围内，对粒子群进行随机初始化，即设置粒子的初 始位置、初始速度和种群规模； 步骤2 、计算每个粒子的适应值； 步骤3 、更新每个粒子的个体最优加和整个群体的全局最优9 6 ； 步骤4 、根据式( 1 - 1 ) 和式( 1 - 2 ) 对粒子的速度和位置进行更新； 步骤5 、判断是否满足终止条件。如果满足，转步6 ；否则，转步2 ， 继续迭代。 步骤6 、输出全局最优曲，算法运行结束。 p s o 算法的流程图如下： p s o 算法的流程图 1 3 3 标准粒子群算法 为了改善算法的收敛性能，s i n 和e b e r h a r t 在1 9 9 8 年的论文中引入了惯性 西北大学硕士学位论文 因子的概念邮】，将速度更新公式( 1 - 1 ) 改为( 1 - 3 ) 所示： y = w 吒+ c , r l ( p 酷一k ) + c 2 r 2 ( g b j 一工占) ( 1 - 3 ) 搿1 = + v 2 1 ( 1 - 4 ) 这里，w 称为惯性因子，其大小决定了对粒子当前速度继承的多少，合适的 选择可以使粒子具有均衡的探索和开发能力。即也就是起到权衡全局搜索能力和 局部搜索能力，w 较大时，前一速度影响较大，全局搜索能力较强：w 较小时， 局部搜索能力较弱。 目前，对于p s o 算法的研究大多以带惯性因子的p s o 算法为基础进行分析、 扩展和改进的，因此把这种带惯性因子的p s o 算法称为标准p s o 算法；而将前 述的p s o 算法称为原始p s o 算法，其实原始p s o 算法就是惯性因子w = 1 的特 殊情况。 1 3 4 粒子群优化算法的参数选择 粒子数：粒子数应根据具体问题而定，一般取2 0 一5 0 。不过对于比较难 的问题或者特定类别的问题，粒子数可以取到1 0 0 或2 0 0 。 粒子的长度：这是由优化问题决定，就是问题解的长度。 粒子的范围：由优化问题决定，每一维可设定不同的范围。 粒子的最大速度：它决定粒子在一个循环中最大的移动距离，该值一般 由用户自己设定。最大速度是一个非常重要的参数。如过最大速度的值取得太大， 则粒子们可能就会飞过优秀区域，如果太小，则粒子们就可能无法充分的探测局 部最优区域以外的区域，这样，容易陷入局部最优。假设搜索空间的第d 维定义 的区间为 一一，+ 为一 ，则通常取屹一= j | 。为一，o 1 k 0 2 ，每一维都用相 同的方法设定 5 1 。 惯性因子：它的大小决定了搜索的步伐大小，一般，在开始的时候搜索 的步伐大些这样可以加快速度，但随着迭代次数的增加让步伐变小进行局部搜索 这样可以避免错过最优解，从而提高解的精度。 学习因子：自身因素参数c l 和社会因素参数c 2 一般要根据经验值来定。 在优化问题中通常取2 ，不过在文献中也有取其他的值。但是一般c l 等于c 2 并且范围在0 和4 之间。 西北大学硕士学位论文 终止条件：一般设为最大循环数或计算精度，这个终止条件通常要由具 体的问题确定。 1 4 粒子群算法的研究进展和主要应用 1 4 1 粒子群算法的研究现状和进展 自p s o 提出以来，由于它的计算快速性和算法本身的易实现性，引起了国 际上相关领域众多学者的关注和研究，其研究大致可以分为：参数选取、拓扑结 构、与其它进化技术的融合及应用。下面就这三方面的研究情况做一简单介绍。 一、基于p s o 参数的研究 对p s o 参数的研究，主要针对惯性因子w ，学习因子c 1 和c ：，其中对p s o 参 数取值的改进技术中研究最多的是关于惯性因子w 的取值问题。w 表明粒子原先 的速度能在多大程度上得到保留，体现了局部搜索能力和全局搜索能力的比例关 系。其类似于模拟退火中的温度，较大的w 可以增强p s o 的全局搜索能力，而 较小的w 能加强p s o 算法的局部搜索能力咐】。因此，随着迭代次数的增加，惯 性因子1 4 应不断减小。目前对，的取值大致有三种取法：固定惯性因子取值法 1 “、线性自适应惯性因子取值法【” 】、非线性惯性因子取值法 2 0 a 2 1 脾艄l 。 原始的p s o 算法可认为是惯性因子w 为1 ；后来，s h i 等7 1 提出按照线性递减 规律改变惯性因子w ，其具体计算公式为： “r ) ：型( 一) + ( 1 - 5 ) t m l x ( 其中为最大惯性因子，为最小惯性因子，t 为当前迭代次数，f 一为 算法总的迭代次数) ：文献”l 试验了将w 设置为从0 9 到0 4 的线性下降，使得 p s o 在开始时探索较大的区域，较快地定位最优解的大致位置，随着w 逐渐减小， 粒子速度减慢，开始精细的局部搜索。为了改善算法的收敛速度和对多维空间的 精细搜索能力，c h a t t e l j e e 等啪1 提出非线性惯性因子的p s o ，其惯性因子的自适应 变化式w 为： w ( t ) _ 【筹】( 一) ( 1 - 6 ) 西北大学硕士学位论文 在式( 1 - 6 ) 中，n 为非线性调节指数，对，l 取值为0 6 ，0 8 ，1 0 ，1 2 和1 4 等作了实验研究，给出不同指数取值时，惯性因子随进化迭代次数的变化规律。 其中，当, 1 1 取值为1 0 时，惯性因子为线性变化规律。随后，c l e r k t 2 4 m ”1 在p s o 算法中引入了另一个参数系数收缩因子，采用收缩因子能够确保算法的收 敛。收缩因子模型如下所示： 略。= a 【吃+ c , e l ( p b 考一) + q r ( 彬一) 】 ( 1 - 7 ) 口2 百：j ：丽2 ，其中2 q + c 2 ，矽 4 1 8 通常将矿设为4 1 ( 岛= q 0 5 ) ，其实只要恰当选取w 、q 、c 2 的值，带惯 性因子的p s o 算法与带收缩因子的p s o 算法一样，从数学上分析，这两个参数惯 性因子w 和带收缩因子t 2 是等价的前者是为了提高算法的收敛性能，平衡收敛 的全局性和收敛速度，后者是为了保证算法的收敛性。 二、基于拓扑结构的研究 p s o 算法有全局版本和局部版本，这两个版本的差别在于粒子的邻域不同， 即与各粒子直接连接的粒子数不同。局部p s o 的粒子，邻域仅为其两边有限的 几个粒子，而全局p s o 的邻域则为该群体所有粒子。如此看来，全局p s o 可看 成是局部p s o 的特殊情况。研究发现，全局p s o 收敛较快，但易陷入局部最优， 而局部p s o 可搜索到更优的解，但速度稍慢。此外，为提高p s o 的性能，研究 者又设计了许多不同的邻域结构。s u g a n t h a n 在p s o 算法中引入了空间邻域的概 念j ，将处于同一个空间邻域的粒子构成一个子粒子群分别进行进化，并随着进 化动态地改变选择阀值以保证群体的多样性；k e n n e d y t 2 7 1 引入邻域拓扑的概念来 调整邻域的动态选择，同时引入社会信念将空间邻域与邻域拓扑中的环拓扑相结 合以增加邻域间的信息交流提高群体多样性。 三、与其它进化技术( 优化算法) 融合 p s o 是一种随机优化技术，其实现技术与遗传算法非常相似，所以一些研究 者在p s 0 算法中引入了选择、交叉、变异算子。l o v b j e r g 等提出带交叉算子的 p s o f 2 ”，在粒子群每次迭代后，按几率在粒子问交换各维，通过交叉来生成更优秀 西北大学硕士学位论文 的粒子，这个交叉概率是用户确定的，与粒子的适应值无关，h i g a s h i 等口明提出 带变异算子的p s o ，引入变异算子来增强群体多样性，避免陷入局部最优。 a n g e l i n e 1 将选择算子引入p s o 算法中，选择每次迭代后的较好粒子复制到下一 代，以保证每次迭代的粒子群都具有较好的性能。除此之外，许多研究者将p s o 算法与其它优化算法相融合，提出一些混合的p s o 算法，例如提出基于模拟退火算 法思想的p s o 算法1 、免疫粒子群优化算法1 3 2 、混沌粒子群优化算法m 1 等。 1 4 2 粒子群算法的主要应用 粒子群优化算法一提出就受到了广泛的关注，各种关于粒子群算法应用研究 的成果不断涌现，有力的推动了粒子群优化算法的研究。粒子群算法主要应用于： 函数优化、神经网络训练、模糊系统控制、生物信号识别、多目标优化等方面， 取得了很好的效果。下面就几个方面作一简单介绍： 1 ) 函数优化 a n g e l i n e 经过大量的实验研究发现，粒子群优化算法在解决一些典型的函数 优化问题时，能够取得比遗传算法更好的优化结果1 6 】s i f t 与e b e r h a r t 的试验证明， 对大多数的非线性b e n c h m a r k 函数，p s o 在优化速度和精度上均较遗传算法有 一定的改善 l ，这说明粒子群优化算法在解决实际问题时同样具有很好的应用 前景。 2 ) 神经网络训练 采用一定的优化算法进行神经网络的训练能够提高神经网络的自学习和自 组织的能力。研究表明，p s o 是一种很有潜力的神经网络训练算法，在实际应用 问题( 如运用p s o 算法训练神经网络进行医疗诊断) 取得了较高的成功率目前 正在将其推广到更多的应用领域。 3 ) 模糊系统控制 模糊控制以模糊集理论作为其理论基础，由z a d e h 教授于1 9 6 5 年提出，已 经在很多实际领域取得成功应用。 4 ) 工程应用 下面简要介绍粒子群优化算法在一些实际应用领域的进展，通过训练神经网 络，粒子群优化算法己成功应用到对医学中震颤行为的分析 3 4 1 ；将p s o 算法与 1 0 西北大学硕士学位论文 b p 算法相结合训练神经网络已用于对电动汽车燃料电池组时充电情况的模拟。 还有，p s o 算法己被美国一家公司用于各种生物化学成分的优化组合，进而人工合 成微生物p 1 ，粒子群优化算法与其他进化算法一样，可以解决几乎所有的优化问题， 或者是可以转化为优化问题进行求解的问题其中最具应用前景的领域包括多目 标问题的优化、系统设计、分类、模式识别、生物系统建摸、规划、信号处理、 决策和模拟等等。目前，在模糊控制器的设计、图象分割、e e g 信号模拟、语 音识别、烧伤诊断以及探测移动目标等方面已经有成功应用的先例1 5 1 。 1 5 粒子群算法的研究方向 粒子群算法自提出以来，在国外得到了相关领域众多学者的关注和研究， c e c 国际年会上，粒子群算法已经被作为一个独立的研究分支。据不完全统计， 短短十几年时间，国外针对粒子群算法研究已完成的博士论文就达十余篇之多： 在i e e e 的国际学术会议上，有2 0 篇左右的论文均是反映粒子群算法的研究成 果的。国内在该领域的研究则刚刚起步，深入的研究和应用还很少，已发表的论 文也不多，p s o 算法的研究还有大量工作要做，主要的研究方向有如下几个方面： ( 1 ) 粒子群算法的改进 标准粒子群算法主要适用于连续空间函数的优化问题，如何将粒子群算法 应用于离散空间优化问题，特别是一类非数值优化问题，将是粒子群算法的主要 研究方向。另外，充分吸引其他进化类算法的优势，以改进p s o 算法存在的不 足也是值得研究的问题。 ( 2 ) 粒子群算法的理论分析 到目前为止，p s o 算法的分析方法还很不成熟，存在许多不完善之处。如 何利用有效数学工具对p s o 算法的运行行为、收敛性以及计算复杂性进行分析 也是目前的研究热点之一。 ( 3 ) 粒子群算法与其他进化算法的比较研究 目前，进化算法的研究在理论和应用两方面都得到迅速发展，效果显著， 其中比较研究成熟的有遗传算法、蚁群算法等，而粒子群算法是一个新兴的群体 智能算法，目前已成为进化算法的一个重要分支，如何从多方面比较各种算法从 而得到各自的特长和不足，如何吸引其他进化类算法的优势来弥补p s o 算法的 不足也是当前研究的热点之一。 西北大学硕士学位论文 ( 4 ) 粒子群算法的应用 算法研究的目的是应用，如何将p s o 算法应用于更多领域，同时研究应用 中存在的问题也是值得关注的热点。 西北大学硕士学位论文 第二章基于随机算法收敛准则的粒子群算法 收敛性分析 s o l i s 和w e t s 证明了随机优化算法以概率1 收敛于全局最优解的条件，为 了分析方便，首先给出有关随机算法的收敛准则，本章主要参考文献 4 0 j 。 2 1 随机算法的收敛准则 随机算法的基本框架如下： ( 1 ) 随机选择初始点x o z ，并设置k = 0 ； ( 2 ) 在样本空间( 掣，b ，以) 上生成向量缸； ( 3 ) 计算吒。= d 皈，炙) ，选择以+ 1 ，令k = k + l ，并转步骤( 1 ) 。 其中，( r n , b ，以) 表示算法在第k 代的概率空间，以为b 上的概率测度，口 为月“的某个子集的口域，d 是算法的迭代方法，用以产生下一代个体，为了保 证算法的有效性，应保证d 所产生的新个体优于当前个体，因此随机算法应满足 下列假设： 假设1 ：f ( d ( x ，f ) ) o ，则有凸( 1 一心( 一) ) = o 其中，a , ( a ) 是由测度以所得的彳的概率。 定义1 ：定义算法的s 一可接受区域如下： r 。= j x i ，( 工) 0 ，若算法发现r 。中的点，则称算法找到了误差为f 的可接受点。 定理1 ：假设目标函数，为可测函数，区域j 为可测子集，并且假设1 和假 设2 满足，设 ，( 黾) ：。为算法所生成的解序列，则 西北大学顶士学位论文 牌尸【以e r c 】- 1 ， 其中，p k r 】是第k 步算法生成的解 毽的概率。 也就是说，对一个随机优化算法，只要能够满足假设l 与假设2 ，就可以保 证以概率1 收敛于全局最优解。 以下分析局部收敛准则： 假设3 ：对于任意的g o x ，存在， 0 , 1 7 1 0 ，使得： i t k ( ( p ( d ( x ，f ) ，疋) p ( x ，r 。) 一，) 或( d ( x ，f ) r ；) ) 1 对于所有k 的和集合l 。= 缸x i 厂( f ( x 。) 中的x 均成立其中，p ( x ，) 表示 x 到集合彳的距离，定义为：p ( 工，_ ) 2 孵p ( z ，6 ) 下面给出随机算法的局部收敛准则： 定理2 ：假设目标函数厂为可测函数，区域j 为可测子集，并且假设1 和假 设3 满足，设 ，( 坼) ：，为算法所生成的解序列，则 骢珂 e r c 】- 1 ， 其中，? i x 。尺：】是第k 步算法生成的解坼r ：的概率，区域r ：表示某一局部极 值点的g 一可接受区域。 2 2 粒子群算法的收敛性分析 定义函数d 为 驴臆) ，翟气功v 魄 ( 2 - 1 ) 其中，符号g ( x i 。) 表示基本p s o 算法的进化方程，按照这里的定义的函数d ， 基本p s o 算法满足假设1 。 通过定理2 可以看出，当所有的微粒最终收敛于l i i n x ( t ) = p = p g 的位置时， 算法将停止运行。因此，如果算法在收敛之前没有搜索到全局( 或局部) 最优解， 将导致算法过早收敛，表明基本粒子群算法是局部收敛算法。 如果基本p s o 算法满足假设2 ，则等同于基本p s o 算法满足下式 西北大学硕士学位论文 s u m ，。 其中，m 。表示在算法第七代时微粒的支撑集，由于 x ( t + 1 ) = x ( f ) + 珊矿( f ) 一x ( t x 萌l + 唬) + 尸旃+ 0 噍 = 石( r ) + ( x ( f ) 一x ( t 一1 ) ) 一z ( f ) ( 缟+ 珐) + 只燕+ 名唬 = ( 1 + c o 一畦一唬) 五( f ) 一c o x ( t 一1 ) + + 名欢 因此，代入可以得到m t 。为 m i ，i = ( 1 + o j 一磊一如) 而，t l 一0 3 x i 。t 一2 + 办p + 唬最 = 玉，i l + ( 玉j ，i l 一再，j 一2 ) + 硝( p 一而， t i ) + 改( 只一g l , 1 k - i ) ( 2 2 ) 其中，o 破蔓c l ，o 欢兰c 2 ，t 埘表示微粒f 在第七代时第，维分量的值。 显然，m i 。表示一个由破、珐所确定的超矩形，其中一个端点为办= 珐= 0 ，另 外一个为呜= c 1 ，办= e 2 。 当m & x ( c ii p 一再肼i ，c 2 i 最一而 。i ) o 5 x d i a ( s ) 成立时， 显然有 “m 。n s ) ，其中 z ( 1 ) = ( x l ( 1 ) ，屯( 1 ) - 一，x 。( 1 ) ) ，v ( 1 ) = ( v l ( 1 ) ，v 2 ( 1 ) ，v 。( 1 ) ) ；置七：= 1 ； 步2 ：( 个体评价) 计算每个粒子的适应度值，记z