模型辅助的计算费时进化高维多目标优化
2022-04-20 17:47阅读：
引用本文
孙超利, 李贞, 金耀初. 模型辅助的计算费时进化高维多目标优化. 自动化学报, 2022, 48(4):
1119−1128 doi: 10.16383/j.aas.c200969
Sun Chao-Li, Li Zhen, Jin Yao-Chu. Surrogate-assisted
expensive evolutionary many-objective optimization. Acta Automatica
Sinica, 2022, 48(4): 1119−1128 doi:
10.16383/j.aas.c200969
http://www.aas.net.cn/cn/article/doi/10.16383/j.aas.c200969?viewType=HTML
文章简介
关键词
高维多目标优化, 代理模型, 计算费时问题, 填充准则
摘 要
代理模型能够辅助进化算法在计算资源有限的情况下加快找到问题的最优解集,
因此建立高效的代理模型辅助多目标进化搜索逐渐受到了重视. 然而随着目标数量的增加,
对每个目标分别建立高斯过程模型时个体整体估值的不确定度会随之增加. 因此通过对模型最优解集的搜索探索原问题潜在的非支配解集,
并基于个体的收敛性, 种群的多样性和估值的不确定度, 提出了一种新的期望提高计算方法,
用于辅助从潜在的非支配解集中选择使用真实目标函数计
算的个体, 从而更新代理模型, 能够在有限的计算资源下更有效地辅助优化算法找到好的非支配解集. 在7个DTLZ
基准测试问题上的实验对比结果表明, 该算法在求解计算费时高维多目标优化问题上是有效的, 且具有较强的竞争力.
引 言
在复杂的工程优化问题中, 通常有多个目标需要同时优化, 而这些目标之间往往相互冲突和影响,
即一个目标的改善会导致至少一个其他目标的恶化, 这些问题被称为多目标优化问题.
一般多目标优化问题的数学模型可表示为:
其中, M是目标个数, x是D维决策空间R^D中的一个决策向量. 在优化问题中,
进化算法(Evolutionary algorithm, EA) 由于其不需要假设任何目标函数的凹凸性, 可微性或约束性,
且有更多的机会获得全局最优解, 因而获得了工业界和科学界的关注, 并且在实际工程中得到了很多应用.
求解多目标优化问题的进化算法(Multi-objective evolutionary algorithm,
MOEA)通常分为4大类:
1) 基于支配关系的进化多目标算法: 如快速非支配排序的遗传算法(Nondominated sorting genetic
algorithm II, NSGA-II)、提升强度的Pareto进化算法;
2) 基于分解的进化多目标算法:如基于分解的多目标进化算法(Multiobjective evolutionary
algorithm based on decomposition, MOEA/D)、参考向量引导进化算法(Reference
vector guided evolutionary algorithm, RVEA);
3) 基于指标的进化多目标算法:基于指标的进化算法、基于超体积估计的算法;
4) 其他算法:如基于分解和支配的高维多目标进化算法(Many-objective optimization
algorithm based on dominance and decomposition,
MOEA-DD)、基于双目标优化的进化算法(Bi-goal evolution, BiGE).
然而, 不管哪一类现有的多目标优化进化算法, 在搜寻最优解集的过程中都需要耗费大量的性能评估次数,
而在许多实际的多目标优化问题中其目标函数的评价非常昂贵, 如: 航空发动机管路卡箍布局优化中,
一台典型的航空发动机通常包含上百根管路, 而涉及计算一根管路震动频率的模拟函数评估可能需要大量的时间,
因此很大程度地限制了多目标进化算法在这类问题中的应用. 目前求解昂贵的多目标优化问题常用的方法之一是引入代理模型,
使用模型代替昂贵多目标计算的进化算法通常称为代理模型辅助的进化多目标算法(Surrogate-assisted
evolutionary multi-objective optimization, SAEMO).
常见的求解多目标优化问题的SAEMO算法通常分为三类：
第1类是在多目标优化过程中直接用代理模型代替费时的目标函数计算来进行环境选择.
如Akhtar等为每个目标建立一个径向基函数模型, 并提出用多个准则来选择具有代表性的点进行真实的目标函数评价.
如Zhang等提出了高斯过程随机模型辅助的算法, 该算法对每个目标建立高斯过程模型,
基于分解策略将多目标问题转换成多个单目标优化问题, 根据个体每个目标的高斯过程模型估值计算切比雪夫函数值,
并利用获取函数进行环境选择. Chugh等提出对每个目标函数建立高斯过程模型,
并通过目标函数估值的角度惩罚距离指标值和估值的不确定度来选择真实计算的个体, 称为克里金模型辅助
的RVEA算法(Kriging-assisted RVEA, K-RVEA). 为了提高计算费时多目标问题的优化性能,
Wang等在为每个目标函数建立代理模型的基础上引入一种自适应获取函数指标, 从而提出了一种新的采样选择标准.
Yang等提出了离线数据驱动的多目标优化, 在进化算法中使用了粗代理模型和细代理模型两种模型,
粗代理模型用于引导算法快速地定位到较好的搜索空间, 同时细代理模型主要关注平衡粗代理模型知识迁移过来的好解.
文献[20]构建了一个正确模型和多个辅助模型作为多个优化问题, 然后利用多任务优化方法来求解这些问题,
实现了从辅助模型到正确模型的迁移. Zhao等对多目标问题的每个目标建立了若干代理模型,
并基于目标空间和决策空间个体的距离提出了一种新的不确定度计算方法.
求解多目标优化问题的第2类SAEMO算法是对多目标问题的聚合函数建立代理模型, 即通过聚合函数将多目标转换为单目标,
对单目标建立代理模型, 从而辅助多目标优化. Knowles基于求解单目标问题的有效全局优化算法(Efficient global
optimization, EGO), 提出使用切比雪夫函数将多目标优化问题转换成单目标优化问题, 并对单目标问题建立高斯过程模型,
利用获取函数选择个体进行真实计算, 从而实现了基于EGO的Pareto面寻优算法 (Pareto optimization with
the efficient global optimization, ParEGO).
代理模型辅助的多目标优化算法中第3类是根据支配关系训练分类模型, 将代理模型作为分类器辅助多目标优化算法.
如Pan等引入人工神经网络来预测参考点与候选解之间的优劣关系来选择好的候选解进行真实计算, 为一种基于分类的代理模型辅助进化算法(A
classification based surrogate-assisted evolutionary algorithm,
CSEA). Zhang等提出利用个体间的支配关系训练支持向量机分类模型来预测后代个体的质量,
从而选择好的个体作为下一个父代.
虽然代理模型在单目标计算费时问题的优化中获得了较多关注, 但其在计算费时多目标优化问题中的应用还处于起步阶段,
目前还有很多亟待解决的问题.
1) 模型的选择. 目前常见的代理模型有多项式回归模型, 径向基函数, 高斯过程, 人工神经网络和支持向量机等.
在进化过程中选择哪一种模型对目标函数进行估值会很大程度影响算法的寻优能力.
2) 模型的用途选择. 通常情况下, 全局代理模型用于辅助提高算法的探索能力,局部代理模型用于辅助提高算法的开发能力.
而在多目标优化问题中, 由于有多个目标,
确定模型的用途更是进化多目标算法能否快速找到Pareto非支配解集的重要因素.
3) 填充标准. 如何选择个体进行真实目标函数计算并且更新模型在代理模型辅助的单目标和多目标进化优化中起着至关重要的作用,
其选择的好坏会直接影响模型更新后的准确度.
在SAEMO中, 模型估值的不确定度会影响算法的搜索方向, 从而影响算法的求解性能, 因此在优化过程中,
估值的不确定度往往和估值同时考虑. 与多项式回归、径向基函数和人工神经网络等模型相比, 高斯过程代理模型不仅能够提供个体估值,
同时还能提供估值的不确定度, 因此本文选择高斯过程模型用来作为原目标函数的估值模型, 并通过对高斯过程模型最优解集的搜索,
探索最优解集可能存在的不同领域, 从而提高算法的开发能力.
另外, 模型搜索获得的最优解集是原优化问题的潜在非支配解, 因此从中选择真实计算的个体能够加快算法对原问题的求解效率.
然而, 由于高斯过程的获取函数是针对单目标优化问题的建模提出来的, 随着目标数的增加,
对每个目标分别建立高斯过程模型时个体估值的不确定度会随之增大. 因此, 针对多目标优化问题,
考虑到个体的收敛性、种群的多样性以及估值的不确定性, 本文对高斯过程模型的期望提高(Expected improvement,
EI)获取函数进行了改进. 使用角度惩罚距离函数值作为个体的收敛性指标, 所有目标估值的不确定度均值作为个体的估值不确定度,
从而使算法在选择个体进行真实计算时在开发和开采能力上达到平衡.
本文主要贡献包含以下两个方面:
1) 通过对模型最优解集的搜索提高算法的开发能力, 使其能够引导种群向具有较好目标函数值的区域进化,
并从获得的最优解集中选择个体进行真实的目标函数评价, 从而加快收敛速度.
2) 考虑个体的收敛性、种群的多样性以及估值的不确定性,
针对计算费时多目标优化问题提出一种新的填充准则.
图 1 不同模型评价次数下算法的性能结果对比图
图 2 不同算法在DTLZ1上的性能结果对比
作者简介
孙超利
太原科技大学教授. 主要研究方向为计算智能和机器学习.
E-mail: chaoli.sun@tyust.edu.cn
李 贞
太原科技大学硕士研究生. 主要研究为方向计算智能和机器学习.
E-mail: s20180522@stu.tyust.edu.cn
金耀初
英国萨里大学教授. 主要研究方向为计算智能,机器学习,计算生物学和计算神经科学等.
本文通信作者.
E-mail: yaochu.jin@surrey.ac.uk
相关文章
[1] 张晗, 杨继斌, 张继业, 宋鹏云, 徐晓惠. 燃料电池有轨电车能量管理Pareto多目标优化.
自动化学报, 2019, 45(12): 2378−2392 doi:
10.16383/j.aas.c190044
http://www.aas.net.cn/cn/article/doi/10.16383/j.aas.c190044?viewType=HTML
[2] 王柳静, 张贵军, 周晓根. 基于状态估计反馈的策略自适应差分进化算法. 自动化学报, 2020,
46(4): 752-766. doi: 10.16383/j.aas.2018.c170338
http://www.aas.net.cn/cn/article/doi/10.16383/j.aas.2018.c170338?viewType=HTML
[3] 封文清, 巩敦卫. 基于在线感知 Pareto 前沿划分目标空间的多目标进化优化. 自动化学报,
2020, 46(8): 1628−1643 doi:
10.16383/j.aas.2018.c180323
http://www.aas.net.cn/cn/article/doi/10.16383/j.aas.2018.c180323?viewType=HTML
[4] 栗三一, 王延峰, 乔俊飞, 黄金花. 一种基于区域局部搜索的NSGA II算法. 自动化学报,
2020, 46(12): 2617−2627 doi: 10.16383/j.aas.c180583
http://www.aas.net.cn/cn/article/doi/10.16383/j.aas.c180583?viewType=HTML
[5] 罗智勇, 王静远, 谢志强, 孙广路, 杨旭.
三层虚拟工作流模型的非线性制造工艺多目标优化算法研究. 自动化学报, 2022, 48(3): 896-908. doi:
10.16383/j.aas.c190090
http://www.aas.net.cn/cn/article/doi/10.16383/j.aas.c190090?viewType=HTML
[6] 季新芳, 张勇, 巩敦卫, 郭一楠, 孙晓燕. 异构集成代理辅助的区间多模态粒子群优化算法.
自动化学报. doi: 10.16383/j.aas.c210223
http://www.aas.net.cn/cn/article/doi/10.16383/j.aas.c210223?viewType=HTML
[7] 陈国玉, 李军华, 黎明, 陈昊. 基于R2指标和参考向量的高维多目标进化算法. 自动化学报,
2021, 47(11): 2675-2690. doi: 10.16383/j.aas.c180722
http://www.aas.net.cn/cn/article/doi/10.16383/j.aas.c180722?viewType=HTML
[8] 侯建华, 张国帅, 项俊. 基于深度学习的多目标跟踪关联模型设计. 自动化学报, 2020,
46(12): 2690-2700. doi: 10.16383/j.aas.c180528
http://www.aas.net.cn/cn/article/doi/10.16383/j.aas.c180528?viewType=HTML
[9] 高开来, 丁进良. 蒸馏与换热协同的约束多目标在线操作优化方法. 自动化学报, 2019,
45(9): 1679-1690. doi: 10.16383/j.aas.c180717
http://www.aas.net.cn/cn/article/doi/10.16383/j.aas.c180717?viewType=HTML
[10] 吕柏权, 张静静, 李占培, 刘廷章. 基于变换函数与填充函数的模糊粒子群优化算法.
自动化学报, 2018, 44(1): 74-86. doi:
10.16383/j.aas.2018.c160547
http://www.aas.net.cn/cn/article/doi/10.16383/j.aas.2018.c160547?viewType=HTML
[11] 余伟伟, 谢承旺, 闭应洲, 夏学文, 李雄, 任柯燕, 赵怀瑞, 王少锋.
一种基于自适应模糊支配的高维多目标粒子群算法. 自动化学报, 2018, 44(12): 2278-2289. doi:
10.16383/j.aas.2018.c170573
http://www.aas.net.cn/cn/article/doi/10.16383/j.aas.2018.c170573?viewType=HTML
[12] 李向丽, 曹晓锋, 邱保志. 基于矩阵模型的高维聚类边界模式发现. 自动化学报, 2017,
43(11): 1962-1972. doi: 10.16383/j.aas.2017.c160443
http://www.aas.net.cn/cn/article/doi/10.16383/j.aas.2017.c160443?viewType=HTML
[13] 赵晓丽, 唐立新. 带有线性恶化工件和释放时间的两个代理单机调度问题. 自动化学报, 2015,
41(1): 104-112. doi: 10.16383/j.aas.2015.c140169
http://www.aas.net.cn/cn/article/doi/10.16383/j.aas.2015.c140169?viewType=HTML
[14] 陈振兴, 严宣辉, 吴坤安, 白猛. 融合张角拥挤控制策略的高维多目标优化. 自动化学报,
2015, 41(6): 1145-1158. doi:
10.16383/j.aas.2015.c140555
http://www.aas.net.cn/cn/article/doi/10.16383/j.aas.2015.c140555?viewType=HTML
[15] 巩敦卫, 刘益萍, 孙晓燕, 韩玉艳. 基于目标分解的高维多目标并行进化优化方法. 自动化学报,
2015, 41(8): 1438-1451. doi:
10.16383/j.aas.2015.c140832
http://www.aas.net.cn/cn/article/doi/10.16383/j.aas.2015.c140832?viewType=HTML
[16] 李波, 苏卓, 冷成财, 王胜法, 罗笑南.
基于混合梯度最小化Mumford-Shah模型的高维滤波算法. 自动化学报, 2014, 40(12): 2926-2935.
doi: 10.3724/SP.J.1004.2014.02926
http://www.aas.net.cn/cn/article/doi/10.3724/SP.J.1004.2014.02926?viewType=HTML
[17] 孙晓燕, 陈姗姗, 巩敦卫, 张勇. 基于区间适应值交互式遗传算法的加权多输出高斯过程代理模型.
自动化学报, 2014, 40(2): 172-184. doi:
10.3724/SP.J.1004.2014.00172
http://www.aas.net.cn/cn/article/doi/10.3724/SP.J.1004.2014.00172?viewType=HTML
[18] 刘晓路, 陈盈果, 贺仁杰, 陈英武. Kriging代理模型在对地观测卫星系统优化中的应用.
自动化学报, 2012, 38(1): 120-127. doi:
10.3724/SP.J.1004.2012.00120
http://www.aas.net.cn/cn/article/doi/10.3724/SP.J.1004.2012.00120?viewType=HTML
[19] 卫忠, 徐晓飞, 战德臣, 邓胜春. 协同供应链多级库存控制的多目标优化模型及其求解方法.
自动化学报, 2007, 33(2): 181-187. doi: 10.1360/aas-007-0181
http://www.aas.net.cn/cn/article/doi/10.1360/aas-007-0181?viewType=HTML
[20] 李换琴, 万百五. 基于填充函数算法的工业产品小波网络质量模型. 自动化学报, 2004,
30(2): 283-287.
http://www.aas.net.cn/cn/article/id/16189?viewType=HTML
[21] 李艳君, 吴铁军. 一种混合动力学系统多目标优化控制问题的求解方法. 自动化学报, 2002,
28(4): 606-609.
http://www.aas.net.cn/cn/article/id/15641?viewType=HTML
[22] 胡光华, 吴沧浦. 平均准则问题的即时差分学习算法. 自动化学报, 2000, 26(4):
533-536.
http://www.aas.net.cn/cn/article/id/16555?viewType=HTML
[23] 王书宁, 戴建设, 胡萍. 极小极大拟合准则下的线性模型选择方法. 自动化学报, 1994,
20(1): 29-35.
http://www.aas.net.cn/cn/article/id/14160?viewType=HTML
[24] 王邵伯, 吕勇哉. 工业大系统多目标优化问题的分解协调方法. 自动化学报, 1989,
15(2): 183-185.
http://www.aas.net.cn/cn/article/id/14901?viewType=HTML
