全局与局部模型交替辅助的差分进化算法

于成龙，付国霞，孙超利，张国晨

（太原科技大学计算机科学与技术学院，太原 030024）

0 概述

随着科学技术的快速发展，工农业生产、国防建设、医疗卫生、人民生活等各个领域对工程产品性能的要求不断提高，工程优化问题也变得越来越复杂。元启发式优化算法（包括进化算法和群智能优化算法）相比于传统的单点迭代算法对目标函数无连续可微的要求，具有更大的概率找到全局最优解，且不一定需要有显式的目标函数公式，在大型电力系统［1-2］、天线设计［3-4］、航空航天及汽车设计［5-6］等科学研究和工程优化中具有广泛应用。然而，元启发式优化算法在获得最优解之前通常需要进行多次目标函数评价。因此，在目标函数计算费时的情况下，很难应用元启发式优化算法来搜索问题的最优设计方案［7］。基于历史数据建立代理模型用来辅助元启发式优化算法，在评价次数有限的情况下搜索全局最优解是目前常用的求解计算费时问题的优化方法［8-9］。相比于计算费时的原优化问题的目标函数评价，训练代理模型所需计算时间成本是低廉的，主要包括多项式回 归（Polynomial Regression，PR）［10］、径向基函数（Radical Basis Function，RBF）［11］、高斯过程（Gaussian Process，GP）［12］、人工神经网络（Artificial Neural Network，ANN）［13-14］和支持向量回归（Support Vector Regression，SVR）［15］等常见的代理模型。

元启发式优化算法中根据模型的用途可以将代理模型分为全局代理模型和局部代理模型。在通常情况下，全局代理模型用于平滑原问题的局部最优解，并引导搜索算法快速定位到最优解附近。LIU等［16］提出一个求解中等规模费时优化问题的高斯过程辅助的进化算法。SCHNEIDER 等［17］采用高斯过程模型的贝叶斯优化以改进具有许多自由度的光学结构。TIAN 等［12］提出一个高斯过程辅助的进化算法（MGP-SLPSO），采用多目标填充准则的方式选择真实评价的个体。YU 等［18］提出一种最优重启策略代理辅助的社会学习粒子群优化算法（GORSSSLPSO），集成了重启策略和全局RBF 代理模型以提供功能强大的优化器来解决计算耗时的问题。局部代理模型则用于较好地拟合原问题在某一个区域中的函数形状，从而辅助算法在该区域中进行搜索，从而提高最优解精度。LIM 等［7］使用集成和平滑的局部代理模型同时进行局部搜索，共同生成可靠的适应值预测和搜索改进策略。适应值继承是一种特殊的局部代理模型，SUN 等［19-20］基于同一代兄弟个体和父代个体提出一种新的适应值估计策略。全局和局部混合代理模型相比于使用单全局代理模型或者单局部代理模型在辅助优化算法搜索最优解时具有较好的搜索性能。WANG 等［21］提出基于主动学习的代理模型辅助的粒子群优化算法（CAL-SAPSO），结合全局和局部代理模型管理策略进行优化。SUN等［11］提出代理模型辅助的协同优化算法，利用RBF全局代理模型辅助社会学习微粒群算法进行全局最优解的探索，同时利用适应值估计策略辅助的微粒群算法进行局部开采，从而实现对高维计算费时优化问题的求解。YU 等［22］提出代理模型辅助的分层粒子群优化算法（SHPSO），与代理模型辅助的协同优化算法不同，在SHPSO 中，社会学习粒子群优化用于进行局部空间的开采，而粒子群优化用于在全局空间中进行探索，从而提高全局最优解的寻找性能。LI 等［23］提出一种求解高维费时问题的代理辅助的多种群优化算法（SAMSO），全局和局部代理模型分别辅助两个种群进化，同时两个种群通过相互学习来提高算法的搜索性能。LIAO 等［24］利用所有历史样本训练全局代理模型，采用最优的若干样本训练局部代理模型，并通过多任务优化方法搜索两个模型的最优解。

混合代理模型辅助的元启发式优化算法能够利用不同模型的优势，相比于单代理模型能够更好地辅助优化算法在评价次数或者计算资源有限的情况下找到较优解。本文基于已有的历史数据，通过不同的样本选择策略建立全局代理模型和局部代理模型。对全局代理模型和局部代理模型进行最优解的交互搜索，通过对全局代理模型的搜索实现对原问题最优解的探索，模型最优解根据真实计算用于更新局部代理模型，使其能够更好地拟合目前最优解附近的局部区域，通过对局部代理模型最优解的搜索提高获得更优解的概率。

1 相关技术

1.1 径向基函数网络

