基于小生境的多目标进化算法

顾清华，骆家乐，李学现

1.西安建筑科技大学 管理学院，西安 710055

2.西安建筑科技大学 西安市智慧工业感知、计算与决策重点实验室，西安 710055

3.西安建筑科技大学 资源工程学院，西安 710055

多目标优化问题广泛存在于工程应用领域，这类问题的显著特征是具有多个相互冲突的目标。这类问题不能得到单一的最优解，而是一组折衷解，称为帕累托最优解。一般来说，传统的数学规划方法不仅计算复杂，而且难以有效地求解该类问题。进化算法被认为是求解该类问题的有效方法。然而，随着目标维数的增加，非支配解的数量呈指数增长[1]，基于帕累托支配的选择标准无法区分候选解，导致难以获取兼具良好收敛性和多样性的解集。为了解决以上问题，许多方法被提出，大致可以分为以下三类。

第一类是定义新的支配关系取代算法中普遍采用的帕累托支配关系。在广义帕累托最优支配GPO（generalized Pareto optimality）[2]和角度支配（angle dominance）[3]中，通过扩大单个解的支配区域来放松严格的帕累托支配关系，不可避免地会面临确定不同特征问题松弛程度的障碍。受到分解方法的启发，一些学者提出了SDEA支配（scalarization-based dominance evolutionary algorithm）[4]和RPS支配（reference points strengthened dominance relation）[5]。即使将以上支配关系嵌入进化算法能够促进解的收敛性，但是由于缺乏多样性维护机制，导致解的多样性较差。为了维护解的多样性，Tian等人[6]利用候选解之间角度的小生境技术提出了SDR支配（strengthened dominance relation）。在SDR支配的基础上，Yang等人[7]和Shen等人[8]分别提出了CDR支配（considering convergence dominance relation）和自适应控制SDR支配中收敛度和小生境的大小的支配关系CSDR（controlled strengthened dominance relation）。但是，其中涉及到多个参数，不同的问题对这些参数的敏感程度不同。

第二类是设计特殊的收敛性和多样性维护策略。例如，在向量角引导搜索的算法VaEA（vector anglebased evolutionary algorithm）[9]中，最大向量角优先原则和劣解消除原则用于临界层选择候选解。但是，解决规则特征的帕累托前沿问题的性能差[10]。在MSEA（multi-stage evolutionary algorithm）[11]、TSEA（multistage evolutionary algorithm）[12]、TSGA-II（two-stage genetic algorithm）[13]中，两阶段搜索策略来选择候选解，其中，第一个阶段基于收敛性选择候选解，第二阶段基于多样性选择候选解。但是，两阶段搜索策略不但需要设定较多的参数来预判进化所处的阶段，而且进化状态也难以预判，如果误判进化所处的阶段会削弱算法的性能。受到拐点驱动种群搜索策略的启发，Zhao等人[14]设计了一种偏好拐点促进种群向帕累托前沿搜索的算法。但是，识别拐点是一个难题，而且难以控制拐点区域的范围。此外，一些学者设计了自适应参考点的方法[15-16]处理不规则帕累托前沿的问题，但是缺点就是每一代都加入了许多参考点，降低了算法的效率且处理规则的帕累托前沿问题的性能差。

第三类是采用分解的方法。其中，分解方法包含两种分解思想。第一种分解思想是将多目标优化问题分解为一组单目标子问题。MOEA/D（decomposition-based many-objective evolutionary algorithm）[17]是该种类型最具代表性的算法。但是，它仅仅适合求解2至3个目标的优化问题。因此，许多MOEA/D的变体[18-20]被提出来求解高维多目标优化问题（目标维数超过三个的优化问题）。第二种分解思想是将目标空间划分为一系列子区域。例如，在NSGA-III（nondominated sorting genetic algorithm）[21]和MaOEADRA（many-objective evolutionary algorithm based on dominance and decomposition）[22]中，目标空间被一组权重向量划分为许多子区域。但是，它们求解退化和不连续等特征的帕累托前沿问题性能较差。因此，一些学者设计了自适应分解策略[23-24]求解不规则帕累托前沿问题。

