高计算代价动态优化问题的代理模型辅助粒子群优化算法

张 勇，胡江涛

(中国矿业大学 信息与控制工程学院，江苏 徐州 221118)

在实际生产生活中存在许多复杂优化问题，其目标函数或约束随着时间发生变化，称其为动态优化问题(dynamic optimization problems, DOP)[1-3]。进化算法是模拟自然界生物进化机制提出的一类启发式智能优化技术[4]。由于不依赖问题特性、具有并行搜索机制等优点，目前进化优化算法已成为解决复杂动态优化问题的一种有效方法[5-7]。针对动态优化问题，尤其是动态多目标优化问题，学者们已经提出了诸多进化优化算法。如陈美蓉等[8]提出的新型动态多目标鲁棒进化优化方法、丁进良等[9]提出的基于参考点预测的动态多目标优化算法、梁静等[10]提出的协同进化动态粒子群优化算法等。但是，现有进化优化方法大都假设候选解的评价代价较小，以保证算法有充足的时间响应环境变化。然而，在很多实际应用中，由于需要运行仿真软件或真实系统来评价每个候选解的优劣，其用于评价单个解的代价往往很大。以基于EnergyPlus仿真软件的建筑节能进化优化设计为例，在普通电脑上计算一个候选解的性能指标值通常需要十几分钟[11]。此时，如果继续使用传统进化算法来解决这类高计算代价的动态优化问题，将很难在有限时间内有效跟踪问题最优解的变化。

相对传统数值优化问题，高计算代价优化问题的目标函数往往没有确定的数学解析式，或者数学表达式计算复杂且耗时[12]。这导致使用进化算法解决该类问题时计算量过大，难以直接使用。鉴于此，学者们提出了许多处理高代价优化问题的有效方法[13]，这其中最为典型的是代理模型辅助的进化算法(surrogate-assisted evolutionary algorithms, SAEAs)[14-17]。该类算法使用代理模型替代计算耗时的真实目标函数来评价进化个体[12]。因为构建和使用代理模型所需的计算工作量低于真实目标值的评价代价，该类算法可以显著节省进化算法的计算成本，有效解决个体评价代价高昂的问题。然而，对于高代价动态优化问题，由于不仅其目标函数会随时间动态变化，而且其个体评价的代价高，已有的代理模型辅助进化算法变得不再适用[18-19]。针对计算代价较高的数据驱动动态优化问题，Luo等[20]利用聚类技术形成的邻域物种构建多个代理模型，给出了一种新且有效的代理辅助进化算法(neighborhood-based speciation differential evolution, NSDE)。该算法依据环境变化情况将动态优化问题弱化为一系列静态优化问题，在环境发生变化后重新采样并真实评价样本的目标函数值，以此来训练当前环境下的代理模型。由于需要不断重新采样，该算法存在样本产生代价过高的不足。

鉴于此，针对高计算代价动态优化问题，本文提出一种代理模型辅助的动态粒子群优化算法，用以减少评价个体或粒子真实目标值的次数，并及时跟踪不同环境下问题的最优解。主要创新点有：(1)提出一种基于多方向预测的初始种群产生方法，用来及时响应问题环境的变化。当环境发生变化时，利用历史环境下问题多个最优解(包括全局和局部)的变化趋势，同时预测新环境下问题最优解的多个可能位置，并由此产生多样性和收敛性都较好的初始种群。(2)提出一种融合目标值预测的代理模型构建方法。采用一种差分策略来预测历史样本在新环境下的目标值，选择部分优秀的历史样本来构建代理模型；同时，利用优秀的历史样本和初始种群产生训练样本集合，在减少真实函数评价次数的基础上，提高所建初始代理模型的质量。

1 基础工作

1.1 动态优化问题

动态单目标优化问题和传统优化问题一样，包括目标函数、决策变量和约束条件[21-23]。它们的主要区别在于是否含有依赖于时间的参数向量。在优化问题中，最小化和最大化两类问题可以互相转换。以最小化问题为例，动态优化问题可以表示为

