参考点自适应调整下评价指标驱动的高维多目标进化算法

何江红 李军华 周日贵 ,

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

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

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

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

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

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

为了能够更好地处理不规则MaOPs,提高算法的通用性,本文提出参考点自适应调整下评价指标驱动的高维多目标进化算法,该算法的具体步骤如下:1)为了有效地生成一组参考点,提出一个PF形状监测基础上的自适应参考点策略,该方法首先利用一条特定的轮廓曲线近似PF,其次在该曲线上找到所有非支配解对应的点,然后以对应点之间的距离作为多样性选择标准,最后利用该准则选择一组多样性好的解作为参考点,此外基于曲线参数对参考点的位置进行调整,以减少偏离种群的参考点所产生的影响;2)为了进一步提高算法性能,在匹配选择中结合Pareto 支配和改进的Pareto支配以及邻域关系,选择一组有希望的解作为父代种群;3)为了最终生成一组接近PF 且分布广泛的种群,在环境选择中利用参考点计算基于指标的适应度函数,将其作为选择标准进行精英选择.

1 基础知识和相关工作

1.1 基础知识

一个具有n个决策变量和m个目标变量的最小化MOPs 可以表示为:

其中x=(x1,···,xn)T∈X是n维决策向量,X表示n维决策空间;y=(y1,···,ym)T∈Y是m维目标向量,Y是m维目标空间;f:X→Y构成m个相互冲突的目标函数,是一个从n维决策空间X到m维目标空间Y的映射.在决策空间中,若解xPareto 支配解y(x≺y),则需满足:

其中fi(x)为解x在第i个目标上的真实目标值.

若在决策空间中不存在x使得x≺x*,则x*为Pareto 最优解,F(x*)为Pareto 最优向量;由于MOPs 目标之间相互冲突的性质,一个目标性能的提升通常会导致其他目标性能的下降,因此需要一组Pareto 最优解作为不同目标之间的权衡,这样的一组解被称为Pareto 解集(Pareto set,PS),对应的在目标空间中的Pareto 最优向量集被称为PF.

1.2 自适应参考点策略

在一些进化算法中通常需要一组在PF 上均匀采样的参考点用于指标值的计算,或一组均匀分布的参考向量用于划分子种群,本文统一采用参考点代替参考向量以及权重向量.由于在大部分的优化问题中,真实PF 是不可知的,因此需要不断地对参考点进行调整使其尽可能地近似PF;为了达到这个目的,研究学者们提出了一系列自适应参考点策略.

在RVEA 中,根据当前种群中目标值的范围调整参考向量,实现目标函数在没有被标准化到相同范围的情况下,依然能得到一组均匀分布的参考点;NSGA-III 中提出基于候选解的分布位置增加和删除参考点;MOEA/D 引入档案对参考点进行管理,若候选解位于稀疏区域,则将其选入档案并生成相应的参考点.

然而上述所提到的自适应参考点策略存在局限性,例如在一些优化问题中频繁地更新参考点在一定程度上影响种群的收敛性,导致出现局部收敛现象;一些自适应参考点策略的有效性取决于用户预先定义参数;某些自适应方法对不同PF 的优化问题普适性低等.因此本文提出一个新的自适应参考点策略,该策略基于PF 形状设计多样性评估准则,并根据该准则选择一组分布广泛的非支配解作为参考点,另外利用曲线参数调整参考点的位置,最终生成一组近似PF 的参考点用于指标值的计算.

1.3 IGD-NS 指标

研究学者提出许多性能指标,如世代距离(Generational distance,GD[27])、反世代距离(Inverted generational distance,IGD[28])、超体积(Hypervolume,HV[29-31])、R2[32-33]、纯多样性(Pure diversity,PD[34])、增强的反世代距离指标(Enhanced inverted generational distance,IGDNS[35-36])等,这些指标被广泛用于评估种群的收敛性、多样性,或同时评估收敛性和多样性,下面具体介绍现存的性能指标:

1) GD 指标

其中P为非支配解集,P* 为从PF 上均匀采样的参考点;GD 指标计算非支配解与参考点之间的最小欧氏距离的平均值,GD 值越小表明种群的收敛性越好;但该指标无法评估种群的多样性,若所有的非支配解重合在同一个点,且该点与参考点之间的欧氏距离很小,则依然能得到一个较好的GD 值,然而此时种群不具有多样性.