即使以上的方法在一定程度上能提高多目标进化算法的求解性能，但是，大多数方法需要预先设定参数，而且大多数参数对于不同特征的问题普适性较差，不合适的参数会削弱算法的求解性能，导致难以平衡收敛性和多样性。此外，目标维数的增加会严重削弱对帕累托前沿的选择压力，给算法的收敛过程和多样性维护产生极大的挑战，特别是对于大部分采用帕累托支配关系作为主要选择标准的算法。针对以上问题，本文做了两点贡献：（1）首先，基于小生境，提出了SDN支配关系（niching based strengthened dominance），其中，设计了一个聚合函数和一种采用目标向量角的密度估计方法分别度量单个解的收敛性和分布性。因此，相较于现存的仅考虑收敛性的支配关系，被提出的支配关系同时考虑了解集的收敛性和多样性。（2）将提出的支配关系嵌入VaEA，设计了VaEA-SDN算法，其中，SDN支配关系取代VaEA中的帕累托支配关系，极大地提升了VaEA求解多目标优化问题平衡收敛性和多样性的能力。

1.1 多目标优化问题

以最小问题为例，多目标优化问题可以用以下数学公式（1）表示：

其中，x=( x1,x1,…,xn)T∈Ω是n维决策向量，Ω是决策空间，ℝM是M维目标空间，F:Ω→ℝM是由决策空间Ω映射到M维目标空间ℝM的目标值组成的目标向量，fi()x是决策变量映射到目标空间在第i个目标上的目标值。

1.2 帕累托支配、非支配解、帕累托最优集、帕累托前沿

定义1（帕累托支配）对于一个最小化的问题，对于给定的两个解x和y，解x帕累托支配解y，被标记为xy，当且满足：

如果对于给定的两个解x和y，如果解x不满足帕累托支配解y的条件，解y也不满足帕累托支配解x的条件，那么解x和y是互不支配的，被标记为xy，y。

定义2（非支配解）对于决策空间的一个解x∈Ω，如果不存在任何x′∈Ω支配解x，被标记为′∈Ω，x′x，那么解x被称为非支配解。

定义3（帕累托最优集）由非支配解构成的集合称为帕累托最优集，被标记为

定义4（帕累托前沿）由帕累托最优集映射到目标空间组成的集合称为帕累托前沿，PF={F (x)∈|x∈P}。

定义5（小生境）在进化算法中，所有解构成的集合被称为种群，每一个种群成员对应一个解，生物体的生存空间对应进化算法中的目标空间。小生境[25]是指目标空间的局部子种群。

定义6（目标向量角）目标向量角指目标空间的两个解之间的锐角，它可以反映两个解在搜索方向的相似性。对于两个解u和v，二者之间的目标向量角可以按以下公式（3）计算：

其中，F′(u)和F′(v)是两个解各自归一化后的目标向量，F′(u)·F′(v)是两个解目标向量的内积，‖ F′(u)‖和‖ F′(v)‖是两个解目标向量的二范数，arccos(·)是两个解的目标向量之间的反余弦值。

2.1 提出算法的整体框架

大多数的多目标进化算法主要依靠帕累托支配关系作为选择子代的方式。然而，在以非支配解占主导空间的高维目标空间，帕累托支配关系无法在非支配解之间提供足够的选择压力。此外，帕累托支配关系并没有考虑解集的多样性。对于一个多目标进化算法来说，应该同时考虑解的收敛性和多样性。然而，小生镜可以较好地维持解集的多样性[25]。在大多数的多目标进化算法中，采用欧式距离来评估解在目标空间的分布性。但是，正如文献[9]，欧式距离并不适合度量高维目标空间解的分布，而目标向量角可以利用角度反映解在目标空间的搜索的相似性。同时考虑到解集的收敛性，聚合函数可以度量解在搜索方向的收敛度。如果种群成员的分布性和收敛度均很好，那么最终整个种群的收敛性和多样性将有效地得到维护。因此，基于小生境，提出了一种同时考虑收敛性和多样性的支配关系来促进种群的收敛性和多样性，其中，一个聚合函数和目标向量角的密度估计方法来分别度量解的收敛度和分布性。此外，结合VaEA，将被提出的支配关系取代VaEA中的帕累托支配关系。

被提出的支配关系结合VaEA的优势和必要性解释如下：

在VaEA中，首先，通过帕累托支配关系对种群非支配排序[26]到不同的前沿面。然后，将位于临界层中的解与外部档案集中的解关联起来，采用最大向量角优选原则和裂解消除原则[9]从临界层选择解来分别维护种群的多样性和收敛性。然而，在VaEA中，外部档案集中解的选择是基于帕累托支配关系。因此，在高维空间，VaEA难以对外部档案集进行维护。相较于帕累托支配关系，本文提出的支配关系在非支配排序阶段就同时考虑了解的收敛性和多样性。此外，VaEA中的最大向量角优选原则和裂解消除原则一定程度上维护了位于临界层解的收敛性和多样性。VaEA通过新的非支配排序后，可以进一步提高种群的收敛性和多样性。

