（系统分析与集成专业论文）粒子群优化算法的研究及改进.pdf

摘要 粒子群算法是一种基于种群搜索策略的自适应随机优化算法，随着计算机 的广泛应用、仿生技术的发展，它己成为求解优化问题的重要工具。粒子群算 法简单易实现、精度高、收敛快，从它提出时就引起了广大学者的研究兴趣。 p s o 算法以其灵活稳定，具有分布式控制和自学习能力的优势，无论是从理论 研究还是应用研究的角度来看，对粒子群算法的研究都具有重要的学术意义和 现实价值。 通过粒子的社会行为分析，本文提出了借鉴前一个粒子飞行经验的改进粒 子群算法，并将其应用于求解无约束优化问题。在总结p s o 算法改进的过程中， 发现对算法融合方面的研究具有积极的意义，提出了与死亡罚函数法相结合的 混合p s o 算法，并将改进的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 ni sa l la d a p t i v es t o c h a s t i co p t i m i z a t i o na l g o r i t h m t h a tb a s e do nt h ep o p u l a t i o ns e a r c hs t r a t e g y w i t ht h ew i d e l yu s eo fc o m p u t e ra n dt h e d e v e l o p m e n to fb i o n i c s ，p s oi sm o s ti m p o r t a n tf o rs o l v i n go p t i m i z a t i o np r o b l e m s t h ep s oa l g o r i t h mh a ss i m p l ec o n c e p t ，h i 曲p r e c i s i o na n df a s tc o n v e r g e n c e m a n y s c h o l a r ss t u d yo ni tf r o mt h ep s oa l g o r i t h mh a v i n gb e e np u tf o r w a r d c o n s i d e r i n g t h ea d v a n t a g eo ff l e x i b i l i t y , s t a b i l i t y , d i s t r i b u t e dc o n t r o la n ds e l f - l e a n i n g ，p s o a l g o r i t h mr e s e a r c hh a si m p o r t a n ts c i e n c em e a n i n ga n dp r a c t i c a lv a l u ee i t h e rf r o mt h e v i e wo f t h e o r e t i c a lo ra p p l i e dr e s e a r c h t h r o u g ht h er e s e a r c ho ns o c i e t yb e h a v i o ra n a l y s i so fp a r t i c l e a ni m p r o v e dp s o a l g o r i t h mw a sp r o p o s e db a s e do naf r o n tp a r t i c l e sf l y i n ge x p e r i e n c e ，a n da p p l i e dt o s o l v et h en o nc o n s t r a i n e do p t i m i z a t i o np r o b l e m i nt h ep r o c e s so fs u m m a r yp s o a l g o r i t h mi m p r o v e m e n t ，t h er e s e a r c hf i n d i n g t h a t a l g o r i t h mf u s i o nh a sa c t i v e s i g n i f i c a n c e d e a t hp e n a l t ym i x e dw i mt h ep s ow i mc o n s t r i c t i o n f a c t o rw a s p r o p o s e d t os o l v et h ec o n s t r a i n e do p t i m i z a t i o n t h ev a l i d i t yh a sb e e nv e r i f i e db yt h e s t a n d a r dt e s t i n gf u n c t i o n t h ef i r s tp a r ti n t r o d u c e st h er e s e a r c hb a s eo f p a r t i c l es w a l t l lo p t i m i z a t i o nb r i e f l y , a tt h es e c o n dp a r t ，i n s t r u c t i o nw a sg i v e nf r o mt h eb a s i ct h e o r y , p a r a m e t e r sc h o o s e a n dt o p o l o g ys t r u c t u r e i m p r o v e dp s oa l g o r i t h m sw e r el i s t e db yt h ep u r p o s eo f i m p r o v e m e n t t h ee n g i n e e r i n ga p p l i c a t i o n so fp s oa l g o r i t h mw a si n t r o d u c e d t h e t l l i r dp a r tg i v e st h ei m p r o v e dp s oa n df u n c t i o nt e s t i tp r o v e st h ea v a i l a b i l i t yo ft h e a l g o r i t h m k e yw o r d s ：p a r t i c l e s w a r mo p t i m i z a t i o n , c o n s t r i c t i o nf a c t o r ，d e a t hp e n a l t y , o p t i m i z a t i o np r o b l e m i i 学位论文独创性声明 本人郑重声明： 1 、坚持以“求实、创新”的科学精神从事研究工作。 2 、本论文是我个人在导师指导下进行的研究工作和取得的研究成果。 3 、本论文中除引文外，所有实验、数据和有关材料均是真实的。 4 、本论文中除引文和致谢的内容外，不包含其他人或其它机构已经发表或 撰写过的研究成果。 5 、其他同志对本研究所做的贡献均已在论文中作了声明并表示了谢意。 作者签名：丛叁短 日期：2 塑墼量也 学位论文使用授权声明 本人完全了解南京信息工程大学有关保留、使用学位论文的规定，学校有 权保留学位论文并向国家主管部门或其指定机构送交论文的电子版和纸质版： 有权将学位论文用于非赢利目的的少量复制并允许论文进入学校图书馆被查 阅：有权将学位论文的内容编入有关数据库进行检索：有权将学位论文的标题 和摘要汇编出版。保密的学位论文在解密后适用本规定。 作者签名；丝垒短 日期：2 塑堕墨 1 1 研究背景及意义 第一章绪论 优化问题自古以来就被人们不断的探讨与研究。随着近代计算机的日益广泛应用，优 化问题的求解技术也随之发展，优化理论与算法的迅速发展形成了一门新的学科，已经出 现了线性规划、非线性规划、整数规划、几何规划、动态规划、随机规划等多个分支。这 些优化技术在工程领域有着广泛的推广和应用，如系统控制、人工智能、生产调度、布局 优化等。但是现实中有许多工程问题呈现复杂化、多极化、非线性、强约束等特点。这就 驱使人们去寻找高效的优化技术，人们从生命现象中得到启示，发明了许多智能的优化方 法来解决复杂优化问题【l j 。例如遗传算法、人工免疫系统、人工神经网络、蚁群算法、粒 子群优化算法、群落选址算法等。这类借鉴模拟了生命系统的行为、功能和特性的科学计 算方法可以称之为人工生命计算( a r t i f i c i a ll i f ec o m p u t a t i o n ) 。 粒子群优化( 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 d y 博士和从事计算智能研究f i | 勺e b e r h a r t 博士1 2 1 受到人工 生命的研究结果启发，于1 9 9 5 年提出的一种基于群智能( s w a r mi m e l l i g e n e e ) 方法的进化 计算技术( e v o l u t i o n a r yc o m p u t a t i o n ) 。粒子群优化算法是群智能方法中用于解决全局优化 问题的一种有效方法p j ，目前已被列为“国际进化计算会议”的一个讨论专题。由于p s o 算法 是一种基于群智能方法的演化计算技术，搜索轨道有多条，显示出良好的并行性。与基于 达尔文“适者生存，优胜劣汰”进化思想的遗传算法不同的是，粒子群优化算法是通过个体 之间的协作米寻找最优解的。粒子群优化算法的最优解搜索主要依赖于其“记忆”能力和粒 子间的信息共享机制。与其它进化计算技术相比。p s o 的优势在于简单容易实现同时又有 深刻的智能背景，既适合科学研究，又特别适合工程应用。因此p s o 一提出，立刻引起了 进化计算等领域的学者们的广泛关注，并在短短的几年时间里出现了大量的研究成果。目 前，已提出了多种p s o 的改进算法，并且p s o 已广泛应用_ = _ 函数优化、神经网络训练、模 式分类、模糊系统控制以及其他的应用领域。 粒子群优化算法自提出以来，已经成为一种重要的优化工具并成功地应用于各个领域。 与其他全局优化算法一样，p s o 算法在实际应用中也有一些不尽如人意的问题。其中最主 要的是它易产生早熟收敛、收敛速度慢、全局寻优能力差等。由于p s o 算法的发展历史尚 短，数学理论基础相对薄弱，在应用推广上都还存在一些问题，有待解决。 1 首先，p s o 在求解高维复杂优化问题时，往往会遇到早熟收敛的问题。这些早熟收敛 点，有可能是局部最优点，也可能是局部最优点邻域内的一个点。这就是说，早熟收敛并 不能保证算法收敛到局部最优点。 其次，p s o 算法的收敛速度也比较缓慢。实际上对p s o 的研究发现，p s o 早期收敛速 度较快，但到寻优的后期，寻优结果改进则不理想。这主要归因子算法收敛到局部极值， 缺乏有效的机制使算法跳出局部极值。 此外，大多数p s o 算法解决的仍是无约束优化问题。而在科学研究和工程实践中，许 多优化问题都带有一定的约束条件。针对上述问题，本文展开了研究，着重从p s o 算法的 应用角度出发，力求找出简单有效的求解方法，并对粒子群算法做出有意义的改进。 1 _ 2 国内外研究现状 粒子群优化算法本身具有概念简单和易于实现的优点，在短短几年中得到很大发展， 迅速引起了国际上相关领域众多学者的广泛关注和研究，并在许多领域取得了成功的应用。 目前，粒子群优化算法的研究大致可分为以下几个领域：算法的理论研究、算法的改进研 究以及算法的应用研究。 ( 1 ) 粒子群优化算法的理论研究 研究一种算法首先要从它的原理进行研究，研究粒子群算法就要首先研究粒子之间是 如何通过相互作用与运动而最终达到全局优化的。与生物社会特性基础相比，p s o 算法的 数学基础还相对薄弱，缺乏深刻且具有普遍意义的理论分析，因此对p s o 算法数学基础的 研究非常重要。在p s o 算法的理论研究方面，k e n n e d y 及s u g a n t h a n 分别从邻域算子角度分 析t p s o 算法性能，c l e r c 等给出y p s o 算法比较完整的理论分析。文献【4 利用微分方程和 差分方程为工具对单个粒子的运动轨迹进行研究发现：单个粒子其轨迹是各种正弦波的随 机的叠加组合。有部分研究者对算法的收敛性进行了分析，其中研究比较多的集中在一些 简化条件下的结果，采用的主要工具是动态系统理论，其它还有采用集合论的方法来研究 此问题pj 。更多的研究者致力于研究算法的结构和性能改善，包括参数分析，拓扑结构， 粒子多样性保持，算法融合和性能比较等。 ( 2 ) 粒子群优化算法的改进研究 自k e n n e d y 和e b e r h a r t 提出p s o 算法，吸引了不少研究者。p s o 算法的改进研究是 p s o 算法研究的重要分支，关于p s o 算法改进的内容十分庞大。p s o 算法的改进来自于它 在实际应用中出现的些不完善的问题，其中最主要的是它容易产生早熟收敛、局部寻优 2 能力较差等。实际上这些缺点也是几乎所有随机算法的弊病。但是梯度法、爬山法、直接 搜索法、模拟退火算法等一些优化算法却具有很强的局部搜索能力，而另一些含有问题域 的相关知识的启发式算法的运行效率也比较高。可以说，大多数优化方法的全局搜索能力 和局部搜索能力单靠一种算法往往无法得到有效利用与平衡，从而影响了算法的求解精度 和效率。因此，如何合理结合不同算法的优点来构造新算法，对于实时性和优化性同样重 要的工程领域，具有很强的吸引力。自然地，人们想到了混合两种算法或者多种算法在一 个模型当中，尽量发挥各个算法的优点，从而形成了一个研究混合算法的方向。因此，在 p s o 算法搜索过程中融合其他优化方法的思想，构成混合p s o 算法，成为p s o 算法改进 的一个重要的思路。 s h i 等引入惯性权重形成了目前的p s o 基本算法并对p s o 模型中参数选择做了详尽 的阐述。c l e f t 提出压缩因子p s o 算法，提高了算法的收敛速度。a n g e l i n e 将选择算子引 入p s o 中，将每次迭代后的较好粒子替换较差的粒子，以保证每次迭代的粒子群都具有较 好的性能，这种算法对某些单峰函数效果良好【6 】。文献 7 】在粒子群每次迭代后，按概率在 粒子间交换各维，通过交叉操作米更新粒子群算法对某些多峰函数效果较好。h i g a s h i 等 人分别提出了自己的变异算法，基本思路都是希望通过引入变异算子来跳出局部极值点， 从而提高算法的全局搜索能力，得到较高的搜索成功率j 。高鹰等人则引入免疫机制的概 念，提高粒子群的多样性和自我调节能力，以增强粒子的全局搜索能力 9 1 。b a s k a r 等人提 出了自己的协同算法，通过使用多群粒子分别优化问题的不同维来对基本算法进行改进尝 试【1 0 l 。 混合p s o 是改进研究的热点，其发展非常迅速。除了将进化算法中的选择、交叉以及 变异算子引入p s o 算法外，还有很多与其他经典优化技术相结合的混合p s o 算法。 孙俊”等给出的量子p s o ，是一种不确定的搜索算法。此算法是标准p s o 在量子空间 的扩展，其性能优于标准p s o 算法，但用在优化网络权重时，优势并不明显。 n o e l 等人提出利用梯度信息的混合p s o 算法l 】”，其主要思想是利用梯度信息使算法搜 索到局部最优点，而p s o 随机的本质使算法能够逃离局部最优点，结合两者从而使算法完 成全局寻优。王俊伟i l m 等通过引入梯度信息来影响粒子速度的更新，构造了一种带有梯度 加速的p s o 算法。梯度信息的加入使粒子的移动更具针对性，进一步提高了p s o 算法的 收敛速度，但也会增加算法对问题的依赖性，特别是有些梯度信息极易将粒子引入局部极 值。 王华秋【】4j 等提出模拟退火p s o ，算法针对p s o 容易陷入局部极小，将模拟退火结合并 行粒子群算法的快速寻优能力。粒子群的追踪过程在各个相对独立的并行进程内完成，从 而保证各个种群的多样性，并且在各个进程引入了模拟退火跳出粒子群局部极值。 此外还有耗散p s o 、自适应p s o 等混合改进算法。相对于标准粒子群算法，大多数的 混合p s o 算法在性能上都有不同程度的提高，但是在工程应用方面，如何合理的选择参数， 使得算法既能避免陷入局部最优又能准确快速的收敛，同时尽可能控制算法的实现复杂度， 对工程实践有着重要的意义。 ( 3 ) 粒子群优化算法的应用研究 p s o 最早应用于非线性连续函数的优化和神经元网络的训练【l ”】，后来也被用于解决 约束优化问题，e b e r h a r t 和k e n n e d y 又提出y p s o 的离散二进制版本【】”，用于解决组合优化 问题。e b e r h a r t 用p s o 来分析人类的帕金森综合症等颤抖类疾病。y o s h i d a 等通过p s o 对各种 离散的连续变量的优化，达到控制核电机组输出稳定电压的目的。国内也有越来越多的学 者关注p s o 的应用，但是相对来说，国内的研究还在起步阶段，大多是对算法综合和算法 的实际工程应用方面的研究。李爱国【1 8 】、周驰【、杨维口、谢晓锋2 1 等人对粒子群算法的 研究进行了综述，张丽平【2 2 】、高鹰刚2 ”、柯品、吕振肃口5 1 等人在粒子群算法的改进方面 做了一定的研究工作，在神经网络训练“1 、平面选址【2 7 】、函数优化1 2 ”、多目标优化以及 旅行商p ”、车辆路径优化【3 2 】等领域，国内学者也展开了相关研究。 4 1 3 本文的研究内容及取得成果 本文主要对粒子群优化算法进行研究，研究内容与取得成果归纳如下： 一、对粒子群算法的机制方面进行研究，包括算法的理论分析，社会行为分析，收敛 性分析。 二、侧重于介绍粒子群算法本身的改进，重点讨论惯性权重p s o 算法和带压缩因子的 p s o 算法，并对这两种算法的参数设置进行分析。 三、介绍粒子群算法的几种代表性的改进方法，侧重从它们的改进目的进行分类介绍。 四、通过对粒子群算法的研究，希望找到一种简单高效的改进算法。根据雁队飞行的 特点，使粒子根据前一个粒子的经验调整自己的飞行，提出了改进的压缩因子粒子群算法 模型，并用来解决无约束优化问题。随着问题规模和复杂度的增加，单一的优化算法往往 难以取得理想的优化结果。因此，算法融台的p s o 算法是很有潜力的一个研究方向。本文 采用死亡罚函数与压缩因子粒子群算法相结合，使得改进后算法的收敛速度快，精确度高， 通过测试函数试验证明了本文提出的改进算法的有效性。 2 1 计算智能 第二章研究基础 信息科学和生命科学的相互交叉、相互渗透以及相互促进是现代科学技术发展的一个 显著特点，生物信息学就是两者结台而形成的新的交叉科学，计算智能则是另一个有说服 力的示侧。它是从模拟自然界生物体系和人类智能现象发展而来，用计算机模拟和再现人 类的某些智能行为。计算智能涉及神经计算、模糊计算、进化计算和人工生命等领域，它 的研究和发展正反映了当代科学技术多学科交叉与集成的重要发展趋势。 第一个关于计算智能( c o m p u 协t i o n a li n t e l l i g e n c e ，c i ) 的定义是由贝兹德克0 3 e z d e k ) 于 1 9 9 2 年在a p p r o x i m a t er e a s o n i n g 学报上提出的。他认为，从严格意义上讲，计算智能 取决于制造者( m a n u f a c t u r e r s ) 提供的数值数据，而不依赖于知识；另一方面，人工智能则应 用知识精品( k n o w l e d g et i d b i t s ) 。1 9 9 4 年6 月底到7 月初，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 ni n t e l l i g e n c e ) 。这次会 议首次将进化计算、人工神经网络和模糊系统这三个领域合并在一起，形成了“计算智能” 这个统一的技术范畴，计算智能的研究由此被提升到一个前所未有的高度。计算智能的提 出对促进人工智能领域中各种理论和方法的集成，对推动人工智能的发展起到了非常重要 的作用。当一个系统仅处理底层数据，具有模式识别的功能，并且不使用人工智能意义中 的知识，那么这个系统就是计算智能系统。计算智能，也可以说是借鉴仿生学的思想，基 于生物体系的生物进化、细胞免疫，神经网络等机制，用数学语言抽象描述的计算方法， 是基于数值计算和结构演化的智能。计算智能展示系统适应和处理新情况的能力，使系统 具有推理的属性，如泛化、发现、联想和抽象。计算智能具有以下一些优点： 1 、自组织、自适应、自学习性。这种特性使得无需事先研究问题的全部结构，使算法 设计变得简单。应用这种通用计算能力，我们可以求解那些复杂的非结构化问题。 2 、并行性。进化计算中，个体都有自己的运动轨迹，群体就表现出并行性。在计算机 广泛应用的今天，计算智能的并行性有着非常重要的意义，它使计算的效率得以提高。 3 、记忆的分布性。计算智能在信息处理上是并行的，但是在信息的存储和表达上是分 布的。这样使得在求解复杂的系统优化问题时具有鲁棒性。 计算智能正处于迅速发展阶段，引起了诸多领域专家学者的关注，成为跨学科的研究 热点。近年来，计算智能方法的麻用研究呈互相融合的趋势，研究和实践表明，它们之间 6 的相互补充可增强彼此的能力，从而获得更有力的表示和解决实际问题的能力。近十多年 来，计算智能应用领域越来越广，在工业控制、模式识别、知识自动获取等许多领域都取 得了激动人心的研究成果和应用。计算智能技术将不断地从生物智能中得到启示，探讨思 想更先进、功能更强大、能解决更复杂系统的整体智能行为的计算智能技术，使新型计算 智能系统逐步实现生物智能的目标。探索新的算法、推进算法之间的融合及加强计算智能 在工程领域的实际应用将成为智能计算重要的发展方向。本文将对一种较新的计算智能方 法一粒子群优化算法作主要的研究。 2 2 人工生命 2 0 世纪4 0 年代和5 0 年代。冯诺依曼就试图用计算的方法揭示生命最本质的东西， 试图描述生命繁殖的逻辑形式，提出了细胞自动机( c e l l u l a r a u t o m a t a c a ) 的设想，并且证 明了确实有一种能够自我繁殖的元胞自动机的存在，虽然它复杂到了当时的计算机都不能 模拟的程度。同时1 9 5 2 年图灵发表了一篇论形态发生的数学论文，证明了相对简单的化学 过程可以从均质组织产生新的秩序，从而提出了人工生命的一些萌芽思想。1 9 7 0 年剑桥大 学的j o h nc o n w a y 编制了一个名为“生命”的游戏程序，该程序由几条简单规则控制，这 几条简单规则的组合可以使细胞自动机产生无法预测的延伸、变形和停止等复杂的模式。 1 9 8 7 年，美国s a n t a f e i n s t i t u t e 的教授c h r i s t o p h e r l a n g t o n 认为，为了能够进一步探索生命 的规律，应当有一门新的科学来详细的研究这些问题，他在l o s a l a m o sn a t i o n a ll a b o r a t o r y 召开的“生成以及模拟生命系统的国际会议”上提出这个新兴的学科“人工生命” ( a r t i f i c i a ll i f e ，a l i a ) ”。此后，人工生命研究进入到一个蓬勃发展的新时期。 l a n g t o n 定，义人工生命是研究人工系统来模拟自然生命系统行为特性的学科( a r t i f i c i a l l i f ei st h es t u d yo fm a n - m a d es y s t e m st h a te x h i b i tb e h a v i o r sc h a r a c t e r i s t i co fn a t u r a ll i v i n g s y s t e m s ) ”。这表明，人工生命研究的共同兴趣在于生命系统行为特性的仿真。人工生命的 研究是基于由下而上的综合方法，一般包含认识和实践两个阶段：认识阶段，抽象地概括 自然生命系统的逻辑原则；实践阶段，通过综合的方法在其它介质上实现这些原则，来构 建人工系统。 人工生命是指具有生命特征的人造系统。在信息科学技术领域中的人工生命，是以计 算机为研究工具，模拟自然界的生命现象，生成表现自然生命系统行为特点的仿真系统。 人工生命作为- - f j 新兴的交叉科学，其研究领域涵盖了计算机科学、生物学、自动控制、 系统科学、机器人科学、物理学、化学、经济学、哲学等多种学科。人工生命研究的重点 是人造系统的模型生成方法、关键算法和实现技术。随着人工生命这门新兴交叉学科的诞 生，人工生命研究得到了很大的发展。许多研究者提出了各种基于人工生命的智能算法【“】。 2 3 进化计算 进化计算( e v o l u t i o nc o m p u t i n g 。e c ) 是一种模拟生物进化过程、机制来求解问题的自组 织、自适应智能计算技术，也称为演化计算。它仿效生物学中进化和遗传的过程，遵从“生 存竞争、优胜劣态”的进化规则，从一组随机生成的初始可行群体出发，借助复制、交换( 重 组) 、突变等遗传操作，逐步逼近所研究问题的最优解。从实质而言，进化计算是一种具有 自适应调节功能的搜索寻优技术。进化计算一般包括遗传算法、遗传规划、进化策略、进 化规划4 种典型方法。目前这类算法己被广泛应用于机器学习、人工智能、自适应控制、 人工神经网络训练、图像处理等各个方面。 自然进化过程的本质就是一个学习与优化的过程，人类通过模拟这一过程，增强了解 决问题的能力。自然进化的结果是使生命体达到适应环境的最优结构和状态，得以在这个 环境中生存延续。在环境压力下进化的过程与人类发明的解析方法截然不同，在这里我们 不必明确地描述问题的全部特征，只需要根据自然法则来产生新的解，通过环境压力选择 适应环境的解或者个体。进化计算正是基于进化的这种过程而发展起来的一种求解问题的 通用方法，它采用简单的编码技术来表示复杂的结构，采用简单的操作和优胜劣汰的自然 选择来指导学习和确定搜索方向，成为复杂的解析方法的一种并行发展的新方法。因为进 化计算模拟生物群体的进化过程，所以一般都采用种群的搜索方式，这就隐含了并行处理 问题的可能，能够同时搜索解空间的多个区域。简单的操作、自然选择和个体自适应调整 使得进化计算具有不受搜索空间限制条件( 如可微、连续、单峰等) 的约束以及不需要其它 辅助信息的特点。 进化计算在2 0 世纪6 0 7 0 年代并未受到普遍的重视，到了8 0 年代，人们越来越认识 到传统优化方法的局限性，并且由于计算机速度的提高和并行计算机的普及，也由于进化 算法的不断发展及其在一些应用领域内取得的成功，进化计算表现出了良好的应用前景。 进化计算体现了优胜劣汰和自然选择的优化思想，为许多难以用传统数学方法和其他人工 智能技术解决的科学和工程问题提供了全新的思路。当前进化计算的研究内容十分广泛 如进化算法的设计与分析、进化计算的理论基础及其在各个领域中的应用等。 粒子群优化扎根于一些交叉学科，包括人工生命、进化计算和群论等。粒子群优化与 进化计算存在一些相似和相异之处。两者都是优化算法，都力图在自然特性的基础上模拟 8 个体种群的适应性。它们都采用概率变换规则通过搜索空间求解。这些就是粒子群优化和 进化计算的相似之处。 粒子群优化与进化计算也有几个重要的区别。粒子群优化具有记忆能力，而进化计算 没有。粒子保持自己及邻域的最好解，并根据它们调整粒子的位置。虽然这两种算法都建 立在适应性的基础上，但是粒子群优化的变化是通过向其他粒子学习而不是通过遗传来重 组和变异得到的。粒子群优化不用适应度函数而是由粒子间的社会交互作用来带动搜索过 程的。 2 4 群智能 自然界存在着许多让人类叹为观止的生物群体智能现象，蜂巢之精美、蚁群之有序、 雁阵之和谐，这些群居生物所体现的社会性和分布式智能实现模式给了人类很大的启发。 对于这些现象的一种解释是，群体中的每个个体都遵守一定的行为准则，当它们按照这些 准则相互作用时就会表现出上述的复杂行为。基于这一思想，c a r i gr e y n o l d s 在1 9 8 6 年提 出一个仿真生物群体行为的模型b o i d 【”j 。这是一个人工鸟群系统，其中每只人工鸟被称 为一个b o l d ，它有三种行为：分离、列队及聚集，并且能够感知周围一定范围内其它b o i d 的飞行信息。b o i d 根据该信息，结合其自身当前的飞行状态，并在那三条简单行为规则 的指导下做出下一步的飞行决策。r e y n o l d s 用计算机动画的形式展现了该系统的行为，每 个b o i d 能够在快相撞时自动分开，遇到障碍物分开后又重新合拢。这实际上就是一种群 体智能模型。 尽管这一模型出现在1 9 8 6 年，但是群体智能( s w a r mi n t e l l i g e n c e ，s i ) 概念正式提出的 时间并不长。一个显著的标志是1 9 9 9 年由牛津大学出版社出版的b n o b a e u a 和md o r i g o 等 人编写的一本专著群体智能：从自然到人工系统c s w a r mi n t e l l i g e n c e ：f r o mn a t u r a lt o a r t i f i c i a ls y s t e m ，) 。群体中存在众多智能个体，它们通过相互之间的简单合作表现出来的智 能行为即称为群体智能。群体指的是一组相互之间可以进行直接通讯或者间接通讯的主体， 它们能够合作进行分布式的问题求解。群体中简单个体是指具有简单能力( 如搬运、通信、 运动等) 的个体，这种能力可以用某一简单的功能函数来表示。简单合作是指个体只能与其 邻近的个体进行某种简单的协同动作，或通过改变环境间接的与其它个体之间进行简单通 信。群智能的主要特点有： ( 1 ) 协作性。协作是群智能最主要的特点，协作不但有行为上的支持而且还有信息上 的共享。而且个体之间可以通过非直接通信进行合作，这样的系统具有更好的可扩充性。 9 ( 2 ) 分布性。群体中个体的行为是成分散状态的，虽然个体的信息是局部的，但是通 过个体之间信息的交流使整个群体的信息为全局的，因此群体行为可以达到全局晟优。 ( 3 ) 鲁棒性。由于群体中个体的分布性，个体行为没有集中控制，所以不会因为某一 个或某几个个体的故障而影响整个问题的求解，这样系统就更具有鲁棒性。 ( 4 ) 自适应性和快速性。群体中个体的行为简单，但是这些行为对环境变化等都能做 出快速的反应，因此具有良好的适应性和快速性。 自2 0 世纪9 0 年代以来，群智能算法作为一种新兴的演化计算技术，已成为越来越多研 究者的关注焦点，它与人工生命，特别是进化策略以及遗传算法有着极为特殊的联系。国 内外群体智能的研究主要体现在：群体行为的模拟、群体智能计算和分布式问题解决装置 研究等方面。尽管它的理论还有待完善，但它已成为有别于传统人工智能中连接主义和符 号主义的新的智能描述方法，并已逐渐成为智能科学领域中一个独立的研究方向。 在国内，国家自然科学基金“十五”期间学科交叉类优先资助领域中认知科学及其信 息处理的研究内容就明确列出了群体智能的进化、自适应与现场认知。2 0 0 1 年3 月8 日在北 京召开的第六届全国人工智能联合会议暨“8 6 3 ”计划智能计算机主题学术会议上，戴汝为 院士特邀报告的主要内容就是群体智能的研究进展。从2 0 0 3 年至今，i e e e 每年都举办以群 智能为专题的学术研讨会。2 0 0 4 年，国家自然科学基金也开始资助有关群智能的相关研究 课题。群智能理论研究领域主要有两种算法：蚁群优化( a n tc o l o n yo p t i m i z a t i o n ，a c o ) 算 法和粒子群优化( 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 刍d o r i g o m 于1 9 9 1 年首次提出。粒子 群算法是受鸟群、鱼群等生物群落的防御、猎食行为中的搜索策略启发而形成的，由美国 学者k e n n e d y 和e b e r h a r t 在1 9 9 5 年提出。这些算法模式都是基于种群寻优的启发式随机搜索 算法，随着群体智能计算理论和应用研究的不断发展，研究者们尝试着将其用于各种工程 优化问题，并取得了意想不到的收获。多种研究表明，群集智能计算在离散求解空间和连 续求解空间中均表现出良好的搜索效果，并在组合优化问题中表现突出。 l o 第三章粒子群优化算法 粒子群优化算法是一类新兴的基于群智能的随机优化算法，同其它的进化算法相比， 其最具吸引力的特征是简单容易实现和更强的全局优化能力。因此，p s o 算法一提出，立 刻引起了演化计算等领域的学者们的广泛关注，并在短短的几年时间里出现大量的研究成 果，形成了一个研究热点，在函数优化、神经网络训练、工业系统优化和模糊系统控制等 领域得到了广泛的应用。大量实验结果表明了p s o 算法能解决遗传算法( g e n e t i ca l g o r i t h m ， c a ) 所能解决的各类优化问题，显示出p s o 算法确实是有力的优化工具。 3 1 基本p s o 算法和标准p s o 算法 3 1 1 算法原理 3 1 1 1 基本p $ o 算法原理 粒子群的概念来源于对鸟群觅食行为的研究。设想这样一个场景：一群鸟在随机搜寻 食物，在这个区域里只有一块食物，所有的鸟都不知道食物在哪里，但是它们知道当前的 位置离食物还有多远。它们通过搜寻目前离食物最近的鸟的周围区域米搜索到食物。 p s o 算法就从这种生物种群行为特性中得到启发并用于求解优化问题。在p s o 中，每 个优化问题的潜在解都可以想象成d 维搜索空间上的一个点，我们称之为“粒子”( p a r t i c l e ) 。 所有的粒子都有一个由被优化的函数所决定的适应值( f i m e s sv a l u e ) ，对于每个粒子，还有 一个速度决定他们飞翔的方向和距离，这个速度根据它本身的飞行经验和同伴的飞行经验 来动态调整，然后粒子们就追随当前的最优粒子在解空间中搜索。 s o 初始化为一群随机 粒子( 随机解) ，然后通过迭代找到最优解。在每一次迭代中，粒子通过跟踪两个“极值” 更新自己，一个是粒子本身所找到的最优解，称为个体极值巴，可以看作是粒子自己的飞 行经验：另一个极值是整个种群目前找到的最优解，该极值是全局极值岛，可以看作是粒 子的同伴的经验。另外，也可以不用整个种群而只用其中一部分为粒子的邻居，那么在所 有邻居中的极值就是局部极值。用整个种群的就是全局版p s o ，用一部分为邻居的就是局 部版p s o ，全局版收敛快，但有时会陷入局部最优，局部版收敛慢，但不容易陷入局部最 优。在实际应用中，可以先使用全局版p s o 搜索到解的大致位置，再用局部版p s o 进行 小范围搜索。 图3 1 粒子运动图 设在一个d 维目标搜索空间中，有m 个粒子组成一个种群，其中 五= ( 一，：，) ，i = 1 ，2 ，m 表示第i 个粒子当前的位置； = ( v 。，v ：，) 表示第i 个粒子当前的速度： 尸= ( p 订，p ，p ，d ) 表示第i 个粒子经历过的最好何置； 名= ( p 段：，p g d ) 表示整个粒子群迄今为止搜索到的最好位置。 k e n n e d y 和e b e r h a r t 最早提出的p s o 算法采用如下公式更新粒子的速度和位置【1 5 】： ( t + 1 ) = ( f ) + c ，( 名一x 。( f ) ) + c ：( 乞一x 。( r ) ) ( 3 1 ) x 。( t + 1 ) = x ，。( t ) + 圪( ，+ 1 ) ( 3 2 ) 其中表示第i 个粒子第d 维上的速度，t 表示第f 代，学习冈子q ，c ：为调节吃和岛 相对重要性的参数，它们分别调节向全局最好粒子和个体最好粒子方向飞行的最大步长， 若太小，则粒子可能远离目标区域，若太大则会导致突然向目标区域l i 去，或飞过目标区 域【36 | 。，r 2 o ，1 为均匀分布的随机数。为了控制粒子飞出边界，即控制速度和位置的值 在合理的区域内，粒子的每一维速度都会被钳位在【_ ，】之间，太人，粒子将 飞离最好解，太小将会陷入局部最优解。假设将搜索空间的第d 维定义为区间【- x 一，x 。 ， 则通常设定= 解一，o 1 足1 0 ，每一维都用相同的设置方法。从( 3 1 ) 式和( 3 - 2 ) 式可以看出，粒子的飞行方向由三部分决定，自己原有的速度、与自己最佳经历的距离 ( 匕一爿。( 州和与群体最佳经历的距离( 巳一x 。( f ) ) 。p s o 中没有许多需要凋1 ，的参数，下面 列 i ；这些参数以及经验设置： 粒子数：一般取2 0 4 0 ，对于大部分问题，较少的粒子就可以取得好的结果，但是对丁 1 2 比较难的问题，可以增加粒子数来取得好的结果。 粒子的长度：问题解的长度由优化问题决定，每一维可以设定不同的范围，如粒子的 范围为【- 5 ，5 】，则粒子的长度一般取1 0 。 。：粒子的最大速度，决定粒子在迭代中的晟大移动距离，通常设定为粒子的范围 宽度。 学习因子：最初令q = 气= 2 ，后来有研究者证明学习因子可以不取为固定值2 ，还有 文献对学习因子采用线性和非线性函数变换，学习因子的选取具有一定的问题依赖性。 迭代终止条件：达到最大迭代次数或者最小误差要求，可以根据具体问题来确定。 3 1 1 2 标准p s o 算法原理 对于公式( 3 1 ) ，如果只有第一项，粒子将以当前的速度和方向飞行，直至达到边界值。 这样想找到晟优解就非常困难了。如果没有这一项，粒子的速度仅取决于粒子的当前位置 和它的最好历史位置。当粒子正好处在群体屉好位置时，粒子将不再飞行，直到出现一个 新的最好点代替此粒子。这种情况下p s o 算法更多的显示的是局部搜索能力，为了改善基 本p s o 算法的收敛性能，y s h i 与r c e b e r h a r t 在1 9 9 8 年的i e e e 国际进化计算学术 会议上发表了题为am o d i f i e dp a r t i c l es w a r mo p t i m i z e r 的论文，首次在速度进化方程中引 入惯性权重p ”，即： ( t + 1 ) = w 0 ( f ) + q ( 己一以( f ) ) + 巳( 易一邑( f ) ) ( 3 - 3 ) 上式称为标准p s o 算法，式中w 称为惯性权重，因此，基本p s o 算法是惯性权重w ；1 的 特殊情况。惯性权重w 使微粒保持运动惯性，使其有扩展搜索空间的趋势，有能力探索新 的区域”“。如果w 较大，则前一速度屹( f ) 影响较大，能够搜索以前所未达到的区域，整个 算法的全局搜索能力加强；若w 较小，则前一速度的影响较小，主要在当前解附近搜索， 局部搜索能力强引入惯性权重w 可以清除基本p s o 算法对的需要，因为w 本身具有 维护全局和局部搜索能力的平衡的作用。从这个意义上看，可以将p ：固定为每维变量的 变化范围，只对w 进行调节。 对全局搜索，通常的好方法是在前期有较高的探索能力以得到合适的解，而在后期有 较高的开发能力以加快收敛速度。为此，可将w 设定为随着进化而线性减少，例如e h 0 9 到 0 4 等等。y s h i ；f i r c e b e r h a r t 的仿真实验结果也表明w 线性减少取得了较好的实验结 果。最初建议w 的取值范围为【o ，1 4 】，但是实验结果表明当w 取 0 8 ，1 2 】时，算法的收敛速 度更快，而当w ，1 2 时，算法则较多地陷入局部极值。在文献 3 8 中，惯性权重w 的计算 公式为： w ( f ) = w 嘴一生x ( 一) ( 3 - 4 ) m”( 。) 2 * 一a x i t e r 。【一一n ) 其中，m a x i t e r 为最大迭代次数，取最大权重系数”k = 0 9 ，最小权重系数。= o 4 ， 这样相当于将惯性权重w 看作迭代次数的函数，使w 从0 9 l - i j 0 4 线性减小，这是一般的线性 递减惯性权重方法，也有一些文献在惯性权重方面作改进，如非线性递减等。y s h i 和 e b e r h a r t j 丕提出了基于模糊系统的惯性权重的动态调整 3 9 1 和针对动态优化问题的随机惯性 权重等方法，这些改进算法虽然提高了收敛速度并且在单峰问题上取得了更高的性能，但 在解决多峰值