minY=f(X,ω(t))。

s.t.gi(X,ω(t))≤0,i=1,2,…,q,

hi(X,ω(t))=0,j=1,2,…,p,

X∈S⊆RD。

(1)

其中:X=(x1,x2,…,xn)是n维决策向量;Y代表其目标函数值;S为问题的搜索空间；ω(t)=(ω1(t),ω2(t),…,ωi(t))是一个依赖于时间的参数向量；gi(X)表示第i个不等式约束;hj(X)表示第j个等式约束；S中所有满足约束条件的可行解构成的可行域，记为Ω⊆S；t表示环境变化时刻。

对于一个动态优化问题，当环境发生变化时，目标函数f和约束函数都可能随之变化。这就意味着，问题的最优解是随着环境变化而不断变化的，历史最优解可能已不再适合新的环境。所以，对一个动态优化算法而言，不仅要具有较好的收敛性，还要能够快速有效地跟踪问题变化的最优解。

1.2 粒子群优化算法

粒子群优化算法(particle swarm optimization, PSO)自从1995年被提出以来，已被广泛应用于各种优化问题[24-28]，目前已成为进化优化中的代表性算法[29-30]。该算法通过模拟鸟群等生物寻找食物的过程，通过粒子群中各粒子之间相互协作、共享信息来寻找问题的全局最优解[31-32]。在PSO中，一群粒子在搜索空间中一起进化或飞行；在进化过程中，每个粒子向着自己经历过的最优位置和邻域粒子经历过的最优位置移动。根据粒子邻域大小的不同，传统算法分为全局版粒子群优化(global PSO)和局部版粒子群优化(local PSO)2种模式。对于每个粒子而言，全局版的邻域被定义为整个粒子群，而局部版使用了不同网络拓扑结构来确定粒子的邻域。

本文考虑收敛速度快的全局版PSO。在全局版中，每个粒子由速度和位置构成。具体地，在一个n维搜索空间中，设Xi(k)=(xi,1,xi,2,…,xi,n)为第k次迭代时第i个粒子的位置，其速度为Vi(k)=(vi,1,vi,2,…,vi,n)；粒子Xi目前为止找到的最佳位置(称为个体最优点)为Pbesti(k)=(pbesti,1,pbesti,2,…,pbesti,n)，整个粒子群到目前为止找到的最佳位置(称为全局最优点)为Gbest(k)=(gbest1,gbest2,…,gbestn)，那么，在下一次迭代时，该粒子的更新公式如下：

(2)

式中:参数w为惯性权重，表示先前速度的惯性大小；c1和c2是加速度参数，为粒子向两个最优点飞行的动力系数；r1和r2为[0, 1]内的两个随机数；k为算法迭代次数。

1.3 RBF代理模型

在使用进化算法解决高计算代价优化问题时，常用方法是利用低代价的代理模型来替代高代价的目标函数，用来评价进化过程中产生的候选解或个体[17]。目前，诸多优秀的学习算法已被用于构建代理模型，如高斯过程(Gaussian process, GP)[33]、径向基函数网络(radial basis functions, RBF)[34]、多项式回归(polynomial regression, PR)[35]等。

径向基函数是由Powell提出的一种多变量插值函数，其实质是某种沿径向对称的标最函数。由于具有较好的光滑性，RBF已被广泛用于拟合昂贵数值模拟的工程系统响应问题。具体地，常用的RBF的模型如下：

(3)

其中:m是采样点的数量;λj是第j个基函数的系数;φ是基函数;r是欧几里得范数；x是过程输入变量的向量;xj是第j个采样点向量；逼近函数f可以是一些权重不同的RBF的组合。最常用的基函数是高斯核函数，形式为φ(r)=e-cr2。

2 代理模型辅助的动态粒子群优化算法

