（通信与信息系统专业论文）粒子群优化算法的改进方法研究.pdf

硕士学位论文 m a s t e r st h e s i s s t u d i e so ni 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 n 彳砌e s i s s u b m i t t e d 觑p a r t i a lf u l f i l l m e n to ft h er e q u i r e m e n t f o rt h em sd e g r e e 讯c i r c u i ta n d s y s t e m b y ， x u j i n g p o s t g r a d u a t ep r o g r a m c o l l e g eo fp h y s i c a ls c i e n c ea n dt e c h n o l o g y c e n t r a lc h i n an o r m a lu n i v e r s i t y s u p e r v i s o r ：l i us h i j i n a c a d e m i ct i t l e ：a s s o c i a t ep r o f e s s o r s i g n a t u r e m a y ，2 0 1 1 华中师范大学学位论文原创性声明和使用授权说明 原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师指导下，独立进行研究工作 所取得的研究成果。除文中已经标明引用的内容外，本论文不包含任何其他个人或 集体已经发表或撰写过的研究成果。对本文的研究做出贡献的个人和集体，均已在 文中以明确方式标明。本声明的法律结果由本人承担。 作者签名： 余静 l 一， 日期：少，年占月d - 日 学位论文版权使用授权书 学位论文作者完全了解华中师范大学有关保留、使用学位论文的规定，即：研 究生在校攻读学位期间论文工作的知识产权单位属华中师范大学。学校有权保留并 向国家有关部门或机构送交论文的复印件和电子版，允许学位论文被查阅和借阅； 学校可以公布学位论文的全部或部分内容，可以允许采用影印、缩印或其它复制手 段保存、汇编学位论文。( 保密的学位论文在解密后遵守此规定) 保密论文注释：本学位论文属于保密，在年解密后适用本授权书。 非保密论文注释：本学位论文不属于保密范围，适用本授权书。 fi 作者签名：? 牟确糊张萍f 恬毒 日期：立川年孓一泷日 日期：少b 牟 b 弘 本人已经认真阅读“c a l l s 高校学位论文全文数据库发布章程”，同意将本人的 学位论文提交“c a l l s 高校学位论文全文数据库”中全文发布，并可按“章程”中的规 定享受相关权益。回壶途塞握交卮进卮；旦坐生；畦生；旦三生筮壶! 作者签名：三岔雷争 日辄沙1 年眄洗日 导师 日期： 迕 哼f m 巾 ， 红 戤、 摘要 粒子群优化算法( 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 ) 是自1 9 9 5 年正式提出以 来不断兴起和壮大的一种新的优化问题解决方案，它的概念简单且易于实现，用具 有一定智能的粒子代表具体优化问题中的候选解，通过随机初始化一定规模的粒子 群，并使之不断迭代进化，利用群体和个体的信息快速寻得最优解。这种算法具有 群智能和进化计算两大理论基础，以其参数少设置简单，收敛速度快等优点倍受广 大学者亲睐。目前，为了使p s o 算法表现更为优秀，已发表了大量有关其改进算法 的论文，而且这些改进算法也已成功应用于很多工程优化问题中，并随着改进研究 的不断深入，其应用领域还在不断扩展，性能也得到不断的提高。 本文首先深入研究了基本p s o 的理论基础、基本原理和实现流程，并对算法涉 及的参数进行了分析。然后通过仿真实验对基本p s o 算法的有效性及其实现特点进 行了分析。其次，针对基本p s o 存在的不足，分析了其根本原因，从粒子运动特点 出发，总结了算法需要改进的方面，以及基本的改进方向，并通过已有的改进实例 阐述了该算法改进方法实现及其适用范围。再次，本文通过对基本理论和已有改进 方法的分析，提出了一种基于多智能体理论的多智能粒子群优化算法，给出了该改 进算法的具体的实现步骤，并通过m a t l a b 仿真实验验证了改进方法的有效性，通 过对优化结果进行具体分析，指出了该改进算法的优势和不足。最后，论文总结了 对于改进p s o 算法做出的努力，并对p s o 及其新的改进方法中存在的不足提出了进 一步的研究计划。 实验证明改进p s o 即m a p s o ，对高维多峰值等复杂函数优化问题的寻优表现较 基本p s o 算法更加有效，在一定程度上提高了算法的寻优准确性，减少算法易陷入 局部最优，早熟收敛等问题，真正实现了p s o 算法的全局寻优。但同时该改进算法 也增加了算法的复杂程度。因此，对该算法的理论和性能还需进一步完善。 关键词：粒子群；多智能体；函数优化；全局寻优；早熟收敛； 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 san e wm e t l l o du s e di nt h es o l u t i o no f o p t i m i z a t i o np r o b l e m s s i n c ei tw a sp r o p o s e di n19 9 5 ，t h er e s e a r c ha r t i c l e sa b o u ti t h a v ei n c r e a s e dq u i c k l y t h ec o n c e p to fp s oi s s i m p l ea n de a s yt oi m p l e m e n t i t r a n d o m l yi n i t i a l i z e sac e r t a i ns c a l eo fp a r t i c l es w a r m ，i nw h i c he a c hp a r t i c l e 、i t i lc e r t a i n i n t e l l i g e n c ei s u s e dt or e p r e s e n tt h ec a n d i d a t es o l u t i o ni n t h es p e c i f i co p t i m i z a t i o n p r o b l e m ，a n dt h e nu s e st h ei n f o r m a t i o no ft h eg r o u pa n di n d i v i d u a lp a r t i c l e st of i n da n o p t i m a ls o l u t i o nq u i c k l yt h r o u g ht h ei t e r a t i v ee v o l u t i o n t m sa l g o r i t h m b a s e do nt h et w o t h e o r i e s s w a r mi n t e l l i g e n c ea n de v o l u t i o n a r yc o m p u t a t i o n ，i sf a v o r e db r o a d l yb e c a u s e o fi t sm a n ya d v a n t a g e ss u c ha si t sf e wp a r a m e t e r s ，s i m p l es e t u pp r o c e d u r ea n dt h ef a s t c o n v e r g e n o w a d a y st h e r eh a v eb e e nal a r g en u m b e ro fp a p e r sa b o u tt h ei m p r o v e da l g o r i t h m i no r d e rt om a k et h ep s oa l g o r i t h mp e r f o r mb e t t e r t h e yh a v eb e e ns u c c e s s f u l l ya p p l i e d t ot h ee n g i n e e r i n go p t i m i z a t i o np r o b l e m s a st h er e s e a r c hi sm o r ea n dm o r ed e e p l y , i t s a p p l i c a t i o nf i e l d sa r ea l s oe x p a n d i n g ，a n di t sp e r f o r m a n c ei sa l s og r e a t l yi m p r o v e d t l ：l i sp a p e rf h s t l yd o e sa ni n d e p t hs t u d yo ft h et h e o r e t i c a lb a s i s ，b a s i cp r i n c i p l ea n d r e a l i z a t i o np r o c e s so ft h ep s oa l g o r i t h m i ta n a l y z e st h ei n f l u e n c eo fr e l a t e dp a r a m e t e r s o nt h ea r i t h m e t i cp e r f o r m a n c e ，t h ee f f i c i e n c yo ft h ea l g o r i t h ma n dt h ei m p l e m e n t a t i o n s o nt h eb a s i so fs i m u l a t i o ne x p e r i m e n t s c o n s i d e r i n gt h ed e f e c t so ft h ep s o ，t h i sp a p e r a n a l y z e sw h a ta n dw h i c ha s p e c t ss h o u l db ei m p r o v e do nt h e b a s i so ft h ep a r t i c l e m o v e m e n tc h a r a c t e r i s t i c s ，a n dt h ep a p e ra l s oe x p l a i n st h ei m p r o v e m e n ta n da p p l i e d s c o p eo ft h ea l g o r i t h m b ya n a l y z i n gt h eb a s i ct h e o r i e sa n dt h ei m p r o v e dm e t h o d s ，t h i s p a p e rp r o p o s e sam u l t i a g e n tp 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 mb a s e do nt h et h e o r y o fm u l t i a g e n t s ，a n dg i v e ss p e c i f i cp r o c e d u r e so ft h i sa l g o r i t h m n 圮a u t h o rp r o v e st h e e f f e c t i v e n e s so fi t si m p r o v e m e n tt h r o u g ht h em a t l a bs i m u l a t i o ne x p e r i m e n t ，a n a l y z e s c o n c r e t e l yt h ei m p r o v e dr e s u l t s ，a n dm e a n w h i l ep o i n t so u tt h ew e a kp o i n t s f i n a l l y , t h i s p a p e rs u m m a r i z e st h e a u t h o r ss t u d yo nt h ep s oa l g o r i t h m ，a n dp r o p o s e saf u r t h e r r e s e a r c hp l a n i ti sp r o v e dt h a tt h ei m p r o v e dm a p s oi sm o r ee f f e c t i v et h a nt h eb a s i cp s ow h e n s o l v i n gt h em o r ec o m p l e xm u l t i m o d a lf u n c t i o no p t i m i z a t i o np r o b l e m s 1 1 1 em a p s o t r u l yr e a l i z e st h eg l o b a lo p t i m i z a t i o no fp s ob yi m p r o v i n gt h ea c c u r a c yo ft h ea l g o r i t h m a n ds o l v i n gp r o b l e m ss u c ha st h ep o s s i b i l i t yo ft r a p p i n gi n t ot h e l o c a lo p t i m a l ，o r p r e m a t u r ec o n v e r g e n c e h o w e v e r , m e a n w h i l et h ei m p r o v e da l g o r i t h ma l s oi n c r e a s e st h e c o m p l e x i t y t h e r e f o r e ，t h et h e o r ya n dp e r f o r m a n c eo ft h ea l g o r i t h mn e e dt ob ef u r t h e r p e r f e c t e d k e y w o r d s ：p a r t i c l es w a r m ；m u l t i a g e n t ；f u n c t i o no p t i m i z a t i o n ；g l o b a lo p t i m i z a t i o n ； p r e m a t u r ec o n v e r g e n c e ； 硕士学位论文 m a s t e r st h e s i s 目录 摘要i a b s t r a c t i i 第1 章绪论1 1 1 粒子群优化算法的起源和发展1 1 2 论文的主要研究内容。3 1 3 论文的内容的组织结构3 第2 章粒子群优化算法综述5 2 1 相关理论基础5 2 1 1 最优化理论5 2 1 2 群体智能7 2 2 粒子群优化算法的原理8 2 2 1 粒子群优化算法的全局模式8 2 2 2 粒子群优化算法的局部模式1 1 2 3 粒子群算法的仿真实验及其分析1 2 2 3 1 引入惯性权重w 及其改进策略对p s o 算法的影响1 4 2 3 2 学习因子q 和c ，的设置对p s o 算法的影响1 6 2 3 3 引入收缩因子对p s o 算法的影响1 7 2 4 本章小结1 7 第3 章粒子群优化算法的改进方法分析 1 9 3 1 粒子群优化算法的局限性1 9 3 2 粒子群优化算法的现有改进策略2 0 3 3 改进粒子群算法的经典实例2 l 3 3 1 基于遗传算法的混合粒子群算法( g a p s o ) 2 1 3 3 2 离散粒子群算法( d p s o ) 2 4 3 3 3 多种群协同进化粒子群优化算法( m p s o ) 2 6 3 4 本章小结2 7 第4 章一种新的改进粒子群优化算法 4 1 智能体相关理论2 9 4 2 智能体具有的算子设计3 l 4 2 1 邻域竞争算子3 2 硕士学位论文 m a s t e r st h e s i s 4 2 2 变异算子3 3 4 2 3 自学习算子3 3 4 3 一种多智能粒子群优化算法( m a p s o ) 3 6 4 4 改进的m a p s o 的仿真实验及其结果分析3 8 4 4 1m a p s o 的仿真实验3 8 4 4 2m a p s o 的仿真结果分析4 0 4 5 本章小结4 l 第5 章总结与展望 4 2 5 1 总结4 2 5 2 展望4 3 参考文献 致谢 4 7 硕士学位论文 m a s t e r st h e s i s 第1 章绪论 1 1 粒子群优化算法的起源和发展 每种算法的产生都是为了解决一定的实际问题或者更好的解决这些问题，粒子 群优化算法的产生也不外乎如此。粒子群算法是一种基于迭代的随机优化算法，在 其产生之前广大学者已研究出很多经典的优化算法。如经典的单纯形法、最速下降 法、牛顿法、拟牛顿法、共轭梯度法、信赖域法等，它们适合解决无约束条件的优 化问题，对于更为复杂问题则效果不佳；为了解决日益复杂的各种实际问题，随着 基于仿生学应用的不断发展壮大，人们通过对人工生命( a l ，a r t i f i c i a ll i f e ) 的不断 研究，又产生了一系列受生物或生物群体行为特征及一些自然现象启发的优化算法 ( 称为启发式算法) ，如根据实际需要在2 0 世纪4 0 年代之后相继提出的遗传算法 ( g a ，g e n e t i ca l g o r i t h m ) 、模拟退火算法( s a ，s i m u l a t e da n n e a l i n ga l o g r i t h m ) 、禁忌 搜索( t s ，t a b us e a r c h ) 和人工神经网络( a n n ，a r t i c l en e u r a ln e t w o r k ) 等，这些算法是 源于大自然实际规律和对于实际问题的经验，所谓“站着巨人的肩膀上前进”能走的 更高更远，它们的应用方向和能解决的现实问题也更多更广。人类的一切行为都必 须遵循自然规律，自然规律是经过漫长的历程沉淀而来的，如果加以合理利用一定 能事半功倍地解决问题。 2 0 世纪6 0 年代为了更好利用这些算法，众多学者开始专注于算法的数学模型 和优化算法的研究。为了更好分析问题，选择合适的算法，7 0 年代又提出了问题复 杂度的理论分析，并将问题按其复杂度分为p 问题、n p 问题、n p h a r d 问题和 n p c o m p l e t e 问题等等。随着社会的不断进步科学文明的不断发展，越来越多的n p 完全问题亟待解决，并要求在合理的时间内得到满足实际需要的答案，而原有典型 算法已慢慢不能满足这些条件，急需提出一种新的机制和搜索方法才能有效解决这 些问题。于是自8 0 年代以来，人们掀起一场启发式算法的研究热潮。对启发式算 法的研究包括对已有算法的改进和完善以及开发新的算法。自1 9 7 5 年h o l l a n d 6 1 模 拟生物进化规律模型提出遗传算法以来，人们发现了生物个体和生物群体活动遵循 一定规律，不同个体或群体还有不同规律，如蚁群、鸟群等觅食规律，这些规律与 寻优算法不谋而合。于是1 9 9 5 年美国电气工程师e b e r h a r t 和社会心理学家k e n n e d y 提出了模拟鸟群觅食活动的粒子群优化算法【l 捌( 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 ) 。 这种算法是基于两种理论基础( 即人工生命和进化计算) 的一种新的优化算法，它 的优点有：( 1 ) 概念简单，参数少且易于调整和控制；( 2 ) 收敛速度较快，收敛效 硕士学位论文 m a s t e r st h e s i s 率高；( 3 ) 有深刻的智能基础，十分适合研究和应用。( 4 ) 采取实数编码，便于确 定初始解和问题的维数。( 5 ) 对初始解得设置依赖性不强，寻优能力较强。它还是 一种全局优化算法，能较准确找寻全局最优。虽然该算法从提出到现在虽只有短短 十几年时间，但其研究成果还是相当多的，这些成果还在不断增多。 最开始，e b e r h a r t 等将“p s o 应用于人工神经网络权重i ) l l 练”【l 】中，通过实验证 明了该算法的有效性；之后，鉴于粒子群算法也存在和其他算法一样的问题如易早 熟收敛，易陷入局部最优( 如在多峰函数最值求解时得到的是其中的一个极值而不 是最值) ，在解决多目标多约束或者高维复杂问题时出现准确性低或者收敛慢等问 题，人们又提出了大量改进方法。如s h i 等提出加上惯性因子及其设置方法的改进 算法、v a nd e nb e r g h 提出使粒子群中最佳粒子始终运动保证局部收敛的改进方法、 k e n n e d y 提出基于一系列拓扑结构的改进算法等等。由于各种优化算法有其各自优 点和缺点，为了充分发挥其优点，得到真正最优结果，众学者又纷纷提出各种混合 改进算法。如a n g e l i n e t 4 l j 将选择算子引入p s o ，保证每代粒子群的较好性能，h i g a s h i 等m 】提出多种基于变异操作的p s o 算法。这些改进均是为了提升p s o 算法性能， 权衡其局部和全局搜索能力，达到解决各种优化问题的目的。 随着粒子群算法的各种改进策略的提出，其性能也能得到一定提高。与遗传算 法等相比，它的概念简单易于实现，参数易于控制，于是大家纷纷尝试将其应用到 各种优化问题中。通过大量实验，人们发现它是连续非线性问题、组合优化问题以 合整数非线性优化问题的可靠工具，其发展潜能相当大，特别是在多目标多约 化问题、聚类、调度、模式识别、决策和机器人等方向的应用。总之，粒子群 的研究虽有一定成果，但仍将继续，其以后发展研究主要的方向有【3 。5 】： ( 1 ) 算法数学模型、收敛性证明等理论研究；目前虽通过实际应用证明了p s o 的收敛性和有效性，但由于健全的理论基础还未建立，对其数学模型和利用模 其收敛性进行验证还需投入大量研究。 ( 2 ) 算法参数调整【4 3 半】和其调整策略研究。该算法参数较少虽易于控制，但由于 参数对算法的影响不同，如何权衡利弊，得到最佳效果还有待进一步研究。 ( 3 ) 算法的局部和全局搜索能力权衡调整研究。标准的p s o 是一种全局优化算 容易出现优化效率不高，要求较多次迭代才能得到最优解的问题，于是有人提 局部p s o 算法，但这种算法又易早熟收敛，陷入局部最优。为了既较快得到最 有不陷入局部最优，我们需要合理权衡局部和全局最优，即选择更有效的邻域 机制( 即拓扑结构) 。 ( 4 ) 基于其他算法操作或其他理论的混合p s o 算法【4 5 l 研究。鉴于各算法各自的 2 硕士学位论文 m a s t e r st h e s i s 优点和缺点，取长补短，更好发挥算法性能，我们需要结合其他算法的基本操作和 理论改进算法现有的不足。除了结合其他优化算法理论，我们当然也可以结合其他 相关理论，如没有免费午餐理论、可拓学理论等。这些理论的加入在一定程度可以 方便算法的实现，人们也还在不断联系算法与其他理论，促进算法性能的改进。 ( 5 ) 算法的应用领域开拓研究。p s o 算法是个有发展潜力的优化算法，虽然人们 己成功将其应用于很多实际问题中，但其适用性还有待发现拓展。 1 2 论文的主要研究内容 粒子群算法作为一种优化算法，以其流程简单易懂，搜索速度快，编码容易， 改进方法多样等特点为广大学者选择。对于非线性连续问题和离散优化问题的解决 都有相应的改进算法予以解决并能有效得到人们需要的答案。但毋庸置疑它还是多 少存在无法准确得到全局最优，容易得到局部极值或者不易收敛等问题。为了既得 到最优解又能较快收敛，人们不断提出相应的改进方法，如a 1 k a z e m i 4 6 】为扩大搜 索空间提出的m u l t i p h a s ep s o 算法，在粒子群中随机选取一部分粒子向全局最优 粒子方向飞翔，其他粒子则向其相反方向飞翔，从而保证全局寻优；还有b a s k a r | 4 7 】 等提出的基于协同进化的p s o 算法，通过将粒子群分为多个群体分别同时优化不同 维的参数实现多种群协同优化来尽快找到全局最优，等等这些改进，都或多或少的 改良了原来p s o 算法的一些性能。 为了更好解决p s o 算法存在的一些问题，本文将就p s o 算法在面对高维多峰 值等更为复杂优化问题时出现寻优不准确或早熟收敛陷入局部最优问题展开研究， 并提出新的改进方法。通过基准函数验证标准算法和改进算法的有效性，并将原始 p s o 算法和改进之后的m a p s o 算法的仿真结果进行对比，并作出分析和评价，制 定了下一步改进的方向。 实际工程应用中的优化问题有很多，近年来利用p s o 及其改进算法来解决得问 题基本涵盖了其他较先提出的优秀寻优算法如遗传算法所能解决的问题范围。为了 便于验证经过改进p s o 算法的有效性和实用性，很多人采取了利用测试点函数检测 算法的方法，这些测试点函数都是具有一定代表性的函数，能从不同角度检验算法 的寻优能力。本文也采用m a t l a b 7 1 0 对标准p s o 和新的改进p s o 一多智能粒 子群优化算法进行了仿真实验，选取了三种多维测试函数，验证了算法改进的效果。 1 3 论文的内容的组织结构 本论文将以粒子群优化算法的改进为重点，给出一种新的改进方法，力求到收 敛精度和收敛速度的更好组合。 硕士学位论文 m a s t e r st h e s i s 其主要内容如下： 第一章介绍了粒子群优化算法的理论来源和研究现状，分析了该算法的研究主 要研究成果，总结了该算法的研究意义。 第二章首先说明了p s o 算法的基本理论基础以及基本算法的实现原理和流程； 其次，对算法中仅有的几种重要参数进行了分析，通过在m a t l a b 7 1 0 的环境下 对基本p s o 进行仿真实验，验证了算法实现寻优的有效性，同时讨论了参数设置对 算法性能的影响。最后总结了基本p s o 算法的研究方向，引出下一章节的内容。 第三章通过前面两章的介绍，总结基本p s o 算法的缺点，并针对这些缺点总结 了基本的改进策略和方向。接着，又通过具体实现了的几种经典的改进算法作出了 具体介绍和分析，了解算法具体改进的实现，为下文新的改进算法的提出奠定基础。 要从根本上改进基本p s o 算法存在的不足，必须提高算法后期粒子多样性，更 好调节算法的局部搜索和全局搜索能力，寻找更快更准收敛于局部最优的方法。基 于这些目标，提出了多种群协同进化、并行计算、混合算法等思想，为下文的改进 算法提供了信息。 第四章依据对p s o 算法的分析和研究，主要提出了一种新的改进算法即多智能 群优化算法，运用多智能体的基本操作，提高粒子的寻优性能。本章首先详细 了多智能体系统理论以及智能体的三种智能算子；接着，给出改进算法的基本 和流程，并用仿真软件仿真其寻优过程；最后，分析了仿真结果，总结该改进 的优势和不足，针对不足制定了下一步的研究目标。 第五章总结了全文的研究内容和方法，分析了本文研究思路，以及所作的工作 作成果，并针对论文工作中的不足以及未涉及到的部分提出下一步要进行的研 向的展望。 4 硕士学位论文 m a s t e r st h e s i s 第2 章粒子群优化算法综述 粒子群优化算法是基于人工生命和进化算法两大理论的一种新型优化算法。算 法的模型来源于对鸟群觅食行为的模拟。人工生命( a r t i f i c i a ll i f e ) 是人工智能 ( a r t i f i c i a li n t e l l i g e n c e ) 的一个热门研究方向，它是通过整合、计算的方式来理解 自然界中的生物。它是基于计算机科学、信息科学、工程技术等的一门交叉学科， 主要研究利用计算技术研究生物现象和利用生物技术研究计算问题这两方面的问 题，特别是后者。对鸟群的研究就是其中一特例，它是对生物群体社会性的一种研 究，并讨论了个体之间的社会协作关系，从而设计了粒子群算法。试想一群鸟是如 何找到食物的，它们活动的特点有哪些。通过对鸟群行为的c g 动画仿真，r e y n o l d s 总结出复杂鸟群的活动遵循以下准则【6 】： ( 1 ) 与自己最近的个体保持距离。 ( 2 ) 向已知的食物所在地点靠近。 ( 3 ) 向鸟群的中心靠近。 正是依靠这些准则，鸟群才能尽快找到食物所在地点。p s o 算法正是基于这些行为 特点的优化算法，它和遗传算法一样都是基于迭代的，但又和遗传算法不一样，它 没有像遗传算法一样有选择、交叉、变异等操作，它是通过个体间的认知共享从而 找到目标值的。 进化计算【3 9 】是人们受自然界生物进化启发得到的一种计算技术，它包括进化规 划、遗传算法、进化策略和遗传规划。群体中每个个体( 问题的可能解) 都遵循适 者生存法则进化，正是依据这种法则随着不断地进化个体达到改善目的。进化算法 一般都有如下过程：( 1 ) 对群体的随机初始化；( 2 ) 计算个体的适应值并与最优 解联系；( 3 ) 按个体适应值取得按照一定概率复制个体；( 4 ) 判断是否达到终止 条件，如果达到则终止计算，输出结果，反之转到步骤( 2 ) 。粒子群算法和其他 进化算法一样都是模拟生物行为，但不遵从“适者生存”法则，它是利用所有粒子间 的合作与竞争机制，共同协作找到最优解得过程。 2 1 相关理论基础 2 1 1 最优化理论 最优化是人类在各种实践活动中的追求目标，不管在哪种环境和问题面前，我 们都趋向于在尽可能满足现有条件下达到最好的效果。因此，最优化问题已经成为 现代的一个很重要的课题，它涉及问题遍及众多学科，其应用更是遍及人工智能、 硕士学位论文 m a s t e r st h e s i s 模式识别、决策系统、系统控制、生产调度和计算工程等各个领域。对于最优化概 念，定义如下： 定义2 1 ：最优化问题【3 j 即在满足一定的约束条件的情况下，寻求一组参数值， 使得某些量的值最满足我们当前需要和要求。其数学模型如下： s mi n8 = f i x ) is t x s = x g i ( x ) o ，i = 1 ，2 ，1 1 ( 2 1 ) 式( 2 1 ) 中，芷敢x ) 为目标函数( o b j e c t i v ef u n c t i o n ) ，s 是约束域，实际问题中，大 多是要实现某个值的最大化或最小化得同时还要满足某些代价，因此定义g i ( x ) 蔓3 约 束函数( c o n s t r a i n t s ) ，一般约束条件不只一个，于是有必要设定i 为x 的维度，x 是n 维优化变量。虽然不是所有问题都求其最小化，但其最大化也是可以化为最小化问 题的，因此上述公式对于最大化问题也是适用的【6 】。 在实际应用中优化问题【3 j 所涉及的面比较广，其分类自然繁多，目前光是在工 程领域就有很多种类，按问题的各种性质就可分为：线性规划问题与非线性规划问 题、单目标优化或多目标优化、确定性或者随机规划问题等等；按问题的复杂度可 分为：p 问题、n p 问题、n p h a r d 问题和n p c o m p l e t e 问题等等；总而言之大体上 从应用上可将所有优化问题分为函数优化和组合优化问题两大类。 对于函数优化问题，主要对象是在一定范围内连续变化的自变量，一般是针对 一些基准点函数进行，这些函数常被用来测试优化算法的可行性、准确性和收敛性 等性能。 目前有很多这样的测试函数，常用的有：s p h e r em o d e l ，s t e pf u n c t i o n ，g e r n e r a l i z e d g r i e w a n kf u n c t i o n ，g o l d s t e i n p r i c ef u n c t i o n 等等。这些函数中有的是含一个自变量 的，有的含有多个变量；有的只有一个极值有的含有多个；有的只有一个约束条件 有的却带有多个。这些特性各异的函数有助于我们模拟不同复杂程度的实际问题， 测试我们所提出的优化算法对于解决相应类型的问题是否有效。 与函数优化不同，组合优化问题的对象是离散的，设每个离散状态对应一组离 散的值，每个离散状态对应一个目标函数值，问题的关键是在这些离散状态中寻求 是目标函数达到最优的目标函数值。典型的组合优化问题如旅行商问题即t s p ( t r a v e l i n gs a l e s m a np r o b l e m ) ，聚类问题( c l u s t e r i n gp r o b l e m ) 、加工调度问题( 即如 f l o w s h o p ，j o b s h o p 等s c h e d u l i n gp r o b l e m ) ，还有着色问题、o 1 背包问题等等。针对 这些组合优化问题，人们也构造了一些b e n c h m a r k 问题模型，帮助测试用于解决这 类问题的算法。 不管是函数优化还是组合优化都有很强的工程代表性，求解这类问题十分复 6 硕士学位论文 m a s t e r st h e s i s 杂，特别是在实际应用中，为了解决各种优化问题，各国学者不断提出不同的优化 算法，经过理论和试验证明了其有效性，也将很多算法成功用于实际问题中。 定义2 2 ：优化算法即一种搜索机制，通过一定的规则和方法来搜索得到实际 问题中在满足一定需求的条件下得到的最优解。 通过对目前常用的方法进行整理总结，可将优化方法分类如下： 法严蕃 广推断类算法 启发式算法厂定点算法 l 局部搜索算法 l 梯度算法 后启发式算法 r 模拟退火算法 i 随机爬山法 i l 重复局部搜索 厂演化规划 l 遗传算法 j 蚁群算法 1 文化算法 l 变异算法 l 粒子群优化算法 图2 1 已有优化算法主要分类 由上面分类我们可以看到，对于优化问题的解法有很多种，粒子群优化算法只 是其中一种，它是一种随机优化算法，也是基于群体智能的新的启发式算法【_ 7 - 9 。 2 1 2 群体智能 每一种生物的产生，都是经过漫长岁月的优胜劣汰规则进化而来的，其生活习 性都存在一定的规律。这些生物有些喜欢独处，有些则向往群居，不论怎样，它们 都处于一定的环境中，需要去改变适应各自的环境。我们一般给这种环境取名为社 会，人也好动物也好，它们都有各自生存的群体。这些复杂的群体，组成了一种生 法 法 算 毙 解 体 单 群 厂i、lil 法 结 算 簿 獒 类 定 瘁 硫 概 硕士学位论文 m a s t e r st h e s i s 物社会系统。随着仿生学理论的广泛应用，人们越来越关注生物群体这一复杂适应 系统的行为特征，并将其应用于各种计算和搜索算法中。如2 0 世纪末由意大利学 者d o r i g o 首次提出的蚁群算法1 6 】。群居的蚂蚁之所以能维持群居，需要通过它们特 有的交流方式，在觅食的时候蚂蚁将自己找到的食物的消息告诉自己的同伴。经过 研究发现它们的信息交流是通过留下踪迹、追踪踪迹等行为，通过这种行为才能让 自己和自己的同伴快速找到更多食物。它们在觅食途中会分泌一种物质( 我们称之 为信息素( p h e r o m o n e ) ) ，其他同伴能沿着有信息素的路找到食物远。通过模拟这 种模型，蚁群算法产生了，并被成功应用于求解组合优化问题( 如旅行商问题，t s p ) 。 群体智能算法之间或多或少都存在一些共性，一种算法的提出，必定会启发人 们对更多群体的关注，如鱼群和鸟群。于是在美国气工程师e b e r h a r t 和社会心理学 家k e n n e d y 的努力下，模拟鸟群的随机寻优算法粒子群优化算法诞生。这种算法一 经提出便引起广大学者的关注，由于其高效的搜索机制和简单模式，在理论和应用 上的研究成果可谓层出不穷。人们最先把粒子群算法应用于人工神经网络和连续的 函数优化问题，与传统算法相比，这种方法同样有效。之后又提出了适合解决离散 问题的二进制离散粒子群算法。为了解决更多问题和更好的解决这些问题，人们又 提出了更多改进意见。 2 2 粒子群优化算法的原理 粒子群优化算法的提出是基于对鸟群觅食行为的模拟，所以在介绍其具体原理 之前，我们先介绍下鸟群是如何觅食的：一群鸟在寻找食物，仔细观察鸟群行为我 们会发现它们会突然散开或者聚集，是什么让它们采取这种同步的行动呢? 这就是 鸟群知识共享的搜索模式，即通过自己已有的认知( 知道自己与食物源所在地的距 离) 与同伴认知( 知道谁离食物最近) ，朝着离自己最近的食物所在处运动，从而 才能最快最有效地找到食物所在。粒子群优化算法( p s o ) 的寻优机制正是模拟这 一过程。 2 2 1 粒子群优化算法的全局模式 原始的粒子群算法是一种全局寻优【l9 】算法，即在允许的搜索空间全面搜索最优 位置直至找到全局最优位置，其基本原理与鸟群运动十分相似。算法中的粒子相当 于鸟群中鸟的角色，我们在优化理论中把它定义为优化问题中的可能解，寻优过程 可以看作：首先在解空间内随机确定一群粒子，然后通过目标函数评价的群中每个 粒子适应值，通过追随各自了解的最优位置，不断进化，最终找到最优解。 算法数学模型建立如下： 8 ： 硕士学位论文 m a s t e r st h e s i s 设有一个解空间为n 维的问题，设置一个大小为m 的粒子群，第i 个粒子的位 置为：z = ( xn ，薯2 ，) ，速度为：巧= ( _ 。，m ：，v , n ) ，速度决定了粒子每次移动 的距离和方向，根据描述问题的目标函数计算粒子当前的适应值，用于衡量粒子的 优劣。设p b , = ( 易。，b ：，) 为到目前为止第i 个粒子在搜索空间内运动所经历的 最佳位置，p g = ( p g l ，p 9 2 ，p g d ) 为全部粒子到目前为止发现的最佳位置。 粒子的位置和速度根据下面式子逐代更新： i 圪( 尼+ 1 ) = 圪( 忌) + q r i ( p b 。一( 七) ) + c 2 r 2 ( p g 一x m ( k ) )，1 、 1 ( 七+ 1 ) = ( 七) + ( 七+ 1 ) 式( 2 2 ) 中k 表示粒子当前的代数，i = l ，2 ，m ，表示问题的维数，n = l ，2 ，n ，表示 群体中每个粒子的编号，n 即为设定的粒子群的规模，c l 和c ，在速度的更新公式中， 影响着粒子向自身经验和群体经验运动的动力，因此常被形象的称为学习因子或者 加速因子。如果适当调整这两个因子，我们会发现它们对收敛性的影响不是很大， 但可以使粒子尽量不向局部最小靠拢，从而提高了收敛速度。而参数和巧是两个 介于( o ，1 ) 之间的随机数，它们的作用是保持粒子的多样性，从而减少算法陷入局 部最优。 式( 2 2 ) 中第一个式子的第二项由于与粒子在寻优过程中所有亲身经历有关，因 此通常称之为粒子的自我“认知”部分，代表了粒子