粒子群优化算法

Comment J1: 在 4 月份已经发给所 有同学的模板基础上，需要补充说明 如下 5 点格式要求： 1. 公式所在行的排版要“右对齐” ，且公式本身基本上要处于所在行的 中间； 2. 每篇参考文献原则上一定要在 论文正文中顺序引用，引用格式为上 标形式！ 3. 参考文献本身的格式一定要特 别注意！ 4. 图和表的标题的字体为宋体、 5 号，图表标题要居中，图的标题在 图的正下方，表的标题在表的正上方。 同时，图和表原则上要和论文正文在 上面和下面各空开一行！ 5. 论文中如要给出关键源代码， 则源代码要使用浅灰色底纹形式！详 见范文的第 11 页和 12 页！ 本文由本文由【中文中文 word 文档库文档库】 搜集整理。搜集整理。中文中文 word 文档库文档库免费提供海量教学免费提供海量教学 资料、行业资料、范文模板、应用文书、考试学习和社会经济等资料、行业资料、范文模板、应用文书、考试学习和社会经济等 word 文档文档 目目 录录 前 言 .1 第一章 概述 .2 1.1 引言.2 1.2 研究背景.2 1.2.1 人工生命计算.2 1.2.2 粒子群算法与遗传算法.3 1.2.3 人工神经网络与粒子群优化算法.3 第二章 粒子群优化算法 .5 2.1 基本粒子群优化算法.5 2.2 算法流程.5 2.3 基本粒子群优化算法的缺点及改进方法.6 2.3.1 基本粒子群优化算法的缺点.6 2.3.2 几种改进算法.6 2.3.2.1 标准粒子群优化算法.6 2.3.2.2 带有收缩因子的粒子群优化算法.7 2.3.2.3 采用微分扰动的粒子群.8 2.3.2.4 带有小生境拓扑结构的粒子群优化算法.9 2.3.2.5 带有梯度加速因子的粒子群优化算法.10 第三章 基于多种群的粒子群优化算法 .11 3.1 算法基本改进方法.11 3.2 算法伪代码.11 第四章 实验分析 .14 4.1 几种常用改进算法.14 4.2 标准测试函数.14 4.3 收敛速度实验分析.15 4.3.1 实验设置.16 4.3.2 实验结果.16 4.4 收敛性能实验分析.17 4.4.1 实验设置.17 4.4.2 实验结果.18 4.5 算法参数分析.19 4.5.1 实验设置.19 4.5.2 实验结果.20 第五章基于多种群的粒子群优化算法的应用 .21 5.1生产计划问题描述.21 5.2实例.22 5.3运行结果.23 第六章总结与展望 .24 6.1课题总结.24 6.2后续研究展望.24 参考文献 .25 致谢 .27 摘摘 要要 在智能领域，大部分问题都可以归结为优化问题。常用的经典优化算法都对问题有 一定的约束条件，如要求优化函数可微等，仿生算法是一种模拟生物智能行为的优化算 法，由于其几乎不存在对问题的约束，因此，得到广泛应用。 本文首先描述了基本粒子群优化算法及其几种改进算法的基本原理, ， 并对基本粒 子群优化算法参数进行了简要分析. 。 根据分析结果,，提出了一种基于多种群的粒子群 优化算法. 。 在 5 个标准优化函数上与基本粒子群优化算法及几种改进算法进行了比较, ， 实验结果表明本文算法在优化多模式函数时性能明显要优于其它算法. 。 本文算法应 用于生产计划安排问题上也获得了较好的性能. 。 最后, 对本文进行了简单的总结和展 望。 关键词：关键词：粒子群优化，适应度，群智能 Abstract In the field of artificial intelligence, most problems belong to the category of optimization. The classical algorithms in common use are usually limited by certain optimizing problems such as the object optimization function, which has to be a continuous one. As bionic algorithm imitates the intellective actions of life free from the limits resulting from the optimizing problems, this kind of algorithm is commonly used. At first place, this dissertation, basing on the particle swarm optimization, illustrates the fundament of this algorithm. This paper also places emphasis on the analysis of parameter that may affect the performance of the algorithm. Also an introduction of improved algorithms and popular advanced improving strategies is shown, as well as the mastery of basic researching process and methods. According to the result of the analysis, the author put forward a new multi-swarms PSO algorithm to overcome the defects of the original. Through the simulation, the results show that, compared with other PSO variants, the algorithm proposed by the author has attained a better solution to the same problems. Finally, the paper gave some further expectations concerning the PSO algorithm research. Keywords: Particle Swarm Optimization, Fitness , Group Intelligence 前前 言言 优化是个古老的问题，其研究的问题是在众多方案中寻找最优方案。长期以来，优 化问题一直受到广泛关注, 是研究的热点问题。早在 17 世纪，英国 Newton 和德国 Leibnitz 发明的微积分就蕴涵了优化的内容。而法国数学家 Cauchy 则首次采用最速梯度 下降法解决了无约束优化问题。后来针对约束优化问题又提出了 Lagrange 乘数法。人们 关于优化问题的研究工作，随着历史的发展不断深入。但是，任何科学的进步都要受到 历史条件的限制，直到二十世纪四十年代，由于科学技术突飞猛进的发展，尤其是高速 数字计算机日益广泛应用，使得优化问题的研究不仅成为一种迫切需要，而且有了求解 的有力工具。因此，优化理论和算法迅速发展起来，成为一门新的学科。至今已出现线 性规划、整数规划、非线性规划、几何规划、动态规划、随机规划等许多分支。这些优 化技术在实际应用中正发挥越来越大的作用。 随着人们生存空间的扩大, 这些常规的优化方法已经无法处理人们所面对的复杂问题。 因此，高效的优化算法成为科学工作者的研究目标之一。本文研究的粒子群优化算法 (particle swarm optimization,简称PSO)是Kennedy和Eberhart源于群体智能和人类 认知学习过程而发展的一种智能优化算法。它与遗传算法(GA)同属群体优化技术，但 PSO 比GA更简单、操作更方便。因此，PSO算法从诞生起，就引起了国内外学者的广 泛关注，并掀起了该方法的研究热潮，且在诸多领域得到了成功应用。但是，PSO 的发 展历史尚短，在理论基础与应用推广上都还存在一些问题，如早熟，种群单一化等，有 待于解决。 针对上述的问题，本文通过对PSO算法原理进行分析，在深入理解几种 PSO 改进 算法的基础上，对 PSO 存在的问题提出了新的改进方法，并将改进的算法应用于实际优 化问题中。 本文主要通过MATLAB7系列作为工作环境，实现算法以及相应的问题模拟。 全文共分五章。第一章概述，主要介绍PSO算法研究背景。第二章粒子群优化算法， 主要介绍PSO算法基本原理，简要分析PSO主要缺陷，并介绍几种常用的改进 PSO 方 法。第三章基于多种群的粒子群优化算法，针对PSO的主要缺陷提出相应改进策略，并 给出伪代码。第四章实验分析，为了检测本文算法性能，选择了三种常用改进 PSO 算法 与本文算法进行了实验比较, 并对实验结果进行了简要分析。同时对本文算法中主要参数 设置方法进行了实验分析，以给出算法参数设置指导思想。第五章基于多种群粒子群优 化算法的应用，本文算法被用于优化生产计划问题并得出结果。第六章对课题进行总结， 并对未来的改进进行展望。 第一章第一章 概述概述 1.1 引言引言 最优化问题是在满足一定约束条件下，寻找一组参数值，使得系统的某些性能指标 达到最大或者最小。它广泛的存在于农业，国防，工程，交通，金融，能源，通信，材 料等诸多领域。最优化技术在上述领域的应用已经产生了巨大的经济效益和社会效益。 国内外的实践证明，在同样条件下，经过优化技术的处理，对系统效率的提高，能耗的 降低，资源的合理利用及经济效益提高均有显著的效果，而且随着处理对象规模的增大， 这种效果也更加显著。但随着处理对象规模的增大，优化问题也越来越复杂，而经典的 优化技术对问题的约束比较大，如梯度下降法要求优化函数是可导等，因此，对于新型 优化算法的研究具有重要的意义。 1.2 研究背景研究背景 1.2.1 人工生命计算人工生命计算 人们从生命现象中得到启示，发明了许多智能的优化方法来解决复杂优化问题。现 在已有很多源于生物现象的计算技巧。例如，人工免疫1模拟生物免疫系统的学习和认知 功能，人工神经网络2-6是简化的大脑模型, 遗传算法7是模拟基因进化的过程。在计算 智能(computational intelligence)领域有两种基于群体智能swarm intelligence8-13的 算法，粒子群优化算法(particle swarm optimization)14和蚁群算法(ant colony optimization) 91315。9,13,15蚁群优化算法模拟了蚂蚁群体在路径选择和信息传递方面的 行为，而粒子群优化算法模拟群居动物觅食迁徙等群体活动中个体与群体协调合作的工 作过程。这类借鉴了模拟生命系统行为功能和特性的科学计算方法称为人工生命计算。 人工生命计算包括两方面的内容，研究如何利用计算技术研究生物现象和研究如何利用 生物技术研究计算问题。人工神经网络，粒子群优化算法，遗传算法，蚁群优化算法等 都属于人工生命计算的范畴。 本文详细介绍的粒子群优化算法是其中的一种新兴计算方法。它同遗传算法类似， 同属随机迭代优化工具。同遗传算法等其他人工生命计算相比，粒子群算法概念简单， 容易实现，调节参数较少。目前粒子群算法越来越引起人们的关注。 1.2.2 粒子群算法与遗传算法粒子群算法与遗传算法 大多数迭代优化技术都有相似的流程： 1. 种群元素随机初始化。 2. 计算种群个体位置适应值(fitness value)。适应值体现与最优解的差异。 3. 种群依适应值进行相应演化。 4. 达到停止条件，停止，否则转 2。 通过对上述步骤观察，可见粒子群算法和遗传算法有很多相似之处。两者都随机初 始化种群(遗传算法则是染色体)。使用适应函数评价系统，且根据其得出的结果进行多次 随机寻优。 然而，粒子群算法没有遗传算法中的交叉(cross over)和变异(mutation)行为。他根 据变化的粒子速度进行每一轮的搜索。再者，粒子群算法中的粒子还有一个重要的特色， 粒子具有记忆能力。 在搜索个体信息共享方面，粒子群算法和遗传算法的做法也是非常不同的。在遗传 算法中，其粒子个体染色体(chromosomes)俩俩之间共享信息，因此其整体是比较均匀 的向最优区移动。粒子群算法通过全局最优粒子指引其他粒子向本轮迭代最优位置移动， 这是一种单向的信息流动。对于第二种机制，较多情况下，算法可能具有更快的收敛速 度。 1.2.3 人工神经网络与粒子群优化算法人工神经网络与粒子群优化算法 人工神经网络是基于生物学中神经网络的基本原理而建立的一种模仿人脑工作方式 的计算模型，可以被视为一种具有大量连接的并行分布式处理器，它可以通过学习获取 知识并解决问题，并且将知识分布存储在连接权中(对应生物神经元的突触)。由于人工神 经网络具有较强的自适应性，学习能力和大规模并行计算能力，目前已被广泛应用于各 种研究及实际工程领域中，如模式识别，信号处理，控制与优化，预测建模，通信等领 域。 近年来，随着进化计算研究热潮的兴起，人们逐渐将进化计算与人工神经网络相结合， 利用各种进化方法去训练神经网络。由于进化算法具有较强的全局收敛能力和较强的稳 定性，且不需要借助问题的特征信息，如导数等梯度信息。因此，将两者相结合，不仅 能发挥神经网络的泛化映射能力而且能够提高神经网络的收敛速度和学习能力。进化计 算用于神经网络优化主要有两个方面：一是用于网络训练，即各层之间的连接权值；二 是优化网络的拓扑结构。具体的研究方法有如下三种： 1.1.通过优化连接权值来训练神经网络通过优化连接权值来训练神经网络 针对特定的神经网络，列出所有的神经元，并将所有的神经元可能存在的连接权值 编码成二进制编码或是实数码串表示的个体，随机生成这些码串的群体，按照常规的方 法执行进化操作。将新形成的码串解码构成神经网络，计算所有训练样本通过此神经网 络产生平均误差，以此来确定每一个体的适应度。这种方法思路简单，但是用于优化的 计算量较大尤其是在优化解决复杂问题的大规模神经网络时，随着神经元的怎增多多， 连接权的总数也随之增多，从而造成进化计算的搜索空间增大。 2.2.优化神经网络的结构和学习规则优化神经网络的结构和学习规则 利用进化算法计算优化设计神经网络的结构，同时包括网络的学习规则以及与之关 联的参数。这种方法直接将未经训练的神经网络的结构模式和学习规则编码成码串表示 的个体，再执行进化操作。与前一种方法相比，器搜索空间相对较小，但是也存在着一 定的缺陷。在优化过程中，每个被选择的个体都必须解码成未经训练的神经网络，再经 过传统的训练以确定其连接权值，因此收敛速度较慢。 3.3.同时优化神经网络的结构和连接权值同时优化神经网络的结构和连接权值 同时优化神经网络的结构和连接权值进行编码以进行优化。Vittorio 曾提出粒度编码 方法来提高连接权值的优化精度，但是粒度控制同时会加剧个体适应度的不连续变化， 从而影响到算法的收敛速度。 采用进化算法去优化神经网络，比起基于梯度的 BP 学习算法，无论是精度还是速度 上，均有了很大的提高。然而，作为一种仿生的随机算法，进化计算本身有具有不可克 服的缺陷。比如进化计算中研究最为充分的遗传算法，虽然它可以用来求解各类复杂问 题，但总是难以克服过早收敛的缺点，同时在采用遗传操作进化时，需要的控制参数过 多，尤其是在优化神经网络的时候，优化过程总是难以控制。因此，为神经网络的优化 寻求更简单，更有效的全局优化函数，是优化领域中的一个研究热点。 第二章第二章 粒子群优化算法粒子群优化算法 2.1 基本粒子群优化算法基本粒子群优化算法 James Kennedy 和 Russell Eberhart 在 1995 年的IEEE International Conference on Neural Networks and 6th International Symposium on Micromachine and Human Science 上分别发表了“Particle swarm optimization”(粒 子群优化) and “A new optimizer using particle swarm theory”(一种使用粒子群理 论的新优化器)的论文，标志着粒子群优化算法的诞生。设想有这样的一个场景：一群鸟 在一个只有一块食物的区域内随机的搜索食物。所有的鸟都不知道食物在哪里。但是他 们知道当前位置和食物的距离。那么最简单有效的寻找策略就是搜索目前和食物距离最 小的鸟的周围区域。PSO从这种模型中得到启示并用其解决优化问题。PSO 中，每个优 化问题的解都是搜索空间中的一只鸟，我们称之为“粒子” 。所有粒子都有一个由被优化 函数决定的适应度值（fitness value） ，每个粒子还有一个速度决定他们飞翔速度的大小 和方向。随即，粒子们会追随当前的最优粒子在解空间内搜索。PSO 初始化为一群随机 粒子（随机解） 。其最终最优解通过若干轮迭代求得。每一次迭代，每一粒子通过两个因 素进行自我更新（通过取得新速度而取得新位置）：粒子自身寻解过程中的最佳解，我 们称它为“自我意识” ，它往往和算法的局部搜索性能有很大的关系，另一个因素我们称 之为“群体智慧” ，是整个群体所找到的最佳解，在速度更新中他能带领整个群体向问题 的全局最优靠拢，在个体和群体的共同协作下算法可以取得最优解。可用下面的公式来 表示粒子每轮的更新行为： (2.1)()()() 1( 2211 tXPCtXPCtVtV idgdidlididid (2.2) ) 1()() 1(tVtXtV ididid 其中，Vid为粒子速度，Xid为粒子位置，C1，C2 称为学习因子或加速常量， 1，2 （0，1）区间内两个随机正数，Plid为个体意识（个体最佳解位置） ，pg 为群 体最佳解位置。 2.2 算法流程算法流程 1. 初始化，设定加速常数和，最大进化代数将当前进化代数置为 t = 1 ， 1 C 2 C max T 在定义空间中随机产生 m 个粒子 X1,X2,Xn，组成初始种群,随机产生各粒子初 n R)(tX 速度 V1，V2,VS组成位移变化矩阵 V(t)。 2. 计算种群中所有粒子的适应值，初始化每粒子pbest为当前粒子，设定种群的 gbest为当前种群的最优粒子。 3. 种群 X(t)演化，对种群中的每一个粒子： (1) 按(2.1),(2.2)式更新粒子的位置和速度。 (2) 计算粒子的适应值。 (3) 比较粒子的适应值和自身的最优值pbest。如果当前值比pbest更优，则更 新pbest为当前值，并更新pbest位置到n维空间中的当前位置。 (4) 比较粒子适应值与种群最优值。如果当前值比gbest更优，则更新gbest 为当前种群最优粒子。 4. 检查结束条件，若满足，则结束寻优；否则，t = t + 1，转至 2.。结束条件为 寻优达到最大进化代数，或评价值小于给定精度。 max T 2.3 基本粒子群优化算法的缺点及改进方法基本粒子群优化算法的缺点及改进方法 2.3.1 基本粒子群优化算法的缺点基本粒子群优化算法的缺点 首先，通过实验发现，PSO的实施过程与他所采用的参数取值有较大的关系，这些 参数取值仍然是一个亟待解决的问题。通常认为，对于不同的问题算法参数设置是不同 的。然而如何设置，则主要依赖设计者的经验, 目前还没有理论用于指导算法的参数设置。 其次，PSO应用于高维复杂问题优化时，往往会遇上早熟收敛的问题，也就是说， 种群还没有达到全局最优点时已经聚集到一点停滞不动。从公式(2.1)中可以会发现，基本 粒子群算法存在一些缺陷，即容易出现早熟收敛，Vid较小和|Plid-Xid|和|pg-Xid|也很小时， 粒子的速度就会受到抑制，从而导致算法搜索停滞不前。这种情况甚至会发生在搜索的 早期，当粒子是当前全局最佳解的时候，就会引起|Plid-Xid|，|Pg-Xid|成为零。这些早熟收 敛点，有可能是局部极小点，也有可能是局部极小点临域的一个点。换句话说，早熟收 敛并不能保证算法收敛到局部极小点。因而，对算法早熟收敛行为处理也是算法改进的 一个难点。 此外，PSO在接近或进入最优点区域时的收敛速度也比较缓慢。实际上对 PSO 的研 究发现，PSO早期收敛速度较快，但到了寻优的后期，其结果改进则不甚理想。这主要 归因于算法收敛到局部极小，缺乏有效的机制使算法保持多样性或逃离局部极小点。 2.3.2 几种改进算法几种改进算法 2.3.2.1 标准粒子群优化算法标准粒子群优化算法 为了改善基本PSO算法的收敛性能，Y.Shi与R.C.Eberhart在 1998 年的IEEE国 际进化计算学术会议上发表了题为“A Modified Particle Swarm Optimizer”16的论 文，首次在速度方程中引入了惯性权重的概念，即 (2.3)()()() 1( 2211 tXPCtXPCtVtV idgdidlididid 式(2.3)中，w称为惯性权重，因此，基本 PSO 算法是惯性权重w = 1 的特殊情况。 惯性权重w使粒子保持运动惯性，使其有扩展搜索空间的趋势，有能力探索新的区域。 引入惯性权重w可清除基本PSO算法对速度最大值的需求，因为w本身具有维护 全局和局部搜索能力的平衡的作用。这样，当速度最大值增加时，可通过减少w来达到 平衡搜索。而 w 的减少可使得所需的迭代次数变少。从这个意义上看，可以将d维速度 的最大值锁定为每维变量的变化范围，只对w进行调节。文献6建议w的取值范围为 0,1.4。 对全局搜索，通常的好方法是在前期有较高的探索能力以得到合适的种子，而在后 期有较高的开发能力以加快收敛速度。为此，可将w设定为随着进化迭代次数而线性减 少，例如由 0.9 到 0.4 等。Y.Shi和R.C.Eberhart的仿真实验结果也表明w线性减少取 得了较好的实验结果。在文献14中，这种线性的w可以模仿模拟退火的中的温度。 （在 某些情况下属实）在本文提出的算法中发现，有些情况下，对上轮迭代粒子速度给于不 保留策略，能够有效提高整个种群的搜索能力。 2.3.2.2 带有收缩因子的粒子群优化算法带有收缩因子的粒子群优化算法 在Clerc16,17的研究中，提出了收缩因子的概念。该方法描述了一种选择w，c1 和 c2 的值的方法，以确保算法收敛。通过正确的选择这些控制参数，就没有必要将粒子速 度控制在速度的极值区间内。接下来首先讨论一个带有收缩因子的粒子群优化算法相关 的收敛模式特例。 一个与某个收敛模式相符合的改进了的速率方程式以以下形式提出： (2.4)()()() 1( 2211 tXPCtXPCtVXtV idgdidlididid 在这里且 l =C1 + C2 = 4.1 我们得出 X = 0.7298 并带入方程 ll X 412 2 2 (2.4)，同时省略参数 t，结果为: (2.5)(05 . 2 )(05 . 2 )(7298 . 0 ) 1( 21 tXPtXPtVtV idgdidlididid 因为 2.05*0.7298 = 1.4962，所以这个方程式与在改进的 PSO 速率更新方程式使用 C1 = C2 = 1.4962 和 w = 0.7298 所得到的方程式是等价的。 Eberhart和Shi将分别利用速度极值和收缩因子来控制粒子速度的两种算法性能做 了比较，结果表明，后者比前者通常具有更好的收敛率。然而在有些测试函数的求解过 程中，使用收缩因子的算法在给定的迭代次数内无法达到全局极值点。按照Eberhart和 Shi的观点，这是由于粒子偏移所期望的搜索空间太远而造成的。为了降低这种影响，他 们建议在使用收缩因子时首先对算法进行限定，比如使得速度极值等于搜索域极值或者 预先设置搜索空间的大小这样可以改进算法对所有测试函数的求解性能不管是在收 敛率方面还是在搜索能力方面。 2.3.2.3 采用微分扰动的粒子群采用微分扰动的粒子群 Swagatam Das，Amit KonarUday，K. Chakraborty对于PSO的研究发现， 通过从微分进化18中引入微分扰动19因子取代公式中(2.1)中粒子的个体意识部分。该因 子形成于群体中随机选择的两个粒子的位置差异向量。同时，与标准PSO算法不同，在 该算法中只有当粒子在新位置的适应度值优于原来位置时，粒子位置才会更新，具体描 述如下： 在他们提出的算法中，对于每一个粒子 i，随机选取两个不同于 i 且互不相同的粒子 j，k。他们之间的差异用向量 来表示。 (2.6) jk XX 第 i 个粒子的第 d 维速度更新公式为： ),()() 1( 22 tXPCtVtV idgddidid if rand d (0,1) CR (2.7) =Vid(t) otherwise CR 是交叉选择概率，d是(2.7)式中的差异向量 的第 d 维分量。 是在0，1上随机 数，为了获得额外探索能力，公式(2.6)中向量微分运算符代替了粒子“个体意识”部分。 当每轮迭代产生的随机概率CR 时，算法使用(2.8)式更新粒子速度，从而得到新的位置 Tr。 (2.8) ) 1()(tVtXrT iii 然而只有新位置体现出更好的适应值时，粒子才会变迁到那里。因此，如果在一个 n 维搜索空间中寻找最小值。 , 那么目标粒子的位置将会被更新为:)(),( ,.,21 Xfxxxf n (2.9)rTtXi ) 1()()(tXfrTfif ii otherwise)() 1(tXtX ii 即粒子只限于移动到更优的位置，或不动。粒子的位置始终为至今最佳解。另一方 面，为了保持粒子搜索活跃性。如果粒子在搜索域中变迟钝（如果他在预定迭代次数内 停滞不前） ，该粒子就会被赋予一随机位置，具体方法如下： )(.)2()1()(NtXtXTXtXif iiii thenfNtXfand i )( (2.10) )() 1 , 0() 1()1( minmaxmin XXrandXNtXtonrfor rir 在这里 是适应函数的全局最小值，N 是该算法中设置的最大迭代次数,(， f max X )定义算法每一轮所允许的搜索区域。 min X 2.3.2.4 带有小生境拓扑结构的粒子群优化算法带有小生境拓扑结构的粒子群优化算法 基于粒子群优化算法中的局部优化模型，根据粒子的下标将粒子群体分割成若干个 相邻的区域，也就是说，粒子 x1 和 x2 在一个半径为 1 的临近区域内可以看成是相邻的， 而不管他们的空间位置如何，根据粒子的空间位置，每个粒子都会选出其特定的最佳邻 居粒子，并用他和最佳邻居的差异向量代替标准PSO速度更新公式中的“个体意识部分” 。 对于种群中每个粒子与临域粒子的拓扑结构，事实上，我们可以看到，PSO算法中 的局部优化模型实际上就是一种简单的临域结构，其每个临域均由粒子的下标决定，而 与粒子的具体位置无关。为了进一步改善算法性能，避免过早收敛的现象，J.Kennedy20在 1999 年提出几种基本的临域结构21，即环形结构和轮型结构及他们的推广。 环形结构是一种最基本的临域结构，在该结构中，每个粒子仅与其附近的两个粒子 相互交流信息，从而能有效地保证种群的多样性。比如，对于粒子 j 而言，其临域为粒子 j+1 和 j-1，从而其信息只能在这两个微粒中交流。这时，对于粒子 k 和 2k 而言，其信息 的交流至少需要经过 k 步才能完成，从而能保证算法充分对每个区域进行搜索，而不至 于陷入过早收敛的情形。此外这里的临域仅与粒子的下标有关，而与粒子的真实位置无 关，从而可以有效的对搜索空间进行搜索，但有时会影响算法效率。作为该结构的推广， 随机环形结构强调了信息交流的迟滞性，但对环形结构的临域仅有粒子下标决定的缺点 做了一定的调整，其临域虽然主体仍由粒子下标决定，但存在两个粒子的临域可以随机 选择，从而在一定程度上提高了算法效率，对算法速度与精度的调整起了平衡作用。 但环形结构的信息交流非常慢，因而即使是随机环形结构，有时其问题的求解也比 较慢。此时，可以考虑使用轮型结构。在该结构中，每个临域不再仅仅是三个粒子了， 而是若干个。其中一个为中心，其余的粒子都与他相邻。也就是说，在每个临域中，只 有中心粒子与该临域中的所有粒子可以交换信息，这样提高了信息的传播速度，避免了 信息的丢失，从而能更好的提高算法效率。 2.3.2.5 带有梯度加速因子的粒子群优化算法带有梯度加速因子的粒子群优化算法 这种算法以一定概率加入梯度信息22，使粒子的移动更具针对性和效率。为减小粒 子陷入局部极小的可能性，对群体最优质进行观察。在寻优过程中，当最优信息出现停 滞时，对部分粒子进行重新初始化，从而保持群体的活性。对于函数 F（x）的梯度可以 表示为他的一阶导数 F（x） 。每次粒子进行速度和位置更新时，每个粒子以概率p按标 准PSO速度更新公式更新，以（1 p）按梯度信息更新，在负梯度方向进行一次直线搜 索来确定速度，直线搜索采用黄金分割法。为防止陷入局部极小。在群体最有信息陷入 停滞时，对群体进行部分重新初始化，以保持群体活性，减少群体陷入具有的可能性。 梯度信息的加入使粒子的移动更具有针对性和效率，进一步提高了PSO算法的收敛 速度，但也会增加算法对问题的依赖性，特别是有些梯度信息极易将粒子引入局优。所 以带有梯度加速的PSO算法需要根据问题的性质来调整梯度信息对于粒子移动的影响程 度。 第三章第三章 基于多种群的粒子群优化算法基于多种群的粒子群优化算法 3.1 算法基本改进方法算法基本改进方法 为了解决粒子群优化算法中普遍存在的种群单一化，收敛早熟化问题，本文提出的 基于多种群的粒子群优化算法在以下几个方面进行了改进： a)该算法基于带有微分扰动因子的粒子群优化算法。引入多种群并行进化概念，即 初始化多个种群进行同时并行进化，在约定条件下进行种群间信息交互。 b)通过实验分析发现，对于多峰函数，该算法速度更新公式中，若不保留粒子的上 轮迭代速度即惯性权重恒定取 0，同时将学习因子取为 1.205，往往会取得较好 的收敛效果。 c)对于原单种群带有微分扰动的粒子群算法新的算法加入搜索域防越界控制。 d)该算法中，为防止各种群粒子由于相互交互而引发种群粒子趋于单一，本算法在 达到一定迭代次数后，将选择全局最优较差的若干种群进行重新初始化。 e)根据带有微分扰动的算法，如果粒子行动停滞不前，则给于该粒子一个在初始化 定义域之间的随机位置。根据作者分析发现，该方法并不科学，因为根据粒子群 算法寻优原理，为了增大寻优成功率，随机位置的发放范围应有目的的缩小。于 是本算法将随机位置放置于当前种群全局最优的位置范围之内。 f)对于粒子的速度和位置使用一种新的初始化方法使得有较好的初始化效果。具体 如下： P_siton粒子位置 P_ciy 粒子速度 P_siton=(1-2 * rand) *max; P_ciy=1-2*rand*max-P_siton / 2; 3.2 算法伪代码算法伪代码 begin initialize the parameter of the algorithm and the population and the position value and velocity of each particle in each swarm. initialize globe best position of each swarm while stopping condition not satisfied do evaluate and store the fitness of each particle of each swarm store in FITVueAryparticleNo,swarmNo calculate the average fitness value of all particle in each swarm and keep it in avgFITswarmNo sort FITVueAryparticleNo,swarmNo chooseNo = rand(swarmNo) for iter = 1:swarmNo for itt = 1: particleNo if fitness(avgFITiter) - fitness(pgiter) gate or counter = 5 particle(best,iter) = particle(worst,chooseNo)/ or particle(worst,iter) = particle(best,chooseNo) end end end for each swarm calculate new pg value end for particle_tag = 1:particleNo particle_A = rand(particleNo) particle_B = rand(particleNo) Vector = |A-B| randNumber = rand(0,1) if rand_Number CR V(t+1) = rand0,1*Vector+c2*rand0,1*(pg-x) else V(t+1) = V(t) end TR = X（t+1） + V(t+1) if（fitness（TR） X(t)） X(t+1) = TR; else X(t+1) = X(t); end sortpg(dimension) = sort(pg) if Xi stagnates for N successive generations for r = 1 to no_of_dimensions Xir(t+1) = Xmin + randr(0, 1)*(sortpg(1),sort(dimension) end end if reach condition (may be run for 400 generation?) reinitialize three worse swarms end end end 第四章第四章 实验分析实验分析 为了验证本文算法的性能,我们把本文提出的基于多种群的粒子群优化算法与粒 子群优化算法的几种常用改进算法进行了比较, ，在实验中, ，选择了 5 个常用的标准 优化函数作为验证函数。本文从三个方面设计了三个不同实验,，实验一，用于验证本文 算法的收敛性能,，实验二用于验证本文算法的收敛速度,，实验三讨论了本文算法参数 的设置方法。. 4.1 几种常用改进算法几种常用改进算法 本文选择 2.3.2 节中已介绍的带有小生境因子的PSO算法，在该算法中，粒子速度 更新公式中的“个体意识”部分中，粒子不再向自己个体的最佳位置移动，而向着周围 多个粒子中的一个最佳粒子移动；带有微分扰动的PSO算法中引入了微分扰动因子(两 随机粒子位置向量差)代替标准粒子群算法中“个体意识部分” ，以及标准PSO算法与本 文算法进行比较。 4.2 标准测试函数标准测试函数 为了与其他改进算法比较，本文使用五个常用标准测试函数来评价算法的性能，每 函数都使用 10 维搜索空间。函数如下： 1 F1 De Jones function 1 D i ix 1 2 )( 最简单的函数，连续单峰函数。全局极小点在于; 0)0(f 2. F2 Axis parallel hyper-ellipsoid D i ixi 1 2 )( 本函数与 F1 相似，它往往被称为带有权重的Sphere model，同时也是连续的单 峰函数。全局极小点在于; 0)0(f 3. F3 Sum of different Powers )1( 1 )( i D i ix 常用单峰测试函数 全局极小点在于; 0)0(f 4. F4 Rastrigins function 6 D i ixix 1 2 )(14 . 3 2cos(10)(10 在 F1 函数的基础上增加了余弦调制从而产生了很多局部极小。因此本函数为高度多 峰函数，其局部极小是规律分布的。 全局极小点在于; 0)0(f 5. F5 Schwefels function 7 D i ixix )(sin)( 本函数的全局最小在搜索空间几何分布上是较疏远的，它临于次全局最优点，据有 欺骗性。因此对于某些寻优算法更有可能陷入局部极小中。 全局极小点在于;9829.418)9687.420(f 本文的所使用的测试函数的初始化均使用标准初始化范围，但是对于某些函数为使 其展示方便期间，我将其初始化范围缩小为-1,1。对于所有的函数我们都使用 10 维的搜 索空间，表 4.1 中，展示了个函数的初始化范围和搜索空间。 测试函数搜索域初始化范围 F1 De Jones function 1 -5.12 , 5.12 -1 , 1 F2 Sum of different Powers -1 , 1 -1 , 1 F3 Rastrigins function 6 -5.12 , 5.12 -5.12 , 5.12 F4Axis parallel yp