为解决高计算代价动态优化问题，本文提出一种代理模型辅助的动态粒子群优化算法(surrogate-assisted dynamic particle swarm optimization, SDPSO)。相对传统粒子群优化算法, SDPSO算法主要从如下两个方面进行了改进:一是环境变化后种群的初始化。当检测到环境变化后，提出一种基于多方向预测的种群初始化方法，平衡了种群中粒子的多样性和收敛性;另一个是面向高计算代价目标函数的代理模型。为了缩减训练样本的产生代价，提出一种融合目标值预测策略的初始代理模型构建方法。

2.1 多方向预测的种群初始化策略

在使用进化算法解决动态优化问题时，需要经过若干迭代来寻找问题的最优解。一个高质量的初始种群能够使算法在一开始就比较接近最优解，进而减少算法的迭代次数。对于高计算代价的动态单目标优化问题而言，当检测到环境变化后及时产生高质量的初始种群，不仅可以节省算法的迭代计算量，而且可以帮助种群更快地找到变化后问题的最优解。鉴于此，提出一种基于多方向预测的种群初始化方法。根据第t和t-1个历史环境下问题多个代表解的变化趋势，从多个方向同时预测第t+1环境下问题最优解的可能位置，进而产生一个多样性好且质量高的初始种群。为此，首先给出一种目标值引导的聚类技术，用来确定历史问题的代表解集合。

2.1.1 历史问题代表解集合的确定 由于同时具有好的多样性和目标值，问题的全局和局部最优解通常最具代表性。然而，对于一个复杂优化问题，因为没有充分的先验知识，决策者往往很难判断其准确的全局和局部最优解信息。鉴于此，给出一种目标值引导的聚类技术，从种群所得最优粒子中寻找问题可能的全局和局部最优解。

算法1:基于聚类技术的历史问题代表解集的确定

输入: 针对历史问题所得最优粒子集合Qt，聚类半径L。

输出: 历史问题的代表解集RSt。

步骤4: 输出代表解集合RSt。

可以看出，通过在决策变量空间中对最优粒子进行聚类，上述方法可以保证所选代表解的多样性；通过选择每一个类中目标值最优的粒子作为代表粒子，该方法又可以保证所选代表解都具有较好的函数值。分析优化多峰函数时种群的分布性可知，邻域中目标值最优的粒子通常最接近问题的全局或局部最优解。这就意味着，从每个类中选择目标值最优的粒子，在一定程度上可以反映出问题的全局和局部最优解信息。

(4)

(5)

为提高种群中粒子位置的多样性，仅利用公式(5)初始化种群中一半粒子的位置；对于剩余一半粒子，则在搜索空间中随机初始化它们的位置。进一步，算法2给出了所提种群初始化策略的伪代码。

算法2:本文种群初始化策略

输入: 第t和t-1环境时刻下所得问题的代表解集合RSt和RSt-1，种群规模N。

输出: 初始化后的种群Pt-1。

步骤1: 根据公式(4)确定RSt中每个解的选择概率；

步骤2.1:i=1；

步骤3: 在搜索空间中随机产生第i+1到第N个粒子的位置；

步骤4: 输出种群Pt+1。

本文通过预测方法来寻找动态优化问题最优解的大致位置，并在最优解附近初始化种群，可以使种群一开始就具有较好的质量，进而加快算法的搜索速度。与此同时，通过多个方向对初始种群进行预测，不仅可以保持良好的种群多样性，而且能够避免因为预测不准确产生的估计误差。

2.2 融合目标值预测策略的代理模型构建

对于一个动态优化问题，当环境发生变化后其表达式往往随之变化。这就意味着，先前时刻的代理模型不再准确甚至不再适用。为提高代理模型的精度，需要重新选择训练样本，重新构建代理模型。构建代理模型有两大要素，即样本点的产生和模型的训练。在样本点的产生方面，本文提出一种融合目标值真实评价和模型预测的初始样本产生机制，用来有效均衡模型构建的精度和代价。在模型的训练方面，采用常用的光滑性好的径向基函数网络来训练代理模型，在此不做阐述。