依据以上的解释，提出的VaEA-SDN算法整体框架与VaEA算法类似，区别在于VaEA-SDN使用被提出的SDN支配关系取代帕累托支配关系对种群进行非支配排序[26]。图1展示了VaEA-SDN算法的流程图，以下步骤是对VaEA-SDN算法流程的具体解释。

图1 VaEA-SDN流程图Fig.1 Flow chart of VaEA-SDN

VaEA-SDN算法的具体步骤如下：

输入参数：种群的规模N，迭代次数t=0，最大迭代次数Gmax；

1.生成数量为N的初始种群Pt；

2.通过遗传算子执行交叉变异产生子代Qt；

3.将父代种群和子代种群合并Pt⋃Qt=Rt；

4.产生参考集RP_Set；

5.将联合种群Rt与每一个参考点RP关联；

6.使用SDN支配关系对联合种群Rt中的解非支配排序到不同等级的前沿面[ F1,F2,…,Fl,…]，其中Fl被称为临界层，Fl满足该要求|F1|+|F2|+…+| Fl-1|＜N,且|F1|+|F2|+…+|Fl|≥N。

7.将Rt中位于F1至Fl-1的个体加入外部档案集St，即St=F1⋃F2⋃…⋃Fl-1；

8.采用最大向量角优选原则和裂解消除原则[9]从临界层Fl中一个一个地选择K个解加入到St，其中K=N-||St，直到档案集St中的种群规模等于N以构成下一代的种群Pt+1，t=t+1；

9.当迭代次数t达到预先设定的最大迭代次数Gmax，算法结束，输出Pt+1；
否则，返回步骤2到步骤8算法继续执行。

输出：最终的种群Pt+1

2.2 参考点的产生和关联操作

参考点的产生：由于被设计的SDN支配关系的定义需要利用参考点构成的小生境。本文用文献[27]中的方法产生一组均匀分布在目标空间的参考点。对于一个具有M个目标的优化问题，参考点的数量H按公式（4）确定：

其中，p是沿每个目标轴的分割数。

关联操作：首先，每个参考点与原点连接起来产生对应的参考方向。然后，计算种群中每个解与所有参考方向之间的目标向量角。最后，将每个解与最小角度对应的参考方向相关联。

2.3 SDN支配关系

SDN支配关系利用参考点的构成的小生境，它的主要特点是如果候选解位于同一个小生境中，收敛度小的解支配收敛度大的解。否则，具有收敛度小且低密度估计值的解支配另一收敛度大且高密度估计值的解。

定义7（SDN支配关系）对于给定一个种群P和一组参考点RP_Set。当且仅当以下任一条件成立，一个解u被称为SDN支配另一个解v，标记为uSDNv。

A RP(u)=RP(v)且Con(u)＜Con(v)

B RP(u)≠RP(v)且Con(u)＜Con(v )D(u)＜D(v)

其中，RP(u)表示解u关联的参考点，Con(u)表示解u的收敛度，它通过将M个目标值相加计算得出，更小Con(u)值意味着解u更好的收敛性。D(u)表示解u的密度估计，它是根据解u所处小生境中解的数量及其与解u之间的目标向量角确定。每个小生境内的解由关联到同一个参考点的解构成。更小的D()u值意味着u解更好地分布。

对于该支配关系的解释如下：当解u帕累托支配解v（满足条件1），则uSDNv。当解u和v是互不帕累托支配，但是关联到同一个参考点时（满足条件（2）A），仅仅依据收敛性度量Con来比较两个解。如果解u的收敛度小于解（即Con(u)＜Con(v)）的收敛度D，则uSDNv。在同一个小生境中，优先考虑收敛性好的解可以确保种群的收敛性。当解u和v是互不帕累托支配且关联到不同的参考点时，同时依据解Con和D来比较两个解。如果解u的收敛度小于解v的收敛度（即Con(u)＜Con(v)）且解u的密度估计值小于解v的密度估计值（即D(u)＜D(v)）（满足条件（2）B），则uSDNv。在不同的小生境内同时强调收敛性和多样性，可以使种群在保证收敛性的情况下维护种群的多样性。以下是如何计算Con和D。

对于给定的一个解u，解u的收敛度按以下公式（5）和（6）计算：

其中，f~i(u)是解u在第i个目标上归一化的目标值，fimin(x)是种群在第i个目标上的最小值，fimax是种群在第i个目标上的最大值。

解u的密度估计值按以下公式（7）～（9）计算：

