引用本文

顾清华, 周煜丰, 李学现, 阮顺领. 基于径向空间划分的昂贵多目标进化算法. 自动化学报, 2022, 48(10): 2564−2584 doi: 10.16383/j.aas.c200791

Gu Qing-Hua, Zhou Yu-Feng, Li Xue-Xian, Ruan Shun-Ling. Expensive many-objective evolutionary algorithm based on radial space division. Acta Automatica Sinica, 2022, 48(10): 2564−2584 doi: 10.16383/j.aas.c200791

http://www.aas.net.cn/cn/article/doi/10.16383/j.aas.c200791

关键词

昂贵多目标优化问题，高斯过程，径向投影，双档案管理策略 

摘要

为了解决难以建立精确数学模型或者真实评估实验成本高昂的多目标优化问题, 提出了一种基于径向空间划分的昂贵多目标进化算法. 首先算法使用高斯回归作为代理模型逼近目标函数; 然后将目标空间的个体投影到径向空间, 结合目标空间和径向空间信息保留对种群贡献更高的个体; 之后由径向空间中个体的位置分布决定下一步应该选择哪些个体进行真实评估; 最后, 采用一种双档案管理策略维护代理模型的质量. 数值实验和现实问题上的结果表明, 与5种先进算法相比, 该算法在解决昂贵多目标优化问题时能够提供更高质量的解.

文章导读

高维多目标优化问题在现实世界很常见, 这类问题是具有3个以上目标的多目标优化问题. 由于多个目标之间往往是相互冲突的, 通常不存在唯一的最优解, 而是由多个最优解组成帕累托前沿面. 进化算法由于其群体的特性, 能够在1次运行中获得1组解, 适用于多目标优化问题[1]. 但是, 对于高维多目标优化问题, 由于帕累托选择压力的丧失, 大部分进化算法都需要上万次的函数评价才能获得一些满意的解. 这使得传统的多目标进化算法在实际应用中遇到了巨大的挑战. 许多现实问题单一的适应度评估(Function evaluation, FE)在计算或经济上都需要昂贵的资源. 以翼型结构优化设计[2]为例, 如果使用10000个FEs, 那么传统的多目标进化算法大概需要188天的时间, 这是难以接受的. 为了解决昂贵的多目标优化问题, 基于代理模型的昂贵多目标进化算法被广泛采用[3-5]. 即用计算量小的代理模型去替代部分计算昂贵的真实函数评价或对大量个体进行预筛选, 以达到减少计算量的目的. 常用的代理模型包括支持向量机、多项式响应面法、径向基函数、人工神经网络及高斯模型(也称为Kriging模型). 其中, 高斯模型不仅提供了预测值, 还给出了预测值的置信度, 这对于避免代理模型陷入局部最优有重要意义. 因此, 高斯模型被广泛作为代理模型应用于工程优化设计领域[6].

目前, 代理辅助进化算法可以分为两类. 第1类是利用代理模型去逼近候选个体的适应度值. 具体而言, 使用历史数据或部分真实数据构建高效的代理模型, 然后用代理模型近似候选解的适应度值. 在帕累托优化的高效全局优化(Pareto optimization efficient global optimization, ParEGO)算法[7]中, 建立了单一的代理模型来逼近候选个体的聚集函数, 其中聚集函数是由1组均匀的权重向量中随机选择的权重向量构成的. 在基于S度量选择的高效全局优化[8]中, 个体的适应度被定义为个体对群体的超体积分数贡献, 代理模型近似逼近超体积指标函数. 但是由于超体积指标函数的复杂性, 其计算复杂度较高. 在高斯随机过程辅助的基于分解多目标进化(Multi-objective evolutionary algorithm based on decomposition with the Gaussian sto-chastic process model, MOEA/D-EGO)[9]算法中, 针对每个目标函数建立多个局部代理模型, 每次迭代时, 候选个体基于距离它最近的聚类中心的局部代理模型进行真实评估. 在Kriging模型辅助的参考向量进化(Kriging-assisted reference vector guided evolutionary algorithm, K-RVEA)[10]算法中, 同时用m个代理模型逼近m个目标函数, 另外, 采用了1种新的管理代理模型的策略, 限制了代理模型的训练样本量, 降低了代理建模的成本. 第2类是将代理模型视作分类器, 利用代理模型过滤较差的候选解以达到减少计算量的目的. 在基于帕累托支配的分类预选进化算法框架[11] (Pareto do-mination based evolutionary algorithm framework with a classification based preselection, CPS-MOEA)中, 根据非支配排序将种群分为两个相等的集合, 两个集合分别存储好解和坏解, 然后训练分类器对新生成的后代进行分类, 以减少昂贵评估的数量. 在基于分类的代理辅助进化(Classification based surrogated-assisted evolutionary algorithm, CSEA)算法[12]中, 使用人工神经网络来预测候选解和预先生成的参考解之间的优势关系, 利用预测中的不确定性信息, 结合优势关系, 选择有前途的解.

