2. 华南师范大学数据科学与工程学院，广东汕尾 516600
2. School of Data Science and Engineering, South China Normal University, Shanwei, Guangdong, 516600, China
科学研究与工程实践中不断涌现出需要同时优化3个以上目标的优化问题，即高维多目标优化问题(Many-objective Optimization Problem，MaOP)。MaOP各目标相互冲突的本质属性使其并不存在唯一的最优解，而往往是一组折中解的集合，即Pareto解集。进化算法(Evolutionary Algorithm，EA)作为一类基于种群的随机启发式算法，其求解过程不要求待解问题满足连续、可微等数学性质，且运行一次即可获得一组近似解，这些特点使得EA非常适于求解MaOP。迄今为止，已涌现出众多的高维多目标进化算法(Many-Objective Evolutionary Algorithm，MaOEA)。根据这些算法的主要思想和技术，可将它们大致分成如下几类。
① 改进支配关系的方法。这类方法通过提出新的支配关系或修改Pareto最优性的定义来改善算法的性能。代表性支配方法包括GPO(Generalized Pareto Optimality)[1]、RPS(Reference Points-based Strengthened dominance)[2]、DAV(Dynamical Angle Vector)[3]、CSDR(Controlled Strengthened Dominance Relation)[4]、改进的(M-1)-GPD(Generalized Pareto Dominance)[5]和CDD(dominance relation Combing Double Distances)[6]等。总体上，这些改进的支配方法可在一定程度上改善MaOEA的性能，但它们在进化过程中一般未动态调整收敛性与多样性的占比，而且一些支配方法需要预设参数，使用不便。
② 基于分解的算法。这类算法将待解的MaOP分解成若干单目标优化问题或一些更为简单的MOP(Multi-objective Optimization Problem)，然后协同求解。代表性算法包括MOEA/D-M2M [MOEA/D (Multiobjective Evolutionary Algorithm based on Decomposition) based on MOP to MOP][7]、NSGA-Ⅲ (Nondominated Sorting Genetic Algorithm Ⅲ)[8]、IM-MOEA (Inverse Modeling based Multiobjective Evolutionary Algorithm)[9]和RVEA (Reference Vector guided Evolutionary Algorithm)[10]等。但需指出的是，基于分解的MaOEA性能的好坏取决于其权重向量(或参考点)与待解问题的Pareto前沿形状是否一致，亦即这类算法的性能与权重向量(或参考点)在目标空间中的分布情况密切相关。
③ 基于指标的算法。这类算法将用于度量解集性能的指标作为算法环境选择的核心准则。典型范例包括基于Sharp-Ratio指标的POSEA[11]、基于R2指标的MOMBI-Ⅱ (Many objective metaheuristic based on the R2 indicator Ⅱ)[12]、基于IGD(Inverted Generational Distance)指标的MaOEA/IGD[13]，以及基于ISDE+ω指标的AMS-MOEA (MOEA with the proposed Adaptive Mating Selection)[14]等。这类算法有效纾解了因Pareto最优性和/或权重向量适配等局限对MaOP求解造成的困扰，提高了种群的选择压力，改善了算法的性能。
广泛使用的IGD指标[15]通过在待解问题真实Pareto前沿上均匀采样一定数目的参考点，累计每个参考点到算法所获近似解集中最近解点的欧氏距离，以此评估算法的收敛性与多样性。由于IGD指标可综合度量解集的收敛性和多样性且计算过程简洁，使得一些MaOEA将其用做环境选择的准则或依据。Tian等[16]提出一种基于IGD的增强型指标IGD-NS(IGD with noncontributing solutions detection)。该指标在IGD的基础上进一步考虑了那些对IGD值无贡献的解，使其能更全面地评估近似解集的质量。但需指出的是，基于IGD-NS指标的MaOEA在一些具有不同Pareto前沿形状的MaOP上通用性差且性能不佳。为解决通用性问题，Tian等[17]提出一种基于IGD-NS指标和参考点调整策略的AR-MOEA算法，在一定程度上改善了算法的性能及通用性。
尽管如此，目前基于IGD指标及其改进的IGD-NS指标的研究尚有提升空间，主要表现在：①IGD-NS指标虽然将非支配解分为贡献解和非贡献解，但是它未能根据非贡献解的分布情况做进一步的区分，在精细化度量解集的收敛性和多样性方面尚需提高；②对于大多数随机产生种群的MaOEA而言，算法初期数目有限的种群个体随机分布在巨大的目标空间，需要采取方法促使种群向Pareto前沿方向逼近，即强调收敛性；算法后期种群中大部分个体聚集在Pareto前沿附近，但它们可能拥挤或稀疏地分布于Pareto前沿附近的某些局部区域，群体多样性不佳，因而需要改善种群的多样性。
为解决上述问题，本研究在IGD-NS的基础上提出一种增强型的IGD-NS指标，即IGD-NSE(Enhanced IGD-NS indicator)，旨在通过精细化处理无贡献解并引入自适应策略，提升算法在MaOP上的综合性能。
1 背景知识不失一般性，一个具有n个决策变量，M个目标函数的最小化MaOP可形式化表示如下[3]：
| $ \left\{\begin{array}{l}\min y=F(x)=\left(f_{1}(x), f_{2}(x), \cdots, f_{M}(x)\right)^{\mathrm{T}} \\ \text { s.t.} x \in \varOmega\end{array}\right., $ | (1) |
式(1)中，$x=\left(x_{1}, x_{2}, \cdots, x_{n}\right)$，是决策(变量)空间$\varOmega$中的点；$\mathbb{R}^{M}$ 是目标空间，且$F: \varOmega \rightarrow \mathbb{R}^{M}$包含了$M$个实值目标函数。通常，这里的M≥4。
定义1 (Pareto支配) 设$x^{1}, x^{2} \in \varOmega$ 是式（1）中MaOP任意的两个解，称$x^{1}$ Pareto支配$x^{2}$（记为$\left.x^{1} \prec x^{2}\right)$ 当且仅当$\forall i \in(1: M): f_{i}\left(x^{1}\right) \leqslant f_{i}\left(x^{2}\right) \wedge \exists j \in(1: M): f_{j}\left(x^{1}\right)<f_{j}\left(x^{2}\right)$ 成立。
定义2 (Pareto最优解) $x^{*} \in \varOmega$ 是Pareto最优解当且仅当不存在其他的解$x \in \varOmega$ 使得$x \prec x^{*}$ 成立。Pareto最优解通常也称为Pareto非支配解或Pareto非劣解。
定义3 (Pareto最优解集) Pareto最优解集(Pareto optimal set，PS)是所有Pareto最优解的集合，即$\mathrm{PS}=\left\{x^{*}\right\}=\left\{x \in \varOmega \mid \neg \exists x^{\prime} \in \varOmega: x^{\prime} \prec x\right\}$。
定义4 (Pareto最优前沿) Pareto最优前沿(Pareto optimal front，PF)是PS在目标空间中的投影，即$\mathrm{PF}=\left\{F(x) \in \mathbb{R}^{M} \mid x \in \mathrm{PS}\right\}$。
定义5 (当前代种群的非劣解集ND) 设$P(t)$为MaOEA的第$t$ 代种群，个体$x^{*} \in P(t)$ 为种群的非劣解，当且仅当$\neg \exists x^{\prime} \in P(t): x^{\prime} \prec x^{*}。P(t)$ 中所有非劣解$x^{*}$ 组成的集合称为当前代种群的非劣解集NDS，即NDS $=\left\{x^{*}\right\}=\{x \mid x \in \left.P(t) \wedge \neg \exists x^{\prime} \in P(t): x^{\prime} \prec x\right\}$。
定义6 (极端解) 对于非劣解集NDS，若个体x∈NDS且在NDS中的某一目标上不存在比x还小的解，则称x为NDS中的极端解。
2 改进的IGD-NS指标 2.1 IGD-NS指标设P为MaOEA算法A获得的近似Pareto解集，R为从待解MaOP的PF上均匀采样获得的参考点集，则IGD的计算方法[15]如下：
| $ \operatorname{IGD}(P, R)=\frac{\sum\limits_{x \in R} \min\limits _{y \in P} \operatorname{dis}(x, y)}{|R|}, $ | (2) |
式(2)中，dis(x, y)表示参考点x与解点y之间的欧氏距离。IGD计算R中的每个点与P中解点的平均最小距离，它能同时度量P的收敛性与多样性，而且IGD值越小表明P的收敛性和多样性越好。特别地，如果IGD(P, R)=0，表明R是P的子集。另外，从IGD的计算过程不难发现，若P中存在某些非支配解，不是参考点集R中任何参考点的最近邻解，则这些解点对IGD值而言是无贡献的，亦即无贡献解(Noncontributing solution)[17]。设y*是近似Pareto解集P中相对于参考点集R的无贡献解，则y*满足如下定义：
| $ \neg \exists x \in R: \operatorname{dis}\left(x, y^{*}\right)=\min\limits _{y \in P} \operatorname{dis}(x, y) 。$ | (3) |
Tian等[17]进一步在IGD指标中考虑了无贡献解，提出了可筛选无贡献解的IGD指标，即IGD-NS指标，该指标定义如下：
| $ \begin{align*} & \;\;\;\; \operatorname{IGD}-\mathrm{NS}(P, R)=\sum\limits_{x \in R} \min\limits _{y \in P} \operatorname{dis}(x, y)+\sum\limits_{y^{*} \in P^{*}} \min\limits _{x \in R} \\ & \operatorname{dis}\left(y^{*}, x\right) , \end{align*} $ | (4) |
式(4)中, P*是解集P中无贡献解组成的集合，P和R的含义同式(2)和(3)。式(4)右边第1项与IGD类似，它反映了种群P的收敛性和多样性；第2项是P*中各无贡献解与R中参考点的最小距离之和，它使得P*中无贡献解的数目最小化。因此，当算法获得的近似Pareto解集收敛性和多样性俱佳且其中的无贡献解尽可能少时，IGD-NS值就越小(越好)。
2.2 IGD-NSE指标从式(4)不难看出，IGD-NS指标定义中虽然考虑了无贡献解，但是指标并未根据这些无贡献解的分布情况对其做进一步的区分，未能细致刻画种群中不同个体对收敛性和多样性的影响。另外，MaOEA在初期通常更加强调收敛性以促使种群不断逼近PF，而在后期种群分布在PF附近，但分布可能不均匀，需要强调多样性。总体上，MaOEA需要在进化过程中自适应调整收敛性和多样性的占比，以获得高质量的解集。
基于此，本文提出一种增强型的IGD-NS指标，即IGD-NSE指标。以下给出若干与IGD-NSE指标密切相关的定义，其中P为MaOEA算法A获得的近似Pareto解集，R为从待解MaOP的PF上均匀采样获得的参考点集，P*是P中无贡献解组成的集合，P′=P\P*为P中贡献解组成的集合。
定义7 (强贡献解与强贡献解集) 设x是P′中任一个体，若x与R中两个或两个以上的参考点均具有最小的欧氏距离，则称x为强贡献解，P′中的所有强贡献解组成其强贡献解集PS。
定义8 (弱贡献解与弱贡献解集) 设x是P′中任一个体，若x仅与R中一个参考点具有最小的欧氏距离，则称x为弱贡献解，P′中的所有弱贡献解组成其弱贡献解集PW。
定义9 (候选解与候选解集) 设y是P*中任一个体，若y为距离强贡献解最近的个体，则称y为候选解，P*中所有候选解组成其候选解集PC。
定义10 (非候选解与非候选解集) 设PC是P*的候选解集，则PN=P*\PC为P*的非候选解集，PN中任意的个体称为非候选解。
为便于理解上述定义，这里以二维目标空间为例，解释强贡献解、弱贡献解、候选解和非候选解。图 1中r1、r2、r3为目标空间从PF上均匀采样的3个参考点，p1、p2、p3、p4、p5和p6为种群中的6个个体，其中p4与参考点r2、r3均具有最小距离，因此p4为强贡献解，而p1仅与r1具有最小距离，则p1为弱贡献解，p5为距离强贡献解p4最近的个体，因此p5为候选解，剩下的p2、p3、p6为非候选解。
|
| 图 1 强贡献解、弱贡献解、候选解和非候选解示意图 Fig. 1 Schematic diagram of strong contributing solution, weak contributing solution, candidate solution, and non-candidate solution |
在上述定义的基础上，IGD-NSE指标可定义如下：
| $ \begin{align*} & \;\;\;\; \operatorname{IGD}-\mathrm{NSE}(P, R)=\sum\limits_{x \in R} \min\limits _{y \in P} \operatorname{dis}(x, y)+ \\ & \sum\limits_{y \in P^{C}} \min\limits _{x \in R} \operatorname{dis}(y, x)+ \\ & \sum\limits_{y \in P^{N}}\left(\left(1+\omega \cdot \frac{\underset{z \in P^{\prime} \wedge x \in R}{\arccos }(\overrightarrow{x z}, \overrightarrow{x y})}{M}\right) \cdot \min\limits _{x \in R} \operatorname{dis}(y, x)\right), \end{align*} $ | (5) |
式(5)中，ω=t/Tmax，t表示算法当前的进化代数，Tmax表示算法最大进化代数，其他符号的含义同前述。
式(5)右边第1项与IGD指标的定义类似，其考察参考点与近似Pareto解集中最近解的距离，第2项刻画了候选解集个体与参考点之间的最近距离，第3项表征非候选解集个体与参考点之间的最近距离且该距离与种群所处的进化阶段、待解问题目标数目、不同类型解之间的分布等自动关联。由此可得，式(5)能够较细致地刻画贡献解、候选解和非候选解对解群收敛性与多样性的影响。IGD-NSE指标值的大小体现了近似解集的质量：当解集中个体收敛性与多样性越好时，第1项的值越小；当解集中贡献解的数目越多，无贡献解数目越少，第2项的值越小；当解集中存在候选解和非候选解时，其在最大程度上选择候选解，这样可降低第3项的值，但若一定要选择非候选解，则自然地选择具有较好收敛性和多样性的非候选解。故IGD-NSE指标值越小表明近似解集的质量越好。在进化初期，ω值较小，第3项的值取决于非候选解与参考点的距离，即强调收敛性；而在进化后期，ω值较大，将更多地强调多样性。此外，待解问题的目标空间维度M越大，算法所生成的解群越具备多样性，此时需降低多样性占比以强调收敛性。如此便从总体上表征了IGD-NSE指标值越小，解群收敛性与多样性越好。
为进一步理解上述定义，图 2以二维目标空间为例，解释强贡献解、弱贡献解、候选解、非候选解以及IGD-NSE指标。该图中的r1、r2、r3为均匀采样的参考点，p1、p2、p3、p4、p5、p6为种群中6个个体。根据前面的定义，图 2(a)中p4为强贡献解，p1为弱贡献解，p5为候选解，p2、p3、p6为非候选解。在进化前期(t较小)，如果要从种群中选取5个个体进入下一代，则除了选中p4、p1、p5之外，还需从p2、p3、p6中选中2个个体。由于d3 < d2 < d6且IGD-NSE指标在进化的前期强调收敛性，因此p3和p2将被选中并进入下一代。类似地，图 2(b)中p5为强贡献解，p1为弱贡献解，p6为候选解，p2、p3、p4为非候选解。同样，如果需选择5个个体进入下一代，则除了p5、p1和p6，还需从p2、p3、p4中选出2个个体。显然，由于θ1 < θ3 < θ2且此时种群处于进化后期(t较大)，IGD-NSE指标更加强调多样性，因此p3和p4将被选中进入下一代。
|
| 图 2 利用IGD-NSE实施环境选择示意图 Fig. 2 Schematic diagram of implementing environmental selection based on IGD-NSE |
3 MOEA/IGD-NSE算法
这里将IGD-NSE指标嵌入经典的MOEA框架，构造出MOEA/IGD-NSE算法，其核心思想是以迭代方式逐一删除种群中对IGD-NSE值贡献最小的个体，直至满足种群规模大小。算法1给出了MOEA/IGD-NSE的完整流程。
算法1 MOEA/IGD-NSE的流程
输入：种群P的规模NP，参考点集R的规模NR，最大进化代数Tmax。
输出：最终解群P。
1.初始化：
1.1 初始化迭代计数器t=0；
1.2 随机生成初始化种群P←RandomInitialize(NP)；
2. 利用P更新参考点集R←UpdateReferenceSet(P, NR)；
3.WHILE (t < Tmax)
4. 利用交叉变异算子产生后代种群并与父代种群合并: P←P∪Variation(P, NP)；
5. 更新参考点集R←UpdateReferenceSet(R∪P)；
6. 利用环境选择策略产生下一代种群P←EnvironmentalSelection(P, R, NP)；
7. t=t+1；
8.END WHILE
9.输出最终解群P。
算法首先初始化种群与参考点集，随后进入迭代：利用二进制交叉和多项式变异算子生成后代种群并与父代合并，更新参考点集后，再通过环境选择策略筛选出下一代种群。这一过程持续至达到最大进化代数，最终输出优化后的解集。
算法2 UpdateReferenceSet的流程
输入：当前种群P，参考点集R的规模NR。
输出：更新后的参考点集R。
1. 将种群P中非支配解复制到NDS集合，即NDS←NondominatedSolution(P)；
2. 将NDS中的极端解复制到参考点集R中，即R←ExtremeSolution(NDS)；
3.IF |R|>NR
4. 从R中随机地删除(|R|-NR)个个体；
5.ELSE
6. WHILE |R| < NR且|R| < |NDS|
7. p←argmaxp∈NDS\R$\min\limits_{q \in R}$arccosine(p, q)；
8. R←R∪{p}；
9. END WHILE
10.END IF
11.输出更新后的R。
算法2描述了参考点集R的更新策略。算法首先在种群P中提取所有非支配解，构建NDS；然后在NDS中筛选出极端解作为初始参考点集R；最后，如果R的规模大于NR，则随机地从R中删除(|R|-NR)个个体直至|R|=NR，否则逐个向R中添加个体p。此处p为NDS\R中的个体，该个体与参考集R内距离最近的个体q所构成的夹角在全部候选个体中最大。总体上，这种更新策略能够在R中保存那些具有较好多样性的非支配解个体。通常，现实中MaOP的PF是未知的，也就是说，在运用IGD-NSE指标度量解集质量时无法从真实PF上采样到均匀分布的参考点，因此，通过保留NDS的极端解并考察NDS中剩余个体与R中参考点的角度来确保R具有较好的分布性，其实质是对真实PF采样的一种合理替代。
算法3 EnvironmentalSelection的流程
输入：合并种群P，参考点集R，种群规模NP。
输出：下一代种群P。
1. F←NondominatedSort(P)；
2. P←F1∪F2∪…∪Fk；//这里的k为满足|F1∪F2∪…∪Fk| < NP的最大取值。
3. WHILE |Fk+1|>NP -|P|
4. 利用公式(6)，从Fk+1中找到个体y′；
5. 将y′从Fk+1中删除: Fk+1←Fk+1\{y′}；
6.END WHILE
7.P←P∪Fk+1；
8.输出下一代种群P。
算法3在开始阶段对合并种群P实施非支配排序，将P划分成若干非支配层F1，F2，…需要指出的是，这里采用Zhang等[18]提出的ENS(Efficient Nondominated Sort)方法对P进行高效地划分。随后，将前k个非支配层中的所有个体全部加入P中。如果|Fk+1|>NP-|P|，则需逐一地从Fk+1中选出个体y′予以删除。这里的y′满足式(6)：
| $ y^{\prime}=\underset{y \in F_{k+1}}{\operatorname{argmin}} \operatorname{IGD}-\mathrm{NSE}\left(F_{k+1} \backslash\{y\}, R\right) 。$ | (6) |
将Fk+1中所有留存个体添加到种群P，并输出下一代种群P。不难看出，这里的环境选择策略与NSGA-Ⅱ (Nondominated Sorting Genetic Algorithm Ⅱ)算法相似，首要准则采用了基于支配的选择，辅以IGD-NSE指标筛选最末非支配层上的个体。根据式(6)，对IGD-NSE值贡献最小的个体将被删除。
4 实验与结果分析 4.1 对比算法为验证MOEA/IGD-NSE的性能，这里选取4种高效的MaOEA如RVEA[10]、MaOEA/IGD[13]、MOEA/IGD-NS[16]、AR-MOEA[17]作为对比算法以检验本文算法的性能。RVEA是一种基于参考点集和角度惩罚距离(Angle-Penalized Distance，APD) 的MaOEA，该算法与MOEA/IGD-NSE类似，在进化过程中均利用了均匀采样的参考点集。MaOEA/IGD是一种基于IGD指标的MaOEA。与MOEA/IGD-NSE类似，MaOEA/IGD利用一种兼容Pareto支配的非支配排序方法对种群进行划分，这里选用MaOEA/IGD作为基于性能指标算法的典型范例。MOEA/IGD-NS是一种基于IGD-NS指标的多目标进化算法，而MOEA/IGD-NSE是在对IGD-NS指标进行改进的基础上发展而来，通过对比实验可以检验改进效果。AR-MOEA在MOEA/IGD-NS框架的基础上设计了一种参考点可调整的策略以求解具有不同PF形状的MaOP，它是近年来发展起来的一种较为经典高效的MaOEA，与其进行对比可以测试本文算法的先进程度。
4.2 测试问题实验选取DTLZ系列[19]的DTLZ1-DTLZ4问题，以及MaF系列[20]的MaF1-MaF4问题为测试问题。这些问题支持目标数扩展，且其真实PF已知，便于计算性能指标；同时，这些测试问题的PF具有不同的特征，能够对MaOEA构成较大的挑战。DTLZ和MaF系列测试问题的特征如下：DTLZ1为线性、多模态，DTLZ2为凹型，DTLZ3为凹型、多模态，DTLZ4为凹型、有偏；MaF1为线性，MaF2为凹型，MaF3为凸型、多模态，MaF4为凹型、多模态。
4.3 性能指标IGD指标度量了真实Pareto前沿到所获近似Pareto解集之间的距离。由于实验采用的测试问题的真实PF是已知的，通过在真实PF上均匀采样，并计算这些采样点到算法所获近似Pareto解点之间的距离，则既能反映解集的收敛性又能反映解集的多样性。假设P是算法获得的近似Pareto解集，R是MOP或MaOP真实PF上均匀采样获得的参考点集，则IGD指标可利用式(7)进行计算：
| $ \operatorname{IGD}(P, R)=\frac{1}{|R|} \sum\limits_{i=1}^{|R|} \text { Dist }_{i}, $ | (7) |
其中，Dist $_{i}=\min\limits _{j=1}^{|P|} \sqrt{\sum\limits_{k=1}^{m}\left(\frac{f_{k}\left(r_{i}\right)-f_{k}\left(p_{j}\right)}{f_{k}^{\text {max }}-f_{k}^{\text {min }}}\right)^{2}}$ 为归一化后的最小欧氏距离，$f_{k}^{\max }$ 和$f_{k}^{\min }$分别表示集合R在第k个目标上获得的最大值和最小值；$r_{i} \in R, i=1$，$2, \cdots, |R|, p_{j} \in P, j=1, 2, \cdots, |P|$。实验中对各测试函数采样10 000个均匀分布的Pareto最优目标解点作为真实PF的代表来计算IGD值。
4.4 统计方法为减少随机因素对性能评估的影响，实验中各算法在每一个测试实例中均独立执行30次(每次使用不同的随机数种子)以获得IGD指标的均值和方差。另外，实验利用显著水平为0.05的Wilcoxon秩和检验来分析各算法所获得近似解集的性能在统计意义上的差异。符号“+”“-”和“=”分别表示对比算法的IGD值明显优于、劣于和无差别于MOEA/IGD-NSE。
4.5 实验环境本文所有实验均在ASUS FL5600L PC上执行，PC配置如下：CPU为AMD A10-8700P、1.8 GHz主频、8.0 G内存、Windows 7 X64位操作系统，所有算法均在PlatEMO平台[21]上实现。
4.6 实验参数实验中所涉及的参数包括各算法共有参数和特有参数。①共有参数方面：为公平起见，不同算法在相同测试实例上执行相同的评估次数EN，各算法在不同测试实例上执行的代数(T)取决于评估次数和种群规模(N)，且满足T=EN/N。对于3-目标的测试问题，实验分配30 000次函数评估，对于5-、8-、10-和15-目标的测试问题，实验分配50 000次函数评估。另外，各算法均采用仿二进制交叉(SBX)和多项式变异(PM)产生新个体，其中SBX交叉的概率(pc)与分布指数(ηc)分别取1与20，PM的变异概率(pm)与分布指数(ηm)分别取1/n(n为决策变量数目)与20。②特有参数方面：RVEA的惩罚参数ɑ取值为2，调整参考向量频度的参数δ取0.1；MaOEA/IGD中基于分解的最差点估计法(DNPE)的参数λ设为100；MOEA/IGD-NS的外部档案的规模NA设为500。
4.7 实验结果及分析表 1给出了5种算法在3-、5-、8-、10-和15-目标的DTLZ1-DTLZ4测试问题上获得的IGD均值和方差。其中，MOEA/IGD-NSE在20个测试例上获得10个最佳的IGD均值(每一行中的最佳值用粗体突出显示，下同)，AR-MOEA获得了4个最佳的IGD均值，RVEA和MOEA/IGD-NS均获得3个最佳的IGD均值，而MaOEA/IGD未能获得任何最佳的IGD均值。从表 1的Wilcoxon秩和检验结果(表中最末一行)来看，本文的MaOEA/IGD-NSE相对于RVEA、MaOEA/IGD、MOEA/IGD-NS和AR-MOEA所获得的净胜得分(优于的数目减去劣于的数目，下同)分别为4、16、10和7。由此可见，MOEA/IGD-NSE在求解DTLZ系列问题时具有显著较优的性能。
| 测试问题 Test problem |
目标数目 Objective number |
RVEA | MaOEA/IGD | MOEA/IGD-NS | AR-MOEA | MOEA/IGD-NSE |
| DTLZ1 | 3 | 1.9821e+1 (4.46e+0) - | 8.8397e+1 (2.11e+1) - | 1.6164e+1 (6.54e+0) = | 2.1861e+1 (3.50e+1) = | 1.4930e+1 (6.29e+0) |
| 5 | 1.8900e+1 (4.99e+0) - | 5.4164e+1 (2.18e+1) - | 8.7848e+1 (1.77e+1) - | 1.8816e+1 (5.73e+0) - | 1.5010e+1 (5.19e+0) | |
| 8 | 8.6858e+0 (2.22e+0) - | 4.1289e+1 (1.03e+1) - | 2.9468e+2 (3.54e+1) - | 1.4782e+1 (8.74e+0) - | 7.0354e+0 (2.81e+0) | |
| 10 | 1.2756e+1 (3.28e+0) - | 2.6396e+1 (1.37e+1) - | 2.8429e+2 (3.07e+1) - | 1.2472e+1 (6.02e+0) - | 5.7797e+0 (2.49e+0) | |
| 15 | 2.8506e+0 (1.95e+0) - | 1.0210e+1 (4.51e+0) - | 2.3234e+2 (1.83e+1) - | 2.5805e+0 (1.71e+0) = | 1.7439e+0 (8.35e-1) | |
| DTLZ2 | 3 | 5.5721e-2 (4.76e-4) + | 4.3588e-1 (1.78e-1) - | 5.4913e-2 (6.26e-4) + | 1.0397e-1 (8.52e-3) - | 9.9773e-2 (7.95e-3) |
| 5 | 1.7094e-1 (1.09e-3) + | 2.3442e-1 (3.56e-2) + | 1.7819e-1 (2.76e-3) + | 1.6696e-1 (3.20e-4) + | 2.4328e-1 (7.13e-3) | |
| 8 | 4.4736e-1 (2.56e-2) + | 7.6445e-1 (1.28e-1) - | 6.1713e-1 (7.05e-2) - | 3.6332e-1 (5.74e-3) + | 4.7824e-1 (1.94e-2) | |
| 10 | 4.9432e-1 (1.82e-2) = | 6.3444e-1 (1.83e-1) - | 1.3365e+0 (9.90e-2) - | 4.9931e-1 (1.18e-2) = | 4.9518e-1 (1.15e-2) | |
| 15 | 6.3808e-1 (2.93e-2) + | 9.6505e-1 (9.98e-2) - | 1.9174e+0 (1.58e-1) - | 6.1716e-1 (1.55e-3) + | 7.8669e-1 (3.35e-2) | |
| DTLZ3 | 3 | 6.6338e+1 (1.33e+1) - | 2.0243e+2 (2.18e+1) - | 3.8871e+1 (1.36e+1) = | 4.4257e+1 (1.48e+1) = | 4.2153e+1 (1.78e+1) |
| 5 | 7.8266e+1 (1.78e+1) - | 1.7427e+2 (5.22e+1) - | 7.6987e+1 (2.53e+1) - | 4.8800e+1 (1.74e+1) - | 3.7537e+1 (9.75e+0) | |
| 8 | 4.9006e+1 (1.52e+1) - | 1.5106e+2 (3.93e+1) - | 9.6806e+2 (1.09e+2) - | 4.3753e+1 (1.35e+1) - | 3.6065e+1 (1.18e+1) | |
| 10 | 5.8960e+1 (1.77e+1) - | 1.0082e+2 (3.78e+1) - | 1.2291e+3 (1.02e+2) - | 6.0086e+1 (2.71e+1) - | 3.1299e+1 (1.01e+1) | |
| 15 | 1.2305e+1 (7.38e+0) - | 2.9673e+1 (9.84e+0) - | 1.2323e+3 (9.13e+1) - | 1.1181e+1 (5.94e+0) - | 8.0098e+0 (5.34e+0) | |
| DTLZ4 | 3 | 1.0744e-1 (8.43e-2) + | 5.3644e-1 (2.15e-1) - | 2.1447e-1 (2.57e-1) + | 4.2473e-1 (2.75e-1) - | 3.5998e-1 (3.10e-1) |
| 5 | 3.1243e-1 (2.28e-2) - | 3.9937e-1 (1.99e-1) - | 2.1738e-1 (8.64e-2) + | 3.0587e-1 (3.61e-2) - | 2.4799e-1 (3.35e-2) | |
| 8 | 4.7015e-1 (2.85e-2) = | 5.3253e-1 (1.07e-1) - | 6.1333e-1 (6.37e-2) - | 4.8989e-1 (1.65e-2) - | 4.6131e-1 (1.08e-2) | |
| 10 | 4.8145e-1 (8.80e-3) + | 5.1216e-1 (6.99e-2) = | 1.2138e+0 (6.88e-2) - | 4.6326e-1 (6.08e-3) + | 5.0196e-1 (1.12e-2) | |
| 15 | 6.3219e-1 (5.56e-3) + | 7.0271e-1 (4.57e-2) = | 1.5419e+0 (1.33e-1) - | 6.9080e-1 (1.70e-2) = | 6.8575e-1 (1.70e-2) | |
| +/-/= | 7/11/2 | 1/17/2 | 4/14/2 | 4/11/5 | ||
| Note: “+”“-”, and “=” indicate that the result is significantly better than, significantly worse than, and statistically indifferent to the MOEA/IGD-NSE algorithm, respectively. | ||||||
表 2给出了5种算法在3-、5-、8-、10-和15-目标的MaF1-MaF4测试实例上获得的IGD均值和方差。其中，MOEA/IGD-NSE、AR-MOEA和MOEA/IGD-NS均获得了5个最佳的IGD均值，RVEA和MaOEA/IGD分别获得了3个和2个最佳的IGD均值。从表 2的Wilcoxon秩和检验结果(表中最末一行)来看，MOEA/IGD-NSE相对于RVEA、MaOEA/IGD、MOEA/IGD-NS和AR-MOEA的净胜得分分别为10、12、5和5。由此可见，MOEA/IGD-NSE较其他对比算法在MaF系列问题上具有较优的IGD性能。究其原因，为刻画种群中各解点对收敛性与多样性的贡献，MOEA/IGD-NSE将无贡献解进一步分成候选解和非候选解；同时，考虑算法在不同进化阶段对收敛性和多样性的要求，利用IGD-NSE指标有效改善了算法总体上的性能。
| 测试问题 Test problem |
目标数目 Objective number |
RVEA | MaOEA/IGD | MOEA/IGD-NS | AR-MOEA | MOEA/IGD-NSE |
| MaF1 | 3 | 8.2221e-2 (1.41e-4) - | 1.5730e-1 (3.34e-3) - | 4.1732e-2 (3.73e-4) + | 6.4699e-2 (3.26e-3) = | 6.6663e-2 (4.58e-3) |
| 5 | 2.9498e-1 (2.05e-2) - | 2.6176e-1 (1.42e-2) - | 1.1926e-1 (2.69e-3) + | 1.4490e-1 (6.27e-3) + | 1.5590e-1 (4.21e-3) | |
| 8 | 5.0144e-1 (5.24e-2) - | 3.6378e-1 (1.59e-2) - | 2.4919e-1 (8.33e-3) + | 2.4223e-1 (7.97e-3) + | 2.6804e-1 (5.93e-3) | |
| 10 | 5.4523e-1 (8.11e-2) - | 3.5223e-1 (1.73e-2) - | 3.1106e-1 (1.03e-2) - | 2.9247e-1 (9.51e-3) - | 2.7909e-1 (5.99e-3) | |
| 15 | 6.5663e-1 (9.29e-2) - | 4.3123e-1 (2.50e-2) - | 3.9029e-1 (2.24e-2) + | 3.7367e-1 (2.08e-2) + | 4.1777e-1 (1.34e-2) | |
| MaF2 | 3 | 4.3347e-2 (1.80e-3) + | 1.8028e-1 (1.08e-1) - | 2.9371e-2 (3.99e-4) + | 3.8506e-2 (2.05e-3) + | 5.5803e-2 (4.39e-3) |
| 5 | 1.1538e-1 (1.20e-3) = | 1.6564e-1 (2.29e-2) - | 1.0154e-1 (2.61e-3) + | 1.2182e-1 (5.86e-3) - | 1.1728e-1 (6.11e-3) | |
| 8 | 4.4043e-1 (1.74e-1) - | 4.2202e-1 (3.19e-2) - | 2.4829e-1 (1.47e-2) = | 1.8280e-1 (5.42e-3) + | 2.5572e-1 (3.52e-2) | |
| 10 | 4.3496e-1 (1.83e-1) - | 4.7789e-1 (3.28e-2) - | 2.7631e-1 (1.55e-2) - | 1.8331e-1 (4.58e-3) + | 2.4788e-1 (1.59e-2) | |
| 15 | 7.1690e-1 (1.18e-1) - | 4.9949e-1 (2.27e-2) - | 3.3997e-1 (2.07e-2) - | 3.1131e-1 (3.35e-2) = | 3.1627e-1 (3.89e-2) | |
| MaF3 | 3 | 4.4958e+4 (7.12e+4) - | 8.2758e+5 (3.94e+6) - | 7.9574e+3 (2.66e+4) = | 8.6183e+3 (4.93e+3) - | 2.7897e+3 (1.74e+3) |
| 5 | 1.0697e+4 (5.77e+3) = | 4.9465e+3 (4.30e+3) + | 8.9858e+4 (1.05e+5) - | 8.6494e+4 (2.26e+4) - | 9.6679e+3 (5.65e+3) | |
| 8 | 2.5039e+3 (9.90e+2) + | 2.5153e+3 (1.72e+3) + | 2.3809e+11 (2.31e+11) - | 2.6469e+4 (1.93e+4) - | 5.5873e+3 (4.60e+3) | |
| 10 | 7.2008e+3 (3.70e+3) = | 1.7267e+3 (1.14e+3) + | 2.6346e+11 (3.58e+11) - | 3.3325e+5 (4.80e+5) - | 1.2303e+4 (1.07e+4) | |
| 15 | 2.2107e+2 (1.47e+2) + | 2.8708e+2 (2.77e+2) + | 2.5077e+11 (2.41e+11) - | 2.4013e+4 (2.96e+4) - | 1.0435e+4 (2.61e+4) | |
| MaF4 | 3 | 1.8912e+2 (5.58e+1) - | 4.3264e+2 (1.19e+2) - | 1.2854e+2 (5.21e+1) = | 1.9515e+2 (6.52e+1) - | 1.3003e+2 (4.13e+1) |
| 5 | 5.5571e+2 (1.99e+2) - | 6.1105e+2 (1.83e+2) - | 5.3523e+2 (2.03e+2) - | 5.2389e+2 (2.70e+2) = | 4.0154e+2 (1.86e+2) | |
| 8 | 2.5011e+3 (1.37e+3) - | 3.6924e+3 (1.19e+3) - | 4.5916e+3 (1.58e+3) - | 2.2477e+3 (1.07e+3) - | 1.4742e+3 (8.51e+2) | |
| 10 | 8.0587e+3 (4.41e+3) = | 1.6602e+4 (5.49e+3) - | 1.9929e+4 (1.63e+4) - | 1.7781e+4 (6.24e+3) - | 8.8459e+3 (3.01e+3) | |
| 15 | 3.3583e+4 (2.76e+4) - | 1.8533e+5 (1.09e+5) - | 1.6834e+5 (7.37e+4) - | 3.8093e+4 (2.38e+4) - | 2.0166e+4 (2.57e+4) | |
| +/-/= | 3/13/4 | 4/16/0 | 6/11/3 | 6/11/3 | ||
| Note: “+”“-”, and “=” indicate that the result is significantly better than, significantly worse than, and statistically indifferent to the MOEA/IGD-NSE algorithm, respectively. | ||||||
为直观地显示算法的求解结果，图 3展示了5种算法在10-目标的DTLZ2[简记为DTLZ2(10)]测试问题上获得近似解的平行坐标。这里的近似解集为各算法在30次独立运行中所获得的最接近于IGD均值的解集。从图 3可以看出，MOEA/IGD-NSE和RVEA在10-目标的DTLZ2测试问题上获得解群的收敛性和分布性均较好，而MOEA/IGD-NS与AR-MOEA所获解集的收敛性较差，MaOEA/IGD在第1-3个目标上的分布性较差。因此，从图 3的直观结果来看，MOEA/IGD-NSE在DTLZ2(10)测试问题上的收敛性与多样性较好，究其原因，DTLZ2测试问题的Pareto前沿为凹型，这使得该问题在目标数增加时对算法的全局搜索能力构成了显著挑战。
|
| 图 3 5种算法在10-目标的DTLZ2测试问题上获得的近似集 Fig. 3 Approximate solution sets obtained by five algorithms on DTLZ2(10) test instance |
此外，为直观地呈现5种算法的收敛性速度，图 4描绘了5种算法在15-目标的DTLZ3测试问题上获得的IGD均值随评估次数增长而变化的轨迹。为获得稳定且可靠的结果，各算法在测试实例上均独立执行30次，每次运行所需的最大评估次数为1×105。从图 4可以看出，随着评估次数的增大，5种算法所获得的IGD均值总体上表现出变小的趋势。但相对而言，MOEA/IGD-NSE获得的IGD均值的变化趋势最好，RVEA和AR-MOEA次之，再到MaOEA/IGD，而MOEA/IGD-NS相对较差。MOEA/IGD-NSE、RVEA与AR-MOEA在经历约4×104次评估后，其IGD均值能较快地下降至一个相对较小的值，并在后续进化过程中保持缓慢变小且趋于稳定的趋势。MaOEA/IGD在经历约3×104次评估后，其IGD均值能下降至一个居中大小的值并趋近稳定，而MOEA/IGD-NS随评估次数增长，IGD均值波动较大。由IGD指标的定义可知，IGD值越小，则算法所获得近似解集的收敛性与多样性效果越好，即解集质量越高。图 4中IGD曲线的变化轨迹直观地表明了MOEA/IGD-NSE相比其他4种算法在15-目标的DTLZ3测试问题上能较快地获得高质量的近似解集。
|
| 图 4 5种算法在15-目标的DTLZ3测试问题上获得的IGD均值变化曲线 Fig. 4 Curves of IGD obtained by five algorithms on DTLZ3(15) test instance |
5 结论
鉴于目前多目标进化算法中一些基于指标和参考向量(参考点)的方法存在诸多不足，本研究提出了一种可随进化过程自适应平衡收敛性与多样性的新指标IGD-NSE，并设计了相应的高维多目标进化算法MOEA/IGD-NSE。实验结果表明，在DTLZ和MaF系列测试问题上，该算法相比其他经典算法展现出更优的收敛性与多样性，是一种具有良好应用前景的多目标进化算法。
| [1] |
ZHU C W, XU L H, GOODMAN E D. Generalization of Pareto-optimality for many-objective evolutionary optimization[J]. IEEE Transactions on Evolutionary Computation, 2016, 20(2): 299-315. DOI:10.1109/TEVC.2015.2457245 |
| [2] |
GU Q H, CHEN H Y, CHEN L, et al. A many-objective evolutionary algorithm with reference points-based strengthened dominance relation[J]. Information Sciences, 2021, 554: 236-255. DOI:10.1016/j.ins.2020.12.025 |
| [3] |
谢承旺, 余伟伟, 郭华, 等. DAV-MOEA: 一种采用动态角度向量支配关系的高维多目标进化算法[J]. 计算机学报, 2022, 45(2): 317-333. |
| [4] |
SHEN J T, WANG P, WANG X J. A controlled strengthened dominance relation for evolutionary many-objective optimization[J]. IEEE Transactions on Cybernetics, 2022, 52(5): 3645-3657. DOI:10.1109/TCYB.2020.3015998 |
| [5] |
ZHU S W, XU L H, GOODMAN E D, et al. A new many-objective evolutionary algorithm based on generalized Pareto dominance[J]. IEEE Transactions on Cybernetics, 2022, 52(8): 7776-7790. DOI:10.1109/TCYB.2021.3051078 |
| [6] |
谢承旺, 郭华, 韦伟, 等. MaOEA/d2: 一种基于双距离构造的高维多目标进化算法[J]. 软件学报, 2023, 34(4): 1523-1542. |
| [7] |
LIU H L, GU F Q, ZHANG Q F. Decomposition of a multiobjective optimization problem into a number of simple multiobjective subproblems[J]. IEEE Transactions on Evolutionary Computation, 2014, 18(3): 450-455. DOI:10.1109/TEVC.2013.2281533 |
| [8] |
DEB K, JAIN H. An evolutionary many-objective optimization algorithm using reference-point-based nondominated sorting approach, part Ⅰ: solving problems with box constraints[J]. IEEE Transactions on Evolutionary Computation, 2014, 18(4): 577-601. DOI:10.1109/TEVC.2013.2281535 |
| [9] |
CHENG R, JIN Y C, NARUKAWA K, et al. A multiobjective evolutionary algorithm using Gaussian process-based inverse modeling[J]. IEEE Transactions on Evolutionary Computation, 2015, 19(6): 838-856. DOI:10.1109/TEVC.2015.2395073 |
| [10] |
CHENG R, JIN Y C, OLHOFER M, et al. A reference vector guided evolutionary algorithm for many-objective optimization[J]. IEEE Transactions on Evolutionary Computation, 2016, 20(5): 773-791. DOI:10.1109/TEVC.2016.2519378 |
| [11] |
YEVSEYEVA I, GUERREIRO A P, EMMERICH M T M, et al. A portfolio optimization approach to selection in multiobjective evolutionary algorithms[C]//Parallel Problem Solving from Nature-PPSN Ⅹ Ⅲ, vol 8672 of Lecture Notes in Computer Science. Cham: Springer International Publishing, 2014: 672-681.
|
| [12] |
HERNÁNDEZ GÓMEZ R, COELLO COELLO C A. Improved metaheuristic based on the R2 indicator for many-objective optimization[C]//SILVA S. GECCO'15: Proceedings of the 2015 Annual Conference on Genetic and Evolutionary Computation. New York: Association for Computing Machinery, 2015: 679-686.
|
| [13] |
SUN Y N, YEN G G, YI Z. IGD indicator-based evolutionary algorithm for many-objective optimization problems[J]. IEEE Transactions on Evolutionary Computation, 2019, 23(2): 173-187. DOI:10.1109/TEVC.2018.2791283 |
| [14] |
DUTTA S, RAJU M S S, MALLIPRDDI R, et al. Adaptive mating selection based on weighted indicator for multi/many-objective evolutionary algorithm[J]. Applied Soft Computing, 2023, 139: 110223. DOI:10.1016/j.asoc.2023.110223 |
| [15] |
ISHIBUCHI H, MASUDA H, TANIGAKI Y, et al. Modified distance calculation in generational distance and inverted generational distance[C]//Proceedings of the International Conference on Evolutionary Multi-Criterion Optimization. Cham: Springer International Publishing, 2015: 110-125.
|
| [16] |
TIAN Y, ZHANG X Y, CHENG R, et al. A multi-objective evolutionary algorithm based on an enhanced inverted generational distance metric[C]//2016 IEEE Congress on Evolutionary Computation (CEC). Piscataway, NJ, USA: IEEE, 2016: 5222-5229.
|
| [17] |
TIAN Y, CHENG R, ZHANG X Y, et al. An indicator-based multiobjective evolutionary algorithm with reference point adaptation for better versatility[J]. IEEE Transactions on Evolutionary Computation, 2018, 22(4): 609-622. DOI:10.1109/TEVC.2017.2749619 |
| [18] |
ZHANG X Y, TIAN Y, CHENG R, et al. An efficient approach to nondominated sorting for evolutionary multiobjective optimization[J]. IEEE Transactions on Evolutionary Computation, 2015, 19(2): 201-213. DOI:10.1109/TEVC.2014.2308305 |
| [19] |
DEB K, THIELE L, LAUMANNS M, et al. Scalable multi-objective optimization test problems[C]//Proceedings of the 2002 Congress on Evolutionary Computation. CEC'02 (Cat. No. 02TH8600). Piscataway, NJ, USA: IEEE, 2002: 825-830.
|
| [20] |
CHENG R, LI M Q, TIAN Y, et al. A benchmark test suite for evolutionary many-objective optimization[J]. Complex & Intelligent Systems, 2017, 3(1): 67-81. |
| [21] |
TIAN Y, CHENG R, ZHANG X Y, et al. PlatEMO: a MATLAB platform for evolutionary multi-objective optimization[Educational Forum][J]. IEEE Computational Intelligence Magazine, 2017, 12(4): 73-87. DOI:10.1109/MCI.2017.2742868 |