2) IGD 指标

其中P为非支配解集,P* 为从PF 上均匀采样的参考点;IGD 指标与GD 指标相似,计算每个参考点与非支配解之间的最小欧氏距离的平均值,IGD值越小,种群质量越好;该指标利用欧氏距离评估收敛性,利用参考点的均匀分布保证多样性,因此能够同时评估种群的收敛性和多样性.

3) HV 指标

其中P为解集,q为目标空间中的预定义参考点,1H(P,q)为H(P,q)的特征函数;HV 指标计算种群到参考点所覆盖的面积,HV 值越大种群质量越好;相比于GD 指标和IGD 指标,HV 的计算不需要PF 的先验信息,然而随着目标数目的增加,计算复杂度成指数形式增加.

4) R2 指标

其中P为种群,V为参考向量集,z*为当前理想点;R2 指标将候选解从目标空间映射到效用空间以计算种群的质量,R2 指标值越小说明种群质量越好;然而R2 指标对中间区域存在固有的偏好,尤其在凸型PF 的优化问题上,分布在中间区域的种群能得到一个较低的R2 指标值.

近年来,IGD-NS 指标受到研究学者们的广泛关注,该指标是 Tian 等在MOEA/IGD-NS[35]中首次提出的,与IGD 指标相比,该指标可以区分对种群没有贡献的解.文献[35]中对无贡献解做了严格定义,即在计算指标值时由于不是任何参考点的最近邻域而被忽略,从而对种群的指标值不产生贡献的解.无贡献解y′公式定义为:

根据无贡献解的定义,可以得到IGD-NS 指标的定义:

其中P*为一组均匀分布的参考点,P为非支配解集,P′为无贡献解集;由公式可知前半部分与IGD指标的计算方法一致,后半部分为无贡献解到参考点的距离,只有同时满足与参考点之间的距离小和无贡献解的数量少两个条件才能得到一个较好的指标值.

Tian 等[35]不但对无贡献解进行公式定义,为了便于理解,还佐以图例解释.如图1 所示,X、Y、Z为参考点,A、B、C、D、E为非支配解,根据上述无贡献解的定义,B、E不属于任意一个参考点的最近邻域,为无贡献解.若在环境选择中选取4 个解作为下一代种群,则需要从当前非支配解集中删除1个候选解,如果使用IGD 指标评估种群的质量,{A、D、C},{A、B、C、D、E},{A、D、C、B},{A、D、C、E} 4 个解集的IGD 指标值相同,无法区分最差解;而IGD-NS 指标由于能够区分B、E两个无贡献解,因此能更准确地评估种群的质量.

图1 二目标下的无贡献解Fig.1 The noncontributed solutions under bi-objective

根据以上分析,IGD-NS 指标与GD 指标相比,可以同时评估种群收敛性和多样性;与IGD 指标相比,可以区分无贡献解;与HV 指标相比,在高维空间中计算代价小;与R2 指标相比,对边界解或中心解不存在偏好.基于这些性质,IGD-NS 指标适合作为选择标准用于进化算法中.

2 参考点自适应调整下评价指标驱动的高维多目标进化算法

2.1 算法基本框架

算法1 为MaOEA-IAR 的主要框架,首先输入种群规模以及最大进化代数,随机生成一个规模为N的初始种群P0;其次在主循环中,通过匹配选择生成父代种群,进而生成子代种群,子代种群和初始种群合并,最后对合并种群进行环境选择生成下一代种群.下面将着重介绍算法的4 个子部分,分别为匹配选择、环境选择、自适应参考点和确定轮廓曲线.

算法1.MaOEA-IAR 算法框架

2.2 匹配选择

匹配选择能够从当前种群中选择一组有希望的解作为父代种群加入交配池.在传统的算法中,通常会利用Pareto 支配关系选择父代种群;然而在高维空间中个体之间互不支配,难以选择非支配解;因此本文采用改进的Pareto 支配,将目标值的比较替换成子空间位置的比较,对个体进行定量比较能够增加选择压力,具体过程如算法 2 所示.

