现实应用中存在各种各样的多目标优化问题(Multi-objective optimization problems, MOPs), 如电能分配^[1]、污水处理控制^[2]、服务质量优化^[3]、车辆路径规划^[4]、软件项目管理^[5]、微电网管理^[6], 等等. 由于MOPs的不同目标函数之间通常相互冲突, MOPs的最优解集不是单一的解而是一组折衷解, 即帕累托最优解集(Pareto optimal set). 虽然一些性能优越的多目标进化算法(Multi-objective evolutionary algorithms, MOEAs), 如NSGA-II^[7], SPEA2^[8]和MOEA-PPF^[9]等能很好的处理MOPs, 但在解决超多目标优化问题(Many-objective optimization problems, MaOPs)时, 上述算法的性能将显著下降. 原因是随着目标函数的增加, 非支配个体在种群中所占的比例将呈指数式增长, 基于帕累托关系的算法会逐渐丧失收敛压力^[10]. 为解决该问题, 学术界从不同角度对超多目标进化算法(Many-objective evolutionary algorithms, MaOEAs) 进行了较广泛的探讨^[11-15], 大致可分为以下四类: 1) 基于放松支配. 该类算法的主要思想是通过扩大支配范围来增强种群往PF方向收敛的压力. 代表性方法有$ \epsilon $支配^[16], $ L $支配^[17]和模糊支配^[18-19]等; 2) 基于指标. 该类算法将个体的指标值作为环境选择的衡量标准, 如IBEA^[20], HypE^[21]和ARMOEA^[22]等; 3) 基于分解. 该类算法将MaOPs分解为多个单目标优化问题(Single-objective optimization problems, SOPs)^[23], 随后在进化框架下同时优化这些SOPs, 如MOEA/D^[24], NSGAIII^[25]和SPEAR^[26]等. 4)混合型. 该类算法采用两种或者两种以上的方法来实现对超多目标问题的优化, 如Two_arch2^[27]和HpaEA^[28]均融合了基于支配和基于指标的方法, SRA^[29]则采用了多指标的策略. 在上述算法中, 基于分解的MaOEAs受到了学术界的高度关注, 该类算法的核心是对参考向量和分解方法的设计.

参考向量主要影响种群在PF上分布的均匀性, 即多样性. 在经典的分解类算法MOEA/D中, 采用一组均匀分布在目标空间上的向量集作为参考向量. 该参考向量在规则PF问题上能取得优越的性能, 但不能很好地处理退化、不连续、凹凸混合等不规则PF问题. 原因在于不规则PF上参考向量的分布不均匀, 进而造成种群在PF上分布不均匀. 针对该问题, 学术界提出了很多对均匀分布的参考向量进行调整的方法, 如CA-MOEA^[30]通过层次聚类方法来调整每代的参考向量, MOEA-AWA^[31]则根据种群中的精英个体来对参考向量进行调整, 类似的调整方法还有g-DBEA^[32]和DDEANS^[33]等. 然而, 由于频繁调整参考向量, 参考向量调整类算法的性能在处理规则PF问题时容易恶化^[34].

分解方法主要影响种群的搜索效率, 即收敛性. 现有研究表明^[35-37], 切比雪夫方法可有效处理各种PF形状的问题但搜索效率很低, 权重求和方法虽然不能处理好非凸PF问题但搜索效率却很高. 为此, Ishibuchi等提出了两种改进方案, 分别为自适应切比雪夫和权重求和方法AS^[37], 同时使用切比雪夫和权重求和方法SS^[38], 以综合切比雪夫和权重求和各自的优势. 此外, Wang等提出了局部权重求和方法LWS^[39], 在综合性能上取得了显著的效果. 但由于LWS加入了局部的思想, 一定程度上降低了权重求和方法的搜索效率.

总体而言, 虽然学术界已对基于分解的MaOEAs进行了较广泛研究, 但该类方法的性能仍存在较大提升空间. 为尽可能不损害权重求和方法搜索效率高的优势, 同时又能处理好各类PF为非凸型的问题, 本文从改进现有分解方法的角度, 提出了一种基于目标空间转换权重求和的超多目标进化算法, 简称NSGAIII-OSTWS. 其中目标空间转换权重求和(Objective space transformation based weighted sum, OSTWS)将各种类型问题的PF转换为凸型曲面, 再利用权重求和方法对问题进行优化. 具体地, 首先利用预估PF的形状计算个体到预估PF的距离; 然后, 根据该距离值将个体映射到目标空间中预估凸型曲面与理想点之间的对应位置; 最后, 采用权重求和函数计算出映射后个体的适应值, 据此实现对问题的优化. 为验证OSTWS的有效性, 本文在NSGAIII框架的基础上, 将OSTWS与现有的7个分解方法在WFG、DTLZ和LSMOP测试问题集上进行了对比, 同时将所提的NSGAIII-OSTWS与9个具有代表性的MaOEAs进行了对比, 实验结果表明NSGAIII-OSTWS具备良好的竞争性能.

本文的内容安排如下. 第1节介绍与本文相关的背景知识. 第2节阐述目标空间转换权重求和方法OSTWS, 以及基于OSTWS的超多目标进化算法NSGAIII-OSTWS. 第3节介绍实验设计、实验结果, 并进行相关讨论. 最后对本文进行总结并指出未来的研究方向.

1.   背景知识

1.1   多目标优化问题

一般来说, 一个MOP的数学定义可表述为:

其中, x是决策空间$ \Omega $中的$ n $维决策向量, $ m $是目标函数的个数, ${\bf{R}}^m$是目标空间. $ F $: $\Omega\to{{\bf{R}}^m}$组成$ m $个目标函数. 目标数$ m $大于3的MOPs也被称为超多目标优化问题, 即MaOPs. 假设x和y是决策空间中的两个不同候选解, x支配y (记为x $ \prec $ y) 当且仅当$\forall i\in \{1,2,\cdots, m \}$, $ f_i $(x)$ \leq f_i $(y)且$\exists i\in \{1,2,\cdots, m \}$, $ f_i $(x)$ < f_i $(y). 如果候选解x不被任何其他解所支配, 则称候选解x为帕累托最优解. 所有帕累托最优解的集合称为帕累托最优解集(Pareto optimal set, PS), 即$PS = \{ {\boldsymbol{x}}{\not{\exists}} \;{\boldsymbol{y}} \in \Omega , $$ {\boldsymbol{x}} \succ {\boldsymbol{y}}\}$. 所有帕累托最优解对应的目标向量构成帕累托最优前沿(Pareto optimal front, PF), 即PF = $ \{ F({\boldsymbol{x}}) | {\boldsymbol{x}} \in PS\} $.

1.2   分解方法

分解方法决定了基于分解的MaOEAs的搜索效率, 对算法的性能有着重要影响. 研究者们设计了许多不同的分解方法, 并在各种MaOPs上展现出了优越的性能. 常见的分解方法有以下三种:

1)权重求和(Weighted sum, WS)法: WS方法通过加权的方式将所有目标组合成一个单一的目标, 其数学定义如下:

其中, $ {\boldsymbol{w}} = [ {\boldsymbol{w}}_1,{\boldsymbol{w}}_2, \cdots ,{\boldsymbol{w}}_m] $为一个参考向量. 在本文中, 满足$ {\boldsymbol{w}}_i>0 $, 并且$\displaystyle \sum\nolimits_{i = 1}^m {({{\boldsymbol{w}}_i}} {)^2} = 1$. 如图1(a)所示, 采用WS方法构造的子问题通过在不同的参考向量w上进行搜索, 可以快速得到一组近似PF点. 在PF为凸的情况下, WS方法能获得一组均匀的PF点, 但在PF为非凸的情况下, 该方法则会丢失PF中的大部分点^[24], 从而严重损失种群的多样性, 即WS方法不能处理好PF为非凸的问题.

图 1  分解方法WS, TCH和PBI在参考向量w上的二维示意图, 其中虚线为等高线

Fig. 1  Illustration of the decomposition methods WS, TCH and PBI on reference vector w, where dashed lines are contour lines

下载: 全尺寸图片 幻灯片

2)切比雪夫(Techebycheff, TCH)法: TCH方法将MaOP转化为一个SOP的数学定义如下:

其中, $ {{\boldsymbol{z}}^*} = [{\boldsymbol{z}}_1^*,{\boldsymbol{z}}_2^*, \cdots ,{\boldsymbol{z}}_m^*] $为理想点. 在实际应用中, 如果$ {\boldsymbol{w}}_i $ = 0, 则将$ 10^{-4} $赋值给$ {\boldsymbol{w}}_i $, 以此来避免除法的不合理情况. 此外, 为进一步提升所获得解集分布的均匀性, 可将式(3)中的1/$ {\boldsymbol{w}}_i $用$ {\boldsymbol{w}}_i $替代^[40]. 图1(b)为TCH方法的二维示意图. 与WS方法相比, TCH方法能处理好任意PF形状的MaOPs. 因此, TCH方法被广泛应用在各种基于分解的算法中^[41-42].

3)基于惩罚的边界交叉(Penalty-based boundary intersection, PBI)法: PBI方法构造子问题的数学定义如下:

其中, $ \theta $($ \theta > 0$) 为一个事先设定的惩罚因子, $ d_1 $为向量$ (F({\boldsymbol{x}})-{{\boldsymbol{z}}^*}) $在权重向量w上的投影长度, $ d_2 $为$ F({\boldsymbol{x}}) $到w的垂直距离. 图1(c)为PBI方法的示意图. 由PBI的定义(式(4))和图1(c)可知, $ \theta $是平衡收敛性(用$ d_1 $衡量)和多样性(用$ d_2 $衡量)的关键性参数. 近来有研究表明^[43-44], 当PBI处理PF为凸的问题时, 较大的$ \theta $可以获得较好的种群分布, 而较小的$ \theta $值有利于种群更好地收敛到PF.

2.   NSGAIII-OSTWS算法

2.1   动机

在基于分解的算法中, 分解方法将MaOP转化为若干个SOPs, 然后在进化框架下以协同的方式优化每个SOPs. 如果没有选择合适的分解方法, 或者使用的分解方法不能很好地将MaOP转化为SOPs, 基于分解的MaOEAs最终获得的种群就有可能无法逼近PF.

目前, 上节介绍的三种分解方法, 即WS、TCH和PBI, 已在基于分解的MaOEAs中被广泛应用. 图1是这三种方法在二维目标空间下的示意图. 每个子图中的等高线将目标空间划分为两个区域, 位于同一条等高线上的解具有相同的质量, 靠近理想点$ {\boldsymbol{z}}^* $区域的解质量则要优于另外一区域. 如图1(a)所示, WS的等高线是一条经过候选解且垂直于参考向量的直线, 其优越区域^[39]占整个区域的1/2. 从图1(b)可以看出, TCH的等高线则为经过候选解和参考向量的两条相互垂直的直线, 其优越区域为$ 1/2^m $, 随着目标函数$ m $的增加, 该值会显著减小. 图1(c)中, PBI的等高线是经过候选解和参考向量的两条相交直线, 它的优越区域由惩罚因子$ \theta $决定. $ \theta $值越大, 则优越区域的面积越小, 通常情况下该区域的面积小于整个区域面积的1/2. 由上述分析可知, WS的优越区域是最大的. 换言之, 采用WS可以更大概率搜索到比目前更优的解, 即收敛速度最快. 然而, 当采用WS处理非凸问题时, PF中的大部分点会被丢失^[24], 从而严重损失种群的多样性^[39]. 综上所述, 相比TCH和PBI而言, WS具有更强的收敛性但却不能处理好非凸问题.

