模型辅助的计算费时进化高维多目标优化

孙超利 李 贞 金耀初

在复杂的工程优化问题中,通常有多个目标需要同时优化,而这些目标之间往往相互冲突和影响,即一个目标的改善会导致至少一个其他目标的恶化,这些问题被称为多目标优化问题[1].一般多目标优化问题[2]的数学模型可表示为:

其中,M是目标个数,x是D维决策空间 RD中的一个决策向量.在优化问题中,进化算法(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],其性质由均值函数μ(x) 和协方差函数k(xi,xj)唯一确定,

其中,xi,xj代表决策空间R 中2 个任意的D维向量,μ(x)和k(x)分别为均值函数和协方差函数.因此,给定数据集 D S={(xi,f(xi)),i=1,2,···,n},假设训练集X=[x1;x2;···;xn],Y=f(x1);f(x2);···;f(xn)],则高斯过程模型可定义如下:

其中,K为n×n阶对称的正定协方差矩阵,每个元素kij表示xi和xj之间的相关性.则

式中,K(X,X*) 表示测试输出样本X*和训练输出样本X之间的协方差矩阵,K(X*,X*)为测试输出样本X*自身的协方差矩阵.

随后,通过最大似然估计方法寻找最优的超参数,从而最终确定高斯过程模型.当给定输入X*,其通过训练集中的输入X和其观测目标输出值Y,预测出概率最大的预测后验分布,即

1.2 RVEA 算法

RVEA 算法[9]是2016 年Cheng 等针对高维多目标优化问题提出的基于分解的进化算法.不同于最初提出的基于分解的多目标进化算法MOEA/D[8],RVEA 中使用一组自适应的参考向量,同时提出了角度惩罚距离(Angle penalized distance,APD)作为环境选择策略.在RVEA 中,参考向量根据目标函数值范围的不同调整其分布,

其中,dt,i,j表示第i个个体在第t代时在第j个参考向量上的APD 值,θt,i,j表示第t代个体i的目标函数值与第j个参考向量之间的夹角.P(θt,i,j)为惩罚函数,其计算公式为

M和N分别表示目标数和参考向量数,tmax为种群最大进化代数,γvt,j表示参考向量Vt,i与其他参考向量之间的最小角度,α是控制惩罚函数速率的参数.式(11) 中,F′(xi(t)) 表示第t代的第i个解归一化之后的目标函数值,其归一化方法为:

式中,F(xi(t)) 是个体i在t代的一个目标函数值,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)

2.1 模型最优解集的搜索

当模型能够很好地拟合原目标函数时,搜索代理模型得到的最优解集即为原优化问题的最优解集,并且能够大量地节省求解问题的计算时间.因此,为了提高对费时高维多目标优化问题的求解效率,在SAExp-EMO 中,通过对高斯过程模型进行最优解集的搜索使种群能够落到目标函数值较好的潜在区域,以供真实计算个体的选择.任何求解高维多目标优化问题的算法都可以用来实现对代理模型最优解集的搜索.RVEA[9]是Cheng 等在2016年提出的基于分解的求解高维多目标优化问题的有效方法,其提供了角度惩罚距离用于在高维目标空间更好地选择下一代父代种群.同时,自适应参考向量可以更均匀的取到最优解集.因此,本文选用RVEA 对高斯过程模型进行非支配最优解集的搜索.|pop(t)|表示当前t代种群大小,算法2 给出了搜索模型最优解集的伪代码.

2.2 改进的填充准则

模型管理是代理模型辅助的优化算法中最重要的环节,由于真实计算的个体不仅要用于模型的更新以提高模型的估值准确度,同时其也是潜在的最优非支配解集中的候选解,所以填充准则的选择,将直接影响最终获得的优化结果好坏.常见的针对高斯过程模型提出的填充准则是针对单目标优化问题的,不能直接用于多目标优化问题.考虑到RVEA中角度惩罚距离指标可以同时衡量一个个体的收敛性和多样性,故本文考虑将目标函数估值的角度惩罚距离值作为个体的性能指标.其角度惩罚距离期望值提高越大,说明个体的整体性能提高较大,因此选择这类个体进行真实的目标函数计算有利于加快费时优化问题最优解集的搜索.另一方面,若个体估值的总体不确定度较大,即各个目标估值不确定的累加和较大时,表明该个体的估值不可信.因此,对这类个体进行真实的目标函数计算并用于模型的更新将有利于代理模型准确度的提高.基于以上分析,本文针对高维多目标优化问题,提出一种改进的期望提高获取函数,以选择具有较高价值的个体进行真实计算.式(15) 给出了改进的期望提高获取函数.

