基于帕累托前沿面曲率预估的超多目标进化算法.pdf

基于帕累托前沿面曲率预估的超多目标进化算法*梁正平,林万鹏,胡凯峰,明仲,朱泽轩(深圳大学计算机与软件学院,广东深圳518060)通信作者:梁正平,E-mail:摘要:基于分解的超多目标进化算法是求解各类超多目标优化问题的主流方法,其性能在很大程度上依赖于所采用参考向量与真实帕累托前沿面(Paretofront,PF)的匹配程度.现有基于分解的超多目标进化算法尚难以同时有效处理各类 PF 不同的优化问题.为此,提出了一种基于 PF 曲率预估的超多目标进化算法(MaOEA-CE).所提算法的核心包括两个方面,首先基于对 PF 曲率的预估,在每次迭代过程中生成不同的参考向量,以渐进匹配不同类型问题的真实 PF;其次在环境选择过程中,再基于预估的曲率选择合适的聚合函数对精英解进行挑选,并对参考向量进行动态调整,在维护种群多样性的同时提升种群的收敛性.为验证 MaOEA-CE 的有效性,将其与 7 个先进的超多目标算法在 3 个主流测试问题集 DTLZ、WFG 和 MaF 上进行对比,实验结果表明 MaOEA-CE 具有明显的竞争力.关键词:超多目标优化;进化算法;曲率预估;参考向量;环境选择中图法分类号:TP301中文引用格式:梁正平,林万鹏,胡凯峰,明仲,朱泽轩.基于帕累托前沿面曲率预估的超多目标进化算法.软件学报,2023,34(9):40964113.http:/ Evolutionary Algorithm Based on Curvature Estimation of Pareto FrontLIANGZheng-Ping,LINWan-Peng,HUKai-Feng,MINGZhong,ZHUZe-Xuan(CollegeofComputerScienceandSoftwareEngineering,ShenzhenUniversity,Shenzhen518060,China)Abstract:Themany-objectiveevolutionaryalgorithmbasedondecompositionisthemainapproachtosolvingmany-objectiveoptimizationproblems,but its performance largely depends on the matching degree between the adopted reference vectors and the real Pareto front(PF).Existing decomposition-based many-objective evolutionary algorithms can hardly deal with all kinds of many-objective optimizationproblemswithdifferentPFatthesametime.Tosolvethisissue,thisstudyproposesamany-objectiveevolutionaryalgorithmbasedonthecurvatureestimation(MaOEA-CE)ofPF.Thecoreoftheproposedalgorithmincludestwoaspects:Firstly,onthebasisofPFcurvatureestimation,different reference vectors are generated in each iteration to gradually match the real PF of different kinds of problems.Secondly,withtheestimatedPFcurvature,theappropriateaggregationfunctionisusedtoselectelitesolutionsanddynamicallyadjustthegenerated reference vector in the environmental selection,which can improve the convergence while maintaining the diversity of thepopulation.Moreover,MaOEA-CE is compared with seven advanced many-objective algorithms on three mainstream problem sets fortesting,i.e.,DTLZ,WFG,and MaF,to verify its effectiveness.The experimental results prove that MaOEA-CE has strongcompetitiveness.Key words:many-objectiveoptimization;evolutionaryalgorithm;curvatureestimation;referencevectors;environmentalselection一般来说,一个多目标优化问题(multi-objectiveoptimizationproblem,MOP)1可以用如下数学形式进行表示:min F(x)=(f1(x),f2(x),.,fM(x)s.t.x (1)*基金项目:国家重点研发计划(2021YFB2900800);国家自然科学基金(61871272);广东省自然科学基金(2020A1515010479,2021A1515011911);深圳市高等院校稳定支持(20200811181752003)收稿时间:2021-01-09;修改时间:2022-01-07;采用时间:2022-01-29;jos 在线出版时间:2022-10-27CNKI 网络首发时间:2022-12-29软件学报ISSN1000-9825,CODENRUXUEWE-mail:Journal of Software,2023,34(9):40964113doi:10.13328/ki.jos.006648http:/中国科学院软件研究所版权所有.Tel:[phone]F(x)其中,x=(x1,x2,xn)是决策空间中的 n 维决策向量,为待求解的 M 个目标函数.当 M 大于 3 时,也称为超多目标优化问题(many-objectiveoptimizationproblem,MaOP)2.基于分解的进化算法对于 MaOP 的求解具有较大的竞争优势,已在各类复杂的软件项目管理、路径规划、特征抽取等 MaOPs 的求解中得到广泛应用37.基于分解进化算法的核心是利用参考向量对目标空间进行划分,将单个超多目标优化问题分解为多个单目标优化问题,然后再进行求解.影响此类算法性能的关键因素是所采用参考向量与待求解问题真实 PF 的匹配程度.基于分解的超多目标进化算法(many-objectiveevolutionaryalgorithmbasedondecomposition,MaOEA/D)中常见的参考向量生成方法包括 NBI8,K-layer9和 MixtureUniformDesign(MUD)10这 3 种类型.其中,NBI 是使用最为广泛的参考向量生成方法,非常适合线性 PF 优化问题的处理.K-layer 方法对于凹型 PF 优化问题有较好的效果.MUD 方法的优势则在于支持任意数目参考向量,但所生成参考向量的多样性不如 NBI 和 K-layer.总体而言,上述 3 类参考向量生成方法各自适合处理一些特定的规则型 PF 优化问题,对于断开、退化、偏好等不规则型PF 优化问题,由于所生成参考向量在 PF 上的分布不均匀,难以取得较好的效果.为支持不同形状 PF 优化问题的处理,现有 MaOEA/D 类算法通常在种群进化过程中引入对参考向量进行自适应调整的策略.根据调整过程中所使用启发式信息来源的不同11,可分为随机参考向量6,12,13、拟合自适应参考向量14,15、局部种群引导的自适应参考向量16,17、局部存档引导的自适应参考向量18,19、基于邻接参考向量的自适应参考向量20,21和基于偏好的自适应参考向量22,23等.上述参考向量调整策略虽然在解决各类不规则 PF 优化问题时可取得较好的效果,但却容易导致在处理规则 PF 优化问题时性能恶化24.为能同时处理好不同形状的 PF 优化问题,且更好地平衡种群的多样性和收敛性,本文提出一种基于 PF曲率预估的超多目标进化算法(many-objectiveevolutionaryalgorithmbasedoncurvatureestimationofPF,MaOEA-CE).MaOEA-CE 采用了一种基于曲率预估的参考向量生成方法(referencevectorsbasedoncurvatureestimation,RVCE),通过当前种群对真实 PF 的曲率进行预估,生成可大致适应实际 PF 形状的参考向量,并在每次迭代过程中对参考向量进行调整,渐进匹配不同类型优化问题的真实 PF.同时,提出了一种基于曲率预估的环境选择策略(environmentselectionbasedoncurvatureestimation,ESCE),进一步基于预估的曲率选择合适的聚合函数对精英解进行挑选,并对参考向量进行动态调整,在维护种群多样性的同时提升种群的收敛性.本文的主要工作和创新点如下.(1)提出一种新的基于曲率预估的参考向量生成方法,该方法可在进化过程中渐进匹配各种形状的 PF.(2)提出一种新的基于曲率预估的环境选择策略,利用预估的曲率自适应选择聚合函数,可较好地平衡种群的多样性和收敛性.(3)将 MaOEA-CE 与 7 个先进的超多目标优化算法在 DTLZ、WFG 和 MaF 问题集上进行对比实验,对MaOEA-CE的性能进行全面验证.本文第 1 节介绍相关工作.第 2 节阐述所提算法的主要内容.第 3 节对实验方案、实验结果进行介绍,并进行相关分析.最后总结全文并对未来工作进行探讨.1 相关工作 1.1 参考向量生成方法Mi=1fi=1MaOEA/D 中常见的参考向量生成方法包括 NBI8,K-layer9和 MUD10.NBI 通过在 M 1 维的单位超平面上进行均匀采点生成参考向量,且满足.由 NBI 生成的参考向量在线性 PF 优化问题上的多样性很好,但对于凹/凸 PF 优化问题,其参考向量存在稀疏不均的缺陷.K-layer 首先将 M 1 维超平面切分成 M 个平面三角形,然后在各切分子区域内通过均匀采点生成参考向量.由 K-layer 生成的参考向量中心密集、边缘稀疏,较适合处理凹型 PF 优化问题,在线性和凸型 PF 优化问题上的多样性则不如 NBI.MUD 采用与 NBI 相同的采点方式,然后将所采集的点转换到一个 M 维单纯形上,再根据转换后的点生成参考向量.由 MUD 生成的参考向量在角落区域较为稀疏,其多样性总体较差.梁正平等:基于帕累托前沿面曲率预估的超多目标进化算法4097 1.2 参考向量调整方法根据参考向量调整过程中所使用启发式信息来源的不同,现有参考向量调整方法可分为如下几种类型.(1)随机参考向量,不使用任何启发式信息,而是采用随机方式对参考向量进行调整.如 MOGLS12在每轮迭代过程中通过随机生成的参考向量来引导精英种群的搜索,RVEA*6则周期性地剔除无效参考向量,并采用随机方式补充新的参考向量.此类方法的优点在于操作简单、容易实现,但难以有效保证种群的多样性和收敛性.f1p+f2p+.+fMp=1(2)拟合自适应参考向量,通过对整个种群/存档的拟合来调整参考向量.如 pa-MOEA/D14将 PF 拟合在的曲面上,同时引入 HV 指标25对参考向量进行调整.此类方法利用整个种群/存档的信息来估计 PF 的形状,从而具有一定的稳健性,缺陷在于要求待求解问题的 PF 形状满足所构建的理论模型,否则拟合出的参考向量质量难以保障.(3)局部种群引导的自适应参考向量,利用局部种群中的个体来调整参考向量.如 MOEA-AM2M16将各子区域内与选定个体具有最大夹角的个体作为新参考向量,g-DBEA17选择跟被删除参考向量具有最大垂直距离的个体作为新的参考向量.此类方法是最常见的参考向量调整方法,当种群能够贴近真实 PF 时可以在各种不规则 PF优化问题上发挥很好的作用,当种群与真实 PF 相差很远时则容易被多样性或收敛性差的个体误导.(4)局部存档引导的自适应参考向量,利用局部存档中的个体来调整参考向量.如 MOEA/D-AWA18首先对外部存档中的个体在当前种群内的稀疏水平值进行计算,再根据稀疏水平值最高的个体生成新的参考向量.此类方法的优缺点与局部种群引导的调整方法相似.(5)基于邻接参考向量的自适应参考向量,依靠邻接参考向量来调整参考向量.如 A-NSGA-III20选择在拥挤区域的有效参考向量周围生成新的参考向量.该类方法能够改善种群的局部多样性,不足之处在于较难处理退化、尖峰或长尾等 PF 形状的优化问题.(6)基于偏好的自适应参考向量,依据偏好信息来调整参考向量.如 pMOEA/D22使用期望点、保留点和偏好半径划定一块偏好区域来调整参考向量.此类方法可以使用较小的种群来处理 MaOPs,计算代价低,但单纯基于偏好信息容易导致种群陷入局部最优.2 MaOEA-CE 算法本节介绍 MaOEA-CE 算法的主要框架和核心策略,并对算法的复杂性进行分析.2.1 算法框架MaOEA-CE 的伪代码如算法 1 所示.首先,初始化大小为 N 的种群 P.在每一轮进化过程中,先根据当前种群信息预估 PF 的近似曲率 p,并利用预估的曲率 p 生成对应曲面上均匀分布的参考向量 W.接着采用二进制锦标赛法26选择父代,并使用模拟二进制交叉(SBX)27和多项式变异(PM)28变异生成子代种群.最后基于曲率 p 和参考向量 W 对子代种群和父代种群的并集进行环境选择.循环上述过程,直至达到最终的进化代数,将最后一代的精英个体组成的种群 P 作为输出.算法 1.MaOEA-CE 算法框架.输入:种群大小 N;输出:种群 P.1.初始化种群 P2.while未达到最大迭代次数do3.根据当前种群 P 预估 PF 的曲率 p4.根据曲率 p 生成参考向量 W5.使用交叉变异生成子代 O6.基于 p 和 W 对 PO 进行环境选择4098软件学报2023 年第 34 卷第 9 期7.end while8.returnP 2.2 曲率预估(1)归一化由于 PF 的缩放会影响曲率 p 的估算,导致生成的参考向量不能很好地匹配真实 PF 的形状.为此,在估算种群所对应 PF 的曲率之前,需对种群进行归一化处理.本文中,将种群 P 的非支配层在各个维度分量上的最小值,作为理想点 z 的对应分量.将角落解在各个维度分量上的最大值,作为极差点 znad 的对应分量.角落解为距离各个方向轴最近的个体,其第 i 维分量值的计算公式如下:xcorneri=x|x=argmindist(x,ei)(2)其中,x 为目标向量,e 为各轴的单位方向向量,dist 为目标向量 x 到轴向单位方向向量 e 的欧式距离.在计算出理想点 z 和极差点 znad 后,对目标向量各个维度进行归一化的公式如下:fi(x)=fi(x)ziznadizi(3)(2)估算 PF 的曲率由于种群中支配个体的收敛性不如非支配个体,若将收敛程度较差的支配个体用于曲率预估,容易导致所估算的近似 PF 的曲率与真实 PF 存在较大差异.为此,本文采用 2REA29中提出的方法,仅选取种群中的非支配个体,并基于它们的 Lp距离30来对曲率 p 进行自适应估算.其中,Lp距离的计算公式如下:L(x|p)=Mi=1(fi(x)p1/p,p 0(4)f1p+f2p+.+fMp=1f1p+f2p+.+fMp=1曲率预估的具体过程如下:首先将 p 值限定在合适的取值区域,并基于一定间隔进行采样,然后分别计算在每个 p 值下,所有非支配个体的 Lp距离对应的标准差.由于所选 p 值对应的曲面越贴近非支配个体构成的近似 PF,对应的标准差越小.故标准差最小的 p 值曲面最接近非支配个体所构成的近似 PF,从而可用该 p 值对应的曲面对当前种群进行拟合,并将该 p 值作为当前种群所对应 PF 曲率的预估值.2.3 根据预估曲率生成参考向量RVCE 的总体框架类似 NBI8,但对于参考向量各维度上的分量值,则基于预估的 PF 曲率进行计算,其伪代码如算法 2 所示.算法 2.参考向量生成.输入:曲率 p,种群大小 N;输出:参考向量 W.1.使用公式(5),公式(6)计算 H,H2.通过公式(7)将曲率为 p 的弧线段均匀划分成 H 份,计算出对应的t0,t1,tH3.根据t0,t1,tH和公式(9)构建参考向量 W4.ifHMthen5.通过公式(7)将曲率为 p 的弧线段均匀划分成 H份,计算出对应的t0,t1,tH6.根据t0,t1,tH和公式(9)构建参考向量 W7.使用公式(10)将 W向内部缩放 1/28.W=WW9.end if10.returnW梁正平等:基于帕累托前沿面曲率预估的超多目标进化算法4099首先,根据目标维度 M 和种群大小 N,使用公式(5)计算各目标维度的划分数 H.若 HM,使用单层采点8生成全部参考向量,如图 1(a)所示,其中的红色实心点对应生成的参考向量.若 HM,使用单层采点即可生成全部参考向量.图 2(a)为均匀切分弧线段的图例,根据公式(7),t0,t1,t2,t3,t4,t5,t6分别对应0,0.2588,0.5000,0.7071,08660,0.9659,1.图 2(b)展示了根据公式(9)构建参考向量坐标(0,0,1),(0,0.2588,0.9659),(0.9659,0.2588,0),(1,0,0)的过程,其中 u1,u2,u3分别为参考向4100软件学报2023 年第 34 卷第 9 期量在第一、第二、第三维的分量.图 2(c)展示了最终生成的参考向量,它们均匀分布在预估曲率所对应的曲面上.f1p+f2p+.+fMp=1RVCE 基于自适应方式生成的预估曲率 p,将不同问题的真实 PF 用曲率不同的曲面进行拟合,并基于该曲面生成具有良好多样性的均匀分布参考向量,从而可较好支持各类 PF 优化问题的处理.101t1t2f1t3t4t5f2u1:u2:u3:0000000000.258 80.258 80.258 80.258 80.258 80.965 90.965 90.965 90.965 9 0.866 01111.00.80.60.40.2000.51.0 1.00.50(a)均匀切分弧线段(b)构建参考向量坐标(c)参考向量在预估曲面上的分布图2RVCE 在三维问题上生成参考向量的示例 2.4 基于预估曲率进行环境选择ESCE 的核心是基于预估的曲率和所生成的参考向量,通过自适应选择聚合函数来挑选精英解.同时通过对参考向量的动态调整,以更好地支持各类不规则型 PF 优化问题.其伪代码如算法 3 所示.算法 3.环境选择.输入:种群 R,种群大小 N,曲率 p,参考向量 W;输出:精英种群 P.1.从种群 R 中找出角落解放入 S 中2.归一化种群 R3.剔除参考向量 W 中没有非支配解关联的参考向量4.根据曲率 p 和参考向量 W 从种群 R 中选出精英种群 S/算法 45.S=SS,R=RS6.if|S|Nthen7.在 S 中剔除|S|N 个局部密度最大的解8.P=S9.end if10.if|S|Nthen11.根据曲率 p、当前精英种群 S 和当前种群 R 确定最终精英种群 U/算法 512.P=U13.end if14.returnP由于角落解覆盖空间大,且相互间隔较远,为确保种群整体的多样性,首先将种群中的角落解作为默认的精英解.接着,对种群进行归一化,并剔除参考向量集中没有任何非支配解关联的无效参考向量.然后,根据预估曲率和剩余的参考向量,通过自适应选择聚合函数,从种群的非支配解集中挑出聚合函数值最优的解作为精英解,如算法 4 所示.最后,若挑选出的精英解个数大于 N,则逐一计算各精英解的局部密度26,并依次删除局部密度最大的多余精英解.若挑选出的精英解个数小于 N,则继续采用算法 5,根据预估曲率、已挑选出的精英解和余下的非支配解,通过新生成的参考向量,继续挑选更多的精英解,直至精英解个数等于 N.梁正平等:基于帕累托前沿面曲率预估的超多目标进化算法4101算法 4.根据曲率和参考向量选择精英种群.输入:候选种群 R,曲率 p,参考向量 W;输出:精英种群 S.1.S=2.forwWdo3.ifp1then4.计算种群 R 中各非支配解与参考向量 w 的 PBI 聚合函数值5.else6.计算种群 R 中各非支配解与参考向量 w 的 TCH 聚合函数值7.end if8.找出聚合函数值最优的解 s9.S=Ss10.end for11.returnSf1p+f2p+.+fMp=1在算法 4 中,对于每个有效参考向量,均通过最优聚合函数值,从非支配解中挑出一个作为环境选择的精英解.当预估曲率 p1 时,选择正交边界惩罚函数(PBI)3作为聚合函数,当曲率 p1 时,则选择切比雪夫函数(TCH)31作为聚合函数.原因在于相比其他聚合函数,对于 PF 形状为非凸的优化问题,PBI 能够在保证种群收敛性的同时提供更好的多样性3,而对于 PF形状为凸的优化问题,TCH 能更好地平衡种群的收敛性和多样性32.因此,通过预估曲率对聚合函数进行自适应选择,有利于确保在将各类 PF 形状拟合到曲面时,都能根据有效参考向量选择出质量更好的精英解,避免仅使用单种聚合函数存在的偏好,从而有效平衡种群的收敛性和多样性.算法 5.根据曲率和当前精英种群确定最终精英种群.输入:候选种群 R,当前精英种群 S,曲率 p;输出:最终精英种群 U.1.U=S2.while|U|1,则将两个解与原点之间构成的夹角作4102软件学报2023 年第 34 卷第 9 期为解之间的距离;若将 PF 拟合成凸形曲面,即 p1,则将两个解与极差点 znad 的夹角作为解之间的距离.基于上述最小距离的最大值找出的 x,是当前种群非支配解中多样性最好的解,因而最合适作为新的参考向量来挑选精英解.此外,为进一步提升种群的收敛性,在每轮选择的最后,均将当前剩余种群中收敛性最差的解删除.由于分量和方法具有简单高效,且搜索性能强等优点26,此处采用分量和作为种群中各个解的收敛指标.图 3 为二维空间中使用 ESCE 进行环境选择的示例.种群大小 N 设为 7,红色弧线表示所拟合的 PF 曲线,其曲率 p=0.5,v1v7为基于 RVCE 生成的参考向量,x11x14为种群的候选解,其中 x1x7为第 1 层非支配解,x8x11为第 2 层非支配解.从图 3 可见,x1和 x7为角落解,直接加入精英种群中.v2和 v6没有非支配解与之关联,从参考向量中将它们剔除.由于 p1,选择 TCH 作为聚合函数,得到分别与剩余参考向量 v1、v3、v4、v5和 v7逐一对应,且聚合函数值最优的 x1、x3、x4、x6和 x7作为新获得的精英解.此时精英种群的大小为 5,需继续挑选精英解.在剩余种群中,x2和 x5为非支配解.从图 3 可见,相比 x2,x5与当前精英种群中各个解的最小距离更大,故将 x5作为新的参考向量.进一步可发现相比 x2,候选解 x5与新参考向量的 TCH 值更优,将 x5加入精英种群.之后,从种群中剔除刚选出的精英解 x5,以及收敛性最差的候选解 x2.继续对剩余种群进行处理,可发现 x9为精英解.此时,精英解的个数等于种群大小,环境选择结束.v1v2v3v4v5v6x1x2x12x8x3x4x10 x5x11x6x14x9x131.00.80.60.40.2000.20.40.60.81.0 x7v7拟合 PF候选解参考向量f2f1图3ESCE 在二维空间中选择精英解的示例 2.5 时间复杂度分析曲率预估的时间复杂度为 O(MN)29,其中 M 是目标维度,N 是种群大小.算法 2 使用预估曲率根据公式(9)生成 N 个参考向量,采用单层采点时的时间复杂度为 O(N),采用双层采点时,考虑外层采点的缩放计算,最坏情况下的计算量是单层采用时的两倍,但时间复杂度依然为 O(N).子代生成中,遗传算子 SBX 和 PM 的时间复杂度为O(DN),其中 D 是决策变量的数目.环境选择过程中,非支配排序的时间复杂度为 O(NlogM2N)7,非支配解与目标空间各方向轴的距离计算需消耗的时间复杂度为 O(MN),种群归一化时间复杂度为 O(MN),算法 4根据参考向量W 选择精英解集需消耗的时间复杂度为 O(MN|W|),其中|W|为参考向量的个数.由于|W|N,故算法 4 的最坏时间复杂度为 O(MN2).对于算法 5,最坏情况下需要补充(NM)N 个解,但其每次调用算法 4时仅涉及一个参考向量,故算法 5 的最坏时间复杂度为 O(MN2).综上分析可知,MaOEA-CE 的时间复杂度为 maxO(MN2),O(DN).3 实验设计与结果分析本节在 DTLZ32、WFG33和 MaF34问题集上,将 MaOEA-CE 与 7 个先进的超多目标优化算法进行对比,以验证 MaOEA-CE 的优异性能.此外,在不同类型的 PF 问题上,分别对参考向量生成方法 RVCE 和环境选择策略ESCE 的有效性进行验证.梁正平等:基于帕累托前沿面曲率预估的超多目标进化算法4103 3.1 实验设计(1)测试问题DTLZ 和 WFG 是 MaOPs 领域两组经典的测试问题集,其中不同的测试问题具有不同的特性和 PF 形状.MaF 是问题特性更为复杂的最新测试问题集,对现有 MaOEA 算法提出了更大的挑战.这 3 组测试问题集包含各种类型的 PF 形状,可大致分为规则 PF 与不规则 PF 两类.规则 PF 又可分为平面 PF、凹曲面 PF 和凸曲面 PF,不规则 PF 问题可分为退化 PF、断开 PF、倒置 PF、凹/凸混合 PF 和具有偏好的 PF 等.其中,DTLZ1、MaF9 和MaF14 为平面 PF,DTLZ2-4、WFG4-9、MaF5 和 MaF12-13 为凹曲面 PF,MaF3 为凸曲面 PF,DTLZ5-6、WFG3和 MaF6 为退化 PF,DTLZ7 和 MaF7 为断开 PF,MaF1、MaF4、MaF8 和 MaF15 为倒置 PF,WFG1-2 和 MaF10-11 为凹/凸混合 PF,MaF2 为具有偏好的 PF.(2)对比算法考虑到 MaOEA-CE 为基于分解的超多目标优化算法,为对其性能进行充分验证,选取多个基于分解的代表性算法 NSGA-III4、RVEA6、SPEA-R9、ASEA35和 hpaEA36作为对比算法,同时也将基于改进 Pareto 关系的算法 NSGA-II-SDR37、基于指标的算法 MaOEA-IGD38作为对比算法,以更全面的验证 MaOEA-CE 的性能.1)NSGA-III 是 MaOEA 领域的经典算法,其特点是将非支配排序与参考向量结合,可提高算法运行效率.2)RVEA 提出了一个新颖的聚合算子 APD,该算子在进化前期偏向于收敛性而在后期侧重多样性,可取得较好的综合性能.3)SPEA-R 提出了一种基于参考向量的密度估计方法和多样性优先的环境选择策略,对处理高维 MaOPs具有很好的性能表现.4)ASEA 提出了一个两阶段排序的环境选择策略,可较好地平衡种群的收敛性和多样性.5)hpaEA 提出了一种突出解选择方法,在父代选择和环境选择过程中优先保护突出解,可提高种群的收敛性.6)NSGA-II-SDR 提出了一种新颖的支配关系 SDR,基于候选解之间的夹角自适应选择精英解,可较好地平衡种群的收敛性和多样性.7)MaOEA-IGD 提出了一种高效的支配比较方法,并基于 IGD 指标进行环境选择,在解决 MaOP 方面具有相当的竞争力.(3)评价指标HV25指标通过计算解集与目标空间参考点之间围成的超体积来对算法进行评估,HV 值越大表示算法性能越好.由于 HV 指标具有严格的帕累托相容性39,可以很好地评判 MaOEA 的综合性能.为了提高 HV 指标的计算效率,本文采用蒙特卡罗模拟方法来计算 HV 指标的值.类似文献 29,使用 10000 个采样点来保证计算的准确性,同时将参考点设为(1.5,1.5,1.5).此外,为验证参考向量生成方法 RVCE 的多样性,本文还采用 SPREAD40指标对其多样性进行专门衡量.(4)参数设置为确保实验的公平性,所有算法使用相同的种群大小.目标数 M 和种群数量 N 的具体设置如表 1 所示.遗传算子 SBX 和 PM 的参数设置如表 2 所示.参照文献 41,决策变量数 D 统一设为 100,WFG 测试问题中的位置变量数设为 k=M1.每个算法独立运行 30 次,实验中的进化代数统一为 2000 代.各对比算法特有的其他参数,采用各自原始文献中设定的值.通过计算 HV 指标的均值和标准差,采用 Wilcoxon 秩和检验对 MaOEA-CE 与其他 7个先进算法综合性能进行衡量.实验结果表格中使用符号“+”“”“”分别表示对比算法的性能在 5%的显著水平上优于、劣于、等于 MaOEA-CE,加粗表示每个测试问题上的最佳结果.表1种群大小设置目标数(M)分割数(H)种群大小(N)312915621083,2156103,2275表2交叉变异参数设置参数名参数值交叉概率(Pc)1.0变异概率(Pm)1/D交叉分布指标(c)20变异分布指标(m)204104软件学报2023 年第 34 卷第 9 期 3.2 实验结果与分析(1)算法整体性能验证与分析表 3表 5 分别展示了 8 个算法在 DTLZ、WFG 和 MaF 测试问题集上的 HV 值统计结果.可以看出,MaOEA-CE 在绝大部分测试问题上都取得了最佳 HV 均值,说明 MaOEA-CE 具有非常优异的整体性能.下面分别介绍各个算法在 3 个测试问题集上的详细结果并进行分析.表3不同算法在 DTLZ17上获得的 HV 值的统计结果(均值)ProblemMMaOEA-CENSGA-IIIRVEASPEA-RASEAhpaEANSGA-II-SDRMaOEA-IGDDTLT139.3746E19.3757E1+9.3758E1+8.9761E19.3758E1+9.3794E1+9.0603E19.2458E159.9535E19.9572E19.9575E19.8701E19.9570E19.9596E1+9.7795E19.7590E189.9981E19.9978E19.9980E19.9831E19.9980E19.9983E1+9.5818E19.7182E1109.9999E19.9940E19.9999E19.9910E19.9999E19.9999E19.6778E19.7637E1DTLZ238.2719E18.2633E18.2633E18.2511E18.2632E18.2667E17.1278E18.1986E159.6105E19.6032E19.6032E19.5966E19.6022E19.6122E1+9.5620E19.6031E189.9434E19.9259E19.9364E19.9328E19.9360E19.8982E19.7828E19.9377E1109.9884E19.9769E19.9864E19.9847E19.9863E19.9607E19.9831E19.9867E1DTLZ338.2707E18.2586E18.2599E17.6426E18.2632E18.2611E17.0900E16.9920E159.6110E19.6015E19.6027E18.9202E19.6031E19.6088E19.5766E19.6014E189.9421E19.8869E19.9359E13.6538E19.9366E19.2456E19.8530E19.9215E1109.9881E19.9597E19.9864E11.9874E29.9860E12.2700E19.9837E19.9866E1DTLZ437.7498E18.0810E1+8.1421E1+8.2468E1+8.1995E1+6.5919E16.5694E17.5729E159.6107E19.5856E19.6023E19.5944E19.6015E19.3655E18.4979E19.5886E189.9435E19.9097E19.9349E19.9315E19.9363E19.8974E19.0644E19.9165E1109.9885E19.9833E19.9864E19.9844E19.9864E19.9854E19.7358E19.9868E1DTLZ534.9691E14.9227E14.6895E14.8013E14.8293E14.9672E14.8459E12.7776E153.9329E13.7469E13.5853E12.6792E13.5169E13.2557E13.7479E13.3263E183.5127E13.3844E13.3362E11.1313E13.3418E11.7885E13.3921E13.2337E1103.4556E13.3533E13.3342E18.7316E23.3355E11.5405E13.3468E13.3387E1DTLZ634.9712E14.8962E14.3809E14.8205E14.6560E14.9706E14.7656E12.7059E153.9140E13.5882E13.6385E11.1392E13.4855E12.4060E13.7179E12.9571E183.4922E13.3359E13.3957E11.8683E33.3414E15.0408E23.3563E13.1209E1103.4616E13.3338E13.3633E12.4107E43.3359E19.9183E33.3355E13.2287E1DTLZ735.2444E15.2897E1+5.2457E1+5.2656E1+5.2049E15.1360E15.2203E14.3744E154.8477E15.3138E1+4.9513E1+5.2104E1+5.1085E1+5.2420E1+5.1197E1+4.4938E184.2246E14.9148E1+4.1973E14.6964E1+3.3758E14.8455E1+4.3294E1+3.5903E1104.1267E14.7833E1+4.0332E14.6247E1+3.5668E14.7031E1+4.4377E1+1.8168E1+/6/21/14/21/35/23/03/24/17/20/13/25/00/28/0f1p+f2p+.+fMp=1f1p+f2p+.+fMp=1表 3 为 8 个算法在 DTLZ 的 7 个测试问题上的 HV 值统计结果.可以看出,在 DTLZ 的 28 个测试实例中,MaOEA-CE 在 18 个上均优于其他 7 个对比算法,尤其在 DTLZ3 和 DTLZ56 的所有目标维度上,MaOEA-CE 的性能均优于其他算法.DTLZ24 为规则型凹曲面 PF 问题,采用 RVCE 生成的参考向量在此类规则型问题上具有很好的多样性,同时在 ESCE 中使用的 PBI 聚合函数能很好平衡此类凹曲面 PF 问题的多样性和收敛性,因此MaOEA-CE 相较于其他算法有更好的性能