为充分发挥WS搜索效率高的优势, 同时又能处理好各类PF形状为非凸的问题, 研究者们提出了一些WS的改进方法, 如AS^[37]和SS^[38]等. 然而, 这些方法的主要思想仅是利用TCH方法来处理WS不能处理好的凸型PF问题, 并未对WS方法本身进行改进. 最近, Wang等^[39]提出了一种新颖的WS方法, 即局部权重求和方法LWS. 该方法的主要思想是对于每个搜索方向, 只在其相邻解中挑选最优解. LWS方法能够较好处理包括PF非凸在内的各类型PF问题, 但由于LWS在求解最优解时加入了局部的思想, 也在一定程度上降低了WS方法搜索效率高的优势. 为验证该结论, 本文将LWS方法和WS方法分别嵌入到基于分解的算法NSGAIII^[25], 形成算法NSGAIII-WS和NSGAIII-LWS. 图2为这两个算法在PF为凸的测试问题ZDT1^[45]上的最终种群分布图. 其中, 运行次数为20次, 迭代次数为120代, 种群大小为200, 决策变量数的大小参照文献[45]设置, 其它参数与NSGAIII保持一致. 从图2可以看出, NSGAIII-WS算法获得的种群具有更好的收敛性. 为尽可能发挥权重求和方法搜索效率高的优势, 同时又能处理好非凸型PF问题, 本文提出了一种新颖的方法——目标空间转换权重求和方法.

图 2  NSGAIII-WS和NSGAIII-LWS算法在ZDT1上获得的最终种群分布

Fig. 2  The final population distribution obtained by NSGAIII-WS and NSGAIII-LWS algorithm on ZDT1

下载: 全尺寸图片 幻灯片

2.2   目标空间转换权重求和方法

目标空间转换权重求和方法OSTWS的核心思想, 是将各种问题的PF转换为凸型曲面, 并基于该凸型曲面进行求解. OSTWS方法的伪代码如算法1所示.

算法1. OSTWS方法

输入. U (种群), $ N $(种群大小), W (参考向量集), $ C $(曲率)

输出. $ g^{wd} $(个体的适应值)

1)归一化种群U;

2)预估出PF的形状: $ p $ = estimate_PFshape(U);

3) for each x $ \in $ U: /*计算个体转换到凸目标空间中所需的距离值*/

4) ${f_i}^{'}({\boldsymbol{x}}) = \frac{{{f_i}({\boldsymbol{x}})}}{{{{(\sum \nolimits_{u = 1}^m ({{f_u}{{({\boldsymbol{x}})})^p}} )}^{1/p}}}},i = 1,\cdots,m$;

5) ${d_1}({\boldsymbol{x}}) = \sqrt {\sum \nolimits_{u = 1}^m( {{f_u}{{({\boldsymbol{x}}))}^2}} }$;

6) ${d_2}({\boldsymbol{x}}) = \sqrt {\sum \nolimits_{u = 1}^m ({{f_u'}{{({\boldsymbol{x}}))}^2}} }$;

7) $d({\boldsymbol{x}}) = {d_1}({\boldsymbol{x}}) - {d_2}({\boldsymbol{x}})$; /*转换到目标空间中凸曲面与理想点之间的对应位置*/

8) ${f_i''}({\boldsymbol{x}}) = \frac{{{f_i}({\boldsymbol{x}})}}{{{{(\sum \nolimits_{u = 1}^m ({{f_u}{{({\boldsymbol{x}})})^C}} )}^{1/C}}}},i = 1,\cdots,m$;

9) $\mathop {{f_i}}\limits^\sim ({\boldsymbol{x}}) = (1 - d({\boldsymbol{x}})){f_i''}({\boldsymbol{x}})$; /*计算每个个体的适应值*/

10) for each w $ \in $ W:

11) ${{g^{wd}}({\boldsymbol{x}}|{\boldsymbol{w}})} = \sum \nolimits_{u = 1}^m { ({{\boldsymbol{w}}_u}\mathop {{f_u}}\limits^\sim ({\boldsymbol{x}}))}$;

12) end for

13) end for

14) return $ g^{wd} $

首先, 采用NSGAIII^[25]中的归一化策略对种群U进行归一化处理, 然后利用2REA^[46]中的估PF方法预估出PF的形状. 种群归一化的目的是维持种群的多样性. 在进化前期, 由于种群中的大部分个体并未收敛到PF, 归一化会存在较大的误差, 但在进化后期, 大部分个体都已靠近或收敛到PF, 此时种群归一化所带来的误差会逐渐降低. 预估的过程是先选取一组候选曲率$ p $值逐一计算种群中非支配个体到理想点的$ L_{p} $范式值, 并据此计算出各$ p $值所对应的标准方差. 方差越小, 代表该$ p $值所对应的曲面越能拟合当前种群的分布. 最终选取具有最小方差的$ p $值所对应的曲面作为预估的PF形状. 之后, 将种群中的所有个体映射到所预估的PF上, 映射公式如下:

接下来, 以原点作为理想点, 分别计算原始个体与映射个体到理想点之间的欧氏距离值$ d_1({\boldsymbol{x}}) $和$ d_2({\boldsymbol{x}}) $, 并将$ d_1({\boldsymbol{x}}) $减去$ d_2({\boldsymbol{x}}) $, 以此得到目标空间转换所需的距离值$ d({\boldsymbol{x}}) $. 随后, 根据$ d({\boldsymbol{x}}) $值将个体转换到目标空间中凸曲面与理想点之间对应的位置, 从而完成目标空间的转换. 具体的做法是以等距离$ d({\boldsymbol{x}}) $的形式将原始种群中的所有个体映射到预设的凸曲面内. 预设凸曲面的定义如下:

其中, [$ f_1({\boldsymbol{x}}) $, $f_2({\boldsymbol{x}}),\cdots$, $ f_m({\boldsymbol{x}}) $]为预设凸曲面上的一个向量, $ C $为预设凸曲面的曲率值, 种群中个体映射到预设凸曲面内的数学公式如下:

最后, 将最小化求解问题转化为最大化求解问题并采用WS方法计算出目标空间转换后个体的适应值, 适应值越大代表个体越优秀.

为更直观地展示OSTWS方法, 图3示例了使用OSTWS方法将线形、凸形和凹形PF中的个体转换到凸目标空间的整个过程. 以3(a)为例, 首先, 预估出真实PF的形状(直线), 并将种群中的所有个体(a, b, c)映射到直线上(a＇, b＇, c＇), 然后计算出原始个体(a, b, c)与映射后个体(a＇, b＇, c＇)之间的欧氏距离值$ d_1 $, $ d_2 $, $ d_3 $. 值得注意的是, 距离值($ d_1 $, $ d_2 $, $ d_3 $)具有正负之分, 如果原始个体到理想点的欧氏距离大于映射后个体到理想点的欧氏距离, 则上述距离值为正, 否则为负. 接下来, 将原始种群中的所有个体(a, b, c)以等距离$ (d_1 $, $ d_2 $, $ d_3 $) 形式映射到预设凸曲线内, 完成种群到凸目标空间的转换, 转换后的个体为$a'' $, $b'' $, $c'' $. 最后, 采用WS方法逐一计算个体($a'' $, $b'' $, $c'' $) 的适应值, 适应值越大的个体被挑选到下一代进化过程中的概率也越大.

图 3  OSTWS方法将PF形状为线形(a), 凸形(b)和凹形(c)种群中的个体转换到凸目标空间的整个过程

Fig. 3  The whole process of transforming the population individuals from linear (a), convex (b) and concave (c) into convex objective space by OSTWS method

下载: 全尺寸图片 幻灯片

2.3   将OSTWS方法整合到NSGAIII中

在进化算法领域, MOEA/D和NSGAII是两个基于分解的经典算法, NSGAIII则是NSGAII在高维目标空间下的改进版. 相比MOEA/D, NSGAIII专门针对MaOPs, 且在高维空间下能够更好地维持种群的多样性^{[25, 47-48]}. 为公平比较各种分解方法在处理MaOPs时的有效性, 本文选择NSGAIII作为基础算法, 并将OSTWS方法嵌入NSGAIII形成新的算法NSGAIII-OSTWS, 算法2为其伪代码. 首先, 初始化规模为$ N $的种群U和参考向量W, 然后对种群U进化过程, 直至算法达到最大迭代次数.

算法2. NSGAIII-OSTWS算法

输入. $ N $(种群大小), MAXGen (最大迭代次数), $ C $(曲率)

输出. U (种群)

1) 初始化种群U和参考向量集W;

2) for $ g $ = 1 to MAXGen do

3) $ S $ = [], ${U}_p$ = [], $ i $ = 1;

4) $ Q $ = OffspringGeneration (U);

5) $ CR $ = U$ \bigcup $$ Q $;

6) ($ F_1 $, $F_2 ,\cdots$) = NondominatedSort($ CR $);

7) repeat

8) $ S $ = $ S $$ \bigcup $$ F_i $ and $ i $ = $ i $+1;

9) until $ \mid $$ S $$ \mid $$ \geq $$ N $

10) if $ \mid $$ S $$ \mid $ = =$ N $

11) ${U}_p$ = $ S $;

12) else

13) ${U}_p = \cup _{j = 1}^{i - 1}{F_j}$;

14) $ g^{wd} $ = OSTWS($ S $, $ N $, W, $ C $);

15) 根据最大值$ g^{wd} $将种群$ S $中的个体归属至w $(\ w\in $$ W\ ) ,$ 并统计前$ F_{i-1} $层中个体归属至每个w上的个体数量;

16) 通过w归属个体的数量和$ g^{wd} $值从$ F_i $层中选取出$N -$$ \mid $${U}_p$$ \mid $个个体加入至${U}_p$中;

17) end if

18) U = $ {U}_p $;

19) end for

20) return U

在每一代进化过程中, 根据上一代种群进行父代选择(二进制锦标赛^[25])、个体交叉(二进制交叉^[49]) 和变异(多项式变异^[50]), 生成规模为$ N $的子代种群$ Q $. 之后, 合并种群$ Q $和U形成规模为2$ N $的种群$ CR $并对种群$ CR $进行非支配层($ F_1 $, $ F_2 $等)排序^[7]. 接下来将位于前$ i -1$层的个体直接作为下一代种群的个体, 其中$ i $为满足$\displaystyle\sum\nolimits_{j = 1}^i{F_j} \ge N$的最小整数. 若$\displaystyle\sum\nolimits_{j = 1}^i{F_j} > N$, 则再调用OSTWS方法从$ F_i $层中挑选$ N $$-\displaystyle\sum\nolimits_{j = 1}^{i-1}{F_j}$个个体进入下一代种群. 具体地, 首先采用OSTWS方法计算出$ S $中前$ i $层中的个体到所有参考向量的权重求和值($ g^{wd} $), 然后识别出具有最大$ g^{wd} $值的个体的参考向量, 并将该个体归属至该参考向量上; 接下来, 统计前$ F_{i-1} $层中个体归属至每个$ W $上的个体数量; 最后, 在归属数量最少的参考向量上选取出$ F_i $中具有最大$ g^{wd} $值的个体并将该其加入至${U}_p$中, 重复该步骤直至$ \mid $${U}_p$$ \mid $ = $ N $, 最后输出种群U.

2.4   时间复杂度分析