其中，Angle(u,v)是解u和它的邻近解v之间的目标向量角；
θ是RP(u)和它的M个邻近参考向量之间的平均向量角；
θi是RP(u)和它的第i个邻近参考向量之间的角度。如果一个解的邻近解越多，且邻近解与该解之间的夹角越小，则该解将被赋予更大的密度估计值，表明其更拥挤。因此，该解的分布性就差，不利于种群的多样性。如果大多数候选解的收敛度和密度估计值均越小，种群的收敛性和多样性就越好。

需要注意的是，如果某一个参考方向仅仅被关联到一个解，说明在该搜索方向上只有一个解引导搜索。为了维持种群的多样性，该解毫无保留地保存到下一代。

用一个简单的例子来说明SDN支配。由于在高维空间几乎所有解都是互不帕累托支配的，因此，假设被比较的两个解互不帕累托支配，一个解SDN支配另一个解，存在两种情况：

情况1两个被比较的解关联到同一个参考点，仅强调收敛性。依据它们各自的收敛度来确定二者之间的支配关系。正如图2中展示的那样，解c和解f是互不支配的，但是它们关联到同一个参考点RP3。因为Con(c)＜Con(f)，所以cSDNf。

图2 阐述两个解之间的SDN支配关系Fig.2 Illustration of SDN dominance relationship between two solutions

情况2两个被比较的解关联到不同的参考点，收敛性和分布性同时强调。同时依据它们各自的收敛度和密度估计值来确定二者之间的支配关系。正如图2中展示的那样，解a和解c是互不支配的，它们分别关联到RP2和RP3。因为Con(a)＜Con(f)且D(a)＜D(C)，所以aSDNc。

经过以上对SDN支配定义及解释，可以得到SDN的以下属性。

属性1 SDN支配在同一个小生境或不同小生境内具备传递性，即，对于∀x,y,z∈U,其中U是算法获得的所有解构成的集合，如果xSDNy并且ySDNz,那么xSDNz。

证明x,y,z在同一个小生境内，即RP(x)=RP(y)=RP(z)。

因此，可以推出RP(x)＜RP(z),Con(x)＜Con(z),即xSDNz。

x,y,z在不同的小生境内，即RP(x)≠RP(y)≠RP(z)。

因此，可以推出Con(x)＜Con(z),D(x)＜D(z),即xSDNz。

依据以上分析可知，在高维目标空间，几乎所有的解都是非支配解，帕累托支配关系无法提供足够的选择压力。但是，SDN支配可以在候选解之间形成一个严格的排序，同时管理候选解的收敛性和多样性。

就收敛性而言，在同一个小生境内优先选择收敛度最好的解（例如，图3中被标绿的解i）可以保证种群在该搜索方向上向帕累托前沿收敛，并且还可以加快向帕累托前沿的收敛速度，因为SDN支配在同一个小生境内具备传递性。

图3 SDN支配在双目标空间平衡收敛性和多样性Fig.3 Balancing between convergence and diversity for SDN dominance in dual objective space

就多样性而言，在所有小生境内都仅仅保留一个收敛度最好的解和优先考虑不同小生境内同时具备良好收敛性和分布性的解可以保证种群的多样性。例如，如果所有小生境都分别保留一个收敛性最好的解（图3中被标绿的解）到下一代，种群将会朝各个方向朝帕累托前沿搜索。因此，优先选择图3中被标绿的解可以在保证收敛性良好的情况下，较好地维持种群的多样性。此外，例如，当图3中位于两个不同小生境内的解d和解b做比较时，优先选择具备良好收敛性和分布性的解d可以在维护收敛的同时提高多样性，因为SDN支配在不用小生境内同样具备传递性。

2.4 计算复杂度分析

对于一个具有M个目标且种群规模性为N的优化问题，VaEA-SDN的计算复杂度分析如下：归一化联合种群Rt计算复杂度为O(MN)；
对于关联操作，计算种群成员与参考方向目标向量角的计算复杂度为O(HN)，其中H是参考点的数量，但是，参考点的数量等于种群的规模。因此，关联操作的计算复杂度为O(N2)；
计算收敛性度量Con的计算复杂度为O(MN)；
计算密度估计值度量D的计算复杂度为O(N2)；
类似利用帕累托支配关系对种群进行非支配排序的比较次数，SDN支配对种群非支配排序的计算复杂度为O(MN2)；
最后，假设通过非支配排序后，临界层Fl包括L个解，参照VaEA，最大向量角优选原则和裂解消除原则的选择过程需要O(ML2)。因此，VaEA-SDN进化一代的总体计算复杂度为O(MN2)。表1展示了下文进行仿真实验的7种算法的计算复杂。从表1展现的结果来看，对比算法的计算复杂度参照原始论文，SDN支配并未增加VaEA的计算复杂度，这个结果是可以预知的。因为SDN支配和VaEA中的帕累托支配对解进行非支配排序的比较次数是一样的。此外，相比其他5个对比算法，VaEA-SDN也并未增加计算复杂度。