当需要重新构建代理模型时，可以利用的种群信息主要包括3部分：①历史环境中用来更新代理模型的优秀粒子，简称历史优秀粒子。由2.3节内容可知，这些用来更新代理模型的样本都是种群进化过程中得到的代表解，不仅具有较好的多样性，而且具有很好的目标值。在很多情况下，历史优化问题往往与当前环境下优化问题具有一定的相关性，甚至具有较高的相似程度。这就意味着，在新环境下历史问题中用来更新代理模型的样本也可能具有较好的质量，选择这部分样本来训练新代理模型会提高模型的预测精度。②面向新环境采用2.1节预测方法得到的粒子初始位置，简称预测粒子。显然，在预测机制可靠的情况，这些粒子的位置将位于新问题的最优解附近。此时，利用这些位置来产生样本，并用它们来训练新的代理模型，势必会提高模型对最优解邻域中候选解的预测精度。③除第②部分所提及的粒子外，新环境下初始种群中剩余粒子，简称随机粒子。因为这些粒子是在搜索空间中随机生成的，选择它们作为样本可以提高训练样本的多样性。

本文利用上述3部分种群信息来产生当前第t+1时刻下模型的训练样本。然而，分析种群进化过程可知，上述种群信息中可能包含数量过多的粒子。利用真实函数评价所有这些粒子的目标值，并用其训练代理模型，势必可以保证代理模型的精度，但不免增加算法的计算代价。鉴于此，给出一种融合目标值真实评价和模型预测的初始样本产生机制。训练样本的构成方法如下：(1)采用一种差分机制预测历史优秀粒子在新环境下的目标值，仅选择目标值最好的部分粒子进行真实评价，并利用这些粒子及其真实目标值组成第1部分样本；(2)真实评价第二部分中的所有预测粒子，并利用这些粒子及其真实目标值组成第2部分样本；(3)从随机粒子中选择与上述两部分粒子差异较大的粒子，进行真实评价，并利用这些粒子及其真实目标值组成第3部分样本。因为第2部分样本可以直接得到，此处不再阐述。下面给出第1和第3部分样本的详细产生方法。

第1部分样本的产生方法：基于目标值预测的初始样本产生机制。在每个时刻，更新代理模型的粒子都需要使用真实函数来评价，而且这些粒子在当前种群中属于适应值较优的一类粒子，重复利用这些粒子的信息，可以在一定程度上减少计算代价。假设在第t个环境时刻用来更新代理模型的历史优秀粒子集合为Ht，首先依据公式(6)预测Ht中每个粒子在当前第t+1环境下的目标值

(6)

(7)

随后, 从Rt+1中选择拥挤程度值最大的前β%的粒子, 并利用真实目标函数评价这些粒子的目标值。这些被选粒子及其真实目标值即组成第3部分样本。

进一步，算法3给出了产生上述3部分样本的具体执行步骤。算法中参数α和β影响到训练样本的分布性。假设需要产生的初始样本数目为N1，第t+1个环境下初始种群中预测粒子和随机粒子的数目分别为|Ct+1|和|Rt+1|，第t个环境下的历史优秀粒子集合为|Ht|，那么，有

α|Ht|=N1-|Ct+1|-β|Rt+1|。

(8)

算法3: 融合目标值预测策略的初始训练样本产生算法

输入: 第t+1个环境下的初始种群Pt+1，初始种群中预测粒子集合Ct+1和随机粒子集合Rt+1，Pt+1=Ct+1∪Rt+1；第t个环境下的历史优秀粒子集合为Ht；

输出: 第t+1个环境的训练样本集合Tt+1。

步骤1: 利用Ht中粒子信息，产生第1部分样本；

步骤1.1: 依据公式(6)预测Ht中每个粒子在当前第t+1环境下的目标值；

步骤1.2: 从Ht中选择目标值最优的前α%粒子, 并保存到临时集合A中；

步骤3: 利用Rt+1中粒子信息，产生第3部分样本；

步骤3.1: 计算Rt+1中每个粒子的相对拥挤程度；

