在实际生活中，存在许多具有多个目标的优化问题，并且这些目标之间是互相冲突的，此类问题被称为多目标优化问题(multi-objective optimization problems, MOPs)^[1]. 实际生活中环境是不断发生变化的，如果MOPs的目标函数、约束和参数会随着环境变化而改变，MOPs则转化为动态多目标优化问题(dynamic multi-objective optimization problems, DMOPs). 在处理复杂的DMOPs时，传统的多目标优化算法(multi-objective optimization algorithms, MOAs)^[2-7]明显具有局限性. 随着环境的变化，Pareto最优解集 (Pareto-optimal set，PS)^[8]和Pareto前沿 (Pareto-optimal front，PF)不断发生变化，传统的MOAs会在环境变化中逐渐丧失种群的多样性，种群在某一时刻陷入局部收敛而不再随环境发生变化. 因此，需要动态多目标优化算法(dynamic multi-object optimization algorithms, DMOAs)^[9-14]及时地响应环境变化，从而追踪到变化后的PS和PF.

近年来，DMOAs不断被提出，并应用于各个领域，例如：调度^[15]、机械设计^[16]、资源管理^[17]、路径规划^[18]等. 为了解决DMOPs,研究大致可以划分为3大模块：环境变化检测^[19-20]、环境变化应答机制^[9-14,21-22]、静态多目标优化算法^[2-7]. 其中静态多目标优化算法大多是为了提高收敛速度，例如：NSGA-II^[5]、RM-MEDA^[6]、MOEA/D^[7]等. 环境变化检测用于检测环境的变化，为后面设计应答机制提供指导，而变化应答机制是解决DMOPs的重要研究目标. 变化应答机制大多利用多样性引入机制^[21]、预测机制^[9-14]、记忆机制^[22]等方式来响应环境的变化. 其中预测机制对周期性问题和非周期性问题均有不错的效果，该机制通过利用历史信息或者其他方法来预测环境变化后的最优解，如果预测足够准确，那么预测机制对DMOPs非常有效. Zhou等^[10]提出种群预测策略(population prediction strategy, PPS),该策略应对DMOPs较有效，但由于在早期阶段缺乏历史信息的积累，前期效果较差. Zou等^[11]提出基于中心点和Knee点的预测策略(prediction strategy based on center points and knee points, CKPS),该策略将Knee点引入预测种群，可以更加准确地追踪PF,但后期效果不够理想. Li等^[12]提出基于特殊点的预测策略(predictive strategy based on special points, SPPS)，利用Knee点、近边缘点、近中心点等特殊点快速地跟踪PF，该策略进一步提高了种群的多样性，但种群中心点的预测缺乏反馈校正，预测的准确性还有待进一步提高. Rong等^[13]提出多向预测策略(multidirectional strategy, MDP),该策略利用先前环境中多个代表性解所确定的多个方向来预测PS在决策空间中的位置，从而提高了解决DMOPs的性能. Chen等^[14]提出结合混合预测和突变策略的变化响应机制(change response mechanism by combining mixed prediction strategy and mutation strategy, HPPCM)，混合预测策略协调基于中心点的预测和基于引导个体的预测，而突变策略可以处理不可预测的环境变化，从而快速适应各种环境变化.

针对上述不足，本研究提出基于个体预测的动态多目标优化算法，其主要贡献如下. 1) 提出参考点联系算法，引入该算法筛选的特殊点，并通过新的特殊点预测策略快速地响应环境变化. 2) 提出针对种群中心点预测的反馈校正机制，对种群中心点预测非支配解集的预测步长进行反馈校正，使预测更加准确. 3) 提出混合多样性维持机制，引入拉丁超立方抽样和精度可控的突变策略分别生成的随机个体，以提高种群的多样性，避免种群陷入局部收敛.

DMOPs定义^[23] 如下：

(1) $ \left. \begin{gathered} \mathop {\min }\limits_{x \in \varOmega } \;F({\boldsymbol{x}},t) = [{f_1}({\boldsymbol{x}},t),{f_2}({\boldsymbol{x}},t),\cdots ,{f_m}({\boldsymbol{x}},t)]^{\rm{T}}. \\ {\rm{s.t}}.\,\,\;\;\;{g_i}({\boldsymbol{x}},t) \geqslant 0,i = 1,2,3,\cdots ,p;\, \\ \qquad {h_j}({\boldsymbol{x}},t) = 0,j = 1,2,3,\cdots ,q. \\ \end{gathered} \right\} $

式中： $ F({\boldsymbol{x}},t) $为 $ m $维的目标向量， $ {\boldsymbol{x}} = {[{x_1},{x_2},\cdots ,{x_n}]^{\rm{T}}} $为 $ n $维的决策变量，定义域为 $ \varOmega $, $ g({\boldsymbol{x}},t) $和 $ h({\boldsymbol{x}},t) $分别为不等式约束以及等式约束， $ t $表示时间变量.

(2) $ t = \frac{1}{{{n_t}}}\left\lfloor {\frac{\tau }{{{\tau _t}}}} \right\rfloor . $

式中： $ \tau $为迭代数， $ {n_t} $为环境变化程度， $ {\tau _t} $为变化频率.

