-
摘要: 代理模型能够辅助进化算法在计算资源有限的情况下加快找到问题的最优解集, 因此建立高效的代理模型辅助多目标进化搜索逐渐受到了重视. 然而随着目标数量的增加, 对每个目标分别建立高斯过程模型时个体整体估值的不确定度会随之增加. 因此通过对模型最优解集的搜索探索原问题潜在的非支配解集, 并基于个体的收敛性, 种群的多样性和估值的不确定度, 提出了一种新的期望提高计算方法, 用于辅助从潜在的非支配解集中选择使用真实目标函数计算的个体, 从而更新代理模型, 能够在有限的计算资源下更有效地辅助优化算法找到好的非支配解集. 在7个DTLZ 基准测试问题上的实验对比结果表明, 该算法在求解计算费时高维多目标优化问题上是有效的, 且具有较强的竞争力.Abstract: Surrogate models have attracted increasing attention in assisting evolutionary many-objective optimization when the computational budget is limited since a surrogate model can assist to accelerate the search for a set of Pareto solutions. However, the approximation uncertainty of an individual on the objective approximated values will be increased when the number of objectives increases in the case that a surrogate model is trained for each objective. Therefore, we propose to explore the potential non-dominated solutions of the original optimization problem by searching for the optimal solutions of the surrogate models, and a new expected improvement in this paper, which takes into account on the convergence of the solution, the diversity of the population, and the uncertainty of the approximation, for assisting selecting solutions from the potential non-dominated solutions to be evaluated using the exact expensive objective function. The surrogate model will be updated using the new evaluated solutions and is expected to assist the optimization algorithms to efficiently find a good set of non-dominated solutions within a limited computational budget. The experimental results on seven DTLZ test problems show that our proposed method is efficient and competitive to solve expensive many-objective problems.
-
在复杂的工程优化问题中, 通常有多个目标需要同时优化, 而这些目标之间往往相互冲突和影响, 即一个目标的改善会导致至少一个其他目标的恶化, 这些问题被称为多目标优化问题[1]. 一般多目标优化问题[2]的数学模型可表示为:
$$ \begin{split} &\text{min} \, \boldsymbol{F} (\boldsymbol{x}) = (f_1 (\boldsymbol{x}),f_2 (\boldsymbol{x}), \cdots, f_M (\boldsymbol{x})) \\ & \text{s.t.} \quad \boldsymbol{x} = (x_1, x_2, \cdots, x_D)^{\rm T }\in {\bf{R}}^D \end{split} $$ (1) 其中,
$ M $ 是目标个数,$ \boldsymbol{x} $ 是$ D $ 维决策空间$ {\bf{R}}^D $ 中的一个决策向量. 在优化问题中, 进化算法(Evolutionary algorithm, EA)[3] 由于其不需要假设任何目标函数的凹凸性, 可微性或约束性, 且有更多的机会获得全局最优解, 因而获得了工业界和科学界的关注, 并且在实际工程中得到了很多应用. 求解多目标优化问题的进化算法(Multi-objective evolutionary algorithm, MOEA)[4]通常分为4大类: 1) 基于支配关系的进化多目标算法: 如快速非支配排序的遗传算法(Nondominated sorting genetic algorithm II, NSGA-II)[5-6]、提升强度的Pareto进化算法[7]; 2) 基于分解的进化多目标算法:如基于分解的多目标进化算法(Multiobjective evolutionary algorithm based on decomposition, MOEA/D)[8]、参考向量引导进化算法(Reference vector guided evolutionary algorithm, RVEA)[9]; 3) 基于指标的进化多目标算法:基于指标的进化算法[10]、基于超体积估计的算法[11]; 4) 其他算法:如基于分解和支配的高维多目标进化算法(Many-objective optimization algorithm based on dominance and decomposition, MOEA-DD)[12]、基于双目标优化的进化算法(Bi-goal evolution, BiGE)[13]. 然而, 不管哪一类现有的多目标优化进化算法, 在搜寻最优解集的过程中都需要耗费大量的性能评估次数, 而在许多实际的多目标优化问题中其目标函数的评价非常昂贵, 如: 航空发动机管路卡箍布局优化[14]中, 一台典型的航空发动机通常包含上百根管路, 而涉及计算一根管路震动频率的模拟函数评估可能需要大量的时间, 因此很大程度地限制了多目标进化算法在这类问题中的应用. 目前求解昂贵的多目标优化问题常用的方法之一是引入代理模型, 使用模型代替昂贵多目标计算的进化算法通常称为代理模型辅助的进化多目标算法(Surrogate-assisted evolutionary multi-objective optimization, SAEMO). 常见的求解多目标优化问题的SAEMO算法通常分为三类. 第1类是在多目标优化过程中直接用代理模型代替费时的目标函数计算来进行环境选择. 如Akhtar等[15]为每个目标建立一个径向基函数模型, 并提出用多个准则来选择具有代表性的点进行真实的目标函数评价. 如Zhang等[16]提出了高斯过程随机模型辅助的算法, 该算法对每个目标建立高斯过程模型, 基于分解策略将多目标问题转换成多个单目标优化问题, 根据个体每个目标的高斯过程模型估值计算切比雪夫函数值, 并利用获取函数进行环境选择. Chugh等[17]提出对每个目标函数建立高斯过程模型, 并通过目标函数估值的角度惩罚距离指标值和估值的不确定度来选择真实计算的个体, 称为克里金模型辅助 的RVEA算法(Kriging-assisted RVEA, K-RVEA). 为了提高计算费时多目标问题的优化 性能, Wang等[18]在为每个目标函数建立代理模型的基础上引入一种自适应获取函数指标, 从而提出了一种新的采样选择标准. Yang等[19]提出了离线数据驱动的多目标优化, 在进化算法中使用了粗代理模型和细代理模型两种模型, 粗代理模型用于引导算法快速地定位到较好的搜索空间, 同时细代理模型主要关注平衡粗代理模型知识迁移过来的好解. 文献[20]构建了一个正确模型和多个辅助模型作为多个优化问题, 然后利用多任务优化方法来求解这些问题, 实现了从辅助模型到正确模型的迁移. Zhao等[21]对多目标问题的每个目标建立了若干代理模型, 并基于目标空间和决策空间个体的距离提出了一种新的不确定度计算方法. 求解多目标优化问题的第2类SAEMO算法是对多目标问题的聚合函数建立代理模型, 即通过聚合函数将多目标转换为单目标, 对单目标建立代理模型, 从而辅助多目标优化. Knowles[22]基于求解单目标问题的有效全局优化算法(Efficient global optimization, EGO), 提出使用切比雪夫函数将多目标优化问题转换成单目标优化问题, 并对单目标问题建立高斯过程模型, 利用获取函数选择个体进行真实计算, 从而实现了基于EGO的Pareto面寻优算法 (Pareto optimization with the efficient global optimization, ParEGO). 代理模型辅助的多目标优化算法中第3类是根据支配关系训练分类模型, 将代理模型作为分类器辅助多目标优化算法. 如Pan等[23]引入人工神经网络来预测参考点与候选解之间的优劣关系来选择好的候选解进行真实计算, 为一种基于分类的代理模型辅助进化算法(A classification based surrogate-assisted evolutionary algorithm, CSEA). Zhang等[24]提出利用个体间的支配关系训练支持向量机分类模型来预测后代个体的质量, 从而选择好的个体作为下一个父代.虽然代理模型在单目标计算费时问题的优化中获得了较多关注, 但其在计算费时多目标优化问题中的应用还处于起步阶段, 目前还有很多亟待解决的问题.
1) 模型的选择. 目前常见的代理模型有多项式回归模型[25], 径向基函数[26-27], 高斯过程[28], 人工神经网络[29]和支持向量机[30]等. 在进化过程中选择哪一种模型对目标函数进行估值会很大程度影响算法的寻优能力.
2) 模型的用途选择. 通常情况下, 全局代理模型用于辅助提高算法的探索能力,局部代理模型用于辅助提高算法的开发能力. 而在多目标优化问题中, 由于有多个目标, 确定模型的用途更是进化多目标算法能否快速找到Pareto非支配解集的重要因素.
3) 填充标准. 如何选择个体进行真实目标函数计算并且更新模型在代理模型辅助的单目标和多目标进化优化中起着至关重要的作用, 其选择的好坏会直接影响模型更新后的准确度.
在SAEMO中, 模型估值的不确定度会影响算法的搜索方向, 从而影响算法的求解性能, 因此在优化过程中, 估值的不确定度往往和估值同时考虑. 与多项式回归、径向基函数和人工神经网络等模型相比, 高斯过程代理模型不仅能够提供个体估值, 同时还能提供估值的不确定度, 因此本文选择高斯过程模型用来作为原目标函数的估值模型, 并通过对高斯过程模型最优解集的搜索, 探索最优解集可能存在的不同领域, 从而提高算法的开发能力. 另外, 模型搜索获得的最优解集是原优化问题的潜在非支配解, 因此从中选择真实计算的个体能够加快算法对原问题的求解效率. 然而, 由于高斯过程的获取函数是针对单目标优化问题的建模提出来的, 随着目标数的增加, 对每个目标分别建立高斯过程模型时个体估值的不确定度会随之增大. 因此, 针对多目标优化问题, 考虑到个体的收敛性、种群的多样性以及估值的不确定性, 本文对高斯过程模型的期望提高(Expected improvement, EI)获取函数进行了改进. 使用角度惩罚距离函数值作为个体的收敛性指标, 所有目标估值的不确定度均值作为个体的估值不确定度, 从而使算法在选择个体进行真实计算时在开发和开采能力上达到平衡.
本文主要贡献包含以下两个方面:
1) 通过对模型最优解集的搜索提高算法的开发能力, 使其能够引导种群向具有较好目标函数值的区域进化, 并从获得的最优解集中选择个体进行真实的目标函数评价, 从而加快收敛速度.
2) 考虑个体的收敛性、种群的多样性以及估值的不确定性, 针对计算费时多目标优化问题提出一种新的填充准则.
1. 相关工作
1.1 高斯过程
高斯过程(Gaussian process, GP)是基于统计理论提出的机器学习方法[28], 其性质由均值函数
$ \mu(\boldsymbol{x}) $ 和协方差函数$ k(\boldsymbol{x}_i,\boldsymbol{x}_j) $ 唯一确定,$$ \mathbf{\mu}(\boldsymbol{x}) = {\rm{E}}[f(\boldsymbol{x})] $$ (2) $$ k(\boldsymbol{x}_i,\boldsymbol{x}_j) = {\rm{E}}[(f(\boldsymbol{x_i})-\mu(\boldsymbol{x_i}))(f(\boldsymbol{x}_j)-\mu(\boldsymbol{x}_j))] $$ (3) 其中,
$ \boldsymbol{x}_i $ ,$ \boldsymbol{x}_j $ 代表决策空间R中2个任意的$ D $ 维向量,$ \mu(\boldsymbol{x}) $ 和$ k(\boldsymbol{x}) $ 分别为均值函数和协方差函数. 因此, 给定数据集$\text{DS} = \{(\boldsymbol{x}_i, f(\boldsymbol{x}_i)), i = 1,2,\cdots,n\}$ , 假设训练集$\boldsymbol{X} = [\boldsymbol{x}_1;\boldsymbol{x}_2;\cdots;\boldsymbol{x}_n],\boldsymbol{Y} = f(\boldsymbol{x}_1); f(\boldsymbol{x}_2); \cdots; $ $ f(\boldsymbol{x}_n)]$ , 则高斯过程模型可定义如下:$$ \hat{f}(\boldsymbol{x}) = f(\boldsymbol{x}) + \varepsilon $$ (4) 其中,
$ \hat{f}(\boldsymbol{x}) $ 是高斯过程回归模型在$ \boldsymbol{x} $ 上的预测值,$ \varepsilon $ 是一个随机变量, 服从均值为零, 方差为$ {\sigma ^2} $ 的高斯分布. 由此可得$$\hat{f}(\boldsymbol{x}) \sim {\rm{N}}(0, \boldsymbol{K}+\sigma^2 {\boldsymbol{I}}) $$ (5) 其中,
$ \boldsymbol{K} $ 为$ n \times n $ 阶对称的正定协方差矩阵, 每个元素$ k_{ij} $ 表示$ \boldsymbol{x}_i $ 和$ \boldsymbol{x}_j $ 之间的相关性. 则$$ \begin{array}{l} \begin{bmatrix} \boldsymbol{Y}\\ \boldsymbol{Y^{*}} \end{bmatrix} = {\rm{N}} \begin{pmatrix} 0, \begin{bmatrix} \boldsymbol{K}(\boldsymbol{X}, \boldsymbol{X})+\sigma^2 {\boldsymbol{I}} & \boldsymbol{K}(\boldsymbol{X}, \boldsymbol{X^{*}}) \\ \boldsymbol{K}(\boldsymbol{X^{*}}, \boldsymbol{X}) & \boldsymbol{K}(\boldsymbol{X^{*}}, \boldsymbol{X^{*}}) \end{bmatrix} \end{pmatrix} \end{array} $$ (6) 式中,
$ \boldsymbol{K}(\boldsymbol{X}, \boldsymbol{X^{*}}) $ 表示测试输出样本$ \boldsymbol{X}^* $ 和训练输出样本$ \boldsymbol{X} $ 之间的协方差矩阵,$ \boldsymbol{K}(\boldsymbol{X^{*}}, \boldsymbol{X^{*}}) $ 为测试输出样本$ \boldsymbol{X}^* $ 自身的协方差矩阵.随后, 通过最大似然估计方法寻找最优的超参数, 从而最终确定高斯过程模型. 当给定输入
$ \boldsymbol{X}^* $ , 其通过训练集中的输入$ \boldsymbol{X} $ 和其观测目标输出值$ \boldsymbol{Y} $ , 预测出$ \hat{f}(\boldsymbol{X}^{*}) $ 概率最大的预测后验分布, 即$$ \hat{f}(\boldsymbol{X}^{*}|\boldsymbol{X}^{*}, \boldsymbol{X}, \boldsymbol{Y}) \sim {\rm{ N}}\left(\mu, \Sigma \right) $$ (7) 其中
$$ \mu = \boldsymbol{K}(\boldsymbol{X^{*}}, \boldsymbol{X}) (\boldsymbol{K}(\boldsymbol{X}, \boldsymbol{X})+ \sigma^2 {\boldsymbol{I}})^{-1}\boldsymbol{Y} $$ (8) $$ \begin{split} \Sigma =\;& \boldsymbol{K}(\boldsymbol{X^{*}}, \boldsymbol{X^{*}}) -\\ &\boldsymbol{K}(\boldsymbol{X^{*}}, \boldsymbol{X}) (\boldsymbol{K}(\boldsymbol{X}, \boldsymbol{X})+ \sigma^2 {\boldsymbol{I}})^{-1} \boldsymbol{K}(\boldsymbol{X}, \boldsymbol{X^{*}}) \end{split} $$ (9) 1.2 RVEA算法
RVEA算法[9]是2016年Cheng等针对高维多目标优化问题提出的基于分解的进化算法. 不同于最初提出的基于分解的多目标进化算法MOEA/D[8], RVEA中使用一组自适应的参考向量, 同时提出了角度惩罚距离(Angle penalized distance, APD)作为环境选择策略. 在RVEA中, 参考向量根据目标函数值范围的不同调整其分布,
$$ \boldsymbol{V}_{t+1,i} = \frac {\boldsymbol{V}_{0,i}\circ (\boldsymbol{V}^{\max}_{t+1} - \boldsymbol{Z}^{{\rm{min}}}_{t+1})}{\|\boldsymbol{V}_{0,i}\circ (\boldsymbol{Z}^{\max}_{t+1} - \boldsymbol{Z}^{{\rm{min}}}_{t+1})\|} $$ (10) 式中,
$ \boldsymbol{V}_{0,i} $ 表示初始化时第$ i $ 个均匀分布的参考向量,$\boldsymbol{Z}^{{\rm{max}}}_{t+1}$ 和$\boldsymbol{Z}^{{\rm{min}}}_{t+1}$ 分别表示迄今为止每个目标上的最大和最小函数值构成的向量.在RVEA中, 角度惩罚距离APD的计算方法如下:
$$ d_{t,i,j} = (1+P(\theta_{t,i,j})) \cdot \left\| \boldsymbol{F}^{'}(\boldsymbol{x}_i(t)) \right\| $$ (11) 其中,
${{{d}}_{t,i,j}}$ 表示第$ i $ 个个体在第$ t $ 代时在第$ j $ 个参考向量上的APD值,$ \theta_{t,i,j} $ 表示第$ t $ 代个体$ i $ 的目标函数值与第$ j $ 个参考向量之间的夹角.$ P(\theta_{t,i,j}) $ 为惩罚函数, 其计算公式为$$P(\theta_{t,i,j}) = M \cdot \left(\frac{t}{t_{{\rm{max}}}}\right)^{\alpha} \cdot \frac{\theta_{t,i,j}}{\gamma_{v_{t,j}}} $$ (12) 式中
$$ \gamma_{v_{t,j}} = \mathop {\min}\limits_{i \in \{ 1, \cdots ,N\} ,i \ne j} \left\langle {{\boldsymbol{V}_{t,i}},{\boldsymbol{V}_{t,j}}} \right\rangle $$ (13) $ M $ 和$ N $ 分别表示目标数和参考向量数,$t_{{\rm{max}}}$ 为种群最大进化代数,$\gamma_{v_{t,j}}$ 表示参考向量$ \boldsymbol{V}_{t,i} $ 与其他参考向量之间的最小角度,$ \alpha $ 是控制惩罚函数速率的参数. 式(11)中,$ \boldsymbol{F}^{'}(\boldsymbol{x}_i(t)) $ 表示第$ t $ 代的第$ i $ 个解归一化之后的目标函数值, 其归一化方法为:$$ \boldsymbol{F}^{'}(\boldsymbol{x}_i(t)) = \boldsymbol{F}(\boldsymbol{x}_i(t))-\boldsymbol{F}^{*} $$ (14) 式中,
$ \boldsymbol{F}(\boldsymbol{x}_i(t)) $ 是个体$ i $ 在$ t $ 代的一个目标函数值,$ \boldsymbol{F}^{*} $ 表示由每个目标最小值组成的向量.2. 代理模型辅助的计算费时进化高维多目标优化
模型的用途以及选择个体真实计算的模型填充准则对于代理模型辅助的进化算法在计算资源有限的情况下寻找计算费时问题的最优解集是非常重要的[31-33]. 随着目标空间维度的增加, 对计算费时问题的求解算法在搜索效率上有了更高的要求. 由于常见的求解高维多目标的优化算法需要大量的目标函数评价次数, 使其在求解这类费时问题时受到了很大地限制. 使用计算廉价的代理模型代替计算费时的目标函数评价是求解计算费时多目标优化问题的常见方法. 然而, 模型的使用方法会极大地影响算法的搜索效率, 特别是当目标空间维度增加时, 由于各个目标均为估值, 一个目标估值错误将会导致优化算法朝着错误的方向进行搜索, 从而严重影响最优解集的寻找. 另一方面, 在搜索最优解集的过程中,选择若干个体进行真实评价也是非常重要的. 这些真实计算的个体不仅用于更新模型, 以提高模型的估值准确度, 同时也是潜在的非支配候选解. 鉴于高斯过程模型不仅能够提供估值还能够提供估值不确定度, 本文提出使用高斯过程模型来估计目标函数值, 以辅助计算费时的高维多目标问题的优化(Surrogate-assisted expensive evolutionary many-objective optimization, SAExp-EMO). 在该方法中, 为了提高搜索效率, 首先将各个代理模型作为优化目标, 使用对求解高维多目标问题具有较好优化性能的RVEA算法对代理模型进行最优解集的搜索, 找到具有较好收敛性能的解, 从而能够提供较好的供真实计算个体选择的候选解集. 算法1给出了本文方法的伪代码. 算法1分为3个部分: 第1部分为初始化阶段(1 ~ 3行), 主要是用拉丁超立方抽样方法采样若干个体以供初始代理模型的训练, 同时获得目前的非支配解集. 第2部分是训练代理模型并对其进行最优解集的搜索(5 ~ 6行), 第3部分是通过填充准则策略从搜索到的代理模型最优解集中选择个体进行真实计算. 第2部分和第3部分交替运行, 直到满足停止条件, 即达到最大评价次数为止.
算法1. 代理模型辅助的计算费时进化多目标优化 (SAExp-EMO)
输入: 最大评价次数MaxOE;评价次数
$ OE = 0 $ ;输出: 最优解集PS
1) 使用拉丁超立方体采样
$ N_s $ 个解, 并对其使用真实的目标函数进行真实计算. 存放到数据库$ Arc $ 中;2)
$ OE = N_s $ ;3) 非支配排序
$ Arc $ 中的个体, 并将非支配解存入集合$ PS $ 中;4) While
$OE \le MaxOE;$ 5) 利用
$ Arc $ 中的样本信息为每个目标函数训练代理模型;6) 利用RVEA对模型进行最优解集的搜索(详见算法2);
7) 利用填充准则选择个体使用真实目标函数进行真实计算, 更新
$ PS $ 并存入$ Arc $ 中(参见算法3);8)
$ OE = OE + 1 $ ;9) End while.
2.1 模型最优解集的搜索
当模型能够很好地拟合原目标函数时, 搜索代理模型得到的最优解集即为原优化问题的最优解集, 并且能够大量地节省求解问题的计算时间. 因此, 为了提高对费时高维多目标优化问题的求解效率, 在SAExp-EMO中, 通过对高斯过程模型进行最优解集的搜索使种群能够落到目标函数值较好的潜在区域, 以供真实计算个体的选择. 任何求解高维多目标优化问题的算法都可以用来实现对代理模型最优解集的搜索. RVEA[9]是Cheng等在2016年提出的基于分解的求解高维多目标优化问题的有效方法, 其提供了角度惩罚距离用于在高维目标空间更好地选择下一代父代种群. 同时, 自适应参考向量可以更均匀的取到最优解集. 因此, 本文选用RVEA对高斯过程模型进行非支配最优解集的搜索.
$ \left| pop(t) \right| $ 表示当前$ t $ 代种群大小, 算法2给出了搜索模型最优解集的伪代码.算法2. 模型最优解集的搜索
输入: 模型的最大评价次数
$ L $ ; 数据库$ Arc $ ; 高斯过程模型$ GP = ({GP}_1,{GP}_2, \ldots,{GP}_M) $ ;输出: 当前种群
$ pop(t) $ ;1)
$ t = 0 $ ;2) 将
$ Arc $ 中所有个体作为RVEA的初始种群$ pop(t) $ ;3)
$ l = \left| Arc \right| $ ;4) While
$l \le L;$ 5) 产生参考向量;
6) 父代种群
$ P(t) $ 通过二进制交叉、多项式变异产生子代种群$ Q(t) $ ;7) 用GP模型对子代个体进行评价;
8) 将父代和子代个体分配给其最近的参考向量;
9) 利用APD指标进行环境选择得到下一代父代种群
$ pop(t) $ ;10) 自适应参考向量;
11)
$ l = l + \left| pop(t) \right| $ ;12)
$ t = t+1 $ ;13) End while;
14) 输出
$ pop(t) $ .2.2 改进的填充准则
模型管理是代理模型辅助的优化算法中最重要的环节
$, $ 由于真实计算的个体不仅要用于模型的更新以提高模型的估值准确度, 同时其也是潜在的最优非支配解集中的候选解, 所以填充准则的选择, 将直接影响最终获得的优化结果好坏. 常见的针对高斯过程模型提出的填充准则是针对单目标优化问题的, 不能直接用于多目标优化问题. 考虑到RVEA中角度惩罚距离指标可以同时衡量一个个体的收敛性和多样性, 故本文考虑将目标函数估值的角度惩罚距离值作为个体的性能指标. 其角度惩罚距离期望值提高越大, 说明个体的整体性能提高较大, 因此选择这类个体进行真实的目标函数计算有利于加快费时优化问题最优解集的搜索. 另一方面, 若个体估值的总体不确定度较大, 即各个目标估值不确定的累加和较大时, 表明该个体的估值不可信. 因此, 对这类个体进行真实的目标函数计算并用于模型的更新将有利于代理模型准确度的提高. 基于以上分析, 本文针对高维多目标优化问题, 提出一种改进的期望提高获取函数, 以选择具有较高价值的个体进行真实计算. 式(15) 给出了改进的期望提高获取函数.$$ \begin{split} EI(\boldsymbol{x}_i) =\;& (d^{*}-d_{t,i,j}) \Phi\left(\frac{d^{*}-d_{t,i,j}}{\tilde{s}(\boldsymbol{x}_i)}\right) +\\ &\tilde{s}(\boldsymbol{x}_i) \varphi\left(\frac{d^{*}-d_{t,i,j}}{\tilde{s}(\boldsymbol{x}_i)}\right) \end{split} $$ (15) 其中,
$ d_{t,i,j} $ 为第$ i $ 个个体在$ t $ 代相对于第$ j $ 个参考向量的APD值,$ d^{*} $ 表示$ Arc $ 中所有个体具有的最小的APD值, 即$$ d^{*} = \min\limits_{i = 1,2,\cdots,|Arc|}\{d_{t,i,j}\} $$ (16) $ s(\boldsymbol{x}_i) $ 为个体$ i $ 各个目标估值不确定度的平均值, 即$$ \tilde{s}(\boldsymbol{x}_i) = \frac{\sum\limits_{k = 1}^M{s_k}(\boldsymbol{x}_i)}{M} $$ (17) 其中,
$ s_k(\boldsymbol{x}_i) $ 表示第$ i $ 个个体在第$ k $ 个目标上的估值不确定度.算法3. 改进的填充准则
输入: 当前模型搜索的最后一代
$ pop(t) $ ; 参考向量$ \boldsymbol{V} $ ;输出: 使用真实目标函数计算的解
$ \boldsymbol{x}^* $ 1)
$ pop(t) $ 中每个个体$ \boldsymbol{x}_i $ 寻找其最近的参考向量$ \boldsymbol{V}_j $ ;2) 计算个体与最近参考向量的APD值
$ d_{t,i,j} $ ;3) 确定个体每个目标上的估值不确定度,将这些估值不确定度的平均值作为个体估值的不确定度;
4) 根据式(15)计算
$ pop(t) $ 中各个解的$ EI $ 值;5) 选择
$ pop(t) $ 中$ EI $ 值最大的个体$ \boldsymbol{x}^{*} $ .算法3给出了改进的填充准则的伪代码
$. $ 在算法3中, 将模型搜索最优解集的最后一代种群个体分配给其最近的参考向量, 并计算相应的角度惩罚距离值. 同时根据各个目标估值的不确定计算个体的整体估值不确定度(所有目标估值不确定度的平均). 随后根据个体的角度惩罚距离和平均不确定度计算其期望提高值, 从种群中选择期望值最大的个体进行真实计算.3. 实验验证
为验证本文方法的有效性, 本文在7个DTLZ基准问题[34]上进行了测试, 每个问题分别测试了3、4、 6、 8、 10个目标. 并和没有代理模型辅助的进化算法RVEA以及具有代表性的用于求解计算费时多目标优化问题的代理模型辅助算法, K-RVEA[17], CSEA[23]和ParEGO[22]进行了对比. 其中K-RVEA同样为每个目标建立代理模型并搜索模型的最优, 和本文不同的是, 在K-RVEA中优化模型的最后一代种群进行了聚类, 并根据和固定参考向量相关联的个体数差异选择APD最小或者不确定度最大的若干个体进行真实评价. CSEA是基于神经网络的求解费时问题的多目标优化问题, 通过对个体的分类选择若干有前途的个体进行真实计算. ParEGO使用切比雪夫函数将多目标优化问题转换成单目标优化问题, 并对单目标优化问题建立高斯过程模型, 利用获取函数选择个体进行真实计算.
3.1 参数设置
实验中, 所有算法的最大目标函数评价次数均设置为300次. 根据文献[34]给出的DTLZ测试函数的定义, 问题的维度为
$ K+M-1 $ ,$ M $ 为目标数, DTLZ1和DTLZ7测试函数$ K $ 的取值分别为5和20, DTLZ2-6测试函数$ K $ 取值为10. 所有算法都独立运行20次, 本文对比算法的结果都在PlatEMO上运行得到. 为了公平比较, 除了初始样本大小, 对比算法中搜索算法的参数均采用原文给出的参数, 即交叉${\eta _{{c}}}$ 和变异${\eta _{{n}}}$ 算子均为20, 交叉概率${p_{{c}}}$ 设为1.0, 变异概率${p_{{n}}}$ 设为$ 1/D $ , 其中$ D $ 为决策变量的维度. 在K-RVEA、CSEA、ParEGO中, 初始采样大小均为$ 11D-1 $ , 其测试问题维度为固定的10维. 而本文测试问题维度是不固定的, 决策空间大小由目标函数个数决定, 因此当目标维度增高, 决策空间维度也随之增大. 由于$ 11D-1 $ 占用大量评价次数, 优化代数减少不利于算法的寻优. 故本实验中K-RVEA、CSEA、ParEGO和SAExp-EMO初始样本设置都为$ N_s = 5D-1 $ . 利用置信度$ \sigma = 0.05 $ 的Wilcoxon秩和检验方法来判断本文算法和其他算法获得的解集之间的差异性. 符号$+$ 、− 和$ \approx $ 分别表示所比较的算法性能比本文SAExp-EMO算法好、差和没有明显的差异.3.2 性能指标
反转世代距离评价指标(Inverted generational distance, IGD)[35]是一个综合性能评价指标, 通常被用作衡量求解多目标优化问题方法的性能指标. 它主要通过计算每个在真实Pareto前沿面上的点(个体)到算法获取的非支配面上个体之间的最小欧式距离和, 来评价算法的收敛性能和分布性能. 值越小, 算法的综合性能越好. IGD的计算公式如下:
$$ IGD({\boldsymbol{P}},{\boldsymbol{Q}}) = \frac{{\sum\limits_{{\boldsymbol{v}} \in {\boldsymbol{P}}} d ist({\boldsymbol{v}},{\boldsymbol{Q}})}}{{|{\boldsymbol{P}}|}} $$ (18) 其中,
$ \boldsymbol{P} $ 和$ \boldsymbol{Q} $ 分别为均匀分布在真实 Pareto面上的点集和算法获得的最优Pareto面.$ dist(\boldsymbol{v},\boldsymbol{Q}) $ 为$ \boldsymbol{P} $ 中个体$ \boldsymbol{v} $ 到Pareto面$ \boldsymbol{Q} $ 的最小欧几里得距离. 因此, IGD 是通过计算真实Pareto面上点集到获取的非支配面的最小欧氏距离的平均值来评价算法的综合性能. 当$ \boldsymbol{P} $ 中个体数足够多时, 其解就会均匀的覆盖真实Pareto面, 本文中$ \left| \boldsymbol{P} \right| $ 设置为10000.3.3 实验结果及分析
3.3.1 搜索模型最优解集的最大评价次数
$ L $ 搜索模型最优解集的评价次数会影响算法对计算费时问题的寻优能力, 评价次数过少, 算法还没找到模型的最优解集, 评价次数过多, 搜索可能会偏离真实的问题最优. 为此, 本文分别使用
$ L = 0 $ ,$ L = 500\times M $ ,$ L = 1\,000\times M $ ,$ L = 1\,500\times M $ ,$ L = $ $ 2\,000\times M $ ,$ L = 2\,500\times M $ 和$ L = 3\,000\times M $ 模型评价次数对DTLZ1和DTLZ2测试问题上进行了算法性能进行了测试, 其中$ M $ 为问题的目标数. 在实验中, 目标函数分别设置为3、6、8、10进行了测试. 图1给出了不同L值下获得的IGD值. 由图1可以看出, 当搜索模型的最大评价次数为$ L = 1\,000\times $ $ M $ 时算法在这两个函数上的性能最好. 为此, 在本文的方法中, 搜索模型最优的停止条件为模型评价次数达到$ L = 1\,000\times M $ .
图 1 不同模型评价次数下算法的性能结果对比图Fig. 1 Performance comparison of the proposed method with different number of evaluations on surrogate model3.3.2 不同算法中的实验结果
为了验证本文算法的有效性, 本文算法和RVEA, ParEGO, K-RVEA以及CSEA在3、4、6、8、10个目标的DTLZ1~7测试问题上进行了实验结果对比. 需要注意的是ParEGO算法是针对目标函数个数不超过4个的多目标优化问题提出的, 因此本文单独将ParEGO和SAExp-EMO方法在3个和4个目标的DTLZ1 ~ 7测试函数上进行了对比. 表1给出了SAExp-EMO和ParEGO获得的IGD平均值的结果,其中最好结果以粗体表示. 由表1 可以看出, 本文提出的SAExp-EMO方法能够在3个目标和 4个目标的DTLZ1 ~ 7测试函数集上获得更好或者一样的IGD值, 说明SAExp-EMO算法在收敛性和多样性上具有更好的性能.
表 1 SAExp-EMO和ParEGO在3个和4个目标函数的DTLZ测试问题上获得的平均IGD统计结果Table 1 Average IGD statistical results of SAExp-EMO and ParEGO on DTLZ test problems of 3 and 4 objective functions测试问题 目标数 ParEGO SAExp-EMO DTLZ1 3 $4.84\times 10^{1}(8.51\times 10^{0})$− $\bf{1.09\times10^{1}(4.16\times 10^{0})}$ 4 $5.49\times10^{1}(1.09\times10^{1})$− $\bf{1.25\times10^{1}(5.06\times10^{1})}$ DTLZ2 3 $4.76\times10^{-1}(3.63\times10^{-2})$− $\bf{1.72\times10^{-1}(4.60\times10^{-2})} $ 4 $5.77\times10^{-1}(2.98\times10^{-2})$− $\bf{3.65\times10^{-1}(4.40\times10^{-1})}$ DTLZ3 3 $4.61\times10^{0}(5.38\times10^{1})$− $\bf{1.65\times10^{2}(6.07\times10^{1})} $ 4 $4.45\times10^{2}(7.57\times10^{1})$− $\bf{2.40\times10^{2}(1.19\times10^{2})}$ DTLZ4 3 $7.80\times10^{-1}(7.38\times10^{-2})$$\approx$ $\bf{5.59\times10^{-1}(4.80\times10^{-2})}$ 4 $8.92\times10^{-1}(9.00\times10^{-1})$− $\bf{7.12\times10^{-1}(1.48\times10^{\rm{-}1})} $ DTLZ5 3 $3.74\times10^{-1}(7.78\times10^{-2})$− $\bf{4.01\times10^{-2}(7.00\times10^{-2})}$ 4 $4.09\times10^{-1}(4.52\times10^{-2})$− $\bf{7.80\times10^{-2}(0.00\times10^{0})}$ DTLZ6 3 $8.04\times10^{0}(2.44\times10^{-1})$− $\bf{3.63\times10^{0}(2.61\times10^{0})}$ 4 $8.16\times10^{0}(2.52\times10^{-1})$− $\bf{3.84\times10^{0}(4.61\times10^{-1})}$ DTLZ7 3 $7.28\times10^{0}(2.16\times10^{0})$− $\bf{7.70\times10^{-1}(1.35\times10^{-1})}$ 4 $ 1.11\times10^{1}(7.97\times10^{-1})$− $\bf{1.09\times10^{0}(3.18\times10^{-1})}$ +/−/≈ 0/13/1 RVEA、K-RVEA和CSEA均是针对高维多目标提出的优化算法, 其中RVEA无代理模型辅助, 而K-RVEA和CSEA均为代理模型辅助的高维多目标优化方法. 表2给出了不同算法在3、4、6、8、10个目标的DTLZ上的测试结果, 其中最好结果以粗体表示. 由表2可以看出, 相比于无代理模型辅助的RVEA, 本文的SAExp-EMO在所有DTLZ测试函数上均获得了性能较好的解, 只有在4个目标的DTLZ4上获得的结果和RVEA无差别. 相比于代理模型辅助的K-RVEA, 本文方法在25个问题上获得了较好解, 在测试问题DTLZ1~7中, 除DTLZ4外, 本文算法的结果都优于K-RVEA. 这是因为 DTLZ4的Pareto前沿是一条退化的覆盖在目标空间中一个子空间曲线, 而SAExp-EMO在使用参考向量搜索模型最优解集的过程中, 有大量没有分配到解的空参考向量, 这使得收敛到Pareto前沿的求解过程缓慢, 而CSEA算法在DTLZ4上取得了最好的效果, 主要归因于CSEA中基于径向空间划分的更新参考点的策略. 从表2可以看出, SAExp-EMO算法在10个目标的DTLZ1、DTLZ2、DTLZ3和DTLZ7的结果明显优于K-RVEA, 这归因于K-RVEA模型最优解集搜索的频率是固定的, 在高维的决策空间中, 会导致种群搜索陷入局部某块区域,不利于找到有前途的候选解. 与 CSEA相比, SAExp-EMO在26个问题上获得了较好解, 只有在3个问题上没有比过CSEA, 表明了本文算法在求解高维多目标优化问题上具有较好的性能.
表 2 SAExp-EMO、RVEA、K-RVEA和CSEA得到的平均IGD值Table 2 Average IGD values obtained by SAExp-EMO, RVEA, K-RVEA and CSEA测试问题 目标数 RVEA K-RVEA CSEA SAExp-EMO DTLZ1 3 $3.65\times10^{1}(1.10\times10^{1})$− $2.48\times10^{1}(8.56\times10^{0})$− $1.97\times10^{1}(5.82\times10^{0})$− $\bf{1.33\times10^{1}(4.53\times10^{0})} $ 4 $3.18\times10^{1}(1.03\times10^{1})$− $3.01\times10^{1}(1.18\times10^{1})$− $1.71\times10^{1}(5.31\times10^{0})$− $\bf{1.35\times10^{1}(5.03\times10^{0})} $ 6 $2.96\times10^{1}(8.16\times10^{0})$− $3.18\times10^{1}(6.94\times10^{0})$− $1.43\times10^{1}(6.68\times10^{0})$− $\bf{1.15\times10^{1}(6.29\times10^{0})}$ 8 $2.00\times10^{1}(9.31\times10^{0})$− $3.22\times10^{1}(1.12\times10^{1})$$\approx$ $1.44\times10^{1}(6.01\times10^{0})$− $\bf{1.17\times10^{1}(4.46\times10^{0})} $ 10 $2.15\times10^{1}(8.45\times10^{0})$− $2.48\times10^{1}(9.28\times10^{0})$− $1.45\times10^{1}(5.70\times10^{0})$− $\bf{1.28\times10^{1}(5.45\times10^{0})}$ DTLZ2 3 $4.09\times10^{-1}(3.22\times10^{-2})$− $2.66\times10^{-1}(4.88\times10^{-2})$− $2.69\times10^{-1}(1.13\times10^{-1})$− $\bf{1.38\times10^{-1}(6.13\times10^{-2} )}$ 4 $5.16\times10^{-1}(3.61\times10^{-2})$− $3.95\times10^{-1}(4.94\times10^{-2})$− $4.76\times10^{-1}(1.04\times10^{-1})$− $\bf{3.27\times10^{-1}(5.53\times10^{-2})}$ 6 $6.97\times10^{-1}(6.73\times10^{-2})$− $5.93\times10^{-1}(4.96\times10^{-2})$− $\bf{5.76\times10^{-1}(4.01\times10^{-2})}$$\approx$ ${6.15\times10^{-1}(4.93\times10^{-2})}$ 8 $7.93\times10^{-1}(3.69\times10^{-2})$− $6.54\times10^{-1}(4.95\times10^{-2})$− $7.57\times10^{-1}(3.52\times10^{-2})$− $\bf{5.45\times10^{-1}(2.42\times10^{-1})}$ 10 $9.54\times10^{-1}(5.16\times10^{-2})$− $7.36\times10^{-1}(4.59\times10^{-2})$− $8.44\times10^{-1}(5.65\times10^{-2})$− $\bf{6.08\times10^{-1}(3.09\times10^{-1})}$ DTLZ3 3 $4.18\times10^{2}(6.66\times10^{1})$− $3.38\times10^{2}(7.51\times10^{1})$− $2.12\times10^{2}(4.37\times10^{1})$− $\bf{1.13\times10^{2}(2.96\times10^{1})}$ 4 $4.17\times10^{2}(7.54\times10^{1})$− $3.56\times10^{2}(7.56\times10^{1})$− $2.17\times10^{2}(4.94\times10^{1})$− $\bf{1.26\times10^{2}(6.16\times10^{1})}$ 6 $3.85\times10^{2}(7.05\times10^{1})$− $3.45\times10^{2}(7.90\times10^{1})$− $2.09\times10^{2}(5.44\times10^{1})$− $\bf{1.46\times10^{2}(7.89\times10^{1})}$ 8 $3.57\times10^{2}(7.05\times10^{1})$− $3.38\times10^{2}(5.74\times10^{1})$− $2.08\times10^{2}(5.09\times10^{1})$− $\bf{1.49\times10^{2}(7.88\times10^{1} )}$ 10 $3.77\times10^{2}(1.02\times10^{2})$− $3.24\times10^{2}(7.92\times10^{1})$− $2.18\times10^{2}(5.85\times10^{1})$ $\approx$ $\bf{1.10\times10^{2}(2.87\times10^{1})}$ DTLZ4 3 $5.58\times10^{-1}(6.90\times10^{-2})$− $\bf{4.17\times10^{-1}(1.12\times10^{-1})}$ $\approx$ $7.22\times10^{-1}(1.53\times10^{-1})$− $4.81\times10^{-1}(1.40\times10^{-1})$ 4 $6.96\times10^{-1}(8.80\times10^{-2})$ $\approx$ $5.46\times10^{-1}(1.13\times10^{-1})$+ $\bf{5.43\times10^{-1}(1.02\times10^{-1})}$+ $6.64\times10^{-1}(1.45\times10^{-1})$ 6 $8.53\times10^{-1}(8.13\times10^{-2})$− $6.84\times10^{-1}(8.64\times10^{-2})$+ $\bf{5.74\times10^{-1}(1.01\times10^{-1})}$ $\approx$ $8.52\times10^{-1}(8.99\times10^{-2})$ 8 $9.32\times10^{-1}(7.75\times10^{-2})$− $8.34\times10^{-1}(9.14\times10^{-2})$+ $\bf{7.39\times10^{-1}(3.42\times10^{-2})}$+ $8.36\times10^{-1}(1.76\times10^{-1})$ 10 $1.03\times10^{0}(7.03\times10^{-2})$− $8.89\times10^{-1}(6.96\times10^{-2})$ $\approx$ $\bf{8.12\times10^{-1}(4.54\times10^{-2})}$+ $8.17\times10^{-1}(2.43\times10^{-1})$ DTLZ5 3 $3.45\times10^{-1}(4.41\times10^{-2})$− $1.81\times10^{-1}(4.44\times10^{-2})$− $1.46\times10^{-1}(4.29\times10^{-2})$− $\bf{3.84\times10^{-2}(8.64\times10^{-3})}$ 4 $3.79\times10^{-1}(7.42\times10^{-2})$− $1.90\times10^{-1}(3.12\times10^{-2})$− $2.00\times10^{-1}(4.29\times10^{-2})$− $\bf{6.98\times10^{-2}(1.43\times10^{-2})}$ 6 $4.28\times10^{-1}(6.52\times10^{-2})$− $2.29\times10^{-1}(3.40\times10^{-1})$ $\approx$ $2.17\times10^{-1}(7.87\times10^{-1})$− $\bf{1.30\times10^{-1}(4.04\times10^{-2})}$ 8 $4.26\times10^{-1}(5.83\times10^{-2})$− $2.19\times10^{-1}(4.87\times10^{-2})$− $2.43\times10^{-1}(6.08\times10^{-2})$− $\bf{8.31\times10^{-2}(2.32\times10^{-2})}$ 10 $4.06\times10^{-1}(1.02\times10^{-1})$− $2.23\times10^{-1}(5.87\times10^{-2})$ $\approx$ $2.54\times10^{-1}(5.35\times10^{-2})$− $\bf{9.97\times10^{-2}(4.07\times10^{-2})} $ DTLZ6 3 $7.94\times10^{0}(2.75\times10^{-1})$− $4.42\times10^{0}(5.40\times10^{-1})$− $4.54\times10^{0}(5.84\times10^{-1})$− $\bf{3.07\times10^{0}(7.11\times10^{-1})}$ 4 $8.02\times10^{0}(2.61\times10^{-1})$− $4.35\times10^{0}(4.66\times10^{-1})$− $6.99\times10^{0}(7.87\times10^{-1})$− $\bf{3.46\times10^{0}(4.82\times10^{-1})}$ 6 $8.19\times10^{0}(3.42\times10^{-1})$− $4.58\times10^{0}(7.79\times10^{-1})$− $7.11\times10^{0}(1.76\times10^{-1})$− $\bf{4.19\times10^{0}(6.93\times10^{-1})} $ 8 $8.18\times10^{0}(2.75\times10^{-1})$− $5.78\times10^{0}(4.49\times10^{-1})$− ${7.21\times10^{0}(5.28\times10^{-1})}$$\approx$ $\bf{3.60\times10^{0}(5.11\times10^{-1})}$ 10 $8.22\times10^{0}(4.07\times10^{-1})$− $6.32e\times10^{0}(6.35\times10^{-1})$ $\approx$ $7.44\times10^{0}(4.18\times10^{-1})$ $\approx$ $\bf{3.95\times10^{0}(1.16\times10^{0})}$ DTLZ7 3 $6.85\times10^{0}(7.29\times10^{-1})$− $1.15\times10^{0}(1.69\times10^{0})$− $4.02\times10^{0}(4.82\times10^{0})$− $\bf{5.36\times10^{-1}(2.26\times10^{-1})}$ 4 $8.81\times10^{0}(1.31\times10^{0})$− $2.14\times10^{0}(3.24\times10^{0})$ $\approx$ $7.54\times10^{0}(9.33\times10^{-1})$ $\approx$ $\bf{6.92\times10^{-1}(1.37\times10^{-1})}$ 6 $1.29\times10^{1}(1.44\times10^{0})$− $3.49\times10^{0}(2.76\times10^{0})$− $1.36\times10^{1}(1.65\times10^{0})$− $ \bf{1.13\times10^{0}(2.42\times10^{-1})}$ 8 $1.72\times10^{1}(2.18\times10^{0})$− $4.18\times10^{0}(2.18\times10^{0})$− $2.26\times10^{1}(2.27\times10^{0})$− $\bf{6.82\times10^{-1}(1.38\times10^{-1})}$ 10 $2.18\times10^{1}(3.56\times10^{0})$− $7.83\times10^{0}(3.32\times10^{0})$− $2.86\times10^{1}(2.30\times10^{0})$− $\bf{1.19\times10^{0}(5.68\times10^{-1})} $ +/−/≈ 0/34/1 3/25/7 3/26/6 为进一步查看最后非支配解集的分布, 图2(a)给出了各个算法在3个目标的DTLZ1测试问题上找到的最优非支配解集. 三角形、正方形、菱形分别表示算法K-RVEA、CSEA和SAExp-EMO所获得最优非支配解集. 由图2(a)可知, SAExp-EMO所获得非支配解的目标函数值比K-RVEA和CSEA都小. 在相同的评价次数下, 相比于K-RVEA, CSEA算法SAExp-EMO获得的种群更靠近真实的Pareto前沿, 说明SAExp-EMO算法有更快和更好的收敛性, 同时从解的分布看, SAExp-EMO所找到的目标空间具有更好解的分布性. 图2(b)为K-RVEA, CSEA, 以及SAExp-EMO在3个目标DTLZ1上独立运行20次获得的IGD均值的收敛图. 由图2(b)可以看出,在相同的评价次数下, SAExp-EMO获得了比K-RVEA和CSEA更好的IGD值, 同时SAExp-EMO算法具有更快的收敛速度.
图 2 不同算法在DTLZ1上的性能结果对比Fig. 2 Performance comparison of different methods on three-objective DTLZ1 problem4. 结束语
针对代理模型辅助的计算费时多目标问题的优化, 本文提出了一种新的填充准则, 基于角度惩罚距离以及目标估值的平均不确定度, 改进期望提高计算方式, 用于选择使用真实目标函数计算的个体. 算法在3、4、6、8 和10个目标的DTLZ基准测试问题上进行了测试, 和其他有代表性的代理模型辅助的多目标进化算法的实验结果相比, 本文所提方法具有更好的求解性能.
目前, 高斯过程模型面临最大的问题是当决策空间维度增加时, 训练时间会呈现指数级增长, 导致在决策空间高维上很难使用. 为此, 如何求解决策空间高维的多目标计算费时优化问题,需要进一步展开研究.
-
图 1 不同模型评价次数下算法的性能结果对比图
Fig. 1 Performance comparison of the proposed method with different number of evaluations on surrogate model
图 2 不同算法在DTLZ1上的性能结果对比
Fig. 2 Performance comparison of different methods on three-objective DTLZ1 problem
表 1 SAExp-EMO和ParEGO在3个和4个目标函数的DTLZ测试问题上获得的平均IGD统计结果
Table 1 Average IGD statistical results of SAExp-EMO and ParEGO on DTLZ test problems of 3 and 4 objective functions
测试问题 目标数 ParEGO SAExp-EMO DTLZ1 3 $4.84\times 10^{1}(8.51\times 10^{0})$− $\bf{1.09\times10^{1}(4.16\times 10^{0})}$ 4 $5.49\times10^{1}(1.09\times10^{1})$− $\bf{1.25\times10^{1}(5.06\times10^{1})}$ DTLZ2 3 $4.76\times10^{-1}(3.63\times10^{-2})$− $\bf{1.72\times10^{-1}(4.60\times10^{-2})} $ 4 $5.77\times10^{-1}(2.98\times10^{-2})$− $\bf{3.65\times10^{-1}(4.40\times10^{-1})}$ DTLZ3 3 $4.61\times10^{0}(5.38\times10^{1})$− $\bf{1.65\times10^{2}(6.07\times10^{1})} $ 4 $4.45\times10^{2}(7.57\times10^{1})$− $\bf{2.40\times10^{2}(1.19\times10^{2})}$ DTLZ4 3 $7.80\times10^{-1}(7.38\times10^{-2})$$\approx$ $\bf{5.59\times10^{-1}(4.80\times10^{-2})}$ 4 $8.92\times10^{-1}(9.00\times10^{-1})$− $\bf{7.12\times10^{-1}(1.48\times10^{\rm{-}1})} $ DTLZ5 3 $3.74\times10^{-1}(7.78\times10^{-2})$− $\bf{4.01\times10^{-2}(7.00\times10^{-2})}$ 4 $4.09\times10^{-1}(4.52\times10^{-2})$− $\bf{7.80\times10^{-2}(0.00\times10^{0})}$ DTLZ6 3 $8.04\times10^{0}(2.44\times10^{-1})$− $\bf{3.63\times10^{0}(2.61\times10^{0})}$ 4 $8.16\times10^{0}(2.52\times10^{-1})$− $\bf{3.84\times10^{0}(4.61\times10^{-1})}$ DTLZ7 3 $7.28\times10^{0}(2.16\times10^{0})$− $\bf{7.70\times10^{-1}(1.35\times10^{-1})}$ 4 $ 1.11\times10^{1}(7.97\times10^{-1})$− $\bf{1.09\times10^{0}(3.18\times10^{-1})}$ +/−/≈ 0/13/1 
下载: 导出CSV
表 2 SAExp-EMO、RVEA、K-RVEA和CSEA得到的平均IGD值
Table 2 Average IGD values obtained by SAExp-EMO, RVEA, K-RVEA and CSEA
测试问题 目标数 RVEA K-RVEA CSEA SAExp-EMO DTLZ1 3 $3.65\times10^{1}(1.10\times10^{1})$− $2.48\times10^{1}(8.56\times10^{0})$− $1.97\times10^{1}(5.82\times10^{0})$− $\bf{1.33\times10^{1}(4.53\times10^{0})} $ 4 $3.18\times10^{1}(1.03\times10^{1})$− $3.01\times10^{1}(1.18\times10^{1})$− $1.71\times10^{1}(5.31\times10^{0})$− $\bf{1.35\times10^{1}(5.03\times10^{0})} $ 6 $2.96\times10^{1}(8.16\times10^{0})$− $3.18\times10^{1}(6.94\times10^{0})$− $1.43\times10^{1}(6.68\times10^{0})$− $\bf{1.15\times10^{1}(6.29\times10^{0})}$ 8 $2.00\times10^{1}(9.31\times10^{0})$− $3.22\times10^{1}(1.12\times10^{1})$$\approx$ $1.44\times10^{1}(6.01\times10^{0})$− $\bf{1.17\times10^{1}(4.46\times10^{0})} $ 10 $2.15\times10^{1}(8.45\times10^{0})$− $2.48\times10^{1}(9.28\times10^{0})$− $1.45\times10^{1}(5.70\times10^{0})$− $\bf{1.28\times10^{1}(5.45\times10^{0})}$ DTLZ2 3 $4.09\times10^{-1}(3.22\times10^{-2})$− $2.66\times10^{-1}(4.88\times10^{-2})$− $2.69\times10^{-1}(1.13\times10^{-1})$− $\bf{1.38\times10^{-1}(6.13\times10^{-2} )}$ 4 $5.16\times10^{-1}(3.61\times10^{-2})$− $3.95\times10^{-1}(4.94\times10^{-2})$− $4.76\times10^{-1}(1.04\times10^{-1})$− $\bf{3.27\times10^{-1}(5.53\times10^{-2})}$ 6 $6.97\times10^{-1}(6.73\times10^{-2})$− $5.93\times10^{-1}(4.96\times10^{-2})$− $\bf{5.76\times10^{-1}(4.01\times10^{-2})}$$\approx$ ${6.15\times10^{-1}(4.93\times10^{-2})}$ 8 $7.93\times10^{-1}(3.69\times10^{-2})$− $6.54\times10^{-1}(4.95\times10^{-2})$− $7.57\times10^{-1}(3.52\times10^{-2})$− $\bf{5.45\times10^{-1}(2.42\times10^{-1})}$ 10 $9.54\times10^{-1}(5.16\times10^{-2})$− $7.36\times10^{-1}(4.59\times10^{-2})$− $8.44\times10^{-1}(5.65\times10^{-2})$− $\bf{6.08\times10^{-1}(3.09\times10^{-1})}$ DTLZ3 3 $4.18\times10^{2}(6.66\times10^{1})$− $3.38\times10^{2}(7.51\times10^{1})$− $2.12\times10^{2}(4.37\times10^{1})$− $\bf{1.13\times10^{2}(2.96\times10^{1})}$ 4 $4.17\times10^{2}(7.54\times10^{1})$− $3.56\times10^{2}(7.56\times10^{1})$− $2.17\times10^{2}(4.94\times10^{1})$− $\bf{1.26\times10^{2}(6.16\times10^{1})}$ 6 $3.85\times10^{2}(7.05\times10^{1})$− $3.45\times10^{2}(7.90\times10^{1})$− $2.09\times10^{2}(5.44\times10^{1})$− $\bf{1.46\times10^{2}(7.89\times10^{1})}$ 8 $3.57\times10^{2}(7.05\times10^{1})$− $3.38\times10^{2}(5.74\times10^{1})$− $2.08\times10^{2}(5.09\times10^{1})$− $\bf{1.49\times10^{2}(7.88\times10^{1} )}$ 10 $3.77\times10^{2}(1.02\times10^{2})$− $3.24\times10^{2}(7.92\times10^{1})$− $2.18\times10^{2}(5.85\times10^{1})$ $\approx$ $\bf{1.10\times10^{2}(2.87\times10^{1})}$ DTLZ4 3 $5.58\times10^{-1}(6.90\times10^{-2})$− $\bf{4.17\times10^{-1}(1.12\times10^{-1})}$ $\approx$ $7.22\times10^{-1}(1.53\times10^{-1})$− $4.81\times10^{-1}(1.40\times10^{-1})$ 4 $6.96\times10^{-1}(8.80\times10^{-2})$ $\approx$ $5.46\times10^{-1}(1.13\times10^{-1})$+ $\bf{5.43\times10^{-1}(1.02\times10^{-1})}$+ $6.64\times10^{-1}(1.45\times10^{-1})$ 6 $8.53\times10^{-1}(8.13\times10^{-2})$− $6.84\times10^{-1}(8.64\times10^{-2})$+ $\bf{5.74\times10^{-1}(1.01\times10^{-1})}$ $\approx$ $8.52\times10^{-1}(8.99\times10^{-2})$ 8 $9.32\times10^{-1}(7.75\times10^{-2})$− $8.34\times10^{-1}(9.14\times10^{-2})$+ $\bf{7.39\times10^{-1}(3.42\times10^{-2})}$+ $8.36\times10^{-1}(1.76\times10^{-1})$ 10 $1.03\times10^{0}(7.03\times10^{-2})$− $8.89\times10^{-1}(6.96\times10^{-2})$ $\approx$ $\bf{8.12\times10^{-1}(4.54\times10^{-2})}$+ $8.17\times10^{-1}(2.43\times10^{-1})$ DTLZ5 3 $3.45\times10^{-1}(4.41\times10^{-2})$− $1.81\times10^{-1}(4.44\times10^{-2})$− $1.46\times10^{-1}(4.29\times10^{-2})$− $\bf{3.84\times10^{-2}(8.64\times10^{-3})}$ 4 $3.79\times10^{-1}(7.42\times10^{-2})$− $1.90\times10^{-1}(3.12\times10^{-2})$− $2.00\times10^{-1}(4.29\times10^{-2})$− $\bf{6.98\times10^{-2}(1.43\times10^{-2})}$ 6 $4.28\times10^{-1}(6.52\times10^{-2})$− $2.29\times10^{-1}(3.40\times10^{-1})$ $\approx$ $2.17\times10^{-1}(7.87\times10^{-1})$− $\bf{1.30\times10^{-1}(4.04\times10^{-2})}$ 8 $4.26\times10^{-1}(5.83\times10^{-2})$− $2.19\times10^{-1}(4.87\times10^{-2})$− $2.43\times10^{-1}(6.08\times10^{-2})$− $\bf{8.31\times10^{-2}(2.32\times10^{-2})}$ 10 $4.06\times10^{-1}(1.02\times10^{-1})$− $2.23\times10^{-1}(5.87\times10^{-2})$ $\approx$ $2.54\times10^{-1}(5.35\times10^{-2})$− $\bf{9.97\times10^{-2}(4.07\times10^{-2})} $ DTLZ6 3 $7.94\times10^{0}(2.75\times10^{-1})$− $4.42\times10^{0}(5.40\times10^{-1})$− $4.54\times10^{0}(5.84\times10^{-1})$− $\bf{3.07\times10^{0}(7.11\times10^{-1})}$ 4 $8.02\times10^{0}(2.61\times10^{-1})$− $4.35\times10^{0}(4.66\times10^{-1})$− $6.99\times10^{0}(7.87\times10^{-1})$− $\bf{3.46\times10^{0}(4.82\times10^{-1})}$ 6 $8.19\times10^{0}(3.42\times10^{-1})$− $4.58\times10^{0}(7.79\times10^{-1})$− $7.11\times10^{0}(1.76\times10^{-1})$− $\bf{4.19\times10^{0}(6.93\times10^{-1})} $ 8 $8.18\times10^{0}(2.75\times10^{-1})$− $5.78\times10^{0}(4.49\times10^{-1})$− ${7.21\times10^{0}(5.28\times10^{-1})}$$\approx$ $\bf{3.60\times10^{0}(5.11\times10^{-1})}$ 10 $8.22\times10^{0}(4.07\times10^{-1})$− $6.32e\times10^{0}(6.35\times10^{-1})$ $\approx$ $7.44\times10^{0}(4.18\times10^{-1})$ $\approx$ $\bf{3.95\times10^{0}(1.16\times10^{0})}$ DTLZ7 3 $6.85\times10^{0}(7.29\times10^{-1})$− $1.15\times10^{0}(1.69\times10^{0})$− $4.02\times10^{0}(4.82\times10^{0})$− $\bf{5.36\times10^{-1}(2.26\times10^{-1})}$ 4 $8.81\times10^{0}(1.31\times10^{0})$− $2.14\times10^{0}(3.24\times10^{0})$ $\approx$ $7.54\times10^{0}(9.33\times10^{-1})$ $\approx$ $\bf{6.92\times10^{-1}(1.37\times10^{-1})}$ 6 $1.29\times10^{1}(1.44\times10^{0})$− $3.49\times10^{0}(2.76\times10^{0})$− $1.36\times10^{1}(1.65\times10^{0})$− $ \bf{1.13\times10^{0}(2.42\times10^{-1})}$ 8 $1.72\times10^{1}(2.18\times10^{0})$− $4.18\times10^{0}(2.18\times10^{0})$− $2.26\times10^{1}(2.27\times10^{0})$− $\bf{6.82\times10^{-1}(1.38\times10^{-1})}$ 10 $2.18\times10^{1}(3.56\times10^{0})$− $7.83\times10^{0}(3.32\times10^{0})$− $2.86\times10^{1}(2.30\times10^{0})$− $\bf{1.19\times10^{0}(5.68\times10^{-1})} $ +/−/≈ 0/34/1 3/25/7 3/26/6
下载: 导出CSV
-
[1] 张晗, 杨继斌, 张继业, 宋鹏云, 徐晓惠. 燃料电池有轨电车能量管理Pareto多目标优化. 自动化学报, 2019, 45(12): 2378-2392Zhang Han, Yang Ji-Bin, Zhang Ji-Ye, Song Peng-Yun, Xu Xiao-Hui. Pareto-based multi-objective optimization of energy management for fuel cell tramway. Acta Automatica Sinica, 2019, 45(12): 2378-2392 [2] Coello Coello C A, Brambila G, Figueroa Gamboa S, Gamboa J F, Tapia M G C, Gómez R H. Evolutionary multiobjective optimization: open research areas and some challenges lying ahead. Complex & Intelligent Systems, 2020, 6(1), 221-236 [3] 王柳静, 张贵军, 周晓根. 基于状态估计反馈的策略自适应差分进化算法. 自动化学报, 2020, 46(4): 752-766.Wang Liu-Jing, Zhang Gui-Jun, Zhou Xiao-Gen. Strategy self-adaptive differential evolution algorithm based on state estimation feedback. Acta Automatica Sinica, 2020, 46(4): 752-766 [4] 封文清, 巩敦卫. 基于在线感知pareto前沿划分目标空间的多目标进化优化. 自动化学报, 2020, 46(8): 1628-1643Feng Wen-Qing, Gong Dun-Wei. Multi-objective evolutionary optimization with objective space partition based on online perception of pareto front. Acta Automatica Sinica, 2020, 46(8): 1628-1643 [5] Deb K, Pratap A, Genetic K, Agarwal S, Meyarivan T. A fast and elitist multiobjective genetic algorithm: NSGAII. IEEE Transactions on Evolutionary Computation, 2002, 6(2): 182-197 doi: 10.1109/4235.996017 [6] 栗三一, 王延峰, 乔俊飞, 黄金花. 一种基于区域局部搜索的NSGAII算法. 自动化学报, 2020, 46(12): 2617-2627Li San-Yi, Wang Yan-Feng, Qiao Jun-Fei, Huang Jin-Hua. A regional local search strategy for NSGAII algorithm. Acta Automatica Sinica, 2020, 46(12): 2617-2627 [7] Zitzler E, Laumanns M, Thiele L. SPEA2: Improving the performance of the strength pareto evolutionary algorithm. Technical Report Gloriastrasse, 2001, 3242(4): 742-751 [8] Zhang Q, Li H. MOEA/D: A multiobjective evolutionary algorithm based on decomposition. IEEE Transactions on Evolutionary Computation, 2007, 11(6): 712-731 doi: 10.1109/TEVC.2007.892759 [9] Cheng R, Jin Y, Olhofer M, Sendhoff B. A reference vector guided evolutionary algorithm for many-objective optimization. IEEE Transactions on Evolutionary Computation, 2006, 20(5): 773-791 [10] Zitzler E, Künzli S. Indicator-based selection in multi-objective search. In Proceedings of: International Conference on Parallel Problem Solving from Nature, Berlin, Heidelberg, 2004. 832−842 [11] Bader J, Zitzler E. HYPE: An algorithm for fast hypervolume-based many-objective optimization. Evolutionary Computation, 2011, 19(1): 45-76 doi: 10.1162/EVCO_a_00009 [12] Li K, Deb K, Zhang Q, Kwong S. An evolutionary many-objective optimization algorithm based on dominance and decomposition. IEEE Transactions on Evolutionary Computation, 2015, 19(5): 694-716 doi: 10.1109/TEVC.2014.2373386 [13] Li M, Yang S, Liu X. Bi-goal evolution for many-objective optimization problems. Artificial Intelligence, 2015, 228: 45-65 doi: 10.1016/j.artint.2015.06.007 [14] 柳强, 焦国帅. 基于Kriging模型和NSGA-II的航空发动机管路卡箍布局优化. 智能系统学报, 2019, 14(2): 281-287Liu Qiang, Jiao Guo-Shuai. Layout optimization of aero-engine pipe clamps based on kriging model and NSGAII. CAAI Transactions on Intelligent Systems, 2019, 14(2): 281-287 [15] Akhtar T, Shoemaker C A. Multi objective optimization of computationally expensive multi-modal functions with RBF surrogates and multi-rule selection. Journal of Global Optimization, 2016, 64(1): 17-32 doi: 10.1007/s10898-015-0270-y [16] Zhang Q, Liu W, Tsang E, Virginas B. Expensive multiobjective optimization by MOEA/D with Gaussian process model. IEEE Transactions on Evolutionary Computation, 2010, 14(3): 456-474 doi: 10.1109/TEVC.2009.2033671 [17] Chugh T, Jin Y, Miettinen K, Hakanen J, Sindhya K. A surrogate-assisted reference vector guided evolutionary algorithm for computationally expensive many-objective optimization. IEEE Transactions on Evolutionary Computation, 2016, 22(1): 129-142 [18] Wang X, Jin Y, Schmitt S, et al. An adaptive bayesian approach to surrogate-assisted evolutionary multi-objective optimization. Information Sciences, 2020, 519: 317-331 doi: 10.1016/j.ins.2020.01.048 [19] Yang C, Ding J, Jin Y, Chai T. Off-line data-driven multi-objective optimization: knowledge transfer between surrogates and generation of final solutions. IEEE Transactions on Evolutionary Computation, 2020, 24(3): 409-423 [20] Yang C, Ding J, Jin Y, Wang C, Chai T. Multi-tasking multi-objective evolutionary operational indices optimization of beneficiation processes. IEEE Transactions on Automation Science and Engineering, 2019, 16(3): 1046-1057 doi: 10.1109/TASE.2018.2865593 [21] Zhao Y, Sun C, Zeng J, Tan Y, Zhang G. A surrogate-ensemble assisted expensive many-objective optimization. Knowledge-Based Systems, 2020, 211: 106520 [22] Knowles J. ParEGO: A hybrid algorithm with on-line landscape approximation for expensive multiobjective optimization problems. IEEE Transactions on Evolutionary Computation, 2006, 14(1): 50-66 [23] Pan L, He C, Tian Y, Wang H, Zhang X, Jin Y. A classification based surrogate-assisted evolutionary algorithm for expensive many-objective optimization. IEEE Transactions on Evolutionary Computation, 2019, 23(1): 74-88 doi: 10.1109/TEVC.2018.2802784 [24] Zhang J, Zhou A, Zhang G. A classification and pareto domination based multiobjective evolutionary algorithm; In: Proceedings of the 2015 IEEE Congress on Evolutionary Computation. Sendai, Japan: 2015. 2883−2890 [25] Freeny A. Empirical model-building and response surfaces. Technometrics, 1987, 30(2): 229-231 [26] Yang H, Liu J. An adaptive RBF neural network control method for a class of nonlinear systems. IEEE/CAA Journal of Automatica Sinica, 2018, 5(4): 457-462 [27] Sun C, Jin Y, Cheng R, Ding J, Zeng J. Surrogate-assisted cooperative swarm optimization of high-dimensional expensive problems. IEEE Transactions on Evolutionary Computation, 2017, 21(4): 644-660 doi: 10.1109/TEVC.2017.2675628 [28] 何志昆, 刘光斌, 赵曦晶, 王明昊. 高斯过程回归方法综述. 控制与决策, 2013, 28(8): 1121-1129He Zhi-Kun, Liu Guang-Bin, Zhao Xi-Jing, Wang Ming-Hao. Overview of gaussian process regression. Control and Decision, 2013, 28(8): 1121-1129 [29] Nelson D, Wang J. Introduction to artificial neural systems. Neurocomputing, 1992, 4(6): 328-330 doi: 10.1016/0925-2312(92)90018-K [30] Cortes C, Vapnik V N. Support-vector networks. Machine Learning, 1995, 20(3): 273-293 [31] Liao P, Sun C, Zhang G, Jin Y. Multi-surrogate multi-tasking optimization of expensive problems. Knowledge-Based Systems, 2020, 205(6): 106262 [32] 田杰, 孙超利, 谭瑛, 曾建潮. 基于多点加点准则的代理模型辅助社会学习微粒群算法. 控制与决策, 2020, 35(1): 131-138Tian Jie, Sun Chao-Li, Tan Ying, Zeng Jian-Chao. Similarity-based multipoint infill criterion for surrogate-assisted social learning particle swarm optimization. Control and Decision, 2020, 35(1): 131-138 [33] Guo D, Jin Y, Ding J, Chai T. A multiple surrogate assisted decomposition based evolutionary algorithm for expensive multi/many-objective optimization. IEEE Transactions on Cybernetics, 2018, 49(3): 1012-1025 [34] Deb K, Thiele L, Laumanns M, Zitzler E. Scalable multi-objective optimization test problems. In: Proceedings of the 2002 IEEE Congress on Evolutionary Computation. Honolulu, USA: 2002. 1: 825−830 [35] Habib A, Singh H K, Chugh T, Ray T, Mettinen K. A multiple surrogate assisted decomposition based evolutionary algorithm for expensive multi/many-objective optimization. IEEE Transactions on Evolutionary Computation, 2019, 23(6): 1000-1004 doi: 10.1109/TEVC.2019.2899030 期刊类型引用(10)
1. 聂君凤，于卓然，李均利. 代理模型辅助的复杂网络能控性鲁棒性优化方法. 小型微型计算机系统. 2024(01): 151-159 . 
百度学术2. 秦淑芬，孙超利. 双阶段填充采样辅助的昂贵多目标优化. 计算机工程与设计. 2024(08): 2492-2502 . 百度学术3. 季新芳，张勇，巩敦卫，郭一楠，孙晓燕. 异构集成代理辅助的区间多模态粒子群优化算法. 自动化学报. 2024(09): 1831-1853 . 本站查看4. 张睿，潘俊铭，白晓露，胡静，张荣国，张鹏云. 面向深度分类模型超参数自优化的代理模型. 计算机应用. 2024(10): 3021-3031 . 百度学术5. 刘晓彤，孙超利，王浩，谢刚. 两阶段模型协同搜索的昂贵多目标进化优化. 控制理论与应用. 2024(09): 1676-1684 . 百度学术6. 闵芬，董文波，丁炜超. 基于决策变量时域变化特征分类的动态多目标进化算法. 自动化学报. 2024(11): 2154-2176 . 本站查看7. 叶华洋，范强，文贤馗，庞玲蓉，钟润峰，唐斌，刘卓娅. 山区小水电站智能监测与预警技术研究与应用. 电力大数据. 2024(10): 64-73 . 百度学术8. 魏凤凤，陈伟能. 自适应约束评估的代理模型辅助演化算法. 计算机科学与探索. 2023(06): 1301-1320 . 百度学术9. 梁正平，黄锡均，李燊钿，王喜瑜，朱泽轩. 基于剪枝堆栈泛化的离线数据驱动进化优化. 自动化学报. 2023(06): 1306-1325 . 本站查看10. 张睿，白晓露，潘理虎. 求解高维昂贵多目标问题的约束型Dropout代理辅助进化算法. 电子学报. 2023(07): 1859-1867 . 百度学术其他类型引用(17)
-
下载:
计量
- 文章访问数: 1265
- HTML全文浏览量: 1177
- PDF下载量: 342
- 被引次数: 27