时间复杂度是衡量算法性能的一个重要方面, 影响算法的整体计算开销. 下面根据NSGAIII-OSTWS的主要流程对其时间复杂度进行详细分析. 算法2第4行的子代个体生成中, 二进制交叉和多项式变异需要O($ DN $)的计算开销, 其中$ D $为决策变量的数量. 算法2第6行对规模为2$ N $的种群进行非支配层排序要花费O($ N \log ^{m-2} $$ N $)^[25]的计算代价. 算法2第15行, 即算法1, 其计算开销包括以下四方面: 1)将规模为2$ N $的种群进行归一化(算法1第1行), 需要O($ mN $) 的计算开销. 2)计算出2$ N $个个体到预设曲面的距离(算法1第4~7行), 需要O($ mN $) 的计算开销. 3) 将2$ N $个个体的目标空间转换到特定曲面内(算法1第8~9行), 需要O($ mN $)的计算开销. 4)计算目标空间转换后2$ N $个个体到参考向量W的权重求和值(算法1第10~12行), 需要O($ mN|W| $) 的计算开销, 其中$ |W| $是参考向量的个数. 因此, 算法1的时间复杂度为O($ mN|W| $). 之后, 在最坏情况下NSGAIII-OSTWS需对2$ N $个个体进行参考向量的归属, 此时需要花费O($ mN|W| $) 的计算代价. 最后, NSGAIII-OSTWS需挑选$ N- $$ \mid {U}_p \mid $个个体至下一代进化过程需要O($ L|W| $) 的计算量, 其中$ L $ = $ |F_l| $. 此外, 在通常情况下, $ N \approx |W| $, $ N > m $. 考虑到以上因素和计算结果, NSGAIII-OSTWS的时间复杂度为Max(O($ DN $), O($ mN|W| $)).

3.   实验与分析

3.1   实验设置

1) 测试问题和评价指标

为检验NSGAIII-OSTWS的性能, 本文选取了超多目标优化领域中使用最为广泛的两组测试问题集WFG^[51]、DTLZ^[52]和最新的大规模决策变量测试问题集LSMOP^[53]. 在DTLZ中, DTLZ8-9为带约束的问题, 因此本文只考虑对DTLZ1-7问题的研究. 参照文献[39], WFG和DTLZ中的决策变量数目统一设置为$ D $ = 100, 其中WFG中的位置变量数设为$ k = m -1$. LSMOP的相关参数与原文^[53]保持一致.

为定量评估算法的求解性能, 分别采用世代距离(Generational distance, GD^[54]), 覆盖PF(Coverage over the pareto front, CPF^[55]) 和修正的反转世代距离(Modified inverted generational distance, IGD^+[56]) 进行收敛性、多样性和综合性(平衡收敛性和多样性的能力)性能衡量, 其计算公式分别如下:

其中U为算法输出的最终种群, $ A $为测试问题PF面上的一组均匀参考点. 对于目标维度不相同的缩放问题(如: WFG), 在计算GD和IGD⁺指标之前需对$ A $和U进行归一化处理^[48]. GD和IGD⁺值越小, 代表算法的性能越好. 参照文献[57], 本实验设置计算GD和IGD⁺所需的参考点数为10000.

2) 参数设置

由于分解算法的种群规模取决于参数$ H $和$ m $, 其中$ H $为沿每个目标轴所考虑的分区. 为公平起见, 本章所测试的目标维度及其对应的种群大小统一设置为表1所示. 为避免参考向量分布不均匀的情况, 当$ m >5 $时, 本文采用两层参考向量生成方法生成参考向量^[58]. 交叉和变异操作所需的参数设置如表2所示. 在NSGAIII-OSTWS中, 曲率$ C $值的参数经验设置为2, 其影响在实验分析部分进行研究. 比较算法的其他参数设置与其原始论文保持一致. 所有算法的终止准则被指定为最大迭代次数(MAXGen), 本文中所有测试问题的MAXGen设为300. 每个算法在每个测试问题上独立运行20次. 为检验算法性能的显著性差异, 采用Wilcoxon^[59]秩和检验来评估一种算法在GD或IGD⁺值方面是否优于另一种算法. 符号“+”, “−” 和“≈”表示相应的竞争算法在5%的显著性水平上分别比所提算法NSGAIII-OSTWS更好, 更差和无统计性差异.

表 1  种群大小设置

Table 1  Setting of the population size

目标数 ($ m $)	分割数 ($ H $)	种群大小 ($ N $)
3	12	91
5	6	210
8	3, 2	156
10	3, 2	275

下载: 导出CSV 

| 显示表格

表 2  交叉变异参数设置

Table 2  Parameter settings for crossover and mutation

参数名	参数值
交叉概率 ($ P_c $)	1.0
变异概率 ($ P_m $)	1/$ D $
交叉分布指标 ($ \eta_c $)	20
变异分布指标 ($ \eta_m $)	20

下载: 导出CSV 

| 显示表格

3.2   实验结果与分析

1) OSTWS方法的有效性验证

为验证目标空间转换权重求和方法(OSTWS) 的有效性, 本小节将OSTWS方法与其他7个分解方法, 即切比雪夫方法(TCH)、惩罚边界交叉方法(PBI^[24])、局部权重求和方法(LWS^[39])、自适应切比雪夫和权重求和方法(AS^[37])、同时使用切比雪夫和权重求和方法(SS^[38])、自适应Lp方法(PaS^[36]) 和自适应惩罚方法(APS^[60]) 在算法NSGAIII的框架上进行比较实验. 表3、表4和表5分别统计了上述分解方法在DTLZ1-DTLZ7、WFG1-WFG9和LSMOP1-LSMOP9测试问题上所获得的GD均值和标准差(括号内为标准差), 其中每个问题的最佳结果以灰色背景突出显示. 图4为各个算法在所有测试问题上的平均IGD⁺表现分, 分值越小表示该算法整体性能越好.

表 3  OSTWS, LWS, TCH, PBI, AS, SS, PaS和APS方法在框架为NSGAIII, 测试问题为DTLZ1-7上获得的GD值统计结果(均值和标准差). 每个实例算法中的最好结果以加粗突出显示

Table 3  The statistical results (mean and standard deviation) of the GD values obtained by OSTWS, LWS, TCH, PBI, AS, SS, PaS and APS methods on the NSGAIII framework and DTLZ1-7 test problems. The best average value among the algorithms for each instance is highlighted in bold

Problem	$m$	NSGAIII-OSTWS	NSGAIII-LWS	NSGAIII-TCH	NSGAIII-PBI	NSGAIII-AS	NSGAIII- SS	NSGAIII-PaS	NSGAIII-APS
DTLZ1	3	6.915×101	7.734×101	7.411×101	7.140×101	7.678×101	7.749×101	7.554×101	7.376×101
		(1.2×101)	(9.4×100)−	(9.3×100)$\approx$	(1.1×101)$\approx$	(1.1×101)−	(7.3×100)−	(9.4×100)$\approx$	(9.8×100)$\approx$
	5	4.218×101	7.562×101	8.102×101	7.015×101	7.870×101	1.294×102	7.993×101	6.507×101
		(4.5×100)	(6.6×100)−	(8.9×100)−	(7.6×100)−	(8.1×100)−	(9.7×100)−	(8.0×100)−	(7.6×100)−
	8	4.881×101	9.120×101	7.814×101	9.002×101	7.875×101	2.458×102	7.411×101	8.732×101
		(1.2×101)	(7.3×100)−	(1.1×101)−	(1.1×101)−	(1.2×101)−	(5.8×101)−	(9.0×100)−	(8.8×100)−
	10	4.422×101	9.338×101	7.014×101	7.334×101	6.757×101	2.672×102	7.299×101	7.538×101
		(1.8×101)	(4.9×100)−	(8.2×100)−	(2.4×101)−	(5.3×100)−	(5.1×101)−	(7.3×100)−	(3.2×101)−
DTLZ2	3	1.681×10−3	3.971×10−3	3.465×10−3	4.582×10−3	3.552×10−3	6.753×10−3	3.585×10−3	4.529×10−3
		(2.3×10−4)	(6.1×10−4)−	(3.9×10−4)−	(6.8×10−4)−	(4.2×10−4)−	(1.1×10−3)−	(5.2×10−4)−	(6.4×10−4)−
	5	3.337×10−3	4.526×10−3	4.968×10−3	6.740×10−3	4.996×10−3	1.003×10−2	4.903×10−3	6.756×10−3
		(9.7×10−5)	(3.6×10−4)−	(3.0×10−4)−	(5.3×10−4)−	(4.3×10−4)−	(1.4×10−3)−	(4.1×10−4)−	(4.0×10−4)−
	8	1.058×10−2	1.265×10−2	1.439×10−2	2.362×10−2	1.470×10−2	7.435×10−2	1.516×10−2	2.488×10−2
		(3.3×10−4)	(2.5×10−3)−	(1.7×10−3)−	(4.6×10−3)−	(1.4×10−3)−	(3.5×10−2)−	(2.5×10−3)−	(3.2×10−3)−
	10	1.070×10−2	1.503×10−2	1.130×10−2	1.733×10−2	1.133×10−2	7.939×10−2	1.227×10−2	1.996×10−2
		(4.2×10−3)	(6.0×10−3)−	(2.7×10−3)−	(7.3×10−3)−	(1.8×10−3)−	(5.4×10−2)−	(3.5×10−3)−	(6.6×10−3)−
DTLZ3	3	8.888×101	8.622×101	8.323×101	8.322×101	8.246×101	8.259×101	8.910×101	8.705×101
		(1.2×101)	(1.5×101)$\approx$	(1.5×101)$\approx$	(9.7×100)≈	(1.1×101)$\approx$	(6.9×100)$\approx$	(1.3×101)$\approx$	(1.2×101)$\approx$
	5	6.174×101	9.024×101	8.343×101	9.531×101	8.414×101	1.255×102	8.277×101	9.465×101
		(7.3×100)	(9.1×100)−	(1.0×101)−	(1.3×101)−	(1.1×101)−	(9.7×100)−	(8.8×100)−	(9.7×100)−
	8	8.605×101	1.266×102	1.220×102	1.536×102	1.176×102	3.001×102	1.293×102	1.434×102
		(2.0×101)	(1.4×101)−	(9.6×100)−	(2.3×101)−	(9.2×100)−	(8.2×101)−	(1.3×101)−	(2.5×101)−
	10	7.830×101	1.340×102	1.201×102	1.427×102	1.157×102	3.629×102	1.273×102	1.314×102
		(3.5×101)	(2.3×101)−	(1.4×101)−	(4.5×101)−	(7.3×100)−	(7.1×101)−	(2.7×101)−	(2.9×101)−
DTLZ4	3	1.918×10−3	4.026×10−3	3.588×10−3	4.068×10−3	3.455×10−3	7.379×10−3	3.242×10−3	4.393×10−3
		(3.1×10−4)	(1.1×10−3)−	(1.1×10−3)−	(2.1×10−3)−	(1.1×10−3)−	(3.0×10−3)−	(1.3×10−3)−	(1.6×10−3)−
	5	3.506×10−3	5.160×10−3	5.502×10−3	8.623×10−3	5.326×10−3	7.816×10−3	5.367×10−3	8.775×10−3
		(5.0×10−4)	(5.4×10−4)−	(4.4×10−4)−	(1.4×10−3)−	(2.9×10−4)−	(2.3×10−3)−	(3.5×10−4)−	(1.0×10−3)−
	8	1.658×10−2	2.169×10−2	2.858×10−2	3.486×10−2	2.597×10−2	7.637×10−2	1.887×10−2	3.592×10−2
		(2.0×10−2)	(1.7×10−2)$\approx$	(1.8×10−2)−	(1.6×10−2)−	(1.7×10−2)−	(3.6×10−2)−	(5.4×10−3)−	(2.2×10−2)−
	10	7.670×10−3	1.737×10−2	1.282×10−2	2.060×10−2	1.336×10−2	1.052×10−1	1.047×10−2	1.792×10−2
		(2.0×10−3)	(1.8×10−2)$\approx$	(7.1×10−3)−	(1.2×10−2)−	(8.2×10−3)−	(6.0×10−2)−	(4.2×10−3)−	(4.8×10−3)−
