搜索
第2章微粒群优化算法综述第2章微粒群优化算法综述微粒群优化算法（PSO）是一种基于种群的随机优化技术，由Eberhart和Kennedy于1995年提出[1-2]。微粒群算法模仿昆虫、兽群、鸟群和鱼群等的群集行为，这些群体按照一种合作的方式寻找食物，群体中的每个成员通过学习它自身的经验和其他成员的经验来不断改变其搜索模式。Kennedy和Eberhart提出微粒群算法的主要设计思想与两个方面的研究密切相关：一是进化算法，微粒群算法和进化算法一样采用种群的方式进行搜索，这使得它可以同时搜索待优化目标函数解空间中的较多区域。二是人工生命，即研究具有生命特征的人工系统，它采用的主要工具是计算机，主要方法是利用计算机编程模拟。Millonas在用人工生命理论来研究群居动物的行为时，对于如何采用计算机构建具有合作行为的群集人工生命系统，提出了五条基本原则[13]：（1）邻近原则（ProximityPrinciple）：群体应该能够执行简单的空间和时间运算。（2）质量原则（QualityPrinciple）：群体应该能感受到周围环境中质量因素的变化，并对其产生响应。（3）反应多样性原则（PrincipleofDiverseResponse）：群体不应将自己获取资源的途径限制在狭窄的范围之内。（4）稳定性原则（PrincipleofStability）：群体不应随着环境的每一次变化而改变自己的行为模式。（5）适应性原则（PrincipleofAdaptability）：当改变行为模式带来的回报是值得的时候，群体应该改变其行为模式。其中4、5两条原则是同一个问题的两面。微粒群系统满足以上五条原则。近十余年来，针对微粒群算法展开的研究很多。目前国内外已有多人从多个方面对微粒群算法进行过综述[14-27]；并出现了多本关于微粒群算法的专著[11,28-29]和以微粒群算法为主要研究内容的博士论文[3,30-36]。1第2章微粒群优化算法综述2.1来源和背景为了说明微粒群优化算法的发展和形成背景，首先介绍一下早期的简单模型，即Boid（Bird-oid）模型。这个模型是为了模拟鸟群的行为而设计的，它也是微粒群优化算法的直接来源。一个昀简单的模型是这样的：每一个鸟的个体用直角坐标系上的点表示，随机地给它们赋一个初速度和初位置，程序运行的每一步都按照“昀近邻速度匹配”规则，使某个个体的昀近邻点的速度变得与它一样，如此迭代计算下去，很快就会使得所有点的速度变得一样。因为这个模拟太简单而且远离真实情况，于是在速度项中增加了一个随机变量，即在迭代的每一步，除了满足“昀近邻速度匹配”之外，每一步速度还要添加一个随机变化的量，这样使得整个模拟看起来更为真实。Heppner设计了一个“谷地模型”来模拟鸟群的觅食行为[37]。假设在平面上存在一个“谷地”，即食物所在地，鸟群开始时随机地分散在平面上，为了寻觅食物所在地，它们按照如下规则运动：首先假设谷地的位置坐标为，单个鸟的位置和速度坐标分别为和，用当前位置到谷地的距离：),(00yx),(yx),(vyvx2020)()(yyxxs−+−=（2-1）来衡量当前位置和速度的“好坏程度”，离谷地的距离越近，则越“好”，反之越“坏”。假设每一个鸟具有记忆能力，能够记住曾经达到的昀好位置，记作pBest，并记a为系统规定的速度调节常数，rand为一个[0,1]间的随机数，设定速度项按照下述规则变化：a*randvyvypbestyya*rand-vyvypbestyya*randvxvxpbestxxa*rand-vxvxpbestxx+==+==则，如果则如果则，如果则如果然后假设群体之间可以以某种方式通讯，每个个体能够知道并记住到当前为止整个群体的昀好位置，记为gBest，记b为系统规定的速度调节常数，Rand为一个[0,1]间的随机数，则速度项在经过以上调整后，还必须按照下述规则变化：b*Randvyvygbestyyb*Rand-vyvygbestyyb*Randvxvxgbestxxb*Rand-vxvxgbestxx+==+==则，如果则如果则，如果则如果在计算机上模拟的结果显示：当a/b较大时，所有的个体很快地聚集到“谷2第2章微粒群优化算法综述地”上；反之，微粒缓慢地摇摆着聚集到“谷地”的四周。通过这个简单的模拟，发现群体能很快地找到一个简单函数（2-1）的昀优点。受该模型启发，Kennedy和Eberhart设计出了一种演化优化算法，并通过不断的试验和试错，昀后将此算法的基本型固定为：)(**2)(**2xgbestxRandxpbestxrandvxvx−+−+=（2-2）vxxx+=（2-3）其中符号的意义同上。研究者认为每个个体被抽象为没有质量和体积，而仅仅具有速度和位置的微粒，故将此方法称为“微粒群”优化算法。开始微粒群体初始化微粒适应度评价计算个体历史昀优位置计算群体历史昀优位置根据速度和位置更新方程更新微粒速度和位置终止条件满足？结束否是图2-1微粒群优化算法流程图据此，可对微粒群算法小结如下：微粒群算法是一种基于种群的搜索过程，其中每个个体称作微粒，定义为在D维搜索空间中待优化问题的潜在解，保存有其历史昀优位置和所有微粒的昀优位置的记忆，以及速度。在每一演化代，微粒的信息被组合起来调整速度关于每一维上的分量，继而被用来计算新的微粒位置。微粒在多维搜索空间中不断改变它们的状态，直到到达平衡或昀优状态，或者超过了计算限制为止。问题空间的不3第2章微粒群优化算法综述同维度之间唯一的联系是通过目标函数引入的。很多经验证据已经显示该算法是一个非常有效的优化工具。微粒群优化算法的流程图见图2-1。以下给出微粒群算法的比较完整的形式化表述。在连续空间坐标系中，微粒群算法的数学描述如下：设微粒群体规模为N，其中每个微粒在D维空间中的坐标位置向量表示为，速度向量表示为，微粒个体昀优位置（即该微粒经历过的昀优位置）记为，群体昀优位置（即该微粒群中任意个体经历过的昀优位置）记为。不失一般性，以昀小化问题为例，在昀初版本的微粒群算法中，个体昀优位置的迭代公式为：),,,,,(21iDidiiixxxxXLL=→),,,,,(21iDidiiivvvvVLL=→),,,,,(21iDidiiippppPLL=→),,,,,(21gDgdgggppppPLL=→⎩⎨⎧=+++其他，，如果)()(,,1,1,1,dtititidtidtipPfXfxp（2-4）群体昀优位置为个体昀优位置中昀好的位置。速度和位置迭代公式分别为：)(**)(**,,2,,1,1,dtidtgdtidtidtidtixpRandcxprandcvv−+−+=+（2-5）dtidtidtivxx1,,1,+++=（2-6）由于初始版本在优化问题中应用时效果并不太好，所以初始算法提出不久之后就出现了一种改进算法[38]，在速度迭代公式中引入了惯性权重ω，速度迭代公式变为：)(**)(**,,2,,1,1,dtidtgdtidtidtidtixpRandcxprandcvv−+−+=+ω（2-7）虽然该改进算法与初始版本相比复杂程度并没有太大的增加，但是性能却有了很大的提升，因而被广泛使用。一般的，将该改进算法称为标准微粒群算法，而将初始版本的算法称为原始微粒群算法。通过分析PSO算法的收敛行为，Clerc介绍了一种带收缩因子的PSO算法变种[4]，收缩因子保证了收敛性并提高了收敛速度。此时的速度迭代公式为))(**)(**(,,2,,1,1,dtidtgdtidtidtidtixpRandxprandvv−+−+=+φφχ（2-8）显然，迭代公式（2-7）和（2-8）并无本质区别，只要适当选取参数，二者完全相同。微粒群算法有两种版本，分别称为全局版本和局部版本。在全局版本4第2章微粒群优化算法综述中，微粒跟踪的两个极值为自身昀优位置pBest和种群昀优位置gBest。对应的，在局部版本中，微粒除了追随自身昀优位置pBest之外，不跟踪种群昀优位置gBest，而是跟踪拓扑邻域中的所有微粒的昀优位置nBest。对于局部版本，速度更新公式（2-7）变为：)(**)(**,,2,,1,1,dtidtldtidtidtidtixpRandcxprandcvv−+−+=+ω（2-9）其中为局部邻域中的昀优位置。lP→图2-2微粒迭代示意图每一代中任意微粒迭代的过程见图2-2所示。从社会学的角度来看速度迭代公式，其中第一部分为微粒先前速度的影响，表示微粒对当前自身运动状态的信任，依据自身的速度进行惯性运动，因此参数ω称为惯性权重（InertiaWeight）；第二部分取决于微粒当前位置与自身昀优位置之间的距离，为“认知（Cognition）”部分，表示微粒本身的思考，即微粒的运动来源于自己经验的部分，因此参数c1称为认知学习因子（也可称为认知加速因子）；第三部分取决于微粒当前位置与群体中全局（或局部）昀优位置之间的距离，为“社会（Social）”部分，表示微粒间的信息共享与相互合作，即微粒的运动来源于群体中其他微粒经验的部分，它通过认知模拟了较好同伴的运动，因此参数c2称为社会学习因子（也可称为社会加速因子）。自从PSO算法被提出以来，由于它直观的背景，简单而容易实现的特点，以及对于不同类型函数广泛的适应性，逐渐得到研究者的注意。十余年来，PSO算法的理论与应用研究都取得了很大的进展，对于算法的原理5第2章微粒群优化算法综述已经有了初步的了解，算法的应用也已经在不同学科中得以实现。PSO算法是一种随机的、并行的优化算法。它的优点是：不要求被优化函数具有可微、可导、连续等性质，收敛速度较快，算法简单，容易编程实现。然而，PSO算法的缺点在于：（1）对于有多个局部极值点的函数，容易陷入到局部极值点中，得不到正确的结果。造成这种现象的原因有两种，其一是由于待优化函数的性质；其二是由于微粒群算法中微粒的多样性迅速消失，造成早熟收敛。这两个因素通常密不可分地纠缠在一起。（2）由于缺乏精密搜索方法的配合，PSO算法往往不能得到精确的结果。造成这种问题的原因是PSO算法并没有很充分地利用计算过程中获得的信息，在每一步迭代中，仅仅利用了群体昀优和个体昀优的信息。（3）PSO算法虽然提供了全局搜索的可能，但是并不能保证收敛到全局昀优点上。（4）PSO算法是一种启发式的仿生优化算法，目前还没有严格的理论基础，仅仅是通过对某种群体搜索现象的简化模拟而设计的，但并没有从原理上说明这种算法为什么有效，以及它适用的范围。因此，PSO算法一般适用于一类高维的、存在多个局部极值点而并不需要得到很高精度解的优化问题。目前针对PSO算法开展的研究工作种类繁多，经归纳整理分为如下八个大类：（1）对PSO算法进行理论分析，试图理解其工作机理；（2）改变PSO算法的结构，试图获得性能更好的算法；（3）研究各种参数配置对PSO算法的影响；（4）研究各种拓扑结构对PSO算法的影响；（5）研究离散版本的PSO算法；（6）研究PSO算法的并行算法；（7）利用PSO算法对多种情况下的优化问题进行求解；（8）将PSO算法应用到各个不同的工程领域。以下从这八大类别着手，对PSO算法的研究现状作一梳理。由于文献太多，无法面面俱到，仅捡有代表性的加以综述。2.2理论分析目前对微粒群算法开展的理论研究主要集中在微粒群算法的原理方面，即微粒之间是如何相互作用的，为什么微粒群算法对于很多优化问题是有效的，而对于有些问题则效果不是很明显。具体来说，这个问题的研究又分为三个方面，其一是单个微粒的运动轨迹；其二是收敛性问题；其6第2章微粒群优化算法综述三是整个微粒系统随时间的演化和分布。对简化微粒行为的第一个分析由Kennedy给出[39]，通过仿真给出了一系列设计选择的情况下不同的微粒轨迹。对简化微粒群算法的第一个理论分析由Ozcan给出[40-41]，作者在文中指出，在一个简化的一维PSO系统中，微粒沿着一条由正弦波定义的路径前进，随机确定其幅度和频率。但是，他们的分析仅限于没有惯性权重的简