表1 7种算法的计算复杂度Table 1 Computational complexity of seven algorithms

3.1 测试问题和对比算法

为了测试被提出算法的性能，两组被广泛使用的基准测试系列问题DTLZ（Deb-Thiele-Laumanns-Zitzler）[28]和MaF（many-objective function）[29]来执行仿真实验。因为MaF2和DTLZ2的都是凹特征的帕累托前沿测试问题，故在MaF测试问题上执行实验时，没有选择MaF2作为测试问题。其他测试问题的特征如表2所示。同时，选择6个先进的算法NSGA-III[21]、VaEA[9]、MSEA[11]、NSGAII-CSDR[8]、RPS-NSGAII[5]和CDR-MOEA[7]作为对比算法。

表2 测试问题及其特征Table 2 Test problems and their characteristics

3.2 算法性能评价指标

世代距离（generational distance，GD）[28]、覆盖帕累托前沿范围（coverage over the Pareto front，CPF）[30]以及反转世代距离（inverted generational distance，IGD）[31]被用来定量评估算法的性能。其中，IGD值越小，表示算法获得的解集兼具良好的收敛性和多样性，即算法平衡收敛性和多样性的能力越好；
GD值越小，仅表示算法获得解集的收敛性越好；
CPF值越大，仅表示算法获得解集的多样性越好。

设P*是算法获得的解集，PF*是沿真实帕累托前均匀分布的解集，||P*和 ||PF*分别是解集P*和PF*中解的数量。评价算法性能的三个指标的定义如下：

（1）IGD指标

其中，d(z,P*)是真实前沿面PF*上的解z到P*上解的最小欧式距离。

（2）GD指标

其中，d(v,PF*)是算法获得解集P*中解v到至真实帕累托前沿上的解的最小欧式距离。

（3）CPF指标

CPF将所获得的解集通过真实帕累托前沿投影到低维空间计算投影解集的超立方体的体积，来度量解的多样性。

其中，Vol()P*是算法获得解集构成的超立方体体积，Vol( )

PF*是真实帕累托前沿面上的解集构成的超立方体的体积。lM-1v表示算法获得的解v在M-1维目标空间构成的立方体的边长，lM-1Y表示真实帕累托前沿面上的解Y在M-1维目标空间构成的立方体的边长。vi和qi算法获得解v和解q在映射空间第i个目标值，yi和pi是真实帕累托前沿面上的解在映射空间第i个目标值。

所有仿真实验都在基于MATLAB的进化多目标优化平台Plat-EMO[32]上进行，每个实验结果均是20次独立运行的平均值和标准差。依据评价指标，使用显著性水平为0.05的Wilcoxon秩和检验[33]在统计学上将对比算法的结果与VaEA-SDN的结果两两进行比较，其中“+”“-”和“=”分别表示对比算法的性能比VaEA-SDN显著优、显著劣以及在统计学上性能相似。

3.3 参数设置

（1）遗传算子：依据所有对比算法的原始论文，交叉概率pc=1；
变异概率pm=1/D，D是决策变量的数量；
交叉分布指标nc=20；
变异分布指标nm=20。

（2）种群的规模：种群的规模N等于参考点的数量H，表3中展示了不同的目标对应的种群规模，正如文献[7]和[21]所建议的那样。

（3）算法的终止条件：每个算法在每个测试问题上都独立运行20次。每次算法在3、5、8、10个目标的测试问题上运行的终止条件是对应的最大迭代次数或评价次数[21]，如表3所示。

表3 种群的规模和最大迭代次数Table 3 Population size and maximum number of iterations

（4）对比算法中的参数按原始论文设置：在NSGAIICSDR中，控制小生境规模的两个参数kmax=1.6，Δk=1.1，控制收敛度的两个参数amax=60，Δa=15。

3.4 实验结果分析

在本节中，首先验证被提出的支配关系的有效性。将在VaEA中嵌入SDN支配的VaEA-SDN与VaEA进行对比仿真实验，采用GD和CPF作为评价指标以验证被提出的支配关系可以提高VaEA的收敛性和多样性，实验结果如表4所示。然后，为了评估VaEA-SDN平衡收敛性和多样性的性能，采用IGD作为评价指标，将VaEA-SDN与6个对比算法在DTLZ和MaF系列问题上进行仿真实验，仿真结果分别如表5和表6所示。对于每个测试问题，最好的结果突出显示。