径向基函数网络（Radial Basis Function Network，RBFN）是一种包含输入层、隐藏层和输出层共三层的神经网络。RBFN 作为代理模型在辅助优化算法中具有较好的拟合效果，且其拟合效果对于问题维度的增加相对不敏感［25-26］。给定样本库{(xi，f(xi))，i=1，2，…，Na}，Na表示样本库中初始样本数量，RBFN 模型可表示如下：

其中：ω=为RBF 网络的输出权重；Nc为隐含层节点数；φ（·）为径向基核函数；ci为第i个隐含节点径向基函数的中心。常见的核函数有高斯核、线性核、多重二次曲面核、立方核等［27］。本文算法中径向基核函数采用立方核函数。

1.2 差分进化算法

差分进化（Differential Evolution，DE）算法在许多优化问题上已被证明是一个简单有效的进化算法［28-29］，遵循进化算法的一般流程，即首先在问题决策空间中产生一个初始化种群{x1(t)，x2(t)，…，xN()t}，其中，t=0，N为种群大小，xi=(xi1，xi2，…，xiD)表示第i个个体，D表示问题的维度。然后通过变异、交叉和选择操作找到问题的最优解。在DE 算法中，常见的变异策略有DE/rand/1、DE/current-to-best/1和DE/best/1等［30］。本文算法中采用标准的DE/rand/1变异策略，即对于每一代t，随机选择3 个不同于当前个体i的个体，并通过以下公式得到变异后的向量vi(t)：

其中：r0、r1和r2为[1，N]中3 个不同的随机数；和表示当前种群中不同于个体xi的3 个个体；Fi称为DE 的变异因子。

每个个体根据一定的概率在各个维度上进行交叉操作，通过式（3）的交叉方法得到交叉后的向量ui(t+1)=(ui1(t)，ui2(t)，…，uiD(t))。uij(t+1)的计算公式如下：

其中：CRj∈[0，1]为交叉概率；jrandint为［1，D］中随机产生的一个整数。对每个向量ui(t+1)计算目标函数值，并与其父代个体进行适应值的对比，保留较优的个体作为下一代的父代个体，即：

2 全局与局部代理模型交替辅助的DE 算法

2.1 算法整体流程

算法1 给出了全局与局部代理模型交替辅助的差分进化算法AGL-DE 的伪代码。首先，通过拉丁超立方体产生一定数量的初始样本，对其使用真实的目标函数评价并将其存入数据集Arc 中。基于这些真实评价的个体确定当前最优解，记为gbest。然后，若没有达到停止条件，即达到最大的评价次数，则循环执行以下操作：交替建立全局代理模型和局部代理模型并对模型进行最优解搜索，搜索到的最优解进行真实目标函数的计算，存入数据集Arc 中，并更新最优解gbest。最后，详细介绍全局代理模型和局部代理模型的训练（步骤6 和步骤10）及其优化。

算法1AGL-DE 算法

2.2 全局代理模型的训练与优化

在代理模型辅助的进化算法中，为了保证算法的收敛性，通常选用适应值最优的若干个样本来训练模型，但是这样会导致算法很快陷入局部最优，使得算法性能下降。本文选择具有代表性的样本建立全局代理模型，并通过在决策空间对全局代理模型最优解的搜索提高算法探索能力，防止算法陷入局部最优。文献［31］表明全局代理模型并非一定需要与原函数精确拟合，其主要作用在于平滑掉局部最优，加速定位到全局最优解附近。为此，本文通过计算每个样本xi和其最近邻个体之间的拥挤度（记为C(xi)）来选择全局代理模型的训练样本。计算方式为对Arc 中个体按照目标函数值从小到大排序，对任意个体xi，其拥挤度为相邻两个个体的目标函数之差。显然，拥挤度越大，说明该个体和其他个体之间的目标函数差值越大，拥挤度越小，说明和该个体的目标函数的相似度较大。为了更好地训练全局代理模型，选择拥挤度大且考虑估值小的样本个体来训练模型。通过-max 的方式将最大化拥挤度转换成最小化问题，根据个体拥挤度和其适应值进行非支配排序，并从非支配排序后的第一层开始选择该层的所有样本放入训练样集，直到当加入第k层的所有样本选择出的样本数大于预定样本数时，在第k层随机选择样本直到达到预定样本数，并利用选择出的所有样本训练全局代理模型。使用差分进化算法搜索模型的最优解，并对其进行真实的目标函数计算。需要注意的是对模型进行最优解搜索时，初始化种群中的个体来自：1）使用拉丁超立方体采样技术得到的初始个体；2）数据集Arc 中适应值较优的若干个体。初始化种群中增加Arc 中适应值较优的个体是为了加快模型最优解的搜索速度。将经过真实目标函数计算的模型最优解存入样本库Arc 中并更新目前找到的最优解gbest。算法2 为算法1 中训练全局代理模型的伪代码。

算法2全局代理模型训练算法

2.3 局部代理模型的训练与优化

