支配的多目标进化算法及自适应调整方案.doc

n 当前文档修改密码：8362839

基于-支配的多目标进化算法及自适应调整策略本文研究工作受国家自然科学基金（No.70571057，No.70171002）和“新世纪优秀人才支持计划” (NCET-05-0253) 资助。刘鎏，男，1982年生，博士研究生，研究方向为多目标进化算法理论及其应用。Email: 。 李敏强，男，1965年生，教授，博士生导师，主要研究领域为进化计算理论，数据挖掘和机器学习。 林丹，男，1968年生， 副教授，硕士生导师，主要研究方向为遗传算法理论及其应用。

刘鎏1，李敏强1，林丹2
1（天津大学 系统工程研究所 天津 300072）
2（天津大学 理学院应用数学系 天津 300072）

摘要: 本文提出了一类新的基于-支配关系的多目标进化算法。该算法采用配对比较选择和稳态替换策略，提高了算法的收敛速度，降低了计算时间。首先，在保持种群分布性上，采用了一种新的基于-支配关系的精英保留策略，避免了传统修剪策略所引起的Pareto前沿面的退化。其次，根据不同取值分析了算法收敛性，提出了一种自适应调整策略。最后，通过5个常用的双目标测试函数的计算，验证了包括该自适应调整策略的多目标进化算法在求解质量上要显着强于 NSGAII，SPEA2和-MOEA等主流多目标进化算法。

关键词： 多目标优化;-支配;进化算法; 自适应调整;精英保留策略;稳态策略

1. 前言

求解最优化问题（也称数学规划问题）是指从所有可能的方案中选择最合理的一种以达到目标优化的过程。当优化问题的目标个数多于一个时，称之为多目标优化。在通常情况下，同一问题中的多个目标函数是彼此矛盾的，因此最终结果是获得一系列折衷解。
多目标进化算法是指利用进化搜索的技术去解决多目标优化问题。David Schaffer[1]提出了第一个多目标进化算法即向量进化遗传算法，而后该领域专家又提出了多种多目标进化算法并应用于求解实际问题。Coello[2]总结了目前的多目标进化算法，并将它们分为两代：第一代强调简洁，第二代强调效率，它们之间的主要区别在于精英个体是否被引入种群的进化过程之中。Laumanns[3]归纳了采用精英策略的多目标进化统一模型（A unified model for MOEAs，UMMEA），通过将存储当前所有非被支配个体的种群同一般的进化种群相结合，实现精英参与种群的进化。大部分第二代的多目标进化算法，如强度Pareto进化算法(SPEA)[4]，强度Pareto进化算法2（SPEA2）[5]，Pareto包络选择算法（PAES）[6]，都符合这样的模型结构。另一个常用的非劣排序遗传算法2（NSGAII）没有直接利用外部种群。它将子代种群和父代种群相结合，优先选择其中的精英个体去构成下一代的进化种群。这种策略也实现了精英个体加入种群进化，并取得了很好的计算结果。
另一个分类标准即是否采用了Pareto支配排序。Goldberg[7]率先将Pareto优化的概念引入多目标进化算法。当前的多目标进化算法大多通过Pareto支配关系的排序来计算种群中个体的适应值，从而引导种群朝向Pareto前沿面进化。虽然这种方法可以较好地改善算法的收敛性，但是排序过程要耗费大量的计算。
为了提高进化算法效率，一些研究者采用了稳态的进化策略。所谓稳态是当新个体产生后立即加入种群的下一代进化过程之中，如简单进化算法（SEAMO）[8]，Pareto收敛遗传算法（PCGA）[9]，-多目标进化算法（-MOEA）[10]。在选择个体进入交配池的操作中，它们均采用配对比较的方法，而没有进行个体适应值的计算。实验结果表明这些基于稳态的进化算法在处理某些问题上要优于基于Pareto排序的算法[8, 11]。
另外，由于非支配解的数量巨大，而外部种群存储容量有限，很多修剪策略，如PAES中的自适应网格，NSGAII中的Crowding-Distance，SPEA中的聚类和SPEA2中的最近距离方法等，都在各自算法中发挥了很好的作用。然而，正如[12]所述，这些修剪策略很可能造成Pareto 前沿的退化，进而影响到最终种群的收敛。Laummans[13]根据-支配关系，提出一种基于网格向量的种群修剪策略，可以很好地防止进化过程中种群的退化。这种策略在计算网格向量时，除了参数，还需要获得各个目标上的最小值，并且相同网格中的个体比较需要计算各自的欧式距离，相对来说计算量比较大。
本文提出了一种新的基于-支配关系的多目标进化算法，即-支配多目标进化算法（-dominance MOEA，EDMOEA）。该算法采用一种新的基于-支配关系的修剪策略，不仅可以防止退化现象，还可以有效的保存极端值个体以保证Pareto前沿面的广度。该算法基于稳态替换策略，利用的选择方法，可以更加快速有效地到达Pareto前沿面。同时，在新算法中采用了新的自适应调整策略，实验结果验证了这种新策略的优越性。
本文的结构如下：第2节介绍了Pareto优化和-Pareto优化的概念；第3节简要引入了协同UMMEA模型，并对其进行了修正；第4节详细讨论了新的EDMOEA算法和自适应调整策略；第5节针对在一系列测试函数上的计算实验，将包含自适应调整策略的自适应多目标进化算法（AEDMOEA）同固定策略的EDMOEA及NSGAII，SPEA2，-MOEA等其它算法进行对比,分析了新算法的性能优势。第6节总结本文研究结论。

