袁亦川，杨 洲，罗廷兴，秦 进

(1．贵州大学计算机科学与技术学院，贵阳550000; 2．贵阳市信息产业发展中心，贵阳550000)(*通信作者电子邮箱175385745@qq．com)

0 引言

许多现实世界中的优化问题都表现出动态性质，即优化的目标函数或待求解的问题会随时间而发生(随机)变化。例如，目标识别过程中，敏感组件的检测性能会受到周围环境的影响和制约;调度问题中，新工件可能随时到达，机器可能发生随机故障或逐渐磨损，资源量会随时间不断变化，原材料的性能可能会随时间发生变化;金融贸易模型中的市场环境可能会突然改变［1－2］;因此，研究适合于求解这些普遍存在于现实世界的动态优化问题(Dynamic Optimization Problem，DOP)的方法和算法有重要的现实意义。

一般来说优化问题可以分为两类:静态优化问题(Static Optimization Problem，SOP)和动态优化问题(DOP)。其中，静态优化问题有统一的定义，可以认为静态优化问题是只有一个解的单决策问题，然而对DOP目前尚且没有一致的定义。简言之，在动态优化问题中，其最优解的位置会随时间推移而改变。

求解DOP的优化算法要求能够在动态环境中搜索到最优解［3－4］。尽管传统演化算法(Evolutionary Algorithm，EA)如粒子群算法、差分进化算法、人工免疫算法等在求解静态优化问题上取得了很好的效果，但求解DOP需要对传统EA进行相关的改进。

目前，动态优化算法主要可以分为环境变化后增加多样性的方法、运行过程中始终保持多样性的方法、基于记忆机制的方法、多种群方法和基于预测机制方法5类［5］。其中，多种群方法主要应用在一类具有多个局部最优(多峰)函数的动态优化问题上，而多峰函数的优化在现实中较为普遍。

对此国内外许多学者将多种群方法与经典演化算法相结合后应用到对动态优化问题的求解上。如:Yang等［6］使用了分层聚类的方法把种群分成多个子种群，该方法是子种群初始粒子依据在适应值曲面的分布自动产生，而不是依赖于像kmeans聚类方法中的参数k;Brest等［2］提出了自适应参数的多种群差分进化(Self-Adaptive Differential Evolution，jDE)算法，控制参数F和Cr能够有效地自适应;姜立强等［7］提出改进差分进化(Modified Differential Evolution，MDE)算法，该算法将种群分为侦测和搜索两个种群，但该算法过于简单，在求解多峰函数时极易陷入局部最优;陈健等［8］提出多种群骨干粒子群优化 (Multi-swarms Bare Bones Particle Swarm Optimization，MBBPSO)算法，该算法通过设置环境勘探粒子及时检测环境的变化，环境变化后，利用上一个环境搜索的信息初始化新的种群，当种群陷入停滞时，采用新的进化方程以加强粒子的活性和使用多种群策略维持种群的多样性，但该算法在求解大规模动态优化问题上表现不佳;Ali等［9］提出基于成功率的自适应的种群动态衰减的部落差分进化算法(adaptive successbased Tribal DE algorithm with dynamic population Reduction，sTDE-dR)算法，该算法采用自适应的策略来控制F、CR参数，并提出多种群竞争策略。算法中种群的整体规模逐渐减小，各子种群通过比较平均误差来确定各子种群在下一代保存多少，以此来保证自适应的最优策略在最优子种群中引导搜索最优解和更充分地利用有限的评价代价。

虽然国内外学者对改进EA求解DOP作出了很多工作，但是在平衡算法的搜索操作和寻优操作方面，在搜索过程中维持种群的多样性方面，在算法跳出局部最优方面以及在快速追踪移动的最优解方面依然有很多不足。

本文在已有研究的基础上，提出一种求解动态优化问题的多种群竞争差分进化算法(Differential Evolution algorithm with Competitive Strategy based on multi-population，DECS)。该算法将一个子种群作为侦测种群，采用新的侦测方法;其余多个子种群作为搜索种群，通过各搜索种群相互竞争来增强种群多样性，且更充分地利用了有限的评价代价;在搜索种群搜索过程中，保证在一个局部最优邻域内有且仅有一个搜索种群进行寻优操作。数值算例表明了该方法的有效性和可行性。