首先将目标空间划分为多个子空间,并计算个体所处子空间的位置yindex,计算方法为:

其中yi为个体y在第i个目标上的目标值,Ti为第i个目标的邻域范围,z为理想点,z*为最低点;并且假设将整个目标空间分为rm个子空间,即将每个目标均分为r等分,将个体所在的子空间作为其所在的邻域,邻域范围即为T.

其次从种群中随机选取2 个个体,通过Pareto支配以及改进的Pareto 支配选择非支配解加入交配池中,在改进的Pareto 支配中,若x支配y,则需要满足:

其中xindexi为个体x在第i个目标上的位置,yindexi为个体y在第i个目标上的位置.

算法2.匹配选择

然后在无法判断支配关系的情况下,计算个体所处邻域内解的个数NUM,选择多样性好的个体加入交配池;最后若多样性也相近,则随机选取1个个体加入交配池中.

2.3 环境选择

环境选择的目的是从合并种群中获得一组接近PF 且分布良好的解集.算法3 给出了环境选择的基本步骤:首先对种群中的个体进行非支配排序,选择前k-1 个等级中的个体作为下一代,再将第k个等级中的个体通过适应度值进行删除操作,直到下一代种群中的个体数与初始种群相等(k值由每个等级中的个体数确定,为满足的最小值,即其中N为初始种群中的个体数).当目标数较小时,能够通过非支配排序选择出部分解,再通过适应度值选择剩下的解;当目标数增大时,种群中几乎所有的解都为非支配解,此时算法主要通过基于IGD-NS 指标的适应度值选择下一代种群,非支配解p的适应度为:

其中P*为一组多样性好的参考点.

算法3.环境选择

2.4 PF 形状监测基础上的自适应参考点策略

传统基于角度距离的多样性评估准则在处理非线性PF优化问题时存在偏差,尤其在凹型PF 中,相同大小的角度距离不能生成均匀分布的候选解,如图2 所示,被选择的候选解倾向于分布在中心区域.因此在生成参考点的过程中,利用基于PF 形状的多样性评估准则对参考点进行自适应,这在一定程度上可以减少这种偏差;由于单独使用多样性评估准则选择参考点可能生成偏离种群的参考点,利用理想点或最低点对参考点的位置进行调整,能够降低此类参考点的影响.

图2 基于角度距离选择参考点Fig.2 Select reference points based on angular distance

算法4.生成参考点

算法4 为自适应参考点的具体步骤,首先根据当前种群状态,用一条特定的轮廓曲线近似PF 并得到曲线参数p;然后在该曲线上找到所有非支配解的对应点,基于对应点设置多样性评估准则;之后将边界解添加到参照点集合Q,以该准则计算剩余非支配解与参照点之间的差异,选择差异最大的非支配解加入集合Q中,直到集合内个体的数量满足N,将Q中的所有个体作为初始参考点,差异值的计算公式如下:

其中x为剩余非支配解,y为参照点;x＇、y＇分别为x、y在曲线上的对应点;fi(x＇)、fi(y＇)分别为x＇、y＇在第i个目标上的值.

最后由于只考虑了多样性方面的差异,可能生成部分偏离种群的参考点,为了降低此类参考点的影响,在凸型PF 问题中,将初始参考点调整为所在邻域内的理想点,在凹型PF 问题中,将初始参考点调整为所在邻域内的最低点.调整之后的参考点如下:

其中y*为凸型PF 中调整之后的参考点,y**为凹型PF 中调整之后的参考点,y为初始参考点,z为理想点,z*为最低点,r为邻域参数,T为邻域范围.

此外,由于邻域参数r是用户预先定义的参数,在一定程度上影响参考点的调整;若参数r过大,则可能出现多个参考点处于同一邻域内;为了避免此类情况发生,本文还根据调整后的参考点数量动态改变参数r,直到每一个参考点处于不同的邻域内.

为了更清楚地理解参考点自适应过程,图3 给出一个两目标优化问题的例子说明如何进行参考点自适应.图3(a)为一组非支配解,根据非支配解的分布确定合适的轮廓曲线近似PF;在曲线上找到所有非支配解的对应点,即非支配解和原点之间的连线与曲线的交点,然后根据多样性评估准则选择一组分布广泛且均匀的初始参考点,如图3(b)所示,实心圆形即为初始参考点;由于PF 形状为凸型,因此将初始参考点调整为所在邻域的理想点,如图3(c).

