引用本文

 

何江红, 李军华, 周日贵. 参考点自适应调整下评价指标驱动的高维多目标进化算法. 自动化学报, 2022, 48(6): 1569−1589 doi: 10.16383/j.aas.c200975

He Jiang-Hong, Li Jun-Hua, Zhou Ri-Gui. Many-objective evolutionary algorithm driven by indicator under adaptive reference point adjustment. Acta Automatica Sinica, 2022, 48(6): 1569−1589 doi: 10.16383/j.aas.c200975  

http://www.aas.net.cn/cn/article/doi/10.16383/j.aas.c200975?viewType=HTML

文章简介

关键词

参考点自适应, 评价指标, 高维多目标, Pareto前沿形状

摘   要

在具有不同Pareto前沿形状的优化问题上, 基于参考点的高维多目标进化算法表现出较差的通用性. 为了解决这个问题, 提出参考点自适应调整下评价指标驱动的高维多目标进化算法(Many-objective evolutionary algorithm driven by evaluation indicator under adaptive reference point adjustment, MaOEA-IAR). MaOEA-IAR提出Pareto前沿形状监测基础上的参考点自适应策略, 利用该策略选择一组候选解作为初始参考点; 然后通过曲线参数对参考点位置进行调整; 将最终得到的能够适应不同Pareto前沿的参考点用于计算增强的反世代距离指标, 基于指标值设计适应度函数作为选择标准. 实验证明提出的算法在处理各种Pareto前沿形状的优化问题时能获得较好的性能, 算法通用性高.

引   言

在现实生活中存在大量由多个相互冲突的目标组成的优化问题, 这类问题称为多目标优化问题(Multi-objective optimization problems, MOPs); 超过三个目标的MOPs称为高维多目标优化问题(Many-objective optimization problems, MaOPs), 这类问题广泛存在于实际应用中, 如自动发动机标定问题、水资源分配系统设计、航空发动机健康管理系统、软件重模块化、软件模块聚类问题等.

研究证明传统的多目标进化算法(Multi-objective evolutionary algorithms, MOEAs)在处理MOPs时能获得较好的性能, 然而在处理MaOPs时却会出现一系列的问题, 如: 随着目标数目的增加, 种群中非支配解比例呈指数形式增加, 算法的选择压力缺失; 在高维空间中, 部分性能评价指标(如超体积指标)的计算代价过大等. 为了应对目标数目增加带来的挑战, 提高MOEAs在处理MaOPs时的能力, 研究学者们提出一系列算法, 大致可以分为三类, 分别为: 基于松弛支配的算法、基于分解的算法、基于指标的算法.

1) 基于松弛支配的算法: 通过修改支配关系扩大解的支配区域, 能在一定程度上缓解支配受阻现象; 常见的松弛支配关系有: 角度支配、网格支配、模糊支配、基于参考点的支配等.

2) 基于分解的算法: 利用一组参考向量将一个MOPs分解为多个单目标优化问题(Single-objective optimization problems, SOPs)或更为简单的MOPs, 随后对这些子问题进行协同进化, 这在一定程度上增加了种群的多样性; 此类经典算法有: MOEA/D、MOEA/D-ANA、RVEA、MOEA/D-ROD、NGSA-III、MOEA-PPF.

3) 基于指标的算法: 通过构建适应度函数将候选解的目标值映射到一个确定的数值上, 并将该值作为环境选择中的选择标准, 该方法能够区分具有相同目标和的解; 此类经典算法有: SMS-EMOA、MOMBI-II、MaOEA-IPB、R2-OSP、MaOEA/IGD等.