步骤3.2: 从Rt+1中选择拥挤程度最大的前β%的粒子，并保存到临时集合B中；

步骤4: 输出训练样本集合Tt+1=T't+1∪T″t+1∪T‴t+1。

由此可见，当初始样本数目N1确定后，参数α和β可以退化为一个参数。进一步，实验3.3将分析不同α取值对模型训练结果的影响。选定上述训练样本后，使用RBF神经网络即可构建出初始代理模型。神经网络的输入为被优化问题的决策变量，输出为预测得到的目标值。本文选择RBF作为代理模型的原因如下：第一，RBF具有很强的非线性拟合能力，可以映射任意复杂的非线性关系，并且学习规则简单；第二，RBF不仅具有全局逼近能力，而且在局部信息描述上也有很好的精度；第三，RBF具有强的鲁棒性和自学习能力[34]。

在上述所代理模型更新策略中，代理模型的训练样本由三部分组成。第一部分是历史环境得到的优秀粒子，第二部分是采用2.1节预测方法得到的预测粒子。考虑不同环境之间的相似性，这两部粒子形成的样本通常具体很好的质量，甚至逼近当前环境的最优解。这些粒子训练得到的代理模型更能精确地预测最优解附近粒子的适应值。第三部分是随机粒子。因为这些粒子是在搜索空间中随机生成的，选择它们作为样本可以提高训练样本的多样性。

2.3 代理模型的管理

在训练出初始代理模型后，即可使用该模型代替当前环境下的高计算代价目标函数来评价新粒子。但是，分析2.2节可知，大部分初始训练样本源自预测结果，而预测结果可能存在不同程度的不确定性。因此，并不能完全保证所建初始代理模型可以正确拟合优化问题。为进一步减小代理模型的误差，在进化过程中仍然需要利用新产生的优秀粒子信息来不断更新代理模型。

本文采用加点训练的方式来更新代理模型[36]。在算法第k次迭代过程中，如果最佳新生粒子的预测目标值优于先前最优粒子的目标值，则计算该最佳粒子的真实目标值。如果其真实与预测目标值之间的差值大于规定阈值，则利用该粒子及其真实目标值组成一个新样本，存入算法3所得样本集合Tt+1中；随后，利用Tt+1中样本重新训练代理模型。

2.4 所提粒子群优化算法的执行步骤

基于上述工作，下面给出所提代理模型辅助动态粒子群优化算法的具体执行步骤。图1给出了所提算法的流程图。需要说明的是，针对第2个环境后的每个环境，都利用一个集合Tt保存该环境所用的训练样本。

图1 所提粒子群优化算法的流程图

步骤1：初始化。确定算法所需参数，包括种群规模N、初始样本规模N1、初始样本控制参数α等；在搜索空间中随机初始化种群中N个粒子的位置；初始化每个粒子的个体最优点为其自身，其全局最优点为种群中最优粒子的位置；设置迭代次数k=1。

步骤2：构建当前环境的初始代理模型。对于前2个初始环境，利用真实目标函数评价初始种群中所有粒子的目标值，并利用这些粒子及其真实目标函数构成训练样本，训练RBF网络得到该环境的初始代理模型。对于后续环境，采用2.2节方法产生当前环境的初始代理模型。

步骤3：更新粒子位置，产生新解。首先，采用代理模型预测出所有新生粒子的目标函数值，选出目标值最大的粒子；随后，基于预测得到的目标值，采用标准方法[31]更新每个粒子的个体和全局最优点，并由公式(2)产生下一代粒子的位置。

步骤4：管理代理模型。如果步骤3所选最佳粒子的预测目标值优于先前最优粒子的目标值，则计算该最佳粒子的真实目标值。如果其真实目标值与预测目标值之间的差值大于规定阈值，则执行2.3节方法，重新训练代理模型。

步骤5：判断环境是否发生变化，并采取相应的响应策略。重新评价当前所得最优粒子的真实目标函数值，如果前后两代该粒子的目标值发生变化，则认为环境发生变化。如果环境发生变化，采用2.1节方法初始化种群中粒子位置，初始化迭代次数为k=1，并返回步骤2；否则，设置迭代次数k=k+1，进入步骤6。

