（计算数学专业论文）粒子群算法的研究及改进.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 a l g o r i t h m ，w h i c h i sak i n d o fs w a r m i n t e l l i g e n t o p t i m i z a t i o na l g o r i t h m s ，i sp u tf o r w a r db yf o r a g i n ga c to fr e s e a r c ha n do b s e r v a t i o na b o u t g r o u p so fb i r d s b e c a u s ei t sf a v o r a b l ec h a r a c t e r i s t i c s ，i t sf o c u s e db yt h em a j o r i t yo fs c h o l a r s i nr e c e n ty e a r s ，i tb e c o m e sa ni m p o r t a n tp a r to fm o d e mo p t i m i z e dm e t h o d a n ds h o w sg r e a t p o t e n t i a li nt h et a r g e tf u n c t i o n ，o p t i m i z a t i o ne n g i n e e r i n gp r a c t i c ea n ds oo n i ni t s e l f , t h e r e a r es t i l lal o to fd e f e c ti nt h e o r ya n dp r a c t i c e i nt h el i g h to ft h es h o r t c o m i n g so fp a r t i c l e s w a r m o p t i m i z a t i o na l g o r i t h mi se a s yt of a l li n t ol o c a lo p t i m u m ，a l li m p r o v 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 n dah y b r i do p t i m i z a t i o na l g o r i t h ma r eo b t a i n e di nt h i sp a p e r f i r s t ，p a r t i c l es w a r mo p t i m i z a t i o nb a s e do np e r i o de v o l u t i o n a r yt a c t i c s i nn e wa l g o r i t h m ，w h e nt h ea l g o r i t h mm a yf a l li n t oal o c a lo p t i m u mb yj u d g m e n t s ，t h e v a l u e so fs o m ep a r t i c l e sa r er e a s s i g n e db yac e r t a i np r o p o r t i o n ，s ot h ea l g o r i t h mi so u to f l o c a lo p t i m u m ，n e a rt ot h eg l o b a le x t r e m e n u m e r i c a le x p e r i m e n t sp r o v et h a tt h ec a l c u l a t i o n o fa c c u r a c ya n dc o n v e r g e n c es p e e do ft h ei m p r o v e da l g o r i t h mh a v e b e e ng r e a t l yi m p r o v e d s e c o n d ，t h eh 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 na l g o r i t h mo fp a r t i c l ea n df i s hs w a r m t h ea l g o r i t h ma n a l y z e st h er e s p e c t i v e l yf e a t u r e so fp a r t i c l ea n df i s hs w a m ：p a r t i c l es w a m a l g o r i t h mh a sf a s tc o n v e r g e n c ea n dc a nr e s e r v eo p t i m u mc o n d i t i o no fe v e r yp a r t i c l e a sa r e s u l to fi n t r o d u c i n gc o n g e s t i o nf a c t o r , f i s hs w a r ma l g o r i t h mh a st h ea b i l i t yo fg l o b a l o p t i m i z a t i o n c o m b i n i n gt h ea d v a n t a g e so ft h e m ，h y b r i do p t i m i z a t i o na l g o r i t h mb a s e do n p a r t i c l ea n df i s hs w a r m i sm a d e i th a ss a t i s f a c t o r yo p t i m i z e dp e r f o r m a n c et h r o u g ht h et e s to f t h ec l a s s i c a lf u n c t i o n k e y w o r d s s w a r mi n t e l l i g e n c e ，p a r t i c l es w a r mo p t i m i z a t i o n ，a r t i f i c i a lf i s h s w a r ma l g o r i t h m ， c o n g e s t i o nf a c t o r , s t a g eo fe v o l u t i o n 西北大学学位论文知识产权声明书 本人完全了解西北大学关于收集、保存、使用学位论文的规定。 学校有权保留并向国家有关部门或机构送交论文的复印件和电子版。 本人允许论文被查阅和借阅。本人授权西北大学可以将本学位论文的 全部或部分内容编入有关数据库进行检索，可以采用影印、缩印或扫 描等复制手段保存和汇编本学位论文。同时授权中国科学技术信息研 究所等机构将本学位论文收录到中国学位论文全文数据库或其它 相关数据库。 保密论文待解密后适用本声明。 学位论文作者签名：盈玉至指导教师签名：学位论文作者签名：堡玉兰指导教师签名： v p 7 年 i 月7 e l fc 年月7 日 西北大学学位论文独创性声明 本人声明：所呈交的学位论文是本人在导师指导下进行的研究工作及取得的研究 成果。据我所知，除了文中特别加以标注和致谢的地方外，本论文不包含其他人已经 发表或撰写过的研究成果，也不包含为获得西北大学或其它教育机构的学位或证书而 使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中作了明确 的说明并表示谢意。 学位论文作者签名： 年 巷玉毛 占月 7 日 l 西北大学硕士学位论文 1 1 群体智能 第一章绪论 1 1 1 群体智能方法的提出 人工智能经过半个世纪的发展，经历了由传统人工智能、分布式人工智能到现场人 工智能等阶段的发展。到二十世纪九十年代，一些学者开始从各种活动和现象的交互入 手，综合地由个体的行为模型开始分析社会结构和群体规律【1 1 。单个的个体只能完成简 单的任务，而由单个个体组成的群体却能完成复杂的工作，发挥其前所未有的水平，涌 现出群体智慧，即群智能研究的是自然界生物的群体所表现出来的特性。群智能的概念 最早是由b e n i 、h a c k w o o d 和w a n g 2 】在分子自动机系统中提出的。1 9 9 9 年，b o n a b e a u 、d o r i g o 和t h e r a u l a z 在( ( s w a r mi n t e l l i g e n c e ：f r o mn a t u r a lt oa r t i f i c i a ls y s t e m s 中对群智能进行 了详细的论述和分析【3 1 ，给出了群智能算法的一种定义：任何一种由昆虫群体或其它动 物社会行为机制而激发设计出的算法或分布式解决问题的策略均属于群智能算法。 虽然群智能现在还处于基本理论描述阶段，各方面的发展还非常不成熟，但在计算 智能领域中已经有了基于群智能的算法和策略，自从1 9 9 1 年f l 了c o l o m i 、d o r i g o 和m a n i e z z o 提出了模拟蚂蚁觅食行为的蚁群算法( a n tc o l o n yo p t i m i z a t i o n ，a c o ) 【4 ，5 】以来，群智能 算法引起了更多的关注，有更多人致力于这方面的研究，1 9 9 5 年k e n n e d y 和e b e r h a r 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 ) 【6 1 ；李晓磊等人 在2 0 0 2 年提出了人工鱼群算法( a r t i f i c i a lf i s hs w a r ma l g o r i t h m ，a f s a ) 【7 8 】；e u s u f f m 和 l a n s e y 在2 0 0 3 年提出了混合蛙跳算法( s h u f f l e df r o gl e a p i n ga l g o r i t h m ，s f l a ) 【9 】等等。 不过目前仅有蚁群算法和粒子群算法得到了广泛的关注和应用。 1 1 2 群体智能方法的特点 与大多数基于梯度信息的传统优化算法不同【1 0 1 ，群智能算法的本质是一种概率搜 索，不需要任何的梯度信息，而且在搜索过程中隐含了并行性，因此在解决复杂的优化 问题时显示出其明显的优势，综合起来群智能算法有以下几个主要的优点1 6 j ： ( 1 ) 鲁棒性：没有中心的控制和数据，这样的系统更具有鲁棒性，不会由于某个或者 某几个个体的故障而影响整个问题的求解； ( 2 ) 分布性：群体中相互合作的个体是分布的，这样更能够适应当前网络环境下的工 第一章绪论 作状态； ( 3 ) 自适应性和快速性：系统中每个个体的能力十分简单，这样每个个体的执行时间 比较短，并且实现也比较简单，具有简单性； ( 4 ) 协作性：可以不通过个体之间直接通信而是通过非直接通信进行合作，这样的系 统具有个别更好的可扩展性； 虽然群智能算法目前还没有遗传算法【1 1 1 、模拟退火算法【1 2 】、人工神经网络等【1 3 】这 些早期的智能算法成熟，但由于其鲁棒性，分布性，自适应性和快速性，协作性等特点， 自提出以来得到了较快的发展。较传统的优化算法而言，提高了优化问题的求解速度和 精度，特别为一些传统优化方法无法解决的复杂优化问题开辟了新的解决途径，同时也 为诸如实际优化，神经网络训练，数据挖掘，模式识别等实际优化问题提供了新的解决 方法【1 4 , 1 5 , 1 6 , 17 】。基于群智能广阔的学术意见和应用前景，它已经引起越来越多的学者的 关注，今后必将发展为一个重要的研究方向。 1 2 原始p s o 算法和标准p s o 算法 1 2 1p s o 算法的起源背景 1 9 8 6 年c r a i gr e y n o l d s 提出了b o l d ( b i r d o i d ) 模型【1 8 , 1 9 。该模型用来模拟鸟群聚集飞 行的行为，提出了群体中个体飞行的三个原则： ( 1 ) 向背离最近的同伴的方向飞行； ( 2 ) 向目的飞行； ( 3 ) 向群体中心靠拢。 群中的任何个体在飞行时都遵循以上三条规则。之后，f r a n kh e p p n e r 在b o l d 模型的基 础上又加入了栖息地的仿真条件，即鸟群的活动范围不会越出栖息地。受到 b o l d ( b i r d o i d ) 模型的启发，1 9 9 5 年，k e n n e d y 和e b e r h a r t 模拟鸟群觅食行为提出了一种 新颖而有效的群体智能优化算法【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 ) 。设想这样一个场景：一群鸟在随机寻找食物，一开始，每只鸟均不知道食物在那 里，所以均无特定的目标进行飞行，但是它们知道哪只鸟距离食物最近，还有自己在曾 经离食物最近的位置，每只鸟开始试图通过这两个位置来确定自己往哪个方向飞行。受 到这种鸟群群体觅食行为的启示，将鸟群觅食行为类比与一个特定问题寻找解的过程。 我们可以将鸟群觅食过程看作是一个优化问题每只鸟看作是问题的一个潜在解， 食物当作是优化问题的最优解，个体找到食物就相当于优化问题找到最优解。当然这旱 的鸟群是经过人工处理的、它们均是有记忆功能、没有质量和体积、不占空间的粒子。 2 2 原始p s o 算法 图】粒子运动图 在算法中，每个粒子可以想象成算法空日j 中的一个潜在解粒子的优劣由目标函数 来衡量各个粒子根据下面的信息来确定自己当前位置： ( 1 ) 自身当前的位置： ( 2 ) 自身当前的速度； ( 3 ) 自身当前的位置和自身历史最优位置之问的距离； ( 4 1 自身当前的位罱和整个群体历史最优位置之间的距离。 每个粒子自身经过的历史最优位置可看作是粒子个体的飞行经验，整个粒子群目前 的最优位置可以看作是整个群的群体飞行经验。所以粒子在每次迭代过程中，粒子通过 个体和群体的飞行经验来调整飞行的速度，即他们下一步的飞行方向和飞行距离，然后 粒子们就在解空间中搜索晟优位置。 在p s o 算法中，首先初始化一群粒子，设有个算法按以下方式迭代：第，个粒 子的位置记为t = ( j 舯j 小，如) ，i = 1 , 2 ，n ，“飞翔”速度已为v ，= ( v 、j v d ，) ， 迄今为止搜索到的个体极值表示为p b , = ( 加舭鹏：，p b 。) ，整个粒子群中，所有粒子 第一章绪论 迄今为止所搜索到的全局极值表示为g b = ( g b 。，驴：，g b d ) 。则第i 个粒子就是按照下面 公式来更新自己的速度和位置【6 】： 1 ，分1 = v 刍+ c l r l ( p 6 5 一x 耐k ) + c 2 r 2 ( 9 6 ：一x 0 )( 1 1 ) x 等1 = x 当+ v 1 ( 1 2 ) 式中：i = 1 , 2 ，n ，n 是群体中的粒子数；的大小根据具体情况而定，一般取2 0 5 0 ， 不过如果遇到比较复杂的问题，粒子数可以适当地增加，取到1 0 0 2 0 0 。 七= 1 , 2 ，2 是迭代次数； d = 1 , 2 9 0o 9 d ，d 是解空间的维数，即自变量的个数； 1 ，0 表示第k 次迭代粒子f 速度矢量的d 维分量； x 0 表示第k 次迭代粒子f 位置矢量的d 维分量； p 冼表示第k 次迭代粒子f 个体最好位置矢量( p b ) 的d 维分量； 9 6 ：表示前k 次迭代粒子群最好位置( 9 6 ) 矢量的d 维分量； r 1 和j j c 2 是介于【0 ，1 区间的随机数； c ，和c ：为学习因子，分别调节向p 6 和g b 方向飞行的步长，学习因子使粒子具有自 我总结和向群体中优秀个体学习的能力，合适的学习因子可以加快算法的收敛且不易陷 入局部最优，根据经验值他们通常都取2 ，不过也有取其他值，一般在0 到4 之间。 卜x d ，x 衄d 】，通常根据实际问题将解空间限制在一定范围； 卜d ，v 一矗 ，速度的最大值根据粒子的取长区间长度来确定。若取太大， 则粒子可能飞过最优区域，若，耐太小，则可能无法充分探测局部最优区域以外的区域， 这样容易陷入局部最优。一般来说，如果解空间的范围为卜x 雠d ，x d 】，则 1 ，眦d = k 奉x m a x d ，0 1 k 0 2 2 0 1 。 p s o 算法的终止条件一般为最大循环数或者达到问题的精度要求，可以根据问题的 不同由用户自己确定。 由上两式可知，粒子i 新速度的计算主要由三部分决定：粒子f 前一次的速度畦； 西北大学硕士学位论文 粒子f 当前位置与自己历史最好位置之间的距离( p 碓一k ) ；粒子f 当前位置与群体目前 最好位置之间的距离( 9 6 刍一x 0 ) 。图2 是以二维空间为例描述了粒子f 的移动原理图： ，越 图2 粒子群移动原理图 如果从社会学的角度来看【2 1 】，公式( 1 1 ) 的第一部分为粒子的先前速度，表示粒子 对自身运动状态的信任。第二部分为“认知( c o g n i t i o n ) 部分，表示粒子自身的经验， 鼓励粒子向自身曾经过的最优位置飞去；第三部分为“社会( s o c i a l ) 部分，表示粒子 间的信息共享与相互合作，即微粒的运动中来源于群体中其他微粒的经验的部分，它引 导粒子飞向整个粒子群中的最优位置。 1 2 3 算法的基本流程 p s o 的具体实现步骤如下： s t e p l ：参数初始化。 在初始范围内，随机初始化一群粒子，即设置种群规模、粒子的初始位 置x ，、初始速度形( 其中f - 1 , 2 ，一，n ) ，并将各粒子的个体最优p 6 ，设置 为初始位置，全局最优值驴设为p b i 中的最优值。 s t e p 2 ：根据式( 1 1 ) 和式( 1 2 ) 对粒子的速度和位置进行更新； s t e p 3 ：计算每个粒子的适应值。 第一章绪论 s t e p 4 ：判断每个粒子的个体最优值。 对每个粒子，将其当前的适应值和上一次的个体最优值p b , 进行比较，如 果当前适应值优于p 6 j ，则令p b , 取当前适应值，否则，个体最优值仍为 原来的加，( 其中f _ 1 , 2 ，n ) 。 s t e p 5 ：判断整个粒子群的全局最优值。 比较当前每个粒子的个体最优值，找出当前迭代中的全局最优值，与历史 全局最优舶比较，如果优于驴，则令的取当前迭代中的全局最优值， 否则，全局最优驴还取原来的值。 s t e p 6 ：判断是否满足终止条件。如果满足则转入s t e p 7 ；否则，转s t e p 2 ，继续迭 代。 s t e p 7 ：输出全局最优9 6 ，算法进行结束。 1 2 4 标准粒子群算法 为了改善算法的收敛性能，s i f t 和e b e r h a r t 在1 9 9 8 年的论文中引入了惯性因子的 概念【2 2 】，将速度更新公式( 1 1 ) 改为( 1 3 ) 所示： v 箩1 = w v ： d + c l r l ( p 6 0 一x 鲁) + c 2 尺2 ( 9 6 ：一x 廿k )( 1 3 ) x 爹1 = x 己+ v 譬1( 1 4 ) 这里，w 是非负数，称为惯性因子( i n e r t i a w e i g h t ) ，用来平衡算法的全局搜索能力和 局部搜索能力，w 较大时，全局搜索能力较强；w 较小时，局部搜索能力就强。因此选 择一个合适的w ，对提高算法的搜索速度和收敛精度等性能方面至关重要，于是许多研 究者对w 的取法进行了大量的研究和改进，具体方法我们在下一节专门给出。 1 3 粒子群算法的研究现状 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 算法中引入了空间邻域的概纠2 3 1 ， k e n n e d y 研究粒子群中的几种领域拓扑结构并分析了它们对算法性能的影响【2 4 1 。 k a e w k a m n e r d p o n g 等人分析可感知的p s o 算法的性能1 2 5 】。j a n s o n 等人提出分层粒子群 算法【2 6 】( h i e r - - a r c h i c a lp a r t i c l es w a r mo p t i m i z e r ) 。当然还有一些学者在其他方面对粒子 群算法进行改进，比如k e n n e d y 讨论了速度更新公式在p s o 算法中的影响【2 7 1 ，同时还 提出了动态概率p s o 算法【2 8 】。 此外，h e 等人还引入了生物群体中“被动征集”的概念改进粒子群的信息共享方 式【2 9 】。赫然等人结合生物群体中的一些特征，提出一种自适应逃逸p s o 算法，算法收 敛速度较快，能够有效进行全局收敛。b e r g h 等人提出协作p s o 算法【3 0 1 ，采用多种群 策略，增强了种群的多样性等等。 二、基于p s o 参数的研究 p s o 参数的研究对提高算法的收敛速度和解的精度有着很重要的意义，所做的研 究主要是针对惯性因子w 、学习因子c ，和c ：，粒子群的规模n 以及速度上限1 ，眦d ，其 中对p s o 参数取值的改进技术中研究最多的是关于惯性因子w 的取值问题。w 表明粒 子原先的速度能在多大程度上得到保留，对算法的局部搜索能力和全局搜索能力进行平 衡调整。受到模拟退火中的温度的启示，认为较大的w 可以增强p s o 的全局搜索能力， 而较小的w 能加强p s o 算法的局部搜索能力 3 1 】，实验证明这一想法是正确的。因此， 随着迭代次数的增加，惯性因子w 应不断减小，于是s h i 等f 2 2 ，3 1 】提出按照线性递减规律 改变惯性因子1 4 ，其具体计算公式为： ， 一， w ( t ) = 地l 二( 一w 曲) + ( 1 5 ) l 咄 ( 其中w 一为最大惯性因子，为最小惯性因子，r 为当前迭代次数，r 一为算法总的 迭代次数) 【3 2 】；随后s h i 等人又提出了模糊惯性权重法，用模糊控制器来动态自适应地改 第一章绪论 变惯性权重的技术【3 3 1 ，由于模糊权重法实现起来较困难，所以没有得到广泛使用 3 4 1 。 一些研究者认为s h i 等人提出的这种线性惯性权重法中的权值变化较为单一，因此对搜 索能力的调节也就有限，使其搜索过程不一定能适应实际问题的复杂情况。于是张丽平 等人提出了随机惯性权重策略，意在改变这种变化单一的状况【3 5 1 。 由于粒子群算法的搜索过程非常复杂，所以简单的w 线性变化无法满足搜索的需 要，c h a t t e r j e e 等提出了一种非线性惯性因子的p s o 算法，其惯性因子的自适应变化 式w 为： w ( ) = 【学 ( w m a x m ) + ( 1 6 ) 显然，线性惯性因子法是上述非线性惯性因子的特殊情况，其中刀为非线性调节指 数，c h a t t e r j e e 等人对门取不同的值进行试验，给出了不同的非线性调节指数对算法性能 的影响。而c l e r c t 3 7 ，3 8 1 等在p s o 算法中引入了另一个参数系数一收缩因子a ，改进后的 速度更新公式和口的具体取值如下： v 耐k = 仅i v y , + c i r l ( p b ：a x 0 ) + c 2 r 2 ( 驴：一x d k ) 】 ( 1 7 ) 2 其中巾= c l + c 2 ，巾 4 ( 1 8 ) 通常取为4 1 ( c 1 = c 2 = 2 0 5 ) ，此时口= 0 7 2 9 。显然惯性因子是收缩因子a = 1 的 特殊情况，与使用惯性因子的粒子群算法相比，收缩因子不仅可以加快算法的收敛性， 而且可以有效控制算法最终收敛，即保证算法的收敛性。 三、与其他技术( 优化算法) 融合 通过将其他优化算法中的一些优点融合至u p s o 算法中，可以取长补短，有效改善原 始p s o 算法的性能。l o v b j e r g 等提出了带交叉算子的p s o 3 9 】算法，；h i g 础i 等f 4 0 】提出了带 变异算子的p s o ；a n g e l i n e m l 】将选择算子引入p s o 算法中，选择每次迭代后的较好粒子 复制到到下一代，以保证每次迭代的粒子群都具有较好的性能。k r i n k 等人混合遗传算 法、粒子群算法和爬山法提出一个称为生命周期模型的混合搜索算法f 4 2 】。吕振肃等人提 出了自适应变异的p s o 优化算法【4 3 】，实验表明该算法能有效避免迭代陷入局部最优。l i u 等人将混沌算法的思想引入p s o 算法中，用以增强p s o 算法的搜索能力【4 4 1 。d a s 等人结合 微分进化算法的思想对p s o 算法进行改进【4 5 】。h o l d e n 等人混合p s o 算法和蚁群算法，并 将其应用于生物数据集的层次分类【矧。除此之外，还有很多其他的融合，例如基于模拟 西北大学硕士学位论文 退火算法思想的p s o 算法 4 7 1 ，免疫粒子群优化算法【4 8 1 等等。 1 4 粒子群算法的主要应用及研究方向 1 4 1 粒子群算法的主要应用 粒子群优化算法一提出就受到了广泛的关注，各种粒子群算法应用研究的成果不断 涌现，它的应用领域已从最初的函数优化和神经网络的训练扩展到更加广阔的领域，有 力地推动了粒子群优化算法的研究。目前粒子群优化算法主要应用于以下几个方面： 1 ) 函数优化 p s o 算法最先被应用于函数优化【6 】，a n g e l i n e 和s h i 经过大量的实验研究发现，粒 子群优化算法在解决一些经典的函数优化问题，甚至一些非线性函数时，展现了良好的 性能【4 9 1 。其后研究者开始尝试用p s o 解决更为复杂的约束优化和多目标优化问题， p a r s o p o u l o s 第一次将p s o 算法应用于多目标优化问题1 5 0 】，也取得了很好的效果。 2 ) 神经网络训练 将p s o 用于神经网络训练也取得了良好的效果。研究表明，p s o 是一种很有潜力 的神经网络训练算法，如用于市区环境状况的分析和预测等取得了较高的成功率【5 l 】。 3 ) i 程领域应用 很多工程中的实际问题，其本质上是优化问题，因此人们很自然想到将p s o 算法 应用于实际的工程问题中。将p s o 算法与b p 算法相结合训练神经网络已用于对电动汽 车燃料电池组时充电情况的模拟。通过训练神经网络，粒子群优化算法己成功应用到对 医学中振颤行为的分析圈；还有，y o s h i d a 等人将p s o 算法应用于电力系统中的无功和 电压控制【5 3 1 。粒子群优化算法和其他进化算法一样，可以解决几乎所有的优化问题，或 是可以转化为优化问题求解的问题。此外，p s o 算法还在生物工程【5 4 1 、电磁学【5 5 1 、数 据挖掘【5 6 1 、博弈5 7 】等很多领域都取得了较好的效果。 1 4 2p s 0 算法的研究方向 粒子群算法自问世以来，在国外得到了相关领域众多学者的关注和研究，在理论和 应用方面已经有了很大的发展，c e c 国际年会上，粒子群算法已经被作为一个独立的研 究分支。但粒子群算法还存在很多的不足需要进一步研究，主要的研究及改进方向集中 第一章绪论 为以下几方面： ( 1 ) 粒子群算法的改进 与许多仿生算法一样，粒子群算法现在还只是刚刚起步，本身有很多的不足之处需 要改进，尤其它作为一种仿生算法，是对生物群体行为的模拟而产生的，那么如何对生 物群体行为进行进一步研究，改善粒子群算法的性能，将是我们努力的一个方向。 ( 2 ) p s o 算法的理论基础的研究 虽然p s o 算法已经在很多方面得到应用，但对其理论上的分析还非常薄弱，例如 人们一直都没给出很完善的收敛性、收敛速度估计等方面的数学证明。如何利用有效数 学工具对p s o 算法的收敛性、计算复杂性以及对算法中的参数设置进行分析也是目前 的研究热点之一。 ( 3 ) p s o 算法与其他进化算法的比较和融合 粒子群算法作为一种新兴的算法，虽然在应用方面展现很好的发展前景，但与其他 早期提出的算法，如遗传算法、蚁群算法相比，在各个方面都不太成熟，如何引进这些 相对成熟的进化算法的优点来弥补粒子群算法目前的不足将是我们今后研究的一个方 向。 ( 4 ) 粒子群算法的应用 算法研究的目的是应用，而p s o 算法已经在较广阔的领域崭露头角，并且由于其 简单、易操作的特点，p s o 算法在收敛速度和精度方面都有了很好的效果，但其中相当 一部分仍处于仿真和试验阶段，离实际的问题还有很远的距离，需要作进一步的努力。 同时考虑到p s o 算法和遗传算法、蚁群算法等有很多相似地方，所以可以将p s o 算法 用到原来遗传和蚁群应用的工程问题中。如何将p s o 算法用到更广阔的领域中去，同 时研究应用中存在的问题都是值得关注的热点。 西北大学硕士学位论文 第二章粒子群算法的收敛性分析 算法的收敛性分析对算法的参数估计、算法的改进有着极其重要的影响，所以粒子 群算法的收敛性分析自然也成为很多学者关注的重点，本章给出一些比较重要的研究结 果，主要参考文献【5 8 】。 2 1 随机算法的收敛条件 首先给出s o l i s 和w e t s 提出的随机优化算法全局收敛需满足的条件： 假设1 ：f ( d ( x ，考) ) = f ( x ) ，并且如果考q ，则f ( d ( x ，考) ) 0 ，则有i - i ( 1 一x 女( e ) ) = 0 。 其中，地( e ) 是由测度j l l 。所得的e 的概率。 定理1 ：假设目标函数f 为可测函数，区域q 为可测子集，杪( ) ) ：。为算法所生 成的解序列，如果假设1 和假设2 满足，则 j i mp x 女r 。】- 1 ， 膏 其中，研以r 。 是第k 步算法生成的解以r 。的概率。 即对于一个随机优化算法，如果能够满足假设1 与假设2 ，那么就可以保证算法以 概率l 收敛于全局最优解。 第二章粒子群算法的收敛性分析 2 2 基本粒子群算法的收敛性分析 定义函数d 为： _ 沪，慧；黜 ， 下面将证明粒子群算法是否满足上述的假设条件： 对于假设1 ， f ( g ( x 啪) ) f ( p g ，女) 时，f ( d ( p g x ， ) ) = f ( p g j ) f ( g ( x 啦) ) 。 f ( g ( x m ) ) f ( p 时) 时，f ( d ( p g j ，x 啦) ) = f ( g ( x 肚) ) ，所以基本粒子群算法满足假 设1 。 对于假设2 ，基本p s o 算法满足假设2 ，则等同基本p s o 算法满足下式 x u m 娃 ( 2 2 ) 其中，x 为粒子群的样本空间，m “表示在算法第七代时微粒的支撑集，由于 x ( k + 1 ) = x ( k ) + v ( k + 1 ) = x ( k ) + o v ( k ) 一x ( 七) 1 + 巾2 ) + 尸巾1 + 名巾2 = x ( k ) + ( x ( 七) 一x ( k 一1 ) ) 一x ( 后) 砷1 + 巾2 ) + 尸巾1 + 丘巾2 = ( i + c o 一咖1 一巾2 ) x ( j j ) 一0 3 x ( k 一1 ) + p 巾l + 乓巾2 其中巾。= c 。，巾：= c 2 r ：，将上式代入可以得到m ，j 为 m ，乒= ( 1 + 一巾1 一巾2 ) x ，女一1 一，工i 一2 + 巾l p + 巾2 乓 = x 。，一1 + ( 工u ， 一l x i , j , k - 2 ) + 巾1 ( 尸一x t , j , 一1 ) + 中2 ( 忍一x l , j 一1 ) 显然，0 巾1 q ，0 巾2 c 2 ，x u ，表示微粒f 在第k 代时第维分量的值。显然， m 继表示一个由审。、巾：所确定的超矩形，其中一个端点为巾，= 巾2 = 0 ，另一个为巾。= c 。， 耷2 = c 2 。 当 m a x ( c ，i p x ，乒l ，c ：1 名一一，i ) o 5 旃口聊，( x ) 成立时 ，显然有 v ( m 啦nx ) v ( x ) ，其中，坊口聊j ( x ) 表示x 在第歹维分量的长度。由于x ，趋于p 和p g 的 西北大学硕士学位论文 加权平均，即t 一( c l p + c 2 忍) 必c l + c 2 ) ，从而腆m ， 七20 ，当七一o o 时，1 ，( 肘冲) 在逐 渐变小，v ( u 膨，士) 也在减小，故1 ，( 0 m ，j n x ) k j 一1 f = 时，存在集合qc x ，使得善t 肛聃( q ) = 0 ，这表明基本p s o 算法不满足假设2 。 因此基本粒子群算法不是全局收敛的。 2 3 两种保证全局收敛的粒子群算法 在基本的粒子群算法无法保证全局收敛的情况下，人们提出一种可以保证全局收敛 的粒子群算法( g s p s o ) ，该算法给全局最好粒子引入了新的速度和位置更新公式： v g ( 七+ 1 ) = 一x g ( 后) + p g ( 七) + w v g ( j | ) + 九( 七) ( 1 2 r ) ( 2 3 ) x g ( 后+ 1 ) = p g ( 七) + w v g ( 七) + 九( 七) ( 1 2 r ) ( 2 4 ) 其中九( 七) 为比例因子，如果算法连续成功找到更好的全局最优微粒达到阈值，增大 z ( k ) ；连续失败次数达到阈值，减小, v k ) ；其他情况九( 七) 不变，从( 2 4 ) 可以看出保证 全局收敛的粒子群算法在最优值的周围进行搜索，搜索范围由比例因子决定。f b e r g h 博士利用s o l i s 和w e t s 提出的随机优化算法全局收敛需满足的条件证明( g s p s o ) 能够保 证收敛到局部最优，但不能保证收敛到全局最优。 另外一种被称为随机粒子群优化算法，是对基本粒子群算法进行如下变形： 在算法中，保留p 譬( 豇) 作为全局最优位置，在样本空间x 中随机产生粒子，的位置 x ，( 七+ 1 ) ，e z 4 - p 。( 后+ 1 ) = x ，( j j + 1 ) ，其他粒子依然按照基本粒子优化算法的方式更新， p 卫( 是+ 1 ) = a r g m i n ( f ( x ，( 露+ 1 ) ) ) ( f = 1 , 2 ，x ) ( 2 。5 ) 如果夕g ( 七+ 1 ) = p j ( 七+ 1 ) ，则随机产生的微粒处于历史最优位置，继续在x 中随机产生， 如果以( 七+ 1 ) p j ( 七+ 1 ) ，_ rp g ( 七+ 1 ) = 以( 尼) ，则所有粒子按基本p s o 的速度位置更 新方式进行更新，如果以( 七+ 1 ) p j ( k + 1 ) _ l f l p g ( 七+ 1 ) p g ( j j ) ，说明存在f o 歹，使得 p g ( 后+ 1 ) = p 毛( j | + 1 ) ，则将第f o 个粒子的位置随机赋值，其他粒子按照基本p s o 算法进 化，这样不时会有粒子进行随机赋值，势必会增加算法的多样性。 第二章粒子群算法的收敛性分析 随机粒子群优化算法中，在进化的每一代中至少有一个粒子因为处于历史的最优位 置而停止进化，利用最优位置的粒子来增加算法的全局搜索能力，s o l i s 和w e t s 证明了 当进化代数k 专时，随机粒子群优化算法以概率1 收敛于全局最优值。 西北大学硕士学位论文 3 1 引言 第三章一种基于阶段进化策略的粒子群算法 为求解无约束优化问题，基于粒子群算法易陷入局部最优的缺点，本章提出了一种 改进的方案。通过几个经典测试函数，证明改进后的粒子群算法在同等迭代次数下收敛 精度明显优于标准粒子群算法，当判断出群体迭代可能陷入局部最优时，改进后的算法 能够适时地重新给一部分粒子赋值，从而跳出最优解，最终找到满意的全局解。 3 2 基于阶段进化策略的粒子群算法 虽然基本的p s o 算法有简单、易实现、功能强大且没有很多参数需要调整等优点， 但也存在着易陷入局部最优导致的收敛精度低和不易收敛等缺点，尤其是在高维情况 下。本章针对基本的p s o 算法易陷入局部最优这一缺点，受人类进化过程的启发，提 出如下改进方案：因为人类进化过程具有阶段性，同一阶段内人类社会的发展具有相同 的特性，在同一个阶段进入到下一个阶段必将经历重大的变革，将人类社会的这种特性 运用到基本的p s o 算法中，得到改进的p s o 算法，称为阶段进化策略【5 9 1 。首先，计算 个粒子适应值的数学期望厂和平均绝对偏差仃，设定一个检验值h ，因为第一次随机取 值的概率至多百分之一，所以我们可以取h = f 1 0 0 ，然后来判断算法是否可能陷入局 部最优，如果仃 h ，算法可能陷入局部最优，则对所有粒子做如下处理：计算每个粒 子的适应值与期望值f 的偏差i ，一卅( 扛1 ，2 ，) ，将偏差小于h 且不是全局最优的粒子 重新随机赋值，全局最优值对应的粒子和不满足上述条件的粒子保持不变，这样两部分 粒子组成一个新的群体，进入下一次迭代。于是每当算法可能陷入局部最优时，改进的 p s o 算法就会适时地给群体重新赋值，使算法跳出局部最优解，而且还保留了每一代全 局最好的粒子。我们知道基本的p s o 算法不是全局收敛的，尤其是对高维的问题，虽 然改进的算法也不能保证全局收敛，但由于其保留了每一代的全局最优粒子，而且还可 以一次次跳出局部解向全局解靠近，所以改进的p s o 算法对于高维优化问题的收敛性 远远优于基本的p s o 算法。 第三章一种基于阶段进化策略的粒子群算法 基本的p s o 算法的终止条件一般是设定最大迭代次数或精确度，这两种设定均有 一个缺陷，对于设定最大迭代次数而言，迭代次数太大可能导致已经是最优解但没到最 大迭代数结果还要徒劳地继续搜索，太小则会导致还有很大的搜索空间算法却不得不停 止。对于设定精确度，我们一般不知道要求的问题的理论最优值是多少，所以无法设定。 本文对应改进的p s o 算法提出了一种终止条件，首先，可自定义一个k 和最大迭代次数， 如果算法连续k 次如上重新赋值，这k 次的个粒子适应值的期望值分别为z ，正，。，五， 如果z ，厶， 的均差小于s ( 说明算法没有太大的搜索潜力了，可能是全局最优了) 或 达到最大迭代次数，则停止搜索。其中j 和s 可以根据用户对计算结果精度的不同要求 而自己设定。 3 3 基于阶段进化策略的p s o 算法流程 s t e p1 初始化所有粒子和有关参数； c l = c 2 = 2 ：学习因子； w ：压缩因子： d ：解空间的维数； ：粒子数； h ：检验迭代是否陷入局部最优的阈值；