DTLZ5	3	4.566×10−3	4.388×10−3	4.698×10−3	5.107×10−3	4.836×10−3	5.209×10−3	5.353×10−3	5.055×10−3
		(7.2×10−4)	(7.7×10−4)≈	(6.3×10−4)$\approx$	(7.8×10−4)−	(7.4×10−4)$\approx$	(8.2×10−4)−	(8.9×10−4)−	(5.4×10−4)−
	5	6.411×10−2	4.279×10−1	1.027×10−1	6.492×10−2	1.194×10−1	2.345×10−1	1.186×10−1	7.556×10−2
		(1.7×10−2)	(8.2×10−2)−	(1.6×10−2)−	(1.5×10−2)$\approx$	(2.3×10−2)−	(3.6×10−2)−	(1.4×10−2)−	(1.6×10−2)−
	8	2.795×10−1	5.134×10−1	4.167×10−1	4.142×10−1	5.253×10−1	1.082×100	5.319×10−1	4.527×10−1
		(5.2×10−2)	(1.1×10−1)−	(7.0×10−2)−	(5.7×10−2)−	(8.8×10−2)−	(5.9×10−1)−	(1.1×10−1)−	(9.5×10−2)−
	10	3.845×10−1	1.266×100	1.283×100	8.411×10−1	1.660×100	2.054×100	1.668×100	9.914×10−1
		(2.3×10−1)	(3.6×10−1)−	(3.1×10−1)−	(2.7×10−1)−	(2.1×10−1)−	(6.5×10−1)−	(2.3×10−1)−	(2.1×10−1)−
DTLZ6	3	3.555×100	4.484×100	4.150×100	4.294×100	4.055×100	6.531×100	4.099×100	4.164×100
		(3.4×10−1)	(3.6×10−1)−	(4.0×10−1)−	(4.3×10−1)−	(2.3×10−1)−	(2.6×10−1)−	(4.0×10−1)−	(4.2×10−1)−
	5	2.454×100	1.135×101	8.566×100	6.659×100	8.595×100	7.759×100	8.606×100	6.597×100
		(2.8×10−1)	(2.3×10−1)−	(5.4×10−1)−	(1.8×10−1)−	(3.0×10−1)−	(4.1×10−1)−	(3.6×10−1)−	(2.7×10−1)−
	8	1.235×101	2.182×101	1.927×101	2.201×101	1.915×101	2.548×101	1.933×101	2.174×101
		(8.7×10−1)	(2.3×100)−	(8.5×10−1)−	(3.1×100)−	(9.4×10−1)−	(6.2×100)−	(1.1×100)−	(4.0×100)−
	10	1.344×101	2.871×101	2.511×101	2.395×101	2.535×101	2.887×101	2.501×101	2.203×101
		(1.6×100)	(8.3×100)−	(1.6×100)−	(1.0×101)−	(1.1×100)−	(1.1×101)−	(4.0×100)−	(8.9×100)−
DTLZ7	3	1.385×10−2	1.479×10−2	1.476×10−2	1.788×10−2	1.538×10−2	1.780×10−2	1.628×10−2	1.839×10−2
		(2.3×10−3)	(2.5×10−3)$\approx$	(2.0×10−3)$\approx$	(2.3×10−3)−	(1.9×10−3)−	(3.3×10−3)−	(3.7×10−3)−	(2.5×10−3)−
	5	8.419×10−3	9.474×10−3	9.755×10−3	1.481×10−2	9.498×10−3	1.712×10−2	9.146×10−3	1.534×10−2
		(1.2×10−3)	(1.4×10−3)−	(1.0×10−3)−	(1.6×10−3)−	(1.0×10−3)−	(1.6×10−3)−	(1.3×10−3)$\approx$	(1.4×10−3)−
	8	2.742×10−2	2.987×10−2	3.999×10−2	3.594×10−2	3.700×10−2	5.275×10−2	4.093×10−2	3.597×10−2
		(1.8×10−3)	(4.4×10−3)$\approx$	(3.2×10−3)−	(5.5×10−3)−	(5.2×10−3)−	(5.6×10−3)−	(5.4×10−3)−	(4.7×10−3)−
	10	2.928×10−2	2.449×10−2	2.800×10−2	2.893×10−2	3.052×10−2	4.273×10−2	3.055×10−2	2.869×10−2
		(2.3×10−3)	(3.6×10−3)+	(2.5×10−3)$\approx$	(2.0×10−3)$\approx$	(1.9×10−3)$\approx$	(3.5×10−3)−	(3.1×10−3)$\approx$	(3.6×10−3)$\approx$
$+/-/\approx$			1/21/6	0/23/5	0/24/4	0/25/3	0/27/1	0/25/3	0/24/4

下载: 导出CSV 

| 显示表格

表 4  OSTWS, LWS, TCH, PBI, AS, SS, PaS和APS方法在框架为NSGAIII, 测试问题集为WFG1-9上获得的GD值统计结果(均值和标准差). 每个实例算法中的最好结果以加粗突出显示

Table 4  The statistical results (mean and standard deviation) of the GD values obtained by OSTWS, LWS, TCH, PBI, AS, SS, PaS and APS methods on the NSGAIII framework and WFG1-9 test problems. The best average value among the algorithms for each instance is highlighted in bold