2．基本概念

2.1 Pareto 支配关系

在多目标优化问题中，Pareto优化解是最常用的优化概念。它最早由Francis Ysidro Edgeworth 在1881年提出而后经Vilfredo Pareto推广[14]（为方便讨论起见，本文的优化问题皆为最小化问题），其定义如下：
定义 1（Pareto 支配）：设，。称解支配解当且仅当部分地优于，即 ,，记做。
定义2（Pareto 最优解）：解称之为解集合的Pareto优化解当且仅当集合。
定义 3（Pareto 最优解集）：对于给定的多目标优化问题，设其定义域为，则其Pareto最优集，定义为：。
将Pareto最优解集在函数空间上对应的集合称之为Pareto前沿，记为。

2．2 -支配关系

-支配关系是传统的Pareto支配关系的弱化[15]，其具有多种概念形式。这里我们采用加的形式,且对于给定的，，。其定义如下：
定义4（-支配）：设,，对，称-支配当且仅当，，且,。记为：。
定义 5（-Pareto最优解集近似）[13]：集合称为的-Pareto最优解集近似，当且仅当对任意都存在，使得。
定义 6（-Pareto解集）[13]：集合称为集合的-Pareto解集,当且仅当为集合的-Pareto最优解集近似,且。
根据以上定义，可以得到如下两个定理。
定理 1 , 。
证明：因为，故对有，且, 使得。又由，则对, 。因此可知。定理得证。
定理 2 设，则有 。
证明：由题设可知，则有, ， 且，使得 。又由，故可知, 。另一方面，由，据定义可知, , , 。显然可知，对，有，即。定理得证。
值得注意的是，和分别作为集合的-Pareto解集和-Pareto最优解集近似，都不是唯一的。一些个体靠近Pareto前沿，但不是Pareto最优解，若满足-支配关系，都有可能包含在中。定义6可以保证中的个体皆为Pareto最优解。

3. 多目标进化算法的进化模型

Laumanns [3]给出了采用精英策略的多目标进化算法的一般模型结构UMMEA，协同进化个体种群和精英种群。精英策略是指优良的个体不会因为劣个体的影响而被排除出种群的基因池。其算法流程如下：首先, 采用初始化算子生成进化种群和精英种群，并选择参数精英强度。然后,由当前的进化种群和精英种群生成子代种群。其中, 精英强度控制精英个体的参与程度，即从精英种群中选择个体作为交配个体的概率。取样过程由取样算子(sample)控制，变化算子（vary）则通过交叉和变异操作而产生子代个体。虽然PAES，SPEA，SPEA2皆可抽象为这样的构架，然而对于NSGAII和-MOEA来说，却需要做一些必要的修正，如算法1所示。
算法1 修正的具有精英策略的多目标进化算法。表示精英种群，表示进化种群，表示精英强度，表示子代种群。
1.
2.
3. while terminatefalse do
4.
5. vary
6.
7.
8.
9. end while