图3 自适应参考点过程Fig.3 Adaptive reference point process

2.5 确定轮廓曲线以及曲线参数p

轮廓曲线与PF 的近似程度直接影响参考点的生成以及算法的性能,闵氏距离能够覆盖各种凹凸度的PF,因此本文利用闵氏距离预先估计PF 形状.算法5 对如何确定一条特定的曲线做了具体描述,首先利用m个边界解构建超平面;然后计算该超平面与原点之间的欧氏距离d,将所有候选解到原点的距离与距离d进行比较,根据种群与超平面之间的位置关系初步判断PF 的凹凸性,并相应地确定曲线参数范围,这一步的目的是缩小曲线参数的范围,降低时间复杂度;最后对于每一个p值,计算所有解的闵氏距离方差,选择方差最小时对应的p值作为曲线参数.此时轮廓曲线可以用公式表示:

图4 为一个两目标优化问题,若要判断PF 的形状,首先连接边界点A、B构建超平面,如图4(a)所示,从图中可以看出,种群中的个体大部分位于超平面的上方,并且根据非支配解与原点之间的距离和超平面与原点之间的距离可以初步判断PF 为凹型,从而确定p的取值范围为{1,1.1,1.2,···,3};然后对于每一个p值,计算所有非支配解的闵式距离方差,如图4(b)所示,方差越小,解之间的轮廓曲线越接近.

图4 确定轮廓曲线以及曲线参数Fig.4 Determine the contour curve and curve parameter

算法5.轮廓曲线

2.6 算法的时间复杂度分析

算法MaOEA-IAR 主要在环境选择中耗费时间,其中生成参考点的最大时间复杂度为O(MrN),M为目标数,r为邻域参数,N为种群规模;确定轮廓曲线以及曲线参数的时间复杂度为O(CpN),Cp为曲线参数数量;计算指标值的时间复杂度为O(N);因此算法的时间复杂度为max(O(MrN)).

3 实验研究与结果分析

在这一部分,将本文提出的算法与当前性能较好的先进算法进行实验对比,对比算法分别为:MOEA-DD、NSGA-III、RVEA、MOMBI-II、ARMOEA,实验取自DTLZ 测试集和WFG 测试集以及IDTLZ1、IDTLZ2.接下来首先介绍实验设置,然后对测试集中具有规则PF 的测试问题的实验结果和算法对比进行分析,之后对测试集中具有不规则PF 的测试问题的实验结果和算法对比进行分析,最后对比同样采用参考点自适应方法的算法AR-MOEA 和MaOEA-IAR 的运行时间,进一步增加算法性能的说服力.除此之外,为了说明参考点自适应策略的有效性,对比AR-MOEA 与MaOEA-IAR 在MaF 测试集上的性能.

3.1 实验设置

1)基准测试问题:本文采用DTLZ 测试集中的测试问题DTLZ1～DTLZ7 和WFG 测试集中的测试问题WFG1～WFG9 以及IDTLZ1、IDTLZ2,这些测试问题的目标数目可以任意扩展,实验重点研究目标数为5、10、15、25 的测试问题,表1 给出了每个测试问题的真实PF 形状以及不同目标数目下各个测试问题对应的决策变量数.

表1 测试问题Table 1 Test questions

2)种群规模:对比算法MOEA-DD、NSGA-III、RVEA、MOMBI-II、AR-MOEA 与MaOEA-IAR的种群规模取决于参考向量的数量,参考向量的数量由外层和内层的划分数目H1、H2决定,表2 总结了不同目标数目下对应的种群规模.

表2 不同目标对应的种群规模Table 2 Population sizes corresponding to different objectives

3)交叉和变异算子:在本文用到的所有进化算法均采用二进制交叉[37]和多项式变异[38]生成子代,交叉概率和变异概率设置为1.0 和1/D(决策变量数目),分布指标都设置为20.

4)终止条件:每一次运行的终止条件是最大评价次数,评价次数为进化代数与种群规模的乘积,对于不同的目标数目所采用的进化代数不同,具体的设置如表3 所示.

