自动化学报  2017, Vol. 43 Issue (2): 313-320   PDF    
基于参考点预测的动态多目标优化算法
丁进良1, 杨翠娥1, 陈立鹏1, 柴天佑1,2     
1. 东北大学流程工业综合自动化国家重点实验室 沈阳 110004;
2. 东北大学自动化研究中心 沈阳 110004
摘要: 为了快速跟踪动态多目标优化问题变化的Pareto前沿,本文提出一种基于参考点预测策略的动态多目标优化算法(PDMOP).该算法对关联到相同参考点的个体建立时间序列,并对这些时间序列通过线性回归模型预测新环境下种群.同时,将历史时刻的预测误差反馈到当前预测中来提高预测的准确性,并在每个预测的个体上加入扰动来增加初始种群多样性,从而能够加快算法在新环境下的收敛速度.通过4个标准测试函数对该算法测试,并和两个现有算法对比分析,结果表明所提算法在处理动态多目标优化问题时能够保持良好的性能.
关键词: 动态优化     多目标优化     时间序列     预测     参考点    
Dynamic Multi-objective Optimization Algorithm Based on Reference Point Prediction
DING Jin-Liang1, YANG Cui-E1, CHEN Li-Peng1, CHAI Tian-You1,2     
1. State Key Laboratory of Integrated Automation of Process Industry, Northeastern University, Shenyang 110004;
2. Research Center of Automation, Northeastern University, Shenyang 110004
Received: 2015-12-07, Accepted: 2016-05-23.
Foundation Item: Supported by Natural Science Fundation of China (61273031, 61525302, 61590922), National Natural Science Fundation of Liaoning Province (2014020021), and Talent Support Project of Liaoning (LR2015021)
Author brief: YANG Cui-E Master student at Northeastern University. Her main research interest is evolutionary optimization algorithm;
CHEN Li-Peng Master student at Northeastern University. His main research interest is evolutionary optimization algorithm;
CHAI Tian-You Member of Chinese Engineering Academy, professor at Northeastern University. IEEE Fellow and IFAC Fellow. His research interest covers adaptive control, intelligent decoupling control, integrated automation theory, method and technology of industrial process
Corresponding author. DING Jin-Liang Professor at Northeastern University. His research interest covers modeling, operational optimization control of the complex industrial process and evolutionary computation. Corresponding author of this paper
Recommended by Associate Editor WEI Qing-Lai
Abstract: In tracking the moving Pareto front of dynamic multi-objective optimization problem as soon as possible, a new algorithm based on reference point prediction (PDMOP) is proposed. Firstly, PDMOP distributes the past individuals to different time series according to the information of reference point association. Then for these time series, a linear regression model is used to predict the new environment population. At the same time, historical prediction error is added to the current prediction to enhance prediction accuracy, and a Gauss noise is added to every new individual to increase the initialized population diversity. In this way, the algorithm can speed up convergence in the new environment. The results of four benchmark problems and the comparison with other two existing dynamic multi-objective algorithms indicate that the proposed algorithm can maintain better performance in dealing with dynamic multi-objective problems.
Key words: Dynamic optimization     multi-objective optimization     time series     prediction     reference point    

工业应用和科学研究等诸多领域中存在着大量复杂的随时间变化的多目标优化问题[1], 即动态多目标优化问题.其目标函数及约束条件不仅与决策变量有关而且随时间不断变化, 因此其最优解或最优前沿也会随着时间变化.文献表明大多的研究问题与动态多目标优化有关, 比如生产调度[2-4]、工业决策及控制[5-6]等; 许多科学研究问题, 比如机器学习、双层优化、约束优化问题等, 也可以视为动态多目标优化问题进行处理[7].然而, 该类问题具有多个依赖时间的相互冲突的目标, 且其Pareto最优前沿随时间变化.因此, 很难设计出有效的求解方法[8].