定义1.　如果 $ {x_1} $和 $ {x_2} $在时间 $ t $满足以下条件：

(3) $\left. \begin{aligned} &\forall i\in \{1,2,\cdots ,m\}：{f}_{i}({{\boldsymbol{x}}}_{1},t)\leqslant {f}_{i}({{\boldsymbol{x}}}_{2},t);\\ & \exists j\in \{1,2,\cdots ,m\}：{f}_{j}({{\boldsymbol{x}}}_{1},t) < {f}_{j}({{\boldsymbol{x}}}_{2},t), \end{aligned}\right\} $

则 $ {{\boldsymbol{x}}_1} $可以支配 $ {{\boldsymbol{x}}_2} $，记作 $ {{\boldsymbol{x}}_1} \prec {{\boldsymbol{x}}_2} $.

定义2.　在 $ t $时刻，如果不存在个体 $ {\boldsymbol{x}}' \in \varOmega $支配个体 $ {\boldsymbol{x}} $，则 $ {\boldsymbol{x}} $为问题(1)(式（1）)在 $ t $时刻的一个Pareto最优解， ${\rm{P}}{{\rm{S}}_t}$为问题(1)在 $ t $时刻所有Pareto最优解的集合. 定义如下：

(4) $ {\rm{P}}{{\rm{S}}_t} = \{ {\boldsymbol{x}} \in \varOmega |\neg \,\exists \,{\boldsymbol{x}}' \in \varOmega ,{\boldsymbol{x}}' \prec {\boldsymbol{x}}\} . $

定义3.　在 $ t $时刻， $ {\rm{P}}{{\rm{S}}_t} $在目标空间的映射被称为 $ {\rm{P}}{{\rm{F}}_t} $：

(5) $ {\rm{P}}{{\rm{F}}_t} = \{ F({\boldsymbol{x}},t)|{\boldsymbol{x}} \in {\rm{P}}{{\rm{S}}_t}\} . $

根据PF和PS动态变化的不同组合，确定4种不同类型的DMOPs，如表1所示.

RM-MEDA^[6]是改进后的分布估计算法，可以在一定的光滑性假设下，即在Karush-Kuhn-Tucker假设下，导出连续MOP的PS,在决策空间中能够形成分段连续的 $ m - 1 $维流形. RM-MEDA不是直接使用种群中的局部信息生成新的种群，而是充分利用当前种群提供的全局信息，因此RM-MEDA具有更强的启发式优化能力. RM-MEDA的流程图如图1所示.

参考点常常被用来解决多目标优化问题上的收敛性和多样性问题，在Das等^[24] 所提方法的基础上，Deb等^[25-26]提出基于参考点的多目标优化算法(NSGA-III),利用预定义的参考点对选择个体的方法进行改进，以维持种群之间的多样性，后续将NSGA-III扩展到求解一般约束多目标优化问题. 本研究的参考点采用Das等^[24] 的方法设计，所设计的参考点在超平面上均匀分布. 假设 $ M $个参考点的集合为 $ R = \{ {{\boldsymbol{r}}^1},\cdots ,{{\boldsymbol{r}}^i},\cdots ,{{\boldsymbol{r}}^M}\} $，生成参考点 $ {{\boldsymbol{r}}^i} $：

(6) $ \left. \begin{gathered} {{\boldsymbol{r}}^i} = {[r_1^i,\cdots ,r_j^i,\cdots ,r_m^i]^{\rm{T}}}; \\ r_j^i \in \left\{ {\frac{0}{H},\frac{1}{H},\cdots ,\frac{H}{H}} \right\},\;\sum\limits_{j = 1}^m {r_j^i} = 1. \\ \end{gathered} \right\} $

式中： $i = 1,2,\cdots ,M$, $j = 1,2,\cdots ,m$, $ M $为参考点的数量，H为每个目标上划分的数目， $ m $为目标函数的个数.

在Das等^[24]的方法中，参考点数量 $ M $的表达式为

(7) $ M = C_{m+H - 1}^H. $

通常，参考点的数量与种群的大小一致，本研究根据种群中非支配解集的大小设置参考点的数量.

追踪PS和PF一直是解决动态多目标优化问题的热点，本研究提出参考点联系算法，利用该算法筛选的特殊点来追踪PF，从而实现更快的收敛.

参考点联系算法是将预定义的参考点与非支配个体关联起来. 参考点与原点连接作为该参考点的参考向量，计算每个参考向量与非支配个体的距离，参考点与离其参考向量最近的非支配个体关联. 由于参考点是均匀分布在超平面上的，若有非支配个体关联较少的参考点或没有关联参考点，说明附近有其他非支配个体与其竞争，则这些个体不具备较好的多样性；反之，关联较多参考点的非支配个体具有较好的多样性. 如图2所示，非支配个体 $ {{A}} $关联了3个参考点，其多样性优于关联2个参考点的 $ {{B}} $、 $ {{C}} $、 $ {{D}} $以及关联1个参考点的 $ {{E}} $，而 $ {{F}} $、 $ {{G}} $作为边界点则直接加入到特殊点集中.