1 相关工作

1．1 动态优化问题的定义和描述

在文献［10－12］中，DOP被定义为在一段时间内的一系列SOP，即每个动态函数由一个基本静态函数和由一组动态规则应用到该基函数所获得的动态函数序列组成。定义如下:

定义1 假设ψ为搜索空间，向量x∈ψ，时间t∈T，一个动态函数DFt描述如下:

其中:fb0(x)是带有k个可变化特征的基准静态函数;gt是在t－1时刻动态适应度函数的参数函数;cht是在t时刻基函数所有可能的改变集合;st是t时刻特征的改变程度，最后求得t时刻新的评价值。

定义2 函数gt可以被描述为:

在静态环境下，传统EA中种群个体不断迭代而逐渐集中在搜索空间的一个固定解或者搜索空间的一个有限区域，正常而不是过早地收敛对于传统EA处理静态优化问题是必需的，但是，对于动态优化问题而言，一旦收敛，那么当新的环境到来时，EA就失去了探索新的区域所需要的多样性，从而不能追踪到在新的环境下已经变化了的最优解，这种收敛趋势限制了EA算法的性能;因此在动态优化问题的求解过程中，对不断变化的最优解的快速跟踪甚至比找到最优解本身更有意义［5］，求解DOP的主要挑战在于维持种群多样性和追踪移动的最优解。

而基于群体实参数的差分进化(DE)算法［13－14］是目前最好的随机优化算法之一，该方法原理简单、受控参数少、鲁棒性强，通过启发式搜索策略具有自组织性、自适应性及并行性等特点，并且不要求目标函数连续、可微等信息，具有极好的全局搜索能力［15］。基于此，本文通过改进差分进化算法来求解DOP。

1．2 量子个体

Blackwell等［16］认为所有个体不一定要全部按照相同的规则产生，因此他们提出一种类似于量子机制的量子粒子规则，在种群中最优个体位置的邻域内产生新的个体。

在全局最优位置Vg处，以半径rcloud的球体，种群下一代产生规则如下:

这种方法在rcloud范围内，会有较高的可能性生成靠近最优值的点。此外，随着维度D的增加，可能性也会增加。

2 多种群竞争的差分进化算法

2．1 侦测环境变化

如何及时监测环境变化是任何进化算法求解DOP必须解决的首要问题，一般是通过设置监测点来实现。目前常用的监测点选取方法是随机选取搜索种群中任意个体或同时选择搜索种群中最优个体和次最优个体［17］，当发现监测点的评价值改变时则判断为环境改变，但这两种方法都不能及时感知环境变化。

DECS专门设定一个种群作为侦测种群，该种群中任何一个个体的评价值发生变化，都将判定为环境发生改变。

而针对环境中维度改变的情况，只要侦测种群发现自身维度与环境维度不一致，则判定为环境发生改变。

2．2 排除规则

使用多个种群来求解动态优化问题需要各个子种群能有效地分开和避免寻找相同的区域，确保没有任意两个种群追踪同一个局部最优位置的邻域(峰)［17］。

每一次迭代，将各搜索种群中评价值最优个体依次进行比较，如果任意两个搜索种群中最优个体的欧氏距离小于预先定义的阈值rexcl，则有可能两个搜索种群在同一个局部最优位置的邻域寻优。那么，将这两个搜索种群中最优个体的评价值进行比较，将较好评价值个体所在的搜索种群留下，另一个搜索种群重新初始化。

对排斥半径rexcl的取值按照以下的经验规则产生:假设所有的峰均匀分布在整个搜索空间，那么

其中:X为搜索范围，peaks为在环境中峰的个数，D为搜索向量的维度。

算法在同一个峰只保留一个最优种群，将其他种群重新初始化，以便充分利用有限的评价代价和提高种群的多样性。

2．3 种群竞争机制

每迭代m次，就将n个搜索种群中最优个体的评价值进行比较，保留较优个体所在的搜索种群，剩余n－1个搜索种群重新初始化，在不断迭代中，多次竞争。

因为对动态优化问题的求解，总的评价次数是预先设定的，而所有搜索种群在独立寻优的过程中，各搜索种群的每一次迭代都需要花费一定的评价代价，如果陷入局部最优的种群继续迭代，会造成评价代价的浪费。但是将竞争失败的种群重新初始化后，就可以将其花费的评价代价用在对环境的搜索上。一旦其找到更优的局部最优区域，那么，其他搜索种群又将重新初始化。