进化算法(Evolutionary algorithms, EAs) 的出现为求解动态优化问题提供了新的途径.与传统优化算法相比, EAs具有高度并行、自组织、自适应、自学习等特征, 是一种具有广泛适用性的全局优化算法[8-9].因此, 利用EAs解决动态优化问题吸引了越来越多的关注.跟踪动态问题的最优解集/前沿是EAs处理动态多目标优化问题的关键[7-8], 即要求算法能够在保持多样性的同时加快收敛速度.在动态多目标优化算法研究的早期, 许多求解静态多目标优化问题的EAs, 如NSGA-Ⅱ (A fast and elitist multiobjective genetic algorithm)[10]、SPEA-Ⅱ (Improving the strength Pareto evolutionary algorithm)[11]、DE (Differential evolution)[12]等, 经扩展和改进后被直接应用于求解动态问题[8].例如, 在静态多目标优化算法的基础上加入移民策略(如Deb等的DNSGA-Ⅱ (Dynamic multi-objective optimization and decision-making using modified NSGA-Ⅱ)[13]) 和加入免疫策略[14]的动态优化算法等.上述算法在环境变化较小的情况下能够对动态问题最优解进行跟踪.

由于动态优化问题中环境的变化并不是无章可循, 利用历史环境信息预测新环境最优解的位置是加快算法的收敛速度的可行方案.同时由于算法运行过程中产生了大量信息, 如最优解(集) 等, 基于历史信息指导新环境下的初始化种群成为解决动态多目标优化算法的另一思路.对于动态单目标优化问题, 可以直接利用历史最优解构建时间序列进行预测分析.然而, 多目标问题的历史最优解集是一系列Pareto前沿簇, 无法直接建立时间序列.因此, 如何有效地利用历史信息是目前动态多目标优化算法研究的难点和热点话题. Hatzakis等仿照动态单目标优化算法建立时间序列, 提出了一种前馈方法(Forward-looking approach)[15].当算法检测到环境变化时, 利用该策略对种群进行重新初始化.但是该方法忽略了Pareto最优前沿的分布特点, 影响了预测效果. Zhou等在利用种群中心点建立时间序列的同时考虑到Pareto最优前沿的分布特性, 提出了一种基于种群预测的动态多目标优化算法[7].该算法要求问题的动态Pareto最优解集或环境的变化模态之间具有相似性或显性规律, 降低了适应性.文献[16]所提算法将直接预测和局部搜索相结合, 在一定程度上提高了算法的收敛速度.文献[17-18]等也从不同角度设计了一些基于记忆的预测策略, 并取得了一定的效果.当前研究成果大多基于几何距离选取历史Pareto前沿簇中的部分个体建立时间序列, 一方面选择的个体规律性差, 降低了时间序列个体间的相关性, 影响了预测性能; 另一方面, 基于几何距离的个体选取方式增加了算法的计算复杂度[7, 13, 15].

基于上述问题, 综合考虑对动态Pareto最优前沿的跟踪、种群多样性及算法的可推广性等问题, 本文提出了一种基于结构化参考点预测的动态多目标优化算法(Prediction strategy for dynamic multi-objective optimization algorithm based on reference point, PDMOP).该算法将关联在同一个参考点下的个体分别建立时间序列, 对新环境下最优解集进行预测, 能够在保持多样性的同时增加预测的精度.与现有算法相比, 该算法的特点是: 1) 利用当前种群信息及历史Pareto前沿信息, 基于结构化参考点建立预测时间序列; 2) 利用参考点的结构化分布有指导地增加种群多样性, 实现收敛速度与种群多样性的平衡; 3) 在预测模型中加入历史的预测误差进行反馈, 从而使得算法更加稳定.本文利用动态标准测试问题[13, 19]对算法性能进行仿真测试, 并与DNSGA-Ⅱ算法[13]和DSS (Directed search strategy) 算法[16]进行了对比研究.结果表明, 本文所提算法能够快速跟踪动态多目标优化问题随时间变化的Pareto前沿, 并具有良好的环境适应性.

1 问题描述

一般地, 动态多目标优化问题可定义为如下形式[20]:

