论文阅读：《Many-Objective Evolutionary Algorithms: A Survey. 》多目标优化问题的优化目标评估的相关内容介绍

前言

提醒：
文章内容为方便作者自己后日复习与查阅而进行的书写与发布，其中引用内容都会使用链接表明出处（如有侵权问题，请及时联系）。
其中内容多为一次书写，缺少检查与订正，如有问题或其他拓展及意见建议，欢迎评论区讨论交流。

内容由AI辅助生成，仅经笔者审核整理，请甄别食用。

---

论文引用：
Bingdong Li, Jinlong Li, Ke Tang, and Xin Yao. 2015. Many-Objective Evolutionary Algorithms: A Survey. ACM Comput. Surv. 48, 1, Article 13 (September 2015), 35 pages. https://doi.org/10.1145/2792984

多目标优化算法的度量评估

相关背景与定义如下：

定义1（多目标优化问题的优化目标）

优化多目标优化问题（MaOP）的目标，是得到帕累托前沿（PF）的一个近似集$A$，包含以下两个子目标：
(1)$A$中所有解尽可能接近真实帕累托前沿（PF）；
(2)$A$中解在目标空间内尽可能分布均匀。

“近似集”的定义如下：

定义1.1（近似集）

设$A\subseteq \Lambda$为一组目标向量集合，记A={a1,a2,…,a∣A∣}A = \{ \mathbf{a}_1, \mathbf{a}_2, \ldots, \mathbf{a}_{|A|} \}A={a1​,a2​,…,a∣A∣​}。若$A$中任意元素，既不支配$A$中其他目标向量，也不与其他目标向量相等，则称$A$为近似集 。

对应优化目标，近似集的质量从两方面衡量：
(1) 收敛性：在目标空间中与真实帕累托前沿（PF）的贴近程度；
(2) 多样性：解在帕累托前沿（PF）上的分布均匀性。
“质量指标”是对质量的量化度量，定义如下：

定义1.2（质量指标）

$k$元质量指标$I$是一个函数$I:{\Gamma }^k\to \mathbb{R}$，为$k$个近似集的向量$(A_1,A_2,\dots ,A_k)$赋予实数值$I(A_1,A_2,\dots ,A_k)$。

具体质量指标说明

1. 超体积指标（$I_{HV}$，又称$S$度量 ）

描述：对应每个解${\mathbf{a}}_i\in A$，计算超立方体$c_i$并集的勒贝格测度（Lebesgue measure ）。公式为：
IHV(z∗,A)=L(⋃i:ai∈Aci)=L(⋃a∈A{b∣a≺b≺z∗})I_{HV}(\mathbf{z}^*, A) = L\left( \bigcup_{i: \mathbf{a}_i \in A} c_i \right) = L\left( \bigcup_{\mathbf{a} \in A} \{ \mathbf{b} \mid \mathbf{a} \prec \mathbf{b} \prec \mathbf{z}^* \} \right) IHV​(z∗,A)=L(i:ai​∈A⋃​ci​)=L(a∈A⋃​{b∣a≺b≺z∗})
其中${\mathbf{z}}^{\ast }$是目标空间中的最差参考点。该指标同时衡量近似集的收敛性与多样性 。

2. 世代距离（GD）与反转世代距离（IGD）

• 世代距离（GD）：
  衡量近似集$A$到帕累托前沿（PF）的收敛质量。公式为：
  $$GD=\frac{1}{|A|}{\left(\sum _{i=1}^{|A|}dis({\mathbf{a}}_i,P{F}^{\prime }{)}^p\right)}^{\frac{1}{p}}$$
  （$P{F}^{\prime }$是 PF 的子集，$dis({\mathbf{a}}_i,P{F}^{\prime })$是${\mathbf{a}}_i$到$P{F}^{\prime }$的距离 ）

• 反转世代距离（IGD）：
  同时衡量近似集的收敛性与多样性。公式为：
  $$IGD=\frac{1}{|P{F}^{\prime }|}{\left(\sum _{i=1}^{|P{F}^{\prime }|}dis({\mathbf{p}}_i,A{)}^p\right)}^{\frac{1}{p}}$$
  （$dis({\mathbf{p}}_i,A)$是${\mathbf{p}}_i$到近似集$A$的距离 ）

  类似的距离基指标，如 additive approximation metric、${\Delta }_p$指标等，也被用于性能度量 。

3. 广义扩展指标（IGS）

用于衡量近似集的多样性，定义如下：
$$IGS=\frac{{\sum }_{i=1}^{s}d({\mathbf{e}}_i,A)+{\sum }_{\mathbf{p}\in P{F}^{\prime }}|d(\mathbf{p},A)-\bar{d}|}{{\sum }_{i=1}^{s}d({\mathbf{e}}_i,A)+|P{F}^{\prime }|\bar{d}}$$
其中：