为快速找到更优解，利用数据集Arc 中的若干最优解建立局部代理模型。算法3 给出了训练局部代理模型的伪代码。与训练全局代理模型类似，从数据集Arc 中选择一定数量的训练数据训练局部代理模型。利用差分进化算法进行局部代理模型最优解的搜索。对找到的局部代理模型最优解使用真实的目标函数进行计算，存入数据集Arc 中并更新目前计算得到的最优解。

算法3局部代理模型训练算法

3 实验设计与结果分析

为评估AGL-DE 算法的性能，在7 个单目标基准问题［7，32］上进行测试，这7 个基准问题的函数名称、全局最优值和函数特征如表1 所示。本节首先给出了AGL-DE 算法的参数设置，然后将其与近年来提出的求解费时问题的优化算法在测试函数上进行结果比较，最后对算法框架、参数进行敏感性分析。所有算法均独立运行25 次，并通过显著性水平为0.05 的带有Bonferroni校验的Wilcoxon 秩和检验方法［33］对25 次独立运行结果进行显著性统计检验。

表1 基准函数特性Table 1 Characteristics of the benchmark functions

3.1 参数设置

在AGL-DE 算法中，不同的代理模型均可作为全局与局部代理模型，本文采用RBF 代理模型，主要原因在于RBF 代理模型对于高维问题具有较好的拟合效果［22］。训练RBF 代理模型的最小样本数为2×D。实验中初始产生的样本数为2×D，随着评价次数增多，Arc 中真实计算的样本数增多。若样本过多，则训练模型的速度会减慢，因此在实验中设定训练模型的最大样本数为5×D，在每次模型训练时训练模型的样本数为［2×D，5×D］中的一个随机整数Nt。需要注意的是若产生的随机整数Nt大于当前已有样本数，则Arc 中所有样本均参与模型的训练，否则从Arc 中随机挑选Nt个数据进行模型训练。对于模型最优解的搜索，初始种群大小设置为50，从Arc中选择的最优解个数为［40，50］中的一个随机整数，剩余的初始解使用拉丁超立方体方法产生。迭代次数设置为［D，4×D］中产生的一个随机整数。使用DE/rand/1 作为变异策略，二项式交叉作为DE 的交叉策略，变异因子设置为0.5，交叉概率设置为0.3。在实验对比中，所有算法的终止条件均为达到最大的真实评价次数，在10、20 和30 维的低维测试问题上算法评价11×D次，在50 和100 维的高维测试问题上算法评价1 000 次。

3.2 与其他算法的实验结果对比分析

表2 给出了AGL-DE 与GORS-SSLPSO［18］、CAL-SAPSO［21］、DDEA-SE［34］、SHPSO［22］算法在低维测试问题上的统计结果，其中，符号“+”、“-”和“≈”分别表示AGL-DE 算法相较于其他算法具有显著性优、显著性差和没有显著性差异，加粗数据表示该数据对应的算法找到的解是所有算法中最优的，最后一行的数字分别表示AGL-DE 算法相较于其他算法具有显著性优的个数、显著性差的个数和没有显著性差异的个数。SHSPO 算法在低维问题上只涉及了30 维，因此仅对SHPSO 算法在30 维问题上的结果进行比较。从表2 可以看出，除了F5 测试问题以外，AGL-DE 算法在F1～F4 这4 个测试问题上基本优于其他算法，虽然GORS-SSLPSO 算法在F4 上的结果略好，但是与AGL-DE 算法并没有显著性差异。

表2 AGL-DE 与GORS-SSLPSO、CAL-SAPSO、DDEA-SE、SHPSO 算法在低维测试问题上的统计结果Table 2 Statistical results of AGL-DE and GORS-SSLPSO，CAL-SAPSO，DDEA-SE，SHPSO algorithms on low-dimensional test problems

表3 给出了AGL-DE 与GORS-SSLPSO［18］、MGP-SLPSO［12］、DDEA-SE［34］、SHPSO［22］、SAMSO［23］算法在高维测试问题上的统计结果。从表3 中可以看 出，AGL-DE 算法相比于 GORS-SSLPSO、MDP-SLPSO、DDEA-SE、SHPSO、SAMSO 算法在高维问题上获得了13/14、8/14、13/14、10/14 和9/14 的更好解。此外，还可以看出AGL-DE 算法在5/7 个100 维测试问题上获得了比其他算法更优的结果，表明AGL-DE 算法对于高维问题具有较好的求解效果。

表3 AGL-DE 与GORS-SSLPSO、MGP-SLPSO、DDEA-SE、SHPSO、SAMSO 算法在高维测试问题上的统计结果Table 3 Statistical results of AGL-DE and GORS-SSLPSO，MGP-SLPSO，DDEA-SE，SHPSO，SAMSO algorithms on high-dimensional test problems