算法1在进化过程中强调了子代种群同父代种群之间的竞争作用。这种竞争不仅在评估过程中而且也分别在两个种群的更新算子（和）中。显然，-MOEA可以看作算法1的一个实例，NSGAII即是精英种群设置为零的特殊情形。当直接把子代种群看作下一代进化种群时，算法1同Laumanns所提的UMMEA是等价的[3]。由于进化种群的更新过程同精英种群是相对独立的，在进化过程中或许有部分的精英个体进入进化种群。因此,精英强度重新定义为从两个协同种群中选择的交配个体都为精英的概率。

4．EDMOEA 算法

在本节中，我们提出了一类新的基于-支配关系的多目标进化算法。同-MOEA一样，它也可以分解为算法1的实例。这两个算法的主要区别即在于精英种群的更新策略上。新算法的更新策略结构简单，且具有较少的参数设置。

4.1 精英种群的更新策略

首先，我们给出对于给定的集合逼近其Pareto最优解集的迭代搜索算法的基本框架[13]，如算法2所示。
算法2 迭代的搜索算法
1:
2:
3: while terminate false do
4:
5: generate()
6: update
7: end while
8: Output:

其中,表示迭代次数，表示在第次循环时所产生的新的个体，而集合表示时的精英种群。算子generate()是指在第次迭代时产生新的子代个体；update()表示结合新的子代个体对原有的精英种群做更新操作，其流程如算法3所示。
算法3 生成Pareto最优解集的更新算法
1: Input: ,
2: if such that then
3:
4: else
5:
6:
7: end if
8: Output: .

显然，如果我们采用算法3的更新策略，通过算法2所得到的最终种群将是Pareto最优解集的子集合。然而若仅仅将算法3第2行的Pareto支配关系改为-Pareto支配关系，最后所输出的解集仅仅是-Pareto最优解集近似[13]。故一类新的用以生成-Pareto解集的算法构成如下：
算法4 生成-Pareto解集的更新算法
1: Input: ,
2: if such that then
3:
4: Output: ; // 算法终止
5: else
6:
7:
8: end if
9: if such that then
10:
11: else
12:
13: end if
14: Output: . // 算法终止
定理3 设是第代生成的个体，为到第代为止所生成的个体的集合。而指根据算法4的更新策略在第代时所输出的最终种群，则是的一个-Pareto 解集。
证明：首先，可证。令任意,,。假设存在,,。如果，则在时不会被接收（算法4，第3行）；如果存在,，使得，则根据Pareto支配关系的传递性可知，故依然被排除在最终种群之外。如果，则将会从中被移除（算法4，第7行）。这皆与矛盾。故假设不成立，即中的任一个体均为非被支配解。
其次，可证是集合的-Pareto最优解集近似。假设其不正确，则当且仅当存在,，其不被的任何成员-Pareto支配，但却不属于集合。倘若不属于集合，则其或者在时不被集合接收，或者在时被接收但在以后的更新过程中被移除。对于后者，只有当可以支配的个体进入中，移除才能进行。根据定理1，若两个个体满足支配关系则意味着它们也满足-支配关系。而又因为支配关系具有传递性，故在输出种群中必有一个体可以-支配，这与假设矛盾。另一方面，拒绝操作发生在算法4的第2或第9行。同理可知，如果个体被拒绝，则表明种群中存在某一个体对它具有-支配关系。而根据定理2，即使这样的个体在以后的更新过程中被移出，其替代个体仍然可以-支配，亦与假设矛盾。
故综合可知，是的一个-Pareto 解集。定理得证。
可见利用算法4的更新策略，可以保证最终的输出种群为Pareto最优解集的子集，且其中的个体成员的-邻域内都无其它个体，保证了均匀的分布性。值得注意的是，在输出种群中可能存在一些个体，这里我们称之为“临近点”。它们位于Pareto前沿的边缘，可以-支配一些虽然处在前沿面上但和它们不具有Pareto支配关系的个体。而当进化结束时，如果能够支配这些“临近点”的个体没有生成，则它们将会保留到最终的输出种群中。不过根据定理2可知，这些点的存在不会影响算法4的收敛性。实际上，它们仍可以看作当前种群中的Pareto最优解，因为一旦能够支配它们的个体生成，它们将会从最终种群中移除。