$\begin{eqnarray}\label{eq.1} \left\{\begin{array}{l} \min {\pmb f}( {\pmb x}, t) = \{ {f_1}( {\pmb x}, t), {f_2}( {\pmb x}, t), \cdots, {f_M}( {\pmb x}, t)\} \\ {\rm s.\, t.}\ { {\pmb g}}( {\pmb x}, t) \le 0, \\ \qquad\! {\pmb h}({\pmb x}, t) = 0, \\ \qquad\! {\pmb x} \in D \end{array} \right. \end{eqnarray}$ (1)

其中, t为时间变量, ${\pmb x}= {({x_1}, {x_2}, \cdots, {x_n})^{\rm T}}$n维决策变量, ${ {\pmb g}}$${ {\pmb h}}$分别为不等式和等式约束, D为搜索空间, ${ {\pmb f}}$为依赖于时间t变化的M维目标函数.

定义 1.  对于某一时间(环境)t, 称向量${\pmb u_t} = {(u_1^t, u_2^t, \cdots, u_M^t)^{\rm T}}$ Pareto占优向量${\pmb v_t} = {(v_1^t, v_2^t, \cdots, v_M^t)^{\rm T}}$, 当且仅当对于$\forall i \in \{ 1, 2, \cdots, M\}$, $u_i^t \le v_i^t$$\exists i \in \{ 1, 2, \cdots, M\}$, 使得$u_i^t < v_i^t$, 其中M是目标函数的个数.

定义 2.  对于某一时间(环境)t, 称向量$\pmb x_{u}\in D$为问题(1) 的Pareto最优解[21], 当且仅当不存在$\pmb x_{\nu }\in D$, 使得$\pmb \nu _{t}=f\left ( \pmb x_{\nu }, t \right )$ Pareto占优$\pmb u _{t}=f\left ( \pmb x_{u}, t \right )$.

优化问题的所有Pareto最优解构成的集合称为Pareto最优解集(Pareto-optimal set, PS); 相应的, 其PSt (Pareto set) 对应的目标函数值集合构成Pareto最优前沿(Pareto-optimal front, PF).根据Pareto最优解集和Pareto最优前沿随时间的变化情况, 动态多目标问题可分为以下4类[20]:

1)  Pateto最优解集随时间变化而Pareto最优前沿不随时间变化;

2)  Pareto最优解集和Pareto最优前沿都随时间变化;

3)  Pareto最优解集不随时间变化而Pareto最优前沿随时间变化;

4)  Pareto最优解集和Pareto最优前沿都不随时间变化.

2 动态多目标优化算法(PDMOP)

本文利用环境和历史最优解信息预测新环境下PS的初始种群来加快收敛速度, 提出一种基于参考点预测的动态多目标优化算法(PDMOP).该算法主要包括历史信息重用、个体关联、预测策略和环境检测等主要步骤, 具体如下.

2.1 历史信息重用

当环境变化后, 利用历史信息对新的PS/PF进行预测的基础是合理地挑选有效的历史信息.在动态单目标优化问题中, 仅需预测当前唯一的最优解或部分局部最优解, 历史信息的选取和重用相对简单有效.而动态多目标优化问题需要预测的是Pareto最优解集, 历史信息的重用比较困难.近年来, 为了解决静态多目标问题的多样性和收敛性问题, 运用Das等提出的方法[22]设计参考点的策略相继被提出[23-25].例如, 为了保持种群的多样性, Deb等提出NSGA-Ⅲ[23], Azzour等利用参考点的信息对个体进行排序[26]等.

本文提出了一种基于结构化参考点和种群个体关联策略来记录历史信息, 并利用该历史信息初始化新环境下的种群的方法.对于不同环境且关联在同一个参考点下的个体作为一个时间序列, 对每一时间序列利用预测模型来预测新环境下的个体.本文采用文献[27]的方法设计参考点.所设计的参考点是均匀分布在超平面上的点, 参考点的集合记为Z, 如式(2) 所示.