表4 VaEA和VaEA-SDN在DTLZ测试问题上的GD值和CPF值Table 4 GD and CPF values obtained by VaEA and VaEA-SDN on DTLZ test problems

表5 7种算法在DTLZ测试问题上的IGD值Table 5 IGD values of seven algorithms on DTLZ test problems

表6 7种算法在MaF测试问题上的IGD值Table 6 IGD values of seven algorithms on MaF test problems

3.4.1 SDN支配有效性验证

相较于VaEA-SDN，在超过5个目标具有多模态特征的DTLZ1和大部分DTLZ3测试问题上，VaEA的收敛性指标更好，多样性指标较差。这是因为随着目标维数的增加，DTLZ1的局部帕累托前沿的数量会线性递增，而DTLZ3的局部帕累托前沿的数量是呈指数倍增加，VaEA中采用的帕累托支配关系过度地强调解的收敛性，没有考虑解的多样性，使得VaEA陷的局部收敛性较好，但是难以向全局最优搜索，GD值更好，CPF值较差。8和10目标的DTLZ2的帕累托前沿上的点至坐标原点的欧式距离均为1，SDN利用目标求和来度量解的收敛性，可以保证解的收敛性良好，但可能会使解偏离均匀分布的参考向量。3目标的DTLZ5和DTLZ6最终会在三维空间退化成一条曲线，使得VaEA-SDN的小生境内集中过多的解，其中采用的密度估计方法难以判断解的分布性。故而VaEA-SDN在这几个测试实例上的多样性比VaEA差。

但是VaEA-SDN的优势还是很明显的，从表4中的结果可知，VaEA-SDN在DTLZ的24个测试实例中均获得了18个最佳GD值和CPF值。VaEA-SDN在DTLZ4和DTLZ5上均取得了最佳的收敛性，同时在这两个测试问题上，多样性也取得了令人满意的表现。同样，对于帕累托前沿特征综合了DTLZ4和DTLZ5更复杂的DTLZ6，VaEA-SDN在收敛性和多样性方面均展现了强大的竞争力。对于DTLZ4和DTLZ2，SDN支配在所有测试实例上均改善了VaEA的收敛性。特别是SDN支配使VaEA的多样性在具有偏好特点的DTLZ4所有测试实例均得到了改善。

为了直观地观察改进策略的性能，图4中画出算法VaEA和VaEA-SDN在DTLZ测试系列中具有代表性的10目标DTLZ3和8目标DTLZ6上GD值的迭代曲线。很明显，无论从收敛速度还是收敛精度方面比较，SDN支配均极大地改善了VaEA的性能。

图4 VaEA和VaEA-SDN在DTLZ3和DTLZ6上GD值的变化Fig.4 Variation of GD values of VaEA and VaEA-SDN on DTLZ3 and DTLZ6

综合以上分析和表4中的仿真结果可知SDN支配可以有效地保证了VaEA的收敛性，同时提高VaEA的多样性，这为接下来执行广泛的实验验证VaEA-SDN平衡收敛性和多样性的竞争力奠定了基础。

3.4.2 DTLZ系列测试问题上的性能验证与分析

表5展示了7种算法在DTLZ基准测试问题上IGD的平均值和标准差。显然，VaEA-SDN是最佳的优化算法，CDR-MOEA紧随其后，因为在24个测试实例上VaEA-SDN和CDR-MOEA分别获得了12和9个 最佳IGD，而NSGA-Ⅲ、VaEA、MSEA、NSGAII-CSDR和RPSNSGAII获得的最佳结果数分别为3、0、3、2、0。相较于VaEA，VaEA-SDN在总共24个测试实例上有22个结果超过了VaEA。以下是对实验结果的详细分析。

DTLZ1和DTLZ3是具有多模态特征的测试问题，这会对算法收敛到全局最优产生极大的挑战。从表5的结果可以观察到，在这两个测试问题上，VaEA-SDN性能略次于NSGAII-CSDR和CDR-MOEA。从图5所有算法在10目标的DTLZ3上所获解集的平行坐标图来看，NSGA-III、VaEA、MSEA以及RPS-NSGAII所获解集的收敛性很差，仅仅只有VaEA-SDN、NSGAII-CSDR和CDR-MOEA可以获得收敛性且多样性良好的解集。主要因为这3种算法均在非支配排序阶段同时对解的收敛性和多样性进行了维护。这对于算法然收敛到全局最优具有优势。NSGAII-CSDR和CDR-MOEA利用候选解之间的角度来自适应地确定小生镜的规模。此外，CDR-MOEA还采用了一种角度距离维护多样性。NSGAII-CSDR依据进化进程利用参数更新小生境的规模和收敛性度量方法。因此，相比VaEA-SDN，NSGAIICSDR和CDR-MOEA处理具有多模态特征问题的表现更胜一筹。

