-
摘要: 为了快速跟踪动态多目标优化问题变化的Pareto前沿，本文提出一种基于参考点预测策略的动态多目标优化算法（PDMOP）.该算法对关联到相同参考点的个体建立时间序列，并对这些时间序列通过线性回归模型预测新环境下种群.同时，将历史时刻的预测误差反馈到当前预测中来提高预测的准确性，并在每个预测的个体上加入扰动来增加初始种群多样性，从而能够加快算法在新环境下的收敛速度.通过4个标准测试函数对该算法测试，并和两个现有算法对比分析，结果表明所提算法在处理动态多目标优化问题时能够保持良好的性能.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 两目标优化问题的结构化参考点Fig. 1 Two-objective optimization problem structured reference point2.2 个体关联
参考点和个体的关联方式如下:首先连接每个参考点和原点作为该参考点的参考向量.对于每个参考点, 将与该参考点的参考向量距离最近的个体进行关联.算法步骤如表 1所示. 图 2给出两目标问题中个体和参考点的关联示例. 图 2中, 个体和参考点的关联用连接线表示.
表 1 个体关联算法Table 1 Individual correlation algorithm算法1 个体关联算法 步骤1 for $i=1:H$ do ///H参考点的个数 步骤2 链接参考点和原点作为该参考点参考线 步骤3 end 步骤4 for $i=1:N$ do ///N种群的个体数 步骤5 for $j=1:H$ do 步骤6 计算每个个体和参考线的距离 步骤7 end 步骤8 与个体垂直距离最小的参考点记录为关联参考点 步骤9 end 
图 2 两目标优化问题个体和参考点关联Fig. 2 Two objective optimization problem of individual associated with reference point2.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算法2 PDMOP算法伪代码 步骤1 参数及种群初始化:设置初始化参数, 时间常数τt, 种群大小pop, 进化代数max_gen, 并在决策空间内随机产生规模为pop初始种群p0t.令t=0, T=0, gen=0 步骤2 环境探测：根据式(7) 计算η (t), 如果η (t) < η则转步骤3, 否则转步骤4. 步骤3 环境未发生变化, 进化操作更新父代个体. 步骤3.1 进化操作:以一定的交叉概率pc, 变异概率pm, 对当前父代个体ptgen进行进化操作, 产生新的种群Ωgent. 步骤3.2 对Ωtgen∪ptgen快速排序, 并根据参考点关联选择个体pt+1gen作为下一代个体, 转步骤5. 步骤4 环境发生变化, 产生预测种群响应变化 步骤4.1 产生预测种群, 基于式(4) 所示预测模型, 产生与种群大小为pop的预测种群, 并将其作为下一时刻算法的初始种群. 步骤4.2 存储历史信息, 转步骤5. 步骤5 判断是否满足算法停止条件, 若满足则停止; 否则, t=t + 1, 转步骤2. 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测试函数 搜索空间 目标值, PS和PF FDA1 $[0, 1]\times[-1, 1]^{n - 1}$ FDA3 $[0, 1]\times [-1, 1]^{n - 1}$ FDA4 ${[0, 1]^n}$ FDA5 ${[0, 1]^n}$ 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均值和方差的比较), 说明本文算法能很好地适应各个动态的环境, 在每个环境下都能快速地收敛到最优解.
表 4 算法性能评价比较Table 4 The comparison of algorithm performance测试函数 性能评价指标算法 IGD HVR FDA1 DNSGA-Ⅱ 0.071365018(0.002269256) 0.71946556 (0.000297) DSS 0.02600748(0.001803211) 0.70582515 (0.000535) PDMOP 0.015680472 (0.000359908) 0.73517365 (0.000364) FDA3 DNSGA-Ⅱ 0.044540016 (0.001073) 0.71305567 (0.000135) DSS 0.025739528 (0.001627) 0.6885821 (0.001138) PDMOP 0.01396887 (0.000212644) 0.72832574 (0.00032) FDA4 DNSGA-Ⅱ 0.52746455 (0.00360) 0.9912373 (4.065E-05) DSS 0.590349722 (0.019668538) 0.991158595 (0.00059) PDMOP 0.487834225 (0.002480901) 0.9936884 (4.83E-05) FDA5 DNSGA-Ⅱ 0.815775725 (0.0609696) 0.9958528 (3.26E-05) DSS 0.785075639 (0.020305) 0.981521674 (0.00057) PDMOP 0.767482022 (0.0258126) 0.99085766 (1.58E-06) 2) HVR性能评价:对文中提到的4个标准测试函数采用3种算法独立运行30次的HVR性能指标的均值如图 7~10所示. 表 4给出10个环境下HVR性能指标的均值和方差, 可以用来比较算法在各个环境下的稳定性.
图 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-Ⅱ算法相比更接近于真实解, 从而在进化过程中能够快速地收敛到最优解.
4) 实验结论:本文所提算法PDMOP通过和关联在相同参考点建立时间序列, 当动态多目标优化问题的环境变化时, 各个时间序列分别对该环境下的最优解进行预测; 同时, 在预测模型中加入反馈思想, 即将历史的预测误差反馈到预测模型中, 使得预测结果更加稳定; 最后, 预测解附近加入高斯扰动来增加种群的多样性.使得所提算法在保持种群的多样性的同时加快收敛速度.通过与DSS和DNSGA-Ⅱ算法的实验结果比较, 可以得出PDMOP算法能够更准确地预测到新环境下的最优解集.并通过HVR和IGD性能评价指标的比较, 说明PDMOP算法能够稳定地保持最优解的多样性和收敛程度.
4. 结语
近年来, 在动态多目标优化进化算法的研究领域, 利用历史信息提高算法的求解性能吸引了越来越多的关注.针对动态多目标优化问题, 本文提出了一种基于结构化参考点的Pareto前沿预测的动态多目标优化算法.该算法利用历史信息预测新环境下最优解的潜在分布区域, 提高了算法适应环境变化的能力.本文对历史信息的提取采用了对结构化参考点关联的个体建立时间序列, 利用线性回归模型和预测误差反馈对时间序列进行预测, 并增加高斯扰动保持预测种群的多样性, 具有较高的可适应性和操作可行性.利用动态多目标优化标准测试问题进行性能测试, 结果表明本文所提PDMOP算法能够及时适应环境的变化, 迅速跟踪问题的Pareto前沿.同时, 该算法结构简单, 具有良好的可移植性.
-
图 1 两目标优化问题的结构化参考点
Fig. 1 Two-objective optimization problem structured reference point
图 2 两目标优化问题个体和参考点关联
Fig. 2 Two objective optimization problem of individual associated with reference point
表 1 个体关联算法
Table 1 Individual correlation algorithm
算法1 个体关联算法 步骤1 for $i=1:H$ do ///H参考点的个数 步骤2 链接参考点和原点作为该参考点参考线 步骤3 end 步骤4 for $i=1:N$ do ///N种群的个体数 步骤5 for $j=1:H$ do 步骤6 计算每个个体和参考线的距离 步骤7 end 步骤8 与个体垂直距离最小的参考点记录为关联参考点 步骤9 end 
下载: 导出CSV
表 2 PDMOP算法伪代码
Table 2 Pseudo code of PDMOP
算法2 PDMOP算法伪代码 步骤1 参数及种群初始化:设置初始化参数, 时间常数τt, 种群大小pop, 进化代数max_gen, 并在决策空间内随机产生规模为pop初始种群p0t.令t=0, T=0, gen=0 步骤2 环境探测：根据式(7) 计算η (t), 如果η (t) < η则转步骤3, 否则转步骤4. 步骤3 环境未发生变化, 进化操作更新父代个体. 步骤3.1 进化操作:以一定的交叉概率pc, 变异概率pm, 对当前父代个体ptgen进行进化操作, 产生新的种群Ωgent. 步骤3.2 对Ωtgen∪ptgen快速排序, 并根据参考点关联选择个体pt+1gen作为下一代个体, 转步骤5. 步骤4 环境发生变化, 产生预测种群响应变化 步骤4.1 产生预测种群, 基于式(4) 所示预测模型, 产生与种群大小为pop的预测种群, 并将其作为下一时刻算法的初始种群. 步骤4.2 存储历史信息, 转步骤5. 步骤5 判断是否满足算法停止条件, 若满足则停止; 否则, t=t + 1, 转步骤2.
下载: 导出CSV
表 3 测试函数
Table 3 Test instance
测试函数 搜索空间 目标值, PS和PF FDA1 $[0, 1]\times[-1, 1]^{n - 1}$ $\begin{array}{l} {f_1}\left( {{\pmb x}, t} \right) = {{\pmb x}_1}, {f_2}\left( {{\pmb x}, t} \right) = g\left( {1 - \sqrt {\frac{{{f_1}}}{g}} } \right)\\ g = 1 + {\sum\nolimits_{i = 2}^n {\left( {{x_i} - G\left( t \right)} \right)} ^2}, G = \sin \left( {0.5\pi \frac{t}{{{n_T}}}} \right)\\ {\rm PS}\left( t \right):0 \le {x_1} \le 1, {x_i} = G, {\rm for}{\kern 1pt} {\kern 1pt} i = 2, \cdots, n\\ {\rm PF}\left( t \right):{f_2} = 1 - \sqrt {{f_1}}, {\kern 1pt} {\kern 1pt} {\kern 1pt} 0 \le {f_1} \le 1 \end{array}$ FDA3 $[0, 1]\times [-1, 1]^{n - 1}$ $\begin{array}{l} {f_1}\left( {{\pmb x}, t} \right) = {\pmb x}_1^F, {f_2}\left( {{\pmb x}, t} \right) = g\left( {1 - \sqrt {\frac{{{f_1}}}{g}} } \right)\\ g = 1 + G + {\sum\nolimits_{i = 2}^n {\left( {{x_i} - G\left( t \right)} \right)} ^2}\\ G = \left| {\sin \left( {0.5\pi \frac{t}{{{n_T}}}} \right)} \right|, {\kern 1pt} {\kern 1pt} F = {\kern 1pt} {10^{2\sin \left( {0.5\pi t} \right)}}\\ \textrm{PS}\left( t \right):0 \le {x_1} \le 1, {x_i} = G, \textrm{for}{\kern 1pt} {\kern 1pt} i = 2, \cdots, n\\ \textrm{PF}\left( t \right):{f_2} = 1 - \sqrt {{f_1}}, {\kern 1pt} {\kern 1pt} {\kern 1pt} 0 \le {f_1} \le 1 \end{array}$ FDA4 ${[0, 1]^n}$ $\begin{array}{l} {f_1}\left( {{\pmb x}, t} \right) = \left( {1 + g} \right)\cos \left( {0.5\pi {x_1}} \right)\\ {f_2}\left( {{\pmb x}, t} \right) = \left( {1 + g} \right)\sin \left( {0.5\pi {x_1}} \right)\\ g = {\sum\nolimits_{i = 2}^n {\left( {{x_i} - G\left( t \right)} \right)} ^2}\\ G = \left| {\sin \left( {0.5\pi \frac{t}{{{n_T}}}} \right)} \right|\\ \textrm{PS}\left( t \right):0 \le {x_1} \le 1, {x_i} = G, \textrm{for}{\kern 1pt} {\kern 1pt} i = 2, \cdots, n\\ \textrm{PF}\left( t \right):f_1^2 + f_2^2 = 1 \end{array}$ FDA5 ${[0, 1]^n}$ $\begin{array}{l} {f_1}\left( {{\pmb x}, t} \right) = \left( {1 + g} \right)\cos \left( {0.5\pi {y_1}} \right)\\ {f_2}\left( {{\pmb x}, t} \right) = \left( {1 + g} \right)\sin \left( {0.5\pi {y_1}} \right)\\ g = G + {\sum\nolimits_{i = 2}^n {\left( {{x_i} - G\left( t \right)} \right)} ^2}\\ G = \left| {\sin \left( {0.5\pi \frac{t}{{{n_T}}}} \right)} \right|\\ {y_i} = x_i^F, F = 1 + 100{\sin ^4}\left( {0.5\pi t} \right)\\ \textrm{PS}\left( t \right):0 \le {x_1} \le 1, {x_i} = G, \textrm{for}{\kern 1pt} {\kern 1pt} i = 2, \cdots, n\\ \textrm{PF}\left( t \right):f_1^2 + f_2^2 = {\left( {1 + G} \right)^2} \end{array}$
下载: 导出CSV
表 4 算法性能评价比较
Table 4 The comparison of algorithm performance
测试函数 性能评价指标算法 IGD HVR FDA1 DNSGA-Ⅱ 0.071365018(0.002269256) 0.71946556 (0.000297) DSS 0.02600748(0.001803211) 0.70582515 (0.000535) PDMOP 0.015680472 (0.000359908) 0.73517365 (0.000364) FDA3 DNSGA-Ⅱ 0.044540016 (0.001073) 0.71305567 (0.000135) DSS 0.025739528 (0.001627) 0.6885821 (0.001138) PDMOP 0.01396887 (0.000212644) 0.72832574 (0.00032) FDA4 DNSGA-Ⅱ 0.52746455 (0.00360) 0.9912373 (4.065E-05) DSS 0.590349722 (0.019668538) 0.991158595 (0.00059) PDMOP 0.487834225 (0.002480901) 0.9936884 (4.83E-05) FDA5 DNSGA-Ⅱ 0.815775725 (0.0609696) 0.9958528 (3.26E-05) DSS 0.785075639 (0.020305) 0.981521674 (0.00057) PDMOP 0.767482022 (0.0258126) 0.99085766 (1.58E-06)
下载: 导出CSV
-
[1] 柴天佑, 丁进良, 王宏, 苏春翌.复杂工业过程运行的混合智能优化控制方法.自动化学报, 2008, 34(5):505-515 http://www.aas.net.cn/CN/abstract/abstract13476.shtmlChai 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 http://www.aas.net.cn/CN/abstract/abstract13476.shtml [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] 王大志, 刘士新, 郭希旺.求解总拖期时间最小化流水车间调度问题的多智能体进化算法.自动化学报, 2014, 40(3):548-555 http://www.aas.net.cn/CN/abstract/abstract18320.shtmlWang 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 http://www.aas.net.cn/CN/abstract/abstract18320.shtml [4] 田云娜, 李冬妮, 刘兆赫, 郑丹.一种基于动态决策块的超启发式跨单元调度方法.自动化学报, 2016, 42(4):524-534 http://www.aas.net.cn/CN/abstract/abstract18840.shtmlTian 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 http://www.aas.net.cn/CN/abstract/abstract18840.shtml [5] 戴文战.一种动态多目标决策模型及其应用.控制与决策, 2000, 15(2):197-200 http://www.cnki.com.cn/Article/CJFDTOTAL-KZYC200002016.htmDai 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 http://www.cnki.com.cn/Article/CJFDTOTAL-KZYC200002016.htm [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] 刘淳安.动态多目标优化进化算法及其应用.北京:科学出版社, 2011.Liu Chun-An. Dynamic Multi-Objective Optimization Evolutionary Algorithm and Its Application. Beijing:Science Press, 2011. [9] 陈志旺, 白锌, 杨七, 黄兴旺, 李国强.区间多目标优化中决策空间约束、支配及同序解筛选策略.自动化学报, 2015, 41(12):2115-2124 http://www.aas.net.cn/CN/abstract/abstract18784.shtmlChen 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 http://www.aas.net.cn/CN/abstract/abstract18784.shtml [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] 郭观七, 尹呈, 曾文静, 李武, 严太山.基于等价分量交叉相似性的Pareto支配性预测.自动化学报, 2014, 40(1):33-40 http://www.aas.net.cn/CN/abstract/abstract18264.shtmlGuo 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 http://www.aas.net.cn/CN/abstract/abstract18264.shtml [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. 期刊类型引用(32)
1. 刘阚蓉，李岩，谭树彬，刘圆超，刘建昌. 基于半监督迁移学习的动态多目标进化算法. 控制理论与应用. 2025(01): 1-12 . 
百度学术2. 李二超，刘辰淼. Pareto解集旋转的分类多策略预测动态多目标优化. 计算机工程与应用. 2024(22): 87-104 . 百度学术3. 闵芬，董文波，丁炜超. 基于决策变量时域变化特征分类的动态多目标进化算法. 自动化学报. 2024(11): 2154-2176 . 本站查看4. 陈满丽，马永杰. 使用指数平滑预测的动态多目标优化算法. 自动化与仪器仪表. 2024(12): 20-27+32 . 百度学术5. 严佳豪，张明珠，杨中国，高晶，王桂玲，赵卓峰. 基于Seq2Seq模型的工作流动态调度多目标进化算法. 郑州大学学报(理学版). 2023(01): 35-41 . 百度学术6. 徐奇，侯星，吴亚婷. 基于参考点信息预测的动态多目标优化经济决策模型研究. 安徽商贸职业技术学院学报. 2023(01): 43-47 . 百度学术7. 杨宇晴，王德睿，丁进良. 基于RAGAN的工业过程运行指标前馈-反馈多步校正. 自动化学报. 2023(05): 999-1009 . 本站查看8. 张维海，彭称称，蒋秀珊. 多目标动态优化中Pareto随机合作博弈研究综述. 控制与决策. 2023(07): 1789-1801 . 百度学术9. 梁正平，李辉才，王志强，胡凯峰，朱泽轩. 自适应变化响应的动态多目标进化算法. 自动化学报. 2023(08): 1688-1706 . 本站查看10. 唐晓乐，王宏伟，夏浩，罗洪平. 组合预测策略的动态多目标优化算法. 计算机工程与设计. 2022(07): 1930-1940 . 百度学术11. 张乾，张强. 动态规划迭代算法在末端防御中的应用. 电子设计工程. 2021(03): 104-107 . 百度学术12. 郭一楠，汤万宝，陈国玉，巩敦卫. 动态多目标进化优化研究进展. 信息与控制. 2021(02): 162-173 . 百度学术13. 崔志华，张茂清，常宇，张江江，王晖，张文生. 基于平均距离聚类的NSGA-Ⅱ. 自动化学报. 2021(05): 1171-1182 . 本站查看14. 孙惠娟，张乐乐，彭春华. 基于差异化需求响应模型预测控制的微网时域滚动优化调度. 电网技术. 2021(08): 3096-3105 . 百度学术15. 许美玲，王依雯. 基于改进差分进化和回声状态网络的时间序列预测研究. 自动化学报. 2021(07): 1589-1597 . 本站查看16. 范衠，朱贵杰，李文姬，游煜根，李晓明，林培涵，辛斌. 进化计算在复杂机电系统设计自动化中的应用综述. 自动化学报. 2021(07): 1495-1515 . 本站查看17. 张勇，胡江涛. 高计算代价动态优化问题的代理模型辅助粒子群优化算法. 陕西师范大学学报(自然科学版). 2021(05): 71-84 . 百度学术18. 陈俊杰，李洪均，曹张华. 性能感知的核心网控制面资源分配算法. 浙江大学学报(工学版). 2021(09): 1782-1787 . 百度学术19. 刁鹏飞，李树森，姜雪松. 基于多种群分解预测的动态多目标引力搜索算法. 控制与决策. 2021(12): 2910-2918 . 百度学术20. 卿东升，张晓芳，李建军，郭瑞，邓巧玲. 基于蜂群–粒子群算法的天然林空间结构优化. 系统仿真学报. 2020(03): 371-381 . 百度学术21. 覃运初，罗富贵. 动态域等值线的多目标环绕跟踪方法研究. 控制工程. 2020(03): 520-525 . 百度学术22. 李二超，赵雨萌. 基于参考线的预测策略求解动态多目标优化问题. 控制与决策. 2020(07): 1547-1560 . 百度学术23. 刘若辰，李建霞，刘静，焦李成. 动态多目标优化研究综述. 计算机学报. 2020(07): 1246-1278 . 百度学术24. 马永杰，陈满丽，陈敏. 基于Pareto解集分段预测策略的动态多目标进化算法. 计算机工程与科学. 2020(08): 1454-1462 . 百度学术25. 封文清，巩敦卫. 基于在线感知Pareto前沿划分目标空间的多目标进化优化. 自动化学报. 2020(08): 1628-1643 . 本站查看26. 马永杰，陈敏，龚影，程时升，王甄延. 动态多目标优化进化算法研究进展. 自动化学报. 2020(11): 2302-2318 . 本站查看27. 王琼，郭戈. 车队速度滚动时域动态规划及非线性控制. 自动化学报. 2019(05): 888-896 . 本站查看28. 孙燕，张弛，路兴龙，王靖戈，付俊. 具有不等式路径约束的微分代数方程系统的动态优化. 自动化学报. 2019(05): 897-905 . 本站查看29. 高开来，丁进良. 蒸馏与换热协同的约束多目标在线操作优化方法. 自动化学报. 2019(09): 1679-1690 . 本站查看30. 常红伟，夏克文，白建川，牛文佳，武盼盼. 采用云量子PSO的属性约简方法. 计算机工程与应用. 2018(10): 99-104 . 百度学术31. 刁鹏飞，毕晓君，王艳娇. 基于分解技术的动态多目标引力搜索算法. 系统工程理论与实践. 2018(05): 1300-1309 . 百度学术32. 宋涛，庄雷，景晨凯. 基于动态域等值线的多目标环绕跟踪方法研究. 小型微型计算机系统. 2018(08): 1657-1661 . 百度学术其他类型引用(44)
-
下载:
计量
- 文章访问数: 5261
- HTML全文浏览量: 1285
- PDF下载量: 2210
- 被引次数: 76