Problem	$m$	NSGAIII-OSTWS	NSGAIII-LWS	NSGAIII-TCH	NSGAIII-PBI	NSGAIII-AS	NSGAIII- SS	NSGAIII-PaS	NSGAIII-APS
WFG1	3	4.082×10−2	4.125×10−2	4.435×10−2	4.357×10−2	4.475×10−2	4.206×10−2	4.454×10−2	4.368×10−2
		(6.0×10−4)	(9.1×10−4)$\approx$	(8.9×10−4−	(7.2×10−4)−	(7.5×10−4)−	(1.1×10−3)−	(1.2×10−3)−	(6.7×10−4)−
	5	2.789×10−2	2.670×10−2	3.220×10−2	2.936×10−2	3.194×10−2	2.790×10−2	3.225×10−2	2.960×10−2
		(9.2×10−4)	(4.3×10−4)+	(6.2×10−4)−	(3.9×10−4)−	(7.8×10−4)−	(7.8×10−4)−	(6.2×10−4)−	(3.0×10−4)−
	8	3.323×10−2	3.429×10−2	3.472×10−2	3.483×10−2	3.504×10−2	3.624×10−2	3.506×10−2	3.446×10−2
		(9.2×10−4)	(1.3×10−3)−	(8.6×10−4)−	(9.1×10−4)−	(1.3×10−3)−	(3.4×10−3)−	(1.5×10−3)−	(1.4×10−3)−
	10	2.474×10−2	2.585×10−2	2.589×10−2	2.614×10−2	2.546×10−2	2.816×10−2	2.535×10−2	2.607×10−2
		(5.6×10−4)	(5.3×10−4)−	(1.2×10−3)−	(9.3×10−4)−	(9.5×10−4)−	(1.6×10−3)−	(9.3×10−4)−	(8.2×10−4)−
WFG2	3	5.354×10−3	5.103×10−3	5.846×10−3	6.124×10−3	5.965×10−3	8.529×10−3	6.085×10−3	6.088×10−3
		(6.5×10−4)	(4.8×10−4)≈	(6.4×10−4)−	(4.6×10−4)−	(4.8×10−4)−	(1.6×10−3)−	(7.1×10−4)−	(4.9×10−4)−
		5	4.885×10−3	5.663×10−3	7.042×10−3	5.902×10−3	7.329×10−3	6.705×10−3	6.924×10−3	6.009×10−3
			(2.2×10−4)	(6.0×10−4)−	(6.3×10−4)−	(2.1×10−4)−	(5.3×10−4)−	(8.3×10−4)−	(1.1×10−3)−	(2.1×10−4)−
		8	8.277×10−3	1.011×10−2	9.969×10−3	9.745×10−3	1.025×10−2	1.269×10−2	1.006×10−2	1.018×10−2
			(7.0×10−4)	(1.1×10−3)−	(5.7×10−4)−	(1.6×10−3)−	(1.0×10−3)−	(2.8×10−3)−	(9.9×10−4)−	(3.1×10−3)−
		10	1.528×10−2	1.447×10−2	1.309×10−2	1.329×10−2	1.142×10−2	1.460×10−2	1.179×10−2	1.317×10−2
			(1.8×10−3)	(1.8×10−3)$\approx$	(1.9×10−3)+	(2.3×10−3)+	(1.6×10−3)+	(2.7×10−3)$\approx$	(1.1×10−3)+	(2.6×10−3)+
WFG3	3	1.154×10−2	1.273×10−2	1.480×10−2	1.684×10−2	1.4610×10−2	2.620×10−2	1.497×10−2	1.693×10−2
		(1.5×10−3)	(1.6×10−3)−	(1.2×10−3)−	(2.0×10−3)−	(1.1×10−3)−	(2.0×10−3)−	(2.0×10−3)−	(1.1×10−3)−
	5	3.912×10−2	3.555×10−2	1.130×10−1	8.826×10−2	1.320×10−1	5.550×10−2	1.156×10−1	7.736×10−2
		(4.2×10−3)	(4.5×10−3)+	(1.1×10−2)−	(2.7×10−2)−	(1.2×10−2)−	(7.5×10−3)−	(1.5×10−2)−	(2.0×10−2)−
	8	6.263×10−1	8.328×10−1	6.008×10−1	5.867×10−1	7.676×10−1	5.991×10−1	6.118×10−1	6.314×10−1
		(1.3×10−1)	(8.3×10−2)−	(1.2×10−1)$\approx$	(1.2×10−1)≈	(2.5×10−1)−	(9.2×10−2)$\approx$	(1.2×10−1)$\approx$	(2.3×10−1)$\approx$
	10	2.374×100	3.674×100	2.840×100	1.902×100	3.110×100	2.402×100	3.252×100	1.965×100
		(8.6×10−1)	(6.4×10−1)−	(1.0×100)−	(6.0×10−1)≈	(9.7×10−1)−	(2.7×10−1)−	(1.1×100)−	(6.7×10−1)$\approx$
WFG4	3	1.387×10−3	2.231×10−3	3.001×10−3	3.370×10−3	2.893×10−3	4.412×10−3	2.953×10−3	3.284×10−3
		(1.1×10−4)	(1.5×10−4)−	(2.5×10−4)−	(2.1×10−4)−	(2.3×10−4)−	(3.6×10−4)−	(1.5×10−4)−	(2.4×10−4)−
	5	3.717×10−3	2.834×10−3	5.696×10−3	4.746×10−3	5.847×10−3	4.401×10−3	5.766×10−3	4.725×10−3
		(6.3×10−5)	(7.6×10−5)+	(3.1×10−4)−	(8.3×10−5)−	(3.6×10−4)−	(1.4×10−4)−	(3.4×10−4)−	(6.5×10−5)−
	8	1.263×10−2	1.244×10−2	1.543×10−2	1.501×10−2	1.497×10−2	1.462×10−2	1.517×10−2	1.437×10−2
		(3.8×10−4)	(3.6×10−4)≈	(6.9×10−4)−	(7.1×10−4)−	(6.3×10−4)−	(1.4×10−3)−	(5.4×10−4)−	(1.5×10−3)−
	10	7.624×10−3	1.344×10−2	1.203×10−2	8.833×10−3	1.210×10−2	1.401×10−2	1.211×10−2	8.060×10−3
		(8.9×10−4)	(5.8×10−4)−	(1.4×10−4)−	(1.8×10−3)−	(2.0×10−4)−	(6.9×10−4)−	(2.1×10−4)−	(1.3×10−3)$\approx$
WFG5	3	2.770×10−3	3.404×10−3	3.979×10−3	4.138×10−3	3.927×10−3	5.689×10−3	3.861×10−3	4.077×10−3
		(7.4×10−5)	(2.0×10−4)−	(2.2×10−4)−	(1.7×10−4)−	(1.8×10−4)−	(5.0×10−4)−	(1.9×10−4)−	(1.6×10−4)−
	5	4.094×10−3	3.377×10−3	6.612×10−3	4.771×10−3	6.671×10−3	4.338×10−3	6.681×10−3	4.755×10−3
		(8.3×10−5)	(5.6×10−5)+	(4.5×10−4)−	(8.2×10−5)−	(4.7×10−4)−	(1.9×10−4)−	(5.1×10−4)−	(8.3×10−5)−
	8	1.288×10−2	1.281×10−2	1.747×10−2	1.543×10−2	1.767×10−2	1.385×10−2	1.737×10−2	1.548×10−2
		(2.2×10−4)	(5.9×10−4)≈	(5.6×10−4)−	(2.0×10−4)−	(5.8×10−4)−	(1.1×10−3)−	(4.6×10−4)−	(3.0×10−4)−
	10	9.292×10−3	1.366×10−2	1.149×10−2	8.550×10−3	1.158×10−2	1.246×10−2	1.159×10−2	8.604×10−3
		(3.8×10−4)	(3.0×10−4)−	(3.3×10−4)−	(3.8×10−4)+	(3.0×10−4)−	(8.8×10−4)−	(3.2×10−4)−	(4.0×10−4)+
WFG6	3	2.151×10−3	3.052×10−3	3.902×10−3	4.170×10−3	3.933×10−3	5.274×10−3	3.913×10−3	4.134×10−3
		(1.6×10−4)	(1.9×10−4)−	(2.0×10−4)−	(3.0×10−4)−	(2.7×10−4)−	(4.4×10−4)−	(2.4×10−4)−	(2.3×10−4)−
	5	3.999×10−3	3.168×10−3	8.235×10−3	4.969×10−3	8.134×10−3	4.872×10−3	7.986×10−3	4.941×10−3
		(9.9×10−5)	(7.5×10−5)+	(9.9×10−4)−	(1.2×10−4)−	(8.0×10−4)−	(2.0×10−4)−	(8.7×10−4)−	(1.1×10−4)−
	8	1.250×10−2	1.215×10−2	1.800×10−2	1.544×10−2	1.799×10−2	1.536×10−2	1.7820×10−2	1.555×10−2
		(2.4×10−4)	(7.6×10−4)≈	(5.8×10−4)−	(2.3×10−4)−	(7.9×10−4)−	(9.2×10−4)−	(9.1×10−4)−	(3.0×10−4)−
	10	7.483×10−3	1.238×10−2	1.230×10−2	7.812×10−3	1.241×10−2	1.463×10−2	1.244×10−2	8.120×10−3
		(5.2×10−4)	(6.1×10−4)−	(4.0×10−4)−	(3.6×10−4)−	(3.1×10−4)−	(6.7×10−4)−	(3.2×10−4)−	(9.1×10−4)−
WFG7	3	8.882×10−4	2.105×10−3	3.270×10−3	5.073×10−3	3.280×10−3	7.455×10−3	3.182×10−3	4.750×10−3
		(4.9×10−5)	(3.2×10−4)−	(7.6×10−4)−	(7.9×10−4)−	(3.7×10−4)−	(3.0×10−3)−	(4.5×10−4)−	(5.8×10−4)−
		5	3.323×10−3	2.647×10−3	7.618×10−3	5.695×10−3	8.228×10−3	4.176×10−3	8.303×10−3	5.888×10−3
			(8.2×10−5)	(9.6×10−5)+	(1.6×10−3)−	(5.7×10−4)−	(1.8×10−3)−	(3.2×10−4)−	(1.6×10−3)−	(7.7×10−4)−
		8	1.168×10−2	1.245×10−2	1.742×10−2	1.599×10−2	1.745×10−2	1.330×10−2	1.736×10−2	1.606×10−2
			(6.5×10−4)	(2.2×10−3)−	(6.5×10−4)−	(6.3×10−4)−	(5.7×10−4)−	(1.0×10−3)−	(6.3×10−4)−	(8.2×10−4)−
		10	6.602×10−3	1.129×10−2	1.217×10−2	8.449×10−3	1.222×10−2	1.308×10−2	1.220×10−2	8.566×10−3
			(6.2×10−4)	(8.8×10−4)−	(3.1×10−4)−	(5.0×10−4)−	(2.6×10−4)−	(5.0×10−4)−	(3.6×10−4)−	(7.1×10−4)−
WFG8	3	4.390×10−3	5.139×10−3	5.619×10−3	5.561×10−3	5.792×10−3	7.016×10−3	5.703×10−3	5.550×10−3
		(2.7×10−4)	(2.4×10−4)−	(2.6×10−4)−	(2.5×10−4)−	(2.5×10−4)−	(4.8×10−4)−	(3.5×10−4)−	(3.0×10−4)−
	5	4.796×10−3	4.301×10−3	7.939×10−3	5.018×10−3	7.786×10−3	5.403×10−3	7.969×10−3	5.053×10−3
		(1.1×10−4)	(1.0×10−4)+	(4.1×10−4)−	(1.0×10−4)−	(4.8×10−4)−	(3.6×10−4)−	(5.9×10−4)−	(9.2×10−5)−
	8	1.307×10−2	1.308×10−2	1.832×10−2	1.569×10−2	1.834×10−2	1.524×10−2	1.828×10−2	1.560×10−2
		(3.0×10−4)	(1.1×10−3)$\approx$	(5.5×10−4)−	(2.5×10−4)−	(5.0×10−4)−	(1.1×10−3)−	(4.7×10−4)−	(6.4×10−4)−
	10	9.844×10−3	1.405×10−2	1.227×10−2	9.342×10−3	1.229×10−2	1.346×10−2	1.243×10−2	9.774×10−3
		(2.6×10−4)	(4.3×10−4)−	(4.0×10−4)−	(4.8×10−4)+	(3.0×10−4)−	(8.9×10−4)−	(4.6×10−4)−	(8.4×10−4)$\approx$
WFG9	3	2.200×10−3	6.110×10−3	5.287×10−3	8.679×10−3	5.360×10−3	8.726×10−3	4.796×10−3	8.011×10−3
		(2.8×10−4)	(6.8×10−4)−	(5.0×10−4)−	(1.1×10−3)−	(6.0×10−4)−	(9.6×10−4)−	(7.7×10−4)−	(6.3×10−4)−
	5	4.144×10−3	4.250×10−3	8.592×10−3	7.838×10−3	8.773×10−3	5.496×10−3	8.772×10−3	7.720×10−3
		(1.1×10−4)	(2.1×10−4)−	(1.3×10−3)−	(3.6×10−4)−	(2.0×10−3)−	(4.4×10−4)−	(1.3×10−3)−	(4.5×10−4)−
	8	1.339×10−2	1.570×10−2	1.810×10−2	1.814×10−2	1.827×10−2	1.508×10−2	1.801×10−2	1.793×10−2
		(3.2×10−4)	(1.8×10−3)−	(7.5×10−4)−	(5.5×10−4)−	(6.2×10−4)−	(1.6×10−3)−	(7.3×10−4)−	(4.3×10−4)−
	10	1.082×10−2	1.533×10−2	1.245×10−2	1.288×10−2	1.280×10−2	1.315×10−2	1.276×10−2	1.274×10−2
		(3.5×10−4)	(3.1×10−4)−	(3.2×10−4)−	(4.1×10−4)−	(4.6×10−4)−	(8.6×10−4)−	(4.3×10−4)−	(3.8×10−4)−
$+/-/\approx$			7/22/7	1/33/2	3/31/2	1/35/0	0/32/4	1/34/1	2/30/4

下载: 导出CSV 

| 显示表格

表 5  OSTWS, LWS, TCH, PBI, AS, SS, PaS和APS方法在框架为NSGAIII, 测试问题集为LSMOP1-9上获得的GD值统计结果(均值和标准差). 每个实例算法中的最好结果以加粗突出显示

Table 5  The statistical results (mean and standard deviation) of the GD values obtained by OSTWS, LWS, TCH, PBI, AS, SS, PaS and APS methods on the NSGAIII framework and LSMOP1-9 test problems. The best average value among the algorithms for each instance is highlighted in bold

Problem	m	NSGAIII-OSTWS	NSGAIII-LWS	NSGAIII-TCH	NSGAIII-PBI	NSGAIII-AS	NSGAIII-SS	NSGAIII-PaS	NSGAIII-APS
LSMOP1	3	8.526×10−1 (1.3×10−1)	9.451×10−1 (9.7×10−2)−	8.776×10−1 (1.1×10−1)$\approx$	9.691×10−1 (1.4×10−1)−	8.904×10−1 (1.4×10−1)$\approx$	1.439×100 (7.8×10−1)$\approx$	9.296×10−1 (1.4×10−1)$\approx$	9.070×10−1 (1.3×10−1)$\approx$
	5	4.829×10−1 (2.1×10−1)	5.596×10−1 (5.7×10−2)−	5.858×10−1 (5.3×10−2)−	5.483×10−1 (9.3×10−2)−	5.800×10−1 (4.8×10−2)−	8.027×10−1 (8.0×10−2)−	4.784×10−1 (1.0×10−1)≈	5.518×10−1 (4.5×10−2)−
	8	5.409×10−1 (1.4×10−1)	8.855×10−1 (5.9×10−2)−	8.447×10−1 (1.6×10−1)−	8.037×10−1 (2.0×10−1)−	9.307×10−1 (2.1×10−1)−	1.343×100 (1.7×10−1)−	7.875×10−1 (1.1×10−1)−	8.568×10−1 (1.4×10−1)−
	10	4.598×10−1 (1.1×10−1)	8.812×10−1 (1.01×10−1)−	8.967×10−1 (7.9×10−2)−	6.762×10−1 (1.4×10−1)−	9.021×10−1 (8.4×10−2)−	9.689×10−1 (1.1×10−1)−	6.232×10−1 (7.5×10−2)−	9.011×10−1 (1.0×10−1)−
LSMOP2	3	7.646×10−3 (1.8×10−4)	1.026×10−2 (2.3×10−4)−	9.405×10−3 (1.3×10−4)−	9.825×10−3 (1.6×10−4)−	9.403×10−3 (1.4×10−4)−	1.105×10−2 (1.1×10−3)−	9.698×10−3 (1.7×10−4)−	9.490×10−3 (1.8×10−4)−
	5	6.197×10−3 (8.9×10−5)	8.530×10−3 (9.0×10−5)−	7.660×10−3 (7.0×10−5)−	7.866×10−3 (5.8×10−5)−	7.661×10−3 (1.6×10−4)−	9.447×10−3 (5.4×10−4)−	7.920×10−3 (5.0×10−5)−	7.623×10−3 (4.5×10−5)−
	8	1.243×10−2 (6.0×10−4)	2.217×10−2 (2.6×10−3)−	1.890×10−2 (2.2×10−3)−	1.948×10−2 (6.8×10−4)−	1.839×10−2 (1.5×10−3)−	1.792×10−2 (3.7×10−3)−	1.982×10−2 (1.5×10−3)−	1.824×10−2 (2.1×10−3)−
	10	9.467×10−3 (2.1×10−4)	1.364×10−2 (6.5×10−4)−	1.230×10−2 (1.3×10−3)−	1.271×10−2 (1.6×10−4)−	1.248×10−2 (1.1×10−3)−	1.658×10−2 (4.0×10−3)−	1.213×10−2 (3.3×10−4)−	1.239×10−2 (1.3×10−3)−
LSMOP3	3	2.990×102 (1.32×102)	2.763×102 (7.0×101)≈	2.993×102 (8.8×101)$\approx$	3.366×102 (1.8×102)$\approx$	3.316×102 (8.7×101)$\approx$	4.780×102 (2.5×102)−	3.243×102 (1.3×102)$\approx$	3.793×102 (1.0×102)−
	5	6.116×102 (2.8×102)	8.207×102 (1.7×102)−	9.284×102 (1.5×102)−	9.599×102 (5.5×102)−	9.630×102 (2.2×102)−	1.906×103 (4.6×102)−	9.785×102 (4.95×102)−	9.834×102 (2.7×102)−
	8	1.369×103 (5.8×102)	2.207×103 (5.8×102)−	2.607×103 (6.1×102)−	1.927×103 (6.2×102)−	3.040×103 (5.2×102)−	3.418×103 (8.0×102)−	2.167×103 (8.0×102)−	3.087×103 (8.9×102)−
	10	3.379×103 (1.7×103)	3.133×103 (1.1×103)$\approx$	4.097×103 (9.2×102)$\approx$	2.945×103 (1.5×103)≈	4.655×103 (1.2×103)−	3.510×103 (7.9×102)$\approx$	3.373×103 (1.9×103)$\approx$	4.029×103 (9.6×102)$\approx$
LSMOP4	3	3.073×10−2 (2.0×10−3)	3.744×10−2 (9.4×10−4)−	3.730×10−2 (1.4×10−3)−	4.045×10−2 (1.2×10−3)−	3.704×10−2 (1.1×10−3)−	4.004×10−2 (4.9×10−3)−	4.034×10−2 (1.0×10−3)−	3.742×10−2 (1.2×10−3)−
	5	2.598×10−2 (1.8×10−3)	3.942×10−2 (1.8×10−3)−	3.656×10−2 (2.1×10−3)−	3.888×10−2 (2.0×10−3)−	3.547×10−2 (1.5×10−3)−	3.750×10−2 (4.6×10−3)−	4.093×10−2 (1.6×10−3)−	3.641×10−2 (1.6×10−3)−
	8	1.995×10−2 (7.8×10−4)	3.397×10−2 (1.3×10−3)−	2.209×10−2 (3.5×10−3)−	3.297×10−2 (1.4×10−3)−	2.324×10−2 (4.2×10−3)−	5.114×10−2 (9.6×10−3)−	3.301×10−2 (1.4×10−3)−	2.257×10−2 (4.2×10−3)−
	10	1.459×10−2 (4.8×10−4)	2.521×10−2 (1.3×10−3)−	1.490×10−2 (8.0×10−4)$\approx$	2.260×10−2 (7.0×10−4)−	1.548×10−2 (1.1×10−3)−	2.585×10−2 (6.9×10−3)−	2.283×10−2 (1.0×10−3)−	1.613×10−2 (2.4×10−3)−
LSMOP5	3	2.605×100 (3.9×10−1)	2.694×100 (3.2×10−1)$\approx$	2.534×100 (3.2×10−1)$\approx$	2.780×100 (2.7×10−1)$\approx$	2.516×100 (4.6×10−1)$\approx$	3.782×100 (4.9×10−1)−	2.772×100 (4.1×10−1)$\approx$	2.292×100 (2.4×10−1)+
	5	2.314×100 (1.4×100)	3.210×100 (2.3×10−1)−	3.370×100 (3.1×10−1)−	3.510×100 (8.2×10−1)−	3.075×100 (2.4×10−1)−	5.678×100 (5.9×10−1)−	3.810×100 (4.8×10−1)−	3.079×100 (3.1×10−1)−
	8	4.708×100 (2.2×100)	7.771×100 (1.1×100)−	7.613×100 (9.5×10−1)−	5.93×100 (3.6×100)$\approx$	7.218×100 (9.6×10−1)−	7.384×100 (1.7×100)−	8.816×100 (1.8×100)−	7.327×100 (1.1×100)−
	10	5.077×100 (7.7×10−1)	6.883×100 (6.8×10−1)−	6.279×100 (9.4×10−1)−	6.707×100 (2.0×100)−	6.522×100 (9.3×10−1)−	4.854×100 (6.3×10−1)≈	7.631×100 (2.8×10−1)−	6.118×100 (7.2×10−1)−
LSMOP6	3	4.402×103 (2.5×103)	3.127×103 (1.4×103)$\approx$	2.938×103 (1.1×103)≈	3.477×103 (1.7×103)$\approx$	3.410×103 (1.6×103)$\approx$	4.088×103 (2.0×103)$\approx$	4.089×103 (2.5×103)$\approx$	3.025×103 (2.0×103)$+$
	5	5.002×103 (2.6×103)	5.108×103 (1.3×103)$\approx$	5.354×103 (1.0×103)$\approx$	4.366×103 (2.5×103)$\approx$	5.637×103 (1.4×103)$\approx$	1.202×104 (3.4×103)−	3.587×103 (1.2×103)+	5.220×103 (1.6×103)$\approx$
	8	2.206×104 (4.9×103)	2.041×104 (5.6×103)≈	2.484×104 (9.6×103)$\approx$	3.608×104 (9.8×103)−	2.475×104 (8.7×103)$\approx$	7.647×104 (1.8×104)−	3.385×104 (1.3×104)−	2.425×104 (5.4×103)$\approx$
	10	1.933×104 (4.8×103)	1.924×104 (2.7×103)≈	2.847×104 (6.9×103)−	3.601×104 (8.8×103)−	2.661×104 (9.5×103)−	5.022×104 (8.7×103)−	3.410×104 (7.8×103)−	2.844×104 (6.2×103)−
LSMOP7	3	5.540×102 (1.4×102)	8.520×102 (4.2×102)−	8.707×102 (3.8×102)−	9.200×102 (4.0×102)−	8.946×102 (2.5×102)−	2.598×103 (8.7×102)−	9.381×102 (2.8×102)−	1.013×103 (3.0×102)−
	5	4.597×103 (1.6×103)	4.424×103 (1.8×103)$\approx$	5.261×103 (2.1×103)$\approx$	4.238×103 (9.4×102)≈	5.665×103 (1.6×103)−	1.403×104 (3.9×103)−	4.530×103 (1.8×103)$\approx$	5.627×103 (3.4×103)$\approx$
	8	3.305×104 (8.4×103)	3.482×104 (8.4×103)$\approx$	3.490×104 (7.6×103)$\approx$	4.471×104 (1.8×104)−	2.847×104 (9.6×103)≈	5.022×104 (1.0×104)−	4.770×104 (1.6×104)−	3.268×104 (7.4×103)$\approx$
	10	3.545×104 (4.5×103)	3.599×104 (6.3×103)$\approx$	3.980×104 (8.8×103)$\approx$	4.835×104 (8.0×103)−	3.065×104 (6.0×103)+	3.246×104 (5.90×103)$\approx$	5.216×104 (6.9×103)−	3.455×104 (8.2×103)$\approx$
LSMOP8	3	3.940×10−1 (8.9×10−2)	4.540×10−1 (5.3×10−2)−	4.006×10−1 (6.0×10−2)$\approx$	4.445×10−1 (7.2×10−2)−	4.205×10−1 (6.5×10−2)$\approx$	1.071×100 (1.8×10−1)−	4.654×10−1 (7.6×10−2)−	4.081×10−1 (8.3×10−2)$\approx$
	5	5.216×10−1 (1.3×10−1)	6.430×10−1 (7.1×10−2)−	6.342×10−1 (1.1×10−1)−	8.661×10−1 (1.3×10−1)−	6.569×10−1 (1.2×10−1)−	2.096×100 (2.8×10−1)−	8.376×10−1 (1.3×10−1)−	6.559×10−1 (1.1×10−1)−
	8	2.282×100 (6.5×10−1)	3.190×100 (4.8×10−1)−	3.522×100 (5.1×10−1)−	4.130×100 (6.7×10−1)−	3.117×100 (5.0×10−1)−	3.437×100 (4.4×10−1)−	4.167×100 (3.1×10−1)−	3.361×100 (4.3×10−1)−
	10	2.307×100 (2.4×10−1)	2.924×100 (3.4×10−1)−	2.958×100 (3.6×10−1)−	3.363×100 (2.9×10−1)−	2.690×100 (4.0×10−1)−	2.299×100 (2.1×10−1)≈	3.322×100 (2.9×10−1)−	2.853×100 (4.5×10−1)−
LSMOP9	3	4.151×10−1 (8.1×10−2)	4.150×10−1 (5.9×10−2)$\approx$	4.220×10−1 (1.0×10−1)$\approx$	4.240×10−1 (8.7×10−2)$\approx$	3.690×10−1 (5.8×10−2)+	5.607×10−1 (1.3×10−1)−	4.334×10−1 (9.4×10−2)$\approx$	4.134×10−1 (6.4×10−2)$\approx$
	5	2.658×10−1 (3.9×10−2)	2.945×10−1 (3.7×10−2)−	2.915×10−1 (5.0×10−2)$\approx$	3.451×10−1 (5.9×10−2)−	2.772×10−1 (4.2×10−2)$\approx$	4.072×10−1 (7.1×10−2)−	3.220×10−1 (5.3×102)−	2.750×10−1 (3.4×10−2)$\approx$
	8	1.766×100 (1.7×10−1)	2.421×100 (2.4×10−1)−	3.296×100 (3.5×10−1)−	2.265×100 (2.2×10−1)−	3.525×100 (3.4×10−1)−	4.172×100 (3.9×10−1)−	2.267×100 (2.5×10−1)−	3.801×100 (4.0×10−1)−
	10	1.789×100 (2.5×10−1)	2.766×100 (2.5×10−1)−	4.112×100 (3.2×10−1)−	2.824×100 (3.4×10−1)−	4.783×100 (3.5×10−1)−	4.820×100 (2.8×10−1)−	2.740×100 (3.5×10−1)−	4.940×100 (3.6×10−1)−
$+/-/\approx$			0/25/11	0/22/14	0/28/8	2/25/9	0/30/6	1/27/8	2/24/10

下载: 导出CSV 

| 显示表格

图 4  NSGAIII-OSTWS, NSGAIII-LWS, NSGAIII-TCH, NSGAIII-PBI, NSGAIII-AS, NSGAIII-SS, NSGAIII-APS和NSGAIII-PaS, 在所有测试问题实例中的平均IGD⁺性能得分排名. 得分越小, 整体性能越好

Fig. 4  Ranking in the average performance score over all test problem instances for the algorithms of NSGAIII-OSTWS, NSGAIII-LWS, NSGAIII-TCH, NSGAIII-PBI, NSGAIII-AS, NSGAIII-SS, NSGAIII-APS and NSGAIII-PaS. The smaller the score, the better the overall performance in terms of IGD⁺

下载: 全尺寸图片 幻灯片

由表3、表4和表5可以看出, NSGAIII-OSTWS在绝大部分DTLZ测试问题上都取得了最佳GD均值, 此外, 虽然NSGAIII-OSTWS没能在所有的WFG和LSMOP测试问题中获得最具竞争力的GD性能, 但总体上获得了最优的性能, 这表明本文所提出的OSTWS方法是非常有效的, 原因在于充分利用了WS方法搜索效率高的优势.

下面具体分析各个算法在DTLZ1-DTLZ7、WFG1-WFG9和LSMOP1-LSMOP9测试问题上的性能. DTLZ1是一个线性问题, NSGAIII-OSTWS在该问题上获得了最佳的GD值, 即在线性的DTLZ1问题上, OSTWS方法的收敛性要强于其它所对比的分解方法. DTLZ2-4和WFG4-9为凹问题, 对于DTLZ2-4, NSGAIII-OSTWS获得了最优性能. 为直观展示各个算法在凹问题上的收敛性能, 图5例举了所有算法在10维DTLZ2问题上的最终种群分布图. 从图5可以看出, 算法NSGAIII-OSTWS的种群分布在目标空间[0, 1]内, 其它算法的种群大部分都分布在目标空间[0, 1.2] 内, 这表明算法NSGAIII-OSTWS能很好的将种群收敛到PF上, 而其它算法却不能. 虽然WFG4-9同样为凹问题, 但相对于DTLZ2-4来说, WFG4-9测试问题具有多峰、带欺骗和变量不可分离等更加复杂的特点, 从而给算法带来了更大的挑战. 但从表4可以看出, NSGAIII-OSTWS在大部分WFG4-9测试问题上都能取得最佳的性能指标值. DTLZ5-6和WFG3为退化问题, 对于DTLZ5-6, NSGAIII-OSTWS仍然表现出了最佳的收敛能力. 在WFG3上, 由GD指标的统计数据可知NSGAIII-OSTWS的性能则一般. WFG1是一个凹凸混合问题, WFG2和DTLZ7为不连续问题, 在这三个问题上, NSGAIII-OSTWS的性能会有所下降. 原因是OSTWS很难快速且准确地预估出此类PF的形状, 需要消耗一定的迭代次数, 从而降低了种群的收敛速度. 但本文所采用的预估PF方法最终能较好地预估出这些问题的PF形状, 故在处理这些不规则测试问题时依然取得了较好的性能. 相对于DTLZ和WFG测试问题集, LSMOP具有更大规模的决策变量, 种群的收敛难度增大, 对现有的超多目标算法提出了更大的挑战. 由于OSTWS继承了权重求和分解方法的高搜索效率, 因此相对于原始的NSGAIII算法, NSGAIII-OSTWS在难收敛的大规模决策变量问题处理上仍具有显著的优势, 能较快地将种群进化至PF. 从表5可以看出, 本文所提出的算法NSGAIII-OSTWS在LSMOP的大部分测试问题上都取得了最佳的GD指标值, 这再次验证了OSTWS方法具有很强的搜索效率. 综合统计结果可以看出, NSGAIII-OSTWS在DTLZ、WFG和LSMOP测试集上虽然没能在每个测试实例上都获得最优的GD结果, 但总体收敛性能优异.

图 5  NSGAIII-OSTWS, NSGAIII-LWS, NSGAIII-TCH, NSGAIII-PBI, NSGAIII-AS, NSGAIII-SS, NSGAIII-PaS和NSGAIII-APS在10维DTLZ2问题上所获得的解集

Fig. 5  Solution set of NSGAIII-OSTWS, NSGAIII-LWS, NSGAIII-TCH, NSGAIII-PBI, NSGAIII-AS, NSGAIII-SS, NSGAIII-PaS and NSGAIII-APS on DTLZ2 problem with 10-objectives

下载: 全尺寸图片 幻灯片

为进一步测试本文所提出的OSTWS在多样性维持上的性能, 我们在前沿面为线性(DTLZ1)、凹型(DTLZ2)、退化(DTLZ5)和不连续(DTLZ7)的问题上, 将NSGAIII-OSTWS与其他7个算法进行对比. 表6展示了上述算法在最新多样性评价指标CPF上的平均测试结果, 可以看出OSTWS在整体上取得了最佳的多样性性能.

表 6  OSTWS, LWS, TCH, PBI, AS, SS, PaS和APS方法在框架为NSGAIII, 测试问题集为DTLZ1, DTLZ2, DTLZ5和DTLZ7上获得的CPF值统计结果(均值和标准差). 每个实例算法中的最好结果以加粗突出显示

Table 6  The statistical results (mean and standard deviation) of the CPF values obtained by OSTWS, LWS, TCH, PBI, AS, SS, PaS and APS methods on the NSGAIII framework and DTLZ1, DTLZ2, DTLZ5 and DTLZ7 test problems. The best average value among the algorithms for each instance is highlighted in bold

Problem	m	NSGAIII-OSTWS	NSGAIII-LWS	NSGAIII-TCH	NSGAIII-PBI	NSGAIII-AS	NSGAIII-SS	NSGAIII-PaS	NSGAIII-APS
DTLZ1	3	1.374×10−3 (2.4×10−3)	5.495×10−4 (1.7×10−3)$\approx$	8.242×10−4 (2.7×10−3)$\approx$	4.558×10−4 (1.4×10−3)$\approx$	1.099×10−3 (2.3×10−3)$\approx$	0.000×100 (0.0×100)−	2.748×10−4 (1.2×10−3)$\approx$	4.021×10−4 (1.3×10−3)$\approx$
	5	1.436×10−4 (3.5×10−4)	8.930×10−5 (2.2×10−4)$\approx$	2.924×10−4 (9.7×10−4)$\approx$	2.837×10−4 (5.6×10−4)$\approx$	2.954×10−4 (5.9×10−4)$\approx$	5.953×10−5 (2.7×10−4)$\approx$	3.020×10−4 (5.0×10−4)≈	2.339×10−4 (4.1×10−4)$\approx$
	8	7.099×10−5 (1.1×10−4)	3.072×10−5 (6.0×10−5)$\approx$	1.083×10−4 (2.0×10−4)$\approx$	3.749×10−4 (7.7×10−4)≈	5.327×10−5 (1.1×10−4)$\approx$	2.757×10−5 (6.4×10−5)$\approx$	1.655×10−4 (4.5×10−4)$\approx$	1.068×10−4 (2.0×10−4)$\approx$
	10	1.657×10−4 (4.1×10−4)	7.355×10−5 (2.2×10−4)$\approx$	6.571×10-6 (1.7×10−5)−	1.422×10−4 (4.2×10−4)$\approx$	4.603×10−5 (1.2×10−4)$\approx$	1.399×10−4 (4.4×10−4)$\approx$	7.511×10−5 (2.4×10−4)$\approx$	8.130×10−5 (2.3×10−4)$\approx$
DTLZ2	3	5.698×10−1 (4.3×10−2)	3.218×10−1 (2.3×10−2)−	5.792×10−1 (3.5×10−2)$\approx$	6.891×10−1 (1.1×10−2)+	5.427×10−1 (4.5×10−2)−	1.684×10−1 (3.6×10−2)−	5.632×10−1 (3.1×10−2)$\approx$	6.837×10−1 (2.3×10−2)$+$
	5	5.993×10−1 (2.2×10−2)	1.585×10−1 (1.2×10−2)−	5.521×10−1 (4.1×10−2)−	7.114×10−1 (1.4×10−2)+	5.416×10−1 (4.7×10−2)−	1.307×10−1 (3.0×10−2)−	5.433×10−1 (4.1×10−2)−	7.108×10−1 (1.5×10−2)$+$
	8	3.780×10−1 (2.8×10−2)	5.395×10−2 (1.6×10−2)−	2.871×10−1 (4.2×10−2)−	4.085×10−1 (2.8×10−2)+	2.922×10−1 (2.4×10−2)−	3.258×10−2 (2.6×10−2)−	2.947×10−1 (2.4×10−2)−	3.682×10−1 (1.1×10−1)$\approx$
	10	2.185×10−1 (3.7×10−3)	2.729×10−2 (1.5×10−2)−	1.752×10−1 (4.3×10−2)−	1.914×10−1 (6.6×10−2)$\approx$	1.912×10−1 (2.1×10−2)−	3.958×10−2 (1.3×10−2)−	1.855×10−1 (1.9×10−2)−	1.900×10−1 (6.3×10−2)$\approx$
DTLZ5	3	6.043×10−1 (4.4×10−2)	5.616×10−1 (7.6×10−2)−	5.755×10−1 (7.9×10−2)$\approx$	6.053×10−1 (4.6×10−2)$\approx$	5.639×10−1 (5.4×10−2)−	5.423×10−1 (5.4×10−2)−	5.925×10−1 (5.9×10−2)$\approx$	6.092×10−1 (5.3×10−2)≈
	5	5.397×10−1 (7.5×10−2)	4.781×10−1 (4.9×10−2)−	3.670×10−1 (5.6×10−2)−	4.987×10−1 (4.5×10−2)−	2.654×10−1 (6.3×10−2)−	1.838×10−1 (4.1×10−2)−	2.452×10−1 (7.8×10−2)−	4.935×10−1 (6.0×10−2)−
	8	5.903×10−1 (1.2×10−1)	4.791×10−1 (7.8×10−2)−	5.093×10−1 (6.2×10−2)−	5.213×10−1 (8.9×10−2)$\approx$	4.770×10−1 (9.3×10−2)−	3.355×10−1 (1.3×10−1)−	3.963×10−1 (9.9×10−2)−	5.067×10−1 (8.9×10−2)−
	10	3.857×10−1 (5.1×10−2)	2.622×10−1 (5.2×10−2)−	3.066×10−1 (5.6×10−2)−	3.804×10−1 (4.8×10−2)$\approx$	2.635×10−1 (5.7×10−2)−	3.790×10−1 (1.4×10−1)$\approx$	2.391×10−1 (8.5×10−2)−	3.524×10−1 (4.4×10−2)−
DTLZ7	3	2.961×10−1 (4.3×10−2)	2.502×10−1 (4.3×10−2)−	2.853×10−1 (5.1×10−2)$\approx$	2.866×10−1 (3.9×10−2)$\approx$	2.835×10−1 (6.6×10−2)$\approx$	1.519×10−1 (3.6×10−2)−	2.676×10−1 (5.6×10−2)$\approx$	2.911×10−1 (4.8×10−2)$\approx$
	5	2.716×10−1 (3.4×10−2)	1.956×10−1 (2.8×10−2)−	2.760×10−1 (2.3×10−2)$\approx$	2.890×10−1 (4.2×10−2)$\approx$	2.622×10−1 (2.7×10−2)$\approx$	2.139×10−1 (3.5×10−2)−	2.530×10−1 (1.8×10−2)$\approx$	2.974×10−1 (3.1×10−2)+
	8	5.846×10−1 (1.0×10−1)	2.044×10−1 (3.4×10−2)−	3.897×10−1 (5.4×10−2)−	5.149×10−1 (4.7×10−2)−	3.996×10−1 (6.1×10−2)−	2.534×10−1 (3.7×10−2)−	3.618×10−1 (7.0×10−2)−	5.210×10−1 (4.9×10−2)−
	10	1.3102×10−1 (4.1×10−2)	2.657×10−1 (3.2×10−2)$+$	9.318×10−2 (2.0×10−2)−	1.994×10−1 (1.6×10−2)$+$	9.436×10−2 (1.5×10−2)−	2.663×10−1 (3.3×10−2)+	1.056×10−1 (2.4×10−2)−	2.015×10−1 (2.0×10−2)$+$
$+/-/\approx$			1/11/4	0/9/7	4/2/10	0/10/6	1/11/4	0/8/8	4/4/8

下载: 导出CSV 

| 显示表格

为直观地展示算法在平衡收敛性和多样性上的综合性能, 图4给出了各个算法在IGD⁺上的性能打分图, 分值越小表示该算法整体性能越好. 从图4可以看出, 算法NSGAIII-OSTWS获得了最小的IGD⁺打分值, 这表明与NSGAIII的变体相比, NSGAIII-OSTWS具有很强的综合性能.

2)算法整体性能验证与分析