步骤6：判断在当前环境内算法是否满足终止条件。如果满足，则终止算法，输出当前环境下最优解，并等待新环境出现；否则，返回步骤3。如果不存在新环境，终止整个算法。

3 实验与分析

本节分析本文算法的有效性。首先，给出所用高计算代价动态测试问题；其次，给出实验所涉及的参数设置，并分析关键参数对本文所提算法的影响；然后，分析所提两个关键算子对算法性能的影响；最后，与传统代理模型辅助进化算法对比，说明所提算法的有效性。

3.1 动态优化测试函数

广义动态基准生成器(GDBG)常被用于产生动态优化问题[37-38]。本文使用GDBG产生的6个测试函数验证所提算法的性能，它们分别是旋转峰函数(F1)、组合Sphere(F2)、组合Rastrigin(F3)、组合Griewank(F4)、组合Ackley(F5)和混合组合函数(F6)[39]。在这些函数中，F1和F2有10个局部最优，其他函数有大量的局部最优。由于本文针对最小化问题设计了相关算子，因此通过取负的方式，将上述测试函数中的最大化问题转换为最小化问题。每个函数有6种环境变化类型, 即小阶跃变化(T1)、大阶跃变化(T2)、随机变化(T3)、混沌变化(T4)、循环变化(T5)和带噪声的循环变化(T6)；后续实验设置环境变化次数为60。进一步，为了模拟函数评价的高计算代价特性，每次函数评价时设置一个延时函数以模拟其真实的计算耗时，实验设置为1 s。

3.2 参数设置与性能测度

在每个环境中训练代理模型的样本规模取值为50个，选择MATLAB中的newrb函数训练代理模型[40]。各项参数设置如下：均方误差设置为0.25，扩展速度设置为0.5，最大神经元数目设置为50，两次显示之间添加的神经元数目设置为5。对于任意一个测试函数的每个变化类型，都独立运行比较算法20次。

本文所提SDPSO算法所需参数的设置情况[41]如下：初始种群的规模设置为50，收敛因子w设置为0.729, 加速度常数c1和c2设置为2.05。在公式(5)和公式(6)中，噪声扰动ε和ε′皆设置为服从标准正态分布的一个随机数。在算法迭代过程中，需要设置一个误差阈值来判断是否需要更新代理模型。为在减少计算代价的同时加快进化进程，误差阈值的设置需要兼顾算法的计算速度和结果的精度。对于函数F1，由于在算法后期种群所得最优解的变化并不明显，因此设置其误差阈值为5；对于函数F2—F6，由于在算法后期种群所得最优解的误差仍然比较大，故此设置它们的误差阈值为50。当全局最优的变化超过这个阈值时，即刻重新选择样本点更新代理模型。

使用最优解误差来度量算法的性能，其值为针对所有环境算法得到的最优结果与真实最优解之间的平均距离[42]，公式为

(9)

其中：E代表环境数目；ri是第i个环境中算法得到的最优值；oi为第i个环境中的真实全局最优。

3.3 关键参数分析

在所提SDPSO算法中，参数α决定了代理模型的初始训练样本，直接影响到算法的最终性能。本实验选择F1-T1、F1-T6、F3-T2和F4-T2等问题作为测试对象，分析参数α取值变化对SDPSO算法性能的影响。依次取α={0.1,0.2,…,1}，图2给出了不同取值下SDPSO所得最优解的误差。

图2 不同α取值下所提算法所得误差曲线

