（通信与信息系统专业论文）改进粒子群算法研究及其在网络路由中的应用.pdf

摘要粒子群算法是一种随机搜索算法。它借鉴了生物群落捕食的机理，简单通用、鲁棒性强、适合于并行处理，是一种有效的全局搜索方法，在多个方面得到了成功的应用。但粒子群算法也存在易早熟、局部搜索能力差等缺点。本文对基本粒子群算法及其改进算法进行了系统的分析和研究，主要研究如下：第一，针对基本粒子群算法易陷入局部最优解的缺点，提出了一种改进的粒子群算法。该算法将整个种群分成两部分，一部分粒子仍按原方向飞行，而另外一部分粒子( 变异粒子) 不再朝群体最优解方向飞行，而是向反方向飞行，这样就提高了种群的多样性，扩大了搜索的空间，改善了常规粒子群算法摆脱局部最优解的能力。在此基础上，还进一步讨论了变异率对寻优结果的影响。第二，将本文所提改进粒子群算法应用于工业p i d 控制器的参数整定，以及带约束优化的工业设计中，均取得了非常理想的效果。第三，目前，离散粒子群算法的研究还比较少。针对基本粒子群算法求解旅行商问题( t s p ) 时的缺点，如速度慢、效率低且难以表达。本文提出了一种和遗传算法结合的混合粒子群算法。采用类似遗传算法的变异、交叉操作，使得位置更新和速度更新公式易于表达。让整个粒子群分成多个种群分别进行预选式进化，得到了具有局部较优基因组合的新粒子，以此组成新的种群进行全局性的优化。应用于t s p 问题的仿真表明，它是一种稳定、高效的优化算法。最后，将本文所提混合粒子群算法应用于i p 网络的q o s 路由优化中，以满足q o s 要求的同时又使所选路径费用最小为优化指标。对网络的仿真实验表明，此算法具有良好的效果。关键词：粒子群算法；遗传算法；p i d 控制器参数整定：约束优化；旅行商问题网络路由a b s t r a c tp 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 sar a n d o ms e a r c hm e t h o db a s e do nt h eb i o l o g i c a lc o m m u n i t y sp r e y i n g i ti ss i m p l e ，r o b u s ta n di sf i tt ob eu s e di nt h ep a r a l l e lc o m p u t a t i o n p s oi sv e r ye f f e c t i v ei ng l o b a ls e a r c h ，a n dh a sb e e ns u c c e s s f u l l ya p p l i e di nm a n ya s p e c t s ，b u ti ta l s oh a ss o m ed i s a d v a n t a g e ss u c ha se a s i l yt ob ep r e m a t u r e ，b a dl o c a ls e a r c hc a p a b i l i t y t h i st h e s i sa n a l y z e dt h eb a s i cp s oa n di t sm o d i f i e da l g o r i t h ms y s t e m a t a c i a l l y t h em a i nw o r k sa r ea sf o l l o w ：f i r s t l y , i no r d e rt oo v e r c o m et h ed i s a d v a n t a g et h a tt h eb a s i cp s oc o u l db ee a s i l yt r a p p e di nt h el o c a lo p t i m u m t h i st h e s i sp r o p o s e dam o d i f i e dp s o t l l i sa l g o f i t h r ad i v i d e dt h ew h o l es w a r mi n t ot w og r o u p so n eg r o u pf l i e st o w a r d st h eg l o b a l l yb e s tp o s i t i o nf o u n ds of a r , t h eo t h e r ( m u t a t e dp a r t i c l e s ) f l i e si nt h eo p p o s i t ed i r e c t i o n t h e r e b y , t h ed i v e r s i t ya n de x p l o r a t i o no ft h es p a c ea r ei n c r e a s e d ，a n dt h ea b i l i t yt ob r e a ka w a yf r o mt h el o c a lo p t i m u mi si m p r o v e d m o r e o v e r , h o wt h em u t a t i o nr a t ew o u l da f f e c tt h er e s u l ti sa l s od i s c u s s e d s e c o n d l y , t h i sa l g o r i t h mi sa p p l i e dt ot h ep i dc o n t r o l l e rt u n i n ga n dt h ei n d u s t r i a ld e s i g nw i t l lr e s t r i c t i o n s t h er e s u l t sa r ef a i r l yw e l lt h i r d l y , b yf a r , t h es t u d yo nt h ed i s c r e t ep s oi sr e l a t i v e l yn o tp o p u l a r w h e nt h eb a s i cp s os o l v i n gt r a v e l i n gs a l e s m a np r o b l e m ( t s p ) ，i th a sm a n yd i s a d v a n t a g e s ，s u c ha ss l o ws p e e d ，l o we f f i c i e n c y ，h a r dt ob ee x p r e s s e d i no r d e rt oo v e r c o m et h e s es h o r t c o m i n g s ，t h i st h e s i sc o m b i n e dt h ep s ow i t hg a ( g e n e t i ca l g o r i t h m ) a d o p t e dt h em u t a t i o na n dt h ec r o s s o v e rf r o mg a ，t h i sc o m b i n e da l g o r i t h mc a ne a s i l ye x p r e s st h es p e e d - l o c a t i o nu p d a t ef o r m u l a i td i v i d e st h ew h o l es w a r mi n t om a n yg r o u p s ，a n dm a k e st h e me v o l v es e p a r a t e l yf o r t h ep r i m a r ye l e c t i o n t h eb e r e rl o c a lg e n es e q u e n c e so b t a i n e df r o mt h ep r i m a r ye l e c t i o na r eu s e df o rt h eg l o b a ls e a r c h s i m u l a t i o nh a sb e e nc a r r i e do u to nt s pa n dt h er e s u l ts h o w st h a tt h ec o m b i n e da l g o r i t h mi sr o b u s ta n de f f i c i e n t a tl a s t ，t h ec o m b i n e da l g o r i t h mp r o p o s e di nt h i st h e s i si sa p p l i e dt ot h ei pn e t w o r k sq o sr o u t i n g t h eo p t i m i z a t i o nt a r g e ti st om e e tt h eq o sr e s t r i c t i o n ，a tt h es a m et i m e ，t h es e l e c t e dr o u t i n g sc o s tm u s tb em i n i m u ms i m u l a t i o nr e s u l to nan e t w o r ks h o w st h a tt h ea l g o r i t h mi sg o 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 ；g e n e t i ca l g o r i t h m ；t h ep i dc o n t r o l l e rt u n i n g ；o p t i m i z a t i o nw i t hr e s t r i c t i o n s ；t r a v e l i n gs a l e s m a np r o b l e m ；n e t w o r kr o u t i n g学位论文独创性声明：本人所呈交的学位论文是我个人在导师指导下进行的研究工作及取得的研究成果。尽我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其他入已经发表或撰写过的研究成果。与我一同工作的同事对本研究所做的任何贡献均已在论文中作了明确的说明并表示了谢意。如不实，本人负全部责任。论文作者( 签名) ：乏刍丝2 0 0 6 年；月2 ) 日学位论文使用授权说明河海大学、中国科学技术信息研究所、国家图书馆、中国学术期刊( 光盘版) 电子杂志社有权保留本人所送交学位论文的复印件或电子文档，可以采用影印、缩印或其他复制手段保存论文。本人电子文档的内容和纸质论文的内容相一致。除在保密期内的保密论文外，允许论文被查阅和借阅。论文全部或部分内容的公布( 包括刊登) 授权河海大学研究生院办理。论文作者( 签名) ：! 鱼墅2 0 0 6 年岁月2 7 日塑塑查堂堡主堂垡堡壅兰二皇l ! l第一章绪论1 1 粒子群算法产生的背景二十一世纪是信息社会，人们在享受到信息社会给我们带来无尽便利的同时，也深刻感受到了海量信息带给我们的挑战。面对海量信息的挑战，人们有两个基本的策略，一个是计算得更快：在这方面，我们看到信息技术的代表- c p u在不断地“进化”，从3 8 6 、4 8 6 到奔腾3 、奔腾4 ，然而c p u 的进化速度似乎始终赶不上信息增长、传播的速度。目前，c p u 技术陷入了“摩尔定律”1 失效的境地。人类的另外一个基本策略就是计算得更加智能：在这方面大自然始终是人类的老师，人类受到社会系统、物理系统、生物系统等运行机制启发，建立和发展起一个个研究工具和手段来解决和攻克研究过程中遇到的困难。典型的有遗传算法( g e n 砸ca 1 9 0 r i t h m ，g a ) j - 2 、人工神经网络( a r t i f i c i a ln e u r a ln e t w o r k s ，a n n ) 3 4 、进化规划( e v o l u t i o n a lp r o g r a m m i n g ，e p ) 1 5 j 、蚁群优化算法( a n tc o l o n yo p t i m i z a t i o n ，a c o ) ( 6 i 等。这些方法已经被广泛应用于工程实践，有许多很成功的实例。而在计算智f l e ( c o m p u t a t i o n a li n t e l l i g e n c e ，c i ) ”j 领域中，有两种基于群体智能( s w a r mi n t e l l i g e n c e ，s i ) 的算法：蚁群优化算法和粒子群优化算法。前者是对蚂蚁群落搜索食物行为的模拟，已经成功运用在很多组合优化问题上；后者就是本文将要介绍的粒子群优化算法。粒子群优化算法( p a r t i c l es w a r mo p t i m i z a t i o p n p s o ) 是由e b e r h a r t 博士和k e n n e d y 博士发明的一种进化计算技术1 8 9 】，是进化计算领域中的一个新的分支，其源于对鸟群和鱼群群体运动行为的研究。很多群居物稽，其亲属社会网络有助于共同照顾年轻个体，群居生活可以共享食物，而在天敌入侵时能提供警告并集体防御，群体的捕食可能会比单一个体更加有效，当很多双眼睛同时寻找食物的时候，捕食效率可以提高。由于创新和模仿而积累的文化进化，产生了问题解决方案的积聚，这些解决方案是建立在群体相互协作和交流之上的。文化保持了标准，并试图去满足或者超越这些标准，就像棘轮可以防止向后滑动，这就是迈克尔- 托马塞罗所说的“棘轮效果”【l “。粒子群算法模拟自然界群体生物间的社会行为。个体在学习自身经历的同时彼此相互作用，著且种群成员逐渐地移入问题空间的更好区域。与基于达尔文“适者生存，优胜劣汰”进化思想的遗传算法不同的是，粒子群优化算法是通过个体之间的协作来寻找最优解的。文献】引用了生物社会学家1 摩尔定律：一定的时问间隔内随着：薛j 乜路的复杂度提高，集成的兀件数目将增加一倍然而每个芯片的成本却下降一半。l河海土学硕士学位论文第一章绪论e 0w i l s o n 关于生物群体的一段话，“至少在理论上，一个生物群体中的一员可以从这个群体中所有其他成员以往在寻找食物过程中积累的经验和发现中获得好处。只要食物源不可须知地分抽于不同地方，这种协作带来的优势可能变成决定性的，超过群体中个体之i 训对食物竞争所带柬的劣势。”这段话的意思是说生物群体中信息共享会产生进化优势，这也正是粒子群优化算法的基本思想。粒子群算法概念简单。容易实现，其代码只有短短的几行，和其他优化算法相比，这也是它的优点之一。短短几年罩，粒子群算法已经获得了很大的发展，并已经在一些领域得到了很好的应用。粒了群算法已经在些经典的优化问题的求解和实际应用中显示出了强大的牛命力和潜力。它具有与传统优化算法( 如数学规划、动态规划等) 不同的如下特点：一、它是一类不确定性的方法。不确定性体现了自然界的生理机制，并且在求解某些特定问题方面优于确定性算法。二、它在优化过程中不依赖于优化问题本身的严格数学性质，如连续性、可导性及目标函数和约束条件的精确数学描述。三、它是一类基于多个智能体的智能算法。各智能体通过自学习不断提高自身的适应性，同时通过相互之问的协作柬更好地适应环境。四、它具有潜在的并行性。搜索过程不是从个点出发，而是同时从多个点同时进行。这种分布式的多个智能体的协作过程是异步并发进行的分布并行模式将大大提高整个算法的运行效率和收敛速度。1 2 最优化问题及其分类本文主要是研究改进粒子群算法在最优化问题中的应用，所以有必要先简单介绍一下晟优化问题相关的知识。最优化问题有三个基本要素：变量、约束和目标函数。在求解过程中选定的基本参数称为变量，对变量取值的种种限制称为约束，表示可行方案衡量标准的函数称为目标函数。最优化问题可分为函数优化问题和组合优化问题两大类，其中函数优化的对象是一定区问内的连续变量，而组合优化的对象是解空间中的离散状态。下面分别加以介绍。函数优化问题通常可描述为：令s 为r n 上的有界子集( 即变量的定义域) ，f s r 为n 为实值函数，所谓函数f 在s 域上全局最小化就是寻求点x r a i n s ，使得坟x i 。) 在s 域上全局最小即v x s ：“x n u n ) 兰f 【x ) 。组合优化问题通常可描述为：令g j - s “s 2 s n 为所有状态构成的解空间，c ( s i )为状态s 。对应的目标函数值，要求寻找最优解s 十，使得vs n ，c ( s * ) = m i n c ( s o 。组合优化往往涉及排序、分类、筛选等问题，它是运筹学的一个重要分支。组合优化往往涉及排序、分类、筛选等问题，它是运筹学的一个重要分支。河海大学硕士学位论文第一章绪论典型的组合优化问题有旅行商问题( t r a v e l i n gs a l e s m a np r o b l e m ，t s p ) 、加工调度问题( s c h e d u l i n gp r o b l e m ，如f l o w s h o p ，j o h - s h o p ) 、o - l 背包问题( k n a p s a c kp r o b l e m ) 、装箱问题( b i np a c k i n gp r o b l e m ) 、图着色问题( g r a p hc o l o r i n gp r o b l e m ) 、聚类问题( c l u s t e r i n gp r o b l e m ) 等。最优化的主要内容是研究最优化问题的计算方法，把可解决某个问题的计算方法称为适用于该问题的算法。算法的性能比较通常是基于一些称为b e n c h m a r k的典型问题展开的。1 3 粒子群算法的研究现状国内外研究表明，p s o 是解决复杂系统优化问题的一个有力工具。起初，p s o 算法主要用于连续函数的优化，后来也应用于组合优化等离散系统的问题研究。此外，对粒子群算法的改进也体现在很多方面。如：二进制的粒子群算法，w 随进化代数线性递减的粒子群算法，参数自适应的粒子群算法，以及和其他智能算法相结合的粒子群混合算法，等等。在具体应用方面：p s o 广泛应用于神经网络的训练，各类连续问题和离散问题的参数优化( 在模糊控制器的设计、机器人路径规划、信号处理和模式识别等问题上均取得了不错的效果) ，还应用于组合优化的问题当中【1 2 - 1 5 1 。除了以上领域外，p s o 在多目标优化、自动目标检测、生物信号识别、决策调度、系统辨识以及游戏训练等方面也取得了一定的成果 1 6 2 0 】。虽然目前已经开发出了很多种类各不相同的改进型粒子群算法，其性能也不断地得到提高，但是，作为一种优化算法，粒子群算法自身仍存在着许多难以解决的问题，如早熟收敛、控制参数的选择等。这些问题的存在，给粒子群算法的实际应用带来了极大的不便。这些算法的性能仍然有待于进一步改进以更好地满足实际要求。1 4 本文主要研究内容本文主要工作在于改进粒子群算法的性能，以满足实际应用的需要。作者对粒子群算法作了以下几方面的研究：第一，在详细分析粒子群算法优缺点的基础上，提出了一种改进的粒子群算法。该算法将整个粒子群按照变异率产生变异的粒子，变异的粒子不再朝群体最优解方向飞行，而是向反方向运动，这样就提高了种群的多样性，扩大了搜索的空间，改善了常规粒子群算法摆脱局部最优解的能力。应用于基准测试函数寻优的仿真实验表明该算法比基本粒子群算法以及遗传算法具有更好的寻优性能。还进一步讨论了变异率对寻优结果的影响。河海大学硕士学位论文第一章绪论第二，将这种改进的粒子群应用于工业p i d 的参数整定，各个参数的整定效果都比较理想，应用于带约束条件的工业没计( 压力容器的设计、水泵问题) 也取得了较好的效果。第三，针对基本粒子群算法求解旅行商问题( t s p ) i j q 速度慢、效率低且难以表达的缺陷，提出了一种和遗传算法结合的粒子群算法。采用类似遗传算法的变异、交叉操作，使得位置更新和速度更新公式易于表达。让整个粒子群分成多个子种群分别进行预选式进化，得到了具有局部较优基因组合的新粒子，以此形成一个新的种群进行总体进化。应用于t s p 问题的仿真表明，它是一种稳定、高效的优化算法。第四，将以上的混合算法应用于网络的q o s 路由优化的实例中，以满足q o s要求的同时又使所选路径费用最小为优化指标。对网络的仿真实验表明，此算法具有良好的效果。1 5 章节安排本文的章节安排如下：第一章：绪论，介绍本文的研究背景和主要研究内容等。第二章：介绍基本粒子群算法。第三章：提出了一种基于粒子运动方向变异的改进粒子群算法。第四章：将该改进算法应用于工业p i d 参数整定和带约束问题的优化。第五章：提出了一种和遗传算法结合的混合粒子群算法求解旅行商问题。第六章：将该混合粒子群算法应用于i p 网络的q o s 路由优化最后对改进算法的性能作了归纳，并对它的进一步研究作了展望。河海大学硕士学位论文第二章基本粒子群算法第二章基本粒子群算法2 1 粒子群算法概述2 1 1 粒子群算法简介从2 0 世纪9 0 年代初，就产生了模拟自然生物群体( s w a r m ) 行为的优化技术。如d o r i g o 等从生物进化的机理中受到启发，通过模拟蚂蚁的寻径行为，提出了蚁群优化方法 6 1 ；e b e r h a r t 和k e n n e d y 于1 9 9 5 年提出了粒子群优化算法( 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 算法【”l ，是基于对鸟群、鱼群捕食行为的模拟。粒子群算法同遗传算法类似，是一种基于迭代的优化工具，系统初始化为一组随机解，通过迭代搜寻最优解。但是粒子群算法并没有遗传算法所采用的交叉与变异操作。同遗传算法比较，粒子群算法的优势在于需要调整的参数不多，结构简单，收敛速度快。由于粒子群算法具有思想简单、易于实现、应用效果明显等优点而被众多应用领域所接受，并在自适应控制、组合优化、模式识别、机器学习、人工生命、管理决策等领域得到了广泛的应用。粒子群算法具有较强的鲁棒性，特别是对于一些大型、复杂优化非线性系统，更显示出其独特和优越的性能。粒子群算法作为- n 新兴学科，各种理论、方法尚未成熟，有待迸一步发展和完善。尽管在粒子群算法的研究和应用过程中会出现许多难题，同时也会产生许多不同的算法设计观点，然而，目前粒子群算法的各种应用实践已经展现出了其优异的性能和巨大的发展潜力，它的发展前景激励着各类专业技术人员把粒子群算法的理论和方法运用到自己的工作实践中。2 1 2 粒子群算法的基本思想粒子群优化算法是基于群体的演化算法。r e y n o l d s 对鸟群飞行的研究发现，鸟仅仅是追踪它有限数量的邻居，但最终的整体结果是整个鸟群好像在一个中心的控制之下，即复杂的全局行为是由简单规则的相互作用引起的。p s o 即源于对鸟群捕食行为的研究，一群鸟在随机搜寻食物，如果这个区域里只有一块食物，那么找到食物的最简单有效的策略就是搜寻目前离食物最近的鸟的周围区域。p s o就是从这种模型中得到启示而产生的，并用于解决优化问题。另外，人们通常是以他们自己及他人的经验来作为决策的依据，这就构成了p s o 的基本概念。堡壅查堂堡主兰堡丝兰笙兰童查查丝王壁苎查算法采用速度一位置搜索模型，每个粒子代表解空间的一个候选解，解的优劣程度由适应度函数决定。速度矿= ( l ，f ：，) 决定粒子在搜索空间迭代时的位移。其中，适应度函数根据优化目标定义。粒子群算法随机初始化为一群粒子，其中第i 个粒子在d 维解空间的位置表示为x ，= ( x n ，x 。，x ，。) 。与进化算法比较，粒子群算法保留了基于种群的全局搜索策略，但是其采用的速度一位置模型，操作简单，避免了复杂的遗传操作。它特有的记忆使其可以动态跟踪当前整个种群的最优粒子。p s o 算法在优化问题时，问题的解对应于搜索空间中一只鸟的位置，称这些鸟为“粒子”( p a r t i c l e ) 或“主体”( a g e n t ) 。它们都有自己的位置和速度( 决定飞行的方向和距离) ，还有一个由被优化函数决定的适应值。各个粒子记忆、追随当前的最优粒子，在解空间中搜索。每次迭代的过程不是完全随机的，如果找到较好解，将会以此为依据来寻找下一个解。令p s o 为一群随机粒子( 随机解) ，在每一次迭代中，粒子通过跟踪两个“极值”来更新自己：第一个就是粒子本身所找到的最好解，叫做个体极值点( 用b 。= ( p ，只：，匕) 表示) ，全局版p s o 另一个极值点是整个种群目前找到的最好解，称为全局极值点( 用g 。，= ( g 。g 。，o i a ) 表示) 。而局部版p s o 中，个体是用其中一部分邻近的粒子作为邻居，所有邻居中的最好解就是局部极值点( 用l 。= ( 厶，厶：，l 。) 表示) 。下图所示的就是p s o 算法的方向示意图：yj否。7l h e v lo剧2 - ip s o 算法方向示意图河海大学硕士学位论文第二章基本粒子群算法从此算法方向示意图，我们可以清楚地看出粒子的运动轨迹要受到g 。和的综合影响。在找到这两个最好解后，粒子根据如下的式( 2 1 ) 和式( 2 2 ) 来更新自己的速度和位置：一+ l = w x + c l r a n d x ( b ，州一x ，) + c 2 r a n d x ( g b e s r x ，)( 2 1 )x = y j + + l( 2 2 )式( 2 1 ) 中的w 称为惯性权重，是与前一次速度有关的一个比例因子，c 、c ：是加速系数( 或称学习因子) ，分别调节向全局最好粒子和个体最好位置方向飞行的最大步长。若太小，则粒子可能远离目标区域缓慢地飞行：若太大，则会导致突然向目标区域飞去，或飞过目标区域。合适的c 、c ：可以加快收敛且不易陷入局部最优。般取c = c ：= 2 ，r a n d 是【o ，l 】之削的随机数。为防止粒子远离搜索空间，粒子的每一维速度心都会被钳位在卜。，屹一】之间，屹。太大，粒子将飞离最好解，太小将会陷入局部最优。假设将搜索空间的第d 维定义为区间【一局。，局。】，则通常。= k + 局。，o 1 后i ，大多数问题时，每一维都采用相同的设置。2 1 3 粒子群算法的运算过程如图2 2 所示，粒子群算法的主要运算过程描述如下：1 ) 种群初始化。随机生成m 个个体作为初始群体p ( o ) 。由于粒子群算法以群体为运算对象，所以我们必须为粒子群操作准备一个出若干初始解组成的初始群体。2 ) 个体评价( 适应度评价) 。计算群体中各个个体的适应度。粒子群算法在搜索进化过程中一般不需要其他外部信息，仅用评估函数值来评价个体或解的优劣，并作为以后粒子群操作的依掘。评估函数值又称为适应度( f i t n e s s ) 。3 ) 根据式( 2 1 ) 、( 2 2 ) 更新粒子群的速度和位置。这是整个粒子群算法中最关键的一步，种群的“个体学习”、和“社会学习”都在这一步实现。4 ) 终止条件判断。若满足终止条件( 达到最大迭代次数或满足最小误差标准) ，则以进化过程中所得到的具有最大适应度的个体作为最优解输出，终止计河海大学硕士学位论文第二章基本粒子群算法算；否则，转至第一步，继续迭代。粒子群优化算法的流程图如下所示：开始初始化粒子群计算每个粒子的适府度根据粒子的适应度更新p b c s f 乖g b e s i根据公式( 1 ) 平公式( 2 )更新粒子群的速度利位置达剑最人迭代次数或者满足最小误著标准j 兰结求幽2 - 2 粒子群算法流剧2 1 4 粒子群算法的特点及其应用粒子群算法具有很强的鲁棒性，与传统的优化技术相比，它采用了许多独特的方法和技术。1 ) 传统的优化算法都是从一个初始点出发，再逐步迭代以求最优解。p s o则不然，它是以一个群体，多点同时出发经过不断迭代求得满意解。2 传统的优化算法不仅需要利用目标函数值，而且往往需要目标函数的导数值等其他一些辅助信息才能确定搜索方向。粒子群算法仅使用由目标函数值变翌塑查兰堡主兰堡笙兰釜兰童薹查垫三! ! ! 堕换来的适应度函数值就可以确定进一步的搜索方向和搜索范围，无需目标函数的导数值等其他一些辅助信息。3 1 传统的优化算法大都采用确定性的搜索方法，一个点到另一个点的搜索转移有确定的转移关系和转移方向，这种确定性往往使得搜索可能永远达不到最优点，因而限制了算法的应用范围。而粒子群算法属于一种群体搜索方法，具有潜在的自适应性。2 2 粒子群算法的发展粒子群优化算法是基于群体智能理论的优化算法，通过群体中粒子间的合作与竞争产生的群体智能指导优化搜索。与一般进化算法比较，粒子群优化算法是一种更高效的并行搜索算法，其概念简单，容易实现，一般代码只有短短的几行，优点显著。粒子群算法也是一种进化算法，但是它没有用遗传算子来更新染色体的基因，而是类似梯度下降算法使得染色体向符合度函数值最高的地方群游。粒子群算法并投有能够给出严格的数学证明，但是在实际应用中被证明是有效的。虽然粒子群算法有很多优点，但是也存在着算法精度较低，易发散等缺点，尤其是当这种算法在解空间内搜索时，有时会出现在全局最优解附近振荡的现象。具体表现在：首先，由于整个粒子群都是根据全体粒子和自身的搜索经验向着最优解的方向“飞行”，在较大的加速项系数作用下，粒子群有可能错过最优解，在远离最优解的空间里发散，使算法不能收敛：其次，在算法收敛的情况下，由于所有的粒子都向最优解的方向群游，所以所有的粒子趋向同一，失去了粒子间的多样性，使得后期的收敛速度明显变慢，同时算法收敛到一定精度时，算法无法继续优化，算法所能够达到的精度较低。针对以上的基本p s o 算法的优缺点，国内外的专家、学者做了大量的工作，提出了很多的改进【1 7 。2 ”。主要的改进算法如下：2 2 i 离散二进制p s o 算法在粒子群算法中如何描述问题的可行解，即把一个问题的可行解从其解空间转换到粒子群算法所能处理的搜索空间的转换方法就称为编码。编码是应用粒子群算法时要解决的首要问题，也是设计粒子群算法时的一个关键步骤。粒子群算法的编码方法主要分为两大类：二进制编码和实数编码。p s o 的基本算法最初是用来对连续函数进行优化的，所以一般采用实数编码。而实际中许多问题是组合优化问题，因此，k e n n e d y 和e b e r h a r t 博士在基本_ 可海大学硕士学位论文第一二章基本粒子群算法p s o 算法的基础上发展了离散二进制p s o 算法来解决这一类问题。离散二进制p s o 算法与基本p s o 算法的主要区别在于运动方程( 式( 2 3 ) 、( 2 4 ) ) ，离散二进制p s o 算法的运动方程如下：k + l = k + r a n d ( 只一x ，) + r a n d x ( g ，一)( 2 3 )i f p s i g ( + 1 ) t h e n x h = 1e l s e x = 0( 2 4 )式( 2 4 ) 中，j i g ( z , “) = i 赢是j i g m 口f d 函数：8 “砷，l 】是随机矢量。粒子的位置只有( o ，1 ) 两种状态，而速度v 与某一概率的门限值相关，速度值越大，则粒子位置取l 的可能性越大，反之越小。在式( 2 3 ) 中没有权重函数w 对速度进行调节，为防止速度v 过大，需设置一v m a x ，使s g r 矽函数不会过于接近0 或1 ，以保证一定的概率使算法从一种状态跃迁到另一种状态。2 2 2p s o 的参数改进与优化基本p s o 的参数是固定的，在对某些函数优化上的精度较差，s h i 提出惯性昕饯雠糊黜触棚一一堕掣，其帆。帆。分别是w 的最大、最小值，i t e r , 。是最大的进化代数。这种改进使算法在搜索初期有着较快的探索能力，而在后期又能进行较精确的挖掘，一定程度上提高了算法性能。但对很多复杂问题，这种改进的效果有限。2 0 0 1 年s h i 又提出了自适应模糊调节w 的p s o ，在对单峰函数的处理中取得了良好的效果，但无法推广。b e r g h 通过使粒子群中的最佳粒子g b e s t 始终处于运动状态，得到了保证收敛到局部最优的g c p s o ，但其性能并不佳。2 2 3l b e s t 模型e b e r h a r t 和k e n n e d y 博士称以上的基本p s o 算法为“g b e s t ”模型。他们也发展了“l b e s t ”模型。在“l b e s t ”模型中粒子所能够得到的信息只有它自己和最近的一组邻居的最好位置l b e s t ，而不是整个群体的最好位置6 虽e 盯。“l b e s t ”模型主要有两种最基本的形式；圆形和车轮形，如下所示o河海大学硕士学位论文第二章基本粒子群算法6135图2 - 3 圆形“l b e s t ”模型0幽2 4 车轮形“l b e s t ”模型结果表明，拓扑结构非常影响算法的性能，且最佳的拓扑形式因问题而定。如对有很多局部最优的函数，车轮形拓扑邻域算法能得到最好的结果，k e n n e d y 推测，这是由于较慢的信息流动；而对于单峰函数，圆形拓扑邻域算法可以产生较好的结果，因为它有较快的信息流动( 这里的拓扑都是在粒子序号空间下的拓扑1 。当然，很多问题的拓扑结构要比以上两种形式复杂的多，这方面的研究也有很多学者在深入研究。2 2 4 混合p s o 模型a n g e l i n e 于1 9 9 8 年提出采用进化计算中的选择操作的改进型p s 0 模型，称为混合p s o 。在a n g e l i n e 的模型中，将每次迭代产生的新的粒子群根据适应函数进行选择，用适应度较高的一半粒子的位置和速度矢量取代适应度较低的一半粒子的相应矢量，而保持后者个体极值不变。这样的模型在提高收敛速度的同时保证了一定的全局搜索能力，在大多数的b e n c h m a r k 函数的优化上取得较基本p s o 模型更好的优化结果。但是必须指出，混合p s o 的收敛速度的提高是以牺牲全局搜索能力为前提的。在解决超高维、非线性、多局部极值的复杂性优化问题时有其局限性，而且实际的工程优化问题的环境往往是动态变化的，采用上述的半数选择机制并不能保证对动态环境的跟踪优化。因此，考虑将模糊系统引入选择机制，根据不同问题制定相应的模糊控制规则，确定合理的输入变量，根据特定的优化问题进行动态的选择将是这种模型下步的研究重点。l o v b j e r g ，r a s m u s s e n 和k r i n k 于2 0 0 0 年提出将进化算法中的交叉操作也引入基本p s o 中。交叉机制首先以一定的交叉概率从所有粒子中选择待交叉的粒、，、，影一。o 一|(罐f 恁河海大学硕士学位论文第一二章基本粒子群算法子，然后两两随机组合进行交叉操作产生后代粒子。后代粒子的位置和速度矢量如下所示：c 删l ( 工，) = p 。p a r e n t i ( x ，) + ( 1 一f ) x p a r e n t 2 ( x ，)( 2 5 )c h i l d 2 ( j ，) = 只。p a r e n t 2 ( x ，) + ( 1 一只) p a r e n t l ( x ，)( 2 6 )幽州k)=1parenq。(v,)+parent2：(7吲)parenti(v,)1parentp a r e n t( 2 7 )”。( ) +：( ) rc h i l d 2 ( 杉) = 1 p a r e n t ，, ( ( k v , ) ) + + p a r e n t ：2 ( ( v , ) ) l 。p a r e n t 2 p a r e n tp a r e n t( 1 ) i( 2 8 )，( k ) +：( ) r1、交叉型p s o 与传统的p s o 模型的惟一区别在于粒子群在进行速度和位置的更新后还要进行上述的交叉操作，并用产生的后代粒子取代双亲粒子。交叉操作使后代粒子继承了双亲粒子的优点，在理论上加强了对粒子间区域的搜索能力。例如两个双亲粒子均处于不同的局部最优区域，那么两者交叉产生的后代粒子往往能够摆脱局部最优。而获得改进的搜索结果。实验证明，与传统的p s o 及传统的遗传算法比较，交叉型p s o 搜索速度快，收敛精度高。目前，利用进化操作改进传统p s o 算法的探索仍在继续。除以上的混合算法之外，还出现了量子p s o ，模拟退火p s o 、耗散p s o 等，也有采取p s o 与基于梯度的优化方法相结合的办法。2 3 常用测试函数为了测试算法的性能，常采用一些著名的测试函数( b e n c h m a r k f u n c t i o n ) 作仿真实验。下面选用了一些常用的测试函数：2巧：f i x ) - - - 2 0 + 2 1 0 c o s ( 2 z 日c , ) ) ，一5 1 2 一5 1 2 ，i = 1 ，2 ( 2 9 )i = l五：厂( x ) = 1 0 0 ( x 12 一x 2 ) 2 + ( 1 一z 。) 2 ，一2 0 1 4 t 2 0 1 4 ，( 2 1 0 )? 则s 一甓，- 1 0 0 x l , x 2 w i 因为适应度函数同目标函数相关，所以目标函数确定1后，取适应度函数f ( x ) = 之，进行参数寻优系统的最优控制参数也就是在满足约j1束条件下，使f ( x ) = 之最大时，z 所对应的控制器参数4 1 2 实现方法针对基本p s o 及其改进算法表现出强烈的趋同性的特点，通过改变部分粒子的运动方向来维持和增加种群的多样性，提高粒子群算法对解空间的搜索能力。该算法的基本思想是：把整个种群分成不同的两个小组，当一个小组的粒子飞向目前的最优解时，另外一个小组反方向飞行，以有效避免算法陷入局部最优的可能性。具体的方法是：借用遗传算法中变异率的概念，将整个种群的数目乘以变异率，产生变异的粒子，这部分变异的粒子，飞行速度的方向不再按照原速度更新公式计算出的速度方向，向整个种群目前找到的最优解飞行，而是朝相反的方向飞行。这样就显著增加了种群在搜索过程中的多样性，使得粒子集聚的程度大大减轻，不至于陷于局部最优解。其他学者提出类似的方法【5 2 1 ，如在在常规的粒子群算法的位置更新公式中加入一个反方向的积分项，相当于加入一个扰动，使得粒子群不会轻易地陷入局部最优解，等等。2 4翌塑盔堂雯主兰堡堕奎塑些皇堕塑王墅苎鎏堕壁旦4 1 3 仿真实验为了验证改进p s o 算法( m p s o ) 的良好性能，针对以下5 种被控对象【4 2 1 ，我们进行了m p s o 算法和p s o 算法的比较研究，得到的平均性能列于表4 一l 中，相应的优化曲线对比和输出特性对比见图4 - 2 - 图4 1 1 ，其中采样周期取t = 0 0 1 s 。 。取0 0 0 3 ，c 取l ， 是随机产生的3 维数组( 三个变量b ，互，乃) 。( 1 ) g ( s ) = k “正s + 1 ) ( 疋s + 1 ) 互= l ，正= 1 ，k = l( 2 ) g 2 ( s ) = 国2 ( s 2 + 2 c o 。争+ 2 ) 0 3 。= l ，亭= 0 2( 3 ) g 】( s ) = 出2 ( s 2 + 2 。争+ 出2 ) 。= l ，f = o 8( 4 ) g 。0 ) = l “1 + s ) 3( 5 ) g 5 ( s ) = l ( 1 + 5 ) ( 1 + o 5 s ) 0 + o 2 5 s ) ( i + 0 1 2 5 s ) f = 0 1本实验每种算法运行1 0 次每次迭代2 0 0 0 代，然后比较m p s o 和p s o 在l o次优化中b e s t j 的平均值以及1 0 次优化得到的b e s t j 的最小值。通过对实验的结果比较发现，m p s o 无论是在得到的b e s t j 平均值还是在b e s t j 的最小值方面都要优于p s o 算法。而且在图4 2 一图4 1 1 的比较中发现，经过m p s o 优化后的控制对象的输出曲线具有平滑，扰动小，超调量小等优点。在以下的图中，虚线对应于m p s o 算法，实线对应于p s o 算法：表4 - 1m p s o 和p s o 的优化性能对比1 0 次优化b e s t j 的平均值l o 次优化b e s t j 的最小值控制对象m p s op s om p s op s oo l ( s )8 9 3 9 41 1 5 2 4 38 5 5 3 39 9 5 6 40 2 ( s )1 1 0 9 9 01 2 6 4 2 79 ，0 7 5 09 1 5 0 7g 3 ( s )8 9 5 3 71 0 0 9 5 48 6 4 7 48 7 1 2 7g 4 ( s )2 3 6 2 4 92 4 4 7 3 02 3 1 3 9 12 4 0 6 8 2g “s )1 5 4 3 3 11 7 4 3 0 21 5 0 4 4 91 6 3 7 3 7河海大学硕士学位论文第叫章改进粒子群算法的应用趔8皤图4 - 2f u n c t i o n l 函数的进化曲线对比图4 - 3f u n c t i o n i 函数输山特性对比图4 - 4f u n c t i o n 2 函数的进化曲线对比姆8 堪_暑o，(_h口河海大学硕士学位论文第p u 章改进粒子群算法的应用图4 - 5f u n c t i o n 2 函数输山特性对比进化代数圈4 - 6f u n c t i o n 3 幽数的进化曲线对比t i m e ( s )图4 - 7f u n c t i o n 3 函数输出特性对比p j o ；-坦翠蝌hjo目-河海大学硕士学位论文第圳章改进粒予群算法的应用3 63 43 2j 四3 0基瞄2 82 62 42 2趔g堪05 0 01 0 0 01 5 0 0进化代数图4 - 8f u n c t i o n 4 函数的进化曲线对比图4 - 9f u n c t i o n 4 函数输出特性对比图4 l of u n c t i o n 5 函数的进化曲线对比=_o*g河海大学硕士学位论文第叫帝改进粒子群算法的应用售臭皇图4 - 1 1f u n c t i o n 5 晒数输出特性对比4 2 改进粒子群算法在其他方面的应用以下