尽管上述算法能在一定程度上缓解传统算法在处理高维优化问题时存在的不足, 但面对具有不规则Pareto前沿(Pareto front, PF)的优化问题时, 常规方法可能无法获得很好的性能, 因此需要设计更先进的算法. 目前处理不规则优化问题的算法可以分为四类, 分别是采用固定参考向量与辅助选择方法协同合作, 在搜索过程中根据种群分布调整参考向量, 用参考点同时衡量多样性和保持收敛性, 以及对群体进行聚类或划分目标空间为子区域.其中参考向量的调整是非常重要的, Ma等在文献[24]中对单纯性上的各种参考向量调整策略进行综述, 将其分为随机调整、基于拟合的调整、局部种群指导的调整、局部档案的调整、基于领域参考向量的调整和基于偏好的调整, 并且详细讨论了每种方法的优缺点以及有待解决的问题. 除此之外, 近年来研究学者还结合不同的策略提出一些新型算法, 如 Yuan等在文献[25]中提出PREA, 该算法基于平行距离进行个体选择, 与传统的角度距离、径向交叉距离相比, 基于平行距离导出的点无论是在凹型、凸型, 还是在不规则PF上都是均匀分布的, 这有利于提高算法在处理各种优化问题时的多样性; Liu提出FDEA, 该算法利用模糊预测评估不同形状PF上解的相似性, 并以此为依据对种群进行分割, 有效地提高了算法的多样性, 同时提供一个共享权重向量加快收敛速度, 两者共同作用提高算法的性能.

为了能够更好地处理不规则MaOPs, 提高算法的通用性, 本文提出参考点自适应调整下评价指标驱动的高维多目标进化算法, 该算法的具体步骤如下: 

1) 为了有效地生成一组参考点, 提出一个PF形状监测基础上的自适应参考点策略, 该方法首先利用一条特定的轮廓曲线近似PF, 其次在该曲线上找到所有非支配解对应的点, 然后以对应点之间的距离作为多样性选择标准, 最后利用该准则选择一组多样性好的解作为参考点, 此外基于曲线参数对参考点的位置进行调整, 以减少偏离种群的参考点所产生的影响; 

2) 为了进一步提高算法性能, 在匹配选择中结合Pareto支配和改进的Pareto支配以及邻域关系, 选择一组有希望的解作为父代种群; 

3) 为了最终生成一组接近PF且分布广泛的种群, 在环境选择中利用参考点计算基于指标的适应度函数, 将其作为选择标准进行精英选择.

图 3  自适应参考点过程

图 7  DTLZ5问题3目标上获得的非支配解

作者简介

何江红

南昌航空大学硕士研究生.主要研究方向为进化计算.

E-mail: he192652@163.com

李军华

南昌航空大学教授. 主要研究方向为进化计算和智能控制. 本文通信作者.

E-mail: jhlee126@126.com

周日贵

上海海事大学教授. 主要研究方向为人工智能及其应用.

E-mail: rgzhou@shmtu.edu.cn

相关文章

[1]  罗忠涛, 郭人铭, 郭杰, 何子述, 卢琨. OTH雷达图像的粗糙度指标及用于射频干扰自适应抑制. 自动化学报, 2022, 48(3): 887-895. doi: 10.16383/j.aas.c190286

http://www.aas.net.cn/cn/article/doi/10.16383/j.aas.c190286?viewType=HTML

[2]  陈健, 李诗云, 林丽, 王猛, 李佐勇. 模糊失真图像无参考质量评价综述. 自动化学报, 2022, 48(3): 689-711. doi: 10.16383/j.aas.c201030

http://www.aas.net.cn/cn/article/doi/10.16383/j.aas.c201030?viewType=HTML

[3]  孙超利, 李贞, 金耀初. 模型辅助的计算费时进化高维多目标优化. 自动化学报, 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

[4]  武文亮, 周兴社, 沈博, 赵月. 集群机器人系统特性评价研究综述. 自动化学报, 2022, 48(5): 1153-1172. doi: 10.16383/j.aas.c200964

http://www.aas.net.cn/cn/article/doi/10.16383/j.aas.c200964?viewType=HTML

