基于自适应支配和参考向量的高维多目标优化算法
孙文静， 李军华
（南昌航空大学 信息工程学院，南昌 330063）
[摘 要]现有的改进支配方法提高了解集逼近Pareto 前沿的能力，但平衡种群收敛性和多样性的能力仍然不足。针对此问题，提出了一种基于自适应支配和参考向量的高维多目标优化算法(An adaptive dominance and reference vector bad evolutionary algorithm for many-objective optimization ，ADRVEA)。首先提出自适应支配(Adaptive dominance ，AD)来设计小生境机制；然后通过参考向量划分目标空间来提高种群多样性；最后构建适应度表达式来实现精英选择。实验证明所提出的ADRVEA 不仅性能良好，而且有效平衡了种群的收敛性和多样性。[关键词]高维多目标优化； 平衡收敛性和多样性； 自适应支配； 参考向量
[中图分类号] U458 [文献标志码] A doi ：10.3969/j.issn.2096-8566.2021.01.009[文章编号]2096-8566(2021)01-0052-11
An Adaptive Dominance and Reference Vector Bad Evolutionary
Algorithm for Many-objective Optimization
SUN Wen-jing ， LI Jun-hua
（School of Information Engineering, Nanchang Hangkong University, Nanchang 330063, China ）
Abstract : Improved dominance method improve the ability to approach the Pareto front, but they show poor ability in balancing convergence and diversity of population. To address this issue, this paper propos an adaptive dominance and reference vector bad evolutionary algorithm for many-objective optimization (ADRVEA). Firstly, the adaptive dominance (AD) is propod to design an niche mechanism. Then the reference vector is adopted to divide the objective space for the purpo of the enhanced diversity. Finally, the fitness function is constructed to complete the elite lection. The experimental results demonstrated that the propod ADRVEA not only has significant performance, but also effectively balances the convergence and diversity.Key words: Many-objective optimization ； balance convergence and diversity ； adaptive dominance ； reference vector
引 言
多目标优化问题(Multi--objective optimization problems ，MOPs)[1]
包括2个或3个优化目标。当目标数大于4个时，则升级为高维多目标问题(Many-objective optimization problems ，MaOPs)
[2-3]
。
随着目标维数的增加，一般的多目标进化算法(Multi-objective evolutionary algorithms ，MOEAs)在处理MaOPs 时会出现性能退化，区分解集的能力下降等问题。为此，研究学者们相继提出许多先进
[收稿日期]2020-11-01 [修回日期]2020-12-31[基金项目]国家自然科学基金(20181BCB24008)
[通讯作者]李军华(1974— )，男，博士，教授。主要研究方向：遗传算法及计算机图像处理。
第 35 卷 第 1 期南昌航空大学学报：自然科学版
Vol. 35 No. 12021 年 3 月Journal of Nanchang Hangkong University: Natural Sciences Mar. 2021
和杰出的算法，这些算法可分为3类：基于松弛支配的算法：通过改进Pareto支配或提出新的支配方法
来提高选择压力。例如：g支配[4]、S-CDAS[5]、网格支配[6]、RP支配[7]、角度支配[8]和SDR[9]等；基于分解的算法：通过一组参考点将一个MOP分解为多个单目标子问题或易于管理的MOPs，从而降低问题的求解难度。例如：RVEA[10]、AMOEA/D[11]和SPSAT[12]等；基于指标的算法：采用指标作为适应度值来指导种群进化过程，如HypE[13]、MOMBI-II[14]等。
尽管大多数MOEAs提高了高维目标空间的搜索能力，但平衡种群收敛性和多样性的能力仍然不足。针对这一问题，本文提出一种基于自适应支配和参考向量的高维多目标优化算法(An adaptive dominance and reference vector bad evolutionary algorithm for many-objective optimization, ADRVEA)，该算法首先根据种群分布、目标维数等信息构建自适应小生境方法；然后引入分解方法来进一步增强全局目标空间的多样性；最后构建适应度表达式来选择精英个体。
1 相关知识
1.1 背景知识
MOEAs中广泛采用Pareto支配关系，但基于Pareto支配的算法在处理MaOPs时效果较差，这是由于：
式中：f(x) = (f1(x), f2(x),…, f M(x))是M维目标值，解之间的支配概率为1/2M-1，该概率随M增加而呈指数下降，则产生“支配阻抗”现象。为此，研究者们通过改进支配区域或修改支配关系来解决这一困难。
1.2 改进支配方法
第1类，扩大支配区域的方法：通过扩展解的支配区域来提高选择压力；S-CDAS[5]通过修改解的目标值来自适应控制解的支配区域。第2类，基于网格支配的方法：将目标空间划分为若干个网格，并利用每个解的网格值判断Pareto支配关系；Yang[6]提出以个体为核心的网格计算来确定网格环境中解之间的关系。第3类，引入参考点的支配方法；g支配[4]在最优点的附近估计有效集；Elarbi[7]提出基于参考点和Pareto支配的RP支配。第4类，自适应小生境支配方法：通过自适应小生境达到区分解的目的；SDR[9]根据候选解分布提出了小生境机制，并在每个小生境内确定收敛性最好的解。
1.3 分解方法
RVEA[10]通过一组均匀分布的参考向量来划分目标空间，并建立解与参考向量之间的联系，选择与参考向量最近的候
选解，从而引导种群对MOEAs的搜索。SPSAT[12]通过空间分割选择机制来提升多样性，但为了进一步增强收敛性和多样性，采用基于角度的截断机制作为环境选择的第二选择标准。
目前，大多数参考向量生成方法采用Das和Dennis提出的系统方法，该方法通过在M-1维的单位超平面上生成一组均匀分布的参考点。若在每个目标上划分H份，那么M维目标空间中总数为N的参考点为：
2 基于自适应支配和参考向量的高维多目
标优化算法
2.1 ADRVEA的算法框架
为了提高种群收敛性和多样性之间的平衡，本文提出一种基于自适应支配和参考向量的高维多目标优化算法。算法1为ADRVEA框架的伪代码，首先初始化产生N个初始种群和参考向量；然后采用遗传算子生成子代种群；最后将父代种群和子代种群合并，进入环境选择，直到满足终止条件，确定最终的种群。
算法1 ADRVEA框架
第 1 期孙文静，李军华：基于自适应支配和参考向量的高维多目标优化算法• 53 •
输入：N（种群大小）；和暗恋的男生聊天技巧
P t
max
输出：（最后种群）；
1：/*初始化*/
2： V = UniformReferenceVector(N)；
3： P0 = Initialization(N)；
4：/*主循环*/
5：While not fulfill the termination do
6： Q t = Variation(P t)；
R t=P t∪Q t
7： ；
8： P t + 1 = EnvironmentalSelection(R t, V)；
9：t = t + 1;
10：end while
2.2 ADRVEA环境选择
收集邮票英语环境选择的目的是为了从2N个合并种群选择N个收敛性和多样性良好的解集进入下一代。ADRVEA环境选择的伪代码见算法2，首先对合并种群的目标值进行平移；接着对平移后的种群进行一次AD非支配排序，该步骤是为了获得种群中的解所对应的非支配层数，从而构建最终的适应度函数。
算法2环境选择
输入：R t（合并种群），V（参考向量）；
输出：P t + 1（下一代种群）；
1：/*平移目标值*/
2： R't = ObjectiveValueTranslation(R t)；
3：/*AD非支配排序*/
4： (F1, F2, F i,•••) = AD-NondominatedSort(R't)；
5：/*划分子空间*/
angle t=arccos(R′t,V t)
6： ；
7：/*计算适应度值*/
Fit=F t,i+Norm(angle t)
8： ；
9：/*选择精英选择*/
k=argmin Fit
学习是快乐的
10： ；
11：P t + 1 = P t + 1∪{I t, k}；
12：Return P t + 1
1）划分子空间。
为了进一步增强种群的多样性管理，引入参考向量对划分目标空间，并在每个子空间内建立解与参考向量之间的联系，从而获得一组多样性较好的子种群。若一个解和参考向量之间的夹角最小，则该解属于这个参考向量。由于每个子空间内，可能存在多个解与参考向量相属，这些解将组成同一子空间内的子种群。
2）适应度表达式。
为了实现精英选择，对每个子种群构建合理的适应度表达式。根据AD排序的非支配层数和子
山德士上校
式（3）中：F t,i为第t代下解i的非支配层数，Norm (angle t)表示归一化后的角度值。ADRVEA中，适
应度值越小越好。式(3)在满足2种条件下完成精英选择：①当子种群内解的非支配层数不同时，优先选择非支配层数较小的解；②若满足条件1，进一步选择与参考向量夹角最小的解。
3）自适应支配方法。
i≺AD j
AD定义：①当解i与解j在同一小生境内，且i的收敛度小于j；②当解i与解j不在同一小生境内，且i的收敛度远小于j时；满足①和②中任一条件，解j被解i支配()。解的支配区域由两部分组成：小生境内和小生境外的有限区域。当小生境大小增加时，支配区域随之增加，因此自适应小生境大小可以调整解的支配区域。
根据目标空间中解集的角度信息和目标数来自适应小生境大小。首先计算目标空间中任意解间的最小角度，并组成角度集合；然后对角度集合内的角度进行排序，序号是根据种群大小和目标数确定：
其中M是目标数，|P|是种群大小，β是控制因子。由于进化过程中非支配解比例随M增大而增加，因此考虑M可以自适应地控制解的支配区域。AD 通过候选解间的角度和目标数来自适应小生境大小，在一
定程度上达到动态控制支配区域的目的。
• 54 •南昌航空大学学报：自然科学版第 35 卷
3 实验研究与结果分析
3.1 实验设置
采用DTLZ[15]和WFG[16]测试集以及GrEA[6]、KnEA[11]、MOMBI-II[14]和RPEA[7]4种算法与ADRVEA 进行对比。为了公平对比，算法的种群大小与参考向量大小保相同，具体设置见表1。MOEAs生成子代的遗传算子是模拟的二元交叉[17]和多项式突变[18]。另外，GrEA[6]中网格划分的数div设为5；RPEA[7]中参考点生成的个体比例α设为0.4，参考点和个体之间的差异δ设为0.1。对于任意目标数的测试问题，最大代数设置为1000。
表 1 参考向量的数目设置
目标维数M3581015 N105210156275135
采用反世代距离加(Modified inverted genera-tional distance, IGD+)[19]和超体积(Hypervolume, HV)[13]指标在每个测试实例上执行30次，并采用0.05显着性水平的Wilcoxon秩和检验来分析结果。
3.2 实验结果分析虎皮兰开花
3.2.1 DTLZ测试集上的性能对比
豁达的意思表2为GrEA、KnEA、MOMBI-II、RPEA和ADRVEA在DTLZ1-4上IGD+的均值和标准差。由表可见，ADRVEA在处理不同目标的DTLZ1和DTLZ2测试问题时性能良好。由于DTLZ3存在大量局部PF，则该问题可测试MOEAs能否跳出局部PF，ADRVEA在处理5、8、10和15目标时的性能明显优于其他算法。DTLZ4测试PF高度偏向的情况下算法保持候选解分布的能力，ADRVEA 在3、5和10目标测试实例中IGD+值突出，说明ADRVEA在该问题下能够保持种群的多样性。
表 2 对比算法在DTLZ1-4上获得IGD+的均值和标准差
问题M GrEA KnEA MOMBIII RPEA ADRVEA
DTLZ1
3 6.313 9e−2 (4.98e−2) − 4.009 1e−2 (2.12e−2) − 1.35
4 7e−2 (1.00e−4) + 1.030 1e−1 (2.00e−2) − 1.348 9e−2 (2.61e−4)
5 1.273 0e−1 (6.47e−2) − 1.731 8e−1 (5.13e−2) − 4.60
自制南瓜饼
6 4e−2 (1.80e−4) − 1.382 4e−1 (3.53e−2) − 3.689 9e−2 (3.12e−4) 8 2.531 4e−1 (6.86e−2) − 2.578 0e−1 (9.91e−2) − 1.218 3e−1 (2.74e−2) − 1.555 5e−1 (2.87e−2) − 6.299 1e−2 (5.31e−4) 10 3.368 6e−1 (1.05e−1) − 5.715 5e+0 (5.97e+0) − 1.93
7 5e−1 (3.11e−2) − 1.731 0e−1 (4.49e−2) −7.017 6e−2 (6.79e−4) 15 3.976 6e−1 (1.42e−1) −9.525 9e+0 (1.19e+1) − 2.691 4e−1 (2.93e−2) − 1.957 4e−1 (3.03e−2) − 1.443 2e−1 (6.94e−3)
DTLZ2
3 2.30
4 1e−2 (2.07e−4) − 2.946 7e−2 (1.56e−3) − 2.090 1e−2 (1.27e−5) + 3.684 2e−2 (6.63e−3) − 2.271 2e−2 (2.94e−4) 59.323 0e−2 (8.57e−3) −8.361 6e−2 (8.69e−3) =7.143 1e−2 (3.71e−5) + 1.074 3e−1 (3.28e−3) − 6.449 2e−2 (3.10e−4) 8 1.607 3e−1 (1.79e−3) − 1.533 9e−1 (3.50e−3) − 1.198 1e−1 (2.36e−4) + 1.679 8e−1 (3.75e−3) − 1.267 2e−1 (1.42e−3) 10 1.442 0e+0 (5.73e−1) − 1.817 2e−1 (1.12e−2) = 3.440 3e−1 (9.18e−2) − 2.117 3e−1 (3.61e−3) − 1.672 6e−1 (8.68e−4) 1
5 1.721 9e+0 (6.97e−1) − 2.301 9e−1 (4.47e−3) + 6.473 2e−1 (4.95e−2) − 2.820 3e−1 (8.02e−3) = 2.397 4e−1 (4.05e−4)
DTLZ3
39.414 5e−2 (1.40e−1) − 5.802 7e−2 (3.83e−2) − 2.225 2e−2 (8.24e−4) + 5.862 1e−2 (1.23e−2) − 2.412 4e−2 (1.67e−3) 5 4.908 6e−1 (1.68e−1) − 3.302 2e−1 (1.35e−1) −7.343 0e−2 (1.43e−3) + 1.901 4e−1 (4.34e−2) − 6.426 7e−2 (7.49e−4) 87.008 5e−1 (1.84e−1) − 4.661 6e+1 (2.07e+1) − 1.805 7e−1 (8.89e−2) = 3.486 6e−1 (4.45e−2) − 1.287 2e−1 (2.95e−3) 10 3.689 1e+0 (2.87e+0) − 2.777 2e+2 (9.71e+1) − 5.442 0e−1 (4.33e−2) − 4.337 1e−1 (5.02e−2) − 1.660 2e−1 (1.38e−3) 15 3.150 3e+2 (3.49e+2) − 3.889 5e+2 (1.20e+2) −7.096 7e−1 (4.09e−2) − 5.882 4e−1 (6.28e−2) − 2.758 9e−1 (1.80e−1)
DTLZ4
38.658 8e−2 (1.56e−1) − 2.829 1e−2 (9.52e−4) − 5.123 2e−2 (1.03e−1) − 2.495 3e−1 (1.98e−1) − 2.244 1e−2 (2.41e−4) 59.263 2e−2 (8.90e−3) −8.074 6e−2 (8.76e−3) =9.083 9e−2 (3.57e−2) − 2.603 3e−1 (1.50e−1) − 6.505 1e−2 (3.92e−4) 8 1.613 3e−1 (1.92e−3) − 1.448 6e−1 (3.04e−3) − 1.245 1e−1 (1.79e−2) + 2.001 0e−1 (6.27e−2) − 1.286 9e−1 (9.93e−3) 10 2.058 3e+0 (7.12e−1) − 1.782 9e−1 (1.41e−2) = 2.626 3e−1 (3.50e−2) − 2.007 8e−1 (2.22e−2) − 1.608 1e−1 (9.40e−4) 15 2.373 8e+0 (7.71e−1) − 2.320 8e−1 (5.04e−3) + 5.175 0e−1 (4.45e−2) − 2.646 1e−1 (4.08e−3) + 2.344 5e−1 (5.33e−3)
+/−/≈0/20/01/18/14/15/10/20/0
注：1）“+”表明该算法优于ADRVEA，“−”劣于ADRVEA，“=”则表示与ADRVEA性能相似；2）最好的结果用加粗字体表示。
第 1 期孙文静，李军华：基于自适应支配和参考向量的高维多目标优化算法• 55 •
3.2.2 WFG测试集上的性能对比
表3为不同算法在WFG1-9上获得IGD+值的均值和标准差。可见，ADRVEA和KnEA在混合结构PF的WFG1上性能明显优于其他算法。ADRVEA在处理5、8、10和15目标断开PF的WFG2时算法良好。WFG3具有线性和退化的PF，RPEA在处理该问题时明显优于其他算法。WFG4-9都有凹型的PF，但在决策变量空间的设计存在不同困难。WFG4的PF是多模态，虽然KnEA 在处理15目标时性能最佳，但ADRVEA在5、8和10目标时性能突出。WFG5具有欺骗性特征，ADRVEA在5、8、10和15目标中性能显著。在处理具有不可分且缩放PF的WFG6时，ADRVEA 总体性能良好。
WFG7的PF具有可分离的单峰，ADRVEA在处理5、8和10目标时取得显著的性能。WFG8具有不可分的特性，ADRVEA和KnEA在该问题上性能总体良好。WFG9具有复杂的特性，则处理
表 3 对比算法在WFG1-9上获得IGD+的均值和标准差
问题M GrEA KnEA MOMBIII RPEA ADRVEA
2021年属WFG1
37.358 3e−2 (2.62e−3) +7.325 5e−2 (4.10e−3) + 6.451 7e−2 (5.58e−4) + 2.439 4e−1 (2.60e−2) − 1.720 3e−1 (2.51e−2) 5 2.489 1e−1 (1.54e−2) − 1.491 6e−1 (6.27e−3) − 2.922 4e−1 (1.24e−1) − 1.803 4e−1 (9.00e−3) − 1.315 1e−1 (1.82e−2) 8 5.593 6e−1 (1.10e−1) − 2.750 0e−1 (1.78e−2) + 3.707 2e−1 (5.12e−2) = 3.156 8e−1 (5.96e−2) + 3.656 1e−1 (7.93e−2) 10 5.433 2e−1 (1.46e−1) − 2.790 0e−1 (2.27e−2) =8.591 0e−1 (1.30e+0) − 3.836 5e−1 (4.25e−2) − 2.863 0e−1 (6.01e−2) 15 7.332 9e−1 (2.07e−1) −7.615 3e−1 (5.30e−1) − 3.602 3e+0 (5.00e+0) − 6.816 1e−1 (1.82e−1) − 4.007 3e−1 (1.35e−1)
WFG2
3 4.460 5e−2 (1.64e−3) + 4.961 7e−2 (2.39e−3) + 5.007 5e−2 (7.62e−3) + 1.038 3e−1 (6.41e−2) − 6.898 3e−2 (6.78e−3) 5 1.821 6e−1 (1.64e−2) − 1.478 7e−1 (1.09e−2) − 1.988 3e−1 (6.50e−2) − 2.183 1e−1 (8.05e−2) − 1.056 4e−1 (3.01e−3) 8 2.931 9e−1 (2.29e−2) − 2.839 5e−1 (2.89e−2) − 3.263 2e−1 (3.90e−2) − 3.427 4e−1 (1.05e−1) − 1.690 8e−1 (5.84e−3) 10 3.210 1e−1 (7.70e−2) − 3.01
4 3e−1 (3.00e−2) − 2.542 4e+0 (2.56e+0) − 4.547 1e−1 (1.37e−1) − 1.701 8e−1 (9.07e−3) 1
5 9.800 7e−1 (3.35e−1) − 4.989 2e−1 (2.31e−1) − 1.263 0e+1 (8.41e+0) − 5.637 0e−1 (3.01e−1) − 2.235 0e−1 (1.81e−2)
WFG3
3 5.296 4e−2 (3.10e−3) + 6.16
4 2e−2 (5.37e−3) + 4.436 7e−2 (8.66e−4) + 2.253 4e−2 (2.28e−3) + 1.960 9e−1 (3.17e−2)
5 3.414 5e−1 (5.09e−2) + 3.298 2e−1 (4.16e−2) +9.787 4e−1 (7.47e−2) − 3.555 7e−2 (3.94e−3) + 4.387 1e−1 (6.23e−2) 8 5.347 7e−1 (7.16e−2) +8.419 7e−1 (9.90e−2) +7.375 5e+0 (4.06e−1) − 1.123 9e−1 (3.41e−2) + 1.693 1e+0 (2.71e−1) 10 1.504 3e+0 (2.91e−1) + 1.123 2e+0 (1.28e−1) +9.565 5e+0 (2.16e−1) − 1.398 8e−1 (1.74e−2) + 2.150 7e+0 (2.72e−1) 15 2.645 9e+0 (3.16e−1) + 2.541 7e+0 (5.34e−1) + 1.464 8e+1 (2.09e−1) − 4.363 7e−1 (1.12e−1) + 3.669 2e+0 (3.18e−1)
WFG4
37.851 2e−2 (7.24e−4) −9.940 8e−2 (3.94e−3) −7.353 6e−2 (3.94e−3) + 1.140 6e−1 (1.14e−2) −7.7
12 4e−2 (1.12e−3) 5 4.085 0e−1 (6.31e−3) − 3.352 3e−1 (5.05e−3) − 3.310 7e−1 (7.32e−3) − 4.639 9e−1 (1.70e−2) − 3.056 6e−1 (2.61e−3) 89.532 3e−1 (1.53e−2) −7.671 5e−1 (1.53e−2) =9.266 0e−1 (4.45e−1) = 1.193 2e+0 (8.95e−2) −7.650 6e−1 (9.58e−3) 10 1.747 2e+0 (1.77e−1) − 1.047 2e+0 (6.48e−3) − 4.170 1e+0 (3.38e+0) = 1.288 2e+0 (4.63e−2) −9.577 3e−1 (9.94e−3) 15 5.929 2e+0 (2.46e−1) − 1.344 6e+0 (1.82e−2) + 1.730 8e+1 (3.09e+0) − 2.127 5e+0 (3.23e−1) − 1.346 1e+0 (1.79e−1)
WFG5
3 1.253 7e−1 (1.92e−4) + 1.487 5e−1 (3.17e−3) − 1.390 8e−1 (3.66e−3) − 1.635 0e−1 (6.62e−3) − 1.30
4 1e−1 (6.93e−4)
5 4.797 0e−1 (6.33e−3) − 3.865 9e−1 (7.81e−3) − 4.199 0e−1 (1.07e−2) − 5.375 1e−1 (1.83e−2) − 3.533 5e−1 (1.78e−3) 89.979 6e−1 (1.66e−2) −8.497 9e−1 (1.22e−2) − 1.177 5e+0 (3.66e−2) − 1.377 1e+0 (7.97e−2) −8.025 5e−1 (8.11e−3) 10 1.962 8e+0 (1.92e−1) − 1.115 3e+0 (5.52e−3) − 4.835 7e+0 (5.14e+0) − 1.647 6e+0 (9.27e−2) −9.907 7e−1 (9.10e−3) 15 6.078 3e+0 (4.25e−1) − 1.404 2e+0 (1.37e−2) − 2.269 3e+1 (1.88e+0) − 2.717 1e+0 (3.28e−1) − 1.389 2e+0 (
1.88e−2)
• 56 •南昌航空大学学报：自然科学版第 35 卷
