第4卷第3期 智能系统学报 Vol.4 No.3 2009年6月 CAAI Transactions on Intelligent Systems Jn.2009 doi:10.3969/j.issn.16734785.2009.03.001 粒子群优化方法在动态优化中的研究现状 陈杰，潘峰12，王光辉 (L.北京理工大学复杂系统智能控制与决策救育部重，底实验室，北京100O8l;2.Department of Electrical and Computer Engineering,Purdue School of Engincering and Technology,Indiana University-Purdue University Indianapolis,Indianapo- 1is,N46202,USA) 摘要：作为一种基于群智能的并行随机优化方法，粒子群优化算法(PS0)在优化求解问题中体现出了良好的性能. 从提出至今引起了广泛的关注，研究成果也不断涌现.从2000年开始，PS0被用于动态优化问题中.这对P$0的研 究提出了新的挑战，对于动态问题的优化不再是在解空间中找到一个最优点，而是要尽可能地在解空间中跟踪运动 变化的最优点.对目前为止对于P$0在动态环境优化问题的研究内容进行了分析和总结，介绍了针对动态环境优化 问题P$0的改进方法、对环境变化的检测和应对策路、优化性能评价的一系列方法以及各种试验及应用案例. 关键词：粒子群优化方法；动态环境优化；检测策略；应对策略；性能评价 中图分类号：TP391.41文献标识码：A文章编号：16734785(2009)030189-10 Review of the PSO research in dynamic environments CHEN Jie',PAN Feng12,WANG Guang-hui (1.Key Laboratory of Complex System Intelligent Control and Decision of Ministry of Education,Beijing Institute of Technology,Bei- jing 100081,China;2.Department of Electrical and Computer Engineering,Purdue School of Engineering and Technology,Indiana University-Purdue University Indianapolis,Indianapolis,IN 46202,USA) Abstract:Particle swarm optimization (PSO),a parallel random optimization method based on swarm intelligence, exhibits good performance for optimization problems.Since 2000,PSO has been applied to optimization problems in dynamic environments.The challenge with PSO is that the objective is not only to locate an optimum,but also to track that moving optimum as closely as possible.This paper presented the latest developments of PSO in dynamic environments.Various research approaches were reviewed,including improvements in PSO,dynamic change detec- tion,response strategies,performance evaluation and experiments used in researching dynamic problems. Keywords:particle swarm optimization (PSO);optimization in dynamic environment;detection strategy;response strategy;performance evaluation 生物社会学家E.0.Wilson认为，对于生物种 涌现习然而，在现实世界的许多系统中存在很多 群，个体在搜索食物的过程中可以从群体其他成员 动态的问题.所谓动态问题，是指问题中变量的状态 的经验和经历中获取信息，在搜索未知的、不可预测 常常随着时间的变化而变化，可以是随时间离散变 的零星分布的食物时，这种协作行为的优势远大于 化，或随时间连续变化的，甚至有些是交替进行的， 竞争压力.从这种协作模型中得到启示，Kenned和 诸如价格浮动、路径规划、目标识别、动态规划、投资 Eberhart!]于1995年提出了基于群体智能的并行优 分配、数据挖掘等等.动态优化问题，就是为了获得 化算法一粒子群优化方法(particle swarm optimizer, 诸如上述动态问题的最优解随时间的变化轨迹.动 PS0).并且随着十多年的研究进展，研究成果不断 态优化问题对计算智能方法提出了挑战，主要是因 为动态问题中，不再要求算法在搜索空间中寻找最 收稿日期：200808-22. 优值，而是希望它们能在解空间中尽可能的跟踪最 基金项目：高等学校优秀背年教师数学科研奖励计划资助项目 (20010248). 优解的变化轨迹.同遗传算法、进化计算法、进化规 通信作者：潘峰.Email:andropan(@gmal.com 划等优化方法类似，PS0的研究也已建立了一个多
·190 智能系统学报 第4卷 元化、系统化的框架.这也使得难以面面俱到地尽览 PS0搜索策略（式(1）)以外，提出了很多改进搜索 PS0研究现状的各个方面.因此，本文将专注于PS0 策略来提高PSO的性能， 在动态环境下的优化问题的研究现状 1.2针对动态优化问题的PS0改进搜索策略 通过进化计算方法对动态系统进行优化的研究 1.2.1基于参数调节改进 最早可追溯到1966年)，但是直到20世纪80年代 Carlisle使用的自适应PSO(adaptive PS0,AP- 后，才引起学者们广泛的研究兴趣.之后，对各种算 S0)是早期带线性递减惯量因子w的基本PS0算 法的不同改进方法层出不穷.自从1995年P$0被 法，即式(1)中0是随迭代周期递减的线性函数；但 提出后，对$0的改进方法和扩展设计相继涌 是没有采用Va的Lipschitz约束，没有这个约束，粒 现4.最初由Carlisle和Dozier、Eberhart和Shi 子个体的运动很容易进人不稳定的区域.从这个角 从2000年开始将粒子群优化算法应用于解决动态 度来看有益于增加群体多样性，ω随着迭代周期递 跟踪系统问题.动态PS0算法在随机搜索策略基础 减，使得粒子动态系统的参数稳定域变宽，从而保证 上，增加了环境检测过程，并对检测结果做出响应， 了群体将最终收敛到解空间中的某一个极值区 调整动态PS0算法的搜索策略. 域).与前者不同的是，Eberhart]和Hu叨采用a 1动态优化问题中PS0搜索策略 在[0.5+Rand/2]范围内随机取值的方法.作为对 APS0的一种改进，IAPS0o](improved adaptive par- 1.1标准PS0搜索策略 ticle swarm optimizer)定义了一个活跃因子，以控制 标准PS0算法中，每个粒子代表一个可能的 粒子在空间的分布与多样性.Esquivel山提出的一 解，所有的粒子组成群.假设在D维搜索空间中进 种混合PS0(hybrid PSO,HPS0_dym)方法中，采用了 行问题求解，群体由m个粒子组成，S={x,x2, 大变异操作.GA的变异操作对于S0而言，作用和 …,x}.k时刻第个粒子在搜索空间中的位置向量 原理都类似于PS0当中的扰动因子，用以保证系统 为x=（,x2,…,x),i=1,2,…,m,这也是问 的多样性。 题的一个潜在的可能解，其对应的速度向量为= 1.2.2基于距离的改进 (t暗，吃，…，).P0的邻域函数在每一个迭代周 基于对静电场能量的类比，Blackwell2-3)提出 期根据个体自身位置向量、速度向量、个体历史信 了一种“带电粒子”PS0(charged PS0,CPS0).它通 息、群体信息和扰动来产生新的位置状态（如 过额外增加加速因子来模拟实现带电粒子对其他的 式(1).各参数意义如表1所示. 带电粒子排斥效果，借此来保持系统多样性，以应对 t=切·t+c·ru(pa-xa)+ 环境的动态改变问题.这种CP$0进一步扩展为“原 c2·r(pd-), 子核”PS01(atomic PS0,APS0),即只让一半粒子 城=兹+7嫩 (1) (质子)带正电模拟额外的加速因子，而让另外一半 粒子（中子）保持中性不带电.Jatmiko1将CPS0和 表1参数意义 标准PS0相结合，并增加一个排斥函数，以保持系 Table 1 Nomenclature 统多样性的平衡，他这种改进的方法可以应用于对 参数 意义 参数 意义 气味源定位的问题上 加速因子 1.2.3基于信息的改进 创 惯量因子 C1C2 7 速度比例约束因子 TidsTod 在(0,1)之间的随机数 与重置(reet)操作舍弃所有当前信息不同，在 第个粒子k时刻位置向量 m 种群粒子数量 对动态定价问题的研究中，Mullen16)提出了个体最 粒子运动速度向量 D 搜索空间维数 优衰减PS0(p-best decay PSO,PBDPS0).当群体监 个体位置最优值 的 群体位置最优值 测到动态环境中任何变量的变化，并且触发响应操 粒子在搜索空间中不断通过自身信息p和群 作的时候，每个粒子个体最优值P的适应值按照衰 体信息P向目标点运动.这种显式的描述使得算法 退比率进行衰退.和PBDPSO0类似，动态跟踪PSO 中粒子运动的物理含义相对于其他计算智能的方法 (tracking dynamic PS0,TDPSO)在每次迭代中使用 而言更容易理解.但作为一个由若干粒子个体组成 一个蒸发常数(evaporation constant),用来蒸发（递 的群体复杂系统，以及算法中存在的各种待定参数 减)个体最优P和群体最优P:粒子的适应值.这2 和约束条件，使得S0算法在简单的物理框架下， 种算法在更新它们的历史信息中，为保持粒子的简 却又体现出复杂的运动特性.因此除了采用标准的 单行为而不使用集中控制方法；并且二者都通过对
第3期 陈杰，等：粒子群优化方法在动态优化中的研究现状 ·191 群体中的历史信息的衰减来减少信息传递压力，以 而不是静电的原子模型，Blackwell采用量子的模型 维持群体的多样性.Pan1)和Dou1]将模拟退火算 与带电粒子进行类比，提出了多量子群算法(muli- 法中的基于概率的选择机制引入到S0中(PS0 QS0).由于量子微粒的位置由种群吸引子的概率函 wit汕n simulated annealing,PSOwSA),来作为PS0算法 数决定，所以可以避免粒子间相互对比计算，量子原 的选择函数.这样有条件地接受劣于当前解的点，可 子同时具有复杂性低、分布容易控制的优点 以改善群体中粒子间的信息传递方式，减轻信息传 Parrott和Li2]提出的基于种群的PS0(specia- 递压力，有利于多样的保持。 ion-based PS0)基于粒子间的相似性，在每个迭代 1.2.4存在的问题 周期，粒子被自适应划分为不同的子群，每个群体存 在每一次环境发生动态变化时，多样性状态直 在1个主导粒子，并集中在1个“食物”周围.算法 接决定了群体对动态变化的适应能力和潜在的进行 中采用Pax作为一种避免粒子过分集中，该参数 进一步搜索的能力.因此，在对P$0的搜索策略改 限制了每一个种群中允许的最大粒子数.通过这些 进方法中，都注重采用各种方法以改善群体的多样 PS0模型改进机制的引人，可以避免粒子过分集中 性.对于基于参数调节类的方法中，存在的问题是如 收敛到某一个峰值，提高算法对多峰值同时跟踪的 何选择待调节的参数的值.无论是IAPSO中的活跃 能力， 因子，还是HPS0_dyn中的变异参数，作者都没有给 Parrott2继而提出了一种改进的SPS0模型， 出引入系统中的扰动与动态变化的关系.这样在环 引入了在子群中删除冗余重复粒子的机制，以获得 境和问题没有动态变化期间，以及无论动态变化的 更高效的性能。在综合考虑一些现有的多种群进化 情况如何，都采用一种通用型扰动策略和数值，并不 计算方法改进措施的基础上，并以此为出发点， 利于算法性能的提高.对于基于距离的改进方法而 21设计了基于物种群拓展PS0算法，算法中采用 言，“带电粒子”PS0、“原子核”S0或者排斥函数， 多种改进方法：Pmax2]、中子和量子概念[]（保持 都面临着对距离的掌控和平衡问题.在求解的不同 更优多样性的muli-QS0模型方法)、多样性阈值方 阶段和针对不同的问题，对距离的要求是不同的，那 法（触发以最差种群的逆收敛[2]复位过程）、子群 在对问题的先验知识有限的情况下，只能通过试凑 内的多样性阈值（用以判断粒子是否进行粒子重分 的方法来得到参数的设置.对于基于信息的改进方 布操作).通过并行种群机制和一些列的改进方法， 法而言，无论是衰退比率参数，抑或是蒸发常数，对 增加了种群收敛到多个局部最优值而非单一全局最 算法而言都是新引入的人为设定参数，使得算法更 优的能力. 加依赖于参数的调解」 Pam7-]将群体分为3个子群(swam-core evo- 1.3基于种群的策略 lutionary PSO,SCEPS0),以期望兼顾局部搜索和全 多种群进化算法，常被用来在多形态环境下进行 局搜索.其中核心群采用进化规划算法用以在最优 多峰值定位，以及增强在动态环境下的搜索能力，正 点附近形成新的群体，另外2个子群分别负责进行 如Branke提出的自组织群算法2o](self organizing 细化搜索和探索未知区域 8 couts,S0S),Oppeacher和Wineberg2提出的均衡迁 Wang]设计了多种群协同S0(cooperative 移GA(shifting balance GA,SBGA)等.这些算法通过 multi-swarms particle swarm optimizer,CmSPSO), 使用一些较小的子群来搜寻并监控大量的潜在可行 整个群体分为一些子群，各子群分别搜索解空间中 峰值，而另外一些则对未知的区域进行进一步的探 不同的潜在可行解.当2个子群的最优个体距离小 索.基于多种群的概念，多群体的方法被引入到PS0 于排拆半径时，保留着2个群体中的最优个体，然后 中，通过多个粒子群体用来同时跟踪多个最优值 同时对2个群体中的部分个体进行协同随机初始 Blackwell2设计了“多带电粒子”PS0(muli- 化.虽然文章指出排斥半径与求解区域大小成正比， charged PS0,multi-CPS0)和多量子群算法(mili- 与峰数及粒子数目成反比；但是仍然缺乏有效的对 quantum swarm optimizer,multi-QSO).Multi-CPSO 排斥半径的定量计算，群体协同随机初始化的比例 为CPS0的多种群进化的一种改进方法，在多模空 也许要进一步确定。 间中，每个局部极值附近都会分布有一个CPS0子 无论是各种不同的优化方法（如GA、EA、GP、 群，而中性的子群将继续搜索；并且以一定的距离环 PS0),还是针对不同的问题（如动态优化、多目标优 绕在带电粒子周围以保持足够的多样性，以跟踪系 化、约束优化问题等)，多种群是一种广泛采用的思 统的动态变化.同样是在这篇论文中，基于量子模型 路，从计算模型、算法结构和信息传递的拓扑结构等
·192 智能系 统学报 第4卷 方面都进行了有效的改进.但是需要引入额外的机 2.2有环境动态检测操作 制或者参数，来控制种群间的分布，以维持种群间的 有很多方法被设计用来测量描述环境的动态变 多样性，这无疑在算法中引入了新的待调整参数.此 化，而后算法针对该变化做出自己的调整和响应.这 外在考虑多种群思路的同时，应该充分的考虑到计 些方法大多数都是建立在在环境变化是已知的假设 算的复杂性.S0的魅力之一就是其简单而高效的 上，或环境变化至少是可观和可测的，比如可以通过 性能，如果算法过于复杂，就失去了P$0原本的特 重新计算目标函数值来反应.一种比较普遍的描述 色.另一个原因是，算法采用的个体过多，计算过于 环境变化方法是通过计算一个或一些点的适应值， 复杂的话，对于同样的问题在同样的计算时间和消 然后通过同前一时刻的适应值进行比较得到， 耗下，如果采用经过简单的Monte Carlo抽样都可以 Carlisle[6)在搜索空间中随机选择一个点作为 遍历很大的解空间，甚至有可能找到满意的解，那么 环境变化量测点，而且当且仅当它的适应值变化超 就失去了启发式优化方法自身的优势， 过一个设定的范围时，算法才对此做出相应调整. 2环境变化检测方法 Carlisle'6,90提出了多种形式的“岗哨”PS0(sentry PS0,SPS0).顾名思义，“岗哨”粒子意味一种对动 PS0已有的研究表明，PS0对静态环境和动态 态环境带有监督和监控的PS0方法.该方法在搜索 环境的最优化问题均有较好的效果.它能快速收敛 空间中选择一个或者多个特定的点，这些点可以是 到最优值，但往往也付出了多样性丢失的代价，因而 固定的或者遵循某一分布的随机的点，在每次迭代 算法容易提前收敛到局部最优.在优化进化过程中， 中将自己的适应值与历史适应值比较，从而对环境 个体粒子参考群体最优粒子来搜寻目标并趋向于收 变化进行检测.在文献[31]中，Veeramachaneni也同 敛.因此，对于一个损失了多样性的群体而言，如果 样采用的是这种方法，并将这种动态P$0方法应用 没有有效的策略去增加群体的多样的话，传统的 于信息融合.Pan78]也将固定的“岗哨”粒子作为 P$0方法很难对外界环境变化做出有效的反应，并 SCEPSO和PSOwSA算法对动态环境的检测点， 难于重新启动对新环境的探索过程.因此，目前的研 与随机选择一个点的方法不同，H山通过选择 究中，一类方法是在优化过程中采用某些机制来定 群体最优粒子g来作为检测点.综合文献[6,9]， 期判断动态环境变化， Mullen6一方面使用ge作为探测点，另一方面设 2.1无环境动态检测方法 定一个阚值来减小存在于动态定价问题中的噪声的 对于保持种群的多样性研究的一个出发点就是， 影响.Blackwel2选择每个种群中的量子粒子作为 在整个算法计算过程中采用某种机制保持群体的多 探测点.协同进化群优化方法CE$0中，通过重新计 样性，以便使粒子对环境改变做出自适应调整.这种 算第一个子群CRDE的最优个体的目标函数值来探 思路主要的优点在于不需要对探测环境改变做特定 测动态系统的变化].Bid别的方法是对于 的操作，而在算法事先的设计中引入一些机制，使群 冯·诺依曼邻域模型PS0,则监测前5个最优粒子 体在优化过程中始终能保持一定的多样性2，).它 的pet,对于种群PS0(species--based PS0)则记录前 适合于目标函数是连续的小范围变化情况， 5个最优子群中最优个体的P·文献[25]采用的 另外一类不采用检测操作的方法，采用周期的 也是这个策略，Wag]在每个迭代周期内检测每 动态环境响应和多样性激发的策略.Carlisle)使用 个种群的群体最优粒子，来判断是否发生动态变化， 的自适应PS0(adaptive PS0,APS0)中，在经过一定 对于基于种群类的方法，另一种检测方法[2是在每 的周期后，响应动态环境的操作将被激发，这暗示着 个迭代周期里，对每一个P在它们原来的位置上 虽然这种方法对环境不进行监测：但是默认经过一 重新计算每一个粒子的pt适应值.IAPSO将所有 定周期后，环境是有可能产生变化了，而且必须进行 粒子都作为检测点，每个周期所有粒子都要进行一 响应操作，以激发群体多样性.Esquive心l1提出的 次适应度函数计算， hybrid PS0算法假设已知环境的周期性动态变化， 对于无特定环境动态检测的方法多基于一定的 并对这个周期进行相应的检测.在文献[9]中，检测 假设条件，进而设计动态相应策略；但这一类方法的 群体最优粒子g和次优粒子的适应值在20个周 前提是算法对环境的动态变化规律的假设接近实际 期内是否没有改变，如果没有改变则激发响应操作. 的环境变化规律，或者其差别在可接受的范围之内 和这种方法类似的是文献[15]中的方法，它采用监 否则优化的进程就不能充分相应和跟踪系统的变 测群体最优粒子g在20步内是否改变的方法， 化，而失去了动态优化的意义，因此这种方法对问题
第3期 陈杰，等：粒子群优化方法在动态优化中的研究现状 ·193· 的依赖性很强.其优点是这种方法并不依赖于环境 (gm=0),来让所有机器人能够跟踪到环境的动态 的变化是局部的、或者全局的，都能对动态变化做出 变化进行气味源定位.该文中将“带电粒子”CP 反应 S02]和标准P0相结合，并增加了一个排斥函数 而对环境变化需要进行检测或者监测的方法， 来维持群体多样性平衡.CPS0以及排斥函数的使 额外地增加了计算函数适应值的额外负担.这些对 用也有助于对机器人个体自身体积的考虑，避免发 环境的监测方法，尤其是基于个别粒子或者个别点 生碰撞.但是对于“重置”操作而言，简单的替换操 的监测的方法，都基于一定假设.即动态变化是全局 作也意味着丢失搜索过程中收集的已有信息. 性，或者通过个别的监测粒子可以反映环境的动态 文献[6,9]中采用周期性地对整个或部分种群 变化，或者即使环境的动态变化是局部性的变化，群 或最优g粒子进行重新随机分布，来增加群体多 体也能通过检测点得到触发信息.但如果环境只是 样性，抛弃部分目前已知的信息.重新随机分布 在局部产生动态变化（如第5节中局部适应值峰值 (re-randomization)是另一种典型的途径，但是同“重 变化)，尤其是现实生活中的实际问题，就需要进一 置”操作一样，容易过多地失去过去迭代过程中或 步研究对动态环境进行监测的方法， 许有用的信息.而且重新随机分布对信息的丢失更 动态响应策略 加彻底，这也是许多文献中对该方法持怀疑态度的 主要原因.但是其实总体上来说，这种方法依赖于需 与其他计算智能的方法（如EA、EP、GA等）类 要解决的动态问题类型.在很大一部分的动态环境 似，PS0算法的性能很大程度上要依赖于种群在探索 变化问题中，环境的变化是基于上一时刻或空间的 已知与开拓未知能力上二者间的平衡，群体的多样性 环境状态的，而不是完全的全空间内随机变化，过多 对这种平衡的影响至关重要.特别是动态系统中跟踪 丢失过去信息对算法不利；但是如果粒子状态是随 群体的行为，如果失去了多样性，则变得毫无希望了 机的、变化很大或者当前最优状态相关性很小，则这 一般来说，动态系统中多样性问题多通过2种机制来 种重新随机操作可以将群体从过期的信息束缚中解 解决：主动式和响应式).当然，也有一些算法同时 放出来.因此在文献[9,35]中设计的重新随机化的 使用这2种机制，比如一些基于种群的P$0.因此，本 粒子是以一定的比例进行的，而这个比例的大小，直 文主要通过3个方面来分析为解决动态变化的各种 接关系到算法的优化性能，动态环境的变化特性是 调整策略：主动式、响应式以及混合策略 影响其取值大小的原因之一 3.1主动式策略 多群体设计的基本思想就是将整个群体分为一 预处理策略在文中定义为一种不基于对动态变 些子群.每个子群分别关注解空间中不同的潜在可 化进行探测的应对机制，用以实现防止群体收敛过 行解.这种设计本身就是保证群体整体多样性的一 快和保持群体多样性.它可以通过减小选择压力，降 个有效的方法.当环境发生改变时，由于群体中所有 低历史记忆信息的影响，周期性增加系统多样性或 粒子都还没有收敛到一个狭小的区域，从某种意义 采用多种群结构等实现.基于主动式策略的PS0算 上说群体依然能保持着搜索能力.因此第1节中 法能够具有较好的动态寻优效果，尤其是针对动态 PS0基于种群的搜索策略，在动态响应策略意义上， 环境变化小或者缓慢的情况；但是从另一方面来考 多群方法其实也是一种主动式策略.基于种群的 虑，为了保持多样性，群体不能较快地收敛，而且不 S0]没有专门地用以应对动态变化的操作，它通 能充分接近动态的最优值 过重新随机初始化种群中多余的粒子来动态地调整 当系统动态变化时，群体的历史信息就变成了 种群结构和多样性参数.“多带电粒子”PS0[2]的群 相对陈旧的过时信息，在新环境下它有可能就是错 体中，在一个制定半径范围内的最差群体将被重新 误的，这将会导致对其他个体的误导.“重置”(e 随机化处理，使粒子相互之间散开一定的距离.多量 8t)是处理过时信息和保持种群多样性最常用的机 子群算法(muli-QS0)中用量子群体代替了带电粒 制之一，它动态地用一些粒子位置向量或者重新计 子群体以增加多样性，量子群体的位置只依赖于以 算得到的适应值来替代另外一些粒子的位置向量或 群体吸引子为中心的一个概率函数. 适应值.例如每间隔一定迭代周期，就用粒子个体当 为了保持多样性，除了采用多种群的群体结构 前的位置向量代替它们最优个体pP的位置向 设计外，多群体PS0中融合了其他的一些改进方 量p,来减少种群对历史信息的依赖6,4,25,8，列。 法.这些方法中常用的是一些基于环境变化检测的 Jatmiko1]采用重新设定ge4的适应值为初始值 反应式改进操作.这一类的改进方法可以看作是主