为测试算法NSGAIII-OSTWS的综合性能, 将NSGAIII-OSTWS与9个先进的MaOEAs进行对比实验, 分别为NSGA-III^[25]、Two_arch2^[27]、SRA^[29]、SPEAR^[26]、DDEANS^[33]、HpaEA^[28]、ARMOEA^[22]、MaOEA-IT^[61]和PaRP/EA^[62]. 表7、表8和表9分别为上述算法在DTLZ、WFG和LSMOP测试问题集上所获得的IGD⁺统计结果.

表 7  NSGAIII-OSTWS, NSGAIII, Two_arch2, SRA, SPEAR, DDEANS, HpaEA, ARMOEA, MaOEA-IT和PaRP/EA在DTLZ1-7上上获得的IGD⁺值的统计结果

Table 7  The statistical results of the IGD⁺ values obtained by NSGAIII-OSTWS, NSGAIII, Two_arch2, SRA, SPEAR, DDEANS, hpaEA, ARMOEA, MaOEA-IT and PaRP/EA on DTLZ1-7

NSGAIII-OSTWS	vs	NSGAIII	Two_Arch2	SRA	SPEAR	DDEANS	HpaEA	ARMOEA	MaOEA-IT	PaRP/EA
+		0/28	1/28	5/28	1/28	2/28	2/28	2/28	2/28	1/28
−		27/28	26/28	22/28	25/28	24/28	25/28	24/28	26/28	23/28
$\approx$		1/28	1/28	1/28	2/28	2/28	1/28	2/28	0/28	4/28