$\begin{eqnarray}\label{eq.2} Z:\left\{ \begin{array}{l} {\pmb Z}_i = \left( {z_i^1, z_i^2, \cdots, z_i^M} \right)\\ z_i^j \in \left\{ {\dfrac{0}{p}, \dfrac{1}{p}, \cdots, \dfrac{p}{p}} \right\}, \;\sum\limits_{j = 1}^M {z_i^j} = 1 \end{array} \right. \end{eqnarray}$ (2)

其中, $i=1, 2, \cdots, H$, $H=\binom{M+p-1}{p}$为参考点的数目, M为目标函数个数, p为每维坐标分段的数目.一般情况下, 设置$H\approx N$, N为种群大小.

对于本文解决的两目标动态优化问题, 种群大小设为100, 根据上述参考点的设置方法, 则生成参考点的个数H约为100.参考点的结构分布如图 1所示.

图 1 两目标优化问题的结构化参考点 Figure 1 Two-objective optimization problem structured reference point
2.2 个体关联

参考点和个体的关联方式如下:首先连接每个参考点和原点作为该参考点的参考向量.对于每个参考点, 将与该参考点的参考向量距离最近的个体进行关联.算法步骤如表 1所示. 图 2给出两目标问题中个体和参考点的关联示例. 图 2中, 个体和参考点的关联用连接线表示.

表 1 个体关联算法 Table 1 Individual correlation algorithm
图 2 两目标优化问题个体和参考点关联 Figure 2 Two objective optimization problem of individual associated with reference point
2.3 预测策略

每一个参考点在不同时刻按照算法1关联的Pareto最优解$\{ \cdots, {\pmb x}_{t - 3}^i, {\pmb x}_{t - 2}^i, {\pmb x}_{t - 1}^i, {\pmb x}_t^i\} {\kern 1pt} {\kern 1pt}, {\kern 1pt} {\kern 1pt} {\kern 1pt} (i = 1, 2, \cdots, N)$组成时间序列.该序列反映了最优解的变化规律.而在同一环境中, 与不同参考点关联的个体反映了当前环境的Pareto最优解集的分布.因此, 关联于每一个参考点的时间序列描述了问题Pareto解集的移动情况, 对$t+1$时刻的Pareto解集位置的预测可以表示为

$\begin{eqnarray}\label{eq.3} {\pmb x}_{t + 1}^i = f({\pmb x}_{t}^i, {\pmb x}_{_{t - 1}}^i, \cdots, {\pmb x}_{_{t - K + 1}}^i, t) \end{eqnarray}$ (3)

式中, f代表预测模型, $i = 1, 2, \cdots, H$表示参考点.为了减少预测的复杂度选用线性回归模型进行预测.前两个时刻的信息作为历史信息建立预测模型.从第三个时刻开始, 对关联在同一个参考点的个体采用如下模型预测新的个体.

$\begin{eqnarray}\label{eq.4} {\pmb x}_{t + 1}^i = {\pmb x}_t^i + \left( {{\pmb x}_t^i - {\pmb x}_{t - 1}^i} \right) + {\pmb\varepsilon} \end{eqnarray}$ (4)

其中, ${\pmb\varepsilon} = {\pmb x}_t^i - {\pmb x}_t^{i'}$t时刻的预测误差.将t时刻的预测误差反馈到$t+1$时刻的预测中来提高预测的准确性.

此外, 为保持种群多样性, 本文在每个预测个体附近产生高斯扰动$~\varsigma ~$来增加预测种群的多样性, 即:

$\begin{eqnarray}\label{eq.7} {\pmb x}_{t+1}^{i}={\pmb x}_{t+1}^{i}+\varsigma \end{eqnarray}$ (5)

高斯扰动定义如下:

$\begin{eqnarray}\label{eq.5} \varsigma \sim {\rm N}(0, {\delta ^2}) \end{eqnarray}$ (6)

其中, $\delta$为标准差:

$\begin{eqnarray}\label{eq.6} {\delta ^2} = \frac{1}{{4n}}||{{\pmb x}_t} - {{\pmb x}_{t - 1}}||_2^2 \end{eqnarray}$ (7)

其中, n为决策变量的维度.

2.4 环境检测

当环境发生变化时, 利用环境检测算子进行检测, 即算法感知到动态环境发生了变化.然后算法采用本文提出的预测策略产生预测新环境下的种群, 并将该种群作为新环境下算法的初始种群, 使得算法快速收敛到新环境下的最优解.因此, 环境检测算子的设计对问题求解至关重要, 环境探测器设计如下:

$\begin{eqnarray}\label{eq.8} \eta (t) = \frac{{\frac{1}{H}\mathop \Sigma \limits_{i = 1}^H ||f({\pmb x}_{t}^i) - f({\pmb x}_{{t - 1}}^i)||}}{{||f({\pmb x}_{t}^1) - f({\pmb x}_{t}^H)||}} \end{eqnarray}$ (8)

其中, $x_t^i$表示环境t时第i个参考点关联的个体.对于给定的探测阈值$\eta$, 当$\eta (t) > \eta$时, 则认为环境发生变化, 启用种群预测策略.

2.5 PDMOP算法步骤

PDMOP算法以静态多目标优化算法NSGA-Ⅱ算法为基本框架, PDMOP算法的伪代码如表 2所示.

表 2 PDMOP算法伪代码 Table 2 Pseudo code of PDMOP
3 实验仿真及结果分析

本文选取4个动态多目标优化标准测试问题FDA1, FDA3, FDA4, FDA5进行仿真实验, 并与文献[13]提出的DNSGA-Ⅱ算法和文献[16]提出的DSS算法进行对比研究.

3.1 测试函数

在动态多目标的4种类型中[20], 当环境变化时第一类和第二类问题对新环境下最优解的跟踪比较困难.本文提出的算法主要解决这类问题.本文采用的标准测试函数[28]中, FDA1属于动态问题分类中的第一类问题.当环境变化时, 其Pareto最优前沿面不变, 而Pareto最优解随环境变化而变化. FDA2属于动态问题分类中的第二类问题, 当环境变化时, 其Pareto最优前沿面和Pareto最优解均随环境的变化而变化. FDA1和FDA3的Pareto前沿面是一个凹形的曲面. FDA4和FDA5的Pareto前沿面是凸型曲面, 且Pareto最优解都随环境变化而变化, 但是FDA5的Pareto最优前沿面随环境变化而变化属于第二类问题, 而FDA4属于第一类问题.标准测试函数如表 3所示.

表 3 测试函数 Table 3 Test instance
3.2 参数设置

1) 问题参数设置:测试函数环境的变化幅度$\tau _T = 5$, 决策变量的维度$n = 20$.每个问题的环境变化频率为30代改变一次环境.当算法运行到300代时停止, 共10个环境, 每个算法独立运行30次.

2) 种群大小设置为100.