这种竞争机制保持一个搜索种群进行寻优操作，n－1个搜索种群进行环境探索操作，各搜索种群通过竞争决定是寻优操作或探索操作。以此确保在搜索最优解的同时增加了种群的多样性，从而有效地解决了种群容易陷入局部最优的问题。

2．4 DECS 描述

基于以上描述，本文提出的多种群竞争差分进化算法的主要步骤如下:

步骤1 初始化。设置算法维度D，设置算法总评价次数，种群初始化范围［Xmin，Xmax］，峰的数量 peaks，初始化侦测种群P0，计算P0的评价值向量f(P0)，初始化各搜索种群P1，P2，…，Pn，算法迭代次数 iter← 0。

步骤2 侦测环境变化算法。

1)若环境发生维度变化，则更新维度参数D，并将所有搜索种群 P1，P2，…，Pn重新初始化，iter←0，跳转步骤8;

2)若侦测种群的评价值向量中任何一个值发生变化，则以变化后的评价值向量更新变化前的评价值向量，并将所有搜索种群 P1，P2，…，Pn重新初始化，iter← 0，跳转步骤 8。

步骤3 对n个搜索种群执行变异操作。

步骤4 对n个搜索种群执行交叉操作。

步骤5 对n个搜索种群执行选择操作。

步骤6 排除算法:

1)计算最小排除距离 rexcl的值;计算 P1，P2，…，Pn种群的评价值向量，并找出其中最优的个体besti(i=1，2，…，n);

2)计算种群中最优个体的欧氏距离:rj=d(besti，best((i+1)modn))，j=1，2，…，n。如果rj＜ rexcel，则计算f(besti)与f(best((i+1)modn))，保留 besti，best((i+1)modn)中较优评价值所在搜索种群，另一个搜索种群重新初始化。

步骤7 竞争算法:每迭代m次，计算P1，P2，…，Pn种群中最优个体评价值f(best1)，f(best2)，…，f(bestn);保留f(best1)，f(best2)，…，f(bestn)中最优评价值所对应的种群，其他种群重新初始化;并对保留的唯一种群的下一代执行量子个体生成机制。

步骤8 迭代次数iter←iter+1，如果达到总评价次数，则算法结束;否则，跳转步骤2。

图1 多种群竞争差分进化算法的流程Fig．1 Flowchart of multi-population-based competitive differential evolution algorithm

3 实验设置与测试函数

仿真实验环境为 Windows 10系统，其中 CPU为 Inter Core i5-4590/3．30 GHz，4核，内存为 8 GB，实验使用 Matlab进行编码。

为了验证算法的性能，这里选取了IEEE CEC 2009提出的标准动态优化问题集 GDBG benchmark进行测试，此benchmark构建了峰的位置、高度、宽度、维度会变化的动态环境，具体函数形式见文献［18］，并将计算结果与复位粒子群优化(restart Particle Swarm Optimization，rPSO)算法［19］(经典算法PSO求解动态环境问题的改进算法，一旦环境变化，种群将重新初始化)、人工免疫算法(Artificial Immune Network for Dynamic optimization，Dopt-aiNet)算法［19］和 MDE 算法［7］进行比较。GDBG中的测试函数见表1。其中F1函数为Rotation peak函数，具体形式见文献［18］，F2函数是Sphere函数的混合函数，F3函数是Rastrigin函数的混合函数，F4函数是Griewank函数的混合函数，F5函数是Ackley函数的混合函数，F6函数是表1中所有函数的混合函数。

表1 测试基准函数Tab．1 Details of the basic benchmark functions

对GDBG benchmark中每一个测试函数进行7种改变方式，包括小步改变(T1)、大步改变(T2)、随机改变(T3)、混沌改变(T4)、周期性改变(T5)、带噪声的周期性变化(T6)和维度改变(T7)，以此模拟了49个标准动态变化问题。其中仅F1是求最大值问题，且需要分别求解10个峰和50个峰两种情况;F2～F6函数都是求最小值问题。

对于49个动态问题中每一个动态问题，独立运行5次，总评价次数为7．5E06，每评价1．5E05次环境改变，因此单个问题每次运行时环境改变10次。

