admin管理员组

文章数量:1034213

多目标优化算法之算法性能评价

本专栏发布多目标优化算法相关内容，主要内容为经典算法介绍（NSGA-II、NSGA-III、MOPSO、MOEA/D、SPEA2、PESA-II等）以及近年来的新兴算法介绍（MOGWO等）、算例（ZDT系列、DTLZ系列、WFG系列等）、算法循环测试方法、算法性能评价。

先介绍算法性能评价部分

通常，多目标优化中的性能指标可分为仅评估收敛性的指标（例如，GD和CM）；仅评估多样性的指标，例如，Spacing和PD；以及同时评估收敛性和多样性的参数（例如，IGD和HV）。大多数现有性能指标的详细列表可在本文中找到。

1 收敛性convergence

1.1 世代距离GD（generational distance）

% D. A. Van Veldhuizen, Multiobjective evolutionary algorithms: Classifications, analyses, and new innovations , 1999.

评估算法得到的非支配解集PF与真实Pareto前沿PFtrue之间的距离。

GD=\frac{\sqrt{\sum_{i=1}^{N}d_i^2}}{N}

N为非支配解集个数，di为第i个非支配解与PF最近的点的距离，其越小越好，若GD=0说明所有解都在真实pareto前沿上。

2 分布性diversity

2.1 基于距离：空间度量指标Spacing

J. R. Schott, Fault tolerant design using single and multicriteria genetic algorithm optimization Master's thesis, Department of Aeronautics and Astronautics, Massachusetts Institute of Technology, 1995.

Spacing\left(P\right)=\sqrt{1/(|P|-1)\ \sum_{i=1}^{|P|}(d\ ̄-d_i )^2 }

其中 di表示第i个解到P中其他解的最小距离，d\ ̄ 表示所有解的平均值。简而言之，“间距”测量的是每个解与其他解的最小距离的标准偏差。因此，该度量评估解集的均匀性，而不考虑其分布性。

基于距离的评价指标还有一个Δ，在Deb提出NSGA-II算法中一块提出的。但是在高维目标情况（尤其是目标大于3时）效果不理想，因此并未此种方法。

2.2 基于网格：网格分布度DM（最优面不连续的不适用）

K. Deb and S. Jain, Running performance metrics for evolutionary multi objective optimization, KanGAL Report 2002004, 2002.

Deb于2002年提出了网格分布性评价方法(Debetal，2002b)，其方法是首先将解集中的非支配个体映射到一个合适的超平面上，这样就可以少考虑一维的信息，然后将映射平面分成一些网格(或者是m-1维的盒子)，根据格子里包含的非支配个体的情况来计算分布度函数。如果所有的格子都有非支配个体，那么这是分布最好的情况。如果有些网格没有一个非支配个体，那么其分布性就比较差。这种方法需要选择一些参数，如映射的超平面网格的大小等。

2.3 基于其他领域（信息熵或生物学）：以生物多样性PD为例

H. Wang, Y. Jin, and X. Yao, “Diversity assessment in many-objective optimization,” IEEE Trans. Cybern., vol.47, no. 6, pp. 1510–1522, 2017.

PD(P)=\max{p\inP}(PD(P-{p})+\min{q\inP-{p}}f(p)-f(q))

应该注意的是，PD是为评估填充超立方体的点的多样性而设计的，而MOP的Pareto最优解通常位于M维所有目标空间中的（M-1）维流形上，因此，远离帕累托前沿的解通常对 PD 值贡献更大。因此，PD 主要考虑收敛性，因为收敛性较差的解通常具有较大的分散性。

3 综合评价

3.1 反向世代距离IGD

PIOTR CZYZç AK and ANDRZEJ JASZKIEWICZ Pareto Simulated AnnealingöAMetaheuristicTechnique for multiple-Objective Combinatorial Optimization

世代距离是指算法所获得的非支配解集PFm 中所有解点到 Pareto 最优前沿PF…的平均距离。而反转世代距离则是世代距离的逆向映射，它采用Pareto最优前沿 PE…中的解点到算法所求得的非支配解集PE…的平均距离表示。CMOW假设P表示待评价的近似解集，R表示在Pareto最优前沿上均匀采样的一组参考点，p-r表示近似解集中的解点p到参考点r的欧氏距离。

简单说来,IGD指标度量了R中每个参考点到近似解集P中最近解的平均距离。显然,IGD值越小说明P和R的相似程度越高。由于R中的参考点是从Pareto最优前沿上均匀采样获得的，因此IGD 值越小意味着近似解集P的收敛性和多样性越好。

3.2 改进的反向世代距离IGD+