[5]  梁正平, 李辉才, 王志强, 胡凯峰, 朱泽轩. 自适应变化响应的动态多目标进化算法. 自动化学报. doi: 10.16383/j.aas.c210121

http://www.aas.net.cn/cn/article/doi/10.16383/j.aas.c210121?viewType=HTML

[6]  陈国玉, 李军华, 黎明, 陈昊. 基于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

[7]  李新利, 邹昌铭, 杨国田, 刘禾. SealGAN: 基于生成式对抗网络的印章消除研究. 自动化学报, 2021, 47(11): 2614-2622. doi: 10.16383/j.aas.c190459

http://www.aas.net.cn/cn/article/doi/10.16383/j.aas.c190459?viewType=HTML

[8]  张洋, 江铭虎. 作者识别研究综述. 自动化学报, 2021, 47(11): 2501-2520. doi: 10.16383/j.aas.c200654

http://www.aas.net.cn/cn/article/doi/10.16383/j.aas.c200654?viewType=HTML

[9]  陈勇, 吴明明, 房昊, 刘焕淋. 基于差异激励的无参考图像质量评价. 自动化学报, 2020, 46(8): 1727-1737. doi: 10.16383/j.aas.c180088

http://www.aas.net.cn/cn/article/doi/10.16383/j.aas.c180088?viewType=HTML

[10]  封文清, 巩敦卫. 基于在线感知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

[11]  张晗, 杨继斌, 张继业, 宋鹏云, 徐晓惠. 燃料电池有轨电车能量管理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

[12]  余伟伟, 谢承旺, 闭应洲, 夏学文, 李雄, 任柯燕, 赵怀瑞, 王少锋. 一种基于自适应模糊支配的高维多目标粒子群算法. 自动化学报, 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

[13]  丁进良, 杨翠娥, 陈立鹏, 柴天佑. 基于参考点预测的动态多目标优化算法. 自动化学报, 2017, 43(2): 313-320. doi: 10.16383/j.aas.2017.c150811

http://www.aas.net.cn/cn/article/doi/10.16383/j.aas.2017.c150811?viewType=HTML

[14]  王志明. 无参考图像质量评价综述. 自动化学报, 2015, 41(6): 1062-1079. doi: 10.16383/j.aas.2015.c140404

http://www.aas.net.cn/cn/article/doi/10.16383/j.aas.2015.c140404?viewType=HTML

[15]  陈振兴, 严宣辉, 吴坤安, 白猛. 融合张角拥挤控制策略的高维多目标优化. 自动化学报, 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

[16]  巩敦卫, 刘益萍, 孙晓燕, 韩玉艳. 基于目标分解的高维多目标并行进化优化方法. 自动化学报, 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

[17]  张小利, 李雄飞, 李军. 融合图像质量评价指标的相关性分析及性能评估. 自动化学报, 2014, 40(2): 306-315. doi: 10.3724/SP.J.1004.2014.00306

http://www.aas.net.cn/cn/article/doi/10.3724/SP.J.1004.2014.00306?viewType=HTML

[18]  成孝刚, 安明伟, 阮雅端, 陈启美. 基于变分的盲图像复原质量评价指标. 自动化学报, 2013, 39(4): 418-423. doi: 10.3724/SP.J.1004.2013.00418

http://www.aas.net.cn/cn/article/doi/10.3724/SP.J.1004.2013.00418?viewType=HTML

[19]  马儒宁, 涂小坡, 丁军娣, 杨静宇. 视觉显著性凸显目标的评价. 自动化学报, 2012, 38(5): 870-876. doi: 10.3724/SP.J.1004.2012.00870

http://www.aas.net.cn/cn/article/doi/10.3724/SP.J.1004.2012.00870?viewType=HTML

[20]  刘玉生. 分散模型参考自适应控制. 自动化学报, 1992, 18(6): 671-678.

http://www.aas.net.cn/cn/article/id/14349?viewType=HTML