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

3816 Journal of Software 软件学报 Vol.32, No.12, December 2021

• 一种为真实评估,即用原昂贵问题进行评估,正如引言部分提到的,用原昂贵问题进行评估一般需要仿
真计算、真实实验、数据驱动的方式,需要巨大的代价.因此,真实评估需要被限制使用,不然优化时间
会是难以接受的;
• 另一种为模型评估,即用训练的代理模型进行评估,这种方式相比真实评估只需要非常少的消耗.
本文所涉及到的代理辅助进化算法流程如图 1 所示,更多有关代理辅助进化算法的内容可以查阅文献
[2,13].图 1 中,初始化是在决策空间内随机采样一定数量的解,并进行真实评估.这些解作为训练集,用于建立代
理模型.候选解生成算子是在模型评估下迭代优化产生候选解.选择算子是在候选解中选择部分候选解进行真
实评估,并加入到训练集以更新代理模型.此时,若未达到真实评估上限,则继续迭代优化;否则输出真实评估过
的解,即种群中的非支配解.其中,与一般进化算法的选择过程不同的是:由于受到真实评估次数的限制,同时,模
型评估与真实评估的函数值存在一定的误差,代理辅助进化算法需要选择更具代表性的解 [17] .即:在现有种群中
对候选解的收敛性与多样性进行权衡,而不是直接按照适应度值进行选择.另外,新候选解的产生并不是把当前
种群直接作为父代解,同时,真实评估的解较少,因此在代理辅助进化算法中,种群并没有明显的迭代更新过程,
而是用于保存所有真实评估过的解.

Fig.1 Flow diagram of the SAEA
图 1 代理辅助进化算法流程示意图
1.3 相关工作

目前有较多研究针对解决多目标昂贵问题的代理辅助进化算法,这里简要介绍较为流行的算法.
• Knowles 提出的 ParEGO [15] 拓展了 EGO [19] ,并首次把 EGO 用于解决多目标优化问题.ParEGO 把问题均
匀划分成多个子问题,即把多目标优化问题转化为单目标优化问题,每次随机选取一个子问题,把预期
改善(EI) [19] 作为选择策略来选择进行真实评估的解.此外,ParEGO 还限制了训练集的大小以减少建模
时间;
• Ponweiser 等人提出的 SMS-EGO [16] 使用下置信界(LCB) [21] 来划分解的支配关系,把得到的解分成非ε
支配解、ε支配解、支配解:对于非ε支配解,SMS-EGO 计算其 S-metric 作为适应度;对于ε支配解和支配
解,SMS-EGO 分配一个惩罚值作为适应度,距离非支配解越远惩罚越大.基于此选择策略来选择进行
真实评估的解.虽然 SMS-EGO 表现不错,但是由于需要大量计算 S-metric,所以它的运行时间特别长;
• Zhang 等人提出的 MOEA/D-EGO [17] 先对进化算法得到解聚类,然后把 EI 作为选择策略,在每一簇中选
择一个解进行真实评估.此外,它采用模糊聚类的方法建立代理模型,在利用所有真实评估的解的同时
减少了建模时间.与 ParEGO 相比,MOEA/D-EGO 运行速度相对更快,因为它每次批量选择解,而不只是
选择单个解;
• Chugh 等人提出的 K-RVEA [18] 更多的贡献在模型管理策略上.它把本次得到的候选解与上一次得到的
候选解分别分配到一组参考向量上:如果不活跃的参考向量在数量上的变化少于一定的数量,就采用
不确定性作为选解依据;否则采用角度惩罚距离作为选解依据.此外,K-RVEA 在更新模型的时候会筛
选解来限制训练集的大小,从而减少建模时间;