（计算机应用技术专业论文）粒子群—模拟退火融合算法及其在函数优化中的应用.pdf

摘要 优化是一种以数学为基础，用于求解各种实际问题的应用技术，其目的是 对一个给定的问题，从众多方案中选择出最优方案，使目标函数适应度达到最 优值。随着人们认识与改造世界能力的扩大，在实际工程领域中，涌现出多目 标、非线性、不可微，甚至混杂的系统。经典优化方法不能有效求解，必须采 用计算智能技术来解决此类问题。 2 0 世纪8 0 年代以来，智能优化算法( 人工神经网络、模拟退火算法、遗传 算法、粒子群算法和蚁群算法) ，通过模拟某些自然现象和过程发展起来，为优 化理论提供了新的思路和手段，并在科学、经济以及工程领域得到了广泛应用。 作为粒子群优化算法的改进线性惯性权重粒子群优化算法，改善了粒 子群优化算法易陷入局部最优的状况。但由于仅使惯性权重线性减小，使算法 一旦进入局部最优点邻域内就很难跳出来，以致收敛到局部最优点，而且迭代 次数往往较大。因此，本文提出了一种非线性的惯性权重调整策略，得到非线 性惯性权重粒子群优化算法( u l w p s o ) ，该方法虽在单峰、多峰中取得了较好 的效果，但是在多峰函数中存在收敛精度较低，收敛成功率较低等缺点。 在进化算法的搜索过程中，算法的探测和开发能力单靠一种算法往往无法 得到有效的利用。因此，在粒子群优化算法的搜索过程中融合其他优化方法的 思想，是提高粒子群优化算法搜索效率和求解质量的一个有效途径。 因此，本文将模拟退火算法的m e t r o p o l i s 准则引入到非线性调整惯性权重 粒子群优化算法( u l w p s o ) 中，得到粒子群一模拟退火融合算法( u l w p s o - s a 融合算法) ，使得粒子在飞行的过程中，不仅可以接受使目标函数适应度“变优” 的解，而且可以一定的概率接受使目标函数适应度“变坏”的解。实验表明 u l w p s o s a 融合算法在寻找全局最优值的过程中增加了粒子的多样性，增强 了粒子群摆脱局部最优解的能力，不易陷入局部最优，具有较强的全局寻优能 力，较高的收敛速度和收敛精度。 关键词：粒子群优化算法，模拟退火算法，粒子群一模拟退火融合算法，函数 优化 a b s t r a c t o p t i m i z a t i o ni sa na p p l i c a t i o nt e c h n o l o g y ，w h i c hb a s e do nm a t h e m a t i c st os o l v e a l lk i n d so fp r a c t i c a lp r o b l e m s i t sp u r p o s ei st oc h o o s et h eb e s tp l a nf r o mn u m e r o u s p l a n s ，t of m dt h eo p t i m a lv a l u eo ft h eo b j e c t i v ef u n c t i o ni ns o l v i n ga c t u a lp r o b l e m w i t hp e o p l e sc o g n i t i o na n dt r a n s f o r m a t i o nw o r l da b i l i t ye n l a r g ed a yb yd a y ，a t a c t u a ls y s t e ma n de n g i n e e r i n gf i e l d s ，e m e r g em o r em u l t i - o b j e c t i v e s ，n o n l i n e a r , n o t d i f f e r e n t i a b l e ，e v e nm i x e ds y s t e m t r a d i t i o n a lo p t i m i z a t i o nm e t h o d sc a nn o ts o l v e t h e s eq u e s t i o n se f f e c t i v e l y ，s ow em u s tu s ec o m p u t a t i o n a li n t e l l i g e n c et e c h n o l o g yt o s o l v et h e s ep r o b l e m s s i n c e1 9 8 0 si 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 u c ha s ：a r t i f i c i a ln e u r a l n e t w o r k s ，s i m u l a t e da n n e a l i n ga l g o r i t h m ，g e n e t i ca l g o r i t h m ，p a r t i c l es w a r m o p t i m i z a t i o na l g o r i t h ma n da n tc o l o n ya l g o r i t h m ) ，d e v e l o p e db ys i m u l a t i n gs o m e o ft h en a t u r a lp h e n o m e n aa n dp r o c e s s e s ，p r o v i d en e wi d e a sa n dt o o l st ot h e o p t i m i z a t i o nt h e o r y ，a n dh a sb e e nw i d e l yu s e di nt h es c i e n t i f i c ，e c o n o m i c , a n d e n g i n e e r i n g f i e l d s a sai m p r o v e m e n ta l g o r i t h mo 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 - - l i n e a ri n e r t i aw e i g h tp a r t i c l es w a r mo p t i m i z a t i o ni m p r o v et h ep a r t i c l es w a r m o p t i m i z a t i o na l g o r i t h me a s i l yf a l li n t ot h el o c a lo p t i m a lc o n d i t i o n s h o w e v e r , b u t t h ei n e r t i aw e i g h td e c r e a s e sl i n e a r l ym a k et h ea l g o r i t h mo n c et u ni n t ot h ea r e a n e a r l o c a lo p t i m a lp o i n t , i tw i l lb ev e r yd i f f i c u l tt oj u m po u t , a n dg e tal o c a lo p t i m a lp o i n t i t si t e r a t i o n si su s u a l l yv e r yl a r g e t h e r e f o r et h et h e s i sp r e s e n t san o n l i n e a ri n e r t i a w e i g h ta d j u s t m e n ts t r a t e g y ，s ow eg e tt h eu n - l i n e a ri n e r t i aw e i g h tp a r t i c l es w a r m o p t i m i z a t i o na l g o r i t h m ( u l w p s o ) ，a l t h o u g hi tg e tg o o dr e s u l t i n o p t i m i z i n g s i n g l e p e a k f u n c t i o na n d m u l t i p e a l 【f u n c t i o n b u t i n m u l t i p e a l 【f u n c t i o n o p t i m i z a t i o np r o c e s st h eu l w p s oa l g o r i t h ma l s oh a sl o wc o n v e r g e n c ea c c u r a c y a n dl o wc o n v e r g e n c es u c c e s sr a t ed e f e c t s i nt h ep r o c e s so fe v o l u t i o na l g o r i t h m sr e s e a r c h ，a l g o r i t h m sd e t e c t i n ga n d d e v e l o p m e n tc a p a b i l i t yd e p e n do n o n ea l g o f i t h r a a r eo f t e nu n a b l eo b t a i n e d e f f e c t i v e l y t h e r e f o r e , f u s i n go t h e ro p t i m i z e dm e t h o dt ot h e p a r t i c l es w a r m o p t i m i z a t i o n 砧g 硎t h md e t e c t i n gp r o c e s si s a l le f f i c i e n tm e t h o dt or a i s et h ep s 0 a l g o r i t h md e t e c t i n ge f f i c i e n c ya n d s o l u t i o nq u a l i t y s ot h et h e s i sf u s e dt h es i m u l a t e da n n e a l i n ga l g o r i t h m sm e t r o p o l i st h o u g h tt o t h eu n l i n e a ri n e r t i aw e i g h 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 f i t h m ( u l w p s 0 a l g o r i t h m ) ，s ow eg e tt h eu l w p s 0 - s af u s i o na l g o r i t h m t h eu l w p s 0 一s a f u s i o na l g o r i t h mm a k ei ns w a r m sf l i g h tp r o c e s s ，t h es w a mn o to n l yc a na c c e p t g o o df u n c t i o nv a l u ep o i n t ，b u ta l s oc a na c c e p tw o r s ef u n c t i o nv a l u ep o i n tb yc e r t a i n p r o b a b i l i t y t h r o u g h c a r r i e de x p e r i m e n t , t h er e s u l ts h o wu l w p s o - s af u s i o n a l g o r i t h mi n c r e a s e dt h es w a r m sm u l t i p l i c i t y ，a n ds t r e n g t h e n e ds w a r m sg e tr i do f t h ep a r t i a lo p t i m a ls o l u t i o na b i l i t y , c a n tr u ni n t ol o c a lm i n i m u me a s i l y ，s t r e n g t h e n t h eo v e r a l ls i t u a t i o nd e t e c t i n ga b i l i t y ，a n dh a sh i g h e rc o n v e r g e n c er a t ea n dp r e c i s i o n 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 na l g o r i t h m ，s i m u l a t e da n n e a l i n ga l g o r i t h m ， s w p s 0 - s aa l g o r i t h m ，f u n c t i o no p t i m i z a t i o n m 独创性声明 本人声明，所呈交的论文是本人在导师指导下进行的研究工作及取得的研 究成果。尽我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其 他人已经发表或撰写过的研究成果，也不包含获得武汉理工大学或其他教育机 构的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任何贡 献均己在论文中做了明确的说明并表示了谢意。 签名：趣立：童一日期：芝篁：生：丝 关于论文使用授权的说明 本人完全了解武汉理工大学有关保留、使用学位论文的规定，即学校有权 保留、送交论文的复印件，允许论文被查阅和借阅；学校可以公布论文的全部 或部分内容，可以采用影印、缩印或其他复制手段保存论文。 ( 保密的论文在解密后应遵守此规定) 日期：丝益：生鱼 武汉理工大学硕士学位论文 第1 章绪论 1 1 本文研究背景和意义 优化技术以数学为基础 ，用于求解各种工程问题的最优方案，广泛应用 于工业、农业、国防、工程、交通、金融、化工、能源、通信等许多领域，已 经在资源利用、结构设计、调度管理、后勤供应等许多领域中产生了巨大的经 济效益和社会效益。 随着人类生存空间的扩大，以及认识与改造世界范围的拓宽，常规优化方 法如1 1 】：牛顿法、共辆梯度法、模式搜索法、单纯形法等，己无法处理人们所 面对的复杂问题。因此，高效的优化算法成为科学工作者的研究目标之一。同 时高速数字计算机日益广泛的应用，为求解复杂的优化问题提供了强有力的保 障工具。由此优化理论和算法迅速发展起来，形成一门新的学科，至今己出现 【2 】：线性规划、整数规划、非线性规划、几何规划、动态规划、随机规划、网 络流等许多分支，这些优化技术在实际应用中正发挥越来越大的作用。 在我国国民经济的各个领域中存在着相当多高难度的优化命题【1 ，2 3 l ，如： 在运输中的最优调度、资源的最优分配、生产流程的最优编排、国土的最优开 发、农作物的合理布局、建筑工程设计领域中坝体断面的优化设计、水利优化 设计、水库蓄洪量的最优设计等，都是一些变量维数高、非线性强且不易求解 的优化命题。 国内外的实践应用表明【3 l = 在同样条件下，经过优化技术处理的系统效率 高、能耗低、资源利用合理，能够提高经济效益，而且随着处理对象规模的增 大，这种效果也更加显著。这对国民经济的各个领域来说，其应用前景无疑是 巨大的。 1 2 当前国内外发展现状 1 2 1 最优化问题 最优化问题【2 l 是从所有可能的( 有限的或无限的) 方案中选出最合理的、能达 武汉理工大学硕士学位论文 到最优目标的方案，而搜索最优方案的方法就是最优化方法。长期以来，人们 对最优化问题进行不断的探讨和研究。早在1 7 世纠1 1 ，英国伟大科学家牛顿开 创了微积分时代，提出极值问题。但由于受计算手段等历史条件的限制，在2 0 世纪4 0 年代以前，最优化理论还未形成- - j 7 学科。 2 0 世纪4 0 年代以来，随着生产和科学研究突飞猛进的发展，最优化理论 和方法日益受到人们的重视，特别是计算机的广泛应用，使最优化问题的研究 不仅成为一种迫切的需要，而且有了求解的有力工具，最优化理论和相关算法 迅速发展起来，形成了一门新的应用数学分支学科，已经渗透到生产、管理、 商业、军事、决策等各领域i l j 。 优化包括搜索最小值和最大值两类情况，传统的优化方法主要有以下三裂l ，2 j ： 1 枚举法：当可行解数目为有限时，理论上枚举法可以得到较为精确的最 优解。而对于连续函数，首先要进行离散化处理，解的精确性依赖于离散化的 细度。枚举法的主要缺点是：当枚举的空间较大时，求解的效率较低，有时所 需的计算资源甚至是无法满足的。 2 启发式算法：寻找能产生可行解的启发式规则，以找到一个近似最优解。 启发式算法效率比较高，但是每个具体问题都有其特殊性，都要找到其特有启 发式规则。因此，启发式规则一般无通用性，不适合求解其他问题。 3 基于梯度的搜索算法：一般优化问题求解，用的较多的是基于梯度的搜 索算法。基于梯度的搜索算法求解问题的效率较高，算法也有通用性，但是搜 索到最优解的概率依赖于初始点的选取。 随着生产、经济、技术的发展，工程技术人员、管理人员在实际工作中经 常会面临这样一类问题1 1 ，2 ，3 l ：在工程设计中，怎样选取参数使得设计既能满足 要求又能降低成本；在资源分配中，怎样的分配方案既能满足各方面的基本要 求，又能获得好的经济效益：在生产计划安排中，选择怎样的计划方案才能提 高产值和利润；在原料配比问题中，怎样确定各种成分的比例才能提高质量、 降低成本。这一类问题的共同点是选出最合理、达到最优目标的方案，这就是 工程优化问题。 许多工程优化问题十分复杂，常需要在复杂而庞大的搜索空间中寻找最优 解或者准最优解。传统的优化算法【1 l 面对这些大型问题时，需遍历整个搜索空 间，会产生搜索组合的爆炸，无法在多项式时间内完成搜索，无论是在计算速 度、收敛性、初值敏感性等方面都远不能满足要求，因此很难用于工程优化问 2 武汉理工大学硕士学位论文 题的求解。 1 2 2 计算智能发展综述 由于人们认识与改造世界的能力扩大，对科学技术也提出了更新、更高的 要求，其中对高效的优化技术和计算方法的要求日益迫切。同时，在实际系统 中，特别是人工智能与控制领域，不断涌现出多目标、非线性、不可微，甚至 混杂的系统，经典优化方法不能有效求解的优化问题，必须采用智能技术p j 。 1 9 9 2 年美国学者b e z e d kj c 在 a p p r o x i m a t er e a s o n i n g ) ) 学报上首次给出 了计算智能( c o m p u t a t i o n a lh l t e l l i g e n c c ) 的定义【3 1 ：计算智能是依据工作者所提供 的数值化数据，来进行计算处理的。 1 9 9 4 年6 月，i e e e 神经网络委员会在o r l a n d o 召开了i e e e 首次国际计算 智能大会( w o r l dc o n f e r e n c eo nc o m p u t a t i o n a li n t e l l i g e n c e ) 3 1 ，首次将进化计算、 人工神经网络和模糊系统这三个领域合并在一起，形成了“计算智能”这个统一 的技术范畴。 计算智能从模拟自然界生物群体和人类智能现象发展而来，用计算机模拟 和再现人类的某些智能行为，并用于改造自然的工程实践的一种新型人工智能 研究领域。计算智能的最大特点是【3 】：对函数要求较弱、寻优结果与初值无关， 并具有一定的并行性，不需要建立问题本身精确的数学模型，适合于解决那些 因为难以建立有效的形式化模型，而用传统人工智能技术又难以有效解决甚至 无法解决的问题。因而计算智能显示出其不可比拟的优势，己成为学术界研究 的一个热点。 归纳起来，计算智能有如下一些优点【3 j ： 1 自组织、自适应和自学习性。该特性的存在，消除了算法设计过程中一 个最大障碍，即需要事先描述问题的全部特点，并且要针对不同问题的不同特 点采取不同的措施。因此，借助进化算法的通用计算能力，我们能够解决那些 复杂的非结构化问题。 2 本质并行性。随着计算机性能飞速发展，算法的并行性有着特别重要的 意义。超大规模集成电路技术使得专门用于计算的多节点互连成为可能，并且 根据节点数目成倍的提高计算效率。 3 记忆的分布性。计算智能在信息处理上是并行的，在信息的存储和表达 上是分布的。进化算法中种群的数目大小对问题的求解除速度以外并没有根本 3 武汉理工大学硕士学位论文 上的影响，从而提高了容错性和鲁棒性。 4 其它特性。除了上述优点，计算智能根据具体算法还有自身的一些优良 性能，如：进化算法一般对函数的连续性和导数没有严格的要求，对于多目标 优化问题能给出一组p a r e t o 非劣解等。 作为计算智能的一种，进化算法具有如下特点【2 】：不是盲目式的乱搜索， 也不是穷举式的全面搜索，而是根据个体生存环境，即：目标函数来进行有指 导的搜索。进化算法只需利用目标的取值信息而不需要梯度、连续性、凸性等 信息，因而适用于大规模、高度非线性的不连续、多峰函数的优化以及无解析 表达式的目标函数优化，具有很强的通用性；算法的操作对象是一组个体，而 非单个个体，具有多条搜索轨迹，因而具有隐并行性。 进化计算本身【1 l 对待求解的问题一无所知，只要给出了合理的表示方案、 适应函数、遗传算子、控制参数、终止准则等内容，算法就可以对未知空间进 行有效的搜索，最后找出问题的最优解。进化计算目前已被成功的应用到那些 难以用传统的方法进行求解的复杂问题之中，特别是在系统识别、故障诊断、 机器学习及神经网络设计等领域，进化计算已经显示出它的魅力。然而，作为 一个新的、跨学科的研究课题，进化计算的理论研究还有待进一步完善，其中 包括基础理论、编码机制、控制参数的选择策略、收敛性分析等等。 2 0 世纪8 0 年代以来，一些新的有别于传统的优化算法的方法得到了迅速 发展：人工神经网络( a r t i f i c i a ln e u r a ln e t w o r k s ，删，在一定程度上模拟了人 脑的组织结构；遗传算法( g e n e t i c a l g o r i t h m ，g a ) ，借鉴了自然界优胜劣汰的进 化思想；模拟退火算法( s i m u l a t e da n n e a l i n g ，s a ) 【4 】，思路源于物理学中固体物 质的退火过程。以及模拟自然界生物群体行为来构造的群体智能算法( s w a r m i n t e l l i g e n c ea l g o r i t h m ) ，典型的方法有：m d o r i g o 提出的蚁群算法( a n tc o l o n y o p t i m i z a t i o n ，a c o ) 以及j k e n n e d y 与r e b e r h a r t 提出的粒子群算法( 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 ) 5 1 。 粒子群优化算法( p s o ) 源于对鸟群觅食过程中的迁徙和聚集的模拟【5 1 ，收敛 速度快、易实现并且仅有少量参数需要调整，目前己经被广泛应用于目标函数 优化、动态环境优化、神经网络训练、模糊控制系统等许多领域。对粒子群优 化算法的研究发现【6 】，早期收敛速度较快，但到寻优的后期，其结果改进则不 是很理想。这主要由于算法收敛到局部最优点，缺乏有效的机制使算法逃离该 局部最优点。粒子群优化算法是一种较新的群体智能优化算法，类似于遗传算 4 武汉理工大学硕士学位论文 法，但没有交叉和变异等遗传操作，也无需二进制编码，只有位置更新和速度 更新算子，而且对目标函数没有连续、可微等要求 6 1 。 模拟退火方法思想( s a ) 来源于固体的退火过程。1 9 8 3 年，k i r k p a t r i c k l 4 j 等人 首先意识到固体退火过程与优化问题之间存在着类似性，m e t r o p o l i s 等对固体 在恒定温度达到热平衡过程的模拟也给他们以启迪。通过把m e t r o p o l i s 准则引 入到优化过程中来，最终他们得到一种对m e t r o p o l i s 算法进行迭代的优化算法， 这种算法类似固体退火过程，称之为模拟退火算法。由于众多专家和学者对模 拟退火算法的不断的进行研究与改进，使得该算法从基本的模拟退火算法发展 到了今天的多样型的模拟退火算法，如：快速模拟退火算法【羽，使得该算法的 速度和收敛性都得到较大提高；适应性的模拟退火算法1 9 1 ，使得该算法具有智 能性；遗传模拟退火算法i l o l ，即将遗传算法和模拟退火算法二者的优越性结合 起来。每种算法的提出都与其特定应用范围紧密结合，这样才使得改进的算法 在其应用领域具有较好的适用性。 1 3 本文的主要内容 本文主要做了以下几方面的工作：系统研究了粒子群优化算法和模拟退火 算法的基本理论知识；对粒子群优化算法进行了改进，加入了惯性权重，提出 一种非线性惯性权重调整策略，并对改进后的粒子群优化算法用测试函数进行 了性能分析；最后将模拟退火算法与非线性惯性权重粒子群优化算法进行了融 合，用五个优化测试函数对融合算法进行了性能分析。全文共分五章： 第1 章：介绍了的本文的研究背景、最优化问题、计算智能的基本理论和 技术发展史，以及粒子群优化算法和模拟退火算法的研究现状，总结了本文的 主要内容和研究成果。 第2 章：研究了粒子群优化算法的基本思想、数学模型、算法的特点，概 括了粒子群算法的应用领域( 函数优化、神经网络训练、组合优化、工程应用) ； 设计并实现了粒子群优化算法，给出了的基本的执行流程和流程图，对算法的 时间复杂度与边界条件进行了总结分析； 第3 章：研究了模拟退火算法的基本思想、数学模型、算法的特点，设计 并实现了模拟退火算法，给出了算法的流程和流程图，并对影响模拟退火算法 性能的冷却进度表的几个主要参数进行了分析。 5 武汉理工大学硕士学位论文 第4 章：对粒子群优化算法的进行了改进，加入了惯性权重参数，针对线 性调整惯性权重的不足，提出了一种非线性调整惯性权重的策略，得到改进的 非线性惯性权重粒子群优化算法( u l w p s o ) 。用五个标准测试函数对改进算法 的性能进行了分析，实验数据表明，改进算法在一定程度上提高了算法的收敛 性能，较好的平衡了算法的全局收敛能力和局部搜索能力，具有较高的收敛精 度和较快的收敛速度。但在高维、多峰、复杂问题寻优时该算法仍存在早熟收 敛、收敛精度比较低的缺点。 第5 章：对模拟退火算法和非线性调整惯性权重粒子群优化算法( u l w p s o ) 进行了融合，将模拟退火算法的m e t r o p o l i s 准则引入u l w p s o 算法当中，使得 粒子群不仅能够接受目标函数适应度较优的解，也可以以一定概率接受目标函 数适应度“变坏”的解，增加了粒子群的多样性。通过对用五个标准测试函数对 融合算法( u l v r p s o s a ) 的性能进行了分析，实验表明u l w p s o s a 算法提高了 收敛的速度和最优值的精度，增强了粒子全局寻优的能力。 第6 章：总结与展望。 1 4 本文的主要成果 本论文的研究成果是： 1 针对粒子群优化算法( p s o ) 易陷入局部最优解的不足，对粒子群优化算 法进行了改进，加入了惯性权重参数，并对惯性权重策略进行了改进，提出一 种非线性调整惯性权重的策略，得到改进的非线性惯性权重粒子群优化算法 ( u l w p s o ) ，运用五个标准测试函数对p s o 、l w p s o 、u l w p s o 进行了性能分 析和比较，实验数据表明u l w p s o 具有较强的收敛精度和较高的收敛速度，不 易陷入局部最小； 2 根据模拟退火算法以一定概率接受“恶化”解，有利于避免算法搜索过程 因陷入局部最优解而无法自拔的弊端，将模拟退火算法的这种思想，引入到非 线性惯性权重粒子群优化算法( u l w p s o ) 中，得到粒子群一模拟退火融合算法 ( u l w p s o s a ) 。实验数据表明，该方法能够得粒子在搜索过程中以一定概率接 受使目标函数适应度“变坏”的点，扩大了粒子群的多样性，增强了求解全局最 优解的能力，提高了寻找全局最优解的速度和收敛精度。 6 武汉理工大学硕士学位论文 第2 章粒子群优化算法 2 1 粒子群优化算法简介 粒子群优化算法是由e b e r h a r t 和k e n n e 等于1 9 9 5 年开发的一种基于群体智 能方法的演化计算技术【5 6 l ，是演化计算领域中的一个新的分支，其思想源于鸟 群群体运动行为的研究，它用无质量无体积的粒子作为个体，并为每个粒子规 定简单的行为规则，从而使整个粒子群呈现出复杂的特性，可用来求解复杂的 优化问题。 自粒子群优化算法提出以后，因其概念简明、实现方便，成为一个研究热 点，已被“国际演化计算会议”( i e e ei n t e r n a t i o n a lc o n f e r e n c e so ne v o l u t i o n a r y c o m p u t a t i o n ，c e c ) 列为一个讨论的专题1 6 j 。 2 1 1 粒子群优化算法的基本思想 自然界中一些生物的行为呈现群体特征，可以用简单的几条规则将这种群 体行为( s w a r m b e h a v i o r ) 在计算机中建模，实际上就是在计算机中用简单的几条 规则来建立个体的运动模型，但这个群体的行为可能很复杂。例如，r e y n o l d s 使用了下列三个规则作为简单的行为规则【1 1 j ： ( 1 ) 向背离最近的同伴的方向运动； ( 2 ) 向目的运动； ( 3 ) 向群体的中心运动。 这就是著名的b o i d ( b i r d o l d ) 模型，在这个群体中每个个体的运动都遵循这 三条规则，通过这个模型来模拟整个群体的运动。粒子群优化算法的基本概念 也是如此，每个粒子( p a r t i c l e ) 的运动用几条规则来描述。因此，粒子群优化算 法简单、容易实现，越来越多地引起人们的注意。 我们可以设想这样一个场景：一群鸟在随机搜寻食物，在这个区域里只有 一块食物，所有的鸟都不知道食物在哪里，但是它们知道当前的位置离食物还 有多远。那么找到食物的最优策略是什么呢? 最简单有效的办法就是搜寻目前离 食物最近的鸟的周围区域【1 2 l 。研究者还发现鸟群在飞行过程中经常会突然改变 7 武汉理工大学硕士学位论文 方向、散开、聚集，其行为不可预测，但其整体总保持一致性，个体与个体间 也保持着最适宜的距离。通过对类似生物群体的行为的研究，发现生物群体中 存在着种社会信息共享机制，它为群体的进化提供了一种优势，这也是粒子 群优化算法形成的基础【6 , 1 2 。 粒子群优化算法就是从这种生物种群行为特性中得到启发并用于求解优化 问题。在粒子群优化算法中，每个优化问题的潜在解都可以想象成d 维搜索空 间上的一个点，我们称之为“粒子”( p a r t i c l e ) 。粒子在搜索空间中以一定的速度飞 行，这个速度根据它本身的飞行经验和同伴的飞行经验来动态调整1 6 j 。所有的 粒子都有一个被目标函数决定的适应度值( f i t n e s sv a l u e ) ，并且知道自己到目前 为止发现的最好位置( p a r t i c l eb e s t ，记为p b e s t x i ) 和当前的位置( p a r t x i ) ，这个可 以看作是粒子自己的飞行经验。除此之外，每个粒子还知道到目前为止整个群 体中所有粒子发现的最好位置( g l o b a lb e s t ，记为g b e s t x ，g b e s t x 是在p b e s t x i 中的最好值) ，这个可以看作是粒子的同伴的经验【5 , 6 , 1 2 。每个粒子使用下列信息 改变自己的当前位置【5 】：1 当前位置( p a r t x i ) ；2 当前速度( p a r t v o , 3 当前位 置与自己最好位置( p b e s t x i ) 之间的距离；4 当前位置与群体最好位置( g b e s t x ) 之间的距离。优化搜索正是在由这样一群随机初始化形成的粒子而组成的一个 种群中，以迭代的方式进行的。 2 1 2 粒子群优化算法的数学描述、特点及应用 1 粒子群优化算法的数学描述 在粒子群优化算法中，每个优化问题的潜在解是搜索空间中的一只“鸟”， 称之为“粒子”，即每个粒子的位置就是一个潜在的解1 5 , 6 1 。粒子群优化算法随机 初始化一群粒子的位置和速度，第i 个粒子在d 维空间的位置、速度分别表示 为： p a r t x i - 1 ，毛2 ，) p a r t v _ f ；“，屹2 ，) 其中i = 1 ，2 ，n ，n 表示粒子群种群规模，即粒子群中粒子个数，一般初 始( 化为1 0 - 4 0 ) ，d 为实际解决问题中维数，即实际问题自变量个数；然后通 过迭代找到最优解，在每一次迭代中，计算每个粒子的适应度，每个粒子通过 跟踪两个“极值，来更新自己【5 】：一个就是粒子本身所找到的最优解，叫做个体 8 武汉理工大学硕士学位论文 极值p b e s t e ；另一个极值是整个种群目前找到的最优解，叫做全局极值g b e s t f 。 计算每个粒子的适应度( 适应度函数一般由实际问题中被优化的函数决 定) ，根据适应度，更新每个粒子的个体最优值点p b e s t x ( p 。，p 2 ，p d ) 和 全局最优值点g b e s t x 。这里的是否“最优”是由具体的优化问题决定，若该问题 求最大值，则粒子适应度越大为最优；反之，若该问题求最小值，则粒子适应 度越小为最优。 假设优化问题求最小值，p a r t f i 为当前粒子的适应度，p b e s t f i 为该粒子个体 最优点的适应度，g b e s t f 为全局粒子最优点的适应度。以求最小适应度为例说 明优化方法，若p a r t f i p b e s t f i ，p b e s t f i = p a r t f i ，p b e s t x i = p a r t x i ；否则，p b e s t f i 、 p b e s t x i 不变；若p a r t f i g b e s t f ，g b e s t f = p a r t f i ，g b e s t x = p a r t x i ；否则，g b e s t f 、 g b e s t x 不变。 粒子根据以下公式( 2 1 ) 、( 2 2 ) 来更新其速度和位置： p a r t 巧( t + 1 ) = p a r t 巧 + c l 掌r a n d 0 * ( p b e s o i j 一朋嘞 + c 2 事r a n d 0 木( g b e s q 一即慨( f ) ) p 叫 p a r t x 玎o + 1 ) tp a r t x 豇o ) + p a r t v l jo + 1 ) ( 2 2 ) 式中i 为第i 个粒子，i = l ，2 ，n ，j 为实际问题的维数，j = l ，2 ，d ， c ，= c ，= 2 ，t 为迭代次数，r a n d o 为均匀分布在0 - 一1 之间的随机数。公式( 2 1 ) 主 要通过三部分来计算粒子i 新的速度：( 1 ) 粒子前一时刻的速度；( 2 ) 粒子当前位 置与自己最好位置之间的距离；( 3 ) 粒子当前位置与群体最好位置之间的距离。 粒子i 通过公式( 2 2 ) 计算新位置的坐标。通过式( 2 1 ) 、( 2 2 ) ，粒子决定下一步 的运动位置。在图2 - 1 中，以两维空间为例描述了粒子根据公式( 2 1 ) 、( 2 2 ) 从 位置到移动的原理。如果从社会学的角度来看，公式( 2 1 ) 的第一部分称为记忆 项，表示上次速度大小和方向的影响；公式的第二部分称为自身认知项，是从 当前点指向此粒子自身最好点的一个矢量，表示粒子的动作来源于自己经验的 部分；公式的第三部分称为群体认知项，是一个从当前点指向种群最好点的一 个矢量，反映了粒子闯的协同合作和知识的共享。粒子就是通过自己的经验和 同伴中最好的经验来决定下一步的运动，这与人类的决策何其相似，人们通常 也是通过综合自身已有的信息和从外界得到的信息来做出决策的。 9 武汉理工大学硕士学位论文 图2 1粒子移动原理 迭代终止条件根据具体问题一般选为最大迭代次数或( 和) 满足规定的误差 标准为止f 5 】。 2 粒子群优化算法的特点 粒子群优化算法的具有如下优点 6 a 3 , 1 q ： ( 1 ) 搜索过程是从一组解迭代到另一组解，采用同时处理群体中多个个体的 方法，具有本质的并行性； ( 2 ) 采用实数进行编码，直接在问题域上进行处理，无需转换，因此算法简 单，易于实现； ( 3 ) 在优化过程中，每个粒子通过自身经验与群体经验进行更新，具有学习 的功能； ( 4 ) 是解决连续型优化问题的一个强有力的工具。 粒子群优化算法的缺点是【1 5 , 1 3 , 1 5 1 ： ( 1 ) 在处理高维的复杂问题时，算法易陷入局部最优； ( 2 ) 当问题的规模较大时，算法收敛的速度较慢，且精度不高。 3 粒子群优化算法的应用 粒子群优化算法简洁，易于实现，不需要设置很多的参数，也不需要梯度 信息。粒子群优化算法是非线性连续优化问题、组合优化问题和混合整数非线 性优化问题的有效优化工具，目前已经广泛应用于函数优化、神经网络训练、 实践工程等应用领圳6 】。 ( 1 ) 函数优化 实际的工程问题很多都可转换为函数优化问题进行求解，函数优化已经有 1 0 武汉理工大学硕士学位论文 一些成熟的解决方法，如：遗传算法。但对于超高维、多局部极值的复杂函数 而言，遗传算法在优化的收敛速度和精度上难以达到期望的要求。a n g e l i n e 通 过大量的实验研究发现，粒子群优化算法在解决一些典型的函数优化问题时， 能够取得比遗传算法更好的优化结果【1 6 l 。这就说明粒子群优化算法在解决实际 问题时同样具有很好的应用前景。s h i 与e b e r h a r t 的实验证明，对大多数的非线 性b e n c h m a r k 函数，粒子群优化算法在优化速度和精度上均较遗传算法有一定 的改善【1 7 1 。 ( 2 ) 神经网络训练 工业、经济、医疗等领域的许多实际问题如质量控制、破产预测、图像识 别、医疗诊断等都可以转换为模式分类问题求解。神经网络自学习、自组织、 容错以及模拟非线性关系的能力使其特别适合于解决上述复杂的实际应用问 题。研究表明，粒子群优化算法是一种很有潜力的神经网络训练算法，粒子群 优化算法保留了基于种群的、并行的全局搜索策略，其采用的速度一位移模型 操作简单，避免了复杂的遗传操作【6 , 1 8 l 。粒子群优化算法用于神经网络的训练中， 主要包含3 个方面：连接权重、网络拓扑结构及传递函数、学习算法。每个粒 子包含神经网络的所有参数，通过迭代来优化这些参数，从而达到训练的目的 【1 9 。2 0 l o ( 3 ) 组合优化 许多组合优化问题中存在序结构如何表达，以及约束条件如何处理等问题， 离散二进制版粒子群优化算法不能完全适用。研究者们根据问题的不同，提出 了相应问题的粒子表达方式，或通过重新定义速度更新公式中的“+ ”和”算子 来解决不同问题。目前，已提出了多种解决t s p 和v r p 等组合优化问题同。 “) 粒子群优化算法的工程应用 日本的f u j i 电力公司的研究人员将电力企业著名的r p v c ( r e a c t i v ep o w e r a n dv o l t a g ec o n t r 0 1 ) i n 题简化为函数优化问题，并使用改进的粒子群优化算法进 行优化求解【2 1 】，与传统方法如专家系统、敏感性分析相比，实验产生的结果证 明了粒子群优化算法在解决该问题的优势。 通过训练神经网络，粒子群优化算法成功应用到对医学中震颤行为的分析 【2 2 1 。经粒子群优化算法训练的人工神经网络已经能够区分人的本能震颤和病理 性震颤。 此外，将粒子群优化算法与神经网络算法相结合，训练神经网络已用于对 1 1 武汉理工大学硕士学位论文 电动汽车燃料电池组实时充电情况的模拟，实验证明相对于1 9 9 6 年e b e r h a r t ， s i m p s o n 和b o b b i n s 的模拟方法，上述方法的模拟精确程度明显提高。 2 2 粒子群优化算法的设计与实现 2 2 1 粒子群优化算法流程及其流程图 粒子群优化算法的步骤如下所示： ( 1 ) 设定粒子的个数n ，初始化每个粒子的速度p a r t v i 、位置p a h x i ，迭代次 数t = 0 ，最大迭代次数i t e r m a x ； ( 2 ) 初始化个体极值点p b e s t x i 、全局极值点g b e s t x ，个体极值p b e s t e ，全局 极值g b e s t f ； ( 3 ) 根据实际问题计算每个粒子的适应度p a r t r ； ( 4 ) 通过比较得出个体极值p b e s t f i ，全局极值g b e s t f ； 全局极值点g b e s t x 。以求最小值为例： 若p a r t f i p b e s t e ，p b e s t e = p a r t f i