简介超体积指标是多目标优化中衡量解集质量的全局性指标常被用于多目标进化算法的性能评估。这套 MATLAB 工具包面向需要计算超体积、排序非支配解集的算法研究者与学习者围绕帕累托前沿评估中的参考点设定、体积计算和排序效率等关键问题提供可运行代码。压缩包共包含 3 个文件全部为 .m 脚本整体大小仅 6KB涵盖模式计算、排序算法和超体积核心实现三个模块结构清晰便于阅读和二次开发。目前已有 956 人学习下载。通过学习代码读者能深入理解超体积原理掌握非支配解集排序与体积计算的具体实现还可将其集成到多目标进化算法中作为适应度函数指导种群进化以获得更优的帕累托前沿适合科研入门和实践应用。1. hypervolume 究竟是什么多目标优化里最被低估的一个数字在多目标优化里算法跑完一轮摆在你面前的是几十上百个非支配解老板问“哪个算法效果更好”你盯着散点图说不上来。hypervolume 正是解决这个问题的指标它用参考点和解集围出的超体积大小把收敛性和分布性压进一个数。值越大说明解集离真实前沿越近、覆盖面越广这是它成为 NSGA-III、MOEA/D 等算法内部比较基准的原因也是你做实验时最该先算的一项。这篇笔记适合刚接触多目标优化的新手也适合一直用 IGD 但想换一个更稳健指标的熟手。2. 从支配关系到超立方体为什么 hypervolume 值得算2.1 几何直觉一个以参考点为锚的多面体以最小化双目标问题为例每个解是坐标平面上的一个点两个目标值越小越好。hypervolume 的定义看起来很抽象几何上却很简单给定一组解集 S 和一个参考点 rS 里每个解 p 与参考点 r 围成一个以 p 为顶点、r 为对角点的超矩形hypervolume 就是这些超矩形并集的体积。更直白地说你在目标空间里把解集所在的那块区域从参考点方向“填满”填出来的体积就是 HV。解越收敛到左下角最小值问题这个多面体往左下方的延伸越好解分布得越开多面体横向和纵向的跨度越大。这两点正好对应多目标优化的两个核心诉求收敛性和多样性。# 二维示意参考点取 (5,5)两个解 p1(1,2), p2(3,1) # p1 围出的矩形是 (1,2) 到 (5,5)p2 围出的矩形是 (3,1) 到 (5,5) # 并集面积 这两个矩形重叠后的总面积这个例子看着简单但请注意“并集”两个字。如果直接算两个矩形面积相加重叠区域会被重复计算这正是后面精确实现最需要注意的细节。2.2 数学定义与那个“不想要就删”的参考点正式定义是用 Lebesgue 测度写的HV(S, r) λ({q | ∃s∈S, s ⪯ q ⪯ r})。翻译成人话所有被 S 中至少一个解支配、同时本身又支配参考点 q 的点组成的区域体积。这里要求解的目标值都优于参考点 r也就是 r 必须被 S 里每个解支配或者说 r 要在各个目标维度上都是极差的值。对最小化问题参考点 r 通常取各目标上界向量加上一个小偏移。选得太小某些解与 r 之间没有超矩形空间HV 计算出来偏小甚至为 0选得太大会导致 HV 数值巨大解集之间的差距被稀释。这不是玄学而是决定实验结果可比性的关键参数具体取值方法放到第 4 章说。这里补一张常用指标对比方便理解 hypervolume 的特长指标需要真实前沿同时反映收敛与分布适用维度主要短板hypervolume不需要是2-5 维常用精确计算代价高IGD需要是任意依赖参考前沿质量GD需要只剩收敛性任意不反映分布Spread需要只剩分布性任意对前沿形状敏感2.3 为什么说它是“无需真实前沿”的黑匣子指标你对比两个算法的效果用 GD、IGD 都需要先知道真实 Pareto 前沿而多数工程问题的真实前沿是未知的。hypervolume 不需要外部参考前沿只需要一个你自己定的参考点这个参考点本质上是对“目标范围”的合理估计。因此 HV 可用来比较任何两批解集哪怕它们来自不同的算法、不同的初始化解、甚至不同的目标函数归一化方式。也正因为这样HV 常被用来做算法早停判据每迭代一轮算一次 HVHV 增长曲线变平缓说明解集已经收敛到稳定区域再跑只是微调。这个用法是第 6 章的重点。3. 最小可运行实现用 Python 写出第一个 hypervolume 计算3.1 环境准备与数据约定实现 hypervolume 前先把数据格式定清楚。我常用的约定是一个 2D NumPy 数组每一行是一个解每一列是一个目标值所有目标统一为最小化方向。如果你的问题是最大化先做取反或取倒数变换。import numpy as np # 模拟一批双目标解目标均为最小化 S np.array([ [1.0, 3.0], [2.0, 2.0], [3.0, 1.0], [1.5, 2.5], ]) ref np.array([4.0, 4.0]) # 参考点每个目标都劣于所有解这段代码里 S 的每一行是一个解ref 是参考点。先确认一件事S 里每个解的所有目标值都必须严格小于 ref否则该解不参与 HV 贡献甚至会发生方向性错误。我一般会在计算前加一个检查语句过滤掉不满足条件的解。3.2 二维精确计算扫描线法二维场景下 hypervolume 有很简洁的精确算法把所有解按 x 轴第一个目标降序排序然后从左往右扫维护 y 轴贡献的最大值累加每个解带来的增量面积。这也是理解 HV 几何构造最直观的方式。def hypervolume_2d(points, ref): 精确计算二维超体积。points、ref 均为 [x, y] 结构最小化方向。 points np.array(points, dtypefloat) points points[np.all(points ref, axis1)] # 只保留被参考点包围的解 if len(points) 0: return 0.0 # 按 x 降序排列相同 x 时 y 降序确保扫描顺序正确 order np.lexsort((points[:, 1], points[:, 0]))[::-1] points points[order] hv 0.0 max_y 0.0 for x, y in points: # 当前解相对参考点的矩形高度要扣除已被覆盖过的部分 if y max_y: hv (ref[0] - x) * (y - max_y) max_y y return hv hv hypervolume_2d(S, ref) print(HV , hv) # HV 7.75核心逻辑在循环里x 降序扫描时已处理过的解在 x 维度上更靠左它们与参考点围出的矩形会覆盖当前解的一部分 y 区间。max_y 记录的是“已完成扫描的解在 y 方向上覆盖到的最大上界”。只有当当前解的 y 值高于 max_y才会产生新区块新区块面积是宽度 (ref[0] - x) 乘以新增高度 (y - max_y)。这个扣除操作避免重复计算也就是前面说的并集关键点。参数说明lexsort 的第一个键是 y、第二个是 x配合 [::-1] 实现“先按 x 降序、再按 y 降序”如果不做这个排序扫描顺序错误会让结果偏大或偏小。ref[0] - x 是当前解到参考点横向距离y - max_y 是未被覆盖的纵向新增高度。这个算法的时间复杂度是 O(n log n)主要花在排序上n 是解的数量适合解集规模在几千以内的场景。3.3 三维及以上蒙特卡洛近似与它的适用边界三维以上精确计算超体积要复杂得多。精确算法用递归切面法每层递归分解超矩形复杂度随维度指数增长工程里超过 5 个目标基本跑不动。常见做法是蒙特卡洛采样近似在参考点约束的区域内随机撒点统计落在解集支配区域内的点占比乘以总体积就是 HV 的近似值。def hypervolume_mc(points, ref, n_samples100_000, seed42): 蒙特卡洛近似超体积适用于 3 维以上。 rng np.random.default_rng(seed) points np.asarray(points, dtypefloat) n_dim len(ref) samples rng.uniform(ref * 0, ref, size(n_samples, n_dim)) # 每个样本检查是否被至少一个解支配 dominated np.zeros(n_samples, dtypebool) for p in points: # 解 p 支配样本 s 的条件p 在每一维都小于等于 s且至少一维严格小于 less_equal np.all(samples p, axis1) strict_less np.any(samples p, axis1) dominated | (less_equal strict_less) volume np.prod(ref) return volume * dominated.mean()这段代码先按参考点构成的空间均匀采样默认假设原点0,...,0是理想边界适用于目标值已经归一化到从 0 到参考点的区间。然后逐一判断样本是否被某个解支配最后统计被支配样本占比。n_samples 参数直接决定精度建议从 10 万起步结果波动大就加到 100 万但注意每次给 seed 固定值否则同批解集两次计算结果不可复现。蒙特卡洛的明显短板是精度受目标维度影响大维度越高被支配区域占总体积的比例可能越小需要更多采样点才能达到同样的相对误差。在 3-4 维把它当趋势参考没问题但别拿它和一维二维的精确结果做严格数值对比。3.4 现有工具怎么选先算完再决定要不要自己造轮子实现方式很多常见做法是先用成熟库验证自己的理解再在性能瓶颈时改造。pymoo 里有pymoo.indicators.hv.Hypervolumedeap 也有 HV 工具platypus 内置了指标计算。不过这些库在新版本里 API 变过好几次如果你只是算个指标建议直接读它们的源码实现思路。我一般只在二维时用自己写的扫描线三维以上直接用 pymoo 或者自己写蒙特卡洛视精度需求而定。4. 参考点设定与数据归一化决定 HV 数值可信度的三个参数4.1 参考点取值的三种常用策略参考点不是随便给的它左右 HV 的绝对数值和可比较性。常见策略有三种按场景选用策略取值方式适用场景注意点固定边界目标函数已知上下界时取各维上界小偏移仿真问题、约束明确偏移过小会丢解信息数据驱动该批解集每维最大值基础上加 10%-20%算法对比实验不同解集间要统一前沿反推用已知参考前沿计算极值再加偏移有部分先验知识偏移量要大于数值噪声固定边界最省事但工程问题里目标边界往往不精确比如调度问题的完工时间上限是拍脑袋定的。实验对比时我倾向于数据驱动但关键约束是“所有参比解集必须使用完全相同的参考点”否则 HV 数值不可比。代码层面直接在调用前统一处理# 多个算法结果统一参考点 all_poynts np.vstack([res1, res2, res3]) ref all_poynts.max(axis0) * 1.2这里 1.2 是常用的经验偏移量参考点因此严格劣于所有解。如果原始目标值跨数量级比如第一个目标在 0-1第二个目标在 100-1000先做归一化再算 HV否则第二个目标几乎主导整个体积数值第一个目标的贡献完全被吞掉。4.2 归一化细节什么时候做怎么做做算法对比实验时同一个问题跑不同算法解集的目标值范围差异可能很大。如果不归一化边界目标占主导hypervolume 的比较结果基本失真。我一般把每个目标归一到 [0,1]取所有参比解集在每一维的全局最小值和最大值作为缩放依据而不是用单个算法自己的极值。之所以强调“全局”是因为单个算法的极值会奖励分布窄的算法它自己归一化自己把本不拥挤的区域拉伸到满格HV 虚高。这是踩坑重灾区代码上只需要注意统一缩放参数min_vals np.min(np.vstack([res1, res2, res3]), axis0) max_vals np.max(np.vstack([res1, res2, res3]), axis0) norm1 (res1 - min_vals) / (max_vals - min_vals 1e-12)分母里加 1e-12 是为了防止某一维所有解值相同造成除零。归一化后目标区间是 [0,1]参考点取 1.1 或 1.0 均可但要统一。注意如果只是单次运行展示结果、不跨算法对比归一化就不是必需的对 HV 的单调排序没有影响。4.3 最小化最大化问题方向变换的常见误区hypervolume 的定义基于最小化结构解越靠近坐标原点越好。如果你的问题是最大化目标比如收益、召回率直接拿原始值算 HV 会得到完全错误的体积。常见做法是取负号把最大化转成最小化但取负后目标区间变成负数区域参考点不好确定。更稳的方法是取倒数或取 1 - 归一化值让目标范围重新回到正数区间。我习惯的做法先做数据驱动归一化把每个目标映射到 [0,1]最大化的目标用 1 - x 转换最小化的目标保持 x然后统一参考点为 [1.2]*n。这样做的好处是目标方向一致HV 计算逻辑不用在函数里区分最大最小。很多现成库默认最小化不处理方向就会一头扎进负数区域。5. 常见问题与避坑算出来的 HV 不对多半是这五个地方5.1 现象一HV 计算结果是负数这个现象一般会把人吓一跳。原因很直接解集里有解不满足“被参考点支配”的约束比如某个目标值大于参考点导致算法内部的支配方向翻转计算出来的数值失去意义。即使我的扫描线函数里有过滤逻辑用第三方库时默认不检查出了问题要自己排查。解决方式计算前显式断言np.all(points ref)。如果不满足优先检查参考点设置是否偏移太小再检查是否忘了做最大化到最小化的方向转换。这也是我自己最常犯的在新问题的目标范围没摸清时随手设个参考点一跑就翻车。5.2 现象二两个算法 HV 一样但散点图看起来差很多参考点取得过大时解集之间的差异被稀释到小数点后很多位打印出来都是同一个值。原因很简单体积的绝对大小被参考点主导而解集的差异只体现在一块很小的区域。解决方式是压缩参考点让它贴近解集边界。比如数据驱动策略下把 1.2 的偏移系数改成 1.05或者先画散点图看解集范围再定参考点。5.3 现象三同一批解两次计算 HV 不同这里有两个可能来源。第一种是蒙特卡洛近似没设固定随机种子每次采样结果自然不同。第二种是解集排序不稳定尤其是包含重复解时排序结果依赖初始顺序扫描线算法对顺序敏感。解决方式采样加 seed排序前先对重复解去重或加稳定排序参数。去重时注意只去完全相同的目标向量不是去支配重复两回事。5.4 现象四解集包含被支配点导致 HV 偏大很多人把整个存档都丢进 HV 计算但存档里可能残留被其他解支配的解。这些点的超矩形会被真实非支配解的矩形覆盖理论上不影响并集面积。但在二维扫描线实现里如果被支配点先进入循环并抬高了 max_y后面真实前沿解的新增面积会被错误扣除结果不但没偏大反而偏小。原因在于“被支配点对并集无贡献”这句话成立的前提是它排在正确位置而排序时它可能干扰覆盖状态。解决方式计算 HV 前现做一轮非支配排序过滤掉被支配点这是最稳的做法。5.5 现象五3 维以上 HV 和论文对不上如果你复现论文HV 数值对不上先别怀疑自己算法错。论文的参考点原始向量没写明归一化区间是常见事目标归一化方式不同HV 数值就会差出几十倍。另外有些论文用精确算法有些用蒙特卡洛采样数不足导致误差。解决方式仔细看论文的参考点定义尽量让目标和参考点使用同一套归一化再比较相对趋势而不是绝对数值。6. 进阶用法用 HV 增量做收敛判定顺便验证求解器6.1 从 HV 到 HV 增量每个新解贡献的大小HV 增量ΔHV指把一个新解 p 加入现有解集 S 后HV 的增加量。由于 HV 衡量的是并集面积这个增量天然等于“p 独立覆盖出、且未被 S 覆盖”的区域面积。用二维扫描线实现增量计算很容易去掉当前解的 y 值与 max_y 比较时取 0得到的就是净新增贡献。三维以上近似计算则复杂一些但工程里常用蒙特卡洛差值的简化估算。增量计算的最大用途是算法早停判断每轮迭代结束后把新产生的非支配解逐个并入存档如果连续 N 轮 HV 增量都低于某个阈值说明再跑下去收益微薄可以停了。这比看种群代数更精准因为种群代数只能告诉你“跑了多少”不能告诉你“还有多少进步空间”。6.2 一个简单的收敛判定循环把增量判定做成一个通用循环可以在任何基于种群的多目标算法上复用THRESHOLD 0.001 # 增量阈值按问题规模调整 STALE_ROUNDS 5 # 连续几轮低于阈值就停 prev_hv 0.0 stale_count 0 for generation in range(max_gen): # 假设 solve_one_generation() 返回本轮的非支配解集 archive get_archive_after_evolution(generation) hv_now hypervolume_2d(archive, ref) delta hv_now - prev_hv prev_hv hv_now if delta THRESHOLD: stale_count 1 if stale_count STALE_ROUNDS: print(f早停在第 {generation} 代当前 HV {hv_now:.4f}) break else: stale_count 0这段逻辑的核心是“相对停滞”而不是“绝对停滞”因为 HV 增量会随代际递减前期大概率快速上升后期逐渐平滑。阈值设置按 HV 绝对量级调整建议先跑一次完整过程观察增量衰减曲线再取曲线变平处数值的 1/10 作阈值。另外早停依据 HV 增量需要保证每轮归档的解集具有可比性比如都使用同一参考点、同一归一化参数否则前后轮的 HV 值根本不在同一坐标系里。6.3 验证 HV 计算器本身的正确性把自己的 HV 计算器投入实验前先做一次交叉验证。常见做法是用已知真实前沿的问题比如 zdt1、dtlz1求出理论 HV 值或直接用成熟库的计算结果做基准。取同一批解同一参考点对比我的扫描线实现和第三方库输出差值小于 1e-6 才算通过。蒙特卡洛近似则用固定种子跑三次看标准差在可接受范围内。我自己的习惯是在新问题里先用二维小规模解集做人工验算三个点手动画图算矩形面积并集再和代码输出比对。这一步虽然原始却能最快抓出排序方向、参考点偏移这类基础错误。之后再做跨库交叉验证。经验是验证步骤不要省hypervolume 的实现写错时结果差一点会让你误判算法优劣这种“看着不对又说不上哪里不对”的状态在实验里最花时间。最后提醒一个我自己常犯的教训hypervolume 的一切比较都建立在“测量条件一致”的前提上。参考点、归一化、去不去被支配点、精确还是近似任何一项不一致都会毁掉可比性。早停判定里尤其要固定测量条件否则拿到的收敛曲线只是假象。希望帮到你。本文还有配套的精品资源点击获取