4.2 EDMOEA算法流程

结合算法4中的更新策略，EDMOEA的算法流程如下：
（1）随机生成初始种群，将其中的不可支配个体复制到第二种群，并求出其在目标上的极值点，，并设置进化代数。
（2）从中随机选择一个个体，设其为。
（3）以和作为父代，如果则更换其它的目标的极值个体。对所选父代遗传操作（交叉和变异），生成的子代个体设为，。
（4）比较，的支配关系，选择非被支配的个体；如果两者互为不可支配，则比较-支配关系。如果均不可行，则随机选择一个作为优胜者，然后利用算法4的更新策略，将其加入种群之中。
（5）如果不满足终止条件，令，从第2步开始重新进化；否则，即为最终的输出种群。
显然，EDMOEA算法可以分解为统一模型的特例。因为其选择进行交配的个体都是当前种群中的非被支配个体即精英个体，故EDMOEA在进化过程中的精英强度将一直为1.0，为高精英强度进化算法。如[16]所述，在多目标进化算法中高精英参与比例有利于种群的收敛。由于父代个体之一，，为所对应目标的当前极值，故若，则必不等于，，除非精英种群中只有唯一的个体。所以这种策略可以避免对相同的个体进行遗传操作。
EDMOEA与-MOEA在算法结构尤其是精英种群的更新策略上有显着的区别：
首先，-MOEA根据的支配关系将目标函数空间中的点转化为网格向量，这样通常会导致一些在某一目标上的函数值是极端值的个体被支配，从而缺失于最终的输出种群。如[17]所述，如果这些代表Pareto前沿边界的个体被排除，精英种群所逼近的前沿面将会收缩，从而算法将收敛到部分的Pareto前沿面。但是采用算法4的更新策略，当前种群的极端个体将会保留到下一代，除非有可以支配它们的个体产生，而若其能够支配具有极端值的个体，则必在对应目标上具有更好的边界取值。
其次，在网格向量的计算过程中，尤其在对实际问题的处理时，需要各个目标函数上可能取得的最小值的信息。虽然它们可以在算法进行过程中获得，但当新的最小值产生后，需要对当前的精英种群中个体的网格向量值进行更新。这些都将增加计算量。采用EDMOEA的更新策略，只需要各个目标上的参数值，而且更新操作中仅需比较新个体与精英种群的支配关系，计算复杂度同种群大小呈线性关系。
最后，如图1所示，在-MOEA中，对于同一网格中个体的处理，无法保证相邻网格的个体保持一致的分布。而根据算法4的更新策略，一旦个体在精英种群中确定，其的-邻域内将不在有个体被包括在最终的种群中（如图2所示）。因此相比-MOEA，其将更有效的保持种群的多样性。

图1：图中所有个体都属于Pareto前沿面；点A和B，点C和D分别位于同一个网格内。根据-MOEA算法网格内的操作策略，点A和D将分别被点B和C取代，种群分布的均匀性将降低。

图2：点所支配的区域如图中阴影所示。根据-支配关系，其支配域扩展到点所支配的区域即虚线所包括的范围，从而点临近的个体将从精英种群中排除。

4.3 自适应调整策略