可以看出，对于测试问题F1-T1、F1-T6和F4-T2，当参数α取值为0.3时所提算法得到了最佳结果；对于测试问题F3-T2，当参数α取值为0.4时所提算法得到了最佳结果；当参数α取值为0.3时，所提算法得到了排名第2的优化结果。随着参数α取值的不断增加，所提算法处理4个问题的性能逐渐变差。当参数α取值为1时，针对4个问题所提算法都得到了最差结果。产生这种现象的主要原因是，当α=1时用于构建代理模型的初始数据全都来自历史环境的最优解。一方面，这些解的多样性相对较差；另一方面, 相对新环境其函数值也可能较差。利用分布性和最优性相对较差的样本集合来构建代理模型，势必会降低进化过程中粒子目标值的预测精度，进而影响算法的性能。鉴于此，后续实验设置α=0.3。

3.4 关键策略分析

本节实验分析本文种群初始化策略和代理模型更新策略的有效性。

3.4.1 基于多方向预测的种群初始化策略 为了验证本文基于多方向预测的种群初始化策略的有效性，将SDPSO中种群初始化策略替换成随机初始化种群策略[43]，并记改变后算法为NA-SAPSO。通过比较SDPSO和NA-SAPSO的结果，用来验证本文所提种群初始化策略的有效性。为了避免其他因素的干扰，NA-SAPSO采用与SDPSO相同的参数设置，而且NA-SAPSO和SDPSO中的代理模型都采用RBF代理模型。

图3展示了NA-SAPSO和SDPSO处理6个测试问题时所得结果的平均误差。可以看出，对于F1-T3、F2-T2、F2-T3、F2-T5、F2-T6和F4-T6等6种情况，SDPSO所得误差要略小于NA-SAPSO所得误差值；然而，对于剩余全部30种情况，在所提种群初始化策略的帮助下，SDPSO的误差值都明显小于NA-SAPSO的误差值。其原因如下：一方面，在算法初始阶段，本文所提种群初始化策略既可获得一个高质量的初始种群，这在一定程度上可以加快算法的搜索速度；另一方面，本文方法可以从多个方向同时预测新环境下问题最优解的可能位置，这在一定程度上可以提高种群的多样性，增加种群找到问题真实最优解的概率。

图3 NA-SAPSO和SDPSO处理6个测试问题(36种情况)时所得结果的平均误差

3.4.2 融合目标值预测机制的代理模型更新策略 为了验证本文融合目标值预测机制的代理模型更新策略的有效性，将其与基于初始种群的样本产生策略进行对比。具体地，将SDPSO中的样本产生策略替换成基于初始种群的样本产生策略，并记改变后的算法为IP-SAPSO。通过比较SDPSO和IP-SAPSO的结果，用来验证本文代理模型更新策略效果。为了避免其他因素的干扰，IP-SAPSO采用与SDPSO相同的参数设置。

图4展示了IP-SAPSO和SDPSO处理6个测试问题时所得结果的平均误差。可以看出，除F2-T5、F2-T6、F3-T3和F4-T6等4种情况外，对于剩余全部32种情况，在本文种群初始化策略的帮助下，SDPSO所得误差都明显小于NA-SAPSO所得误差值。其原因如下：一方面，本文代理模型更新策略重复利用了历史环境信息，减少了真实函数的评价次数，大大降低了算法的计算代价；另一方面，本文策略使用得到的最优解不断更新代理模型，使代理模型在真实最优解附近更为精确,这在一定程度上可以充分保证算法的局部开发能力。因此，本文代理模型更新策略也是非常有效的。

图4 IP-SAPSO和SDPSO处理6个测试问题时所得结果的平均误差

3.5 对比结果分析

为了验证本文算法的有效性，本文对已有的动态进化优化算法(DPSO)[44]进行扩展，并将其作为对比算法。具体地，在DPSO的框架下加入RBF神经网络作为代理模型，每次环境变化后利用初始种群重新构建代理模型，记扩展后的DPSO算法为RBF-DPSO。

将本文算法SDPSO与RBF-DPSO进行对比，表1—6分别展示了两种算法处理6个测试问题时所得平均误差值和运行时间以及每个环境下真实函数的平均评价次数。其中，T1—T6表示问题环境变化的6种状态，计算时间为单个环境下算法的执行时间。进一步，利用置信度为0.05的t检验比较两种算法的显著差异性，其中，“+”表示SDPSO所得结果显著优于选定对比算法，“-”表示选定对比算法的结果显著优于SDPSO，“=”两者所得结果无明显差异。