根据非支配个体关联参考点的数量，从多到少依次选择 $ {\rm{nu}}{{\rm{m}}_1} $个非支配个体加入特殊点集中. 为了给筛选提供便利，预定义参考点的数量大于非支配解集的总数. 参考点联系算法的具体步骤见算法1.

算法1　参考点联系算法

1）将种群分层，选择第1层的个体为非支配个体.

2）根据非支配解集的大小，采用式(6)的方法设计参考点集 $ R $.

3）计算每个参考向量与非支配个体的距离，参考点与离其参考向量最近的非支配个体关联.

4）根据非支配个体关联参考点的数量，从多到少依次排列，按照顺序选择 $ {\rm{nu}}{{\rm{m}}_1} $个非支配个体加入特殊点集.

除了以上筛选的点和边界点以外，本研究还采用文献[11]中的方法，选择Knee点加入特殊点集，Knee点是指在PF上具有最大边际效用的点，在Knee点附近，一个目标上有一个较小的改进，将会伴随着至少一个目标的严重退化. 参考点联系算法在筛选过程中会避免出现和Knee点重合的情况，且当实际筛选点的数量少于 $ {\rm{nu}}{{\rm{m}}_1} $时，从非支配解集中随机选择个体补齐.

选择参考点联系算法筛选的点、边界点和Knee点作为特殊点代表整个PF,而对特殊点集的预测能快速地响应环境变化，加快种群的收敛. 采用文献[27]、[28]的方法，提出特殊点预测策略，在图3中，通过例子来说明该特殊点预测策略的思想. 首先计算 $ t $时刻特殊点集的最小值点 $ {\bf{min}}^t $和最大值点 ${\bf{ max}}^t $:

(8) $ \left. \begin{gathered} {\bf{min}}^t = {[{\rm{min}}_1^t,\cdots ,{\rm{min}}_i^t,\cdots ,{\rm{min}}_n^t]^{\rm{T}}}, \\ {\bf{max}}^t = {[{\rm{max}}_1^t,\cdots ,{\max} _i^t,\cdots ,{\rm{max}}_n^t]^{\rm{T}}}. \\ \end{gathered} \right\} $

利用式(8)计算 $ t - 1 $时刻特殊点集的最小值点 ${\bf{ min}}^{t - 1} $和最大值点 $ {\bf{max}}^{{t - 1}} $,然后计算 $t$时刻最小值点和最大值点第 $i$维的运动方向 $\min D_i^t$和 $\max D_i^t$,如下式：

(9) $ \left. \begin{gathered} {\min} D_i^t = {\min} _i^t - {\min} _i^{t - 1}, \\ {\max} D_i^t = {\max} _i^t - {\max}_i^{t - 1}. \\ \end{gathered} \right\} $

根据 $t$时刻的 $ {\bf{mi}}{{\bf{n}}^t} $和 $ {\bf{ma}}{{\bf{x}}^t} $以及 $\min D_i^t$和 $\max D_i^t$，可以预测出 $ t+1 $时刻的最小值点 $ {\bf{mi}}{{\bf{n}}^{t+1}} $和最大值点 $ {\bf{ma}}{{\bf{x}}^{t+1}} $， $ {\bf{mi}}{{\bf{n}}^{t+1}} $和 $ {\bf{ma}}{{\bf{x}}^{t+1}} $则组成了 $ t+1 $时刻的决策空间：

(10) $ \left. \begin{gathered} {\rm{min}}_i^{t+1} = {\rm{min}}_i^t+\min D_i^t, \\ {\rm{max}}_i^{t+1} = {\rm{max}}_i^t+\max D_i^t. \\ \end{gathered} \right\} $

利用特殊点预测出 $ t+1 $时刻最小值点和最大值点组成的决策空间，然后进一步预测 $ t+1 $时刻的特殊点集. 它不是一个准确的预测，因此增加了一个高斯扰动，若 ${{\boldsymbol{x}}^t} = {[x_1^t,\cdots ,x_i^t,\cdots ,x_n^t]^{\rm{T}}}$为 $ t $时刻的一个特殊点，则预测的公式为

(11) $ \begin{split} x_i^{t+1} = \;&\frac{{(x_i^t - {\rm{min}}_i^t)({\rm{max}}_i^{t+1} - {\rm{min}}_i^{t+1})}}{{{\rm{max}}_i^t - {\rm{min}}_i^t}}+ \\ \;&{\rm{min}}_i^{t+1}+{\rm{Gaussian}}(0,d)\;. \end{split} $

式中： $ x_i^t $和 $ x_i^{t+1} $分别为 $ t $时刻 $ {x^t} $第 $ i $维的决策变量和 $ t+1 $时刻 $ {x^{t+1}} $第 $ i $维的决策变量， $ d $表示方差的扰动. 特殊点预测策略的步骤如算法2所示.

算法2　特殊点预测策略

输入：特殊点集 $ {\rm{specia}}{{\rm{l}}^t} $,特殊点集的大小 $ {N_{\rm{s}}} $.

输出：预测的 $ t+1 $特殊点集 ${\rm{po}}{{\rm{p}}_{\rm{s}}}$.

