（计算机软件与理论专业论文）微粒群算法及其在作业车间调度中的应用.pdf

111啕 f 原创性声明和关于论文使用授权的说明 原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师的指导下，独 立进行研究所取得的成果。除文中已经注明引用的内容外，本论文不 包含任何其他个人或集体已经发表或撰写过的科研成果。对本文的研 究做出重要贡献的个人和集体，均已在文中以明确方式标明。本声明 的法律责任由本人承担。 论文作者签名：立：! 垒重 日期：塑塑! 三每 关于学位论文使用授权的声明 本人完全了解山东大学有关保留、使用学位论文的规定，同意学 校保留或向国家有关部门或机构送交论文的复印件和电子版，允许论 文被查阅和借阅；本人授权山东大学可以将本学位论文的全部或部分 内容编入有关数据库进行检索，可以采用影印、缩印或其他复制手段 保存论文和汇编本学位论文。 ( 保密论文在解密后应遵守此规定) 论文作者签名：窒! 】垒重导师签名：超苎望竺日期：翌! 乏竺l 。 目录 摘要i a b s t r a c t i i 第一章绪论1 1 1 研究背景及优化算法简介1 1 2p s o 算法的现状2 1 3 本文主要研究内容及组织结构2 第二章基本微粒群优化算法4 2 1 微粒群算法简介4 2 2 基本微粒群算法4 2 3 参数分析5 2 4 基本微粒群算法流程7 2 5 复杂环境下的应用7 2 5 1 离散优化8 2 5 2 多目标优化8 2 5 3 约束优化9 2 5 4 动态优化9 2 6p s o 算法的特点及改进9 第三章提高微粒群算法计算效率的策略1 2 3 i 算法的具体参数设定和调整策略1 2 3 1 1 带惯性权重的微粒群算法1 2 3 1 2 线性递减权重法1 2 3 1 3 自适应权重1 3 3 1 4 随机权重策略1 3 3 1 5 增加收缩因子1 4 3 1 6 基于模糊系统的惯性因子的动态调整1 5 3 1 7 其他参数的变化1 5 3 1 8 其他方面的改进1 6 3 2p s o 算法拓扑结构的改进1 6 3 3 与其他智能算法相结合1 7 3 3 1 基于遗传思想改进微粒群优化算法1 7 3 3 2 混沌微粒群优化算法1 9 3 3 4 基于模拟退火的微粒群优化算法2 1 第四章基于模拟退火的微粒群算法2 2 4 1 算法思想2 2 4 2 算法流程：2 3 4 3 仿真实验结果2 4 第五章用模拟退火微粒群混合算法求解j s p 问题2 6 5 1 作业车间调度的描述2 6 5 2 作业车间调度的p s o 算法研究3 0 5 3 作业车间调度的混合微粒群优化算法3 1 总结3 8 致谢4 0 参考文献4 1 攻读学位期间发表的学术论文目录4 6 l o t a b l eo fc o n t e n t a b s t r a c ti nc h i n e s e i a b s t r a c ti ne n g l i s h i i c h a p li n t r o d u c t i o n 1 1 1b a c k g r o u n da n di n t r o d u c t i o no fa l g o r i t h mo p t i m i z a t i o n 1 1 2t h es t a t u so fp s oa l g o r i t h m 1 1 3t h em a i nr e s e r c hc o n t e n ta n ds t r u c t u r eo ft h i sp a p e r 2 c h a p 2b a s i cp a r t i c l es w a r mo p t i m i z a t i o n 4 2 1i n t r o d u c t i o no fp s oa l g o r i t h m 。 4 2 2t h eb a s i cp a r t i c l es w a r ma l g o r i t h m 4 2 3p a r a m e t e ra n a l y s i s 5 2 4t h eb a s i cp r o c e s so fp 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 m 7 2 5a p p l i c a t i o no fc o m p l e xe n v i r o n m e n t 7 2 5 1d i s c r e t e0 p t i m i z a t i o n 7 2 5 2m u l t i o b j e c t i v eo p t i m i z a t i o n 8 2 5 3c o n s t r a i n e do p t i m i z a t i o n 8 2 5 4d y n a m i c0 p t i m i z a t i o n 9 2 6p s oa l g o r i t h mc h a r a c t e r i s t i c sa n di m p r o v e m e n t 9 c h a p t e r3t h es t r a t e g yt oi m p r o v et h ee f f i c i e n c yo fp s oa l g o r i t h m 1 3 3 1a l g o r i t h ms p e c i f i cp a r a m e t e rs e t t i n ga n da d j u s t m e n t 1 3 3 1 1p s ow i t hi n e r t i aw e i g h t 1 3 3 1 2l i n e a rd e c r e a s i n gw e i g h t 1 3 3 1 3a d a p t i v ew e i g h t 1 4 3 1 4r a n d o mw e i g h ts t r a t e g y 1 4 3 1 5i n c r e a s et h es h r i n k a g ef a c t o r 1 4 3 1 6f u z z yi n e r t i af a c t o ro ft h ed y n a m i ca d j u s t m e n t 1 6 3 1 7c h a n g e si no t h e rp a r a m e t e r s 1 6 3 1 8o t h e ri m p r o v e m e n t s 1 6 3 2i m p r o v e dp s oa l g o r i t h mf o rt o p o l o g y 1 6 3 3c o m b i n e dw i t ho t h e ri n t e l l i g e n ta l g o r i t h m s 1 7 3 3 1b a s e do ng e n e t i ci d e a st oi m p r o v ep a r t i c l es w a r mo p t i m i z a t i o n 3 3 2c h a o sp a r t i c l es w a r mo p t i m i z a t i o n 1 9 3 3 4p 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 ns i m u l a t e da n n e a l i n g2 1 c h a p4p 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 ns i m u l a t e da n n e a l i n g 2 2 4 1t h o u g h to ft h ea l g o r i t h m 2 2 4 2a l g o r i t h mf l o w ：2 3 4 3s i m u l a t i o nr e s u l t s ：2 4 c h a p5p s ow i t hs i m u l a t e da n n e a l i n gh y b r i da l g o r i t h mf o rs o l v i n gt h e p r o b l e mj s p ：2 ( ； 5 1d e s c r i p t i o no fj o bs h o ps c h e d u l i n g 2 6 5 2r e s e a r c ho fp s oa l g o r i t h mf o rj o bs h o ps c h e d u l i n g 3 0 5 3h 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 nf o rj o bs h o ps c h e d u l i n ga l g o r i t h m 3 l s u m m a r y ：3 ； t h a n k s 4 l r e f e r e n c e s 4 1 p u b l i s h e dp a p e r s z 1 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 算法) 源于对生物界鸟 群群体运动行为的研究，通过群体间个体的合作与竞争来实现对优化问题的求 解，是一种群智能优化算法，由于它的原理简单，参数少，收敛速度快，很快成 为新的研究热点。该算法已经在函数优化、神经网络训练、组合优化等许多领域 得到广泛应用，并取得了较好的效果。但是由于实际工程问题的复杂性、约束性 等特点，使得简单的p s o 算法难以满足实际需要，有大量的问题值得研究和改 进。 本文主要研究p s o 算法，首先讨论p s o 基本算法，分析了该算法的原理及 算法流程，并对参数的设置进行归纳，讨论了p s o 算法在具体参数设定和调整 策略、p s o 算法拓扑结构、与其他智能算法相结合三个方面进行的改进。然后， 作为微粒群算法改进策略的一种，讨论基于模拟退火的微粒群算法，比较基于模 拟退火微粒群算法和基本微粒群算法的计算效率。重点比较了两种微粒群算法的 收敛速度，能否有效地避免早熟，得到解的优化程度等特征。通过用基本测试函 数进行实验，验证了模拟退火微粒群算法的优越性。最后，将基于模拟退火的微 粒群算法应用于作业车间调度( j s p ) 问题的求解，针对最小化最大完成时间的 j s p 问题，给出一种基于随机键和析取图的编码和解码方式，采用关键路径法生 成调度并对微粒进行评价，在使用微粒群优化操作的同时，设计一种基于关键路 径的邻域结构，基于模拟退火策略进行局部搜索以提高算法的整体性能。经实验 测试，基于模拟退火p s o 算法对各算例均能获得最优解，有很好的搜索质量。 同时，算法多次独立运行所得平均值和最差解非常接近，甚至相同，所以算法对 初始群具有较好的鲁棒性。且优于多种p s o 改进算法，取得了较好的结果。 关键词：微粒群优化算法；优化算法；d $ p ；模拟退火算法 a b s t r a c t p a r t i c l es w a i mo p t i m i z a t i o n ( p s o )i sas w a r mi n t e lli g e n ta l g o r i t h m w h i c hi sb a s eo ni m i t a t i n gt h eb i r df l o c k sp r e y i n gb e h a v i o r ，t h r o u g h g r o u pc o o p e r a t i o n a n d c o m p e t i t i o na m o n gi n d i v i d u a l st oa c h i e v e o p t i m i z a t i o np r o b l e m s t h em a i nv i r t u eo fp s oi ss i m p l ei np r i n c i p l e ，f e w i nt u n i n gp a r a m e t e r s ，s p e e d yi nc o n v e r g e n c ea n de a s yi ni m ple m e n t a ti o n s o ，i ta t t r a c t sm o r ea n dm o r er e s e a r c h e r s a t t e n t i o n n o w ，p s oi sw i d e l y u s e df o rt h eo p t i m i z a t i o no ff u n c t i o n s ，n e u r a ln e t w o r kt r a i n i n ga n d m u l t i t a r g e ta n do b t a i n sg o o de f f e c t b u tt h ep s oa l g o r i t h mi sd i f f i c u l t t om e e tt h ea c t u a ln e e d sf o r t h ec h a r a c t e r i s t i c so ft h ep r a c t i c a l e n g i n e e r i n gp r o b l e m sa l w a y si sc o m p l e x i t y ，o n s t r a i n ta n dd i f f i c u l t y e t c ，t h e r ea r em a n yis s u e sn e e dt os t u d ya n di m p r o v e m e n t t h i sp a p e rm a i n l ys t u d i e st h ep s oa l g o r i t h m f i r s te x a m i n et h eb a s i c a l g o r i t h mo fp s o ，a n a l y s i st h et h e o r ya n dt h ea l g o r i t h mf l o w ，s u m m a r i z e d t h ep a r a m e t e r s s e t d i s c u s sav a r i e t yo fi m p r o v e dm e t h o d s e s p e c i a l l y i m p r o v e df r o mt h es p e c i f i cp a r a m e t e r so fp s oa l g o r i t h mt os e ta n da d j u s t t a c t i c s ，p s oa l g o r i t h mt o p o l o g y ，c o m b i n e dw i t ht h r e eo t h e ri n t e l l i g e n t a l g o r i t h m st h r e ea s p e c t s t h e n ，a sas t r a t e g yt oi m p r o v ep a r t i c l es w a r m o p t i m i z a t i o n ，b a s e do ns i m u l a t e da n n e a l i n gp a r t i c l es w a r ma l g o r i t h mt o c o m p a r et h eb a s i cp a r t i c l es w a r ma l g o r i t h mc o m p u t a t i o n a le f f i c i e n c y f o c u s i n go nt h et w ok i n d so fp a r t i c l es w a r ma l g o r i t h mc o n v e r g e n c es p e e d ， c a n e f f e c t i v e l y a v o i d p r e c o c i o u s ，g e t t h e o p t i m a l s o l u t i o n c h a r a c t e r i s t i c ss u c ha sd e g r e e e x p e r i m e n tb yt e s t i n gf u n c t i o nt ov e r i f y t h es u p e r i o r i t yo ft h ea l g o r i t h m f i n a l l y ，b a s e do ns i m u l a t e da n n e a l i n g p a r t i c l es w a r ma l g o r i t h mi sa p p l i e dt oj o bs h o ps c h e d u l i n g ( j s p ) t os o l v e t h ep r o b l e m ，m i n i m i z et h em a x i m u mc o m p l e t i o nt i m ef o rt h ej s p ，i sg i v e n b a s e do nr a n d o mk e y sa n dd i s j u n c t i v eg r a p he n c o d i n ga n dd e c o d i n gm e t h o d ， u s i n gt h ec r i t i c a lp a t hm e t h o ds c h e d u l i n ga n dp a r t i c l e s g e n e r a t e dt o e v a l u a t e ，a tt h es a m et i m eo ft h eu s eo fp 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 mo p e r a t i n g ，d e s i g n i n gac r i t i c a lp a t h b a s e dn e i g h b o r h o o d s t r u c t u r e ，s t r a t e g yb a s e do ns i m u l a t e da n n e a li n gl o c a ls e a r c ha l g o r i t h m t oi m p r o v et h eo v e r a l lp e r f o r m a n c e t h ee x p e r i m e n tt e s t e dp s oa l g o r i t h m b a s e do ns i m u l a t e da n n e a li n gh a v ea c c e s st ot h ev a r i o u se x a m p l e st h e o p t i m a ls o l u t i o n ，t h e r ei sav e r yg o o ds e a r c hq u a l i t y m e a n w h i l e ，t h e a l g o r i t h mi sr u ni n d e p e n d e n t l ym a n yt i m e sa n dt h ew o r s ts o l u t i o no ft h e a v e r a g ei n c o m ei sv e r yc l o s et o ，o re v e nt h es a m e ，s ot h ei n i t i a lc l u s t e r a l g o r i t l mh a sg o o dr o b u s t n e s s a n dt h ei m p r o v e da l g o r i t h mi ss u p e r i o rt o av a r i e t yo fp s oh a v ea c h i e v e dg o o dr e s u l t s k e y w o r d s ：p a r t i c i es w a r mo p t i m i z a t i o na i g o r i a i g o r i t h i n ；j s p ：s i m u i a t e da n n o a ii n ga i g o r i t h m ， _ 第一章绪论 1 1 研究背景及优化算法简介 优化技术就是在众多方案中寻找最优方案，即在满足一定的约束条件下，寻 找一组参数值，使得某些指标达到最大或最小。优化技术以数学为基础，可用于 求解各种工程问题优化解的应用技术。作为一个重要的科学分支，它涉及多种不 同学科，其应用涉及系统控制、人工智能、模式识别、生产调度和计算机工程等 各个领域，一直受到很多学者的关注，并研究出多种解决优化问题的方法。优化 算法是搜索方法，优化算法的研究对于改进算法性能、拓宽算法应用领域、完善 算法体系同样具有重要作用。因此，优化理论及算法的研究是具有理论和应用的 价值重要课题。 优化技术从应用方面归纳，可分为函数优化问题和组合优化问题。函数优化 的对象是一定区间内的连续变量，算法性能多基于基准函数。而组合优化问题的 对象的解空间多为离散状态，往往涉及排序、分类、筛选等问题，是运筹学的一 个重要分支。典型的组合优化问题有旅行商问题、聚类问题、加工调度问题等。 解决最优化问题的优化算法可分为经典优化算法和启发式优化算法。传统经 典算法始于1 9 4 7 年美国数学家d a n t z i g 提出的单纯形法，此算法是求解线性规 划问题的一种方法。随后，k a m a k a 提出了椭球算法( 多项式算法) 和内点发。 对于非线性问题，起初人们试图用线性优化理论去逼近求解非线性问题，但效果 并不理想。后来的非线性理论大多都建立在二次函数的基础上，在此技术上提出 了许多经典的优化算法：共轭梯度法、牛顿法、拟牛顿法等。但对于大型问题， 需要遍历整个搜索空间，无法在多项式时间内完成搜索。如许多工程优化问题， 都是复杂的问题，搜索空间复杂庞大，传统算法远不能满足要求。 后来研究者在大自然运行规律中找到许多解决实际问题的方法，称为启发式 算法，如遗传算法、模拟退火算法、人工神经网络、禁忌搜索等，及演化算法、 蚁群算法、拟人物算法和量子算法等。各种启发式算法都各有特点、互不相同， 当结合两种不同的算法时经常会有出乎意料的效果，所以启发式算法之间又有着 紧密的联系。群体智能算法也属于启发式算法，从2 0 实际9 0 年代初，已有模拟 自然界生物的群行为来构造随机优化算法的思想。典型的方法有d o r i g o 提出的 蚁群算法和e b e r h a r t 与k e n n e d y 提出的微粒群算法。微粒群算法是群体智能优 化算法的代表，不仅代表了一类群体进化计算技术，更代表了一种群体搜索机制。 故本文主要研究微粒群算法。主要介绍p s o 算法及该算法的一系列改进，p s o 算 法与其他智能算法的融合以及基于模拟退火微粒群算法在j s p 问题中的应用。 1 2p s o 算法的现状 微粒群算法始于1 9 9 5 年e b e r h a r t 与k e n n e d y 1 j 提出的基本微粒群算法，其 中基本p s o 的参数是固定的，在对某些函数优化上的精度也较差。后来s h i p 等 人提出了惯性因子c o 的一系列改进算法，大大改进了算法的性能。后来，k e n n e d y 等【3 j 研究微粒群的拓扑结构，分析微粒间的信息流，提出了一系列的拓扑结构。 a n g e l i n e 【4 】将选择算子引入p s o 中，选择每次迭代后的较好的微粒并复制到下一 代，以保证每次迭代的微粒群都具有较好的性能。h i g a s h i 等【5 i 分别提出了自己 的变异p s o ，通过引入变异算子跳出局部极值点的吸引，从而提高算法的全局搜 索能力，得到较高的搜索成功率。b a s k a r 6 1 等提出协同p s o 算法，通过使用多群 微粒分别优化问题的不同维、多群微粒协同优化等办法对基本算法进行改进。 a i - k a z e m i 【7 提出m u l t i - p h a s ep s o 在微粒群中随机选取部分个体向全局最优飞， 而其他个体向反方向飞，以扩大搜索空间。 另外还出现了量子p s o 、模拟退火p s o 、耗散p s o 、自适应p s o 等混合改进 算法，也有采取p s o 与基于梯度的优化方法相结合的办法等。 微粒群算法概念简单，具有很强的发现较优解的能力，但是它有很多薄弱的 地方值得进一步研究。 1 3 本文主要研究内容及组织结构 本文主要研究内容有：微粒群算法的研究与改进、微粒群优化算法的应用、 基于模拟退火微粒群算法的研究以及该算法在j s p 问题中的应用。论文分六章。 第一章介绍了研究背景与国内外p s o 算法的研究现状，并给出本文的主要研 究内容。 第二章主要内容是基本微粒群优化算法，对基本微粒群算法进行了详细介 绍。包括算法的基本理论、算法流程、参数分析以及目前的实际应用情况等。 第三章介绍了微粒群算法的主要改进，主要集中在算法参数的选择与设计、 算法的总体结构、与其他智能算法结合，提高种群多样性等几个方面。 第四章主要内容是模拟退火算法和微粒群算法相结合提出的基于模拟退火 2 微粒群算法。通过4 个测试函数对算法进行了对比实验，结果表明该算法优于标 准微粒群算法。 第五章将基于模拟退火微粒群算法应用于j s p 问题，并用f t 类和l a 类两类 典型j s p 算例测试算法的性能。取得较好的结果。 结论，最后总结全文的工作，对进一步的研究方向进行了展望。 第二章基本微粒群优化算法 2 1 微粒群算法简介 微粒群优化( 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 9 9 5 年 由e b e r h a r t 和k e n n e d y 8 删共同提出的，是一种基于群体智能的随机寻优算法， 它模仿鸟类的觅食行为，将问题的搜索空间比于鸟类的飞行空间，将每只鸟抽象 为一个无质量无体积的微粒，用以表示问题的一个候选解，优化所需要寻找的最 优解则等同于鸟寻找的食物。p s o 算法中的微粒的飞行的行为规则类似于鸟类运 动，从而使整个微粒群的运动表现出与鸟类觅食类似的特性，进而用于求解复杂 的优化问题。 该算法的基本思想是通过群体中个体之间的协作和信息共享来寻找最优解。 p s o 算法与人工生命，特别是进化算法有着极为特殊的关系。相比于进化算法， p s o 算法保留了基于种群的全局搜索策略，采用简单的速度一位移模型，避免了 复杂的遗传操作，同时特有的记忆使算法可动态跟踪当前的搜索情况来调整其搜 索策略。 2 2 基本微粒群算法 微粒群算法中，每个优化问题的解都是搜索空间中的一只鸟，被抽象为没有 质量和体积的微粒，并将其延伸到n 维空间。微粒i 在n 维空间里的位置和速度 都表示为一个矢量。p s o 算法首先在可行解空间和速度空间随机初始化微粒群， 即确定微粒的初始位置和速度。例如，d 维目标搜索空间中第i 个微粒的位置和 速度分别表示为x i 2 k ，l ，薯 2 ， ，d 】和v ：2 【m ，1 m 2 ，v f ，引。在每一次迭代中，评价 各微粒的目标函数，确定t 时刻每个微粒所经过的最佳位置 ( p b e s t ) p i 2 晚| l ，只2 ，砖，d 】以及群体所发现的最佳位置( 驴e s t ) p , ，通过跟踪这两个 最佳位置按照如下公式分别来更新各微粒的速度和位置。 一o + 1 ) = h ，( f ) + q ，i 【b ，一毛，o ) 】+ 乞吃【珞一一，( f ) 】( 2 - i 、 t ，o + 1 ) = 墨( f ) + m ，o + 1 ) ，j = l ，d ( 2 - 2 、 其中，c 1 和c 2 为正的学习因子，或称加速常数，r 1 和r 2 为0 到1 之间均 匀分布的随机数。另外，通过设置微粒的速度区间【v m h ，“j 和位置范围 妯，觚j ，则可以对微粒的移动进行适当的限制。 4 从公式可以看出，微粒速度更新由三部分完成。第一部分反映微粒当前速度 的影响，联系微粒当前的状态，起到了平衡全局和局部搜索的能力。 第二部分反映认知模式的影响，即微粒本身的记忆的影响，使微粒具有全局 搜索能力，避免陷入局部极小。 第三部分反应群体信息的影响，体现微粒之间的信息共享。 微粒群优化算法有两种版本，即全局版本和局部版本，即驴邸的设置不同。 全局版本中，微粒跟踪的两个极值为自身最佳位置和群体最佳位置。在局部版本 中，微粒除跟踪自身最佳位置外，不跟踪群体最佳位置，而是跟踪拓扑邻域中所 有微粒的最佳位置，其速度更新公式如下： k ，j o + 1 ) 2m ( f ) + c 1 巧【b ，一x i d ( t ) + c ：r e p l ，一薯，o ) 】 ( 2 3 ) 其中上 2 峨l ，p ，2 ，鼎，d j 为局部邻域中的最佳位置。 从基本微粒算法模型可以看出，微粒的飞行速度直接影响着算法的全局收敛 性。速度过大，能保证各微粒很快飞行全局最优解的区域，但当逼近最优解时， 由于微粒飞行缺乏有效的控制与约束，很容易飞越最优解，转去其他区域，从而 很难收敛到全局最优。所有，算法的速度缺乏有效的控制时，不具备较强的局部 搜索能力。为有效控制微粒飞行速度，s h i 和e b e r h a r t 在算法模型中引入了惯 性权重系数国，以实现对微粒飞行速度的有效控制与调整。后来该版本成为最基 本的p s o 算法，公式变为： q 。，( f + 1 ) = k ，( t ) + g r l p i ，j 一薯，j o ) 】+ 乞眨【攻，一薯，o ) 】( 2 - 4 、 而( f + 1 ) 2 薯，( f ) + ，j o + 1 ) ，j f = 1 ，d ( 2 5 ) 可以看出，c o 越大，微粒飞行速度越大，微粒将以较大的步长进行全局搜索； 国较小，则微粒步长小，趋向于精细的局部搜索。 2 3 参数分析 p s o 算法的搜索性能取决于其全局探索和局部改良能力的平衡，这很大程度 上依赖于算法的控制参数，包括种群规模、最大速度、最大代数、惯性因子、加 速常数等。 微粒种群数目m ，m 设置较小时，算法收敛速度快，但易陷入局部最优； 当m 设置较大时，p s o 算法优化能力很好，但是收敛速度慢。具体设置应根据具 体问题设定，一般设为1 0 到5 0 之间，对比较复杂的问题，微粒可以取到1 0 0 或 者更多，但是群体过大将导致计算时间大幅增加，而且当群体数目增至一定水平 式，再增加微粒数目也不再有显著的作用。 最大速度酲是一个非常重要的参数，决定搜索的力度。“较大，粒子移 动迅速，微粒的探索能力强，但容易越过优秀的搜索空间，错过最优解，；如果“ 较小，微粒的开发能力强，但容易陷入局部最优，可能会使微粒无法移动足够远 的距离以跳出局部最优，从而也可能找不到解空间的最佳位置。 对于惯性权值，当c o 较大( 1 ) 时，侧重于全局搜索，速度随时间增 大，加速增大至最大速度( 假设速度钳制操作使用) ，则种群就会发散，微粒不 能改变运动方向以转回需要搜索的区域；国较小( 国 4 。 1 2 一c 一c - 4 c i 典型的参数取法有： ( 1 ) a = c 2 = 2 0 5 ，此时c 为4 1 ，收缩因子c p 为0 7 2 9 ，这在形式上就等 于国= o 7 2 9 ，c l = c 2 = 1 4 9 4 4 5 的基本p s o 算法。 ( 2 ) 微粒规模n = 3 0 ，q = 2 8 ，c 2 = 1 3 ，此时c 为4 1 ，收缩因子为0 7 2 9 。 些参数的组合被称为经典参数集。 此模型中c p 的作用类似于参数圪。的作用，用来控制与约束微粒的飞行速 。但实验结果表明，t p 比圪。更有效地控制微粒速度的振动。e b e r h a r t 和s h i 文献中，详细分析比较了权重和压缩因子两者参数对算法性能的影响，并认为 缩因子比惯性权重系数，能更有效地控制与约束微粒的飞行速度，同时增强了 算法的局部搜索能力。 3 1 6 基于模糊系统的惯性因子的动态调整 一个进化算法得以成功的关键点在于能够权衡全局搜索和局部搜索。较大的 c o 倾向于全局搜索，而小的国倾向于局部搜索。通过动态地改变惯性权重，可达 到动态地调整搜索能力。微粒群算法搜索过程是非线性且复杂的过程，一个从全 局搜索到局部搜索的线性变化并不能真实地反映搜索全局最优所需的过程，尤其 是对于动态问题。因此，s h iy 等【2 】提出了一种模糊规则动态调整的方法，通 过对当前最优性能评价( c b p e ) 和当前惯性权重制定相应的隶属度函数和模糊 推理规则，确定惯性权重的增量。c b p e 测量的是算法找到的最好候选解得性 能。由于不同的优化问题有不同的性能评价范围，所以为了让该模糊系统有广泛 的适应性，采用了标准化的c b p e ( n c b p e ) 。假定优化问题为最小化问题，则 n c b p e ：塑丝二咝垫 c b p e 。糕一c b p e 。i i l 其中c b p e 。i 。为估计的( 或实际的) 最小值，而c b p e 。找为非优c b p e ，任 何c b p e 值大于或等于c b p e 。的解都是最小化问题所不能接受的解。实验结果 表明，与c o 线性减小策略相比，模糊自适应策略具有更好的性能。但是该算法需 要建立模糊规则，在复杂系统被优化前，领域知识往往贫乏难以获取，实现比较 复杂。 3 1 7 其他参数的变化 对于学习因子，一般固定为常数，且取值为2 。但在实际应用中，也有一些 其他的取值方式，常见的有同步变化和异步变化。 同步变化的学 - - j 因子指的是将学习因子c i 和g 的取值范围设定为 【m ，气。】，第t 次迭代式的学习因子取值公式为： q = 乞= c m 。一量堂宰t l m “ 异步变化是指，两个学习因子在优化过程中随时间进行不同的变化，这样使 得在优化的初始阶段，微粒具有较大的自我学习能力和较小的社会学习能力，加 强全局搜索能力，在后期，微粒具有较大的社会学习能力和较小的自我学习能力， 有利于收敛到全局最优。学习因子的变化公式为： q ：c l 一譬饥乞：十譬f m a xl m 8 x 其中，q ，柳和巳埘分别代表q 和f ：的初始值，q , r - 和乞，加代表q 和巴的迭代 终值。对于大多数情况下采用如下参数设置效果较好： c 1 ，榭= 2 5 ，c 1 ，向= o 5 ，巳。绷= 0 5 ，c 2 , f l n = 2 5 。 对于微粒群算法的各种改进，各个参数的选取都会影响结果的精度，只有不 断调整参数的组合，才可能取得满意的结果。 3 1 8 其他方面的改进 由于基本微粒群优化算法主要针对连函数进行搜索运算，但许多实际工程问 题都描述为离散的组合优化问题，为此k e n n e d y 和e b e r h a r t 与1 9 9 7 年提出了一 种二迸制离散微粒群优化算法。还有二阶微粒群算法及二阶振荡微粒群算法等多 种改进办法。 3 2p s 0 算法拓扑结构的改进 在提出微粒群优化算法的全局模式和局部模式后，k e n n d y l 2 5 1 等又进一步研 究微粒群的拓扑结构，分析微粒间的信息交流，提出了一系列的拓扑结构，如图 所示，并对其做了实验研究。 ” 。自 簿 奠扁 ，鼢 气! 繁羚。丛 渺 ( 4 ) p s o 算法的 星形结构，如图( 1 ) 所示，其中所有微粒都相互连接，并可以相互交流， 1 6 因此每个微粒都会背全局最优解吸引，并效法这个最优解的移动。使用这种星形 结构的p s o 被称为g b e s t p s o ，它收敛速度比具有其他拓扑结构的p s o 更快，但 更容易陷入局部极值，所以g b e s t p s o 在单峰问题中表现最好。 环形结构，其中每个微粒只与其邻域内的刀，个直接邻居交流。当刀= 2 时， 一个粒子只能与它的两个毗邻的微粒进行交流，如图( 2 ) 所示。每个微粒效法 邻域内最好的微粒，并向它靠近。从图可以看出，微粒的邻域相互重叠，这将有 利于邻域之间的信息交流并最终使微粒收敛到一个唯一的解。由于信息流在整个 社会网络中的传递速率太慢，算法的收敛速度会比较慢，但是相对于星形结构， 微粒可以覆盖更大部分的搜索空间。这样在解决多模问题时，环形结构就可以找 到比星形结构更好的解。使用这种结构的p s o 被称为l b e s t p s o 。 图( 3 ) 是四类社会结构，结构中存在4 个聚类，聚类之间有两条连接，聚 类之内的每个微粒都有5 个邻居。 图( 4 ) 是金字塔结构，是一个三维轮廓。 图( 5 ) 是冯诺依曼结构，所有微粒形成一个网格结构。这种结构被应用 在很多经验学习问题中，并展现了良好的性能。 尽管人们研究和使用了多种拓扑结构，但是没有一种结构能对所有问题都表 现的最好。总体来说，全连接的结构在单模问题上表现最好，较少连接的结构在 多模问题上占优势，但由于微粒连接程度的不同表现也不尽相同。 除静态拓扑结构外，也有研究者提出了动态微粒群拓扑结构【2 6 1 。 3 3 与其他智能算法相结合 除了微粒群算法外，还有遗传算法、蚁群算法、鱼群算法、模拟退火算法以 及神经网络等智能算法，它们均是一种随机搜索的迭代算法，对优化对象的性质 没有要求，但各算法的搜索机制、特点和适用范围存在着差异，每种算法都各有 特点，通过将不同方法的特性进行互补和融合，设计出鲁棒高效的优化方法，这 种混合智能算法成为计算机科学和运筹学领域的一个共同研