下载: 导出CSV 

| 显示表格

表 8  NSGAIII-OSTWS, NSGAIII, Two_arch2, SRA, SPEAR, DDEANS, HpaEA, ARMOEA, MaOEA-IT和PaRP/EA在WFG1-9上上获得的IGD⁺值的统计结果

Table 8  The statistical results of the IGD⁺ values obtained by NSGAIII-OSTWS, NSGAIII, Two_arch2, SRA, SPEAR, DDEANS, HpaEA, ARMOEA, MaOEA-IT and PaRP/EA on WFG1-9

NSGAIII-OSTWS	vs	NSGAIII	Two_Arch2	SRA	SPEAR	DDEANS	HpaEA	ARMOEA	MaOEA-IT	PaRP/EA
+		1/36	0/36	0/36	0/36	5/36	0/36	0/36	0/36	0/36
−		35/36	26/36	35/36	35/36	30/36	36/36	36/36	36/36	34/36
$\approx$		0/36	0/36	1/36	1/36	1/36	0/36	0/36	0/36	2/36

下载: 导出CSV 

| 显示表格

表 9  NSGAIII-OSTWS, NSGAIII, Two_arch2, SRA, SPEAR, DDEANS, HpaEA, ARMOEA, MaOEA-IT和PaRP/EA在LSMOP1-9上获得的IGD⁺值的统计结果