图5 7种算法在10目标DTLZ3上解集的平行坐标图Fig.5 Parallel coordinates of solution sets obtained by seven algorithms on 10-objective DTLZ3

DTLZ2是一个相对简单的测试问题。VaEA-SDN在DTLZ2的所有测试实例上均取得了最佳的表现。NSGA-III在该测试问题上的性能也不错。由于DTLZ2的帕累托前沿均匀分布在目标空间，VaEA-SDN和NSGA-III都引入一组均匀分布的参考点。因此，在保持良好收敛的情况下有效地维护解集的多样性。

DTLZ4是具有偏好特点的测试问题。在该测试问题上，VaEA-SDN表现最佳。从图6解的分布可以直观地观察到NSGAII-CSDR和CDR-MOEA所获解的多样性特别差。VaEA、MSEA和RPS-NSGAII虽然可以获取接近且覆盖整个帕累托前沿的解，但是解的多样性较差。即使NSGA-III得到解集多样性较好，但是只有少数解分布在真实帕累托前沿上。只有VaEA-SDN在该测试实例上可以得到收敛性和多样性均良好的解集。

图6 7种算法在3目标DTLZ4上获得的非支配解集Fig.6 Non-dominated solution sets obtained by seven algorithms on 3-objective DTLZ4

DTLZ5帕累托前沿面具有退化的特点。CDR-MOEA在该问题上表现最佳，这是因为CDR-MOEA利用单个解与邻近参考向量的角度距离可以使解在处理退化问题时保持解尽可能位于邻近个体中心，有效地维护解的多样性。虽然VaEA-SDN在该问题上没有获得最佳的IGD值，但是，它的性能并不差，仅仅紧随CDR-MOEA其后。在8、10个目标上，VaEA-SDN的表现仍然比NSGA-III、VaEA、MSEA、NSGAII-CSDR和RPS-NSGAII好。图7（a）展示了7种算法在10目标的DTLZ5上IGD值的变化曲线，相比于VaEA，SDN支配关系极大改善了VaEA的性能，并且进化过程性能稳定。

DTLZ6是在DTLZ5上改进得到的测试问题。与3目标的DTLZ5类似，具有3个目标的DTLZ6最终都会退化成一条曲线。正如在3.4.1小节分析的那样，在这两个测试实例上VaEA-SDN难以判断解的分布，故而VaEA-SDN在3目标的DTLZ6上表现出了中等的性能。但是，随着目标维数的增加，VaEA-SDN实现了最佳的性能。从图7（b）可以看出来，即使VaEA-SDN在进化早期性能不如CDR-MOEA和NSGAIII-CSDR，但是它的性能改善幅度最大且收敛速度最快，并且在进化末期获得了最佳的表现。

图7 7种算法在10目标的DTLZ5和DTLZ6上IGD值的变化Fig.7 Variation of IGD values of seven algorithms on DTLZ5 and DTLZ6 with 10-objective

3.4.3 MaF系列测试问题上性能验证与分析

DTLZ测试系列问题缺乏凸特征的测试问题。为了更全面地验证被提出VaEA-SDN的优势，MaF系列测试问题被用来执行进一步的实验。

表6展示了7种算法在MaF系列测试问题上的IGD值，很明显VaEA-SDN在MaF系列测试问题上极具优势。因为VaEA-SDN在MaF的所有测试实例上均优于NSGA-III和RPS-NSGAII。此外，相比其他6个算法，VaEA-SDN在MaF4和MaF5的所有测试实例上均展现了最好的表现，同时在MaF1和MaF3也取得了3个最佳的结果。值得注意的是在3目标MaF系列测试上，MSEA的性能与VaEA-SND性能类似，取得了较好的结果。这是因为不像在高维目标空间，在较低维的3目标MaF上依然会出现较多的非支配解，MSEA利用帕累托帕累托支配关系不断重复判断种群进化所处的阶段，然后每次都仅仅替换掉收敛性和多样性最差的解。因此，MSEA可以在较低维空间保持解集的良好分布和收敛。

