多目标优化算法评价指标(performance metrics)

作者：Li_阴宅 | 2024-08-09 13:31:35

踩

多目标优化算法评价指标

参考Performance metrics in multi-objective optimization

Riquelme, N., Lücken, C. V., & Baran, B. (2015, 19-23 Oct. 2015). Performance metrics in multi-objective optimization. Paper presented at the 2015 Latin American Computing Conference (CLEI).

1.多目标优化定义

2.常用评价指标

2.1 hypervolume (HV)

2.2 generational distance(GD)

2.3 inverted generational distance(IGD)

2.4 set coverage(C)

单目标优化问题比较各种算法的性能可以直接通过目标值比较，但是多目标优化算法找到的往往是帕累托解，需要一些合适的评价指标来比较这些算法的性能。

1.多目标优化定义

多目标优化问题有n个决策变量，k个目标函数，空间包括两类：n维的决策空间 $\Omega$ ，代表每个解，k维的目标空间 $\Lambda$ ，代表每个解的目标值， $\Omega$ 中的每个点在 $\Lambda$ 都有对应的点，但是 $\Omega$ 中可能多个点对应 $\Lambda$ 中一个点

帕累托支配(Pareto Dominance)：给定属于 $\Omega$ 中的两个解s1和s2，如果s1在每个目标函数上都不比s2差，并且至少有一个更优，那么s1支配s2，如果s1不支配s2且s2也不支配s1，那么两者不可比，定义为 $s1\sim s2$ 。如下1支配2，5支配1，1和4不可比
帕累托最优集(Pareto optimal set)：所有 $\Omega$ 空间里未被支配的解集合 $P^{*}$
帕累托最优前沿(Pareto optimal front)： $P^{*}$ 在 $\Lambda$ 中的映射为帕累托最优前沿 $PF^{*}$
近似集(approximation set)：定义 $A\subseteq \Lambda$ 为一些目标向量的集合，如果对于A中每个元素，都没有支配或等于A中的其它目标向量，那么A被称为一个近似集，所有近似集的集合定义为 $Z$ ，解决现实问题的结果通常是一个近似集A而不是 $PF^{*}$

给定一个近似集A，常从以下三个方面评价这个解集

基数指标(Cardinality metrics)：A的基数是指A 中存在的解的数量，直观上，解的数量越多越好
准确性指标(Accuracy metrics)：A的收敛性，也就是A和理论的帕累托最优前沿距离有多远，如果 $PF^{*}$ 未知，考虑用参考集R代替
多样性指标(Diversity metrics)：包括分布distribution和广度spread，分布是指A中的解的相对距离，广度是指A中的解覆盖的值范围

2.常用评价指标

以下是文献中整理的使用数量排名前10的评价指标及对应类别，本文主要介绍hypervolume (HV)，generational distance(GD)，inverted generational distance(IGD)和set coverage(C)，基本文献里用到的都是这几种方法。

2.1 hypervolume (HV)

hypervolume (HV)也称为S metric，hyper-area，Lebesgue measure，用于评价目标空间被一个近似集覆盖的程度，是最为普遍的一种评价指标。其中需要用到一个参考点(reference point)，HV值为PF与参考点之间组成的超立方体的体积。HV的比较不需要先验知识，不需要找到真实的帕累托前沿。如果某个近似集A完全支配另一个近似集B，那么A的超容量HV会大于B，因此HV完全可以用于Pareto比较。

2.2 generational distance(GD)

用于评价获得的帕累托前沿PF和最优帕累托前沿 $PF^{*}$ ，对于每个属于PF的解x，找到与其最近的 $PF^{*}$ 中的解y，计算其欧式距离，GD为平均最短欧式距离，其值越小，代表收敛性更好，找到的PF与最优帕累托前沿越接近。

2.3 inverted generational distance(IGD)

和GD相似，但是同时考虑了多样性和收敛性，对于真实的最优帕累托前沿中的每个解y，找到与其最近的PF中的解x，计算其欧式距离，取平均值而不需开方，如果 $PF^{*}$ 的数量大于PF数量，那么IGD就能最完整的表达PF的性能，IGD值越好，代表算法多样性和收敛性更好。

如下图分别为GD和IGD，GD是从获取PF出发，找到真实PF中与之距离最近的点，IGD是从真实PF出发，找到获取PF中与之距离最近的点。GD和IGD都需要先确定真实的最优帕累托前沿。

2.4 set coverage(C)

用于评价两个帕累托解集的支配关系，假设A和B是两个帕累托前沿(Pareto fronts)，那么C值可以表达如下，|B|代表B中的解数量，C(A,B)表示B中的解被A的某个解支配的百分比，C(A,B)值越大，A的性能越好。

声明：本文内容由网友自发贡献，转载请注明出处：【wpsshop】