1）根据式(8)计算 $ t $时刻和 $ t - 1 $时刻特殊点集的最小值点 $ {\bf{mi}}{{\bf{n}}^t} $和 $ {\bf{mi}}{{\bf{n}}^{t - 1}} $以及最大值点 $ {\bf{ma}}{{\bf{x}}^t} $和 $ {\bf{ma}}{{\bf{x}}^{t - 1}} $.

2）根据式(9)计算 $ t $时刻最小值点和最大值点第 $ i $维的运动方向 $ \min D_i^t $和 $ \max D_i^t $.

3）根据式(10)预测 $ t+1 $时刻的最小值点 $ {\bf{mi}}{{\bf{n}}^{t+1}} $和最大值点 $ {\bf{ma}}{{\bf{x}}^{t+1}} $.

4）根据式(11)预测 $ t+1 $时刻的特殊点集.

种群中心点的预测方法^[9-11]被广泛应用到种群的预测中，该预测方法通常被用来预测非支配个体， 但由于缺乏误差反馈和校正机制，预测的准确性还有待进一步提高，因此，本研究采用了针对该预测方法的反馈校正机制^[29]来弥补这一缺陷.

首先须构建一个代表个体，将 $ t $时刻非支配解集的中心点 $ {{\boldsymbol{C}}^t} $作为代表个体：

(12) $ {{\boldsymbol{C}}^t} = \frac{1}{{\left| {{\rm{P}}{{\rm{S}}^t}} \right|}}\sum\limits_{{{\boldsymbol{x}}^t} \in {\rm{P}}{{\rm{S}}^t}} {{{\boldsymbol{x}}^t}} . $

式中： ${{\rm{P}}{{\rm{S}}^t}} $为t时刻种群的非支配解集， $ {{\boldsymbol{x}}^t} $为非支配个体.

然后对代表个体进行预测：

(13) $ {{\boldsymbol{C}}^{t+1}} = {{\boldsymbol{C}}^t}+{{\boldsymbol{P}}^t}. $

式中： $ {{\boldsymbol{C}}^{t+1}} $为预测的 $t+1$时刻非支配解集的中心点； $ {{\boldsymbol{P}}^t} = {{\boldsymbol{C}}^t} - {{\boldsymbol{C}}^{t - 1}} $表示初始预测的步长和方向， $ {{\boldsymbol{C}}^{t - 1}} $为 $ t - 1 $时刻非支配解集的中心点.

如图4所示，基于 $ {{\boldsymbol{C}}^{t+1}} $，在预测步长的范围内，沿初始预测的正负方向对最优变量均匀采样，生成 $ 2N $个搜索个体 $ S = \{ {{\boldsymbol{s}}^1},\cdots ,{{\boldsymbol{s}}^i},\cdots ,{{\boldsymbol{s}}^{2N}}\} $：