表3 不同目标对应的终止条件Table 3 Termination conditions corresponding to different objectives

5)评价指标:算法性能由IGD 指标[22]和PD指标[34]评估.IGD 指标为同时衡量种群收敛性和多样性的指标,在IGD 指标计算中,对于每个测试实例,利用Das 和Dennis 在[39]中提出的方法(在10 目标、15 目标和25 目标测试问题中,采用双层参考点采用方法)在PF 上采样大约5000 个均匀分布的参考点,计算距离每个参考点最近的解与参考点之间的欧氏距离的平均值;为了进一步证明本文提出的方法在生成均匀参考点方面的有效性,采用PD 指标单独衡量种群的多样性,PD 指标利用Lp标准距离计算解的差异,通过种群中解的差异性的累加衡量多样性.

6)统计方法:每个算法在每个测试问题上独立运行30 次,采用Wilcoxon 秩和检验方法比较本文提出算法与现存算法之间的性能,均值分析的显著性水平设置为0.05.

7)对比算法参数设置:对于MOEA-DD,选择局部父代概率δ设置为0.9;对于RVEA,控制惩罚概率参数α设置为2,参考向量自适应的频率fr设置为0.1;对于MOMBI-II,差异门限α设置为0.5,公差门限ε设置为0.001,最小向量记录规格设置为5.

3.2 算法在规则PF 测试问题上的对比分析

根据表4 的数据分析,在具有规则PF 的测试问题中,虽然MaOEA-IAR 没有在所有的测试问题上获得最好的性能,但总体性能良好.DTLZ1 为线性PF,AR-MOEA 在该测试问题上指标值突出,这与AR-MOEA 采用的参考点更新方法有关,在线性PF 上,初始均匀分布的参考点不会被档案中的候选解更新;DTLZ2 为凹型PF,MaOEA-IAR 在5 目标和25 目标上获得最好性能,AR-MOEA 在其余目标上获得最好性能;DTLZ3 为凹型PF,该测试问题测试算法能否收敛到Pareto 全局最优,在该测试问题中,AR-MOEA 表现最好;DTLZ4 依然为凹型PF,测试当PF 高度偏向的情况下算法能否确保最优解均匀分布,从表中可观察到MaOEA-IAR 在10 目标、15 目标和25 目标上获得最优性能,说明该算法在保持解均匀分布的能力上优于其他算法;WFG4～WFG9 为凹型PF,且与现实优化问题相似,在此类测试问题上,MaOEA-IAR 在大部分测试问题上能够获得最好性能,这是由于基于PF 形状的多样性评估准则能够准确地评估解之间的多样性.综合统计结果,在具有规则PF 的测试问题中,虽然MaOEA-IAR 没有在每一个测试问题上获得最好的性能,但总体性能良好,尤其在WFG测试问题中的性能显著.

表4 MOEA-DD、NSGA-III、RVEA、MOMBI-II、AR-MOEA 以及MaOEA-IAR 在DTLZ1～DTLZ4,WFG4～WFG9上获得IGD 值的统一结果(均值和标准差).最好的结果已被标记Table 4 The statistical results (mean and standard deviation) of the IGD values obtained by MOEA-DD、NSGA-III、RVEA、MOMBI-II、AR-MOEA and MaOEA-IAR on DTLZ1～DTLZ4,WFG4～WFG9.The best results are highlighted

表4 MOEA-DD、NSGA-III、RVEA、MOMBI-II、AR-MOEA 以及MaOEA-IAR 在DTLZ1～DTLZ4,WFG4～WFG9 上获得IGD 值的统一结果(均值和标准差).最好的结果已被标记 (续表)Table 4 The statistical results (mean and standard deviation) of the IGD values obtained by MOEA-DD、NSGA-III、RVEA、MOMBI-II、AR-MOEA and MaOEA-IAR on DTLZ1～DTLZ4,WFG4～WFG9.The best results are highlighted(continued table)

