Page 151 - 《软件学报》2021年第12期

孙哲人 等:面向多目标优化的多样性代理辅助进化算法 3815

Key words: surrogate; evolutionary algorithm; multi-objective optimization; expensive problem; reference vector; model management;
Kriging

[1]
多目标优化问题(multi-objective optimization problem,简称 MOP) 是指包含两个或两个以上目标的优化
问题,其目标之间往往相互冲突且难以相互比较.由于能够较好地权衡多目标优化问题中的多个目标,进化算法
[2]
逐渐成为了很多领域中解决多目标优化问题的一种较为流行的工具 ,如经济、金融、工程 [3−5] .
在过去的 30 多年里,专家学者对多目标进化算法进行了大量的研究,提出了许多先进的算法,大体可以分
[6]
[7]
成基于支配、基于分解和基于指标这 3 种 :基于支配的算法主要有 Zitzler 等人提出的 SPEA2 和 Deb 等人提
[9]
[8]
出的 NSGA-II ,基于分解的算法主要有 Deb 等人提出的 NSGA-III 和 Zhang 等人提出的 MOEA/D [10] ,基于指
标的算法主要有 Zitzler 等人提出的 IBEA [11] 和 Beume 等人提出的 SMS-EMOA [12] .进化算法在解决多目标优化
问题时,需要对解进行大量的真实评估,即,使用原始的目标函数评估解.然而,现实中存在很多问题需要计算机
仿真、真实实验或数据驱动的方式来评估,因此其评估过程往往需要花费大量时间、人力、物力和财力,这类
问题被称为昂贵问题 [13] ,如创伤系统优化 [14] 等.对于昂贵问题,由于受到评估时间的限制,进化算法难以在短时
间内给出较好的结果.而代理辅助进化算法可以通过廉价的模型评估代替昂贵的真实评估来加速进化算法,大
大减少评估过程的代价,同时能够保证较好的优化结果.
目前,常用的代理模型主要有多项式响应模型、Kriging 模型、神经网络模型、径向基函数网络模型和支
[2]
持向量回归模型,但在选择代理模型方面缺乏理论指导 .一般来说,在使用插值法的模型中,首选的是 Kriging
模型,因为 Kriging 模型在评估解的目标值的同时,可以给出解的不确定性,而不需要额外使用其他方法来计算
不确定性.因为有此特性,Kriging 模型是代理辅助进化算法一个较为流行的选择,如 Knowles 提出的 ParEGO [15] ,
Ponweiser 等人提出的 SMS-EGO [16] ,Zhang 等人提出的 MOEA/D-EGO [17] 和 Chugh 等人提出的 K-RVEA [18] 都使
用了 Kriging 模型.
以上提到的算法是此领域较为流行且具有代表性的算法,它们选择解的时候更多关注解在模型评估下的
收敛性.但很多情况下,在模型评估下的好解是伪好解,即在真实评估下并不是好解.对于 Kriging 模型来说,训练
样本的分布对模型评估的准确度有很大的影响,训练样本在需要评估的解四周分布越广泛,则模型评估会相对
越准确 [19] .对于多目标优化问题,广泛分布在帕累托前沿(Pareto front,简称 PF)上的解,也会较为广泛分布在帕累
托最优集合(Pareto set,简称 PS)上 [20] .因此,如果能够在真实 PF 附近得到分布较为广泛的样本,Kriging 模型就可
以较好地近似真实 PF 附近的局部空间,从而增加找到在真实 PF 附近的解的可能.这就需要更多地考虑多样性,
而不只是收敛性.因此,本文提出了基于多样性的代理辅助进化算法(DSAEA)来解决昂贵多目标优化问题.
1 背景知识

1.1 多目标优化问题
多目标优化问题的一般形式如下:
min ( ) { ( ),...,f=F x 1 x f m ( )}x T
subject to ∈x R d ,
T
T
d
其中,F(x)={f 1 (x),...,f m (x)} 为 m 个目标组成的目标向量,x={x 1 ,...,x d } 为 d 个决策变量组成的决策向量,R 为 d
m
k
l
维决策空间,R 为 m 维目标空间,F 表示从决策空间映射到目标空间.当且仅当∀i={1,...,m},f i (x )≤f i (x )和
l
k
k
l
∃j={1,...,m},f j (x )<f j (x ),则称 x 支配 x .如果一个解在解集中没有解能够支配它,则称为非支配解;反之,则称为支
配解.所有非支配解的决策向量构成的集合叫做帕累托最优集合 PS,对应的目标向量构成的集合叫做帕累托前
沿 PF.
1.2 代理辅助进化算法
代理辅助进化算法中的评估方式分为两种.