(14) $ s_j^i = \left\{ \begin{gathered} C_j^{t+1} \pm \frac{i}{N}{P_j},\;\;\,j \in {V_{{\rm{std}}}}; \\ C_j^{t+1},\quad \quad \quad \,\,j \notin {V_{{\rm{std}}}}. \\ \end{gathered} \right. $

式中： $i = 1,2,\cdots , N,$ $j = 1,2,\cdots ,n$； $ {{s}}_j^i $为 $ {{\boldsymbol{s}}^i} $的第 $ j $维决策变量； $ {{\boldsymbol{C}}^{t+1}} = {[C_1^{t+1},\cdots ,C_j^{t+1},\cdots ,C_n^{t+1}]^{\rm{T}}} $, $ C_j^{t+1} $为 $ {{\boldsymbol{C}}^{t+1}} $的第 $ j $维决策变量； $ {{\boldsymbol{P}}^t} = {[{P_1},\cdots ,{P_j},\cdots ,{P_n}]^{\rm{T}}} $， $ {P_j} $为 $ {{\boldsymbol{P}}^t} $的第 $ j $维决策变量； $ {V_{{\rm{std}}}} $为最优变量集合.

最后对这组搜索个体 $ S = \{ {{\boldsymbol{s}}^1},\cdots ,{{\boldsymbol{s}}^i},\cdots ,{{\boldsymbol{s}}^{2N}}\} $和 $ {{\boldsymbol{C}}^{t+1}} $进行评估，将非支配个体存储到外部存档 $ A $中， $ A = \{{{\boldsymbol{a}}^1},\cdots ,{{\boldsymbol{a}}^i},\cdots ,{{\boldsymbol{a}}^{\left| A \right|}}\} $,在 $ A $中随机选择一个非支配个体 $ {{\boldsymbol{a}}^i} $. 非支配个体 $ {{\boldsymbol{a}}^i} $优于 $ {{\boldsymbol{C}}^{t+1}} $,其对应的预测步长也优于初始预测的步长，因此初始预测步长可以通过 $ {{\boldsymbol{C}}^{t+1}} $和 $ {{\boldsymbol{a}}^i} $之间的向量差 $ {\boldsymbol{\varDelta}} $进行修正：

(15) $ {P_j} = {P_j}+a_j^r - C_j^{t+1},\,\,\,j \in {V_{{\rm{std}}}}. $

式中： $r = {\rm{Random}}\;(\left| A \right|)$为1~ $ \left| A \right| $的随机整数， $ a_j^r $为 ${{\boldsymbol{a}}^r}$的第 $ j $维决策变量.

最优变量的选择，根据非支配解集中每个维度决策变量的标准差决定，选择标准差较小的变量作为最优变量. 根据文献[29]、[30]中单一最优变量的定义，如果一个决策变量是单一最优的，那么所有解在该决策变量上的值是相同，因此本研究选择非支配解集中标准差较小的变量作为最优变量. 反馈校正机制的具体步骤如算法3所示.

算法3　反馈校正机制

输入：非支配解集 ${\rm{PS}}^t$

输出：校正后的预测步长 ${{\boldsymbol{P}}^t}$

1）根据式(12)计算 $ t - 1 $时刻和 $ t $时刻非支配解集的中心点 $ {{\boldsymbol{C}}^{t - 1}} $和 $ {{\boldsymbol{C}}^t} $, $ {{\boldsymbol{C}}^t} $作为代表个体.

2）根据式(13)对 $ {{\boldsymbol{C}}^t} $进行预测，得到预测的 $ t+1 $时刻非支配解集的中心点 $ {{\boldsymbol{C}}^{t+1}} $.

3）计算非支配解集中每个维度决策变量的标准差，选择标准差较小的变量为最优变量 $ {V_{{\rm{std}}}} $.

4）根据式(14)生成 $ 2N $个搜索个体 $S = \{ {{\boldsymbol{s}}^1},\cdots ,{{\boldsymbol{s}}^i},\cdots , {{\boldsymbol{s}}^{2N}}\}$.

5）重新评估 $ {{\boldsymbol{C}}^{t+1}} $和搜索个体 $S = \{ {{\boldsymbol{s}}^1},\cdots ,{{\boldsymbol{s}}^i},\cdots ,{{\boldsymbol{s}}^{2N}}\}$，并将非支配个体存储到 $ A $中.

6）对于 $ j \in {V_{{\rm{std}}}} $，利用式(15)对 $ {{\boldsymbol{P}}^t} $进行校正.

根据校正后的预测步长对非支配个体进行预测. 为了使预测的非支配个体更接近 $ t+1 $时刻真实的非支配个体，分别对非支配个体进行小、中、大3种步长的预测^[31]:

(16) $ {\boldsymbol{x}}^{t+1} = {\boldsymbol{x}}^t+{{\boldsymbol{P}}^t}\times {\rm{rs}}. $

式中： ${\boldsymbol{x}} ^{t+1}$表示 $ t+1 $ 时刻的非支配个体； $ {\rm{rs}} $为沿移动方向的移动步长，使用3种不同的值(0.5, 1.0, 1.5)表示，分别代表非支配个体小、中、大3种步长的预测，其中，小步长和大步长的预测作用在同一非支配解集，各预测一半的非支配个体，3种步长预测后的种群共同构成了 $ t+1 $时刻的非支配解集.

在动态环境中，保持多样性是非常重要的，本研究提出混合多样性维持机制，通过拉丁超立方抽样^[32]在式(8)~(10)预测的 $ t+1 $时刻的决策空间和 $ t $时刻特殊点的最小值点和最大值点组成的决策空间中分别生成 $ {N_1} $个随机个体. 除此之外，在Zhang等^[33]提出的精度可控突变算子的基础上，提出精度可控的突变策略，对非支配解集进行突变，生成随机个体. 所提出的精度可控突变算子表达式如下：

(17) $ {x'_i} = {x_i}+\Delta \beta ， $

(18) $ {x'_i} = {x_i} - \Delta \beta . $

式中： $\Delta \beta = \Delta \alpha +1/{10^{{\rm{Random}}(q)}}\times {\rm{Gaussian}}(0,{\rm{std}})$,其中 $\Delta \alpha = 1/{10^{{\rm{Random}}(q)}}\times {\rm{Random}}(9)$， ${\rm{std}}$为非支配解集中每个维度决策变量的标准差； $i = 0,1,\cdots ,n$； $ {x_i} $为 $ {\boldsymbol{x}} $的第 $ i $维决策变量； $ {x'_i} $为 ${\boldsymbol{x}}'$突变的第 $ i $维决策变量.

精度可控的突变策略的具体步骤如算法4所示.

算法4　精度可控的突变策略

输入：非支配解集 ${\rm{PS}}^t$， ${\boldsymbol{x}}$为 ${\rm{PS}}^t$中的非支配个体

输出：随机解 ${\rm{po}}{{\rm{p}}_2}$

1）计算 $\Delta \alpha = 1/{10^{{\rm{Random}}(q)}}\times {\rm{Random}}(9)$.

2）计算 $\Delta \beta = \Delta \alpha +1/{10^{{\rm{Random}}(q)}}\times {\rm{Gaussian}}(0,{\rm{std}})$.

3） $ r = {\rm{Random}}(2) $.

4）if $ r = = 1 $ then

　　 if $ i \in {V_{{\rm{std}}}} $ then

　　　 ${x'_i} = {x_i}$;

　　 else

　　　 ${x'_i} = {x_i}+\Delta \beta $;

　　 end if

　 else

　　 if $ i \in {V_{{\rm{std}}}} $ then

　　　 ${x'_i} = {x_i}$;

　　 else

　　　 ${x'_i} = {x_i} - \Delta \beta $;

　　 end if

　 end if

该策略对非支配解集突变生成随机个体，为了保证突变的随机个体仍具有较好的收敛性，只对非最优变量进行突变，变量 $ r $随机取1或2，使突变可以生成均匀扩散的随机个体. $ \Delta \beta $和 $ \Delta \alpha $都用于控制变量的精度， $ \Delta \beta $在 $ \Delta \alpha $基础上增加了精度可控的高斯分布，在扩大了搜索范围的同时也可以通过比 $ \Delta \alpha $更小的步长在决策空间中局部搜索最优解， 理论上，本研究提出的精度可控的突变策略所突变的随机个体，具有更好的多样性和更均匀的分布.

IPS是在动态多目标进化算法的框架下进行的. IPS在环境变化后产生新的初始种群，使新的种群能够对环境变化快速响应并追踪其变化的PF. 算法5是对IPS的详细描述，IPS的流程图如图5所示.

算法5　IPS算法

初始化：时间变量 $ t:\, = 0 $,初始化种群 $ {\rm{pop}} $,迭代次数计数器 $ {g_t}:\, = 0 $,算法总进化代数 $ {g_{{\rm{max}}}} $.

1）检测环境变化，如果环境没有发生变化，转步骤10）；否则，转步骤2）.

2）根据算法1得到参考点联系算法筛选的点，和Knee点、边界点一起作为特殊点.

3）利用式(8)~(10)预测 $ t+1 $时刻最小值点和最大值点组成的决策空间，并利用式(11)预测 $ t+1 $时刻的特殊点集 $ {\rm{po}}{{\rm{p}}_{\rm{s}}} $.

4）计算非支配解集的中心点 $ {{\boldsymbol{C}}^t} $.

5）利用式(14)~(15)对式(13)的预测步长进行反馈校正，并利用校正的预测步长预测 $ t+1 $时刻的非支配解集 $ {\rm{po}}{{\rm{p}}_{{\rm{Non}} - {\rm{dom}}}} $.

6）对式(8)~(10)计算的 $ t $时刻决策空间和预测的 $ t+1 $时刻决策空间进行拉丁超立方抽样生成随机解 $ {\rm{po}}{{\rm{p}}_1} $.

7）根据算法4对 $ t $时刻非支配解集突变生成随机解 $ {\rm{po}}{{\rm{p}}_2} $.

8）得到新种群 $ {\rm{po}}{{\rm{p}}^{t+1}} = {\rm{po}}{{\rm{p}}_{\rm{s}}}+{\rm{po}}{{\rm{p}}_{{\rm{Non}} - {\rm{dom}}}}+ {\rm{po}}{{\rm{p}}_1}+ {\rm{po}}{{\rm{p}}_2} $.

9）对 $ {\rm{po}}{{\rm{p}}^{t+1}} $执行RM-RMAD中的环境选择算法.

10）用RM-RMAD对种群进行优化.

11）如果 $ {g_t} > {g_{{\rm{max}}}} $, 则输出 $ {\rm{po}}{{\rm{p}}_t} $并终止；否则 $ {g_t}:\, = {g_t}+1 $，转步骤1）.

采用几种常见的动态多目标测试问题，包括FDA系列^[23]和DMOP系列^[34]以及F5~F10系列问题^[6]. 其中，FDA和DMOP系列问题的决策变量之间是线性相关的，而F5~F10系列问题的决策变量之间是非线性相关的. F9~F10是更难收敛的测试问题，例如，F9的Pareto前沿在大部分时间内发生平稳变化，但偶尔会出现较大的环境变化，这会降低算法的收敛速度. 在所有的测试问题中，FDA4和F8是三目标测试问题，其他是两目标测试问题.

采用修正的反向代距离(modified inverted generational distance, MIGD)^[11-12]和修正的超体积差(modified hypervolume difference, MHVD)作为DMOAs的性能评价指标，衡量算法在收敛性和多样性方面的性能.

反向代距离 (inverted generational distance, IGD)^[35]被广泛应用到衡量算法的收敛性和多样性，IGD指标的定义如下：

(19) $ {\rm{IGD}}({\rm{P}}{{\rm{F}}_t},{\rm{PF}}_t^*) = {{\displaystyle \sum\limits_{v \in {\rm{P}}{{\rm{F}}_t}} {d(v,{\rm{PF}}_t^*)} }}/{{\left| {{\rm{P}}{{\rm{F}}_t}} \right|}}. $

式中： $ {\rm{P}}{{\rm{F}}_t} $为 $ t $时刻标准PF； $ {\rm{PF}}_t^* $为 $ t $时刻算法所得的PF； ${d(v,{\rm{PF}}_t^*)} $为 $ v $距 $ {P_t} $中最近个体的距离， $ d(v,{\rm{PF}}_t^*) = {\min _{u \in {\rm{PF}}_t^*}}\;\left\| {F(v) - F(u)} \right\| $.

IGD评价的是标准PF和算法所得PF的接近程度以及算法所得PF中个体的分布性，MIGD是IGD的修改版本，它被定义为运行期间某些时间步长内的IGD平均值：

(20) $ {\rm{MIGD}} = \frac{1}{{\left| T \right|}}\sum\limits_{t \in T} {{\rm{IGD}}({\rm{P}}{{\rm{F}}_t},{\rm{PF}}_t^*)} . $

式中： $ T $为运行中的一组时间离散点集合.

MIGD是综合的评价指标，可以评价算法在收敛性和分布性方面的性能，其值越小，说明算法的性能越好.

超体积差 (hypervolume difference, HVD)^[36]测量的是标准PF和算法所得PF之间的超体积差，HVD的评价指标如下：

(21) $ {\rm{HVD}}({\rm{P}}{{\rm{F}}_t},{\rm{PF}}_t^*) = {\rm{HV}}({\rm{P}}{{\rm{F}}_t}) - {\rm{HV}}({\rm{PF}}_t^*). $

式中： $ {\rm{HV}}(S) $表示集合 $ S $的超体积.

MHVD是对HVD的修改版本，它被定义为运行期间某些时间步长内的HVD平均值，其表达式如下：

(22) $ {\rm{MHVD}}({\rm{P}}{{\rm{F}}_t},{\rm{PF}}_t^*) = \frac{1}{{\left| T \right|}}\sum\limits_{t \in T} {{\rm{HVD}}({\rm{P}}{{\rm{F}}_t},{\rm{PF}}_t^*)} . $

式中： $(Z_1^t+0.5,\cdots ,Z_j^t+0.5,\cdots ,Z_m^t+0.5)$为计算超体积的参考点， $ Z_j^t $表示 $ t $时刻标准PF第 $ j $个目标的值， $ m $表示目标函数的个数. MHVD可以同时衡量收敛性和多样性，其值越小，说明算法所得PF收敛性越好，分布越均匀.

选择4种策略与本研究所提的IPS进行对比. 4种策略分别为种群预测策略(PPS)^[10]、基于中心点和拐点的预测策略(CKPS)^[11]、基于特殊点的预测策略(SPPS)^[12]和结合混合预测和突变策略的变化响应机制(HPPCM)^[14]. 5种策略均采用RM-MDEA^[6]对问题优化.

对每个问题独立实验20次，每次实验都会产生100次环境变化，环境的变化程度 $ {n_t} = 10 $,环境变化频率 $ {\tau _t} = 25 $,每次运行的总进化代数为2500，种群大小设置为100，决策空间的维度 $ n = 20 $，在AR(p)模型中，参数 $ p = 3 $，历史信息序列长度设置为23. 各个策略特定的参数设置如下.

1) CKPS的Knee点个数为9.

2) SPPS在种群中心点预测非支配集的过程中将高斯扰动 $ d $=0.1.

3) HPPCM中自主演化的代数 $ \Delta t $=2.

4) IPS中参考点联系算法筛选的特殊点个数 $ {\rm{nu}}{{\rm{m}}_1} $=9，最优变量个数为2，搜索个体总数 $ 2N $=18， $ {N_1} $=25， $ q $=2.

环境变化检测则通过选择种群中5%的个体来检测环境变化，目标值不匹配表明环境发生了改变.

在动态环境中，须讨论不同策略在不同时期的性能，因此，将100次环境变化分为3个阶段：第1阶段包括前20次环境变化；第2阶段包括中间40次环境变化；第3阶段包括最后40次环境变化. MIGD和MHVD的平均值和标准差如表2~5所示. 表中，粗体表示最佳值. 采用Wilcoxon秩和检验^[37]在0.05显著性水平上比较不同结果之间的显著性.

如表2所示为在FDA和DMOP系列问题上比较5种策略的MIGD指标，总阶段代表所有的环境变化.可以看出，1) 在总阶段和第1阶段，IPS有5个MIGD指标是最优的，HPPCM有2个MIGD指标是最优的. 2) 在第2阶段，IPS有3个MIGD指标是最优的，HPPCM有4个MIGD指标是最优的. 3) 在第3阶段，IPS有2个MIGD指标是最优的，PPS和HPPCM有3个MIGD指标是最优的.

出现这样实验结果的原因如下. IPS不需要经验的积累，其参考点联系算法筛选的特殊点可以加速种群的收敛，因此，在第1阶段IPS表现出了更好的性能. PPS随着经验的积累，在后2个阶段的某些测试问题上的MIGD指标优于IPS的. HPPCM的混合预测机制注重收敛，可以快速地响应环境变化，因此在FDA和DMOP系列问题上也有较好的表现. 对于3个目标的测试问题，IPS整体的性能要好于其他4种策略，说明IPS在高维动态多目标问题上有着更好的表现.

F5~F10是决策空间变量呈非线性相关的测试问题，如表3所示，在F5~F10系列问题上比较了这5种策略的MHVD指标，MHVD和MIGD均为综合的评价指标，可以评价5种策略在收敛性和分布性方面的性能. 可以看出，IPS和HPPCM较其他3种策略表现出了更好的性能. 对于测试问题F5~F8,HPPCM在第2、3阶段的MHVD指标大多优于IPS的，原因如下：HPPCM擅长追踪具有重大变化的PS或PF,而IPS的反馈校正机制和特殊点预测策略可以加速种群的收敛，因此IPS在第1阶段表现更好. 对于复杂测试问题F9, IPS的MHVD指标比其他4种策略的都要好，这是因为IPS在面对较大环境变化时仍能较快地收敛. CKPS和SPPS则在F10测试问题上有着更好的表现，是因为其自适应的种群维持机制可以根据问题困难程度引入不同数量的个体.

为了检验5种策略在不同环境变化频率下的性能，选择6个具有代表性的测试问题，比较5种策略对应3种不同 $ {\tau _t} $的MIGD和MHVD指标，环境变化频率 $ {\tau _t} $分别设置为20、25和30. 如表4所示，每种算法都有18个MIGD指标，其中IPS有11个MIGD指标是最优的，HPPCM有5个MIGD指标是最优的，SPPS和CKPS有1个MIGD指标是最优的，不难看出，5种策略中IPS和HPPCM最优和次优的MIGD指标是最多的，说明IPS和HPPCM比其他3种策略的性能更好，另一方面，随着 $ {\tau _t} $的增加，5种策略的性能均得到了提升，原因是较大的 $ {\tau _t} $有更多的迭代次数使种群在环境变化之前找到近似的 $ {\rm{PS}} $.

如表5所示为5种策略在6个测试问题上对应3种不同 $ {\tau _t} $的MHVD指标，与表4较为不同的是，SPPS在DMOP1测试问题上的3个MHVD指标是最优的，原因可能是MHVD在评价算法性能时更倾向于边界解，而SPPS在保留边界解的方面做得更好.

为了进行更加直观的比较，选择DMOP2、F9这2个具有代表性的测试问题来绘制5种策略在不同时刻所获得解集的分布图，如图6、7所示. 图中，横纵坐标表示所获得解集在不同目标上的目标值，圆点表示获得的解集，曲线表示标准PF. 可以看出，对比结果与表2、3的相同，在早期阶段，IPS所获得的解集具有更好的收敛性和分布性，说明IPS可以快速地响应环境变化. 在后期阶段，IPS在环境多次变化后仍能较为准确地追踪到新解，最终得到收敛性和分布性均较好的 $ {\rm{PS}} $，并且，IPS所获得的PF和标准的PF较接近. 其他4种策略在后期阶段的表现也较为不错. 由图7可以看出，IPS在处理F9这种复杂测试问题时也有较好的表现.

比较参考点联系算法筛选0个特殊点和9个特殊点的IPS，设筛选特殊点的个数为 $ s $, $ s = 0 $的IPS为IPS(0)， $ s = 9 $的IPS为IPS(9)，选择F6和F9作为代表问题来比较IPS(0)和IPS(9)在20次运行中环境变化的IGD趋势，结果如图8所示. 可以看出，IPS(9)整体的IGD趋势低于IPS(0)的，说明其性能比IPS(0)要好，原因是引入参考点联系算法筛选的特殊点可以使种群更快速更准确地响应环境变化，同时维持了种群的多样性.

反馈校正机制是为了解决种群中心点预测方法缺乏误差反馈和校正机制，从而预测不够准确的问题. 为了验证反馈校正机制对IPS的影响，比较具有反馈校正机制和不具有反馈校正机制的IPS，设不具有反馈校正机制的IPS为IPS(N). 选择F6和F9测试问题来比较IPS和IPS(N)在20次运行中环境变化的IGD趋势，结果如图9所示. 图中，N_c为环境变化的次数. 可以看出，IPS表现出了比IPS(N)更好的性能. 原因如下：反馈校正机制校正了预测的步长和方向，提高了预测的准确性，使种群更准确地追踪新的最优解，面对复杂测试问题F9,IPS的表现明显优于IPS(N),说明反馈校正机制应对复杂问题也较有效.

提出基于个体预测的动态多目标优化算法，种群中心点预测的非支配解集是预测种群的主体，采用反馈校正机制对其预测步长进行校正，从而更准确地追踪PF,同时引入由参考点联系算法筛选的特殊点，继而对特殊点集的预测可以快速响应环境的变化，再由混合多样性维持机制采用拉丁超立方抽样和精度可控的突变策略分别产生一部分随机个体以保持种群的多样性. 选择在FDA系列问题、DMOP系列问题以及F5~F10共13个测试问题上与其他4种算法进行比较，实验结果表明，无论是决策空间变量线性相关的问题，还是线性无关的问题，IPS都能快速响应环境的变化，获得收敛性和多样性均较好的解集.

IPS在应对不连续问题时有待改进，这也给未来的研究指明了一定的方向，如何在后2个阶段延续第1个阶段的表现将是笔者未来研究工作的重点. 此外，特殊点预测策略在种群尚未收敛的时候，可能会存在预测不准确的问题，而记忆策略对PS随时间不发生变化的问题有较好的影响，因此，将预测策略与记忆策略结合也是一项可研究的工作.