第5章 基于分解的多目标演化 算法中的变化算子 5.前言 1 .................... 本章将实验研究基于分解的MOEAs 中的变化算子在高维多目标优化中对算法性能 的影响。动机来源于两方面:第一,基于分解的MOEAs在高维多目标优化方面的最新 进展[39,45]表明这类技术在高维多目标优化中应该引起足够的重视。然而,绝大部分与这 方面相关的研究均采用传统的遗传算子来产生子代解,这为在其中探究其他可用的变化 算子,如DE[22],留下了研究空间。第二,若干最近的研究[87,90,91]已经表明,当处理高维目 标时,应该更加仔细地解决如何在决策空间执行有效搜索的问题。可是,众所周知,对于 一些复杂的问题,单纯的遗传算子一般很难在决策空间中实现开发和探索的平衡。鉴于 上述两个方面,探究其他变化算子如何和以何种程度影响基于分解的高维多目标算法在 MaOPs上的性能,是非常有意义和有必要的。为了这个目的,本章关注这类技术中的一 个代表性算法,即NSGA-Ⅲ[45],研究若干种变化算子对其搜索性能的影响。本章的主要 贡献反映在如下几方面。 (1)据我们所知,这是首次将DE 算子引入最近提出的NSGA-Ⅲ中,并形成了一个新 的NSGA-Ⅲ变体,即NSGA-Ⅲ-DE 。另外,本章也探究了两个主要控制参数对NSGA DE 性能的影响。Ⅲ- (2)基于对NSGA-Ⅲ和NSGA-Ⅲ-DE 搜索行为的实验分析,本章提出了带有新的再 生机制的其他两种NSGA-Ⅲ变体,即NSGA-Ⅲ-2S 和NSGA-Ⅲ-HVO,二者较NSGA-Ⅲ 和NSGA-Ⅲ-DE 均有显著的性能提升。 (3)因为NSGA-Ⅲ的作者并没有公开他们的源代码,原始的NSGA-Ⅲ文献[49]也并 没有完全给出其归一化过程的细节,所以要实现NSGA-Ⅲ且得到与原文献中相似的结果 并不简单。Chiang[132]提供了NSGA-Ⅲ的一个C++实现,但是该程序在目标数目为8或 者更高的问题上表现非常差。作为本章的辅助材料,作者公开了自研的NSGA-Ⅲ实现源 码,该程序似乎在大多数情形下与原作者的实现有着相似的性能。 本章后续由如下部分组成:5.3节给 2节描述了本章实验中将要研究的目标算法;5. 智能演化优化 出了大量的实验结果以及相关讨论;最后,4节对本章工作进行了小结。 5. 5.目标算法 2 ........................ 原始的NSGA-Ⅲ使用模拟两点交叉(SBX)和多项式变异[92]来产生子代个体。本章 之后称它为NSGA-Ⅲ-SBX以显著区分于本章中所考虑的其他NSGA-Ⅲ变体,即 NSGA-Ⅲ-DE 、NSGA-Ⅲ-2S和NSGA-Ⅲ-HVO 。 NSGA-Ⅲ-DE使用DE算子替换NSGA-Ⅲ-SBX中的SBX算子,这也是二者唯一的 不同之处,DE算子的细节参见2.-1描述了NSGA-Ⅲ 2节。算法5DE如何通过当前种群 P 生成子代种群Q。 算法5- 1 NSGA-Ⅲ-DE中的再生机制 1:P←{X1, G ,X2, G ,…,XN , G } 2:Q←. 3:fori←1toN do 4: Ui, G ←DEOperator(Xi, G ) 5: Yi, G ←PolynomialMutation(Ui, G ) 6: Q←Q∪Yi, G 7:endfor 8:returnQ NSGA-Ⅲ-2S是一个两步的算法,它简单地结合了NSGA-Ⅲ-SBX和NSGA-Ⅲ-DE 。 在NSGA-Ⅲ-2S中,NSGA-Ⅲ-DE首先运行,在运行至最大代数的一半时,转而运行 NSGA-Ⅲ-SBX 。NSGA-Ⅲ-HVO使用了一种随机策略混合了三种不同的变化算子,即 SBX 、DE和多项式变异。当要生成一个子代解时,它从三个算子中随机选择一个算子。 算法5-2描述了NSGA-Ⅲ-HVO如何利用当前种群 P 生成子代种群Q。需要进一步解 释的是,在步骤6中,首先需要随机选择一个整数ri ∈[1, N ]且ri ≠i,然后再对Xi, G 和 Xri, G 执行SBX 。 算法5- 2 NSGA-Ⅲ-HVO中的再生机制 1:P←{X1, G ,X2, G ,…,XN , G } 2:Q←. 3:fori←1toN do 4: 随机选择一个整数k∈[1,3] 5: ifk=1then 6: Yi, G ←SBXCrosover(Xi, G ) 7: elseifk=2then 98 第 5 章基于分解的多目标演化算法中的变化算子 8: Yi, G ←DEOperator(Xi, G ) 9: else 10: Yi, G ←PolynomialMutation(Xi, G ) 11: endif 12: Q←Q∪Yi, G 13:endfor 14:returnQ 注意,鉴于篇幅原因,本章中只关注NSGA-Ⅲ和它的变体,但是类似的实验发现和结 论也可以基于NSGA-Ⅲ的改进算法θ-DEA 得到。 5.实验研究 3 ........................ 5.1 实验设置 3. 为了测试所考虑的算法,本章实验中采用两组测试问题。第一组问题均是归一化问 题,包括DTLZ1~4[105]。第二组问题包含三个非归一化问题,它们是SDTLZ1~2[45]和 WFG6[106]。所有这些问题的目标数目设置、决策变量数目设置、SDTLZ1~2的比例因子 3. 设置完全与4.1节相同。注意,除了WFG6 问题,其他问题的设置与原始NSGAⅢ研 究[45]也是一致的。 IGD) 45] 为了评价目标算法,我们采用反转世代距离(作为性能指标,并使用文献[中 建议的方法计算IGD 值。IGD 能够同时衡量一个解集的收敛性和多样性,且较小的值意 味着越佳的性能。 对于参数设置,针对不同的实例,每个所考虑的算法采用与原始NSGA-Ⅲ研究[45]中 相同的种群大小和最大迭代次数(MaxG设置。三种变化算子所使用的参数如表5. en) 1 所示。5.2节也将研究参数 F 和Cr对NSGADE 性能的影响。 3.-Ⅲ 表5.变化算子的参数设置 1 变化算子参数名称参数值 SBX 交叉概率(pc ) 1.0 交叉中的分布指数(ηc ) 30 DE 缩放因子(F) 0.5 交叉概率(Cr) 0.1 99 智能演化优化 续表 变化算子参数名称参数值 多项式变异 变异概率(pm ) 1/ n 变异中的分布指数(ηm ) 20 所有的算法都实现在jMeta[127]框架下,且每个算法对每个测试实例均独立运行20 次。 5.2 NSGAⅢ-DE 中参数的影响 3. 在NSGA-Ⅲ-DE 中,有两个典型的控制参数 F 和Cr。本节主要研究这两个参数对 NSGA-Ⅲ-DE 性能的影响。为了说明问题,使用具有5、8、10 和15 目标的DTLZ1 、 DTLZ3 、SDTLZ2 和WFG6 问题。 为了检验F的影响,将C1, 1在区间[4,0] 1 r固定为0.且以步长0.0.1.中变化F。图5. 显示了NSGA-Ⅲ-DE 随参数 F 的性能变化,这里的性能用所得IGD 的中值来体现。由 图5.1可见,在DTLZ1 、DTLZ3 和SDTLZ2 问题上, F 对NSGA-Ⅲ-DE 的性能施加了类 似的影响。具体来说,在这三个问题上,但是除了在5目标 IGD 值随着 F 的变化而波动, DTLZ1 实例上,波动幅度均很小。对于WFG6 问题,在5、IGD 随着 8和10 目标实例上, F的增大而缓慢增长,但是在15 目标实例上, IGD 值却呈现波动的趋势。 至于Cr, 1且Cr∈[1] 其中,5。图5. 进一步研究步长为0.0,的情形, F 被固定为0.2 显示了Cr对NSGA-Ⅲ-DE 所得IGD 中值的影响。由图5.在DTLZ1 、DTLZ3 和 2可见, SDTLZ2 问题上,Cr对NSGA-Ⅲ-DE 的性能影响很大,且从整体上来看,随着Cr的增 加,IGD 的变化趋势基本上与其他三个问题一致, IGD 值剧烈增长。对于WFG6 问题,但 是变化范围小很多。 图5.1在不同目标数m的情形下,参数F(Cr=0.1)对NSGA-Ⅲ-DE 所得IGD值(20次独立运行所得结果的中值)的影响 100 第 5 章基于分解的多目标演化算法中的变化算子 图5.(续) 1 图5.在不同目标数 m 的情形下,参数Cr(5)对NSGA 2 F=0.-Ⅲ-DE 所得IGD 值(20 次独立运行所得结果的中值)的影响 总之,对 F 和Cr的影响,我们能得到如下一些有意义的见解。在大多数所考虑的实 例上,DE 一般能在 F 的较大变化范围内取得相对稳定的性能,且F=5在大 101 NSGA-Ⅲ-0. 智能演化优化 102 多数情况下是一个很好的选择。相对于F,NSGA-Ⅲ-DE的性能对于Cr的变化会更加 敏感。根据实验结果,推荐使用较小的Cr值,即Cr∈[0,0.1],较大的Cr值经常会导致 特别差的性能。回顾前文可知,Cr其实控制了期望个体中平均有多少变量发生改变。因 此,这意味着当子代个体继承父代个体大多数信息时,NSGA-Ⅲ-DE 能够获得较好的性 能。有趣的是,文献[90]中也有类似的实验发现:对于高维多目标0/1背包问题,当产生 子代解时,在两个父代解之间只交换少量的基因可以提高算法性能。 5.3.3 NSGA-Ⅲ-DE、NSGA-Ⅲ-SBX:探索与开发 本节将在高维多目标问题上比较NSGA-Ⅲ-DE和NSGA-Ⅲ-SBX的搜索行为。具体来 说,我们想了解在搜索空间中,哪个算法更擅长于探索,哪个算法更擅长于开发。理解了这 一点将有助于我们设计更加有效的变化算子。注意,这里并不将这两个算法在不同问题实 例上做一个详细的性能比较,这将在5.3.4节中进行。为了检测NSGA-Ⅲ-DE和NSGA-Ⅲ- SBX的探索能力,这里以5目标DTLZ2为例。首先,为该实例随机产生一个种群。然后, NSGA-Ⅲ-DE和NSGA-Ⅲ-SBX均将该种群作为初始种群,并执行一定数目的代数。图5.3 绘出了NSGA-Ⅲ-DE和NSGA-Ⅲ-SBX所得IGD值随着代数增长的变化轨迹。从图5.3中 可以看出,在初始的进化过程中,这两个算法以类似的方式减小IGD值,但是NSGA-Ⅲ-DE 在大约40代后,成功找到了更好的IGD值。这个现象诠释了,通过在决策空间中随机分布 的解,NSGA-Ⅲ-DE能够比NSGA-Ⅲ-SBX更快地确定有希望的搜索区域。图5.4进一步分 别绘出了NSGA-Ⅲ-DE和NSGA-Ⅲ-SBX在MaxGen/2=135代之后所得种群的决策变量值 的平行坐标。因为5目标DTLZ2的Pareto最优解集是: xj = [0,1],j=1,2,3,4 0.5 j=5,6,…,14 { (5.1) 可以从图5.4中清晰地看出,在进化过程早期,NSGA-Ⅲ-DE 可以更快地收敛到 Pareto最优解集上。上述实验发现表明,相比于NSGA-Ⅲ-SBX,NSGA-Ⅲ-DE可以对搜 索空间进行更加有效的探索。 为了研究算法的开发能力,进一步再做一个类似的实验,但是初始种群是一个已经比较 接近Pareto前沿面的种群,该种群可以通过任何一个高维多目标演化算法得到。在这个初 始种群上,分别执行NSGA-Ⅲ-DE和NSGA-Ⅲ-SBX,图5.5中描述了IGD随代数变化的进 化轨迹。可以看出,图5.5中的情形与图5.3有着很大的不同。在该情形下,从开始阶段起, NSGA-Ⅲ-SBX就能够比NSGA-Ⅲ-DE更快地随代数推移而降低IGD值。因为初始种群本 身是一个精英种群,所以NSGA-Ⅲ-SBX相比于NSGA-Ⅲ-DE能够更好地进一步精练质量较 高的解,从而显示了NSGA-Ⅲ-DE在搜索空间进行开发方面的优越性。 许多研究显示,采用先开发再探索的策略可以在开发之前从搜索空间中抽取必要的 第 5 章基于分解的多目标演化算法中的变化算子 图5.当初始种群为随机产生的种群时,在5目 3 NSGA-Ⅲ-DE(NSGA-Ⅲ-SBX) 标DTLZ2 实例上所得IGD 值随代数的进化轨迹 图5.对于5目标DTLZ2,在相同的随机产生的初始种群上,DE 和NSGA 4 NSGA-Ⅲ--Ⅲ-SBX 运行135 代后所得种群的决策变量值的平行坐标 图5.当初始种群为目标空间中接近Po前沿面的种群时, 5 aretNSGA-Ⅲ-DE(NSGA-Ⅲ-SBX) 在5目标DTLZ2 实例上所得IGD 值随代数的进化轨迹 103 智能演化优化 信息,从而如果首先执行NSGA-Ⅲ-DE 然后执行NSGA-Ⅲ-SBX,可以期望获得更好的性 能,这也正是开发NSGA-Ⅲ-2S 的动机。另外,既然NSGA-SBX 和NSGA-Ⅲ-DE 显示了 互补的优势,很自然地可以综合三种不同算子的效果从而增强搜索的性能,这是NSGAⅢ-HVO 的主要目的。之后,将进一步验证NSGA-Ⅲ-2S 和NSGA-Ⅲ-HVO 的有效性。 5.4 NSGAⅢ变体之间的比较 3. 本节将在全部两组问题上测试所有的目标算法。表5. 2显示了在归一化问题上的比 较结果,而表5.本章中的 3则显示了在非归一化问题上的比较结果。正如前面所提及的, NSGA-Ⅲ-SBX 是NSGA-Ⅲ的一个“非官方”的实现,所以也列出了原始NSGA-Ⅲ论 文[45]中的结果作为比较。注意,在文献[45]中,尽管NSGA-Ⅲ也在WFG6 问题上进行了 测试,但是作者并没有指明该问题所采用的变量的数目。因此,这里并不使用原始 NSGA-Ⅲ在WFG6 上的结果。下面将详细描述本节所得比较结果。 表5.Ⅲ变体在归一化测试问题上所得IGD 的最好值、中值和最差值 2 NSGA (最优的结果以粗体标记) 104 问题mNSGA-Ⅲ.NSGA-Ⅲ-SBXNSGA-Ⅲ-DENSGA-Ⅲ-2SNSGA-Ⅲ-HVODTLZ1 3 4.880E-04 8.901E-04 5.639E-04 2.091E-04 8.715E-051.308E-03 2.186E-03 6.893E-04 2.822E-04 1.406E-044.880E-03 2.070E-02 9.174E-04 5.693E-048.024E-04 5 5.116E-04 7.601E-04 2.513E-04 2.843E-04 5.560E-059.799E-04 1.991E-03 3.767E-04 3.416E-04 8.053E-051.979E-03 4.493E-02 4.630E-04 9.292E-04 1.047E-048 2.044E-03 3.386E-03 2.478E-03 1.730E-03 9.321E-043.979E-03 4.704E-03 2.985E-03 2.150E-03 1.314E-038.721E-03 1.175E-02 3.395E-03 3.098E-03 2.557E-0310 2.215E-03 2.867E-03 2.245E-03 1.733E-03 1.023E-033.462E-03 4.488E-03 2.623E-03 2.158E-03 1.137E-036.869E-03 2.343E-02 4.027E-03 3.742E-03 3.394E-0315 2.649E-03 2.849E-03 1.667E-03 1.246E-03 5.448E-045.063E-03 5.769E-03 1.972E-03 2.019E-03 8.728E-041.123E-023.275E-02 2.063E-02 3.645E-02 3.733E-02 第 5 章基于分解的多目标演化算法中的变化算子 续表 问题mNSGA-Ⅲ.NSGA-Ⅲ-SBXNSGA-Ⅲ-DENSGA-Ⅲ-2SNSGA-Ⅲ-HVODTLZ2 3 1.262E-03 1.213E-03 3.756E-03 1.099E-031.304E-03 1.357E-032.043E-03 4.354E-03 1.401E-03 1.632E-03 2.114E-03 8.355E-03 4.782E-03 1.892E-032.065E-03 5 4.254E-03 4.752E-03 5.137E-03 2.275E-032.601E-03 4.982E-03 6.415E-03 5.750E-03 2.825E-033.209E-03 5.862E-03 9.040E-03 6.608E-03 3.030E-034.117E-03 8 1.371E-02 1.486E-02 8.245E-03 6.592E-03 5.680E-031.571E-02 1.737E-02 1.009E-02 8.155E-03 7.197E-031.811E-02 2.105E-02 1.222E-02 9.850E-03 9.038E-0310 1.350E-02 1.558E-02 7.727E-03 6.125E-03 4.502E-031.528E-02 1.745E-02 8.527E-03 7.005E-03 5.361E-031.697E-02 2.545E-02 9.491E-03 8.248E-03 6.549E-0315 1.360E-02 1.591E-02 5.457E-03 5.745E-03 3.585E-031.726E-02 1.984E-02 6.587E-03 6.875E-03 4.792E-032.114E-02 2.358E-02 8.683E-03 8.403E-03 6.080E-03DTLZ3 3 9.751E-04 1.203E-03 1.947E-03 2.475E-04 1.207E-044.007E-03 4.809E-03 2.540E-03 2.977E-04 2.511E-046.665E-03 1.714E-02 3.189E-03 3.307E-041.696E-03 5 3.086E-03 4.175E-03 4.150E-03 8.566E-04 4.658E-045.960E-03 8.056E-03 4.702E-03 1.086E-03 5.585E-041.196E-02 2.390E-02 5.715E-03 1.281E-03 7.871E-048 1.244E-02 1.530E-02 1.075E-02 8.474E-03 4.304E-032.375E-02 3.219E-02 1.317E-02 1.115E-02 5.154E-039.649E-02 1.130E-01 1.497E-02 1.607E-02 1.284E-0210 8.849E-03 9.217E-03 7.426E-03 4.892E-03 2.541E-031.188E-02 1.516E-02 8.426E-03 6.140E-03 2.975E-032.083E-02 2.825E-02 9.466E-03 7.790E-03 4.615E-03 105 智能演化优化 续表 问题 m NSGA-Ⅲ . NSGA-Ⅲ-SBX NSGA-Ⅲ-DE NSGA-Ⅲ-2S NSGA-Ⅲ-HVO 1.401E-02 1.689E-02 4.767E-03 4.844E-03 1.993E-03 DTLZ3 15 2.145E-02 4.019E-02 5.799E-03 6.312E-03 3.506E-03 4.195E-02 8.801E-02 1.048E-02 8.108E-03 7.010E-03 2.915E-04 3.815E-04 3.084E-03 3.471E-04 2.716E-04 3 5.970E-04 9.040E-04 3.697E-03 4.156E-04 3.470E-04 4.286E-01 3.704E-03 4.223E-03 6.204E-04 4.414E-04 9.849E-04 6.464E-04 5.076E-03 6.947E-04 6.624E-04 5 1.255E-03 1.099E-03 6.298E-03 9.227E-04 8.746E-04 1.721E-03 1.972E-03 7.422E-03 1.375E-03 1.151E-03 5.079E-03 3.581E-03 1.663E-02 5.026E-03 4.500E-03 DTLZ4 8 7.054E-03 4.844E-03 1.941E-02 6.426E-03 5.315E-03 6.051E-01 5.698E-03 2.128E-02 7.750E-03 6.367E-03 10 5.694E-03 3.834E-03 1.148E-02 5.639E-03 3.925E-03 6.337E-03 4.703E-03 1.434E-02 6.553E-03 4.361E-03 1.076E-01 5.656E-03 1.525E-02 7.492E-03 5.054E-03 15 7.110E-03 5.514E-03 8.543E-03 5.830E-03 3.093E-03 3.431E-01 7.312E-03 1.014E-02 7.367E-03 4.936E-03 1.073E+00 1.053E-02 1.151E-02 1.015E-02 6.651E-03 注:.结果摘自原始的NSGA-Ⅲ 论文[45]。 表5.Ⅲ变体在非归一化测试问题上所得IGD 的最好值、中值和最差值 3 NSGA (最优的结果以粗体标记) 问题 m NSGA-Ⅲ . NSGA-Ⅲ-SBX NSGA-Ⅲ-DE NSGA-Ⅲ-2S NSGA-Ⅲ-HVO 3.853E-04 1.342E-03 9.805E-04 4.629E-04 1.559E-04 SDTLZ1 3 1.214E-03 5.843E-03 1.465E-03 5.899E-04 2.329E-04 1.103E-02 4.925E-02 1.748E-03 8.159E-04 6.576E-04 5 1.099E-03 2.580E-03 3.156E-04 5.353E-04 1.197E-04 106