（应用数学专业论文）基于空间收缩的粒子群优化算法及其在投资预测中的应用.pdf

哈尔滨工程大学硕士学位论文 摘要 优化技术是一种以数学为基础，用于求解各种工程问题优化解的应用技 术。多年来，由于其广泛的应用而备受瞩目，并且发展迅速。随着应用领域 的拓展，最优化问题的时空复杂性使其求解非常困难，传统的优化算法已很 难满足问题需要。近年来，智能优化算法的诞生给最优化技术提供了新的思 路和手段，并在科学研究、经济及工程技术问题中得到广泛应用和发展。粒 子群优化算法是一种新的随机搜索群智能优化算法。作为一种智能算法，它 在复杂优化问题求解中显现了巨大潜力，成为近年来一个研究的热点。 本文简要介绍了与p s o 算法相关的优化基础知识，系统论述了p s o 算 法的基本原理、实现流程以及算法产生以来的主要研究成果，并从算法改进 和应用方面对p s o 算法进行了深入的研究。本文的主要研究成果可归纳为： 1 根据对算法的经验分析，本文指出了算法容易出现早熟的原因，并把 空间收缩的机制引入粒子群优化算法，根据空间收缩的不同方式，提出了两 种基于空间收缩的p s o 算法模型，即种群灭亡精英演化模型和淘汰不良粒子 的精英演化模型，阐明了算法原理及重要参数对算法性能的影响。 2 通过系列的数值实验，给出了两种改进算法参数选择的合理建议。为 研究本文算法性能，在5 个具有代表性的基准测试函数上，进行了与一些经 典改进算法的对比实验。实验结果显示，本文两种算法能有效地避免早熟收 敛同时可提高算法后期局部搜索能力，从而很大程度地改善算法性能。这两 种算法在高维复杂函数寻优上表现了明显的优势，尤其在3 0 维r o s e n b r o c k 函数上表现卓越。此外，模型二算法优化效果更好。 3 本文将两种基于空间收缩的p s o 算法作为学习算法应用于前向网络 训练，研究了基于p s o 的前向网络学习算法的原理和实现过程，并成功应用 在解决投资预测问题上。结果显示，基于空间收缩p s o 学习算法的前向网络 训练速度较快同时具有很好的泛化能力，在投资问题上的预测精度高于基于 b p 算法的前向网络预测精度。 关键词：粒子群优化算法；神经网络；早熟收敛；空间收缩；投资预测 哈尔滨工程大学硕士学位论文 a b s t r a c t o p t i m i z a t i o ni s ak i n do fa p p l i e dt e c h n i q u et of i n do p t i m a ls o l u t i o n si n v a r i o u se n g i n e e r i n gp r o b l e m s f o ri t sw i d ea p p l i c a t i o ni nt h e s ey e a r s ，i ti sh i g h l y c o n c e r n e da n dr a p i d l yd e v e l o p e d w i t ht h ee x p a n s i o no fa p p l i c a t i o nf i e l d s ，t h e t i m ea n ds p a c ec o m p l e x i t yo fo p t i m i z a t i o np r o b l e m sm a k e si tm o r ea n dm o r e d i f f i c u l tt os o l v et h e m ，s ot h a tt r a d i t i o n a lo p t i m i z a t i o na l g o r i t h m sc a n n o tm e e tt h e n e e d si np r a c t i c e i nr e c e n ty e a r s ，t h eb i r t ho fi n t e l l i g e n to p t l m i z a t i o na l g o r i t h m s p r o v i d e sn e wi d e a sa n dm e a n st oo p t i m i z a t i o nt e c h n i q u e sa n dt h ei n t e l l i g e n t a l g o r i t h m s ，w h i c ha r ea p p l i e dw i d e l ya n dd e v e l o pr a p i d l yi ns c i e n c er e s e a r c h ， e c o n o m i c sa n de n g i n e e r i n gt e c h n o l o g y p a r t i c l es w a r mo p t i m i z a t i o ni san e w k i n do fr a n d o ms e a r c hs w a r mi n t e l l i g e n ta l g o r i t h m a sa ni n t e l l i g e n to p t i m i z e r , i t s h o w sp o t e n t i a li ns o l v i n gc o m p l e xo p t i m i z a t i o np r o b l e m s ，a n db e c o m e sf lh o t t o p i ci ns c i e n t i f i cr e s e a r c h e s i nt h i sd i s s e r t a t i o n ，f i r s t l yw eb r i e f l yi n t r o d u c es o m eo p t i m i z a t i o nk n o w l e d g e r e l a t e dt o p s o s e c o n d l y , w es y s t e m a t i c a l l yd i s c u s st h eb a s i cp r i n c i p l e ，t h e p r o c e s so fi m p l e m e n t a t i o na n dp r i m a r yr e s e a r c hr e s u l t s t h e n ，w ed os o m ed e e p r e s e a r c hi n i m p r o v e m e n to ft h ea l g o r i t h m a n di t s a p p l i c a t i o n t h em a i n c o n t r i b u t i o n sg i v e ni nt h ed i s s e r t a t i o na r ea sf o l l o w s 1 t h ed i s s e r t a t i o np o i n t so u tt h er e a s o nf o rp r e m a t u r ec o n v e r g e n c eb yt h e e m p i r i c a la n a l y s i sf r o mn u m e r i c a le x p e r i m e n t s t h e nw ei n t r o d u c et h es p a c e c o n t r a c t i o nm e c h a n i s mt op s o ，a n da c c o r d i n gt ot h ed i f f e r e n tw a y so fs p a c e c o n t r a c t i o n ，w ep r e s e n tt w om o d e l so fp s oa l g o r i t h mb a s e do ns p a c ec o n t r a c t i o n ， t h a ti s t h ee l i t ee v o l u t i o nm o d e lw i mp o p u l a t i o ne x t i n c t i o n ( e e p v ) a n de l i t e e v o l u t i o nm o d e lw i n lb a d p a r t i c l e se l i m i n a t e d ( e e b p e ) w ee x p o u n d t h e p r i n c i p l e sa n d t h ei n f l u e n c eo f i m p o r t a n tp a r a m e t e r st ot h ea l g o r i t h mp e r f o r m a n c e o f b o t ha l g o r i t h m sp r e s e n t e di nt h ed i s s e r t a t i o n 2 w eg i v er e a s o n a b l es u g g e s t i o nt ot h ec h o i c eo ft h ep a r a m e t e r si nb o t h 哈尔滨工程大学硕士学位论文 a l g o r i t h m sb ys e r i e so fn u m e r i c a le x p e r i m e n t s i no r d e rt os t u d yt h ep e r f o r m a n c e o fo u ra l g o r i 恤m s ，w ed i ds e r i e so f c o m p a r i s o ne x p e r i m e n t sw i t hs o m ec l a s s i c a l i m p r o v e da l g o r i t h m s o nf i v e r e p r e s e n t a t i v eb e n c h m a r kt e s tf u n c t i o n s t h e e x p e r i m e n t a lr e s u l t ss h o wt h a t ，b o t ha l g o r i t h m sc a ne f f e c t i v e l ya v o i dp r e m a t u r e c o n v e r g e n c ea n dm e a n w h i l ee l _ l h a n c el o c a ls e a r c hc a p a b i l i t yi nl a t eo fa l g o r i t h m s ， t h u si m p r o v ea l g o r i t h mp e r f o r m a n c eg r e a t l y , a n db o t ha l g o r i t h m ss h o wo b v i o u s a d v a n t a g e si ns e a r c hf o ro p t i m ai nt h eh i g h - d i m e n s i o n a lc o m p l e xf u n c t i o n s ， e s p e c i a l l y i n3 0 - dr o s e n b r o c kf u n c t i o n i n a d d i t i o n ，t h e s e c o n dm o d e l o u t p e r f o f n l $ t h a no t h e ra l g o r i t h m si no p t i m i z a t i o ne f f e c t ss u c ha st h eb e s t - q u a l i t y o f t h eo p t i m a ，s e a r c hs p e e de t c 3 b o t hi m p r o v e da l g o r i t h m sa r ea p p l i e dt ot r a i n i n gf e e d f o r w a r dn e t w o r ka s l e a r n i n ga l g o r i t h m n 伦p r i n c i p l ea n di m p l e m e n t a t i o np r o c e s sb a s e do ns p a c e c o n t r a c t i o np s 0a r es t u d i e d ，f i n a l l yt h ef e e d f o r w a r dn e t w o r kb a s e do ns p a c e c o n t r a c t i o np s oa r es u c c e s s f u l l ya p p l i e di nt h ep r e d i c t i o no fi n v e s t m e n tp r o b l e m t h ee x p e r i m e n t a lr e s u l t si l l u s t r a t et h ee f f i c i e n c y t h ef e e d - f o r w a r dn e t w o r kb a s e d o ns p a c ec o n t r a c t i o np s oh a sf a s t e rt r a i n i n g s p e e da n db e t t e rg e n e r a l i z a t i o n c a p a c i t yt h a nb pl e a r n i n ga l g o r i t h m ，a n di th a sm u c hb e t t e rp r e d i c t i o na c c u r a c yi n t h e1 1 1 0 d e lo f i n v e s t m e n tp r e d i c t i o nc o m p a r e dw i t hb p a l g o r i t h m 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 ；n e u r a ln e t w o r k ；p r e m a t u r e c o n v e r g e n c e ；s p a c ec o n t r a c t i o n ；i n v e s t m e n tp r e d i c t i o n 哈尔滨工程大学 学位论文原创性声明 本人郑重声明：本论文的所有工作，是在导师的指导 下，由作者本人独立完成的。有关观点、方法、数据和文 献的引用已在文中指出，并与参考文献相对应。除文中已 注明引用的内容外，本论文不包含任何其他个人或集体已 经公开发表的作品成果。对本文的研究做出重要贡献的个 人和集体，均已在文中以明确方式标明。本人完全意识到 本声明的法律结果由本人承担。 作者( 签字) ：盗垒垄 日期：年牟月 日 哈尔滨j ：科人学硕十学何论文 1 1 引言 第1 章绪论 1 1 1 传统优化算法概况 最优化理论与算法是应用数学的一个重要分支，它研究的问题是讨论在 众多的被选方案中采用什么样的方案最优以及如何用恰当的方法找到最优方 案或计算最优解的问题。优化是一个古老的课题，长期以来，人们对优化问 题一直进行着探讨和研究。早在t 7 世纪，英国数学家n e w t o n 和德国数学家 l e i b n i t z 发明的微积分就渗透了优化的思想，后来又出现了l a g r a n g i a t l 乘数 法。1 8 4 7 年，法国著名数学家c a u c h y 研究了函数值沿什么方向下降最快的 问题，提出了最速下降法。人们对优化问题的研究随历史发展而不断深入。 然而，任何科学的进步都受当时历史条件的限制，直到二十世纪四十年代， 计算机技术的迅猛发展使得对优化问题的研究不仅成为一种迫切需要，而且 为之提供了有力的求解工具。因此，优化理论和算法也迅速发展起来，形成 - - f 新的学科。至今，在优化领域内已出现了线性规划、整数规划、非线性 规划、动态规划及多目标规划等许多分支。而且这些优化理论及技术在实际 应用中正在发挥着越来越大的作用。随着人类认识的深入以及科学的进步， 优化算法及搜索技术也在不断提高，经典的优化算法如牛顿法、共轭梯度法、 模式搜索法、单纯形法、r o s e n b r o c k 法等已经无法处理人们当l ；i 面对的很多 复杂问题。因此，追求更高效的优化算法成为科学工作者的研究目标之一。 1 1 2 智能优化算法介绍 当前科学技术正进入一个多学科相互交叉、相互渗透的时代，这一点在 计算机科学领域更为突出。计算机的应用使得解决大规模复杂优化问题成为 可能，另一方面，复杂的实际问题也对计算机的计算速度和智能提出了新的 挑战，这种挑战在算法技术方面更为严峻。由于很多传统的优化算法是基于 哈尔滨下样人学硕十学位论文 梯度的算法，而且计算量大，实际问题却往往是不连续或不可导的问题，甚 至有些问题没有明确的函数表达式，所以，这些传统优化算法已经很难满足 人们的需求。科学家们一直在试图寻找一种适合大规模并行计算且具有智能 特性如自组织、自适应、自学习等能力的算法。 经过几十年的努力探讨，他们在一些大自然的生命现象和物理现象中得 到启发，提出了一些新颖的优化算法。而且，这些算法在各种实际问题中得 到了广泛应用并发展迅速。人工神经网络( a n n ) 在一定程度上模拟了人脑 的组织结构，遗传算法( g a ) 借鉴了自然界优胜劣汰的进化论思想，蚁群算 法( a c o ) 的灵感源于自然界蚂蚁觅食的寻径方式，模拟退火算法( s a ) 受 启发于物理学中固体物质的退火过程，禁忌搜索( t s ) 模拟了人类有记忆过 程的智力过程“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 ) ，或 是智能计算( i n t e l l i g e n tc o m p u t a t i o n ) 。 智能计算虽然至今没有一个统一的严格定义，但可以这样概括它它 是人们受自然( 生物界) 规律的启迪，根据其原理模仿求解问题的算法。从 自然界得到启迪模仿其结构进行发明创造，这就是仿生学。这是我们向自然 界学习的一个方面。另一方面，我们还可以利用仿生原理进行设计( 包括设计 算法) ，这就是智能计算的思想。这方面的内容很多，如人工神经网络技术、 遗传算法、模拟退火算法、模拟退火技术和群集智能技术等“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 ，也 译为“微粒群算法”) 就是由美国社会心理学家k e n n e d y 和电器工程师e b e r h a r t 于1 9 9 5 年共同提出的一种新的智能优化算法0 1 。 1 2 研究背景及课题意义 粒子群优化算法是由鸟群，鱼群觅食过程得到的启发而提出的一种群智 能的优化算法，在优化领域显示了很强的优越性。 1 该算法和其他群智能算法一样，沿多条轨道同时搜索，显示了很强的 并行性。 2 哈尔滨i ：稃人学硕十学何论文 2 算法运行无需任何导数信息，只需目标函数值，具有很强的通用性。 3 算法原理简单，程序易实现，比g a 操作更方便。 因此，粒子群优化算法自从产生之日起就引起了国内外学者的广泛关注， 并掀起了对该算法的研究热潮，而且在诸多应用领域涌现出了大量成功应用 的实例州。然而，p s o 的发展仅仅经历了十几年，算法理论基础、算法设计、 应用领域等诸方面都有若干问题尚待解决。因而，改进算法性能、拓宽算法 应用领域、完善算法体系对p s o 这种新算法的发展具有重要作用。所以，对 粒子群优化算法的研究是个同时具有理论意义和应用价值的重要课题。 首先，粒子群优化算法，虽然形式简单易于实现，但是，该算法的收敛 情况与各参数的取值有着密切关系，如何选取合适的参数仍然是一个亟待解 决的问题。 其次，p s o 算法应用在高维复杂问题时，常常会出现早熟收敛的问题， 也就是算法在没有找到全局最优点时种群就发生停滞现象。这些早熟收敛点， 可能是局部极小点，也可能是局部极小点邻域内的点。研究早熟收敛问题可 为改进算法设计奠定基础。 此外，该算法在晚期收敛速度缓慢，局部搜索能力不足。也就是在种群 到达最优点邻域内时，其寻优速度比算法早期慢很多，甚至搜索速度几乎为 零，导致最终结果不甚理想。因此，如何采取有效机制避免这种现象的发生 对改进p s o 算法具有重要意义。 针对上述问题，本文做了细致的研究，提出了算法的改进方案，并做了 大量的数值实验分析，详细分析了改进算法参数选择的问题以及算法性能。 1 3 本文的主要工作及内容安排 1 3 1 主要工作 根据本文提出的问题，对p s o 算法进行了较深入的研究。本文将主要进 行以下几方面的工作： 1 总结了粒子群优化算法理论领域的研究成果，并根据数值实验的经验 详细分析了算法。指出算法容易出现早熟的原因在于在算法后期种群多样性 3 哈尔滨t 。稃大学硕十学侍论文 的丧失以及搜索速度的锐减。 2 为改善p s o 算法早熟收敛和晚期局部搜索能力不足的缺点，将空间 收缩机制引入p s o 算法，提出了基于空间收缩的粒子群优化算法，考虑到空 间收缩的不同方式，我们给出了两种基于空间收缩p s o 算法模型，种群灭亡 精英演化模型和淘汰不良粒子的精英演化模型。阐明了两种基于空间收缩算 法的原理、实现流程和重要参数的影响。 3 通过一系列的数值实验，给出了基于空间收缩p s 0 算法的合理参数 选择建议。并在此基础上，通过与一些经典改进算法几个著名基准测试函数 上的对比实验，分析了本文算法的性能。 4 研究了基于p s o 学习算法的前向网络训练，将本文提出的两种p s o 改进算法应用于前向网络训练中，并成功解决了投资预测问题。 1 3 2 内容安排 本文共6 章。 第1 章简要介绍了传统优化算法及智能优化算法，说明了课题的研究背 景与意义以及论文的主要工作。 第2 章介绍与粒子群优化算法研究相关的优化基础知识。主要包括局部 最优与全局最优概念、优化算法的分类、无免费午餐定理以及群智能的一些 知识。 第3 章回顾p s o 算法的发展，阐明算法原理和流程，并列举几种经典的 p s o 改进算法。最后，总结p s o 算法的收敛性理论并给出了算法的经验分析。 第4 章针对粒子群优化算法的早熟现象和晚期局部收敛能力不足的问 题，提出基于空间收缩技术的粒子群优化算法，并给出两种空问收缩的模型， 详细说明算法原理和实现流程以及重要参数。 第5 章通过系列的数值实验，给出合理参数选择的建议并通过与一些经 典算法的对比实验，分析本文算法的性能。 第6 章研究基于p s o 学习算法的前向网络训练，将本文提出的两种p s o 改进算法应用于前向网络训练中，并成功应用于投资预测问题。 最后，总结全文内容并研究展望。 4 哈尔滨丁张大学硕十学位论文 2 j 1 引言 第2 章优化算法及其研究基础 作为一种群智能的随机优化算法，粒子群优化算法是离不开优化理论和 群智能算法基础的。为此，在介绍粒子群优化算法之前，本章主要介绍优化 算法方面的一些概念、分类和理论以及群智能算法方面的相关知识。 2 2 优化的概念与分类 2 2 1 局部最优与全局最优 优化方法涉及的工程领域很广，问题种类与性质繁多。很多连续变量问 题都可以归纳为函数优化问题( 多数离散变量问题可以归纳为组合优化问 题) ，也就是求函数最优值的问题。函数最优值可分为局部最优值和全局最优 值。 设，( x ) 为定义在n 维欧氏空间露”的某一区域q 上的r t 元实函数，求函 数f i x ) 极小点的问题( 极小化问题) 可表示为 m t m i n 厂( x ) ，x = ( 一，x 2 ，毛) 7 q ( 2 - 1 ) 其中，函数f ( x ) 称为目标函数，区域q 称为可行域。 定义2 1 设f ( x ) 为目标函数，q ( q r ”) 为可行域，若存在x r ” 的f 邻域 口= 渊恬一x 0 0 j ( 2 2 ) 使得z ( x ) f i x ) ，v x q n b 成立，则称x 为函数( x ) 的局部极 小点，或称x 为极小化问题m 。i n ，( x ) 的局部最优解。 哈尔滨一鼙人学硕十学位论文 定义2 2 设，( x ) 为目标函数，q ( q c 屁”) 为可行域，对于点x q ， 若，( x ) f ( x ) v x q 成立，则称x 为函数f ( x ) 的全局极小点，或称x 为极小化问题m i n 厂( x ) 的全局最优解。 e n 无论全局优化还是局部优化问题，解析求解往往有很多困难。这样，数 值求解方法成为求解优化问题的主要手段。很多算法都是从某一仞始点出发， 按照一定的规则和机制在可行域内搜索得到最优解。由于求局部最优问题可 以利用函数的导数、梯度、h e s s i a n 阵等局部信息，局部优化算法相当成熟， 常见的优化算法大多为局部优化算法，如n e w t o n 法、最速下降法、共轭梯 度法、d a v i d o n - f l e t c h e r - p o w e r ( d f p ) 法、l e v e n b e r g - m a r q u a r d t ( l m ) 算法等”1 。 由于缺乏启发信息而且全局优化涉及的问题往往更复杂，全局搜索难度很大， 全局优化算法显然没有局部优化算法那么成熟。没有有效的搜索机制，导致 全局搜索技术相当困难。目前，许多学者把目光转向启发式算法、随机算法 及近似算法如模拟退火算法、填充函数法、隧道函数法等”1 。此外，智能算 法为全局优化问题提供了新的思路，遗传算法、免疫算法已经取得了相当的 成绩，而且正在蓬勃发展中“。1 。 本文研究的粒子群优化算法就是一种具有一定全局搜索能力的并行随机 智能算法。 2 2 2 优化算法及分类 所谓优化算法，其实就是一种搜索过程或规则，它是基于某种思想和机 制，通过一定的途径或规则得到满足用户要求的问题的解。 就优化机制与行为而分，目前常见的优化算法主要可分为：经典算法， 构造型算法、改进型算法、基于系统动态演化的算法与混合算法等。 1 经典算法。包括线性规划、动态规划、整数规划和分枝定界法等运筹 学中的传统算法，其算法计算量一般很大，只适用于小规模问题，工程中往 往不实用。 2 构造型算法。用构造的方法快速建立问题的解，通常算法的优化质量 差，难以满足工程需要。譬如，调度问题中的经典构造方法有：j o h n s o n 法、 6 哈尔滨f 稃人学硕十学位论文 p a l m e r 法、g u p t a 法、c d s 法、d a u n e n b r i n g 的快速接近法、n e h 法等。 3 改进型算法，或称邻域搜索算法。从任一可行解出发，对其邻域的不 断搜索和当前可行解的替换来实现优化。根据搜索行为，它又可分为局部搜 索法和指导性搜索法。 所谓局部搜索法是指以局部优化策略在当前可行解的邻域中进行贪婪搜 索，例如，只接受优于当前可行解的状态作为下一个当前可行解的爬山法； 接受当前可行解邻域中的最好解作为下一个可行当前解的最速下降法等。 所谓指导性搜索法是指利用一些指导规则来指导整个解空间优良解的探 索，如s a 、g a 、e p 、t s 、p s o 等。 4 基于系统动态演化的方法。将优化过程转化为系统动态的演化过程， 基于系统动念的演化来实现优化，如神经网络和混沌搜索等。 5 混合型算法。指上述各算法从结构或操作上相混合而产生的各类算法。 当然，优化算法还可以从其他角度进行分类，如确定性算法和随机算法， 局部优化算法和全局优化算法等“”。 2 3 无免费午餐定理 无免费午餐定理( n of r e el u n c ht h e o r e m s ，简称n f l 定理) 是由最优 化理论领域的最重要的定理之一。它是由w o l p e r ta n dm a c r e a d y 于1 9 9 7 年提 出并证明的“”1 。 n f l 定理的简单表述为：对于所有可能的问题，任何给定的两个算法a 、 a ，如果算法彳在某些问题上表现比彳好，那么彳在其他问题上的表现就一 定比4 差。也就是说，任何两个算法，对于所有问题的平均表现度量是完全 一样的。 该定理说明，没有任何一种算法比线性列举或者纯随机搜索算法更优。 该定理只是定义在有限的搜索空间，对于无限搜索空间结论是否成立尚不清 楚。由于计算机实现的搜索算法只能在有限搜索空间实施，所以该定理对现 存的所有算法都适用。 尽管该定理认为对所有函数集，任何最优化算法是等价的。但是对于有 限的特定函数子集，n f l 定理则认为可以设计出在该子集上平均表现性能更 7 哈尔滨t = 拌人学硕十学位论文 优的算法，这也是本文研究的一个重要基础。 2 4 群智能算法 自然界中存在好多这样的生物，它们个体的能力微弱，但聚集起来就能 完成很多大型的任务。单只蚂蚁的能力和智能相当简单，不论工蚁还是蚁后 都不可能有足够的能力指挥筑巢、觅食、迁徙或清扫蚁穴等复杂行为。那么， 它们是如何相互协调、分工、合作完成这些任务的呢? 我们经常能够看到成 群的鸟、鱼或者浮游生物。这些生物的聚集行为有利于它们觅食和逃避捕食 者。它们的群落动辄以十、百、千甚至万计，并且经常不存在一个统一的指 挥者。它们是如何完成聚集、移动这些功能呢? 这些问题都是非常有趣的很 值得探讨的问题。 基于对以上自然界中的群集生命现象的细致观察与深刻研究，人们从仿 生学中得到启示，通过模拟自然界中一些群集生命的行为提出了一类新的智 能算法一群智能算法。 群体智能作为一个新兴领域，自从2 0 世纪8 0 年代出现以柬，引起了多 个学科领域研究人员的关注，已经成为人工智能以及经济、社会、生物等交 叉学科的热点和前沿领域。由单个复杂个体完成的任务可由大量简单的个体 组成的群体合作完成，而后者往往更具有健壮性、灵活性和经济上的优势。 群体智能( s w a r mi n t e l l i g e n c e ) 利用群体优势，在没有集中控制，不提供全局模 型的前提下，为寻找复杂问题解决方案提供了新的思路。对群体智能的定义 进行扩展，普遍意义上有以下几种理解。 1 由一组简单智能体( a g e n t ) 涌现出来的集体的智能( c o l l e c t i v e i n t e l l i g e n c e ) ，以蚁群优化算法( a n tc o l o n yo p t i m i z a t i o n ，a c o ) 和蚂蚁聚类算 法等为代表； 2 把群体中的成员看作粒子，而不是智能体，以粒子群优化算法( p a r t i c l e s w a r mo p t i m i z a t i o n ，p s o ) 为代表。 群体智能是对生物群体的一种软仿生，有别于传统的对生物个体结构的 仿生。群智能算法可以将个体看成是非常简单和单一的，也可以让它们拥有 学习的能力，从而解决具体的问题“”。 8 哈尔滨i 程人学硕十学佛论文 群智能可以表述为：一组相互之间可以进行直接通讯或间接通讯( 通过 改变局部环境) 的主体，能够通过合作对问题进行分布求解。换言之，一组 无智能的主体通过合作能表现出智能行为特征“”。 群智能系统表现出来这样的特性：这些系统利用局部信息从而可能产生 不可预测的群体行为。它们由具有简单能力的低级个体组成，个体只能与其 邻近的个体进行某种简单的通讯和协同( 直接通信) ，或者通过环境问接与其 它个体通讯( 间接通信) 。然而，低级个体与它们的环境局部交互所表现出来 的集体行为却形成了具有某种一致功能的整体模式“”。 群智能的概念是由m i l l o n a s 在1 9 9 4 年开发人工生命算法时提出的，同时 m i l l o n a s 还提出了群智能算法的五点原则。 1 接近性原则：群体应能够实现简单的时空计算； 2 优质性原则：群体能够响应环境要素； 3 变化相应原则：群体不应把自己的活动限制在一狭小范围； 4 稳定性原则：群体不应每次随环境改变自己的模式； 5 适应性原则：群体的模式应在计算代价值得的时候改变”1 。 社会组织的全局群行为是由群内个体行为以非线性方式出现的。个体问 的交互作用在构建群行为中起到重要的作用。 在群体智能的范畴内，已经取得了相当多的研究成果。研究和掌握群体 智能系统的特性与规律，是一个具有理论和应用两个方面重要意义的课题。 它的研究与发展将为人工智能领域带来新的活力，提供解决问题的全新的角 度和方法。同时，由于它广阔的市场前景以及其与人类社会经济密切相关性， 群体智能的研究现实意义非常明显。可以预见，对群体智能的研究即将全面 展开，必将在某些方面出现新的成果“”。 2 5 小结 本章介绍了与粒子群优化算法相关的局部最优与全局最优的问题，介绍 了优化算法的分类，阐述了优化理论中一个相当重要的定理无免费午餐 定理，最后，介绍了与粒子群优化算法密切相关的群智能的一些知识。 9 哈尔滨t 稃人学硕十学付论文 3 1 引言 第3 章粒子群优化算法概述 粒子群优化算法( a s o ) 是一种很有i ； 景的随机搜索群智能优化算法，在优 化的各个应用领域显示了很强的实力。本章将介绍p s o 的各个方面，主要概 括以下方面内容：算法的产生、发展，算法的原理，改进算法以及收敛性的 理论和经验分析等。 3 2 粒子群优化算法的产生与发展 3 2 1 算法的提出 粒子群优化算法( p s o ) 是由k e n n e d y 博士和e b e r h a r t 博士提出的一种 基于群智能方法的进化计算技术，该算法首先于1 9 9 5 年提出，短短的十几年 中得到了迅速的发展。粒子群优化算法是基于群体的演化算法，其思想来源 于人工生命和演化计算理论。 生物社会学家e o w i l s o n 对鱼群进行了研究后提出：“至少在理论上， 鱼群的个体成员能够受益于群体中其他个体在寻找食物的过程中的发现和以 前的经验，这种受益超过了个体之白j 的竞争所带来的利益消耗，不管任何时 候食物资源不可预知的分散。”这说明，同种生物之间信息的社会共享能够带 来好处。 r e y n o l d s 对鸟群飞行进行研究后发现，鸟仅仅是追踪它有限数量的邻居， 但最终的整体结果是整个鸟群好像在一个中心的控制下，即复杂的全局行为 是由简单规则的相互作用引起的。这就是p s o 算法的基础“。 p s o 即源于对鸟群觅食行为的研究，一群鸟在随机搜寻食物，如果这个 区域里只有一块食物，那么找到食物的最简单有效的策略就是搜寻目i j i 离食 物最近的鸟的周围区域。p s o 算法就是从这样的模型中得到启示而产生的。 l o 哈尔滨： 程人学硕十学位论文 在方法论上，p s o 算法植根于两个主要方面的理论：一方面，很明显它 与人工生命，尤其是群智能理论有密切关系；另一方面，它也与进化计算， 比如遗传算法、进化规划等紧密关联0 1 。 在p s o 算法中，用速度和位置描述粒子，由粒子组成种群，粒子间通过 信息共享实现良好的全局搜索能力。该算法概念的提出有一定的文献基础的 和深刻的实际意义。“群”这个术语在很多文献中曾被提到，尤其是在m i l l o n a s 的一篇文章中提到了五条群智能的基本原则( 见第2 章2 4 节) 。p s o 的概念和 公式看起来很贴近这五个原则。k e n n e d y 和e b e r h a r t 在文献 3 中提到选j 犟粒 子”是一种折中，当种群个体的质量和体积很小时，可以被称作“点”，但感 觉上速度和加速度更适用于粒子，甚至可以定义粒子的质量和体积任意小。 此外，r e e v e s 在文献 1 5 中也曾提到“粒子系统”。所以，作者选用了“粒 子群”这个概念来描述该算法n ，。 3 2 2 算法发展 p s o 算法作为一种新的群智能进化算法，自提出以来，得到了进化计算 领域众多学者的广泛关注。s h i 等首先在速度项引入惯性权重( i n e r t i a w e i g h t ) ， 随后又提出了线性递减惯性权重p s o ( l i n e a r l yd e c r e a s i n gi n e r t i aw e i g l l t ) ， 并对p s o 模型中参数选择作了详尽阐述“”。c l e r c 等提出收缩因子法 ( c o n s t r i c t i o n f a c t o r m e t h o d ) “”】，c a r l i s l e 与d o z i e r 提出了较全面的p s o 算法 参数选择的建议”，y u h u is h i 等提出了自适应p s o 算法恤“。此外，由其它 算法与p s o 算法的融合的混合算法也发展迅速，如与遗传算法、进化规划、 免疫算法、禁忌搜索算法、模拟退火算法、非线性单纯形法等算法的结合都 有过研究嘲“。从拓扑结构上，p s o 算法也有全局版和局部版之分( 见图3 1 ) ， 文献 a 0 中详细研究了邻域拓扑结构对算法性能的影响。最初，p s o 仅仅用 来解决连续优化问题，后来，有学者又推广到解决离散问题，提出二进制p s o 算法叭1 。在理论方面，c l e r c 等分别从代数角度和离散动念系统的角度分析了 算法的收敛性嘲。在应用领域，p s o 算法已经成功应用于函数优化、人工 神经网络训练、电力系统、模糊系统控制、系统辨识、状念估计等领域“捌。 哈尔滨l ：稃人学硕十学位论文 ( a ) 全局版模型( b ) 局部版模型 图3 1p s o 算法的两种拓扑结构模型 3 2 3 发展展望 从国内外关于p s o 算法的大量文献及进化计算领域的方展趋势分析，作 者认为以下几个方面值得关注”“： 1 对p s o 算法自身的研究 拓扑结构对算法影响显著，虽然有过这方面的研究，但是目前的研究还 未能全面掌握复杂空间拓扑和邻域拓扑对算法的影响。此外，搜索机制( 比 如分阶段搜索等方式) 对算法也有较大影响，在这方面有过一些研究，但仍 值得进一步研究。 2 理论分析与算法评价 现阶段对p s o 的理论研究还很不成熟，还缺乏系统的理论分析，数学基 础相对薄弱。如何利用有效的数学工具对p s o 算法的运行行为、收敛性及 算法复杂性分析以及如何评价算法是目前研究的热点之一。 3 p s o 算法的生物学基础 如何根据群体进化行为完善p s o 算法，同时分析群体智能行为，如何将 其引入p s o 算法中，以充分借鉴生物群体进化规律和进化的智能性也是目前 的研究方向之一。 4 p s o 算法与其它算法的融合 在p s o 算法与其它算法的融合方面已有过大量的研究，然而，这个方面 的研究仍将继续发展。 5 应用领域的拓展 2 哈尔滨一i ：稃大学硕十学竹论文 迄今为止，p s o 算法已成功应用于很多领域，显示了算法很强的生命力。 如何将算法应用于更多的应用领域，并在应用中发展算法，也是一个相当重 要的课题。 3 3 粒子群优化算法原理 与其它进化算法类似，p s o 算法通过个体问的协作与竞争，实现复杂空 间的搜索能力。算法中表示问题潜在解的集合称为种群，种群的个体称为粒 子，表示问题的一个可行解。用速度和位置来描述粒子，并用目标函数确定 粒子的适应度( f i t n e s sv a l u e ) 。在每一代中粒子通过追踪两个极值，一个是粒 子自身迄今找到的最优值p b e s t ，一个是种群迄今找到的最优值g h o s t 。这样 粒子追随当前最优粒子，逐步迭代( 进化) ；实现强大的搜索能力。 3 3 1 算法的数学描述 算法的数学描述：设q ( cr ”) 为一疗维目标搜索空| 日j ，由m 个粒子组成 一个种群x = b 。，x ：， 。 记第f 个粒子的速度和位置分别为 q ( 七) = ( v ，i ( 七) ，h 2 ( 七) ， ( 七) ) ，一( 七) = ( x l ，( 七) ，x f 2 ( 露) ，j ( 七) ) 7 第f 个粒子的当前个体最优解为 p b e s t , ( 七) = ( p 。l ( 七) ，只2 ( 七) ，p 。( 七) ) 种群全体的当前最优解为 g b e s t g ( | ) = ( g g t ( 七) ，9 9 2 ( 七) ，g 。( 七) ) 其中k 表示当前进化代数。根据追踪最优粒子原理，粒子置按下式更新其速 度和位置。 嘣“d 2 氍g a 竹n d l ( o 鬣1 ) ( g b e 1 s t 芝挈x l d 蓠“d 卜 c 2 ， ，( 七) 一( 七) ) 。 ( 七+ 1 ) = x u ( k ) + ( i + 1 ) ( 3 - l b ) 其中，d = 1 , 2 ，。栉。 式( 3 1 a ) 、( 3 1 b ) 分别描述粒子速度和位置更新方式。q ，岛为加速常 哈尔滨l ：程人学硕十学付论文 数( 或学习率) ，通常在0 2 间取值，分别表示粒子对个体认知和社会知识 的信任程度，r a n d ( o ，1 ) 和r a n d ( o ，1 ) 表示 0 ，l 】范围的服从平均分布的独立随机 数。 公式(