Table 9  The statistical results of the IGD⁺ values obtained by NSGAIII-OSTWS, NSGAIII, Two_arch2, SRA, SPEAR, DDEANS, HpaEA, ARMOEA, MaOEA-IT and PaRP/EA on LSMOP1-9

NSGAIII-OSTWS	vs	NSGAIII	Two_Arch2	SRA	SPEAR	DDEANS	HpaEA	ARMOEA	MaOEA-IT	PaRP/EA
+		10/36	13/36	12/36	10/36	11/36	10/36	16/36	7/36	9/36
-		21/36	21/36	20/36	23/36	22/36	23/36	17/36	24/36	23/36
$\approx$		5/36	2/36	4/36	3/36	3/36	3/36	3/36	5/36	4/36

下载: 导出CSV 

| 显示表格

从表7, 表8和表9的数据可以看出, 与其它先进的MaOEAs相比, NSGAIII-OSTWS在绝大部分测试问题上取得了最佳IGD⁺值, 这表明NSGAIII-OSTWS在平衡收敛性和多样性上非常具有竞争力. 首先, 由表7, 表8和表9可以看出, NSGAIII-OSTWS的性能要明显优于经典算法NSGAIII, 说明OSTWS在很大程度上提高了NSGAIII的整体性能, 这再次验证了OSTWS的有效性. 其次, NSGAIII-OSTWS的整体性能要强于其它最新算法Two_arch2、SRA、SPEAR、DDEANS、HpaEA、ARMOEA、MaOEA-IT和PaRP/EA, 尤其是在规则问题上, 如DTLZ1-4和WFG4-9. 原因是NSGAIII-OSTWS在规则问题上易于预估出PF的形状, 从而有利于加速种群的收敛. 值得注意的是, DDEANS也获得了较好的性能, 原因是DDEANS采用了参考向量调整的方法, 从而能在不规则测试问题上, 如DTLZ7和WFG1-2, 较好地维持种群的多样性.

为直观展示各个算法在平衡种群收敛性和多样性上的能力, 图6给出了所有算法在10维DTLZ4问题上的最终种群分布图. 从图6可以看出, 算法NSGAIII-OSTWS获得的种群具有良好的收敛性和多样性, 而对比算法NSGA-III、Two_arch2、SRA、SPEAR、DDEANS、HpaEA、ARMOEA和MaOEA-IT获得的种群都没有收敛到PF, 这反映了NSGAIII-OSTWS的优越性. 此外, 为进一步观察各个算法的收敛性能, 图7给出了各个算法在DTLZ、WFG和LSMOP测试问题上的平均GD表现分, 分值越小表示该算法的收敛性性能越好. 从图7可以看出, 算法NSGAIII-OSTWS在绝大部分测试问题上都获得了最低的GD表现分, 表明与其它类型的算法相比, NSGAIII-OSTWS具有很强的收敛能力, 这归功于NSGAIII-OSTWS算法采用的OSTWS方法具有很高的搜索效率, 从而使得种群能快速的收敛到PF. 但对于退化和不连续的不规则测试问题DTLZ5-7, 由于较难准确预估出真实PF的形状, 导致NSGAIII-OSTWS在处理DTLZ5-7问题时收敛性会有所下降.

图 6  SRA, SPEAR, DDEANS, HpaEA, ARMOEA, MaOEA-IT和PaRP/EA在10维DTLZ4问题上所获得的解集

Fig. 6  Solution set of NSGAIII-OSTWS, NSGAIII, Two_arch2, SRA, SPEAR, DDEANS HpaEA, ARMOEA, MaOEA-IT and PaRP/EA on DTLZ4 problem with 10-objectives

下载: 全尺寸图片 幻灯片

图 7  NSGAIII-OSTWS, NSGAIII, Two_arch2, SRA, SPEAR, DDEANS, HpaEA, ARMOEA, MaOEA-IT和PaRP/EA在所有测试问题, 即DTLZ(Dx), WFG(Wx) 和LSMOP(Lx) 上的平均GD表现分, 分值越小, 算法的整体性能越好. 通过实线连接NSGAIII-OSTWS的得分, 以便易于评估分数

Fig. 7  Average performance score of NSGAIII-OSTWS, NSGAIII, Two_arch2, SRA, SPEAR, DDEANS, HpaEA, ARMOEA, MaOEA-IT and PaRP/EA on all test problems, namely DTLZ(Dx), WFG(Wx)and LSMOP(Lx). The smaller the score, the better the overall performance in terms of GD. The values of NSGAIII-OSTWS are connected by a solid line to easier assess the score

下载: 全尺寸图片 幻灯片

3)参数$ C $的敏感性分析

NSGAIII-OSTWS算法的核心是将各种问题的PF转换为凸型曲面, 其中参数$ C $用于控制预设凸曲面的曲率, 因此对算法的性能有着一定的影响. 由于预设曲面为凸形, 其曲率值$ C > 1$. 图8为不同预设凸曲线在参考向量w上获得的最优解示意图. 从中可以看出, 当$ 1< C <2 $时, 由参考向量w获得的最优解逐渐靠近w; 当$ C $ = 2时, w获得的最优解正好位于w上; 当$ C > 2$时, w获得的最优解逐渐远离w. 由于参考向量主要用于对种群多样性的管理, 最优解越靠近参考向量越有利于多样性的维护, 因此$ C $值取2相比其它取值更能维持种群的多样性. 为验证这一结论, 本小节在凹凸混合问题WFG1、凹问题WFG4、线性问题DTLZ1和不连续问题DTLZ7上测试了$ C $为{1.2, 2, 3, 4, 5, 6, 7, 8, 9, 10}的IGD⁺性能. 图9为实验结果, 可以看出, 随着$ C $值的增加, NSGAIII-OSTWS的整体性能先逐渐提升后逐渐恶化, 当$ C $ = 2时, 算法具有最佳的性能, 这验证了当$ C $值取2时算法具备良好性能这一结论.

图 9  不同$ C $值在WFG1, WFG4, DTLZ1和DTLZ7问题的3, 5, 8和10目标维度上的IGD⁺均值

Fig. 9  The median IGD⁺ values of different $ C $ values on WFG1, WFG4, DTLZ1 and DTLZ7 problems with 3-, 5-, 8-, and 10-objectives

下载: 全尺寸图片 幻灯片

图 8  不同预设凸曲线在参考向量w上获得的最优解示意图

Fig. 8  The optimal solution obtained by different preset convex curves on the reference vector w

下载: 全尺寸图片 幻灯片

4.   结论

为充分发挥权重求和搜索效率高的优势, 同时又能处理好PF形状为非凸的问题, 本文提出了一种基于目标空间转换权重求和的超多目标进化算法, 简称NSGAIII-OSTWS, 其中目标空间转换权重求和方法(OSTWS)将各种问题的PF转换为凸型曲面, 再对其进行优化求解. 为验证NSGAIII-OSTWS的有效性, NSGAIII-OSTWS与7个NSGAIII的变体以及9个最新的MaOEAs在WFG、DTLZ和LSMOP测试问题集上进行了实验对比. 实验结果表明, 相比其他算法, NSGAIII-OSTWS具备良好的竞争性能.

虽然所提算法NSGAIII-OSTWS在处理MaOPs上取得了优越的性能, 但仍有一些开放性的工作值得进一步的探索. 例如, 不规则问题的PF形状难以精确预估, 这势必导致个体映射的不准确进而影响算法的性能. 因此, 未来需要进一步研究如何更加精确地映射个体. 此外, 将本文所提出的算法应用于现实生产和生活中各类实际问题的求解具有重要的价值, 这也是未来需要进一步开展的工作. 本文所提算法的源代码已在https://github.com/CIA-SZU/LTT上公开.