为了更直观地观察各个算法的性能指标，图8展示了所有对比算法在3、5、8、10目标的MaF1和MaF5上所获IGD值的三维柱状图。从图8可以清晰地观察到RPS-NSGAII和NSGA-III在MaF1上性能较差，而CDRMOEA和NSGAII-CSDR在MaF5上的性能较差，特别是它们在8和10目标的MaF5上IGD值都很大，说明这两个算法处理具有偏好的凸问题难以获得收敛且分布良好的解集。

图8 7种算法在MaF1和MaF5上获得的平均IGD值Fig.8 Averange IGD values obtained by seven algorithms on MaF1 and MaF5

图9展示了所有对比算法在10目标的MaF4和MaF5上的IGD变化曲线。对于10目标的MaF4，图9（a）可以观察到VaEA-SDN比VaEA更快且更好地收敛，且在该测试实例上取得了最佳性能。对于10目标的MaF5，图9（b）可以观察到VaEA和VaEA-SDN在整个进化过程中性能一直是最好的两个算法，但是，VaEA在进化早期的性能劣于VaEA-SDN。

图9 7种算法在10目标的MaF4和MaF5上IGD值的变化Fig.9 Variation of IGD values of seven algorithms on MaF4 and MaF5 with 10-objective

此外，为了直观地比较各个算法所获的解集质量，图10展示了所有对比算法在10目标MaF3上所获解集的平行坐标图。NSGA-III、VaEA、MSEA、RPS-NSGAII、CDR-MOEA在该测试实例上IGD的值都特别大，说明这5种算法处理多模态且凸的MaF3时根本无法收敛。从图10展示的结果来看，仅仅只有NSGAII-CSDR和VaEA-SDN可以获得一组近似到帕累托前沿的解。

图10 7种算法在10个目标的MaF3上解集的平行坐标图Fig.10 Parallel coordinates of solution sets obtained by seven algorithms on 10-objective MaF3

最后，VaEA-SDN在MaF的16个测试实例上取得了14个最好的结果，而它的6个对比算法NSGA-III、VaEA、MSEA、NSGAII-CSDR、RPS-NSGAII以及CDRMOEA仅仅分别获得了0、2、6、1、0、1个最佳结果。因此，综合以上的分析，VaEA-SDN对于处理凸特征的系列复杂问题同样具备极大的优势。

3.5 汽车碰撞安全实验的应用

为了验证VaEA-SDN算法的实用性，将其应用于汽车碰撞安全设计问题的优化[34]。该问题旨在优化车辆前部结构的耐撞性。第一个目标是吸能，第二个目标是汽车正面碰撞时加速度，第三个目标是偏置碰撞时的脚趾板侵入。该优化问题包含3个相互冲突且需要同时最小化的目标。本次实验最大迭代次数设置为1 000，种群的大小设置为91。所有算法在该问题上20次运行得到的平均IGD值用作比较结果。由于计算IGD值需要一组参考集，参照文献[21，35]，将所有算法在该实际问题上获得的非支配解的合并解集作为参考集。正如表7所示，采用多阶段搜索策略的MSEA获得了最佳的结果，但是它的计算复杂度最高。虽然VaEA-SDN在该实际应用不是最佳的算法，但是，它的性能仅仅稍逊于MSEA，同时相较于其他5个先进的对比算法，VaEASDN取得了最佳的结果。因此，VaEA-SDN在实用性方面具备一定的应用价值。

表7 7种算法汽车安全设计优化中获得的IGD值Table 7 IGD values obtained by seven algorithms in vehicle safety design optimization

为了提高多目标进化算法解决多目标优化问题平衡收敛性和多样性的能力，提出了SDN支配关系。相较于帕累托支配关系，被提出的支配关系在非支配排序阶段同时管理了解的收敛性和多样性。然后，将该支配关系嵌入VaEA设计了多目标进化算法VaEA-SDN。最后，VaEA-SDN与6个先进的多目标进化算法在DTLZ和MaF测试系列问题上进行了广泛的对比仿真实验。实验结果表明，VaEA-SDN求解多目标优化问题可以有效地平衡解集的收敛性和多样性。最后，汽车碰撞安全实验的应用也验证了VaEA-SDN算法的实用性。但是，VaEA-SDN也有一定的局限性，解决多模态特征的问题上性能稍逊于NSGAII-CSDR和CDR-MOEA，解决退化特征的问题上稍逊于CDR-MOEA。因此，相较于NSGAII-CSDR和CDR-MOEA，解决具有多模态[36-37]和退化特征[38]的实际问题也会有一定的局限性。将来可以考虑设计一种约束处理策略到VaEA-SDN中去解决现实应用中的约束多目标优化问题。