根据上述讨论可见，取值在基于-支配的进化算法中起关键作用。Laumanns[13]曾给出的估值公式，并提出一种动态调整值以获取给定规模的解集的方法。首先从一个最小的值开始，当精英种群中的个体数量超过事先给定的最大规模时，则按照某种规则增大取值。然而当新的值设定后，精英种群中个体的网格向量值需要更新，这需要额外的计算量。另一方面，当新的网格向量值取定后，精英种群内的个体需按照其新的网格向量坐标重新确定网格的支配关系，同样将耗费额外的计算量。
事实上，我们发现在EDMOEA算法中大的取值反而更有利于算法的收敛（见5.1），故据此，我们提出一种自适应的调整方法如下：
1． 开始于一个最大的取值；
2． 如果满足终止条件则终止调整策略，否则按照预先设定的下降幅度，，减少当前的取值，即如下式所示：
，
显然当从一个大的取值开始时，精英种群中现存个体的-支配关系不会因为值的降低而发生变化。因此没有必要再对它们进行重新的比较。结合如[17]的终止法则，我们给出了如下的终止条件：
1) 当适应值函数计算次数超过给定的最大上限（这里设为250*100）；
2) 当在给定的一段连续的进化代数后，精英种群没有新的个体出现。因为精英种群中新产生的个体将丰富当前Pareto前沿的多样性或者将其朝向真实的Pareto前沿逼近。
3) 当在给定的一段连续的进化代数后，精英种群中的极端个体的目标函数值没有变化。精英种群中的极端值的变化在一定程度上也反应了种群的收敛性。于是同上一个终止法则相结合，如果它们都在给定的计算次数后保持不变，则表明深度搜索已经充分进行，需要降低的取值开始进行当前Pareto前沿的广度搜索。这样可以增加依靠当前Pareto前沿的多样性，引导搜索朝向真正的Pareto前沿面推进。
4) 当的值达到其的底线。
可见这种自适应的调整策略类似与模拟退火的思路，当按照既定的判断标准，种群进化没有进展时，则按照如上的调整公式，降低在各个目标函数上的限制范围，从而促使种群的进化。注意到第二和第三个终止法则中有一个重要的参数即给定的一段连续进化代数，本文中我们将其设置为200。同时设定最大的取值为0.06，最小的为0.0006。

5．实验结果和讨论

在本节中，计算实验采用了多目标进化算法测试中被广泛应用的5个多目标函数[10]，这些函数包括双目标函数，具有凸性、多模态等不同特性。首先讨论了在不同取值下的EDMOEA的性能，然后通过其它通用多目标进化算法，如NSGAII，SPEA2，-MOEA等，进行比较分析，表明 了EDMOEA和AEDMOEA的优越性。

5.1 对于不同取值的EDMOEA算法的收敛性

首先，分别采用5个不同的值0.0006，0.006，0.06，0.6，0.9（这里我们认为在各个目标上的取值一致且算法进化种群大小为100，进行25，000次适应值评价），结果表明当为较大的取值，EDMOEA可以更好的收敛到Pareto前沿曲面。
采用当代距离指标（General Distance，GD）[18]包括的GD-Max和GD-Min两种性能指标，评测最终种群同Pareto前沿面的接近程度。它们各自表示最终近似种群中的个体到Pareto前沿面的距离的最大值和最小值。实验结果如表4-5所示。

表1：GD-Max值的平均值和标准差

ZDT1
ZDT2
ZDT3
ZDT4
ZDT6

0.0006
Mean
1.2119E-02
1.0863E-03
1.1407E-02
1.1129E-02
1.3745E-02
Stdev
2.7043E-03
1.4911E-05
1.6469E-03
3.4330E-03
9.8181E-05

0.006
Mean
2.6564E-03
1.0806E-03
6.9647E-03
3.3678E-03
1.3027E-02
Stdev
1.3827E-03
8.6884E-05
1.4223E-03
1.2395E-03
3.3852E-04

0.06
Mean
6.2141E-04
7.8769E-04
1.4519E-03
1.4695E-03
7.3574E-03
Stdev
6.8781E-05
1.8808E-04
3.3364E-04
1.3116E-03
2.2523E-03

0.6
Mean
2.9802E-09
2.4039E-15
1.8433E-03
1.9133E-03
6.0361E-04
Stdev
4.0809E-09
1.9155E-16
1.0071E-03
1.0973E-03
6.0102E-05