每当环境改变时，记录本次变化期间的离线误差:

其中:f(xbest(t))为当前环境中理论最优评估值，f(x*(t))为当前算法求解的实际最优评估值。

当一个动态问题达到总评价次数时，计算算法的平均离线误差期望(Average mean，Avg_mean)、平均离线误差标准差(STandard Deviation，STD)。计算公式见文献［18］。

DECS参数如表2所示，rPSO算法、Dopt-aiNet算法和MDE算法的参数设置分别见文献［7，18－19］。

表2 DECS参数Tab．2 Parameter settings for DECS

4 实验结果

表3～9给出了三种算法在GDBG benchmark上的测试结果，包括平均离线误差期望(Avg_mean)、平均离线误差标准差(STD)，表中较优实验结果用加粗字体表示。

图2～3表示在部分问题上，DECS一次独立求解的离线误差收敛图、算法实际最优评价值和理论最优评价值的收敛图。其中:实线表示实际最优评价值，虚线表示理论最优评价值;横轴为评价次数，一次独立运行的评价次数为1．5E06，每评价1．5E05次环境改变。

表3 10个峰的F1函数的Average mean和STD性能值Tab．3 Average mean and STD for F1 with 10 peaks

表4 50个峰的F1函数的Average mean和STD性能值Tab．4 Average mean and STD for F1 with 50 peaks

表5 F2函数的Average mean和STD性能值Tab．5 Average mean and STD for F2

表6 F3函数的Average mean和STD性能值Tab．6 Average mean and STD for F3

表7 F4函数的Average mean和STD性能值Tab．7 Average mean and STD for F4

表8 F5函数的Average mean和STD性能值Tab．8 Average mean and STD for F5

表9 F6函数的Average mean和STD性能值Tab．9 Average mean and STD for F6

图2 不同动态优化问题的离线误差收敛趋势Fig．2 Convergence trend of off-line error for different DOP

图3 不同动态优化问题的评价值收敛趋势Fig．3 Convergence trend of evaluation value for different DOP

实验中主要衡量的评估量是平均离线误差期望和平均离线误差标准差，平均离线误差期望为离线误差函数Elast(t)在多次独立运行过程中多次动态变化的离线误差期望，能够有效衡量算法对动态环境问题的求解性能。平均误差标准差则反映算法在求解DOP时的鲁棒性。

从表3～表9中可以看出，在10个峰F1函数的T1～T4和T7变化问题，50个峰F1函数的T2、T3、T7变化问题，F2函数的T3、T5变化问题，F3函数的T1～T7变化问题，F4函数的T2、T3、T5变化问题，F5、F6函数的T1～T7变化问题上DECS的平均误差期望小于Dopt-aiNet算法。这些结果统计表明DECS在49个问题中有34个问题的求解结果优于DoptaiNet算法，49个问题中所有问题的求解结果优于rPSO算法和MDE算法。

从以上实验结果看出，DECS在F3函数、F5函数、F6函数上所有变化的求解都要优于Dopt-aiNet算法、rPSO算法、MDE算法。F3函数的基准函数为Rastrigin函数，其有多个局部最优值，是高度多模态的多峰函数，但多个峰的最小值位置是规律分布的。F5函数的基准函数为Ackley函数，其图像特征是外部区域有多个局部最小值邻域，中心区域有一个较大邻域的全局最优位置，且相对全局最优位置的邻域来说，外部区域几乎是平坦的。F6函数的基准函数具有5个函数的众多特征。这说明，DECS能够有效求解环境中特征明显的动态优化问题。

DECS在F2函数和F4函数上所有变化的求解都是只有3个变化超过Dopt-aiNet算法，所有变化超过rPSO算法和MDE算法。F2函数的基准函数为 Sphere函数，其在［－5．12，5．12］内是一个连续的、凸的、单峰的球面函数，尽管本实验中该函数搜索范围［－100，100］较大，但该函数相比本实验中其它函数却不具有较大的复杂性。F4函数的基准函数为Griewank函数，其有许多广泛分布的局部最小值区域，而且是规律分布的，这种复杂性在搜索范围放大的情况下会体现出来，本实验中该函数的搜索范围［－100，100］远大于Rastrigin函数的搜索范围［－5，5］，其峰的数量也远远大于Rastrigin函数峰的数量。实验数据表明，对于F2函数问题，DECS能够找到最优解的邻域，但Dopt-aiNet算法却具有更好的求解性能。而对于F4函数这种具有较大复杂性的环境，DECS性能优于rPSO算法和MDE算法，但和Dopt-aiNet算法性能相近，因此DECS在较大复杂性的环境中不具备明显优势。