径向空间划分是将高维目标空间的个体投影到径向空间, 并利用二维网格进行划分的一种技术, 可以很好的反映个体的邻域关系. 这有利于寻找保持种群收敛性和多样性的解. 在这项技术的基础上, 本文提出了利用Kriging模型辅助径向空间划分的昂贵多目标进化算法(Kriging model assisted radial space division evolutionary algorithm, K-RSEA), 算法主要创新总结如下:

1)利用径向空间中解的位置分布衡量种群的拥挤程度. 当径向空间中的个体稀疏时, 综合考虑目标空间和径向空间的个体信息, 选择有利于平衡种群的收敛性和多样性的候选个体真实评估; 当径向空间中的个体拥挤时, 代理模型的质量被考虑, 利用其提供的不确定信息选择有利于目标空间探索的候选个体真实评估.

2)采用双档案管理策略. 1个固定档案存储建立代理模型的个体, 在径向空间中利用邻域关系对其进行维护; 1个可变档案存储所有真实评估得到的非支配解.

本文后续安排如下. 第1节介绍算法使用到的相关技术; 第2节详细介绍基于径向空间划分的昂贵多目标算法; 第3节进行数值实验; 第4节在1个汽车优化设计的现实问题上验证了算法性能; 第5节是总结和展望.

图 1  高斯过程(Kriging模型)图解

图 2  径向空间中个体的位置分布情况

图 3  6种算法在求解3个目标DTLZ1问题过程中获得的最佳HV值对应的非支配解集

本文提出了一种基于径向空间划分的昂贵多目标进化(K-RSEA)算法. 该算法根据径向空间中个体的拥挤程度选择合适的解真实评估. 所选择的解兼顾种群的多样和收敛性能的同时还考虑了代理模型的质量. 另外, 固定档案限制代理模型的训练时间成本, 可变档案存储真实评估得到的非支配解, 不仅仅降低了算法的时间成本, 也提高了代理模型的质量. 数值实验表明, K-RSEA在处理昂贵的多目标优化问题能够提供分布性和多样性更好的结果, 与最新提出的几种先进算法相比, K-RSEA解决昂贵多目标优化问题更具有优势. 最后, 在1个汽车耐撞性优化设计问题验证了算法的现实意义. 未来工作将会把本文提出的算法K-RSEA扩展到复杂约束问题并尝试解决更多的昂贵现实问题.

作者简介

顾清华

西安建筑科技大学教授. 主要研究方向为多目标优化, 车辆调度和复杂系统建模与仿真. 本文通信作者. E-mail: qinghuagu@126.com

周煜丰

西安建筑科技大学硕士研究生. 主要研究方向为多目标优化和车辆调度. E-mail: zyf18215649083@163.com

李学现

西安建筑科技大学博士研究生. 主要研究方向为群智能优化算法在采矿系统工程中的应用. E-mail: lixuexian2019@163.com

阮顺领

西安建筑科技大学副教授. 主要研究方向为矿山智能系统和深度学习. E-mail: ruanshunling@163.com