（应用数学专业论文）粒子群优化算法的研究与改进.pdf

摘要 优化是人们在科学研究、工程技术和经济管理等诸多领域中经常碰到的问题。 现代优化方法如人工神经网络、禁忌搜索、模拟退火、遗传算法和蚁群算法等在解 决问题时展现出强大潜能，它们可在合理的时间内逼近复杂对象问题的最优解。这 些算法涉及神经科学、人工智能、统计力学、生物进化等概念，很多都是以一定的 自然现象作为基础构造的算法，其中粒子群优化算法( p a r t i c l es w a r mo p t i m i z a t o n ， 简称p s o ) 是1 9 9 5 年k e n n d y 和e b e r h a r t 提出的，源于对鸟群运动行为的研究，是一 种基于群智能优化算法的演化计算技术。由于它的较强的全局搜索能力，较少的参 数设置，简单容易实现，所以从一提出，就引起了许多学者的关注，并得到了迅速 的发展，并被应用到了各个领域，如函数优化、神经网络训练、组合优化和一些工 程应用。 本文首先分析了研究粒子群优化算法的重要意义，接着介绍了与p s o 研究有关 的几个基础问题，包括优化的基本概念和分类方法等。随后，着重介绍了粒子群优 化算法的基本原理、数学描述、算法流程和收敛性分析，从p s o 算法的参数选择与 设汁、拓扑结构、混合算法、改进方法及应用等方面做了较为系统的研究工作。 在工程的实际问题中，我们经常会遇到一些维数比较高的数据需要处理或维数 比较高的函数需要优化，数值测试表明现今的各种优化方法，在处理低维的函数优 化时，计算结果比较理想，而在处理高维的问题时，结果不尽人意。粒子群算法的 优化性能比较明显，特别对维数不高的优化问题，效果更为显著，但粒子群算法易 陷入局部极值也是实际存在的。为此本文提出了一种新的改进粒子群优化算法 ( m a p s o ) ，该算法在运行过程中根据群体适应度方差与理想方差的比较来动态改变 确定l j ，j 最佳粒子的惯性权值，并且根据群体的适应度方差及平均聚集距离判断算 法是否陷入局部寻优，通过对群体中的部分粒子进行变异运算，摆脱局部搜索陷阱增 强全局搜索的能力。该算法增强了粒子群优化算法跳出局部最优解的能力，能够有效 避免早熟收敛问题，又保持了前期搜索速度快的特性，同时又不引入其它算法概念， 算法的理解复杂度、实现复杂度得到有效控制。通过对5 个标准函数的测试，表明 这种改进的p s o 算法的全局搜索能力和搜索成功率有较大提高。并将该方法应用于 对s 0 2 催化氧化反应动力学模型的非线性参数估计，取得了良好效果。 关键词；粒子群优化，进化算法，收敛性分析，惯性权重，变异算子 a b s t r a c t m a n ys c i e n t i f i c ，e n g i n e e r i n ga n de c o n o m i cp r o b l e m sn e e dt h eo p t i m i z a t i o no fas e to fp a r a m e t e r s w i t ht h ea i mo fm i n i m i z i n go rm a x i m i z i n gt h eo b j e c t i v ef u n c t i o n s m o d e mo p t i m i z a t i o nm e t h o d ss u c h a sa r t i f i c i a ln e u r a ln e t w o r k , t a b us e a r c h , g e n e t i ca l g o r i t h ma n da n tc o l o n ya l g o r i t h me t c ，h a v es h o w n c a p a b i l i t i e so ff i n d i n go p t i m a ls o l u t i o n st om a n yr e a l w o r l dc o m p l e xp r o b l e m sw i t h i nar e a s o n a b l e a m o u n to ft i m e t h e s em e t h o d sh a v ef o r g e dc l o s et i e sw i t hn e u r a ls c i e n c e ，a r t i f i c i a li n t e l l i g e n c e ， s t a t i s t i c a lm e c h a n i c s ，a n db i o l o g ye v o l u t i o ne t e , s o m eo ft h e ma 恐c a l l e di n t e l l i g e n to p t i m i z a t i o n a l g o r i t h m s 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 ) a l g o r i t h mi sa ne v o l u t i o n a r yc o m p u t a t i o nt e c h n i q u e b a s e d0 1 1s w a r mi n t e l l i g e n c eo p t i m i z a t i o na l g o r i t h m ，w h i c hw a sd e v e l o p e db yk e n n e d ya n de b e r h a r ti n 19 9 5a n di n s p i r e db yt h es o c i a lb e h a v i o ro fb i r d sb l o c k i n g d u et oi t ss t r o n ga b i l i t yt og l o b a ls e a r c h , t e s sp a r a m e t e r sa n ds i m p l i c i t y , i th a sg a i n e dm u c ha t t e n t i o ns i n c ei tw a sp r o p o s e d a n di ti sd e v e l o p e d r a p i d l ya n di su s e di nm a n yf i e l d ss u c ha sf u n c t i o no p t i m i z a t i o n ，n e u r a ln e t w o r kt r a i n i n g , c o m b i n a t i o n o p t i m i z a t i o na n ds o m ep r o j e c ta p p l i c a t i o n t h i st h e s i sf i r s ta n a l y z e st h ei m p o r t a n c eo 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 ，a n dt h e n i n t r o d u c e ss e v e r a lr e l a t e di s s u e so fp s o ，i n c l u d i n gt h eb a s i cc o n c e p to fo p t i m i z a t i o n , t a x o n o m i c a p p r o a c ha n de t c a f t e r w a r d ，w ee m p h a t i c a l l ye x p l a i nt h eb a s i cp r i n c i p l e s ，m a t h e m a t i c sd e s c r i p t i o n ，t h e a l g o r i t h mf l o wa n dt h ec o n v e r g e n c ea n a l y s i so fp s o ；a n ds y s t e m a t i c a l l ys t u d yt h ei m p r o v e m e n to f p s ob ym o d i f y i n gt h ec h o i c e sa n dt h ed e s i g no ft h ep a r a m e t e r s ，t h et o p o l o g i c a ls t r u c t u r e ，a n dm i x e d a l g o r i t h m s f i n a l l yw ea p p l yp s 0t oap r a c t i c a lp r o b l e m i nm a n yp r a c t i c a le n g i n e e r i n gp r o b l e m s ，w eo f t e nn e e dt op r o c e s ss o m eh i g h e rd i m e n s i o n a ld a t a o rt oo p t i m i z eh i g h e rd i m e n s i o n a lf u n c t i o n s n u m e r i c a lr e s u l t ss h o wt h a tt h ee x i s t i n gm e t h o d sd ow e l l f o rl o w e rd i m e l a s i o n a lc a s e s ，b u tn o tf o rh i g h e rd i m e n s i o n a lc a s e s a l t h o u g ht h ea d v a n t a g e so f o p t i m i z a t i o np e r f o r m a n c eo fp s o 矾q u i t eo b v i o u s ，e s p e c i a l l yf o rs o m eo p t i m i z a t i o np r o b l e mw i t h d i m e n s i o nn o ts oh i g h ，i tm a ya l s oe n da tt h el o c a lm i n i m a t oc o n q u e rs u c hp r o b l e m s , w ep r o p o s ea n e wm o d i f i e dp s om e t h o d ( m a p s o ) i nt h i st h e s i s t h i sm e t h o dd y n a m i c a l l yc h a n g e st h ei n e r t i a w e i g h tf o rt h eb e s tp a r t i c l ed e t e c t i n g ；d e t e r m i n e sw h e t h e rt h ea l g o r i t h mf a l i si n t oal o c a lm i n i m u m n e i g h b o r h o o db yt h ea d a p t i v ev a r i a t i o na n dt h em e a l ld i s t a n c eo ft h es w a r m ；e n h a n c e st h ea b i l i t yt o j u m po u tt h el o c a lm i n i m u ms e a r c ha n dd ot h eg l o b a lm i n i m u ms e a r c hb ya d o p t i n gm u t a t i o no p e r a t i o n o ns o m ep a r t i c l e s i tc a ne f f e c t i v e l yp r e v e n tp r e m a t u r ec o n v e r g e n c ea n dk e e pt h ec h a r a c t e r i s t i co ff i r s t s t a g ef a s tc o n v e r g e n c es p e e d t h eu n d e r s t a n d i n gc o m p l e x i t ya n di m p l e m e n t a t i o nc o m p l e x i t ya r ea l s o e f f e c t i v e l yc o n t r o l l e db yt h em e t h o dw i t h o u ti n t r o d u c i n go t h e ra l g o r i t h m s t h ea l g o r i t h mi st e s t e do n f i v es t a n d a r df u n c t i o n s o u rn u m e r i c a lr e s u l t ss h o wt h a tt h em o d i f i e dp s oa l g o r i t h mc a ni m p r o v et h e g l o b a ls e a r c ha b i l i t ya n dg r e a t l ye n h a n c et h es u c c e s s f u ls e a r c hr a t e t h ea l g o r i t h mi sa p p l i e dt ot h e e s t i m a t i o no fn o n l i n e a rp a r a m e t e r sf o r t h ed y n a m i cm o d e lo fl o wt e m p e ；r a t u r es 0 2o x i d a t i o nw i t h c s - r b vs u l f u r i ca c i dc a t a l y s t ，a n dp r o d u c e sq u i t eg o o dr e s u l t s k e yw 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 ，e v o l u t i o n a r ya l g o r i t h m ，c o n v e r g e n c ea n a l y s i s , i n e r t i a w e i g h t ，m u t a t i o no p e r a t o r i i 浙江师范大学学位论文诚信承诺书 我承诺自觉遵守浙江师范大学研究生学术道德规范管理条 例。我的学位论文中凡引用他人已经发表或未发表的成果、数据、 观点等，均已明确注明并详细列出有关文献的名称、作者、年份、 刊物名称和出版文献的出版机构、出版地和版次等内容。论文中 未注明的内容为本人的研究成果。 如有违反，本人接受处罚并承担一切责任。 承诺人( 研究生) ：历和 指导教厩烧嘁 浙江师范大学学位论文独创性声明 本人声明所呈交的学位论文是我个人在导师指导下进行的研究工作及取得 的研究成果。论文中除了特别加以标注和致谢的地方外，不包含其他入或其他机 构已经发表或撰写过的研究成果。其他同志对本研究的启发和所做的贡献均已在 论文中作了明确的声明并表示了谢意。本人完全意识到本声明的法律结果由本人 承担。 作者签名：矿万彳u 日期：c 年，月矽日 学位论文使用授权声明 本人完全了解浙江师范大学有关保留、使用学位论文的规定，即：学校有权 保留并向国家有关机关或机构送交论文的复印件和电子文档，允许论文被查阅和 借阅，可以采用影印、缩印或扫描等手段保存、汇编学位论文。同意浙江师范大 学町以用不同方式在不同媒体上发表、传播沦文的全部或部分内容。同时授权中 国科学技术信息研究所将本学位论文收录到中国学位论文全文数据库，并通 过网络向社会公众提供信息服务，同时本人保留在其他媒体发表论文的权利。 保密的学位论文在解密后遵守此协议。 作者签名：何删新签名：恻日期：铲厂月朋 1 绪论 1 ，1 研究背景 优化是个古老的课题。长期以来，人们对优化问题进行了探讨和研究。早在1 7 世纪，英国n e w t o n 和德国l e i b n i t z 微积分的发明使得优化的发展成为可能。而 b e m o u l l i 、e u l e r 、l a g r a n g e 和w e i e r s t r a s s 则对微积分进行了完善。后来针对约束问 题又提出了l a g r a n g e 乘子，而c a u c h y 则首次采用最速梯度下降法解决无约束问题， 可参看 1 ，2 ，人们关于优化问题的研究工作，随着历史的发展不断深入。但是，任 何科学的进步都受到历史条件的限制，直到二十世纪中页，由于高速数字计算机日 益广泛应用，使得优化技术不仅成为迫切需要，而且有了求解的有力工具。因此， 优化理论和算法迅速发展起来，形成- f - j 新的学科。至今已出现线性规划、整数规 划、非线性规划、几何规划、动态规划、随机规划、网络流等多分支。这些优化技 术在诸多工程领域得到了迅速推广和应用，如系统控制、人工智能、生产调度等。 但是随着计算机科学和技术的发展，从根本上改变了人类的生产和生活。同时， 随着人类生存空间的扩大，以及认识世界和改造世界范围的拓宽，现实中碰到的许 多科学、工程和经济问题呈复杂化、多极化、非线性、强约束、建模困难等特点。 这就使人们对科学技术提出了新的和更高的要求，其中对高效的优化技术和智能计 算的要求尤为追切。 上述的这些经典的优化算法通常采用局部搜索方法，这些局部搜索方法要么是 与特定问题相关，要么是局部搜索方法的变型，但它们有一个共同的特点就是通过 迭代来提高问题域中唯一的候选解的近似程度。这就决定了经典算法只能适用于求 解小规模且定义非常明确的问题。解决实际工程问题，这些算法要么是解的精度， 要么是执行时间，总是不能令人十分满意。寻求一种适合于大规模并且具有智能特 征的算法已经成为人们研究的目标和方向。 。 二十世纪八十年代以来，一些新颖的优化算法，如人工神经网络( 砧州) 瞄嘲、混 沌1 、遗传算法( g a ) 吣坦1 、进化规划( e p ) 叫引、模拟退火( s a ) m 埔1 、禁忌搜索( t s ) n 蝴1 等，通过模拟或揭示某些现象和过程得到发展，其思想和内容涉及数学、物理学、 生物进化、人工智能、神经科学和统计力学等方面，为解决复杂问题提供了新的思 路和手段。在优化领域，由于这些算法构造的直观性与自然机理，因而通常被称为 智能优化算法( i n t e l l i g e n to p t i m i z a t i o na l g o r i t h m s ) ，或称现代启发式算法 ( m e t a - h e u r i s t i ca l g o r i t h m s ) 。 本文研究的粒子群优化算法( 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 ) 是k e n n e d y e b e r h a r t 源于群智能和人类认知的学习过程而发展的另外一种智能优化算法2 6 。 。p s o 与遗传算法有些相似之处，首先，它们都是基于群体的优化技术，亦即搜索轨 道有多条，显示出良好的并行性，其次，无需梯度信息，只需利用目标的取值信息、， 具有很强的通用性，但是，p s o 比g a 更简单、操作更方便。因而，p s o 算法从诞 生起，就引起了国内外学者的广泛关注，并掀起了该方向的研究热潮，且在诸多领 域得到了成功应用，但是，p s o 的发展历史尚短，在理论基础与应用推广上都还存 在一些问题，有待解决。 首先，对任何一个算法，如果不从理论上对其研究，那对其行为将无法彻底剖 析。仅仅从实验数据对粒子群优化算法进行研究，终将无法了解其内部机理。因此， 对粒子群优化算法收敛模型的建立和收敛性分析是十分有益的，也为以后的进一步 研究与新算法的提出都将提供很好的明示。 第二，工程上存在的很多复杂优化问题急需解决，由于粒子群优化算法在求解 复杂优化问题存在易陷局部极值的事实，对粒子群优化算法进行适当改进，以能更 好更准确地求解工程的优化问题是一个有现实意义的课题。 第三，粒子群优化算法刚兴起不久，所以对其在实际中的具体应用还有很多需 要解决的问题。这是由于每个算法都具有自身的特点，在具体应用中针对具体问题 都需进行适当改进，才能用于实际问题的求解，同时对同一个优化问题、使用同一 个算法，若调整策略不同，最后得到的效果也是不一样的。因此，对粒子群优化算 法具体实例应用研究是一个值得的、有意义的。 针对以上问题，本文展丌了细致的研究，对化学工程优化问题，提出了改进策 略，以适应问题的求解，提高算法的运行速度与最终结果的精确性。 1 2 国内外研究现状和进展 p s o 是计算智能领域除蚁群优化算法外的另外一种群体智能算法，它同遗传算 法类似，通过个体| - 白j 的协作和竞争实现全局搜索，系统初始化为一组随机解，称之 为粒子，通过粒子在搜索空间的飞行完成寻优，在数学公式中即为迭代，它没有遗 传算法的交叉以及变异算子，而是粒子在解空间追随最优的粒子进行搜索。 自p s o 提出以来，由于它的计算快速性和算法本身的易实现性，引起了国际上 相关领域众多学者的关注和研究，其研究大致可以分为：算法本身、参数选取、拓 扑结构、与其他进化技术的融合及应用。下面就这三个方面的研究情况做简单的介 绍。 起初，p s o 是为实值问题而设计。后来，算法逐渐扩展到二进制和离散问题，为 p s o 算法与遗传算法的性能比较提供了一个有用的方式，该方法可用于神经网络的 结构优化。 为了提高收敛性能，在原始p s o 算法的速度项中引入了新参数惯性权重( i n e r t i a w e i g h t ) ，惯性权重的引入是为了平衡全局与局部搜索能力，惯性权重较大，全局搜 索能力强，局部搜索能力弱，反之，则局部搜索能力增强，而全局搜索能力减弱。 动态惯性权重能够获得比固定值更为好的寻优结果。动态惯性权重可以在p s o 搜索 过程中线性变化，亦可根据p s o 性能的某个测度而动态改变，比如模糊规则系统。 随后，另一个参数称之为收缩因子( c o n t r a c t i o nf a c t o r ) 的系数被引入，目的是希望 p s o 可以收敛。从数学上分析，这两个参数是等价的。 2 为了提高算法收敛的全局性，保证微粒的多样性是其关键，p s o 算法有全局版席 p s o 和局部版本p s o ，这两种版本的差别在于粒子的邻域不同，即与各粒子直接遥 接的粒子数不同，局部p s o 的粒子，邻域仅为其两边有限的几个粒子，而全局p s ( 的邻域则为该群体所有粒子，如此一来，全局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 算法中引入了空间邻域的概念，将处于同一个空间领域的微粒构威 一个子微粒群分别进行进化，并随着进化动态地改变选择阈值以保证群体的多样性； k e n n e d y 引入邻域拓扑的概念来调整邻域的动态选择，同时引入社会信念将空间邻域 与邻域拓扑中的环拓扑相结合以增加邻域间的信息交流，提高群体的多样性。 p s o 另一个研究的趋势是将其与其他进化计算技术相结合。有些研究者向p s o 当中引入了一些算子，包括选择、交叉和变异，通过选择算子，最好性能的粒子将 被直接复制到下一代，从而保持最优性能的粒子，同进化算法类似，通过交叉算子， 成对的粒子将交换相互的信息，以便有向新的搜索空间飞翔的能力，变异算子主要 目的是为了增强p s o 跳出局部极小的能力。混合p s o 是改进研究的热点，其发展非 常迅速。除了将进化算法中的选择、交叉以及变异算子引入p s o 外，还有很多与其 他经典优化技术相结合的混合p s o 算法，例如梯度下降、k 均值聚类算法、免疫算 法等。 p s o 原理上十分简单，所需参数也较少，并且易于实现，已经应用到很多的领 域，通常，其他进化算法能够应用较好的领域，p s o 算法亦能成功应用，比如p s o 已经被成功地用到进化神经网络、跟踪动态系统、解决多目标优化和约束优化问题， 此外，p s o 还应用到很多的工业领域，比如，p s o 已被成功地应用到反应能源和电 压的控制，以及成分混合优化等。 1 3 本文的主要成果 在本论文中，对p s o 算法进行了较为深入的研究。本文的主要研究成果可归纳 如下： ( 1 ) 本文首先介绍了常见的群集智能算法蚁群算法、粒子群优化算法和进化 算法遗传算法，着重介绍了粒子群优化算法的基本原理、数学描述、算法流程 承j 收敛性分析，然后从算法的参数选择与设计、拓扑结构以及混合算法等方面对粒 子群优化算法的研究进展进行全面综述。 ( 2 ) 由于粒子群优化算法求解高维优化问题存在易陷局部极值的困境，本文提出 了一种新的改进粒子群优化算法( m a p s o ) ，该算法在运行过程中根据群体适应度 方差与理想方差的比较来动态改变确定当前最佳粒子的惯性权值，使得算法在迭代 的早期快速进入局部搜索，并且根据群体的适应度方差和平均聚集距离来判断算法 在迭代的后期是否陷入局部最优点陷阱，对群体中的部分粒子采用新构造的变异运 算作用，从而摆脱局部搜索的束缚，以实现全局搜索的性能。通过对基准函数的测 试，表明这种改进的p s o 算法的全局搜索能力和搜索成功率有较大提高。通过对s 0 2 催化氧化反应动力学模型的非线性参数估计的实际应用取得了良好的效果。 1 4 论文的组织 本文共六章。第二章主要对研究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 算法求解高维优化问题存在易陷局部极值的困境，本文提 出了一种新的粒子群优化算法( m a p s o ) ，该算法在运行过程中根据群体适应度方 差与理想方差的比较来动态改变确定当前最佳粒子的惯性权值，并且根据群体的适 应度方差及半均聚集距离判断算法是否陷入局部寻优通过对群体中的部分粒子进行 变异运算，通过对基准函数的测试证明算法的有效性，并应用到s 0 2 催化氧化反应动 力学模型的非线性参数估计。 4 2 研究基础 2 1 引言 借助于生物觅食运动的启迪，k e n n e d y 和e b e r h a r t 于1 9 9 5 年提出了粒子群优化 ( p s o ) 算法。本章首先讨论了与p s o 相关的优化概念和技术。接着介绍了与p s o 类 似的其它基于种群的仿生算法，包括蚁群算法、遗传算法等，同时还比较了p s o 和 g a 的异同。上述这些内容将为后面算法理论和算法改进的研究提供必不可少的基础。 2 2 优化 优化是科学研究、工程技术和经济管理等领域的重要研究工具，它所研究的问 题是讨论在众多的方案中寻找最优方案。例如，工程设计中怎样选择设计参数，使 设计方案既满足设计要求又能降低成本；资源分配中，怎样分配有限资源，使分配 方案既能满足各方面的基本要求，又能获得好的经济效益；在人类活动的各个领域 中，诸如此类，不胜枚举。优化这一技术，正是为这些问题的解决，提供理论基础 和求解方法，它是- r l 应用广泛、实用性很强的科学。 优化包括寻找最小值和最大值两种情况【2 7 】。寻找函数f n 最大值等价于一f 最小 值寻优，所以两种情况可归结到一起研究。本文主要研究无约束最小化问题，可定 义为给定： 厂：一足 寻找：f ( x 幸) 啦) v x e r 疗 ( 2 - 1 ) 其中x 为盯维定义空间中的向量，或视为该空间的点，x * n 搜寻空间的全局最优 点，厂是目标函数。 在上述无约束优化问题中，目标函数种类繁多，有的是线性的，有的是非线性 的，有的是连续的，有的是离散的，有的是单峰值的，有的是多峰值的，随着研究 的深入，人们逐渐认识到在很多复杂情况下要想完全精确地求出其最优解是不可能 的，凶l f i j 求出其近似最优解或满意解是人们的主要着眼点之一。 在一类特殊优化问题中，目标函数由若干个函数的平方和构成。一般可表示如 下： 给定： ，：一r 肌，f 1 0 ) 邻域 b = 驯l i x - - x 占 ( 2 3 ) 使得对每个x s nb ，似) 如木) 成立，则称矿为极小化问题m i n f ( x ) ，工s nb 的局 部最优解。 + 大多数优化算法都需要一个初始点9 0 s ，局部优化算法应保证在邻域空间夙 如果g o b 找到最小点秽。 2 2 2 全局优化 定义2 1 ：设 ) 为目标函数，s 为可行域，x e s ，若对每一个工s ，厂刁似宰) 成立，则称x 宰为极小化问题r a i nm ，x s 的最优解( 全局最优解) 。 ， 对无约束优化问题，通常取s = f 。本文全局优化都指搜索x 木的过程。全局最小 值厂0 术) ，全局最小点指舛。同样，全局最优化算法也要选择初始点zo s 。 2 2 3n f l 定理 在最优化理论研究领域中，最值得一提的是w o l p e r t 和m a c r e a d y 2 8 2 9 1 于1 9 9 7 年 在( i e e et r a n s a c t i o no ne v o l u t i o n a r yc o m p u t a t i o n ) 上发表了题为“n of r e el u n c h t h e o r e m sf o ro p t i m i z a t i o n ”的论文，提出并严格论证了所谓的无免费午餐定理( n o f r e el u n c ht h e o r e m s ) ，简称n f l 定理。 n f l 定理的简单表述为：对于所有可能的问题，任意给定两个算法a 、a ，如 果a 在某些问题上表现比a 好( 差) ，那么a 在其他问题上的表现就一定比4 差( 好) ， 也就是说，任意两个算法a 、a 对所有问题的平均表现度量是完全一样的。该定理 的结论是，由于对所有可能函数的相互补偿，最优化算法的性能是等价的。该定理 只是定义在有限的搜索空间，对无限搜索空间结论是否成立尚不清楚。在计算机上 实现的搜索算法都只能在有限的搜索空间实施，所以该定理对现存的所有算法都可 直接使用。 n f l 定理的主要价值在于它对研究与应用优化算法时的观念性启示作用。虽然 n f l 定理是在许多假设条件下得出的，但它仍然在很大程度上反映出了优化算法的本 质。当我们所面对的是一个大的而且形式多样的适应值函数类时，就必须考虑算法 问所表现出的n f l 效应，即若算法a 在某些函数上的表现超过算法a ，则在这类的 其他适应值函数上，算法a 的表现就比a 要好。因此，对于整个函数类，不存在万 能的最佳算法，所有算法在整个函数类上的平均表现度量是一样的。 2 3 进化计算 自从生物进化的理论被人们接受之后，关于进化的研究得到了很大的发展，尤 其是近：3 0 年通过模拟自然进化的搜索过程可以产生非常健壮的计算机算法，虽然这 些模型还只是自然界生物体进化的粗糙简化。进化算法就是基于这种思想发展起来 6 的一类随机搜索技术，他们是模拟由个体组成的群体的集体学习过程，其中每个个 体表示给定问题搜索空间中的一个点。进化算法从任一初始的群体出发，通过随机 选择、变异和重组过程，使群体进化到搜索空间中越来越好的区域。选择过程使群 体中适应性好的个体比适应性差的个体有更多的复制机会，重组算子将父辈信息结 合在一起并将他们传到子代个体，变异在群体中引入了新的变种。 目前研究的进化算法主要有三种典型的算法：遗传算法( g e n e t i ca l g o r i t h m s ，简汜 为g a ) 、进化规则( e e v o l u t i o n a r yp r o g r a m m i n g ，简记为e p ) 和进化策略( e v o l u t i o n a r t s t r a t e g i e s ，简记为e s ) ，我们就简单介绍遗传算法。 遗传算法可以说是最广为人知的进化算法。早在2 0 世纪6 0 年代，美国m i c h i g a n 大学的j h o l l a n d 教授在从事如何建立能学习的机器的研究中注意到，学习不仅可 以通过单个的生物体的适应而且通过一个种群的许多代进化适应也能发生。受达尔 文进化适者生存的启发，他逐渐认识到在机器学习的研究中，为获得一个好的学习 算法仅靠单个策略建立和改进是不够的，还要依赖于一个包含许多候选策略的群体 的繁殖，考虑到其研究思想起源于遗传进化，h o l l a n d 就将这个研究领域取名为遗传 算法，d ej o n g 首先将遗传算法应用于函数优化，为这一应用技术奠定了基础。目前， 人们对原来的遗传算法，或称为标准遗传算法进行了大量的改进，使遗传算法应用 于更广泛的领域。 构成基本遗传算法的要素主要有：染色体编码、个体适应度评价、遗传算子以 及遗传参数设置等等。 ( 1 ) 染色体编码方法在对一个问题采用遗传算法进行求解之前，必须对问题的 解窄| 1 白j 进行编码，以便能够由遗传算法操作，常见的编码方法是二进制编码，使用 固定长度的二进制符号串来表示群体中的个体，求解结束后再通过解码变换成实变 量，在编码和解码的过程中，参变量的精度不可避免会受到影响，因此，有人提出 了基于实数编码的遗传算法，其基本原理与二进制编码相同，只是实数编码的染色 体是由各个实参变量构成的向量，初始群体中的各个个体的基因可用均匀分布的随 机数来构成。 ( 2 ) 适应度函数在遗传算法中，遗传操作主要通过适应度函数的导向来实现 的。它是用来评估一个染色体相对于整个群体的优劣的相对值的大小。 ( 3 ) 遗传算子 基本遗传算法通常使用下述三种遗传算子： 选择算子：按照某种策略从父代中挑选个体进入中间代； 交叉算子：随机地从中间群体中取得两个个体，并按照某种交叉策略使两个 个体互相交换部分染色体码串，从而形成两个新的个体； 变异算子：通常按照一定的概率，改变染色体中的某些基因的值。 ( 4 ) 遗传算法的运行参数有以下四个运行参数需要提前设定：群体大小，即 群体中所含个体数量；终止迭代代数( 乃；交叉概率p 。) ；变异概率p 。) 。这四个 7 参数对遗传算法的求解结果和求解效率都有很大的影响。因此，要合理设定这些参 数，才能获得较好的效果。 2 4 群智能 群居昆虫以集体的力量，进行觅食、御敌、筑巢的能力。这种由于个体之间以 及个体与环境之间交互而使群体所表现出来的智能，就称之为群智能，如蜜蜂采蜜、 筑巢、蚂蚁觅食等，从群居昆虫互相合作进行工作中，得到启迪，研究其中的原理， 以此原理来设计新的求解问题的算法。目前主要有两种群智能算法：蚁群算法和粒 子群优化算法，下面介绍人们较早研究的蚁群算法 3 0 - 3 射。 2 4 1 蚁群算法( a c o ) 根据蚂蚁的集群觅食活动的规律，建立了一个利用群体智能进行优化搜索的模 型，蚁群算法对搜索空间的“了解”是从观察蚁群觅食活动从中启发而建立的机制， 主要包括三个方面： ( 1 ) 蚂蚁的记忆。一只蚂蚁搜索过的路径在下次搜索时就不会被选择，由此在蚁 群算法中建立t a b u ( 禁忌) 列表来进行模拟： ( 2 ) 蚂蚁利用信息素进行相互通信。蚂蚁在所选择的路径上会释放一种叫做信息 素的物质，当同伴进行路径选择时，会根据路径上的信息素进行选择，这样信息素 就成为蚂蚁之间进行通讯的媒介。 ( 3 ) 蚂蚁的集群活动。通过一只蚂蚁的运动很难到达食物源，但整个蚁群进行搜 索就完全不同。当某些路径上通过的蚂蚁越来越多时，在路径上留下的信息素数量 也越来越多，导致信息素强度增大，蚂蚁选择该路径的概率随之增加，从而进一步 增加该路径的信息素强度，而某些路径上通过的蚂蚁较少时，路径上的信息素就会 随时白j 的推移而蒸发。因此，模拟这种现象从而利用群体智能建立的路径选择机制， 使蚁群算法的搜索向最优解推进。 可以建立基本的蚁群算法模型，算法由下面三个公式组成 一口一声 尸：= 鸟( 2 4 ) 9 vr 口 f 、 厶u ，q 雁 气仰+ 1 ) = p 事( 芥) + 砖 ( 2 - 5 ) k - i 厶f ：；毒l ( 2 6 ) 乞，i 式( 2 4 ) 、式( 2 5 ) 和式( 2 6 ) 中的参数意义为：m 为蚂蚁个数；嚣为迭代次数；f 为蚂 蚁所在位置；为蚂蚁可以到达的位置：a 为蚂蚁可以到达位置的集合。为启发性 信息，这罩为由i 到的路径的能见度( v i s i b i l i t y ) ，即l 肘i i ：f 为目标函数，这旱为 欧式距离；f i i 为由f 到的路径的信息素强度( i n t e n s i t y ) ：r ：为蚂蚁k 由f 到的路 8 径上留下的单位长度轨迹信息素数量：口为路径权：为启发性信息的权；p 为路 径上信息素数量的蒸发系数；q 为信息素质量系数；p ：为蚂蚁k 从位置f 移动到位 置，的转移概率。 蚁群算法所利用的搜索机制呈现出一种自催化或正反馈的特征，因此可将蚁群 算法模型理解成增强型学习系统，这种选择不满足马尔可夫性：某时刻采取的行动 只与上一时刻的行动相关，与前面所有时刻采取的行动无关，这显而易见，因为蚂 蚁每次选择路径后，就将该路径存到t a b u 列表中，选择下一条路径时，只能在t a b u 列表中不包括的路径中进行选择，而b a t u 列表正是蚂蚁前面所有时刻采取的行动形 成的。因此，蚁群算法模型就不是一个马尔可夫决策过程，也不能理解为动态规划 ( d y n a m i cp r o g r a m ) 和蒙特卡罗( m o n t e - c a r l o ) 这样的增强学习算法，而应理解为一 种q 学习。信息素可理解为q 学习中的回报。 2 4 2 粒子群优化算法 p s o 是计算智能领域除蚁群算法外的另外一种群智能算法，它同遗传算法类似， 通过个体闯的协作和竞争实现全局搜索，系统初始化为一组随机解，称之为粒子。 通过粒子在搜索空间的飞行完成寻优，在数学公式中即为迭代，它没有遗传算法的 交叉以及变异算子，而是粒子在解空间追随最优的粒子进行搜索。 粒子群优化算法的研究大致可分为五个部分。川：算法本身、拓扑结构、参数选 取、与其他进化技术的融合及应用。 p s o 速度的改变由三部分组成：社会项、认知项和动量项，三部分如何平衡， 决定了p s o 算法的性能，原始p s o 中增加了的第一个新参数为惯性权( i n e r t i a w e i g h t ) 。惯性权的引入是为了平衡全局与局部搜索能力，惯性权值较大，全局搜索 能力强，局部搜索能力弱，反之，则局部搜索能力增强，而全局搜索能力减弱。动 态惯性权值能够获得比固定值更为好的寻优结果。动念惯性权值可以在p s o 搜索过 程中线性变化，亦可根据p s o 性能的某个测度而动态改变，比如模糊规则系统。随 后，另一个参数称之为收缩因子( c o n t r a c t i o nf a c t o r ) 的系数被引入，目的是希望p s o 可以收敛，从数学上分析，这两个参数是等价的。 可见，粒子群优化算法也是基于个体的协作与竞争来完成复杂搜索空间中最优 解的搜索，是一种基于群体智能方法的进化计算技术。p s o 同遗传算法类似，是一 种基于群体的优化工具。但p s o 并没有遗传算法用的交叉、变异等操作，而是粒子 在解空间追随最优的粒子进行搜索，因此具有容易实现并且没有许多参数需要调整 的优点。p s o 的提出至今不到十年，但是它已经得到了广泛关注。在基本p s o 算法 的基础上，已经出现了各种有意义的改进p s o 算法以及广阔的应用领域。 2 5 算法比较 p s o 与g a 存在很多共同点又有很多区别，为了更清楚地认识p s o 和g a ，下 面对两者做个简单比较。 9 p s o 和g a 的相同点： ( 1 ) 都属仿生算法。p s o 主要模拟鸟类觅食、人类认知等社会行为而提出；g a 主要借用生物进化中“适者生存 的规律。 ( 2 ) 都属全局优化方法。在解空间中都随机产生初始种群，因而算法在全局的 解空间中进行搜索，且将搜索重点集中在性能高的部分。 ( 3 ) 都属随机搜索算法。p s o 中个体认知项和社会认知项前都加有随机数；而 g a 的遗传操作均属随机操作。 ( 4 ) 隐含并行性。搜索过程是从问题解的一个集合开始的，而不是从单个个体 开始，具有隐含并行搜索特性，从而减小了陷入局部极小的可能性。并且由于这种 并行性，易在并行计算机上实现，以提高算法性能和效率。 ( 5 ) 不受函数约束条件的限制，如连续性、可导性等。 ( 6 ) 对高维复杂问题，往往会遇到早熟收敛和收敛性能差的缺点，都无法保证 收敛到最优点。 p s o 和g a 不同点： ( 1 ) p s o 有记忆，好的解的知识粒子都保存，而g a ，以前的知识