其中,dt,i,j为第i个个体在t代相对于 第j个参考向量的APD 值,d*表示Arc中所有个体具有的最小的APD 值,即

s(xi) 为个体i各个目标估值不确定度的平均值,即

其中,sk(xi) 表示第i个个体在第k个目标上的估值不确定度.

算法3.改进的填充准则

算法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上运行得到.为了公平比较,除了初始样本大小,对比算法中搜索算法的参数均采用原文给出的参数,即交叉ηc和变异ηn算子均为20,交叉概率pc设为1.0,变异概率pn设为 1/D,其中D为决策变量的维度.在K-RVEA、CSEA、ParEGO 中,初始采样大小均为 11D-1,其测试问题维度为固定的10 维.而本文测试问题维度是不固定的,决策空间大小由目标函数个数决定,因此当目标维度增高,决策空间维度也随之增大.由于 11D-1 占用大量评价次数,优化代数减少不利于算法的寻优.故本实验中K-RVEA、CSEA、ParEGO 和SAExp-EMO 初始样本设置都为Ns=5D-1 .利用置信度σ=0.05的Wilcoxon 秩和检验方法来判断本文算法和其他算法获得的解集之间的差异性.符号+、-和≈分别表示所比较的算法性能比本文SAExp-EMO 算法好、差和没有明显的差异.

3.2 性能指标

反转世代距离评价指标(Inverted generational distance,IGD)[35]是一个综合性能评价指标,通常被用作衡量求解多目标优化问题方法的性能指标.它主要通过计算每个在真实Pareto 前沿面上的点(个体)到算法获取的非支配面上个体之间的最小欧式距离和,来评价算法的收敛性能和分布性能.值越小,算法的综合性能越好.IGD 的计算公式如下:

其中,P和Q分别为均匀分布在真实 Pareto 面上的点集和算法获得的最优Pareto 面.dist(v,Q)为P中个体v到Pareto 面Q的最小欧几里得距离.因此,IGD 是通过计算真实Pareto 面上点集到获取的非支配面的最小欧氏距离的平均值来评价算法的综合性能.当P中个体数足够多时,其解就会均匀的覆盖真实Pareto 面,本文中|P|设置为10 000.

3.3 实验结果及分析

3.3.1 搜索模型最优解集的最大评价次数L

搜索模型最优解集的评价次数会影响算法对计算费时问题的寻优能力,评价次数过少,算法还没找到模型的最优解集,评价次数过多,搜索可能会偏离真实的问题最优.为此,本文分别使用L=0,L=500×M,L=1 000×M,L=1 500×M,L=2 000×M,L=2 500×M和L=3 000×M模型评价次数对DTLZ1 和DTLZ2 测试问题上进行了算法性能进行了测试,其中M为问题的目标数.在实验中,目标函数分别设置为3、6、8、10 进行了测试.图1 给出了不同L值下获得的IGD 值.由图1可以看出,当搜索模型的最大评价次数为L=1 000×M时算法在这两个函数上的性能最好.为此,在本文的方法中,搜索模型最优的停止条件为模型评价次数达到L=1 000×M.

图1 不同模型评价次数下算法的性能结果对比图Fig.1 Performance comparison of the proposed method with different number of evaluations on surrogate model

3.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

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

为进一步查看最后非支配解集的分布,图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 problem

4 结束语

针对代理模型辅助的计算费时多目标问题的优化,本文提出了一种新的填充准则,基于角度惩罚距离以及目标估值的平均不确定度,改进期望提高计算方式,用于选择使用真实目标函数计算的个体.算法在3、4、6、8 和10 个目标的DTLZ 基准测试问题上进行了测试,和其他有代表性的代理模型辅助的多目标进化算法的实验结果相比,本文所提方法具有更好的求解性能.

目前,高斯过程模型面临最大的问题是当决策空间维度增加时,训练时间会呈现指数级增长,导致在决策空间高维上很难使用.为此,如何求解决策空间高维的多目标计算费时优化问题,需要进一步展开研究.