0.9
Mean
1.4901E-09
2.8339E-15
1.6932E-02
5.4584E-03
6.9877E-04
Stdev
3.3320E-09
3.6043E-16
3.6553E-02
3.6419E-03
4.2815E-05

表2：GD-Min值的平均值和标准差

ZDT1
ZDT2
ZDT3
ZDT4
ZDT6

0.0006
Mean
1.1677E-06
8.1417E-07
4.1711E-07
4.4446E-05
4.5246E-04
Stdev
3.2006E-07
4.2412E-07
7.0470E-08
3.4413E-05
7.1094E-06

0.006
Mean
1.0209E-07
4.2881E-08
4.4036E-09
2.1387E-04
4.4955E-04
Stdev
2.8099E-08
2.5259E-08
2.3637E-09
2.1250E-04
3.7961E-05

0.06
Mean
8.1530E-16
6.6754E-16
2.3022E-09
4.6551E-04
4.3190E-04
Stdev
1.0178E-16
1.5594E-16
3.1532E-09
6.6613E-04
8.7040E-05

0.6
Mean
5.9999E-16
3.9996E-16
4.4703E-09
9.1825E-04
4.0733E-04
Stdev
2.1477E-16
9.9460E-17
4.0808E-09
4.9524E-04
5.1721E-05

0.9
Mean
8.9474E-16
8.4396E-16
1.5822E-04
2.4948E-03
4.7580E-04
Stdev
2.7979E-17
9.9292E-17
5.4430E-05
1.6005E-03
4.7043E-05

表3：最终种群大小的平均值

ZDT1
ZDT2
ZDT3
ZDT4
ZDT6
0.0006
681.7
769.8
302.6
782
528.6
0.006
98.9
90.7
41.5
99.9
87.6
0.06
10.4
8.5
5.9
10
9.4
0.6
2
2
3
2
2
0.9
2
2
2
2
2

如表1-2所示，随着参数值的增大，EDMOEA在各个问题上的GD-Max和GD-Min的取值呈先减小后增大趋势，图中加粗部分即是各自变化的转折点。对于ZDT1，ZDT2，ZDT3问题，当增至0.06时GD-Min显着减小，表明种群中已有个体充分接近真实Pareto前沿。对于ZDT4问题，尽管当取得0.0006时，GD-Min最小，但当增至0.06时，GD-Max值最小，即整体收敛性在＝0.06时最好。当＝0.06时，ZDT6问题的GD-Max显着减小，在＝0.6时达到最小，而后其GD-Min随增大呈小幅下降，当＝0.6时最小。需要注意的是，当取值过大时，最终收敛种群的规模有限（如表3可见），例如当＝0.6，0.9时，最终种群中只有两个个体在Pareto前沿两端，即各个目标函数的极值点。所以尽管这样得到的GD-Max和GD-Min值很小，但这十分不利于决策者做出最好的选择。事实上，在进化算法的搜索过程中，深度搜索和广度搜索是相互交叉进行的。当选择大的取值的时候，EDMOEA偏重于深度搜索即引导搜索朝向真实的Pareto前沿面，而当采用小的取值，EDMOEA则在当前的Pareto前沿面进行搜索而取得更好的分布性。故我们推荐从较大的取值开始，如＝0.06，直至减少到最小的值。

5.2 EDMOEA和AEDMOEA同其它多目标进化算法的比较

在本节中，EDMOEA、采用自适应调整策略的AEDMOEA、NSGAII、-MOEA、SPEA2等，均用于求解5个测试函数，并针对收敛性、分布性及计算效率对各个算法进行比较分析。
具体的设置如下：所有初始种群中个体的基因都是随机产生且采用实数编码。交叉操作采用仿二进制交叉算子（Simulated Binary Crossover）[19]，变异操作采用多项式变异算子（Polynomial Mutation）[20]，其中的交叉算子参数，变异算子参数20。对于EDMOEA算法，在5个测试函数上都设置相同的参数，（）。SPEA2算法的-近邻参数计算方法如下：（表示种群，表示精英种群大小）。AEDMOEA，EDMOEA，和-MOEA都采用稳态的进化策略，且适应值评价的最大次数为25,000。所有算法的其它共有参数设置如表4所示。