关于测试问题F1，由表1可以看出：(1)对于问题采用的所有6种环境变化类型，本文SDPSO算法都得到了明显优于RBF-DPSO的平均误差。以T1环境类型为例，SDPSO所得结果的平均误差为69.555 8，相对RBF-DPSO降低了10.146 2。(2)对比它们的平均运行时间可知，在显著提升结果精度的同时，SDPSO的计算代价也小于RBF-DPSO。

表1 两种算法处理F1时所得平均误差和时间以及评价次数

关于测试问题F2，由表2可以看出：在6种环境变化类型中，所提SDPSO算法针对3种变化类似(T1、T4和T6)都得到了明显优于RBF-DPSO的平均误差；对于环境变化类型T2，SDPSO也得到了与RBF-DPSO相近的平均误差；剩余两种变化类型，尽管RBF-DPSO所得结果的平均误差明显小于SDPSO，但其运算时间要高于本文SDPSO算法。

表2 两种算法处理F2时所得平均误差和时间以及评价次数

关于测试问题3，由表3可以看出：对于问题采用的所有6种环境变化类型，本文SDPSO算法都得到了明显优于RBF-DPSO的平均误差。以T2环境类型为例，SDPSO所得结果的平均误差为718.769 3, 相对RBF-DPSO降低了89.131 8。并且，在取得较低平均误差的前提下，对于6种环境变化类型SDPSO所用时间也要少于RBF-DPSO。

表3 两种算法处理F3时所得平均误差和时间以及评价次数

关于测试问题4，由表4可以看出：在所有6种环境变化类型中，本文SDPSO算法对4种变化类型(T2—T5)都得到了明显优于RBF-DPSO的平均误差，而且其运行时间也要少于RBF-DPSO；对于剩余两种变化类型(T1和T6)，尽管RBF-DPSO算法所得误差要小于SDPSO，但是SDPSO的运行时间要小于RBF-DPSO。

表4 两种算法处理F4时所得平均误差和时间以及评价次数

关于测试问题5，由表5可以看出：对于问题采用的所有6种环境变化类型，本文SDPSO算法都得到了明显优于RBF-DPSO的平均误差。以T4变化类型为例，SDPSO所得结果的平均误差为1 555.106 5，相对RBF-DPSO降低了173.346 5。并且，在取得较低平均误差的前提下，对于6种环境变化类型SDPSO所用时间也要少于RBF-DPSO。

表5 两种算法处理F5时所得平均误差和时间以及评价次数

关于测试问题6，由表6可以看出：对于问题采用的所有6种环境变化类型，本文SDPSO算法都得到了明显优于RBF-DPSO的平均误差。以T5变化类型为例，SDPSO所得结果的平均误差为1 688.508 1，相对RBF-DPSO降低了62.852 8。并且，在取得较低平均误差的前提下，对于6种环境变化类型SDPSO所用时间也要少于RBF-DPSO。

表6 两种算法处理F6时所得平均误差和时间以及评价次数

4 结论

高计算代价的动态优化问题普遍存在于日常生产生活中。本文针对该类复杂优化问题，提出了一种代理模型辅助的动态粒子群优化算法(SDPSO)。通过引入一种融合目标值预测的代理模型构建方法和一种基于多方向预测的种群初始化策略，该算法不仅可以得到优异的问题最优解，而且可以有效减少个体真实评价次数、加快种群寻优速度。实验结果表明，针对6个典型测试问题和6种环境变化类型组合而成的36种情况，除F2-T2、F2-T3、F2-T5和F4-T6等少数情况外，本文算法都能以较少的运算时间得到最优结果。

然而，代理模型的构建和管理仍然需要较高的计算代价，因此，选择或设计更为有效的代理模型是需要进一步研究的课题。此外，将所提算法应用于实际的昂贵动态优化问题也是今后的研究方向。