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

前言

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

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

文章目录

• 前言
• 多目标优化算法的度量评估
• • • 相关背景与定义如下：
    • • 定义1（多目标优化问题的优化目标）
      • 定义1.1（近似集）
      • 定义1.2（质量指标）
    • 具体质量指标说明
    • • 1. 超体积指标（ I H V I_{HV} IHV​，又称$S$度量 ）
      • 2. 世代距离（GD）与反转世代距离（IGD）
      • 3. 广义扩展指标（IGS）
      • 4. R2 指标
    • 质量指标的局限性与补充
    • 多目标优化的关键挑战

论文引用：
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={ a 1 , a 2 ,…, 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: Γ k →R I: \\Gamma^k \\to \\mathbb{R} I:Γk→R，为$k$个近似集的向量 ( A 1 , A 2 ,…, A k ) (A_1, A_2, \\ldots, A_k) (A1​,A2​,…,Ak​)赋予实数值 I( A 1 , A 2 ,…, A k ) I(A_1, A_2, \\ldots, A_k) I(A1​,A2​,…,Ak​)。

具体质量指标说明

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

描述：对应每个解 a i ∈A \\mathbf{a}_i \\in A ai​∈A，计算超立方体 c i c_i ci​并集的勒贝格测度（Lebesgue measure ）。公式为：
I H V( z ∗ , A ) = L ( ⋃ i : a i ∈ A c i ) = 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∗})
其中 z ∗ \\mathbf{z}^* z∗是目标空间中的最差参考点。该指标同时衡量近似集的收敛性与多样性 。

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

• 世代距离（GD）：
  衡量近似集$A$到帕累托前沿（PF）的收敛质量。公式为：
  G D = 1 ∣ A ∣ ( ∑ i = 1 ∣ A ∣ d i s ( a i , P F ′ ) p ) 1 p GD = \\frac{1}{|A|} \\left( \\sum_{i=1}^{|A|} dis(\\mathbf{a}_i, PF\')^p \\right)^{\\frac{1}{p}} GD=∣A∣1​ ​i=1∑∣A∣​dis(ai​,PF′)p ​p1​
  （ P F ′PF\' PF′是 PF 的子集， d i s ( a i , P F ′ ) dis(\\mathbf{a}_i, PF\') dis(ai​,PF′)是 a i\\mathbf{a}_i ai​到 P F ′PF\' PF′的距离 ）

• 反转世代距离（IGD）：
  同时衡量近似集的收敛性与多样性。公式为：
  I G D = 1 ∣ P F ′ ∣ ( ∑ i = 1 ∣ P F ′ ∣ d i s ( p i , A ) p ) 1 p IGD = \\frac{1}{|PF\'|} \\left( \\sum_{i=1}^{|PF\'|} dis(\\mathbf{p}_i, A)^p \\right)^{\\frac{1}{p}} IGD=∣PF′∣1​ ​i=1∑∣PF′∣​dis(pi​,A)p ​p1​
  （ d i s ( p i , A ) dis(\\mathbf{p}_i, A) dis(pi​,A)是 p i\\mathbf{p}_i pi​到近似集$A$的距离 ）

  类似的距离基指标，如 additive approximation metric、 Δ p\\Delta_p Δp​指标等，也被用于性能度量 。

3. 广义扩展指标（IGS）

用于衡量近似集的多样性，定义如下：
I G S = ∑ i = 1 s d ( e i , A ) + ∑ p ∈ P F ′ ∣ d ( p , A ) − d ˉ ∣ ∑ i = 1 s d ( e i , A ) + ∣ P F ′ ∣ d ˉ IGS = \\frac{\\sum_{i=1}^{s} d(\\mathbf{e}_i, A) + \\sum_{\\mathbf{p} \\in PF\'} |d(\\mathbf{p}, A) - \\bar{d}|}{\\sum_{i=1}^{s} d(\\mathbf{e}_i, A) + |PF\'| \\bar{d}} IGS=∑i=1s​d(ei​,A)+∣PF′∣dˉ∑i=1s​d(ei​,A)+∑p∈PF′​∣d(p,A)−dˉ∣​
其中：

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

4. R2 指标

基于效用函数的指标类别。给定参考集$R$，定义为：
R 2 ( 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$，并选乌托邦点 z ∗ \\mathbf{z}^* z∗加入$R$，则 R2 指标可定义为：
R 2 ( z ∗ , A , V ) = 1 ∣ V ∣ ∑ λ ∈ V min ⁡ a ∈ A { max ⁡ j ∈ { 1 , … , m } { λ j ∣ z j ∗ − a j ∣ } } 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 ）。