（控制理论与控制工程专业论文）多目标粒子群优化算法的全局搜索策略研究.pdf

摘要粒子群优化算法作为群体智能的一种，模拟了鸟群寻觅食物的生物行为，通过个体信息和社会信息在搜索空间中找寻最优。由于粒子群算法的快速收敛性和实现的简单性等特点，已经引起人们越来越多的关注，已广泛应用于函数优化、神经网络训练、模糊系统控制以及其它应用领域。应用粒子群方法解决多目标优化问题时，确定全局最优解成为一个难点，在大多数情况下，类似于单目标优化的最优解在多目标问题中是不存在的，而是得n - 。组非劣解， 1 p p a r e t o 最优解，并且随着目标数量的增加，非劣解的数量也迅速增加，这将对粒子群算法的优化性能产生很大影响，因为全局最优解选取的“好坏”将直接影响算法的收敛性和分布性。另外粒子群的快速收敛性往往会导致算法收敛到局部最优，这是由于种群快速失去多样性造成的，因此当采用粒子群算法解决多目标优化问题时，改善种群的多样性也十分重要。本文针对粒子群算法解决多目标优化问题时遇到的问题提出了不同的全局搜索策略，具体来说本文的主要内容和创新点可以概括如下：1 对多目标优化问题的基本概念和多目标粒子优化算法进行了概括和总结，为深入研究多目标粒子群优化算法奠定了理论基础。2 提出了基于模糊偏好信息的多种群全局搜索策略。该方法将使用者的先验偏好信息加入到种群搜索中，根据每个目标的相对重要性计算偏好权值，采用主种群和辅助种群的多种群方式搜索目标空间，辅助种群的信息通过信息选择环节传递给主种群，该信息反映了决策者的偏好情况。优化过程中，辅助种群保证了算法的多样性，而主种群对辅助种群提供信息的利用，又保证了算法的收敛性。3 提出了基于优先阶的均衡选择全局搜索策略。该方法有效地解决了非劣解数量在随目标空间增加而增加时，种群选择压力对算法性能产生影响的问题。采用优先阶优化准则代替p a r e t o 优化准则，对非劣解集进一步划分排序以减少非劣解集中的点，只保留“最优折衷解”，并将“最优折衷解 作为全局最优解，对粒子的速度进行更新。均衡选择策略的加入，改善了多目标粒子群算法的收敛性能，均衡了算法的勘探和开采能力，在保证种群收敛至u p a r e t o 前沿的同时，也得到了一组分布性和多样性较i i摘要好的非劣解。4 提出了一种基于迁移操作防早熟的全局搜索策略。该方法针对粒子群算法易陷入局部最优的缺点，将迁移操作引入到粒子的搜索过程中，通过粒子性质的变化，增加了种群的多样性。执行迁移操作的过程中，需要确定的参数少，减少了计算的复杂度，另外迁移操作的水平传播方式使种群在“逃离”局部最优后，依然可以在不影响收敛的前提下，继续在目标空间中进行搜索。关键词：粒子群优化，多目标优化，全局搜索策略，模糊偏好信息，多种群，均衡选择，优先阶，最优折衷解，迁移操作，多样性a b s t r a c tp a n i c l es w a r mo p t i m i z a t i o n ( p s o ) i so n ef o r mo fs w a r mi n t e l l i g e n c e ，w h i c hi si n s p i r e db yt h eb e h a v i o ro fb i r df l o c k s t h ep e r s o n a la n dt h es o c i a li n f b n n a t i o na r eu 8 e dt os e a r c ht h eo p t i m a ls o l u t i o n s i t sh i g hs p e e do fc o n v e r -g e n c ea n dr e l a t i v es i m p l i c i t ym a k ep s od r a wm o r e a n dm o r ea t t e n t i o n p s oa l g o r i t h mh a sb e e ns u c c e s s f u l l ya p p l i e dt om a n yf i e l d s t h em a j nd i f f i c u l t yi nam u l t i - o b j e c t i v ep s o ( m o p s o ) a l g o r i t h mi sh o wt oi d e n t i f yt h eg l o b a lb e s t ，b e c a m et h e r ei sas e to fc o m p r o n u s es o l u t i o n smai n u l t i - o b j e c t i v ep r o b l e m ( m o p ) r a t h e rt h a no n eb e s ts o l u t i o ni nas i n g l e -o b j e c t i v ep r o b l e m t h ep r o p o r t i o no fp a r e t oo p t i m a ls o l u t i o n si nan o n d o m -i n a t e ds e tg r o w sw i t ht h en u m b e ro fo b j e c t i v e s ，w h i c hw i l la f f e c to nt h ep e r -f 6 r m a n c eo fp s oa l g o r i t h m i na d d i t i o n ，t h ef a s tc o n v e r g e n c eo fp s ow i l lr e s u l ti nt h el o c a lo p t i m u m p r e m a t u r ec o n v e r g e n c ei sc a u s e db yt h er a p l dl o 硝0 fd i 、惯s i t yw i t h i nt h es w a r m s ow h e na d o p t i n gp s ot os o l v em o p s ，i ti si m p o r t a n tt op r o m o t et h ed i v e r s i t yo fp o p u l a t i o n i nt h i sd i s s e r t a t i o n ，w ep r o p o s ed i & r e n tg l o b a ls e a r c hs t r a t e g i e st os o l v et h ea f o r e m e n t i o n e dp r o b l e m s a n dt h em a i nc o n t r i b u t i o n so ft h i sd i s s e r t a t i o nc a nb es u m m a r i z e da s o l l o w s ：1 t h eb a s i cc o n c e p t so fm o pa n dt h em o p s oa l g o r i t h m sa r es u m m a -r i z e d w h i c hi st h ep r e p a r a t i o nf o rt h ef u r t h e rr e s e a r c ho nt h em o p s oa l g o r i t h m s 2 am l l l t i s w a r mg l o b a ls e a r c hs t r a t e g yb a s e do nf u z z yp r e f e r e n c ei n f o r m a -t i o ni sp r o p o s e d ，i nw h i c ht h ep r i o rp r e f e r e n c eo ft h eu s e ri sc o n s i d e r e dd u r i n gt h eo p t i m i z a t i o np r o c e s s t h ep r e f e r e n c ew e i g h tv a l u er e f l e c t st h er e l a t i v ei m p o r t a n c eo fo b j e c t i v e t h em a i ns w a r ma n da s s i s t a n ts w a r ma r ea d o p t e d t h ep r e f e r e n c ei n f o r m a t i o nf r o mt h ea s s i s t a n ts 蜘l r ml sc o i l s i d e r e db vt h ei n f o r m a t i o ns e l e c t i o n t h em u l t i - s w a r me n s u r e st h ed i v e r s i t ya n dt h ec o n v e r g e n c eo ft h ea l g o r i t h m 3 a ne q u i l i b r i u ms e l e c t i o no fg l o b a ls e a r c hs t r a t e g yb a s e do np r e f e r e n c eo r i va b s r a c d e ri sp r o p o s e d t h i ss c h e m ec a ns o l v et h es e l e c t i v ep r e s s u r ei nt h es w a r mc a u s e db yt h en u m b e ro fo b j e c t i v e si n c r e a s i n g t h ep r e f e r e n c eo r d e r( p o ) i su s e di n s t e a do fp a r e t od o m i n a n c et oc l a s s i f yt h en o n d o m i n a t e ds o l u t i o n s p oc a l lh e l pr e d u c et h en u m b e ro fp o i n t si nan o n d o m i a t e ds o l u t i o ns e tb yr e t a i n i n go n l yt h o s er e g a r d e da s “b e s tc o m p r o m i s e ，a n dt h e n “b e s tc o m p r o m i s e ”a sag l o b a lb e s tu p d a t e st h ep a r t i c l e sv e l o c i t y t h ee x p e r i m e n t a lr e s e t sc o n f i r mt h a tt h ep r o p o s e da p p r o a c ha c h i e v e sb e t t e rp e r f o r m a n c eo ft h ec o n v e r g e n c ea n dt h es u f i i c i e n td i v e r s i t y 4 a na v o i d i n gp r e m a t u r ec o n v e r g e n c eo fg l o b a ls e a r c hs t r a t e g yb a s e do nt r a n s p o s o no p e r a t i o ni sp r o p o s e d ，w h i c hc a ni m p r o v et h ed i v e r s i t yo fp o p u l a t i o nw i t h i nt h eo p t i m i z a t i o np r o c e s s t h eq u a l i t yo ft h ep a r t i c l ei sc h a n g e db yt h et r a n s p o s o no p e r a t i o n i nt h eo p t i m i z a t i o np r o c e s s ，o n l yaf e wp a r a m e t e r sa r en e e d e d ，w h i c hr e d u c e st h ec o m p u t a t i o n a lc o s t a tt h es a m et i m e ，t h et r a n s p o s o no p e r a t i o ni sf l e x i b l ea n dt h ec o n v e r g e n c eo ft h ea l g o r i t h mc a nb eg u a r a n t e e d s i m u l a t i o n sc o n f i r mt h a tt h ep r o p o s e da l g o r i t h mi se f f e c t i v ei nm a i n t a i n i n gt h ed i v e r s i t yo fp o p u l a t i o n 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 ，m u l t i o b j e c t i v eo p t i m i z a t i o n ，g l o b a ls e a r c hs t r a t e g y , f u z z yp r e f e r e n c ei n f o r m a t i o n ，m u l t i s w a r m ，e q u i l i b r i u ms e l e c t i o n ，p r e f e r e n c eo r d e r ，b e s tc o m p r o m i s es o l u t i o n ，t r a n s p o s o no p e r a t i o n ，d i v e r -8 i t y附件四上海交通大学学位论文原创性声明本人郑重声明：所呈交的学位论文，是本人在导师的指导下，独立进行研究工作所取得的成果。除文中已经注明引用的内容外，本论文不包含任何其他个人或集体已经发表或撰写过的作品成果。对本文的研究做出重要贡献的个人和集体，均已在文中以明确方式标明。本人完全意识到本声明的法律结果由本人承担。学位论文作者签名：王宇丢日期：砌罗年；月e t附件五上海交通大学学位论文版权使用授权书本学位论文作者完全了解学校有关保留、使用学位论文的规定，同意学校保留并向国家有关部门或机构送交论文的复印件和电子版，允许论文被查阅和借阅。本人授权上海交通大学可以将本学位论文的全部或部分内容编入有关数据库进行检索，可以采用影印、缩印或扫描等复制手段保存和汇编本学位论文。保密口，在年解密后适用本授权书。本学位论文属于不保密耐。( 请在以上方框内打“4 ”)学位论文作者签名：王守善指导教师签名：日期：翮，年孑月2 日日期：弘年弓月l z 日1 1引言第一章绪论在许多实际问题中，例如经济、管理、军事、科学和工程设计等领域，衡量一个方案的好坏往往难以用一个指标来判断，而需要多个指标进行比较，这些指标有时是不甚协调甚至矛盾的，那么在给定条件下同时要求多个目标都尽可能的好，并为之确定一个合理的方案就是多目标优化问题。例如在设计新产品时，既要考虑使产品具有较好的性能，又要考虑使其制造成本最低，同时还要考虑产品的可制造性、可靠性以及可维修性等性能，这些设计目标的改善可能相互抵触，比如好的维修性会引起可靠性的降低。由于多目标优化问题在各种实际问题中大量存在，与单目标优化相比，多目标优化显得更加重要，因此多目标优化成为最优化领域的一个重要研究方向。对多目标优化问题寻求单一最优解是不现实的，通常多目标优化是产生一组可选的折衷解，由决策过程在可选解集中作出最终的选择1 1 - 3 。多目标优化的思想萌芽于1 7 7 6 年经济学中的效用理论。1 8 9 6 年，法国经济学家p a r e t o 首先在经济平衡的研究中提出了多目标优化问题，引进了被称为p a r e t o 最优的概念。1 9 4 4 年，数学家n e u m a n n 和m o r g e n s t e r n 又从对策论( 博弈论) 的角度，提出了多个决策者而彼此又相互矛盾的多目标决策问题。1 9 5 1 年，t c k o o p m a n s 从生产与分配的活动分析中提出了多目标最优化问题，并且第一次提出了p a r e t o 最优解的概念。他的工作为多目标优化学科奠定了初步的基础。1 9 6 8 年，z j o h n s e n 系统地提出了关于多目标决策模型的研究报告，这是多目标优化这门学科开始大发展的一个转折点。自从2 0 世纪6 0 年代以来，多目标优化问题吸引了越来越多不同背景的研究人员的注意力，无论在优化理论或应用方面都迅速、蓬勃的开展起来【1 ，2 】。人们设计了不少求解多目标优化问题的方法，并运用它们去解决各种实际问题，取得了一定效果。多目标优化问题具有多个目标函数，各个目标涉及相同的一组决策变量，并相互制约，对其中一个目标进行优化时，必须同时以其它目标作为代价，因此很难客观地评价多目标问题解的优劣。一般情况下，多目标优化问题不存一2 一第一章绪论在唯一的全局最优解，所以实际上的多目标优化往往是如何寻求p a r e t o 解集的过程，而p a r e t o 解集中的元素就所有目标而言是彼此不可比较的，因此不能简单地把多个目标归并为单目标求解。一个理想的多目标优化问题的解决过程可以描述成如图1 一l 一1 所示，该过程以最小化为例，其中s t e p l 是寻找折衷解的过程，s t e p 2 是决策过程，h i g h e r - l e v e li n f o r m a t i o n 通常是由待解决问题的要求或者决策者的偏好提供的，这些信息将帮助决策者从折衷解集中最后确定一个解。图1 1 1 一个理想的多同标优化过程f i g u r ei - i - ia ni d e a lm u l t i o b j e c t i v eo p t i m i z a t i o np r o c e d u r e 传统的多目标算法往往是将多目标问题转换成单目标问题后利用成熟的单目标优化算法求解，其缺点是一次优化求解只能求出一个解【4 】。随着优化理论研究的深入，出现越了越来越多更加复杂的优化问题，这些问题通常涉及很多因素，优化问题的模型难以描述，自变量维数很多，常常达到十维甚至上百维，使得计算量大大增加，这类问题可利用信息较少，因此很难设计出通用的优化算法。特别当多目标优化问题具有无穷多个p a r e t o 最优解，且p a r e t o 最优解集在目标函数空间具有非凸、分段、不连续或分布不均匀等特点时，现有的传统多目标优化算法很难获得理想的结果。因此，对于这类问题设计出合适的多目标优化方法成为亟待解决的问题。自从1 9 世纪以来，数理科学、心理学以及生物科学的发展为人工智能的发展提供了理论基础和生物基础【5 1 。由于生物是自然智能的载体，因此生物学成为人工智能研究灵感的重要来源。伴随着计算机技术的日趋成熟，生命科学与工程科学相互交叉渗透，影响促进。2 0 世纪8 0 年代以来，进化计算作为一类优化技术，通过模拟生物进化过程与机制来求解问题，为解决复杂的优化问题提供了新的思路和方法，受到了人们极大地关注。进化计算技术是一种更为宏观意义下的仿生优化算法，通过对达尔文的“优胜劣汰，适者生存”的进化原理及孟德尔等人的遗传变异理论的模拟，在优化过程中建立类似于自然界生物的进化过程与机制，来达到求解优化与搜索问题的目的。近年来出现的人工神经网络、模糊逻辑以及进化计算就是模拟生物个体的某些特征而发展起来的智能算法f 叫。由于进化计算技术采用基于种群的方式组织搜索，所以这些算法具有高度并行性，并且具有自组织、自适应、自学习等智能特征，这些特征引起了人们极大地兴趣。由于上述方法通过模拟生物的进化过程或社会行为使待处理问题得到解决，因此可以不受搜索空间限制条件( 如可微、连续、单峰) 的约束，且在优化过程中不需要梯度信息 s - l o 。近年来，进化计算在多目标优化问题中获得了越来越广泛的应用和研究。由于其在一次优化求解过程中，可以得到多个优化解，克服了传统优化算法中存在的不足，吸引了众多研究者，甚至有研究者称，在多目标优化领域进化计算可比其它搜索策略得到更好的结果【1 1 ，1 2 】，一系列新颖的多目标进化算法应运而生并获得了良好的应用效果。最近几年多目标进化算法发展更加迅速，从2 0 0 1 年以来，有每两年召开一次的有关多目标进化的国际会议( e v o l u t i o n a r ym u l t i c r i t e r i o no p t i m i z a t i o n ，e m o ) ，在国际刊物“i e e et r a n s a c t i o no i le v o l u t i o n a r yc o m p u t a t i o n ”、“e v o l u t i o n a r yc o m p u a t i o n ”、“g e n e t i cp r o g r a m m i n ga n de v o l v a b l em a c h i n e s ”，以及各类国际进化计算的会议( 如c o n g r e s so i le v o l u t i o n a r yc o m p u a t i o n 、g e n e t i ca n de v o l u t i o n a r yc o m p u t a t i o nc o n f e r e n c e 等) 上所发表的有关多目标进化计算的论文比过去有较大幅度的增加。总结进化计算适合于求解多目标问题的主要原因是：1 基于种群的搜索方式实现了搜索的多样性和全局性，通过重组操作充分利用解之间的相似性，在一次运行中得到多个p a r e t o 最优解；一4 一第一章绪论2 进化算法对待处理问题的目标函数没有特殊的要求，不要求目标函数一定连续或者可导。群体智能作为进化计算的一个研究方向是以社会性动物的群体行为和人工生命理论为基础，研究各种群体行为的内在原理，并以这些原理为基础设计出新的问题求解方法。社会性动物的集体智能行为都有一个共同的特征，即相对简单的个体在没有一个集中控制的情况下，通过相互作用产生复杂的群体行为。从计算机科学角度而言，群体智能就是由智能体组成的系统通过相互之间或者与环境之间的交互作用表现出来的集体智能行为【1 3 1 4 】。在这种集体形式的“智能”中，单个智能体本身只具备一些十分有限的基本功能，而不具备直接解决问题所需的知识或者能力，智能是由整个智能体群体及其环境组成的系统所表现出来的一种极为复杂的全局特性。与传统的基于梯度的优化技术和其它的进化算法比较，群体智能的优点在于【1 5 】：1 无集中控制约束，不会因为个别个体出现问题而影响整个问题的求解，保证了整个系统具备更强的鲁棒性；2 可以小通过个体之间直接通信，而通过非直接通信进行合作，这种非直接的信息交换机制保证了系统的扩展性；3 群体中互相合作的个体是分布的，因此可以作为并行分布式算法模式，充分利用多处理器并很好地适应网络环境下的工作方式；4 对目标函数的连续性无特殊要求；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 0 ) 1 1 6 1 已经在很多优化问题上得到成功应用。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 算法同其它进化算法之间既有共同之处又存在一定的差别。两者都以随机初始化种群为初始迭代点，利用事先定义好的适应度准则来评价系统，并根据适应度进行随机搜索；二者的主要区别在于种群更新算子的过程，进化算法通过交叉变异来产生下一代个体，而p s o 算法则根据历史飞行中产生的两个最优位置来决定搜索方向和飞行速度，从而实现对整个种群的更新。作为一种高效并行优化算法，p s o 算法可以用于解决大量非线性、不可微和多峰值的复杂优化问题。当采用p s o 算法解决多目标优化问题时，下面三个基本问题需要考虑解决【1 7 1 ：1 与单目标优化中只有一个最优解不同，在多目标优化问题中要考虑如何在一组非劣解中选择一个作为最优粒子，以指导整个种群的飞行，即最优粒子的选取问题：2 如何保存种群在搜索过程得到的非劣解，即历史飞行位置的记录问题；3 如何保持种群的多样性，以防止整个种群过快收敛于一个解，即如何防止算法早熟问题。虽然p s o 算法对优化函数的形式没有具体的限制，并且研究者已经提出了许多的多目标粒子群优化算法( m u l t i o b j e c t i v ep a r t i c l es w a r mo p t i m i z a t i o n ，m o p s o ) f 1 8 _ 2 2 】，但在提高算法的全局搜索能力和保持利，群的多样性方面依然存在很多有意义的问题。随着目标数量的增多，p a r e t o t 劣解的数量也将急剧增加，导致种群内的选择压力减少，以p a r e t o 非劣关系作为优化准则的m o p s o 算法难以从众多非劣解中选择出最优个体，最终影响多目标粒子群算法的收敛性能。另外p s o 算法存在的早熟问题，将其扩展到多目标优化问题中依然存在，这会对非劣解在p a r e t o 前沿上的分布产生很大的影响。本文针对上述问题，首先考虑了在有决策者偏好信息的情况下，利用模糊偏好一6 一第一章绪论关系对目标进行划分，减少待优化问题的目标数量，并使用多种群结构增加种群的选择压力，提高算法的全局搜索能力；然后又对不存在偏好信息的多目标问题进行了研究，采用新的优化准则来代替p a r e t o 优化准则，在目标数量较多的情况下，使得多目标粒子群算法在勘探和开采能力方面得到了较好的均衡；最后在前面两种算法研究的基础上，对p s o 算法本身存在的早熟问题进行了研究，将一种新的基因操作方式引入到多目标粒子群优化算法中，在算法收敛性不受影响的前提下，使算法的多样性得到极大的改善。1 2p s o 算法p s o 算法【1 6 l 首先由j a m e sk e n n d y 和r u s s e l le b e r h a r t 在1 9 9 5 年共同提出，其基本思想是模拟了鸟类群体寻找食物的过程，并利用生物学家f r a n kh e p p n e r 的生物群体模型【2 3 】对该社会行为建立了模型。研究者发现，鸟群在飞行过程中经常会突然改变方向、散开、聚集，其行为方式是不可预测的，但是整个群体总保持一致性，个体与个体之间也保持着最合适的距离，不会有碰撞现象发生。通过对类似生物群体的行为研究，发现生物群体中存在着一种社会信息共享机制，它为群体的进化提供一种优势，这也是p s o 算法形成的基础。这种算法的最大特点是容易实现，控制参数少，计算速度快，与其它进化算法相类似，粒子群算法也是通过个体间的协作与竞争，实现复杂空间中最优解的搜索。一般来说，能应用遗传算法解决的问题基本上都可以采用p s o 处理，而且效率可能会更高。1 2 1p s o 算法及改进算法作为一种基于种群操作的优化技术，p s o 算法将群体中的每个个体看作d 维搜索空中一个没有体积和重量的粒子，也即代表一个可能的候选解，粒子在搜索空间中以一定的速度飞行，其飞行所经历过的最好位置就是该粒子本身所找到的最好解，粒子的飞行速度由该粒子的飞行经验和群体的飞行经验进行动态地调整，逐代搜索最后得到最优解。设群体规模为，第i ( i = 1 ，) 个粒子在搜索空间中的位置可以表示为x = 0 l ，z 2 ，z d ) ，其飞行速度可以表示为v = ( v l ，v 2 ，v d ) ，则在第t + 1 代时，第i 个粒子将根据下面的公式来更新自己的位置和速度：v i d ( t + 1 ) = 忱d ( t ) + c l r l ( p t d ( t ) 一z 谢( ) ) + c 2 r 2 溉d ( t ) 一z 记( ) ) ( 1 - 2 1 )1 2p s o 算法一7 一x i a ( t + 1 ) = z 记( t ) + v i d ( t + 1 )( 1 2 _ 2 )其中，d = 1 ，d ，m 为第i 个粒子曾经到过的最佳位置，称为个体极值；黜表示整个种群目前搜索到的最佳位置，称为全局极值；c l 和c 2 为常数，称为学习因子或加速度系数；r l 和r 2 是( 0 ，1 ) 上的随机数。每个粒子的个体极值由下面的公式来更新：黝( + 1 ) = l 融x d ( ( 力t + ，d 萎x i a ( ( t f + + 1 1 ) ) 坛娃时，取v i = v m a x 当v i 4( 1 - 2 8 )1 2 一多一v 伊- 4 i 甲、7从数学角度讲，惯性权值w 和压缩因子x 这两个参数是等价的。e b e r h a r t 和s h i 通过将压缩因子法和种群最大速度钳制法相比较后发现【2 7 】，具有压缩因子的p s o 算法对一些函数可以达到比较好的收敛速度，而对某些函数在经过有限次迭代后，算法却不能达到指定的误差要求。1 2 2 粒子群的拓扑结构粒子群的邻域拓扑结构是指单个粒子如何与其它粒子相互连接的方式，它决定了信息在不同粒子之间传递的方式，包括在每一次迭代中粒子可以直接得到哪些粒子传递的信息，以及信息在粒子之间传递的强度如何，如果信息传递强度太强，那么很容易使系统陷入早熟，反之，使得算法收敛速度变慢，影响计算的效率。邻域拓扑结构是决定p s o 算法效果的一个很重要的因素，不同的邻域拓扑结构，优化效果会有很大的差别。下面将给出在p s o 算法中几种典型的邻域拓扑结构。空连接结构在这种邻域拓扑结构中，粒子之间是孤立的，即没有相互连接，粒子的飞行只参照自己的最优位置阢【2 8 】，在这种情况下，公式f l 一2 - i ) 中的c 2 = 0 。全连接结构这种邻域拓扑结构与空连接邻域拓扑结构完全相反，种群中的所有成员都与其它成员相互连接，其结构如图1 2 1 所示。在这种类型的连接中，信息传递速度比较快，所以收敛速度也比较快，但是容易陷入局部极小点。环形连接结构1 0 一第一章绪论图l 一2 - l 全连接邻域拓扑结构f i g u r e1 - 2 - 1t h ef u l l yc o n n e c t e dn e i g h b o r h o o dt o p o l o g y 所有粒子排成一个环状结构，如图1 2 2 所示，这种结构信息传递速度较慢，收敛速度也较慢，但是不容易陷入局部极小点。在这种结构中，因为粒子只与其相邻的粒子之间分享信息，所以此时公式( 1 2 - 1 ) 中的岛为局部最优信息。图1 - 2 2 环形连接邻域拓扑结构f i g u r e1 - 2 - 2t h er i n gc o n n e c t e dn e i g h b o r h o o dt o p o l o g y 树状网络连接结构在树状网络连接的邻域拓扑结构中，所有的粒子按树状结构排列，每一个树状节点包含一个粒子，如图1 2 3 所示。处在子节点位置的粒子，其在搜索空间中飞行的速度受到其自身最优位置和父代节点的最优位置的影响。如果处在子节点位置的粒子搜索到的解优于父代节点，那么这两个粒子在拓扑结构中的位置进行互换。所以，树状网络连接中的粒子具有动态的邻域。1 2p s o 算法一1 l 一图1 2 3 树状网络连接邻域拓扑结构f i g u r el 一2 1 3t h et r e en e t w o r kc o n n e c t e dt o p o l o g y 1 2 3 参数选择算法参数的选取对算法的性能和效率有很大的影响，如何确定最优参数使算法性能最佳本身就是一个极其复杂的优化过程 3 0 1 。p s o 算法中只有较少的几个参数需要调节，这些参数主要包括：种群规模、学习因子c 1 和c 2 、惯性权值w 、压缩因子x 、最大速度k 炼、最大迭代数死戤等。种群规模在单目标优化中，种群规模通常设定几十个粒子，但在多目标优化等较复杂的问题中，粒子数可以取至s j l 0 0 - 2 0 0 个。s h i 和e b e r h a r t 认为p s o 算法对种群大小不敏感【3 1 】，但在多目标优化问题中种群的规模将会对算法的性能产生很大影响，如计算时间，算法产生非劣解的数量等，因此种群规模在实际问题中的取值应根据具体待解决问题的难易程度具体分析。另外，从计算复杂度分析，种群粒子数较多时，需要进行更多的函数评价，从而增加算法的计算时间，但同时也增加算法的可靠性。所以，在选取粒子数大小时，应该综合考虑算法的可靠性和计算时间。学习因子学习因子c 1 和c 2 用来控制粒子自身飞行经历和同伴飞行经历的相对影响，即粒子在个体极值鼽和伞局极值p 。上的加速度权重。较小的学习因子，可使粒子在远离目标区域内振荡：而较大的学习因子则可使粒子迅速向目标区域移动，甚至又离开目标区域【3 2 】。如果c 1 = c 2 = 0 ，则粒子将以当前速度飞行，直到目标空间边界。此时，由于粒子只能搜索有限的区域，所以很难找到较好的解。一1 2 一第一章绪论当c 1 = 0 _ r c 2 0 时，粒子不具备自身的认知能力，但具有“社会认知”能力，此时，粒子可以在幽的推动下，到达新的搜索空间，且算法的收敛速度更快。但当遇到复杂问题时，没有自身认知能力的算法更加容易陷入局部最优点。当c 2 = 0 且c 1 o n ，粒子之间不共享种群的最优信息。由于个体之间不存在相互交流的信息，种群中没有了协作，此时由个粒子组成的群体相当于个独立的个体在搜索空间中进行搜索，此时得到最优解的概率非常小。经上述分析可知，合适的选择学习因子可以提高算法搜索速度，避免陷入局部最优。通常设c l = c 2 = 2 ，但是这种经验设置也仅局限于部分问题的研究。在压缩因子p s o 算法中，对c l 和c 2 的设置要求满足c 1 + c 2 4 。惯性权值惯性权值取较大值时，全局搜索能力强，局部寻优能力弱。反之，局部寻优能力增强，而全局搜索能力减弱 3 1 1 。公式( 1 2 - 6 ) 虽然可以调节算法全局搜索能力和局部寻优能力之间的平衡，但是仍然存在缺点，迭代初期局部搜索能力较弱，即使粒子已经接近全局最优，也往往错过，而在迭代后期，则因为全局搜索能力变弱，容易陷入局部极值。以a c k l e y 函数【3 3 】为例说明惯性权值w 对种群搜索能力的影响，a c k l e y 函数形式如下：m i n ，c x ，= 一2 。e x p ( 一。2一田叩( 佗一1 妻= 1c 。sc 2 丌z t ，)+ 2 0 + e对a c k l e y 函数自变量取1 0 维进行测试，即n = 1 0 ，除惯性权值w 的选取不同外，其余参数设定都相同。种群规模为3 0 ，学习因子c 1 = c 2 =2 ，最大迭代次数t m 戤= 1 0 0 0 ，粒子飞行最大速度y m 缸= 3 。在搜索过程中w 分别取二三个固定值，即0 4 、0 7 、0 9 ，对每一个惯性权值运行3 0 次实验：在线性递减惯性权值中，w m 缸= 0 7 ，w m i n = 0 4 ，线性递减惯性权值实验运行3 0 次。由图1 2 4 可以看出，当惯性权值取值0 4 时，a c k l e y 函数很快收敛到局部最小值；当w = 0 9 时，虽然全1 2p s o 算法一1 3 一局搜索能力增强，但是算法产生振荡，最终在有限迭代次数内，算法没有收敛；而当w = 0 7 时，算法收敛速度较快，并且搜索到的最优解要优于w = 0 4 时的最优解。当采用线性递减惯性权值法时，迭代初期算法的全局搜索能力要好于w 取固定值时的情况，最终最优解的收敛情况也要优于w = 0 7 时。运代教图1 - 2 - 4 不同的惯性权值对a c k l e y 函数收敛性的影响f i g u r e1 - 2 - 4t h ee f f e c to ft h ed i f f e r e n tw e i g h tv a l u eo i lt h ec o n v e r g e n c eo fa c k l e yp r o b l e m 压缩因子x 和最大速度缸的选取在p s o 算法中压缩因子x 的数学意义与惯性权值w 的数学意义相同，在压缩因子取值较小的情况下，意味着粒子每步搜索的长度将变小，即算法的局部寻优能力增强，反之，大的压缩因子值将增加算法的全局搜索能力。定义最大速度弧与搜索空间之间的关系如下：v 矗骶= ，y 五n 缸( 1 2 9 )其中7 为最大速度与搜索边界的比例系数，强为测试问题搜索空间的上限。默过大，粒子可能飞过较好的解；反之，则粒子的勘探能力下降，从而会陷入局部最优。为说明压缩因子x 和最大速度越对算法性能的影响，以g r i e w a n k 函数删和r a s t r i g i n 函数1 3 3 】为例，采用带压缩因子一1 4 一第一章绪论的p s o 算法进行测试。g r i e w a n k 函数形式如下：酬班1 + 志擎2 一廿( 考)r a s t r i g i n 函数形式如下：m i n f ( x ) = 1 0 n + 暖2 1 0 c o s ( 2 7 r x i ) 】g n e w a n k 函数自变量取3 0 维进行测试，即n = 3 0 ，戤=6 0 0 ；r a s t r i g i n i 函数自变量取3 0 维进行测试，即仡= 3 0 ，x m 馘= 5 1 2 。分别固定x 和联两个参数中的一个，变化另外一个，算法的终止条件是设定的最大迭代数t m 拭= 1 0 0 0 0 ，种群规模为5 0 ，e l = c 2 =2 。选代数图1 2 - 5 西= 4 0 5 时。最大速度v ，m a x 对g r i e w a i l k p 殉数收敛性能的影响f i g u r e1 - 2 - 5t h ee f f e c to ft h em a x i m u mv e l o c i t yo i lt h ec o n v e r g e n c eo fg r i e w a n kp r o b l e mw h e nt h ep a r a m e t e ro f 西i ss e t4 0 5 首先测试最大速度对算法性能的影响，此时压缩因子x 固定。西= 4 0 5 时，根据式1 2 8 ，x = 0 8 ；7 分别取0 1 、0 0 1 、0 0 0 1 ，对每一个1 值运行3 0 次。图1 2 5 和图1 2 6 所示分别为g r i e w a n k 函数和r a s t r i g i n 函数的平均最优适应值随迭代数变化的情况。由图1 2 5 和图1 2 6 可以看出，当。较大时，算法收敛速度快：反之，则收敛速度较慢，甚至陷入局部最优。当1 = 0 0 1 时，搜索能力较强，随着迭代数的增加，最优适应值逐渐收敛，但速度较慢。1 2p s o 算法一1 5 一迭代数图1 2 6 西= 4 0 5 时，最大速度v ，m 鑫x 对r a s t r i g i n 函数收敛性能的影响f i g u r e1 - 2 6t h ee f f e c to ft h em a x i m u mv e l o c i t yo nt h ec o n v e r g e n c eo fr a s t r i g i np r o b l e mw h e nt h ep a r a m e t e ro f 西i ss e t4 0 5 考虑到上述对最大速度缸的分析，在测试压缩因子对算法性能影响时，最大速度与搜索边界的比例系数，y 设定为0 0 1 ，固定腻，分别取4 1 、4 3 和4 5 ，即压缩因子) ( 逐渐减小，对每一个妒值运行3 0 次。图1 2 7 和图1 2 - 8 所示分别为g r i e w a n k 函数和r a s t r i g i n 函数的，f 均最优适应值随迭代数变化的情况。对于g r i e w a n k 函数，由图1 2 7 可以看出，当取值较小，即x 较大时，平均最优适应值随迭代次数的增加，变化比较缓慢；随着值增大，即x 较小时，在有限迭代次数内，算法的收敛速度要好于x 较大的情况，压缩因子对算法收敛速度的影响在r a s t r i g i n 函数中更加明显。1 2 4p s o 算法的缺陷及改进策略世界上没有绝对完美的算法，p s o 算法也不例外。近几年研究者对p s o 算法的改进可谓层出不穷，但就其本质来说，这些改进主要是针对p s o 算法的两个缺点，其一是算法容易陷入局部最优，从而导致得不到全局最优解；其二是p s o 算法的收敛精度问题，也即算法的全