根据表5 的数据分析,在多样性方面,本文提出的算法能在大部分问题中表现良好,尤其是在高维空间中,MaOEA-IAR 相较于其他算法而言性能显著.MOEA-DD 在25 目标的DTLZ1 和10 目标的DTLZ4 上面获得最好性能;NSGA-III 在5 目标和25 目标的DTLZ3 上获得最好性能;MaOEAIAR 在剩余的所有目标的测试问题中获得最好性能.可以看出在高维空间中,本文提出的自适应参考点方法所生成的参考点多样性好,相应的种群多样性也有一定提升.

表5 MOEA-DD、NSGA-III、RVEA、MOMBI-II、AR-MOEA 以及MaOEA-IAR 在DTLZ1～DTLZ4,WFG4～WFG9上获得PD 值的统一结果(均值和标准差).最好的结果已被标记Table 5 The statistical results (mean and standard deviation) of the PD values obtained by MOEA-DD、NSGA-III、RVEA、MOMBI-II、AR-MOEA and MaOEA-IAR on DTLZ1～DTLZ4,WFG4～WFG9.The best results are highlighted

表5 MOEA-DD、NSGA-III、RVEA、MOMBI-II、AR-MOEA 以及MaOEA-IAR 在DTLZ1～DTLZ4,WFG4～WFG9 上获得PD 值的统一结果(均值和标准差).最好的结果已被标记 (续表)Table 5 The statistical results (mean and standard deviation) of the PD values obtained by MOEA-DD、NSGA-III、RVEA、MOMBI-II、AR-MOEA and MaOEA-IAR on DTLZ1～DTLZ4,WFG4～WFG9.The best results are highlighted(continued table)

为了更直观地对比各个算法,图5 为6 个算法在10 目标WFG5 上获得的非支配解的分布情况,在平行坐标系中,可以从收敛性、覆盖性、均匀性和扩展性4 个方面来衡量种群质量[40].从图5 可知6个算法都达到PF 的范围,无法准确地评估种群的收敛性;MOEA-DD、NSGA-III、RVEA、ARMOEA、MaOEA-IAR 的覆盖率较好,MOMBI-II在1～7 目标轴上严重缺失解集,覆盖率差;在均匀性方面,6 个算法的平行坐标系下的折线都分布不均匀,这并不意味着生成的种群不均匀,因此在平行坐标系下无法比较种群的均匀性;最后可以观察到6 个算法目标值范围均为0～18,可扩展性较好.图6 为6 个算法在5、10、15、25 目标的DTLZ4 上获得的IGD 指标轨迹,从图中观察到算法MaOEAIAR 在5 目标时与其他算法的性能相似,随着目标数目的增加,MaOEA-IAR 能够较快收敛到一个稳定且较低的IGD 指标值.

图5 WFG5 问题10 目标上获得的非支配解Fig.5 Nondominated solutions obtained on 10-objective WFG5

图6 5、10、15、25 目标DTLZ4 问题上的IGD 进化轨迹Fig.6 Evolutionary trajectories of IGD on 5、10、15、25-objective DTLZ4

3.3 算法在不规则PF 测试问题上的对比分析

根据表6 的数据分析结果,在具有不规则PF的测试问题中,虽然MaOEA-IAR 没有在所有的测试问题获得最好的性能,但总体上性能良好.DTLZ5～DTLZ6 为退化PF,此类测试问题测试进化算法收敛到Pareto 最优曲线上的能力,从表中可观察到,MaOEA-IAR 在5 目标、15 目标、25 目标的DTLZ5 和25 目标的DTLZ6 上获得最好性能,MOEA-DD 在5 目标的DTLZ6 上获得最好性能,AR-MOEA 在其余目标上获得最好性能,因此MaOEA-IAR 虽然不能在所有目标的测试问题上得到最优性能,但与其他算法相比,该算法在处理具有退化PF 的问题时依然能够得到较好的性能,同时为了更直观地反应种群的分布情况,图7 描绘了各个算法在3 目标DTLZ5 上获得的非支配解的分布情况,从图中可观察到MaOEA-IAR 能够生成一组均匀且分布广泛的种群;DTLZ7 为断开PF,该测试问题测试算法在不同Pareto 最优区域保持子种群的能力,可观察到AR-MOEA 能够在5 目标、10 目标和15 目标上获得最好的性能,RVEA在25 目标上获得最好性能,但与剩余算法相比,MaOEA-IAR 在不同区域保持子种群的能力更强;IDTLZ1～IDTLZ2 为翻转PF,AR-MOEA 在5 目标的IDTLZ1 上获得最好性能,MaOEA-IAR 在其余测试问题上获得最好性能,因此对于翻转的优化问题,PF 形状监测基础上的自适应参考点方法依然能发挥较好的作用;WFG1～WFG3 分别为混合、断开、退化PF,MaOEA-IAR 在大部分测试问题上获得最好性能,图8 描绘了各个算法在15 目标WFG1上获得的非支配解的分布情况,从图中可观察到本文提出的算法在覆盖率和均匀性方面均优于其他算法.综合统计结果,在具有不规则PF 的测试问题中,虽然MaOEA-IAR 没有在每一个测试问题上获得最好的性能,但总体性能良好;这是由于在不规则的PF 上,根据种群的分布生成参考点,在没有个体分布的区域不设置参考点,避免在无效区域产生下一代种群.

