引用本文

陈国玉, 李军华, 黎明, 陈昊. 基于R2指标和参考向量的高维多目标进化算法. 自动化学报, 2021, 47(11): 2675-2690 doi: 10.16383/j.aas.c180722

Chen Guo-Yu, Li Jun-Hua, Li Ming, Chen Hao. An R2 indicator and reference vector based many-objective optimization evolutionary algorithm. Acta Automatica Sinica, 2021, 47(11): 2675-2690 doi: 10.16383/j.aas.c180722

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

关键词

R2指标，参考向量，高维多目标优化，进化算法 

摘要

在高维多目标优化中, 不同的优化问题存在不同形状的Pareto前沿(PF), 而研究表明大多数多目标进化算法(Multi-objective evolutionary algorithms, MOEAs) 在处理不同的优化问题时普适性较差. 为了解决这个问题, 本文提出了一个基于R2指标和参考向量的高维多目标进化算法(An R2 indicator and reference vector based many-objective optimization evolutionary algorithm, R2-RVEA). R2-RVEA基于Pareto支配选取非支配解来指导种群进化, 仅当非支配解的数量超过种群规模时, 算法进一步采用种群分解策略和R2指标选择策略进行多样性管理. 通过大量的实验证明, 本文提出的算法在处理不同形状的PF时具有良好的性能.

文章导读

多目标优化问题(Multi-objective optimization problems, MOPs)[1]是指多个目标被同时优化的问题. 在现实生活中, 经常遇到优化问题包含四个及以上目标, 这类问题统称为高维多目标优化问题(Many-objective optimization problems, MaOPs)[2-4]. 虽然一些经典的多目标进化算法(Multi-objective evolutionary algorithms, MOEAs), NSGA-Ⅱ[5]、SPEA2[6]等能够很好地处理多目标优化问题(两个或三个目标), 但是在解决高维多目标优化问题上效果较差.

近年来, 为了提高解决高维多目标优化问题的能力, 研究者们提出了许多优秀的算法, 这些MOEAs主要可以分为三类. 1) 基于各种增强收敛性的算法: 该类算法主要是改进Pareto支配关系或者提出其他增强收敛性的方法, 通过这些方法提高处理高维多目标优化问题时的收敛性. 例如改进的Pareto支配: ϵϵ支配[7]、L最优[8]、模糊支配[9]和优先级排序[10]等. 以及其他基于增强收敛性的算法: GrEA[11]、KnEA[12]等. 2) 基于分解的算法: 该类算法是把一个复杂的高维多目标优化问题分解为一组单目标优化问题(Single-objective optimization problems, SOPs) 或者易于管理的多目标优化问题[13-15], 如RVEA[16]、SPEA/R[17]和NSGA-Ⅲ[18]等. 3) 基于评价指标的算法: 该类算法是采用评价指标作为选择标准来衡量解的质量, 选择机制通过比较解的质量找到更好的解. 这类算法的典型代表包括IBEA[19]、HypE[20]和SMS-EMOA[21]等.

虽然大多数多目标进化算法能够很好地处理一些高维多目标优化问题, 但这些算法对Pareto前沿的形状十分敏感[22], 导致在处理不同形状的PF时不能很好地平衡收敛性和多样性. 针对上述问题, 本文提出了一个基于R2指标和参考向量的高维多目标进化算法(R2-RVEA). 该算法的主要创新在于: 1) R2-RVEA基于Pareto支配作为选择标准选取非支配解, 仅当非支配解的数目超过种群规模时, 算法进一步采用R2指标选择和种群分解策略共同管理多样性; 2) R2-RVEA基于R2指标进一步选择种群分解淘汰的解, 这有利于保留具有良好收敛性和多样性的解.

图 1  目标问题上展示的15个参考向量

图 2  DTLZ4问题15目标上获得的非支配解

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

本文提出了一个基于R2指标和参考向量的高维多目标进化算法. 这个算法致力于处理具有不同PF形状的MOPs以及MaOPs. 在算法中, 为了让种群可以快速地收敛到PF上, 采用了Pareto支配选取当前种群非支配解的方式来指导整个种群优化. 而当整个种群都收敛到PF上以后, 采用种群分解和R2排序进一步管理种群的收敛性和多样性.

实验结果表明了提出的R2-RVEA在处理具有不同PF形状的MOPs以及MaOPs时, 能够很好地平衡收敛性和多样性. 当然, 算法的初期阶段仅采用Pareto支配选取最优解的方式有可能导致种群收敛到局部PF的情况发生, 这使得种群分解和R2排序已经无法有效地管理种群的多样性. 因此, 在保证种群稳定地收敛到PF上, 如何更好地管理种群的多样性仍然是未来工作的一个方向.

作者简介

陈国玉

南昌航空大学硕士研究生.主要研究方向为进化计算. E-mail: 1704081002001@stu.nchu.edu.cn

黎明

南昌航空大学教授. 主要研究方向为图像处理和人工智能. E-mail: liming@nchu.edu.cn

陈昊

南昌航空大学副教授. 主要研究方向为动态和高维多目标进化算法. E-mail: chenhaoshl@nchu.edu.cn

李军华

南昌航空大学教授. 主要研究方向为进化计算和智能控制. 本文通信作者. E-mail: jhlee126@126.com