Hisao Ishibuchi, Hiroyuki Masuda, Yuki Tanigaki, and Yusuke Nojima( Modified Distance Calculation in Generational Distance and Inverted Generational Distance

反转世代距离IGD通过度量Pareto最优前沿PF到算法获得的近似解集PF之间的距离来评估算法的性能。IGD指标的计算相比HV指标而言计算效率更高，这是因为IGD 指标是通过计算两个解点之间的距离获得的，而距离值的计算相比于HV指标中超体积的计算效率会更高，即便在高维目标空间亦是如此。但必须指出，IGD指标相比HV指标而言最大的缺陷在于其不具有Pareto兼容性。为了利用IGD 指标计算效率高，同时克服其与Pareto 支配关系不兼容的缺陷,IGD*指标不仅计算两个点之间的距离，同时还考虑到它们之间的 Pareto支配关系，因此使得IGD指标具有弱Pareto 兼容性，从而提高了度量算法性能的准确性。

3.3 豪斯多夫平均距离averaged Hausdorff distance Δp

2012，Oliver Schutze, Xavier Esquivel, Adriana Lara, and Carlos A. Coello Coello, ¨ Fellow, IEEE Using the Averaged Hausdorff Distance as a Performance Measure in Evolutionary Multiobjective Optimization

-∑dis(x,ry-8dis(y,x),(X,Y)= maxi=1

3.4 超体积HV

1999，Eckart Zitzler and Lothar Thiele Multiobjective Evolutionary Algorithms: A Comparative Case Study and the Strength Pareto Approach

超体积指标 HV 由于和Pareto 支配关系具有兼容性,因而已成为比较流行的性能度量指标。超体指标通过计算非支配解集与参考点围成的空间的超体积来实现对多目标优化算法性能的评估。如下图所示，对于2-目标优化问题而言，非支配解集与参考点构成的区域为灰色阴影部分。

对于HV指标值的计算而言，参考点的设置比较重要。一般地，参考点的

设置有两种，即最差点(非支配解集每维上的最大值组成的向量)和松散形式的最差点。

3.5 CPF

所提出的度量的主要思想是将M维目标空间中的解集投影到(M-1)维空间，然后评估投影解集的多样性。这样的投影有两个优点:首先，由于解集通常位于M 维目标空间中的(M-1)维流形上，因此在目标空间的大部分区域不存在任何解。相比之下，投影解集填充(M-1)维空间中的(M-1)维超立方体，因此更容易评估这种充分采样空间中的多样性。其次，投影消除了收敛性能的影响。

多目标优化算法之算法性能评价

本专栏发布多目标优化算法相关内容，主要内容为经典算法介绍（NSGA-II、NSGA-III、MOPSO、MOEA/D、SPEA2、PESA-II等）以及近年来的新兴算法介绍（MOGWO等）、算例（ZDT系列、DTLZ系列、WFG系列等）、算法循环测试方法、算法性能评价。

先介绍算法性能评价部分

通常，多目标优化中的性能指标可分为仅评估收敛性的指标（例如，GD和CM）；仅评估多样性的指标，例如，Spacing和PD；以及同时评估收敛性和多样性的参数（例如，IGD和HV）。大多数现有性能指标的详细列表可在本文中找到。

1 收敛性convergence

1.1 世代距离GD（generational distance）

% D. A. Van Veldhuizen, Multiobjective evolutionary algorithms: Classifications, analyses, and new innovations , 1999.

评估算法得到的非支配解集PF与真实Pareto前沿PFtrue之间的距离。

GD=\frac{\sqrt{\sum_{i=1}^{N}d_i^2}}{N}

N为非支配解集个数，di为第i个非支配解与PF最近的点的距离，其越小越好，若GD=0说明所有解都在真实pareto前沿上。

2 分布性diversity

2.1 基于距离：空间度量指标Spacing

J. R. Schott, Fault tolerant design using single and multicriteria genetic algorithm optimization Master's thesis, Department of Aeronautics and Astronautics, Massachusetts Institute of Technology, 1995.

Spacing\left(P\right)=\sqrt{1/(|P|-1)\ \sum_{i=1}^{|P|}(d\ ̄-d_i )^2 }

其中 di表示第i个解到P中其他解的最小距离，d\ ̄ 表示所有解的平均值。简而言之，“间距”测量的是每个解与其他解的最小距离的标准偏差。因此，该度量评估解集的均匀性，而不考虑其分布性。

基于距离的评价指标还有一个Δ，在Deb提出NSGA-II算法中一块提出的。但是在高维目标情况（尤其是目标大于3时）效果不理想，因此并未此种方法。

2.2 基于网格：网格分布度DM（最优面不连续的不适用）

K. Deb and S. Jain, Running performance metrics for evolutionary multi objective optimization, KanGAL Report 2002004, 2002.

Deb于2002年提出了网格分布性评价方法(Debetal，2002b)，其方法是首先将解集中的非支配个体映射到一个合适的超平面上，这样就可以少考虑一维的信息，然后将映射平面分成一些网格(或者是m-1维的盒子)，根据格子里包含的非支配个体的情况来计算分布度函数。如果所有的格子都有非支配个体，那么这是分布最好的情况。如果有些网格没有一个非支配个体，那么其分布性就比较差。这种方法需要选择一些参数，如映射的超平面网格的大小等。

2.3 基于其他领域（信息熵或生物学）：以生物多样性PD为例

H. Wang, Y. Jin, and X. Yao, “Diversity assessment in many-objective optimization,” IEEE Trans. Cybern., vol.47, no. 6, pp. 1510–1522, 2017.

PD(P)=\max{p\inP}(PD(P-{p})+\min{q\inP-{p}}f(p)-f(q))

应该注意的是，PD是为评估填充超立方体的点的多样性而设计的，而MOP的Pareto最优解通常位于M维所有目标空间中的（M-1）维流形上，因此，远离帕累托前沿的解通常对 PD 值贡献更大。因此，PD 主要考虑收敛性，因为收敛性较差的解通常具有较大的分散性。

3 综合评价

3.1 反向世代距离IGD

PIOTR CZYZç AK and ANDRZEJ JASZKIEWICZ Pareto Simulated AnnealingöAMetaheuristicTechnique for multiple-Objective Combinatorial Optimization

世代距离是指算法所获得的非支配解集PFm 中所有解点到 Pareto 最优前沿PF…的平均距离。而反转世代距离则是世代距离的逆向映射，它采用Pareto最优前沿 PE…中的解点到算法所求得的非支配解集PE…的平均距离表示。CMOW假设P表示待评价的近似解集，R表示在Pareto最优前沿上均匀采样的一组参考点，p-r表示近似解集中的解点p到参考点r的欧氏距离。

简单说来,IGD指标度量了R中每个参考点到近似解集P中最近解的平均距离。显然,IGD值越小说明P和R的相似程度越高。由于R中的参考点是从Pareto最优前沿上均匀采样获得的，因此IGD 值越小意味着近似解集P的收敛性和多样性越好。

3.2 改进的反向世代距离IGD+

Hisao Ishibuchi, Hiroyuki Masuda, Yuki Tanigaki, and Yusuke Nojima( Modified Distance Calculation in Generational Distance and Inverted Generational Distance

反转世代距离IGD通过度量Pareto最优前沿PF到算法获得的近似解集PF之间的距离来评估算法的性能。IGD指标的计算相比HV指标而言计算效率更高，这是因为IGD 指标是通过计算两个解点之间的距离获得的，而距离值的计算相比于HV指标中超体积的计算效率会更高，即便在高维目标空间亦是如此。但必须指出，IGD指标相比HV指标而言最大的缺陷在于其不具有Pareto兼容性。为了利用IGD 指标计算效率高，同时克服其与Pareto 支配关系不兼容的缺陷,IGD*指标不仅计算两个点之间的距离，同时还考虑到它们之间的 Pareto支配关系，因此使得IGD指标具有弱Pareto 兼容性，从而提高了度量算法性能的准确性。

3.3 豪斯多夫平均距离averaged Hausdorff distance Δp

2012，Oliver Schutze, Xavier Esquivel, Adriana Lara, and Carlos A. Coello Coello, ¨ Fellow, IEEE Using the Averaged Hausdorff Distance as a Performance Measure in Evolutionary Multiobjective Optimization

-∑dis(x,ry-8dis(y,x),(X,Y)= maxi=1

3.4 超体积HV

1999，Eckart Zitzler and Lothar Thiele Multiobjective Evolutionary Algorithms: A Comparative Case Study and the Strength Pareto Approach

超体积指标 HV 由于和Pareto 支配关系具有兼容性,因而已成为比较流行的性能度量指标。超体指标通过计算非支配解集与参考点围成的空间的超体积来实现对多目标优化算法性能的评估。如下图所示，对于2-目标优化问题而言，非支配解集与参考点构成的区域为灰色阴影部分。

对于HV指标值的计算而言，参考点的设置比较重要。一般地，参考点的

设置有两种，即最差点(非支配解集每维上的最大值组成的向量)和松散形式的最差点。

3.5 CPF

所提出的度量的主要思想是将M维目标空间中的解集投影到(M-1)维空间，然后评估投影解集的多样性。这样的投影有两个优点:首先，由于解集通常位于M 维目标空间中的(M-1)维流形上，因此在目标空间的大部分区域不存在任何解。相比之下，投影解集填充(M-1)维空间中的(M-1)维超立方体，因此更容易评估这种充分采样空间中的多样性。其次，投影消除了收敛性能的影响。

本文标签： 多目标优化算法之算法性能评价

版权声明：本文标题：多目标优化算法之算法性能评价 内容由热心网友自发贡献，该文观点仅代表作者本人， 转载请联系作者并注明出处：http://it.en369.cn/jiaocheng/1748127310a2257465.html， 本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容，一经查实，本站将立刻删除。