图7 DTLZ5 问题3 目标上获得的非支配解Fig.7 Nondominated solutions obtained on 3-objective DTLZ5

图8 WFG1 问题15 目标上获得的非支配解Fig.8 Nondominated solutions obtained on 15-objective WFG1

表6 MOEA-DD、NSGA-III、RVEA、MOMBI-II、AR-MOEA 以及MaOEA-IAR 在DTLZ5～DTLZ7,IDTLZ1～IDTLZ2,WFG1～WFG3 上获得IGD 值的统一结果(均值和标准差).最好的结果已被标记Table 6 The statistical results (mean and standard deviation) of the IGD values obtained by MOEA-DD、NSGA-III、RVEA、MOMBI-II、AR-MOEA and MaOEA-IAR on DTLZ5～DTLZ7,IDTLZ1～IDTLZ2,WFG1～WFG3.The best results are highlighted

表6 MOEA-DD、NSGA-III、RVEA、MOMBI-II、AR-MOEA 以及MaOEA-IAR 在DTLZ5～DTLZ7,IDTLZ1～IDTLZ2,WFG1～WFG3 上获得IGD 值的统一结果(均值和标准差).最好的结果已被标记 (续表)Table 6 The statistical results (mean and standard deviation) of the IGD values obtained by MOEA-DD、NSGA-III、RVEA、MOMBI-II、AR-MOEA and MaOEA-IAR on DTLZ5～DTLZ7,IDTLZ1～IDTLZ2,WFG1～WFG3.The best results are highlighted (continued table)

根据表7 的数据分析,相对于具有规则PF 的测试问题,在不规则PF 的测试问题中,本文提出的算法在多样性方面性能稍逊,但依然能在大部分问题中保持较好的性能.MOEA-DD 在5 目标和15 目标上的WFG1 上获得最好性能;NSGA-III在5 目标的DTLZ6,10 目标和25 目标的WFG1上以及15 目标和25 目标的WFG3 上获得最好性能;AR-MOEA 在5 目标的DTLZ5 和DTLZ7 上获得最好性能;其余各个目标下的测试问题上,MaOEA-IAR 算法获得最好性能.这在一定程度上证明了利用PF 形状自适应参考点能够有效地提升算法的多样性.

表7 MOEA-DD、NSGA-III、RVEA、MOMBI-II、AR-MOEA 以及MaOEA-IAR 在DTLZ5～DTLZ7,IDTLZ1～IDTLZ2,WFG1～WFG3 上获得PD 值的统一结果(均值和标准差).最好的结果已被标记Table 7 The statistical results (mean and standard deviation) of the PD values obtained by MOEA-DD、NSGA-III、RVEA、MOMBI-II、AR-MOEA and MaOEA-IAR on DTLZ5～DTLZ7,IDTLZ1～IDTLZ2,WFG1～WFG3.The best results are highlighted

表7 MOEA-DD、NSGA-III、RVEA、MOMBI-II、AR-MOEA 以及MaOEA-IAR 在DTLZ5～DTLZ7,IDTLZ1～IDTLZ2,WFG1～WFG3 上获得PD 值的统一结果(均值和标准差).最好的结果已被标记 (续表)Table 7 The statistical results (mean and standard deviation) of the PD values obtained by MOEA-DD、NSGA-III、RVEA、MOMBI-II、AR-MOEA and MaOEA-IAR on DTLZ5～DTLZ7,IDTLZ1～IDTLZ2,WFG1～WFG3.The best results are highlighted (continued table)