3) 本文算法和DNSGA-Ⅱ算法以NSGA-Ⅱ为框架进行设计, 其交叉概率为0.9, 变异概率为0.1.

4) 文献[16]中的DSS算法以DE算法为框架进行, 参数按照文献中的参数进行设置.

3.3 评价指标

动态多目标优化算法的目标是在动态环境下尽可能地收敛到动态变化的Pareto前沿${P^*}\left( t \right)$, 并且需要保持解集合$S(t)$的多样性[29].本文采用反向代距离(Inverse generation distance, IGD)[30]和超体积比(Hypervolume ratio, HVR)[31]指标来评价所提算法的综合性能.其中, IGD的定义如下:

$\begin{eqnarray} \mathrm{IGD}(t) = \frac{{\sum\limits_{i = 1}^{|{P^*}(t)|} {{d_i}} }}{{|{P^*}(t)|}} \end{eqnarray}$ (9)
$\begin{eqnarray} {d_i} = \min _{k = 1}^{|S(t)|}\sqrt {\sum\limits_{j = 1}^M {{{(f_j^{*(i)} - f_j^{(k)})}^2}} } \end{eqnarray}$ (10)

IGD$(t)$反映算法的收敛性和种群多样性.理想的IGD$(t)$值是零, 意味着$S(t)$已经得到最好的收敛性和多样性.超体积比HVR是基于超体积(Hypervolume, HV)[30]改进而来的, 反映算法保持多样性的能力, 其计算如式(10) 所示:

$\begin{eqnarray}\label{eq.9} \mathrm{HVR}(t) = \frac{{\textrm{HV}(S(t))}}{{\textrm{HV}({P^*}(t))}} \end{eqnarray}$ (11)

式中

$\begin{eqnarray}\label{eq.10} \mathrm{HV} = \textrm{volume}\left(\bigcup\nolimits_{i = 1}^{|S|} {{v_i}} \right) \end{eqnarray}$ (12)

HVR$(t)$能够给出算法保持多样性的信息, 当$S(t)$$P^*(t)$重合时, HVR$(t)$的最大值为1.因此, HVR$(t)$越大, 表明算法的多样性能越好.

3.4 实验结果及分析

1) IGD性能评价:采用FDA1, FDA3, FDA4, FDA5四个标准测试函数, 对本文算法(PDMOP), DSS和DASGA-Ⅱ三个算法分别独立运行30次进行对比实验研究.其性能评价指标IGD的统计均值分别如图 3~6所示. 10个不同环境下的30次独立运行结果的IGD均值和方差如表 4所示, 其中加粗部分表示IGD性能指标评价值比较小, 说明对应算法具有较好的多样性和收敛性.从图 3~6表 4可以看出, PDMOP算法和DSS算法的IGD相对更小, 表明本文所提算法和DSS算法得出的最优解更接近Pareto真实解; 在每个环境下本文算法的IGD性能评价指标相对平稳且都保持在很小的值(见表 4中的IGD均值和方差的比较), 说明本文算法能很好地适应各个动态的环境, 在每个环境下都能快速地收敛到最优解.

