针对动态优化问题（Dynamic Optimization Problem，DOP）中所面临的过时记忆和多样性丧失的挑战，提出了一种改进的多种群骨干粒子群优化算法（Multi-swarms Bare Bones Particle Swarm Optimization，MBBPSO）。通过设置环境勘探粒子及时检测环境的变化，避免了错误信息误导种群的进化方向；环境改变后，利用上一个环境搜索的信息初始化新的种群，提高MBBPSO快速追踪到当前环境的优秀解的能力；当种群陷入停滞时，采用新的进化方程以加强粒子的活性和多种群策略维持群体的多样性。仿真实验表明，MBBPSO在解决动态环境问题中具有较强的竞争
陈健,申元霞,纪滨:求解动态优化问题的多种群骨干粒子群算法 2017,53(19) 47 N(u, a), stag(k)< sMar 处理,也会产生过多的计算量,导致算法时间代价增大 x(+1)=1N(,0),sg(>Ma8.nmnl≤0(5) MBBPSO算法多种群思想是,利用多个对等的科群分 N(u, o).otherwise 别对整个鮮空间进行搜索,各个种样搜索不同的解空间 式中sMax为种群最大停滑代数,stag(k)为种群k的停区域,互不下扰独立完成进行进化。各个种群间只需 滞进化代数,x=(Pb()+Gb,()/2,=PbGb 2)要共享a和相应的适应值即可,一方面太除了主辅 种群复杂控制机制的设置,另一方面避免了亡辅种群间 1Mg)Ma时种群依然保持较高的多样性,则粒过多的信息共享,减少了计算量,提高算法的效率。当 子依据传统的 BBPSO方程进化。当种群k停滞代数 种群所寻找到的 gbest接近其他种群所搜寻到的 sgk)>sMa时,此时种群可能陷入局部最优时无法 gbest时候则重新随机初始化 gbest适应度相对较差的 及时跳出,为了增强粒子的活性,采取概率方式实施突种群,避兔了多个种群在同一区域进行搜索,浪费计算 变和反向学习策略。式(5)中0为选择概率,当随机数。资源。 MBBPSO通过两个种群间距离kk来判断两个 小于选择概率时则实施突变策略,香则实施反向学小 种群是否重合。当d12小于设置的最小距离mid 策略。 突变策略针对pes和 gbest进行操作,更新方程则重新随机初始化较差的种群。种群k与种群k全局 的均值和标准差a具体如式(6)所示 最优位置的离如式(8)所示 =(PU,+Gb,)/2 a'=IPbi-G6l (6)式中,D表示问题的维度种群k1与k2之间的距离d Phi=pbi+sgn(rub; -lb 是k1种群的 gbest与k2种群的gbet的欧氏距离。 Gb,=Gb; +sgn(r2)mlub, -ib 3.4 MBBPSO算法流程 式中,n1、r2是[-1,1之间的随机数,n为[0,1之间的 本文所提出的 MBBPSO算法其体流程如下 随机数。通过式(6)对粒子的 pbest和 gbest进行突变。 步骤Ⅰ初始化参檄。设詈种群的数量,每个种群的 γs和g指引粒子的进化方向,当粒子的ms过规模N,问题的维度D,参数λ,环勘粒子数目,最大迭 早的接近est时,导致了高斯采样的标准偏差δ接近代次数 itermαx,最大停滞代数sMax,算法运行次数 于0,粒子停止进化,过多的粒子陷入这种情况则会导致Max,种群间最小距离mind 种群的过早收敛。通过对 pbest和gbes的突变能够直 步骤2初始化所有种群的粒子,评估粒子的适应 接指引粒子朝着新的方向进化,加强粒子的活性,从而值,将粒子当前位置赋值给pt,更新所有种群的 提高种群跳出局部最优的可能,避免了过早收敛 bbest 用反向学习策略的更新方程的均值μ和标准差 步骤3随机初始化所有环勘粒了,评估并记录环勘 如式(7)所示 粒子的适应值 u=(Pbi+(, )/2 步骤4判断算法是否满足结束糸件(迭代次数达到 0=IP6,-(ub, -l6, -Gb, 最大值)。如果满足保存所有种群所搜索到的 gbest,算 上式通过对 gbest采取反向学习策略,利于扩大标准差法结;否则,继续下一步。 σ,加强种群跳出局部最优的能力。 步骤5依据式(5)更新下一代粒子 3.3多种群策略 步骤6更新所有粒子的 pbest和所有种群的 gbest。 多种群策略中多个种群追踪搜索空间中的一组相 步骤7记录所有种群间的距离d。 对优秀解,而不是·个单的群体最优解,而上·代 步骤8判断所有种样间的离是否不大于mind 环境中的局部最优解有可能是下一代环境中的全局最若大于mn.d,则对两个种群中 gbest适应值较差的种 好解,因此多种群策略快速跟踪到新环境中的全局最群进行随机初始化,重新更新该种群的pbes和gbe 优解。 否则执行下一步。 目前多种群策略已经被广泛运用到求解DOP中 步骤9重新评佔所有环勘粒子的适应值,若至少 针对PSO算法采用的大多数是一种主从关系的多种群有一个环勘粒子的适应值发生变化,则记录环境发生 策咯。主种群及其辅种群的搜索方式,搜索域等各有不变化 同,在主从关系多种样策略中,主种样会控制辅种群的 步骤10判断环境是否发生变化。若变化,则依据 搜索方向,范围以及决定辅种群是否重新生成。这种控式(4)初始化所有种群中的粒子;否则执行下一步。 制机制的设置要根据不同的问题进行相应的修改,导致 步骤11判断是否淸足结束条件。是则记录下全局 算法设计过丁复杂,同时主辅种群之间控制信息的传输最优位置及其适应值;否则返回步骤5 48 017,53(19) Computer Engineering and Applications计算机工程与应用 4模拟实验与分析 度下 MBBPSO采用不同策略的离线误差,从图2中可以 4.1实验模型 采取突变和反向学习的算法其离线误差更低,高维环境 经被普遍运用到动态环境测试问题中。在MPB中每。时具有良好的性。图1、图2表明该策略在求解DOP 移动峰函数( Moving peaks benchmark,MPB)已 下提升的性能更高 个峰具有高度、宽度、位置3个基本特征。随着环境发 采用突变与反向操作 生变化,峰的高度、宽度、位置也发生相应的改变。因此 未采用突变与反向操作 MPB只有较强的普适性,可操作性强。MPB的目标函 数如下: 右40 F(, t)=max H1( (9) 1+W>x(!)-x小() 10 式中,H2()W(2)分别表示第个峰在t时刻的高度和 宽度表示第个峰在时刻时第维上的位置。 2.0 iter/10 本文所设置环境,MPB的高度在[30,70之间随机变化 (a)20维度 宽度在[1,12]之间随机变化,峰值的移动距离设置为1。 70 采用突变与反向操作 本文所采取得动态环境的度量指标为平均离线误 未采用突变与反向操作 差( Mean offline error,MFE)。如式(10)所示 r-Ma.z terMan 40 MFE= (10) Maa iterMat iter=l (-h2) 式中,f为第k个环境全局最优位置的适应值,h为第 k个环境时种群所找到的最好解,ier为当前迭代次数, terman为最大迭代次数,为当前运行次数,rMax为 0.5 0 2.5 算法最大运行次数。所有实验环境取每隔5000代改变 一次, iterm-25000,mMax-10,参数λ-0.02,选择 (b)50维度 概率∂-0.01,种群问最短问间距mind-0.,2 图1 MBBPSO釆用不同策略时的当前误差 4.2反向学习策略及突变的效应 采用定变与反向操作 本组实验用于验证反向操作和突变对 MBBPSO算 未采用突变与反向操作 法动态性能的影响。 MBBPSO参数设置:所有种群粒 子为200;种群数量为20;种群规模为10。动态环境改 置为:峰数量为10,维度D∈{1,5,10,20,50}本组实 验具体结果如表1所示 20 表1不同策略时 MBBPSO在不同动态环境中的动态性能 D未采用反向操作与突变 MBBPSO标准 MBBPSO 0.0006+0.0007 0.0006+0.0002 iter/10" 0.1412+0.0451 U.1096+0.0170 (a)20维度 3.3194+1.6662 0.4923+04449 20 10.6851+6.1093 8.1495+10.5055 采用突变与反向操作 60 未采用定变与反向操作 5们 l5.8584+11.5381 9.172+17982 表1屮可以看出,反向学习策略和突变在所有测试 的动态环境中都能取得较高精度的解,表明该措施有利 于算法的寻优,同时除了维度为20的动态环境外,标准 MBBPSO都取得较低的标准差,说明反向学习策咯和 10 突变能够提高算法的鲁棒性。图1为不同维度下的 MBBPSO采用不同策略的当前误差,从图1中可以看 2.0 2.5 iter/10° 出,反向学习和突变能够明显提高算法追踪新环境最优 (b)50维度 解的能力,且高维环境下优势更加明显。图2为不同维 图2 MBBISO采用不同策略时的离线误差 陈健,申元霞,纪滨:求解动态优化问题的多种群骨干粒子群算法 2017,53(19)49 43 MBBPSO与其他算法的动态性能比较 维度呈负相关;另外可以看出 MBBPSO在维度为5的环 43.1不同维度下的实验结果 境屮取得了最小的标准差,在维度为10和50的环境屮 通过 MBBPSO与目前流行的解决动态优化问题都取得了最大的标准差,说明 MBBPSO在求解低维度 的5种算法相比铰,用于说明算法在不同维度环境中的优的DOP中具有良好的鲁棒性,但是随着问题维度的上 劣,其体算法如下:DASA、CPSO、 MEPE CESO 升,算法的鲁棒性随之降低 CPSO-N动态环境设置为维度D∈(5,10,50),峰432不同变化程度和峰数目下的实验结果 数目M为10,环境变化频度为5000,具体实验结果见 本组实验主要探究在不同变化程度下的动态环境 表2。由表2可知, MBBPSO在3个不同维度的动态测中, MBBPSO算法的性能。本组实验对比算法依次为 试环境中取得解的精度明显优于作比较的5个算法,说 APSOP Kamosi"k mQSo'"、FMSO、CPSO"。动态 眀 MBBPSO算法求解DOP问题的能力要优于比较的算环境设置为维度D=5,峰数目M∈(1,5,10,20,30, 法;然而随着动态环境维度的升高 MBBPSO算法的标40.50,100200,环境变化频度f∈(500,1002500 准差也随之升高说明 MBBPSO算法的鲁棒性与问题5000实验结如表3-表6所示, MBBPSO算法运行 表26种算法在不同维度的动态环境中的离线误差和标准差 问题维度 D DASA CPSO MEP CESO CPSO NE MBBPSO 1.69+0.061.73+0.061.62+0.051.68+0.051.31+0.060.0722+0.0302 228+0.07237+00621+07292+0.042121+0080.932+0622 1945+0.2620.07+0.2519.12+0.252480+0.251825+0.323.8396+1.2058 長36种算法在不同峰数目的动念环境中的离线误差和标准差(∫=500) Kamosi mEsO FMSO CPSO MBBPSO 14.81+0.14546+0.3033.67-3.4227.58+0.9413.46+0.70.4728+01131 4.95+0.115.48+0.1911.91-0.7619.45+0.459.63+0.491.0964+0.5221 105.16+0.115.95+0.09962-0.3418.26+0.32942+0.2122679+0.5944 5.81+0.08 6.45+0.16 9.07-0.2517.34+0.308.84+0.2818848+0.1615 6.03+0.076.60+0.14 8.80-0.21 16.39+0.48 8.81+0.24 3.9552+0.7623 6.10+0.086.85+0.13 8.55-0.2115.34+0.458.94+0.2427202+0.9092 505.95+0.067.04+0.108.720.2015.54+0.268.62+0.233.3722+0.1211 1006.08+0.06 8.54-0.16 8.54+0.213.9331+0.1258 2006.20+004752+0.128190.1711.52+0.61828+0.182.8034+0.6915 長46种算法在不同峰数目的动态环境中的离线误差和标准差(=1000 APSO Kamosi Moso FMSO CPSO MBBPSO 2.72+0.042.90+0.1818.60-1.6314.42+0486.77+0.3802291+0.0726 2.99+0.093.35+0.18 6.56-0.3810.59+0.245.30+0.3 0.4565+0.0312 3.87+0.083.94+0.08 5.71-0.2210.40+0.175.15+0.130.9514+0.5571 4.13+0.064.33+0.12.85-0.1510.33+0.135.23+0.181.2727+0.2208 4.12+0.04 4.41+0.1l 1-0.l514.0(6+0.145.13+0.161.4295+.2645 4.15+0.044.52+0.09 ≤.70-0.14 9.85+0.11561+0.1617356+0.7872 504.11+0.034.57+008 5.87-0.13 9.54+0.115.55+0.142.9592+0.6587 1004.26+0.04 8.77+0095.57+0.1228845+D.5296 2004.21+0.024.76+0.0754-0.118.06+0.075.50+0.122.6239+08994 表§6种算法在不同峰数目的动态环境中的离线误差和标准差(′=2500 APSO mOsO FMSO MBBPSO l()+0. .64 20+0.20 5.798+.0331 51.55+0.051.68+0.163.26-0.215.03+0.122.85+0.240.2219+0.031 2.17+0072.33+0.063.120.145.09+0.092.80+0.100.3827+0.2314 2.5l+0.052.79+0.103.58-0.1 5.32+0.08341+0.|40.3510+0.0351 302.61+0.02288+0.093.63-0.105.22+0.083.62+0.1212261+0.0978 2.59+0.032.86+0.073.55-0.105.09+0063.84+D.1246646+.2641 2.66+0.02297+0.063.630.104.99+0.063.86+0.102.0595+0.786 1002.62+0.023.00+0.05358-0.084.60+0.054.10+0.1128603+0.8759 0264+0.02990.043.300.0 4.34+0(14 3.97+0).10 L9285+.6673 50 017,53(19) Computer Engineering and Applications计算机工程与应用 66种算法在不同峰数目的动态环境中的离线误差和标准差(f=5000 APSO Kamosi mEso FMSO MBBPSO 10.53+0.010.56+0.043.82-0.35344+0.112.55+0.120.0483-0.0114 51.05+0.061.06+0.061900.08294+0071.68+0.l10.0891+0.0132 101.31+0031.51+0.04191-0.083.11+0.061.78+0.050.1304+0.0503 1.69+0051890042560103.36+0.062.61+0.070.8578+0.0287 301.78+00220340.062.680.10328+0.05293+0.082.0558+0.6009 1.86+0.022.040.06265-0.08326+0043.14+00824387+01395 1.95+0.02 08002263-0.083.2+0053.26+0.081.7357+0900 001.95+0012.4-0.02252-0.063.06+0043.41+0071.8119+1.0295 200 90+0012.110.032.36-0.05 84+003340+0.061.4917+0.7874 次数为100次,每个环境变化次数为10次,其他5种对 IN,USA,2003:80-87. 比算法的实验值来源文献[22]。 []王东风,孟丽,赵文杰基于自适应搜索中心的骨干粒子群 从表3表4可以看出,在变化频度广较低的动态环 算汰[计算机学报,2016,39(12):2652-2667 境中(50,、1000 MBBPSO取得的最优解精度要优51张震,潘再平,潘晓弘.基于剪枝簧略的骨干粒子群算 法门控制与决策,2015,30(9):1591-1596 于比铰的算法。从表5、表6中可以看出,在变化频度f 6张芳芳,王建军,张勇,少控制参数的分层式骨下粒子群优 较高的动态环境中(=250,5000, MBBPSO在多数 化算法系统工程理论与实践,2015,35(12):3217-3224 测试环境中能够取得最优解的精度最高。实验结果说[刀]雷阳,李树荣,米,等基丁母干粒子群的混合遗传算法 明 MBBPSO对于不同变化频度和峰数目的动态环境的 及其应用[计算机工程与应用,2010,46(36):7-10 寻优性能优秀。此外,从表3~表6看出, MBBPSO算法8] Liu hao, Ding Guiyan, Wang Bing Bare-bones particle 的鲁棒性与峰数目成反比,说明针对较多峰教的动态环 swarm optimization with disruption operator[J] Applied 境中,算法鲁棒性不高;同时大多数測试环境中算法的 Mathematics and Computation, 2014, 238: 106-122 平均标准差要略徴高丁其他5种算法,说明算法稳定性[] Ding Jianli, I iu jin, Chowdhury K R,etal. A particle 要差于作比较的算法。综上所述, MBBPSO求解DOPs swarm optimization using local search and enhancing 问题的寻优能力优秀,但是鲁棒性还有待提高 diversity for continuous optimization J Neurocomputing 2014,137:261-267. [10 Branke J Memory enhanced evolutionary algorithms for 5结束语 changing optimization problems[C]//Proceedings of the 提出了一种基于多种群的改进 BBPSO算法用于解 1999 Congress on Evolutionary Computation( CEC 1999 决动态优化问题。通过设置环勘粒子及时检测环境变 1999,3:1875-1882. 化,避免种群刺着错误的方向进化。在检测到环境变化[1l12 elinka I A survey on evolutionary algorithms dynamics 后,利用上一代环境所提供的有效信息初始化新一代种 and its complexity--Mutual relations, past, present and 群,加强算法快速跟踪到新环境最优解的能力。通过突 future[J]. Swarm and Evolutionary Computation, 2015 变与反向操作赋予粒子适当的活性,采取多种群策略 5:2-14 有效地维持和补充种群多样性避免算法过早收敛。仿2张震,潘再平,潘晓弘.骨干粒子群算法两种不同实现的 真实验表明,本文 MBBPSO算法具有较强的解决动态 优化特性[浙江大学学报:工学版,2015,49(7):1350 1357 问题的能力。 [13]刘黎黎,李国家,注定伟.动态环境下带有非线性效应的 复合粒子群优化算法控制理论与应用,2012,29 参考文献 1253-1262 I Kennedy J, Eberhart R C Particle swarm optimization[chi[14]焦巍,刘光斌动态环境下的双子群PSO算法控制与 Proceedings of Ife International Conference on Neural 决策,2009,24(7):1083-1086 Networks. Piscataway, NJ USA: IEEE Press, 1995: 1492-[15 Ursem R K Multinational GA optimization techniques 1498 in dynamic environments[ C]//Proceedings of Genetic [2 Clerc M, Kennedy J.The particle swarm-explosion, stabilily and Evolutionary Computation Conference, 2000: 19-20 nd convergence in a multidimensional complex space[J]. [16] Li C, Yang S A clustering particle swarm optimizer for IEFF transactions on Evolutionary Computation, 2002 dynamic optimization C/Proceedings of IEEE Congress 6(1):58-73 on Evolutionary Compulation. PiscaTaway, NJ USA: IEEE [3 Kennedy J Bare bones particle swarms Proceedings Prss,2009:439-44 of the IEEE Swann Intelligence Symposium, Indianapolis (卜转108页)