3.4 算法的运行时间分析

为了增加实验结果的说服力,对算法的运行时间进行对比.由于参考点自适应策略较为耗费时间,与传统算法进行时间上的对比无太大意义,因此本节将同样利用参考点自适应策略的算法AR-MOEA与MaOEA-IAR 进行对比.从表8 中可以观察到,MaOEA-IAR 在大部分的测试问题中能在较短的时间内完成种群的进化,即在更短的时间内得到质量更好的种群,算法的性能较为优越.

表8 AR-MOEA 和MaOEA-IAR 在DTLZ1～DTLZ7,IDTLZ1～IDTLZ2,WFG1～WFG9 上运行时间的统一结果(均值).最好的结果已被标记Table 8 The statistical results (mean) of the time obtained by AR-MOEA and MaOEA-IAR on DTLZ1～DTLZ7,IDTLZ1～IDTLZ2,WFG1～WFG9.The best results are highlighted

3.5 参考点自适应策略的有效性分析

在本节中,为了验证参考点自适应策略的有效性,对比AR-MOEA 与MaOEA-IAR 在测试问题MaF1～MaF7 上的性能.AR-MOEA 与MaOEAIAR 都采用了参考点自适应策略增加参考点的多样性,并且在环境选择中都利用IGD-NS 指标计算适应度值并将其作为选择标准;MaF 测试集中包含更多类型的优化问题,并且增加了具有凹型PF 的优化问题,这一类优化问题对生成参考点的策略要求更高.表9 为算法独立运行30 次的IGD 指标值,其余设置与上述实验设置相同.从表中的数据可以观察到MaOEA-IAR 在10 目标的MaF6 和5 目标的MaF7 上未能获得最好性能,在其余测试问题上获得最好性能,算法中使用到的参考点自适应策略适用于各种形状的优化问题.

表9 AR-MOEA 和MaOEA-IAR 在MaF1～MaF7 上获得IGD 值的统一结果(均值和标准差).最好的结果已被标记Table 9 The statistical results (mean and standard deviation) of the IGD values obtained by AR-MOEA and MaOEAIAR on MaF1～MaF7.The best results are highlighted

3.6 邻域参数r 的分析和讨论

邻域参数在算法中起着重要作用,但由于该参数为用户预先定义参数,虽然在参考点自适应策略中描述了如何调整参数,其初始值却较难确定;因此在本节将算法中的邻域参数r的初始值分别设置为5,7,9,11,13,对比不同取值下算法在测试问题DTLZ1、DTLZ5、IDTLZ1、WFG1、WFG2、WFG4 上获得的IGD 指标值.从表10 中可观察到在大部分的目标下,当r取值为9 时能获得最好的指标值;在25 目标的DTLZ1 和10 目标、25 目标的WFG4上,虽然算法在r为11 时获得最好性能,但r为9 时的性能与最好性能相似;因此,将9 作为邻域参数r的初始值.

表10 不同参数下算法MaOEA-IAR 的性能Table 10 Performance of MaOEA-IAR under different parameters

4 总结

为了改善参考点的适应能力,提高算法在处理具有不同PF 形状的优化问题上的通用性,本文提出参考点自适应调整下评价指标驱动的高维多目标进化算法(MaOEA-IAR),该算法设计一个PF 形状监测基础上的自适应参考点方法,通过种群分布状态以轮廓曲线近似PF,结合曲线参数生成一组多样性好的参考点;同时在匹配选择中利用Pareto支配以及改进的Pareto 支配选择一组有希望的父代种群;两者结合共同指导种群进化.

实验证明本文提出的算法在处理各种PF 的MaOPs 时能获得较好的性能,同时在增强种群多样性方面效果明显;然而在判断PF 形状时,由于某些测试问题不是纯粹的线性、凹型或凸型,因此对于这样的测试问题可能会出现PF 形状判断错误的情况,这在一定程度上对结果造成偏差,因此下一步的工作计划是继续优化判断PF 形状的方法,增强算法在处理复杂PF 问题时的性能.