图 3 FDA1的IGD均值 Figure 3 Average IGD of FDA1
图 4 FDA3的IGD均值 Figure 4 Average IGD of FDA3
图 5 FDA4的IGD均值 Figure 5 Average IGD of FDA4
图 6 FDA5的IGD均值 Figure 6 Average IGD of FDA5
表 4 算法性能评价比较 Table 4 The comparison of algorithm performance

2) HVR性能评价:对文中提到的4个标准测试函数采用3种算法独立运行30次的HVR性能指标的均值如图 7~10所示. 表 4给出10个环境下HVR性能指标的均值和方差, 可以用来比较算法在各个环境下的稳定性.

图 7 FDA1的HVR均值 Figure 7 Average HVR of FDA1
图 8 FDA3的HVR均值 Figure 8 Average HVR of FDA3
图 9 FDA4的HVR均值 Figure 9 Average HVR of FDA4
图 10 FDA5的HVR均值 Figure 10 Average HVR of FDA5

图 7~10分别为测试函数FDA1~FDA5的HVR性能指标, 从图中可以直观看出:本文算法(PDMOP) 的HVR明显高于DSS算法和DNSGA-Ⅱ算法, 表明本文PDMOP算法能够更好地保持种群的多样性; 同时, 从表 4看出本文PDMOP算法的HVR性能指标在每个环境下变化较小, 表明本文算法能更好地适应不同环境的动态变化.

通过对算法的IGD和HVR性能评价指标的统计分析结果可知, 本文提出的PDMOP算法取得较好的收敛速度和收敛程度, 其获得的Pareto最优解在目标空间内分布均匀, 具有较好的保持种群多样性的能力.

3) 实验分析:由IGD和HVR性能评价指标分析表明本文所提算法较DSS算法和DNSGA-Ⅱ算法具有优越性.从环境变化后的初始化(预测) 种群来分析本文所提算法的优越性. 图 11~14给出t=1到t=5时刻的预测种群.从图中明显看出, 当环境变化后本文所提算法PDMOP的预测种群的解与DSS算法和DNSGA-Ⅱ算法相比更接近于真实解, 从而在进化过程中能够快速地收敛到最优解.

图 11 FDA1的预测种群 Figure 11 Prediction population of FDA1
图 12 FDA3的预测种群 Figure 12 Prediction population of FDA3
图 13 FDA4的预测种群 Figure 13 Prediction population of FDA4
图 14 FDA5的预测种群 Figure 14 Prediction population of FDA5

4) 实验结论:本文所提算法PDMOP通过和关联在相同参考点建立时间序列, 当动态多目标优化问题的环境变化时, 各个时间序列分别对该环境下的最优解进行预测; 同时, 在预测模型中加入反馈思想, 即将历史的预测误差反馈到预测模型中, 使得预测结果更加稳定; 最后, 预测解附近加入高斯扰动来增加种群的多样性.使得所提算法在保持种群的多样性的同时加快收敛速度.通过与DSS和DNSGA-Ⅱ算法的实验结果比较, 可以得出PDMOP算法能够更准确地预测到新环境下的最优解集.并通过HVR和IGD性能评价指标的比较, 说明PDMOP算法能够稳定地保持最优解的多样性和收敛程度.

4 结语

近年来, 在动态多目标优化进化算法的研究领域, 利用历史信息提高算法的求解性能吸引了越来越多的关注.针对动态多目标优化问题, 本文提出了一种基于结构化参考点的Pareto前沿预测的动态多目标优化算法.该算法利用历史信息预测新环境下最优解的潜在分布区域, 提高了算法适应环境变化的能力.本文对历史信息的提取采用了对结构化参考点关联的个体建立时间序列, 利用线性回归模型和预测误差反馈对时间序列进行预测, 并增加高斯扰动保持预测种群的多样性, 具有较高的可适应性和操作可行性.利用动态多目标优化标准测试问题进行性能测试, 结果表明本文所提PDMOP算法能够及时适应环境的变化, 迅速跟踪问题的Pareto前沿.同时, 该算法结构简单, 具有良好的可移植性.