表4：参数设置( nreal表示自变量个数)

AEDMOEA
EDMOEA
-MOEA
NSGAII
SPEA2
交叉概率
1.0
1.0
1.0
1.0
0.5
变异概率
1/nreal
1/nreal
1/nreal
1/nreal
1/nreal
种群大小
100
100
100
100
100
精英种群大小
------
-----
-----
100
100
最大进化代数
------
-----
-----
250
250

为了比较5个算法的性能，采用一元评价指标函数。所谓一元评价指标函数是从向量集合到实数集的映射[21]：。利用实数集合上的全序关系，可以比较在空间中的不同向量集合之间的质量。不同的一元指标函数采用了不同的偏好信息。对于给定的集合，定义=，计算与参考集合的指标函数值，其值越小，表明所用集合的质量越高。我们采用比较常用的两个指标函数：Hypervolume指标函数（记为）[4]，Epsilon指标函数（采用加的形式）（记做）[22]。因为两个指标函数采用了不同的偏好信息，若对于相同的比较集合和，它们指标值的序关系分别为和，则可以推断这两个集合是等价的。其中，参照集合构造如下[21]：联合5个算法在运行中所产生的最终近似种群，然后去除其中被支配的和重复的个体。这样，参照集合中的个体即不被任何联合种群中个体所支配。实验结果如表5-9所示。

表5：ZDT1问题的Hypervolume和Epsilon指标的平均值和标准差
MOEA
Hypervolume
Epsilon
Avg
Stdev
Avg
Stdev
AEDMOEA
2.3221E-03
4.5232E-04
1.0038E+00
6.1064E-04
EDMOEA
4.1366E-03
7.3935E-05
1.0052E+00
1.5816E-04
-MOEA
5.5432E-03
1.1594E-04
1.0054E+00
4.0785E-04
NSGAII
6.6350E-03
1.7487E-04
1.0097E+00
1.4182E-03
SPEA2
5.1888E-03
1.7263E-04
1.0057E+00
1.9069E-04

表6：ZDT2问题的Hypervolume和Epsilon指标的平均值和标准差
MOEA
Hypervolume
Epsilon
Avg
Stdev
Avg
Stdev
AEDMOEA
1.7763E-03
4.7114E-04
1.0027E+00
5.9819E-04
EDMOEA
4.2077E-03
9.6955E-05
1.0043E+00
4.7361E-04
-MOEA
3.9445E-03
1.5821E-04
1.0035E+00
7.7450E-05
NSGAII
6.5375E-03
4.3199E-04
1.0077E+00
1.1035E-03
SPEA2
5.4256E-03
1.4433E-04
1.0050E+00
1.8684E-04

表7：ZDT3问题的Hypervolume和Epsilon指标的平均值和标准差
MOEA
Hypervolume
Epsilon
Avg
Stdev
Avg
Stdev
AEDMOEA
4.1403E-04
4.9025E-05
1.0010E+00
1.2560E-04
EDMOEA
4.1264E-03
2.7001E-04
1.0050E+00
3.1227E-04
-MOEA
5.6172E-03
2.1776E-04
1.0064E+00
5.7231E-05
NSGAII
2.6110E-03
2.4214E-04
1.0052E+00
9.0772E-04
SPEA2
2.5096E-03
1.7234E-04
1.0052E+00
5.8042E-04

表8：ZDT4问题的Hypervolume和Epsilon指标的平均值和标准差
MOEA
Hypervolume
Epsilon
Avg
Stdev
Avg
Stdev
AEDMOEA
5.6634E-03
1.8432E-03
1.0090E+00
2.1064E-03
EDMOEA
6.9780E-03
2.9405E-03
1.0079E+00
1.6726E-03
-MOEA
3.5970E-02
2.2407E-02
1.0968E+00
6.9649E-02
NSGAII
9.2137E-03
3.0440E-03
1.0096E+00
1.2534E-03
SPEA2
7.9398E-03
2.7921E-03
1.0071E+00
1.4421E-03