• {e1,…,es}\{ \mathbf{e}_1, \ldots, \mathbf{e}_s \}{e1​,…,es​}是$P{F}^{\prime }$中的$s$个极端解；
• $d(\mathbf{p},A)$是$\mathbf{p}$与$A$的欧氏距离；
• $\bar{d}$是所有$\mathbf{p}\in P{F}^{\prime }$对应$d(\mathbf{p},A)$的均值 。

4. R2 指标

基于效用函数的指标类别。给定参考集$R$，定义为：
R2(A,U)=−1∣U∣∑u∈U(max⁡a∈A{u(a)})R2(A, U) = -\frac{1}{|U|} \sum_{u \in U} \left( \max_{\mathbf{a} \in A} \{ u(\mathbf{a}) \} \right) R2(A,U)=−∣U∣1​u∈U∑​(a∈Amax​{u(a)})
（$U$是效用函数集合 ）

若将$U$设为一系列带权重的切比雪夫（Tchebycheff）函数，权重向量集为$V$，并选乌托邦点${\mathbf{z}}^{\ast }$加入$R$，则 R2 指标可定义为：
R2(z∗,A,V)=1∣V∣∑λ∈Vmin⁡a∈A{max⁡j∈{1,…,m}{λj∣zj∗−aj∣}}R2(\mathbf{z}^*, A, V) = \frac{1}{|V|} \sum_{\lambda \in V} \min_{\mathbf{a} \in A} \left\{ \max_{j \in \{1, \ldots, m\}} \{ \lambda_j | z_j^* - a_j | \} \right\} R2(z∗,A,V)=∣V∣1​λ∈V∑​a∈Amin​{j∈{1,…,m}max​{λj​∣zj∗​−aj​∣}}
该指标可同时衡量近似集的收敛性与多样性 。

质量指标的局限性与补充

根据 Zitzler 等人（2003）的研究，不存在单一质量指标能直接判定近似集$A$优于$B$。多数质量指标仅能表明$A$“不差于”$B$（即$A$至少和$B$一样好 ）。 为克服此局限，可采用二元指标（如 Zitzler 等人 2003 提出的二元$ϵ$- 指标 ）辅助评估。

整体围绕多目标优化算法的“质量度量”展开，明确优化目标（近似帕累托前沿的收敛性 + 多样性 ），并详细介绍超体积、世代距离、R2 等指标的定义与作用，同时指出单一指标的评估局限及补充方案。

以下是对内容的翻译及核心实体信息梳理：

多目标优化的关键挑战

当目标数量增加时，需应对以下问题：

• 支配抗性（DR）现象 ：因大量非支配解占比急剧上升，导致解间“不可比性”难题（文献来源：Fonseca and Fleming 1998；Purshouse and Fleming 2007；Knowles and Corne 2007 ）。
• 解集规模受限 ：非退化场景下，$m$目标问题的帕累托前沿（PF）是$(m-1)$维流形（文献：Ishibuchi et al. 2015；Jin and Sendhoff 2003 ）。描述该前沿需指数级增加解的数量。
• 目标空间解的可视化 ：需特殊技术，如投影到低维空间、用平行坐标等（文献：Walker et al. 2013 ）。

研究表明，基于帕累托支配的算法（如 NSGA-II 、SPEA2 ）在多目标优化问题（MaOPs）上性能显著下降（文献：Knowles and Corne 2007 ），主因是 DR 现象 和 主动多样性促进（ADP）机制 。ADP 指当基于支配的主准则无法区分解时，激活基于密度的次准则筛选存活解；受 DR 和 ADP 影响，最终解集可能无法收敛到 PF，反而远离前沿（文献：Wagner et al. 2007 ）。

提升基于帕累托算法可扩展性的两类思路：

• 缓解 DR 影响：采用松弛支配方法，改进帕累托支配以增强向 PF 的选择压力（文献：Laumanns et al. 2002；Sato et al. 2007 ），相比经典帕累托支配，更易区分多目标优化问题的解。
• 应对 ADP 问题：设计基于多样性的策略（文献：Adra and Fleming 2011 ），更关注收敛性。

非帕累托基的多目标进化算法（如基于指标、基于聚合的方法 ），不依赖帕累托支配推动种群向 PF 进化，无选择压力难题，但受“维度诅咒”困扰——需同时搜索指数级增长的方向。其中：

• 聚合基方法的关键是权重向量设置（文献：Giagkiozis et al. 2013 ），影响种群分布维持效果。
• 超体积基算法受限于高计算成本（文献：Wagner and Neumann 2013 ）。

此外，基于参考集的方法（用参考集评估、选择解 ）为多目标优化问题提供新解法（文献：Deb and Jain 2014 ）；降维方法通过分析目标间关系、特征选择减少目标数；偏好基方法融入用户偏好，聚焦 PF 特定区域；降维方法也尝试消除次要目标，降低原问题难度（文献：Brockhoff and Zitzler 2009 ）。