参考文献
1 Chai Tian-You, Ding Jin-Liang, Wang Hong, Su Chun-Yi. Hybrid intelligent optimal control method for operation of complex industrial processes. Acta Automatica Sinica, 2008, 34 (5): 505–515.
( 柴天佑, 丁进良, 王宏, 苏春翌. 复杂工业过程运行的混合智能优化控制方法. 自动化学报, 2008, 34 (5): 505–515. )
2 Audsley N C, Burns A, Richardson M F, Wellings A J. Real-time scheduling:the deadline-monotonic approach. In:Proceedings of the 1991 IEEE Workshop on Real-Time Operating Systems and Software. IEEE, 1991. 133-137
3 Wang Da-Zhi, Liu Shi-Xin, Guo Xi-Wang. A multi-agent evolutionary algorithm for solving total tardiness permutation flow-shop scheduling problem. Acta Automatica Sinica, 2014, 40 (3): 548–555.
( 王大志, 刘士新, 郭希旺. 求解总拖期时间最小化流水车间调度问题的多智能体进化算法. 自动化学报, 2014, 40 (3): 548–555. )
4 Tian Yun-Na, Li Dong-Ni, Liu Zhao-He, Zheng Dan. A hyper-heuristic approach with dynamic decision blocks for inter-cell scheduling. Acta Automatica Sinica, 2016, 42 (4): 524–534.
( 田云娜, 李冬妮, 刘兆赫, 郑丹. 一种基于动态决策块的超启发式跨单元调度方法. 自动化学报, 2016, 42 (4): 524–534. )
5 Dai Wen-Zhan. A new kind of model of the dynamic multiple attribute decision making based on new effective function and its application. Control and Decision, 2000, 15 (2): 197–200.
( 戴文战. 一种动态多目标决策模型及其应用. 控制与决策, 2000, 15 (2): 197–200. )
6 Ding J L, Wang H C, Nie R, Chai T Y. Multiobjective optimization for planning of mineral processing under varied equipment capability. In:Proceedings of the 2013 International Conference on Advanced Mechatronic Systems. Luoyang, China:IEEE, 2013. 576-581
7 Zhou A M, Jin Y C, Zhang Q F. A population prediction strategy for evolutionary dynamic multiobjective optimization. IEEE Transactions on Cybernetics, 2014, 44 (1): 40–53. DOI:10.1109/TCYB.2013.2245892
8 Liu Chun-An. Dynamic Multi-Objective Optimization Evolutionary Algorithm and Its Application. Beijing: Science Press, 2011.
( 刘淳安. 动态多目标优化进化算法及其应用. 北京: 科学出版社, 2011. )
9 Chen Zhi-Wang, Bai Xin, Yang Qi, Huang Xing-Wang, Li Guo-Qiang. Strategy of constraint, dominance and screening solutions with same sequence in decision space for interval multi-objective optimization. Acta Automatica Sinica, 2015, 41 (12): 2115–2124.
( 陈志旺, 白锌, 杨七, 黄兴旺, 李国强. 区间多目标优化中决策空间约束、支配及同序解筛选策略. 自动化学报, 2015, 41 (12): 2115–2124. )
10 Deb K, Pratap A, Agarwal S, Meyarivan T. A fast and elitist multiobjective genetic algorithm:NSGA-II. IEEE Transactions on Evolutionary Computation, 2002, 6 (2): 182–197. DOI:10.1109/4235.996017
11 Zitzler E, Laumanns M, Thiele L. SPEA2:Improving the Strength Pareto Evolutionary Algorithm, TIK-Report 103, 2001.
12 Storn R, Price K. Differential evolution-a simple and efficient heuristic for global optimization over continuous spaces. Journal of Global Optimization, 1997, 11 (4): 341–359. DOI:10.1023/A:1008202821328
13 Deb K, Udaya Bhaskara Rao N, Karthik S. Dynamic multi-objective optimization and decision-making using modified NSGA-II:a case study on hydro-thermal power scheduling. In:Proceedings of the 4th International Conference on Evolutionary Multi-Criterion Optimization. Matsushima, Japan:Springer, 2007. 803-817
14 Zhang Z H. Multiobjective optimization immune algorithm in dynamic environments and its application to greenhouse control. Applied Soft Computing, 2008, 8 (2): 959–971. DOI:10.1016/j.asoc.2007.07.005
15 Hatzakis I, Wallace D. Dynamic multi-objective optimization with evolutionary algorithms:a forward-looking approach. In:Proceedings of the 8th Annual Conference on Genetic and Evolutionary Computation. Washington, USA:ACM, 2006. 1201-1208
16 Ishibuchi H, Masuda H, Tanigaki Y, Nojima Y. Difficulties in specifying reference points to calculate the inverted generational distance for many-objective optimization problems. In:Proceedings of the 2014 IEEE Symposium on Computational Intelligence in Multi-Criteria Decision-Making. Orlando, USA:IEEE, 2014. 170-177
17 Branke J. Memory enhanced evolutionary algorithms for changing optimization problems. In:Proceedings of the 1999 Congress on Evolutionary Computation. Washington, D.C., USA:IEEE, 1999.
18 Zhou A M, Jin Y C, Zhang Q F, Sendhoff B, Tsang E. Prediction-based population re-initialization for evolutionary dynamic multi-objective optimization. In:Proceedings of the 4th International Conference on Evolutionary Multi-Criterion Optimization. Matsushima, Japan:Springer, 2007. 832-846
19 Helbig M, Engelbrecht A P. Archive management for dynamic multi-objective optimisation problems using vector evaluated particle swarm optimisation. In:Proceedings of the 2011 Congress on Evolutionary Computation. New Orleans, USA:IEEE, 2011. 2047-2054
20 Farina M, Deb K, Amato P. Dynamic multiobjective optimization problems:test cases, approximation, and applications. In:Proceedings of the 2nd International Conference on Evolutionary Multi-Criterion Optimization. Faro, Portugal:Springer, 2003. 311-326
21 Guo Guan-Qi, Yin Cheng, Zeng Wen-Jing, Li Wu, Yan Tai-Shan. Prediction of Pareto dominance by cross similarity of equivalent components. Acta Automatica Sinica, 2014, 40 (1): 33–40.
( 郭观七, 尹呈, 曾文静, 李武, 严太山. 基于等价分量交叉相似性的Pareto支配性预测. 自动化学报, 2014, 40 (1): 33–40. )
22 Das I, Dennis J E. Normal-boundary intersection:a new method for generating the Pareto surface in nonlinear multicriteria optimization problems. SIAM Journal on Optimization, 1998, 8 (3): 631–657. DOI:10.1137/S1052623496307510
23 Deb K, Jain H. An evolutionary many-objective optimization algorithm using reference-point-based nondominated sorting approach, Part I:Solving problems with box constraints. IEEE Transactions on Evolutionary Computation, 2014, 18 (4): 577–601. DOI:10.1109/TEVC.2013.2281535
24 Asafuddoula M, Ray T, Sarker R. A decomposition based evolutionary algorithm for many objective optimization with systematic sampling and adaptive epsilon control. In:Proceedings of the 7th International Conference on Evolutionary Multi-Criterion Optimization. Sheffield, UK:Springer, 2013. 413-427
25 Jain H, Deb K. An evolutionary many-objective optimization algorithm using reference-point based nondominated sorting approach, Part II:handling constraints and extending to an adaptive approach. IEEE Transactions on Evolutionary Computation, 2014, 18 (4): 602–622. DOI:10.1109/TEVC.2013.2281534
26 Azzouz R, Bechikh S, Ben Said L. A multiple reference point-based evolutionary algorithm for dynamic multi-objective optimization with undetectable changes. In:Proceedings of the 2014 IEEE Congress on Evolutionary Computation. Beijing, China:IEEE, 2014. 3168-3175
27 Cheng R, Jin Y C, Narukawa K, Sendhoff B. A multiobjective evolutionary algorithm using Gaussian process-based inverse modeling. IEEE Transactions on Evolutionary Computation, 2015, 19 (6): 838–856. DOI:10.1109/TEVC.2015.2395073
28 Farina M, Deb K, Amato P. Dynamic multiobjective optimization problems:test cases, approximations, and applications. IEEE Transactions on Evolutionary Computation, 2004, 8 (5): 425–442. DOI:10.1109/TEVC.2004.831456
29 Li X D, Branke J, Kirley M. On performance metrics and particle swarm methods for dynamic multiobjective optimization problems. In:Proceedings of the 2007 IEEE Congress on Evolutionary Computation. Singapore:IEEE, 2007. 576-583
30 Zhang Q F, Zhou A M, Jin Y C. RM-MEDA:a regularity model-based multiobjective estimation of distribution algorithm. IEEE Transactions on Evolutionary Computation, 2008, 12 (1): 41–63. DOI:10.1109/TEVC.2007.894202
31 Van Veldhuizen D A. Multiobjective Evolutionary Algorithms:Classifications, Analyses, and New Innovations[Ph.D. dissertation], Air Force Institute of Technology Wright Patterson AFB, OH, USA, 1999.