DECS在10峰的F1函数的7个变化中有5种变化超过Dopt-aiNet算法，全部超过rPSO算法和MDE算法，但对于50个峰的F1函数，之所以在T1、T4变化上DECS效果要弱于Dopt-aiNet算法，那是因为相对于50个峰，实验用的搜索种群数量太少。但由于总评价次数是一定的，搜索种群数量太多，会加大对评价代价的消耗，因此搜索种群并不是越多越好。

对于49个函数中T1～T7的变化问题，在T3变化中的7个函数问题中，DECS比Dopt-aiNet算法、rPSO算法、MDE算法都要好;因为T3变化是随机变化，GDBG benchmark中T3变化的环境变化偏置量为一个服从正态分布的随机量与一个常数的乘积。这说明DECS能够有效求解环境随机变化的动态优化问题。

在T2变化的7个函数问题中，DECS比Dopt-aiNet算法在6个问题中更好，比rPSO算法和MDE算法都要好;T2变化为环境大步的改变，这说明DECS能够有效求解环境变化明显的动态优化问题。

在T5、T7各自的7个函数变化问题中，DECS比DoptaiNet算法都是在5个问题上更好，比rPSO算法和MDE算法都要好。这说明DECS在求解周期的变化问题和维度变化问题上具有较好的性能。

在T1、T4、T6各自的7个函数变化问题中，DECS比DoptaiNet算法分别在3个、3个和4个问题上表现更好，比rPSO算法和MDE算法都要好，实验表明在这类问题上，DECS与Dopt-aiNet算法性能相差不多。这说明DECS在环境小步变化、混沌变化和带噪声的周期变化等问题上不具备明显优势。

在上述问题中，DECS之所以在基函数环境特征较明显的动态优化问题上具有良好性能，是因为其能快速感知环境变化并且在寻优过程中仍有较好的种群多样性。而对环境随机变化、大步变化、周期性变化和维度变化等问题上也具有良好性能，是因为DECS引入竞争机制后，平衡了种群的探索与寻优，使算法具有非常好的环境探索能力。

在DECS与Dopt-aiNet算法比较中，DECS在优于DoptaiNet算法的34个问题中有23个问题的平均误差标准差优于Dopt-aiNet算法，这说明在求解49个动态优化问题中，DECS不仅平均性能超过Dopt-aiNet算法，而且具有较好的鲁棒性。DECS与MDE算法比较过程中，DECS在所有49个问题中的平均误差期望均优于MDE算法，而在这49个问题中有41个问题的平均误差标准差要优于MDE算法;在DECS与rPSO算法的比较中，DECS在所有动态问题中的平均误差期望均优于rPSO算法，而在49个问题中有48个问题的平均误差标准差要优于rPSO算法，这说明在求解49个动态优化问题中，DECS不仅平均性能远远超过rPSO算法和MDE算法，而且具有更好的鲁棒性。

从图3看出一旦环境变化，环境中理论最优的评价值也变化，而DECS的实际最优评价值却能够及时监测并且快速追踪。由此看出DECS具备求解动态问题的能力。

5 结语

本文提出一种称为DECS的改进算法来求解DOP，并在统计学上表明是有效的。该算法在传统的DE算法框架内引入了多种群方法和竞争策略，使用多个种群并行搜索来增强搜索过程中的多样性。同时，多个搜索种群之间互相竞争，大大提高了算法的搜索能力，更高效地利用了有限的评估代价。排除规则和量子个体生成机制使搜索种群在搜索空间上具有更好的种群多样性;而独立的侦测种群，能够迅速感知环境变化。

实验结果统计表明，DECS与其他演化算法相比表现出更好的优化性能和更好的鲁棒性。未来的工作可以使搜索种群之间互相交流，淘汰掉的个体往往具有更优的多样性;也可以使用交叉概率、放缩因子与变异策略自适应地调整来提高算法的性能。