为更好地分析算法的收敛性能，图1、图2 分别给出了AGL-DE 算法和其他算法在低维和高维测试问题上的函数收敛曲线图，横坐标代表真实适应值的评估次数，记为T，为了能够更加明显地观察收敛曲线图的变化情况，纵坐标用25 次独立运行得到的适应值的中值的对数表示，记为lg（F（xT）），其中xT为算法第T次真实适应值评估下找到的最优解，F（xT）为xT对应的目标函数值。

图1 AGL-DE 与GORS-SSLPSO、CAL-SAPSO、SHPSO 算法在低维测试问题上的函数收敛曲线图Fig.1 Function convergence curves of AGL-DE and GORS-SSLPSO，CAL-SAPSO，SHPSO algorithms on low-dimensional test problems

图2 AGL-DE 与GORS-SSLPSO、MGP-SLPSO、SHPSO、SAMSO 算法在高维测试问题上的函数收敛曲线图Fig.2 Function convergence curves of AGL-DE and GORS-SSLPSO，MGP-SLPSO，SHPSO，SAMSO algorithms on high-dimensional test problems

由于F6 测试问题的适应值可能是负值，因此在该测试问题的收敛曲线图上没有对适应值进行取对数操作。需要注意的是，DDEA-SE 算法是一种基于数据驱动的离线优化算法，在优化的过程中不会产生需要真实适应度评估的个体，故没有给出其收敛曲线图。

从图1 可以看出，AGL-DE 在F1～F4 测试问题上都比其他算法具有更快的收敛速度，在低维的单模态和多模态问题上都展现了良好的性能。对于高维优化问题，从图2 可以看出，本文所提AGL-DE 算法在大部分优化问题上具有较快的收敛速度。但是从图2 也可以看出其容易陷入局部最优，如50 维的F2、F3、F5 和F7 测试问题，在搜索算法到达一定程度后不再继续下降。由此分析其早熟收敛的主要原因在于初始样本的选择。从Arc 中选择若干最优解作为DE 的初始种群，当这些解的差别较小时，初始种群的多样性较差。这些解虽然能够引导算法快速收敛到某一个解，但是很难跳出局部最优，从而导致了算法的早熟收敛。

3.3 全局与局部代理模型有效性分析

为验证全局与局部代理模型交替辅助的有效性，将其与仅使用全局代理模型辅助进化算法（G-DE）和仅使用局部代理模型辅助进化算法（L-DE）进行实验结果比较，在实验过程中其他参数设置与3.1 节的设置相同。表4 给出了AGL-DE、G-DE 和L-DE 算法在10 维、20 维和50 维的F1、F3 和F4 测试问题上的统计结果。从统计结果上来看：AGL-DE 比G-DE 显著性好3 个，显著性差1 个，无显著性差异5 个；AGL-DE 比L-DE 显著性好3 个，显著性差2 个，无显著性差异4 个。统计结果表明：全局代理模型和局部代理模型交替辅助差分进化算法比单一模型辅助差分进化算法的效果好。

表4 AGL-DE 与G-DE、L-DE 算法在F1、F3 和F4 测试问题上的统计结果Table 4 Statistical results of AGL-DE and G-DE，L-DE algorithms on F1，F3 and F4 test problems

3.4 参数敏感性分析

为验证在一定区间内随机产生的训练集样本数Nt、种群迭代次数iter 和从Arc 中选择的初始样本数Na的有效性，在不改变其他参数设置的情况下，与固定这3 个参数的3 种策略进行比较，分别将它们固定为区间内的最小值、中值和最大值，即min-values、med-values 和max-values，具体参数设置如表5 所示。在这3 种策略上对50 维和100 维的F1、F2、F4 和F6 测试问题进行测试，表6 给出了AGL-DE 算法和这3 种策略的对比统计结果，可以看出在一定区间内随机生成参数的AGL-DE 算法要比单纯固定这些参数的3 种策略具有更好的性能。

表5 3 种策略的参数设置Table 5 Parameter settings of three strategies

表6 AGL-DE 算法与min-values、med-values、max-values策略在F1、F2、F4 和F6 测试问题上的统计结果Table 6 Statistical results of AGL-DE algorithm and min-values，med-values，max-values strategies on F1，F2，F4 and F6 test problems

4 结束语

本文提出一种全局与局部代理模型交替辅助的差分进化算法，通过对全局代理模型和局部代理模型最优解的交替搜索来更新数据集以及原费时优化问题的最优解，从而在计算资源有限的情况下获得问题的更优解。实验结果表明，相比于近年来提出的求解费时问题的优化算法，该算法在低维和高维测试问题上均获得了较好的寻优效果，然而在某些高维测试问题上容易陷入局部最优，导致早熟收敛。因此在下一步工作中将考虑增强算法多样性，以便跳出局部最优，从而在计算资源有限的情况下找到目标函数的更优解。