表9：ZDT6问题的Hypervolume和Epsilon指标的平均值和标准差
MOEA
Hypervolume
Epsilon
Avg
Stdev
Avg
Stdev
AEDMOEA
7.7802E-04
1.4189E-04
1.0012E+00
1.3933E-04
EDMOEA
5.0907E-03
9.8829E-05
1.0047E+00
1.1774E-04
-MOEA
8.2441E-03
5.6592E-04
1.0058E+00
3.6547E-04
NSGAII
1.8575E-02
1.3916E-03
1.0129E+00
1.7363E-03
SPEA2
1.5011E-02
1.4401E-03
1.0110E+00
1.9763E-03

ZDT1问题是检测算法寻找具有凸性的Pareto最优解集的能力，如表5所示。AEDMOEA在Hypervolume和Epsilon指标上各自取得最小值而EDMOEA取得次小值，NSGAII所得到的近似集合质量最低。ZDT2问题是检测算法对于非凸性Pareto最优解集的处理能力,AEDMOEA最优，-MOEA次之，而NSGAII表现最差。ZDT3问题的Pareto前沿面是非连续的，SPEA2在Hypervolume指标上次优，而EDMOEA在Epsilon指标上要优于SPEA2劣于AEDMOEA。这表明SPEA2和EDMOEA在ZDT3问题上等价，且均劣于AEDMOEA。表8所示为5个算法在处理具有大量局部Pareto前沿点的ZDT4问题的结果。AEDMOEA和SPEA2分别在Hypervolume和Epsilon指标上各自取得最小值，EDMOEA在Hypervolume指标上次优，而其Epsilon指标值要略优于AEDMOEA，故可知三个算法在ZDT4问题上等价。ZDT6问题的Pareto前沿面的个体呈非均匀分布。AEDMOEA在两个指标函数上各自取得最优值，EDMOEA次之，NSGAII最差。由表10的关于ZDT4和ZDT6问题的Hypervolume指标的非参数kruskal-wallis检验，亦可知AEDMOEA和EDMOEA均要显着优于其它的比较算法。

表10：ZDT4和ZDT6问题的Hypervolume指标的非参数kruskal-wallis 检验的值[21]。原假设：行样本同对应的列样本服从相同的分布；备择假设：行样本具有比列样本更好的分布。其中为单尾值，置信参数。
ZDT4问题

AEDMOEA
EDMOEA
-MOEA
NSGAII
SPEA2
AEDMOEA
---
6.2008E-02
4.3926E-13
1.6544E-05
1.2902E-03
EDMOEA
9.3799E-01
---
3.2003E-10
2.6306E-03
6.0566E-02
-MOEA
1.0000E+00
1.0000E+00
---
9.9997E-01
1.0000E+00
NSGAII
9.9998E-01
9.9737E-01
2.9312E-05
---
9.0304E-01
SPEA2
9.9871E-01
9.3943E-01
2.0391E-07
9.6957E-02
---
ZDT6问题

AEDMOEA
EDMOEA
-MOEA
NSGAII
SPEA2
AEDMOEA
---
9.0874E-05
6.7804E-09
3.4672E-14
4.7204E-12
EDMOEA
9.9991E-01
---
9.0874E-05
7.6634E-12
4.9021E-09
-MOEA
1.0000E+00
9.9991E-01
---
9.4174E-09
5.9400E-05
NSGAII
1.0000E+00
1.0000E+00
1.0000E+00
---
9.9979E-01
SPEA2
1.0000E+00
1.0000E+00
9.9994E-01
2.1363E-04
---

上述讨论表明，对于双目标优化问题，除含有大量局部Pareto前沿面的ZDT4问题外，AEDMOEA算法性能均要优于其它算法。即使在ZDT4问题上，其也是等价与SPEA2和EDMOEA算法。另外，根据两个性能评价指标的标准方差