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

摘要 2 0 世纪以来，群体智能的诞生使优化领域得到了很大的发展。科学家们在 研究生物群体行为时得到了启示，提出了许多基于群体智能的算法，粒子群优 化算法是群智能算法中的一支新军，它是一种基于种群搜索策略的自适应随机 算法，被提出以来得到国内外众多学者们的关注。由于它算法简单、参数较少、 易于程序设计的特点，在工程实践中，已广泛的应用于函数优化、参数优化、 神经网络的训练、p i d 参数整定等领域。 本文从粒子群算法的基本原理、参数选择及应用等方面着手，通过对传统 的粒子群算法收敛较慢、易陷入局部最优的问题的研究，提出了一种基于参数 调整的改进方法，调整了传统的粒子群算法中的参数，使粒子寻优过程中速度 与方向的变异随着迭代次数的变化而变化，这样可以加强粒子在寻优过程晚期 的搜索能力，运用s c h a f f e r s 测试函数进行仿真，结果证明这种改进的方法是可 行和有效的。 在文章第一部分首先介绍了粒子群算法的研究现状。第二部分详细的论述 了算法的理论和应用研究。在第三部分中介绍了新提出的改进方法，并对其进 行函数测试。最后一部分是对粒子群算法在多目标优化问题中的应用研究。 关键词：计算智能，粒子群优化算法，参数调整，多目标优化 a b s t r a c t s i n c et h e2 0 t hc e n t u r y , t h eo p t i m i z a t i o nd o m a i nh a sd e v e l o p e dq u i c k l yd u et o t h eb i r t ho fs w a r mi n t e l l i g e n c e t h es c i e n t i s t so b t a i n e dt h e e n l i g h t e n m e n ti nt h e r e s e a r c ho ft h eb i o l o g ys w a r mb e h a v i o ra n dp r o p o s e dm a n ya l g o r i t h m si n c l u d i n g p s oa l g o r i t h mo nt h eb a s i so ft h es w a r mi n t e l l i g e n c e 。p s oa l g o r i t h mi sa n o v e l a r m yi ni 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 ti sa na d a p t e dr a n d o ma l g o r i t h mb a s e d o nt h ep o p u l a t i o ns e a r c hs t r a t e g ya n dg e t sal o to fc o n c e r n t h i sa l g o r i t h mi ss i m p l e a n dt h ec o n v e r g e n ts p e e di s q u i c k , i na d d i t i o n ，i th a sf e wp a r a m e t e r sa n de a s i l y p r o g r a m m i n g i nt h ep r o j e c tp r a c t i c e ，p s oh a sa l r e a d yb e e nw i d e l ya p p l i e di nt h e f u n c t i o no p t i m i z a t i o n ，t h ep a r a m e t e ro 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 ga n dp i d p a r a m e t e r st u n i n g t h i st h e s i sb e g i n sf r o mt h eb a s i cp r i n c i p l e ，p a r a m e t e rc h o i c ea n d a p p l i c a t i o no f p s oa n dp r e s e n t san e wp s oa l g o r i t h mi nw h i c ht h ee x i s t i n gp r o b l e mo ft r a d i t i o n a l p s oa l g o r i t h mc a nb ep a r t l ya v o i d e d ，i n c l u d i n gs l o wc o n v e r g e n c ea n dg e t t i n gi n t o l o c a lo p t i m u mo ft r a d i t i o n a lp s oa l g o r i t h m i ns h o r t ，t h ei d e ai st h a tt h ep a r a m e t e r s o ft r a d i t i o n a lp s oa l g o r i t h mc a nb ea d j u s t e dt om a k et h ev a r i a t i o no ns p e e da n d a s p e c to fp r o c e s si np a r t i c l eo p t i m i z a t i o n o nt h a tw a y , v a r i e t yo fp o p u l a t i o ni s i n c r e a s e da n dt h es e a r c h i n ga b i l i t yi se n h a n c e d s c h a f f e r st e s t i n gf u n c t i o n sa r eu s e d t os i m u l a t i o n ，a n dt h et e s t i n gr e s u l tp r o v e dt h a ti m p r o v e dp s oi sf e a s i b l ea n d e f f e c t u a l a t 也ef i r s tp a r t ，t h ep r e s e n ts i t u a t i o ni np s oa l g o r i t h mi si n t r o d u c e d s e c o n d l y , t h et h e o r ya n da p p l i c a t i o no fp s oi ss u m m a r i z e d t h en o v e la l g o r i t h mi sp r e s e n t e d a n dp l u n g e di n t ot h ef u n c t i o nt e s ti nt h et h i r dp a r t l a s tp a r ti st h ea p p l i c a t i o no ft h e a l g o r i t h mt ot h em u l t i o b j e c t i v eo p t i m i z a t i o nr e s e a r c h k e yw o r d s ：c o m p u t a t i o n a li n t e l l i g e n c e ，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 ， t u n i n gp a r a m e t e r s ，m u l t i o b j e c t i v e so p t i m i z a t i o n 学位论文独创性声明 本人郑重声明： 1 、坚持以“求实、创新的科学精神从事研究工作。 2 、本论文是我个人在导师指导下进行的研究工作和取得的研究 成果。 3 、本论文中除引文外，所有实验、数据和有关材料均是真实的。 4 、本论文中除引文和致谢的内容外，不包含其他人或其它机构 已经发表或撰写过的研究成果。 5 、其他同志对本研究所做的贡献均已在论文中作了声明并表示 了谢意。 作者签名： 日期： 学位论文使用授权声明 本人完全了解南京信息工程大学有关保留、使用学位论文的规 定，学校有权保留学位论文并向国家主管部门或其指定机构送交论 文的电子版和纸质版；有权将学位论文用于非赢利目的的少量复制 并允许论文进入学校图书馆被查阅；有权将学位论文的内容编入有 关数据库进行检索；有权将学位论文的标题和摘要汇编出版。保密 的学位论文在解密后适用本规定。 作者签名：7 p 1 辜 日 期：趔8 驰b l q 邑 1 1 引言 第一章绪论 优化问题是一个古老的问题，但同时也最具有现实的意义，它广泛应用于工业、农业、 国防、工程、交通、金融、化工、能源、通信等许多领域，比如一些资源的规划、设计结 构、管理调度等等许多的领域都得到了很大的经济和社会效益。如何在满足基本需求的同 时又能降低成本呢? 长期以来，人们对优化问题不断地进行探索和研究。优化理论以数学为 基础，已经很快的发展成为应用数学中非常主要的- - f - j 学科，同时与分析几何、概率、系 统科学等等科目也有着重要的联系。实验证明，在同等的条件下，优化技术对系统效率的 提高、能源的降低、资源的合理利用及经济效益的增长都有着明显的效果。传统的方法包 括线性规划法、非线性规划法、牛顿迭代法等等，现代的方法包括许多新型的算法等( 如 图1 1 所示) 。群体智能算法的诞生使优化领域得到了很大的发展，科学家们就利用生物群 体的自然行为来解决许多实际生活中的问题，并且构造和设计出许多仿生物行为的优化算 法，它们都是模拟自然界的生物系统。这些系统根据生物体自身的特性，以及生物自身无 意识的寻觅行为来优化其生存状态从而适应环境的一些新型的优化算法，例如粒子群优化 算法、蚁群算法、人工鱼群算法等等。目前，粒子群优化算法是一种比较新的人工智能进 化算法，它基于迭代的原理，搜索最优值。群体智能优化算法为优化理论提供了新的思路 与方法，并且在科学研究、工程应用等领域得到了广泛的应用。在自然资源日渐消失的今 天，优化理论的广泛应用可以使我们更充分的利用现有的资源，这对人类今后的可持续性 发展起到非常重要的作用。 随着科学的不断发展，各个学科之间的联系越来越紧密，科学家们不单把目光放在自 身的学科上面，而是着眼于整个的自然科学中。学科之间的交叉和碰撞产生了无数新兴的 理论和技术，在其他人眼中再普遍不过的鸟类觅食、蜜蜂采蜜、蚂蚁搬家等生物的自然行 为，都没有逃过科学家们的眼睛。他们发现在自然界中一些生物的行为呈现出群体的特征， 动物学家r e y n o l d s 发现这些以群体形式生存的群落一般都要遵循三个基本的原则：( 1 ) 种 群中的个体之间要保持相对的距离，避免同伴间的拥挤与碰撞；( 2 ) 与临近的同伴保持一 致的方向，这样便可以更加接近目标；( 3 ) 尽量向同伴的中心靠拢。从这三条基本的原则 中，主要表达了两个重要的信息，一个是个体信息，一个是整体信息，从而形成了以群体 智能( s w a r mi n t e l l i g e n c e ) 为核心的理论体系【l 】o 图1 1 优化方法分类 传统方法直接分析对候选解进线性规划 行操作 梯度方法 牛顿迭代法 构建解分枝与限定法 动态规划法 分治法 现代方法确定的禁忌搜索 概率的 单解的模拟退火 随机爬山法 多解的粒子群算法 演化算法 遗传算法 遗传程序设计 进化规则 进化策略 1 2 研究背景与意义 1 9 9 5 年，e b e r h a r t 博士和k e n n e d y 博士在人工生命的研究中得到启发，提出了一种新 的群体智能优化算法一粒子群优化算法( 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 2 】。假设这样一个场景：一群鸟在随机寻找食物，在这个 区域范围内只有一块食物，所有的鸟都不知道这块食物在哪里，但是它们知道当前的位置 离食物还有多远。那么找到食物的最佳、最简单有效的方法就是搜寻目前离食物最近的鸟 的周围区域。p s o 算法就是从这种生物种群行为特性中得到启发并用于求解优化问题。 粒子群优化算法的基本思想是通过群体中个体之间的合作和信息共享来寻找最优解， 是一种基于群体智能方法的进化计算技术。粒子群优化算法利用鸟类群体内个体的合作与 2 竞争等复杂行为产生群体智能，该模型中每个粒子都有一定的感知能力，能够感知粒子周 围处于局部最好位置的粒子以及整个种群的全局最好位置的粒子的存在，根据当前的状态， 调整自己下一步的速度和方向，从而使整个种群表现出一定的智能性。在解决优化问题时， 每个粒子都被看成一个潜在的解，经过多次迭代最终得到所需要的全局最优解。粒子群优 化算法的算法简单、收敛的速度比较快、参数较少、易于实现程序设计。 这种基于种群行为的算法属于群体智能理论。一个种群通常被定义为一个自治群体的 集合，它们通过相互间直接的或者间接的交流，用整体的活动来解决一些分布式的问题。 自治群体是指在一个环境中具备自身活动能力的一个群体，其中的每个个体非常简单，通 常不具备高级的智能，但当它们的集体活动时所表现出来的则是一种高级智能才能达到的 活动，我们称这种行为为群智能( s w a r mi n t e l l i g e n c e ) 。群智能是一种社会生物系统，由简 单个体组成的群体与环境和每个个体之间的互动行为。这些模拟系统利用部分信息来产生 不可预测的群体行为。长期以来，以群居生活的生物，如蚂蚁、蜜蜂、鸟类等，引起了包 括自然学家们的兴趣。群体行为的关键之处就是：每个个体都很简单，但当它们一起集体 活动时却能表现出很复杂的行为。 群体智能的主要特点主要有： ( 1 ) 合作性。合作是群体智能最主要的特点，合作不但有行为上的支持而且还有信息 上的共享。群居生物在捕食、御敌、迁徙的过程中，都是依靠个体之间的合作来完成的。 ( 2 ) 分布性。每个个体是呈分散状态的，没有对群体中个体的行为进行集中控制。 这样虽然个体的信息是部分的，但通过个体间的信息交流，整个群体的信息却是完整的， 因此群体行为往往可以达到全局最优。这个特点与计算机网络的工作环境非常类似。 ( 3 ) 鲁棒性。因为群体中个体具有分布性，没有集中的控制，所以，不会因为其中 的一个或者几个个体的原因而影响整个全局的问题，这样的系统更具有鲁棒性( r o b u s t ) ， 更加稳定。 ( 4 ) 自适应性和快速性。群体中每个个体的行为能力都很简单，区区的几条规则就 可以描述，但这些行为对环境变化都有自适应性和快速性，能根据环境的变化做出快速的 反应。 群智能的合作性、分布性、鲁棒性和快速性的特点使生物群体在没有全局信息的情况 下，为寻找问题的解提供了快速可靠的基础，为系统的复杂性研究以及n p 问题、人工智 能、认知科学等领域的基础理论问题研究开创了新的研究方向，同时也为电信路由控制、 工业动态生产控制、组合优化、无线移动网络基站优化、机场调度、高速公路控制等实际 工程问题提供了解决方法。因此，群智能研究具有非常重要的意义和广阔的前景。本文将 3 主要研究群体智能中的粒子群算法( 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 3 国内外研究现状和进展 粒子群优化算法是属于计算智能领域，除了蚁群优化算法以外的另一种群体智能算法。 与遗传算法( g a ) 相似，p s o 是通过个体间的合作和竞争实现全局的搜索。系统随机初 始化为一组解，称为粒子。通过这些粒子在搜索空间的飞行完成寻优，与g a 不同的是它 没有交叉以及变异的过程，而是粒子在解空间追随最优的粒子进行搜索。最初，粒子群优 化算法是为解决实际问题而设计。后来逐渐扩展到解决离散二进制问题，为粒子群优化算 法与g a 的性能比较提供了一个平台。 粒子群优化算法被提出以来，引起了国际上相关领域广大学者的关注和研究，其研究 大致可以分为：算法机制研究、算法的改进和比较、及算法的应用研究。其中算法机制的 研究主要包括：收敛性分析、复杂性分析及参数分析；算法改进和比较主要包括：多样性 保持、加强局部搜索、与其他算法相结合；算法应用研究主要包括：多目标问题、约束优 化问题、动态问题以及实际问题。 对于提高收敛性能方面来说，传统p s o 算法的速度项中引入了惯性权重( i n e r t i a w e i g h t ) ，惯性权重的引入是为了平衡全局和局部的搜索能力。当惯性权重变大时，全局搜 索能力增强，局部搜索能力变弱；相反，当局部搜索能力增强时，全局搜索能力变弱。动 态的惯性权重可以得到比固定值更好的寻优结果。动态惯性权重可以在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 的一种特殊情况。研究发 现，全局版本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 当中引入了 4 一些算子，包括选择、交叉和变异。通过选择算子，最优的粒子将被直接复制到下一代， 从而保持最优性能的粒子。同进化算法类似，通过交叉算子，成对的粒子将交换相互的信 息，以便有向新的搜索空间飞翔的能力。变异算子主要目的是为了增强p s o 跳出局部极小 的能力。混合p s o 是改进研究的热点，其发展非常迅速。除了将进化算法中的选择、交叉 以及变异算子引入p s o 外，还有很多与其他经典优化技术相结合的混合p s o 算法，例如 梯度下降、k 均值聚类算法、免疫算法等。 粒子群优化算法在近年来得到了很大的发展，综上所述：1 9 9 7 年s h i 提出了通过一个 惯性权值来协调粒子群的全局和局部寻优能力。a n g e l i n e 于1 9 9 8 年提出混合p s o 模型 将基本p s o 算法和选择机制相结合而得到的。l o v b j e r g 等于2 0 0 0 年提出将进化算法中的 交叉操作也引入p s o 的h p s o 模型。k e n n e d y 和e b e r h a r t 提出了一种离散二进制p s o 算 法，2 0 0 2 年c l e r c 推广了这一工作，研究了离散版的p s o 算法，并将其应用于旅行商问题 的求解，取得了较好的结果。2 0 0 4 年高鹰等提出了基于生物免疫系统的i m - p s o ，提高了 进化后期算法的收敛速度和精度。2 0 0 7 年k a n gq i 等人提出了基于万有引力模型的p s o 算法。p s o 原理上十分简单，所需参数也较少，并且易于实现。己经应用到很多的领域。 通常，其他进化算法能够应用较好的领域，p s o 算法亦能成功应用。比如p s o 已经被成功 地用到解决多目标优化和约束优化问题。此外，p s o 还应用到很多的工业领域。比如，p s o 己被成功地应用到p i d 参数整定和神经网络训练，以及成分混合优化掣2 , 3 a 】。 1 4 本文的主要成果 本文在第一章概括性地介绍了群体智能算法的特点和研究现状，第二章详细介绍了传 统的粒子群算法的基本原理、数学模型、算法流程、算法参数等，并且介绍了传统算法存 在的一些问题及近年来进行改进和研究工作，以及粒子群算法在训练神经网络和整定p i d 参数两方面的应用。在第三章中通过对算法的分析和研究，提出了一种新的改进方法，因 为算法收敛速度快、参数较少，所以近年来受到广泛的研究和探索。同其它的基于随机进 化算法一样，粒子群优化算法也存在参数控制和早熟收敛的问题，同时与其它随机算法相 比较，随着迭代次数的增加，粒子群优化算法的搜索的能力也随之降低。针对上述问题， 作者提出了一些控制参数的改进方案来加强算法逃离陷入局部最优点的能力。调整了传统 的粒子群算法中的参数，使粒子寻优过程中速度与方向的变异随着迭代次数的变化而变化。 这样即提高了种群的多样性，也加强了搜索能力。并通过仿真实验证明算法的有效性。第 四章是将粒子群算法应用在多目标优化问题中。最后是对本论文总结和对今后研究的展望。 5 第二章粒子群优化算法 2 1 传统的粒子群算法 2 1 1 算法原理 粒子群优化算法( p a r t i c l es w a r mo p t i m i z a t i o n ) 是一种集群优化算法，它起源于对一 个简化社会模型的仿真，是受鸟群群体运动行为方式启发而提出的一种具有代表性的集群 智能方法。研究者发现鸟群在飞行过程中经常会突然改变方向、散开、聚集，它们的行为 通常是无法预测，但整个群体总能保持一致性，个体与个体间也保持着最适宜的距离。通 过对类似生物群体的行为的研究，发现生物群体中存在着一种社会信息共享机制，它为群 体的进化提供了一种优势，这也是粒子群优化算法形成的基础。 粒子群优化算法的思想来源于人工生命和演化计算理论。r e y n o l d s 对鸟群飞行的研究 发现，鸟仅仅是追踪它有限数量的邻居但最终的整体结果是整个鸟群好像在一个中心的控 制之下，即复杂的全局行为是由简单规则的相互作用引起的。一群鸟在随机搜寻食物，如 果这个区域里只有一块食物，那么找到食物的最简单有效的策略就是搜寻目前离食物最近 的鸟的周围区域。粒子群优化算法就是从这种模型中得到启示而产生的，并用于解决优化 问题。另外，人们通常是以他们自己及他人的经验作为决策的依据，这就构成了粒子群优 化算法的一个基本概念。粒子群优化算法求解优化问题时，问题的解对应于搜索空间中一 只鸟的位置，称这些鸟为“粒子”( p a r t i c l e ) 或“主体”( a g e n t ) 。每个粒子都有自己的位 置和速度( 决定飞行的方向和距离) ，还有一个由被优化函数决定的适应值。各个粒子记忆、 追随当前的最优粒子，在解空间中搜索。每次迭代的过程不是完全随机的，如果找到较好 解，将会以此为依据来寻找下一个解。 粒子群优化算法首先初始化为一群随机粒子( 随机解) ，在每一次迭代中，粒子通过跟 踪两个“极值”来更新自己：第一个就是粒子本身所找到的最好解，叫做个体极值点( 用 p b e s t 表示其位置) ；全局版p s o 中的另一个极值是从是整个种群目前找到的最好解。与基 于达尔文“适者生存、优胜劣汰”进化思想的遗传算法( g a ) 不同的是，粒子群优化算法 是通过个体之间的协作来寻找最优解，它利用了生物群体中信息共享会产生进化优势的思 想。 6 粒子群中粒子的初始位置是在搜索区域内随机产生，每个粒子的初始速度也是随机给 定的。在搜索的过程中，整个种群和每个粒子所经历的最好位置及相应的适应度函数值都 分别被记忆下来。粒子群算法最基本的概念在于加速每个粒子向它自己所经历的和种群所 经历的最好位置移动，移动过程可以用图2 1 来描述： j y v i 一。一- ”一一一”7 、v m 鞭 、么二二二二：- 姗 v p b c s t r 0x 图2 - 1p s o 算法的粒子移动不葸圈 假设在一个d 维的搜索空间中，有肌个粒子( p a r t i c l e ) 组成一个群体( s w a r m ) ，以 一定的速度飞行，其中第i 个粒子表示为一个d 维的向量为= ( 砀，薯：，) 2 ，i = 1 ，2 ，加， 即第i 个粒子在d 维的搜索空间中的位置是五。将x i 代入一个目标函数就可以计算出它的 适应值，根据适应值的大小衡量五的优劣。第i 个粒子的速度表示为v j = ( v ，h ：，) ， 1 f m ，1 d d ；第i 个粒子经历的历史最优值为p i = ( 易，p i ：，助) ：整个种群里所有粒 子所经历的最优值为p g = ( 珞i ，p 9 2 ，p g d ) ；粒子的位置和速度根据如下方程进行变化： k j + 1 = 吃+ c l ，册匾( 虎一) + c 2 ，册吐( 西一艺) ( 2 - 1 ) 搿1 = + 略1 ( 2 2 ) 这里，q 和c 2 被称为学习因子，是正常数。学习因子使粒子具有自我总结和向群体中 优秀个体学习的能力，从而向自己的历史最优点以及群体内或邻域内的历史最优点靠近。q 和c 2 通常等于2 。r a n d 。，r a n d 2 【o ，1 】是在【o ，1 】区间内均匀分布的伪随机数。粒子的速度被 7 限制在一个最大速度v 的范围内。 2 1 2 算法参数 标准粒子群算法的几个参数： ( 1 ) 群体大小m ： m 是个整型参数。当聊很小的时候，陷入局优的可能性很大。然而，群体过大将导致 计算时间的大幅增加。并且当群体数目增长至一定水平时，再增长将不再有显著的作用。 当m = 1 的时候，p s o 算法变为基于个体搜索的技术，一旦陷入局优，将不可能跳出。当m 很大时，p s o 的优化能力很好，可是收敛的速度将非常慢。 ( 2 ) 学习因子q 和c ： 学习因子使粒子具有自我总结和向群体中优秀个体学习的能力，从而向群体内或邻域 内最优点靠近。c i 和c 2 通常等于2 ，不过在文献中也有其他的取值。但是一般c a 等于c 2 ， 并且范围在0 和4 之间。 ( 3 ) 最大速度v 一： 决定粒子在一次迭代中最大的移动距离。较大，探索能力增强，但是粒子容易飞 过最好解。v 麟较小时，开发能力增强，但是容易陷入局优。有分析和实验表明，设定v 一 的作用可以通过惯性权重的调整来实现。所以现在的实验基本上使用v 麟进行初始化，将 设定为每维变量的变化范围，而不必进行细致的选择与调节。 ( 4 ) 惯性权重： 惯性权重的大小决定了对粒子当前速度的继承多少。较大的惯性权重将使粒子具 有较大的速度，从而有较强的探索能力；较小的惯性权重将使粒子具有较强的开发能力。 ( 5 ) 停止准则： 一般使用最大迭代次数或可以接受满意解作为停止准则。 ( 6 ) 邻域定义( 拓扑结构) ： 全局版本p s o 将整个群体作为粒子的邻域，速度快，不过有时会陷入局部最优；局部 版本p s o 将索引号相近或者位置相近的个体作为粒子的邻域，收敛速度慢一点，不过很难 陷入局部最优。在实际应用中，可以先用全局p s o 找到大致的结果，再用局部p s o 进行 搜索。 ( 7 ) 粒子空间的初始化：较好地选择粒子的初始化空间，将大大缩短收敛时间。 8 2 1 3 算法的步骤 p s o 的流程可以描述为： s t e p l初始搜索点的位置x j 及其速度v 通常是在允许的范围内随机产生的，每个粒子 的p b e s t 坐标设置为其当前位置，且计算出其相应的个体极值( 即个体极值点的适应度值) ， 而全局极值( 即全局极值点的适应度值) 就是个体极值中最好的，记录该最好值的粒子序 号，并将g b e s t 设置为该最好粒子的当前位置。 s t e p 2 评价每一个粒子，根据适应度函数计算每个粒子的适应度值。 s t e p 3 对每个粒子，将其适应值与所经历过的最好位置的适应值进行比较，如果更好， 则将其作为粒子的个体历史最优值，用当前位置更新个体历史最好位置。 s t e p 4 对每个粒子，将其历史最优适应值与群体内或邻域内所经历的最好位置的适应 值进行比较，若更好，则将其作为当前的全局最好位置。 s t e p 5 用式( 2 1 ) 和式( 2 2 ) 对每一个粒子的速度和位置进行更新。 s t e p 6 检验是否符合结束条件，如果当前的迭代次数达到了预先设定的最大次数( 或 达到最小错误要求) ，则停止迭代，输出最优解，否则转到s t e p 2 。 开始 随机初始化种群 否 评价每个粒子的适应度 根据粒子的适应度函数更新粒子的个体最优值和全局最优值 根据速度和位置公式更新粒子的速度和位置 达到最大迭代次数或者解的误差在允许范围之内 结束 是 图2 - 2 粒子群算法的步骤 9 2 1 4 全局模型与局部模型 以上算法描述中，粒子跟踪两个极值，自身极值p b e s t 和种群全局极值g b e s t ，称为全 局版本( g l o b a lv e r s i o n ) p s o ，另一种为局部版本( 1 0 c a lv e r s i o n ) p s o ，局部版本中，一 般有两种方式组成邻域，一种是索引号相临的粒子组成邻域，另一种是位置相临的粒子组 成邻域。粒子群优化算法的邻域定义策略称为粒子群的拓扑结构。粒子除了追随自身极值 p b e s t 外，不跟踪全局极值曲e s t 而是追随拓扑近邻粒子当中的局部极值l b e s t 。在该版本中， 每个粒子需记录自己和它邻居的最优值，而不需要记录整个群体的最优值。比如，邻居大 小为2 ，则第f 粒子只需比较自己适应值和第f 一1 和第i + 1 粒子的适应值大小。对于局部版 本，上述6 个步骤中位置的改变是将第5 步当中的位置公式改为下面的式子： 略1 = 吃+ c , r a n d l ( p 刍一) + c 2 ，i 册c f 2 ( 以一) ( 2 3 ) 其中p l 为局部最优点。 比较全局和局部版本两种算法，可注意到，它们收敛速度和跳出局部最优的能力有所 差异。由于全局拓扑结构中所有粒子都信息共享，粒子向当前最优解收敛的趋势非常显著， 因而全局模型通常收敛到最优点的速度较局部结构快，但更易陷入局部极小，表现为整个 种群一致收敛到当前第一个较好的解。对此更好的理解，可以考虑模拟退火的成功之处， 在其中较差的一些解有时也被保留。局部拓扑结构模型则允许粒子与其邻居比较当前搜索 到的最优位置，从而相互之间施加影响，即便其值比种群最好值要差，该影响可以使较差 个体进化为较好的个体。 2 1 5 其他智能算法介绍 1 蚁群算法( a n tc o l o n ya l g o r i t h m ，a c a ) 蚁群算法是意大利学者d o r i g om 等通过模拟自然界中蚂蚁集体寻径的行为而提出的， 最早成功应用于解决n - p 难题中著名的旅行商问题( t r a v e l i n gs a l e s m a np r o b l e m ，t s p ) 。 近几年来已经拓展到离散域和连续域优化问题的各个学科【l l 】。 经过科学家的长期研究证明：蚂蚁是一类社会性很强的生物，它们群体生活、共同觅 食，觅食过程中每只蚂蚁是单独行动的，并且在行动时并不用视觉，它们在行动所经过的 路径上释放出一种特殊的分泌物，也就是信息素，来寻找食物。当碰到没有信息素的岔路 1 0 时，它们就会随机选择一条路径，同时释放出与路径长度有关的信息素，所释放的信息素 量与其走过的路径长度有关，蚂蚁发现不同路径的距离有远、近的区别，则蚂蚁就会选择 最近的路径进行觅食，并把这一情况通过路径上信息素量的大小通知给其它蚂蚁。 基本蚁群算法的求解过程： s t e p l ：初始化参数； s t e p 2 ：生成m 个可行解( 蚂蚁) ； s t e p 3 ：对每一个蚂蚁个体，计算其适应度； s t e p 4 ：确定每一只蚂蚁的最优位置( 最优解) ； s t e p 5 ：确定全局的最优位置( 最优解) ； s t e p 6 ：更新信息素轨迹； s t e p 7 ：判断是否满足终止条件，若满足则终止迭代，否则返回s t e p 3 。 蚁群算法首先成功应用于旅行商问题：如果有n 个城市，需要对所有n 个城市进行访 问且只访问一次的最短距离。在解决旅行商问题时，蚁群优化算法设计虚拟的“蚂蚁”将 摸索不同路线，并留下会随时间逐渐消失的虚拟“信息素”。虚拟的“信息素”也会挥发， 每只蚂蚁每次随机选择要走的路径，它们倾向于选择路径比较短的、信息素比较浓的路径。 根据“信息素较浓的路线更近”的原则，即可选择出最佳路线。由于这个算法利用了正反 馈机制，使得较短的路径能够有较大的机会得到选择，并且由于采用了概率算法，所以它 能够不局限于局部最优解。 目前，除了己得到公认的遗传算法、模拟退火算法、禁忌搜索算法等计算智能算法， 新加入这个行列的蚁群算法正在开始崭露头角，为复杂困难的组合优化问题提供了新颖的 具有竞争力的求解算法。 2 人工免疫算法( a r t i f i c i a li m m u n ea l g o r i t h m a i a ) 人工免疫算法是基于生物免疫抗体产生记忆系统的学习机理的产物，这方面的研究最 初从2 0 世纪8 0 年代中期的免疫学研究发展而来【1 2 】。2 0 世纪9 0 年代初，b e r s i n i h 和v a r e l a f 首次使用人工免疫算法来解决优化问题。免疫系统是哺乳动物抵御外来有害物质侵害的防 御系统，动物一生始终处于复杂多变的、充满伤害的自然环境中，能够平安无事、进行正 常的生命活动，免疫系统在其中起着重要的作用。免疫系统以其有限的资源，能够有效地 应付数量庞大的不同种类的病毒的侵害，这一特性无疑引起了人们特别的关注。在学科交 叉性越来越大的今天，人们在从医学的角度，分析和研究这一特性的同时，也希望能以此 作为启发，设计出新的具有突破性的应用方法，以解决某些应用领域中目前难以解决的难 题。 该免疫算法大致由以下5 个步骤组成： s t e p l 抗原识别：通常会将需要解决的问题抽象成符合免疫系统处理的抗原形式，抗 原识别的过程就对应为问题的求解。 s t e p 2 初始抗体群体产生：将抗体的群体定义为问题的解，抗体和抗原之间的亲和力 对应问题解的评估，亲和力越高，说明解越好。 s t e p 3 计算亲和力。 s t e p 4 克隆选择：与抗原有较大亲和力的抗体优先得到繁殖，抑制浓度过高的抗体， 淘汰低亲和力的抗体。为获得多样性，抗体在克隆时经历变异。 s t e p 5 群体更新：若不能满足终止条件，则转向第3 步，重新开始；若满足终止条件， 则当前的抗体群体则为问题的最佳解。 常用的算法有否定选择算法( n e g a t i v es e l e c t i o na l g o r i t h m ) 和克隆选择算法( c l o n e s e l e c t i o na l g o r i t h m ) 。 3 人工鱼群算法( a r t i f i c i a lf i s hs w a r ma l g o r i t h m ，a f s a ) 人工鱼群算法是在一片水域中生活的鱼类一般都能找到食物丰富的地方并聚集成群。 在这种群体活动中，没有统一的协调者，而是通过鱼类每个个体的自适应行为而达到目的。 模拟鱼类生活觅食的特性，李晓磊等人于2 0 0 2 年提出人工鱼群算法( a f s a ) 1 1 3 , 1 4 】。在此 算法中，人工鱼的活动被描述为三种典型行为：( 1 ) 觅食行为：这是鱼的基本行为，当发 现附近有食物时，会向该方向游动；( 2 ) 追尾行为：当某条鱼发现该处食物丰富时，其它 鱼会快速尾随而至：( 3 ) 聚群行为：它们往往能形成非常庞大的群。人工鱼所处的状态可 以用矢量描述：x = “，屯，) ，t ( f = 1 ，2 ，疗) 是所要优化问题的变量。y = ( x ) 为人 工鱼的食物密度，表示所要优化的目标函数。 4 。j = 一_ i l 为两条人工鱼之间的距离，人 工鱼的感知距离定义为v i s u a l 距离。在人工鱼群算法中定义拥挤因子表示人工鱼所处环境 的拥挤程度，人工鱼在食物较多而又不拥挤的环境下捕食，当环境过分拥挤时它就会离开 这个环境，游往别处。 人工鱼群算法觅食行为如下： s t e p l ：设置最大尝试次数； 1 2 s t e p 2 ：人工鱼从一个状态转移到另一个状态：x j = t + r a n d o m ( v i s u a l ) ； 跏p 3 髁脏截q 坝峨岫= x i + r a n d o m ( s t e p 尚酒则_ i , 一= x i + r a n d o m ( s t e p ) ； s t e p 4 ：检查终止条件，如果条件满足结束迭代，否则转s t e p 2 。 对于人工鱼的追尾行为：由状态葺转移到状态x ，能获得更好的适应值l ，人工鱼就向状 态x ，移动一步。否则，就转入觅食行为。人工鱼的聚群行为，当人工鱼探测到所感知的范 围内具有较多食物又不拥挤时，人工鱼就向伙伴的中心移动，否则，转向觅食行为。 在人工鱼群算法中设置一个公告板，用于记录最优人工鱼个体的状态，当人工鱼自身状 态优于最优状态就替代之。该算法具有良好的求取全局极值能力，并具有对初值、参数选 择不敏感、鲁棒性强、简单易实现等诸多优点，但是当问题规模过大时求解困难并且求解 初期收敛较快，后期较慢。人工鱼群算法目前已用于组合优化、参数估计、p i d 控制器的 参数整定、神经网络优化等。 4 混合蛙跳算法( s h u f f l e df r o gl e a p i n ga l g o r i t h m ，s f l a ) 混合蛙跳算法( s h u f f l e df r o gl e a p i n ga l g o r i t h m ，s f l a ) p s i , 在一片湿地中生活着一 群青蛙，湿地内离散地分布着许多石头，青蛙通过寻找不同的石头进行跳跃去找到食物较 多的地方。每个青蛙通过寻找不同的石头提高自己寻找食物的能力，而青蛙个体之间通过 思想的交流实现信息的交换。模拟群体青蛙的觅食特性，文献 4 】于2 0 0 3 年提出混合蛙跳算 法( s f l a ) 。每只青蛙都具有自己的文化，为了达到自己的目标努力，并被定义为问题的一 个解。湿地的整个青蛙群体被分为不同的子群体，每个子群体有着自己文化，执行局部搜 索策略。在子群体中的每个个体有着自己的文化，并且影响着其它个体，并随着子群体的 进化而进化。当子群体进化到一定阶段以后，各个子群体之间再进行思想的交流实现子群 体间的混合运算，一直到所设置的条件满足为止。对于d 维函数优化问题，第f 只青蛙可 表示为( ，( f ) = ( 叫，昕，畔) ，根据每只青蛙适应值( 位置) 的大小按下降顺序排列。这样， 整个青蛙群体被分为朋个子群体，每个子群体包含n 只青蛙，即池塘中的青蛙数目为 f = m x n 。在进化计算过程中，第一只青蛙进入第一个子群体，第二只青蛙进入第二个子 群体，一直分配下去，直到第m 只青蛙进入到第m 个子群体。然后，第m + 1 只青蛙又进入 1 3 到第一个子群体，第m + 2 只青蛙进入到第二个子群体等，这样循环分配下去，直到所有青 蛙分配完毕。在每一个子群体中，适应值最好的个体和最差的个体记为和乩，整个青蛙 群体的最优值记为【，。在每次循环中，只提高最差个体的适应值。 混合蛙跳中最差适应值( 位置) 青蛙的计算过程为： 蛙跳步长更新：岛= r a n d o ( u b 一乩) ( 2 - 4 ) 位置更新： 乩( 露+ 1 ) = 乩( 七) + 墨( 2 5 ) 岛一，其中r a n d o 【o ，l 】( | j = l ，2 ，刀) ，是最大步长。如果计算后新的解 较优，则用其替代最差个体。并且通过步长和位置公式来求全局最优解u 。如果得到的解 没有改进，那么随机生成新解取代所求个体的解，算法继续迭代直至迭代次数完毕。 混合蛙跳算法的算法流程如下： s t e p l ：针对f 只青蛙( 解) ，随机产生种群； s t e p 2 ：对每只青蛙个体，计算其适应值； s t e p 3 ：将f 只青蛙按适应值降序排列分为埘个子群体； s t e p 4 ：对每一个子群体中的青蛙个体找出其中的最优个体和最差个体，在指定迭代次 数内提高最差个体的适应值； s t e p 5 ：针对各个子群体，按适应值降序排列个体，进行重新分配和混合运算； s t e p 6 ：终止条件是否满足，如果满足，结束迭代，否则转向s t e p 2 。 混合蛙跳算法具有全局优化与局部细致搜索的优点，可以用来优化连续问题和离散问 题，并且具有较强的鲁棒性，可用于非线性函数优化、旅行商问题、齿轮问题掣1 6 】。 2 2 粒子群算法的发展 2 2 1 引入惯性权重 1 9 9 8 年s h i 和e b e r h a r t 将惯性权重的思想引入到传统的粒子群算法中来更新速度方程 6 1 。惯性权重c c ) 是用来控制粒子以前速度对现在速度的影响，也就是粒子对本身以前速度 的改变程度，这个程度会影响粒子的全局和局部的搜索能力。当值比较大的时候对全局 搜索是非常有利的，当值比较小的时候对局部搜索能力是有利的。所以，选择一个适当 1 4 的n 值可以使全局和局部搜索能力得到平衡，同时提高算法的收敛速度和精度，这样也可 以用最少的迭代次数完成整个寻找最优解的过程。粒子群算法中控制惯性权重来增强全局 和局部的搜索能力，目前使用较多的是l d w ( 线性递减策略) ，l d w 是初始化值为0 9 ， 随迭代次数的增加递减至0 4 或者更小。也可以选择将值从0 9 5