尧图网站建设 
做NSGA-III相关笔记的时候我一直有一个很强烈的感受网上讲NSGA-III的资料并不少但大部分都停留在“它比NSGA-II多了参考点”这种层面。真正到自己写代码、调参、跑实验的时候才发现一堆细节没被讲透。这篇笔记就把我从原理到实现再到踩坑的完整过程整理出来适合已经对多目标优化有一定基础、想真正落地使用NSGA-III的读者。目标只有一个让你看完之后能自己写出一个能稳定运行的NSGA-III而不是对着论文发愣。1. 从8目标优化翻车说起NSGA-II在高维目标下的崩溃1.1 为什么NSGA-II适合2-3个目标却处理不了10个目标我第一次用NSGA-II跑多目标问题的时候目标函数只有两个效果相当理想收敛快、解集均匀当时就觉得多目标优化不过如此。直到后来接手一个实际问题目标函数一口气给到8个NSGA-II的表现立刻让我清醒了——种群压根压不到Pareto前沿附近解集在后代迭代中还会整体漂移均匀性更是一塌糊涂。问题出在NSGA-II的保持多样性机制上。NSGA-II在环境选择时对同一非支配层里的个体用拥挤距离来排序优先保留拥挤距离大的个体。这个策略在2-3维目标空间里很好用因为它直观反映了“这个点附近是不是太空旷”可以补点进去。但维度一旦超过3个尤其是到5个、8个、10个目标时拥挤距离就开始失真了。为什么因为高维空间中每个个体附近的邻居数量会急剧减少距离差异也变得非常悬殊拥挤距离不再能精确反映解集在目标空间中的分布均匀性。换句话说它还能大概表示“稀疏”但已经没法保证“均匀”了。另一个核心问题是随着目标数增多非支配层里的个体占比会迅速上升。超立方体里随机采样能互相支配的点越来越少几乎所有点都落在同一个非支配层里。这时候NSGA-II最重要的排序筛选机制就失去了区分度后续选择几乎完全依赖拥挤距离而拥挤距离在高维又不可靠整个算法就在维护多样性的环节上崩掉了。很多论文会把这个现象称为“Pareto支配关系在高维空间中的失效”。你会看到随着目标数M增大一个解支配另一个解的概率按某种指数趋势下降这就导致非支配层变得异常庞大选择压力大幅降低。NSGA-III的出发点很简单——既然支配关系区分不了那么多解那就要在“同为非支配”的解之间找到一个比拥挤距离更稳定、更能体现分布偏好的标准来分高下。1.2 分解思路的卷入MOEA/D带来的启发在NSGA-III之前基于分解的多目标进化算法MOEA/D已经给我留下了非常深的印象。它不把多目标问题当整体去维护Pareto前沿而是先把多目标问题分解成一组单目标子问题每个子问题用一组权重向量定义然后让种群里的个体各自去优化对应的子问题通过子问题之间的邻居关系来协同进化。这种思路的优点是权重向量在目标空间里是均匀分布的只要你最终能让每个个体都收敛到各自权重向量对应的前沿区域解集的分布均匀性就有天然保障。这比在高维空间里计算距离可靠得多。NSGA-III最聪明的地方就是把MOEA/D的“权重均匀分布”思想借了过来但用的不是权重向量加聚合函数的方式而是引入参考点。参考点可以理解成你在目标空间中预先画好的一组“标尺”种群在进化时努力往这些标尺方向分配个体。只要每个参考点方向上都有解收敛过去解集自然就覆盖整个Pareto前沿而且分布均匀。所以我一直觉得NSGA-III并不是对NSGA-II的小修小补它实际上是把“基于支配”和“基于分解”两个流派的核心思想做了融合。非支配排序保证收敛性参考点机制保证多样性这套组合拳让它在高维目标问题上有了质的飞跃。2. NSGA-III的三大核心智力参考点、归一化与生态位选择2.1 参考点生成Das-Dennis方法与小H问题NSGA-III里最显眼的改动就是参考点。参考点不是随机撒的而是按照某种均匀结构生成的原始论文推荐用Das-Dennis方法也叫单纯形网格设计。说得具体一点它把M维目标空间当成一个单纯形每个参考点的坐标分量都从 \( \{0/k, 1/k, ..., k/k \} \) 里取值并且所有分量之和为1。这样生成的参考点数量有个组合公式$$H \binom{M p - 1}{p}$$其中M是目标函数个数p是每个目标方向上的分割份数。举个例子目标数M3分割数p4那么参考点数H C(34-1, 4) C(6,4) 15。如果想在3目标问题上用大约100个参考点可以把p设为9H算出来正好是55或者p13H105。种群规模N通常就取和H接近的值。这里有一个非常实际的问题就是随着M增大参考点数会组合爆炸。M5p8时H C(12,8) 495还算能接受但M10p哪怕取3H C(12,3) 220也勉强。可目标一旦到15个以上想生成上千个参考点C(N,k)的组合增长会把过程和存储都逼得很难受。处理办法通常有几种。第一种是降低分割份数p让参考点数量减下来但这会牺牲分布精度。第二种是随机生成一部分参考点嗯有不少实现会在参考点数量不够的时候用随机均匀采样来凑数。第三种是更高级的做法叫双层参考点生成就是同时在单纯形内部和边界上生成两层参考点在保留边界点重要性的同时增加内部点的覆盖。这个我在后面会稍微展开。实际编码时Das-Dennis参考点的生成可以用递归的方式来实现也就是先固定第一个维度再在剩下的M-1维里递归生成组合。网上很多现成代码都这么写但你们要留意顺序一不小心就会生成重复或者丢失点。2.2 归一化的数学原理理想点、极端点与截距参考点生成了但目标函数数值的范围跟参考点坐标根本不在一个数量级上直接算距离是没有意义的。所以在关联参考点之前必须先做归一化把每个目标上的数值都压缩到差不多同一个尺度里。NSGA-III的归一化分三步走。第一步计算理想点也就是种群中每个目标上的最小值组成的向量记为 \( z^{min} \)。第二步对每个个体用理想点做平移得到 \( f_i(x) f_i(x) - z_i^{min} \)。第三步求每个目标方向上的极端点。极端点的求法值得注意。对第i个目标要找一个个体让它在“主要看第i个目标”的标量函数下取值最小。实际中常用的是Wierzbicki的增强标量函数achievement scalarizing function形式大致是$$ASF(x) \max_{j1..M} \left( \frac{f_j(x)}{w_j} \right) \rho \sum_{j1..M} \frac{f_j(x)}{w_j}$$当我们要找第i个目标的极端点时就令权重向量 \( w_i 1 \)其他权重 \( w_j 10^{-6} \) 这种极小值。这样谁能让ASF最小谁就可以充当第i个目标的极端点。拿到M个极端点之后用这M个点构造一个M-1维的超平面然后计算这个超平面在每个目标轴上的截距 \( a_i \)。最后用截距做归一化$$f_i^{norm}(x) \frac{f_i(x)}{a_i} \frac{f_i(x) - z_i^{min}}{a_i}$$这个归一化处理做完之后所有目标函数的范围基本都落在 \( [0,1] \) 附近参考点坐标也在这个范围里后续计算垂直距离才有意义。这里最需要警惕的是当极端点构造超平面失败或者截距出现负值、极大值的时候这个归一化就废了。原因通常是某些目标上的极端点太接近导致超平面退化。我在第4部分会专门讲这个问题。2.3 关联操作与生态位计数NSGA-III的“拥挤度替代者”归一化完成后需要把每一个个体关联到离它最近的参考点上。这里说的“距离”不是欧氏点到点的距离而是个体到参考点所在直线的垂直距离。参考点一般是从原点出发、经过单纯形上那个坐标点的射线方向所以这个距离可以衡量这个个体在“该参考方向”上有多少偏离。每个个体找到最近的参考点后我们就统计每个参考点关联了多少个体这个数量记作 \( \rho_j \)。这个 \( \rho_j \) 就是NSGA-III替代NSGA-II拥挤距离的核心指标它的含义很直接这个参考方向上已经有多少个解了。生态位选择就是围绕 \( \rho_j \) 展开的。在需要从最后一个非支配层里挑个体补满种群的时候先找出 \( \rho_j \) 最小的参考点优先往这些冷门方向补人。如果某个参考点 \( \rho_j 0 \)但当前前沿面里正好有和它关联的个体那就无条件选一个进来让这个方向上从无到有。如果 \( \rho_j 0 \) 且当前层没有个体关联到它这个参考点就直接被忽略。如果 \( \rho_j 0 \)那就在关联到这个参考点的个体里挑垂直距离最小的进来让这个方向上的解更贴近参考方向。这套机制比拥挤距离好在哪好在它有明确的“分布目标”。每个参考点可以看成目标空间里的一个表示点参考点均匀按参考点补出来的个体就均匀。而拥挤距离只是局部密度估计高维下根本没有“均匀”的全局概念。2.4 与NSGA-II选择算子的区别把两代算法的选择算子放在一起对比区别就很清晰了。NSGA-II是“非支配排序 拥挤距离”NSGA-III是“非支配排序 参考点关联 生态位计数”。前者是一种相对被动的保持多样性方式它不知道所谓的“均匀”应该按什么全局标准来组织只是尽量在稀疏地方放点。后者是一种带引导的选择方式参考点在目标空间里画好了网格选择过程就是往网格上分配个体。这个差异带来的效果差异是很实际的。以目标数M3、种群大小N100为例NSGA-II偶尔会在Pareto前沿的某个局部区域堆出一大团点另一块区域却空荡荡NSGA-III因为参考点均匀分布在整个单纯形上只要进化代数足够每个参考方向附近都会分配到个体分布基本不会出现大片空洞。3. 把整个算法流程走一遍从初始化到环境选择3.1 种群初始化与参考点准备NSGA-III的起点和标准遗传算法一样先随机初始化N个个体每个个体是一组决策变量编码。不同的是你同时要生成H个参考点并确定种群规模和参考点数量的关系。比较推荐的做法是先算参考点数H再决定种群规模N。如果N正好等于H那最省心。如果N小于H就随机从H个参考点里选N个作为激活参考点。如果N大于H理论上也可以只要最后环境选择能通过生态位计数补满就行但通常不建议让N比H大太多否则部分方向会冗余堆积。我自己的实践习惯是在优化问题目标数M不超过8的情况下优先让H等于N或者H是N的近似值。这可以省掉很多调参时的心智负担。3.2 遗传操作与合并种群主循环的每一代都用遗传操作从当前种群P_t里生成子代种群Q_t。遗传操作的选择算子、交叉算子、变异算子可以根据决策变量的类型自由选择。如果决策变量是连续的可以选SBX交叉和多项式变异如果决策变量是离散的可以选模拟二进制交叉的变体或者直接用均匀交叉加位翻转变异。子代生成完之后把父代和子代合并成一个规模为2N的种群 \( R_t P_t \cup Q_t \)。这个操作和NSGA-II完全一致本质上是为了保证精英保留让父代里的好基因不至于在替换中丢失。3.3 逐层筛选非支配排序的边界处理接下来对 \( R_t \) 做快速非支配排序把种群划分成若干互不支配的前沿层 \( F_1, F_2, ... F_l \)。注意这一步和NSGA-II前端排序一样没有区别。真正的分水岭是当 \( F_1 \cup ... \cup F_l \) 的总个体数第一次大于等于N的时候。假如前l层的总个体数刚好等于N那就直接把 \( F_1 \cup ... \cup F_l \) 作为下一代种群不用做参考点选择这最省事。但在大多数情况下前l层加起来会超过N而 \( F_1 \cup ... \cup F_{l-1} \) 加起来又不到N。这时候就要从 \( F_l \) 这一层里挑一部分个体补满N。3.4 关键一步在前沿层F_l上做基于参考点的选择这一步是NSGA-III里最核心也最容易写错的地方。我先给出完整的处理流程。第一已经从 \( F_1 \cup ... \cup F_{l-1} \) 中确定了保留下来的个体集合 \( S_t \)接下来要在 \( F_l \) 中选 \( K N - |S_t| \) 个个体进下一代。第二对整个 \( S_t \cup F_l \) 做归一化。极端的思路是只对 \( S_t \) 做归一化但那样会导致某些进入 \( F_l \) 的个体坐标被扭曲所以正确做法是把这两部分合并起来一起算理想点和极端点。第三把 \( S_t \cup F_l \) 里的每个个体都关联到最近的参考点统计每个参考点当前关联的个体数 \( \rho_j \)。第四构造一个当前待激活参考点集合 \( J_{min} \{ j \, | \, \operatorname{arg\,min}_j \rho_j \} \)。意思就是找到所有 \( \rho_j \) 最小的参考点如果多个并列就都拿进来。第五从 \( J_{min} \) 里随机挑一个参考点j。如果 \( \rho_j 0 \)说明这个方向还没有个体那就优先从 \( F_l \) 中找出所有关联到参考点j的个体选垂直距离最小的那个加入下一代后面再更新 \( \rho_j \)把这个参考点从待激活集合里去掉。如果 \( F_l \) 中不存在关联到参考点j的个体那就直接把这个参考点废弃再随机挑下一个 \( J_{min} \) 里的参考点。如果 \( \rho_j 0 \)说明这个方向已经有个体了那就在所有关联到参考点j的 \( F_l \) 个体中选垂直距离最小的补进去。这个过程循环K次最终把下一代种群填满。最后用一句话总结这个流程先按支配关系分层淘汰弱者再用参考点方向引导补位保证收敛性的同时维持均匀性。这也是整个算法最值得品味的设计。4. 实现与参数细节代码层面最容易翻车的地方4.1 参考点数量与种群规模的匹配关系编程实现NSGA-III时我遇到过最无语的问题就是参考点数和种群规模不匹配。有人直接把种群规模改成和参考点数一样这通常没毛病。但有时候为了对比公平实验要求N固定为100而参考点数算出来是120或者84这就需要在生成参考点之后做一次筛选或补全。如果参考点数比N大一般就随机抽样出N个参考点来用。如果参考点数比N小我建议不要硬用宁可把参考点分割参数调大一点也别出现N远大于H的局面。因为参考点是多样性的“锚”锚少了算法就退化成往少数方向上堆个体均匀性反而比NSGA-II还差。有个经验值可以分享在目标数M3、N100的时候H取91到105都行M5、N200的时候H取190到220都行。重点不是H要精确等于N而是H不要和N差出一个量级以上。4.2 极端点计算与截距的数值稳定性极端点计算是NSGA-III实现里最容易踩的深坑。我刚开始复现的时候用的是一种简化方式对第i个目标直接找种群中 \( f_i(x) \) 最小的个体作为极端点。这样算出来的M个极端点在多数情况下也能用但一旦目标之间存在比较强的冲突或者前沿形状不规则简化方式就会选到不合适的点导致超平面截距计算出问题。更稳妥的做法是用增强标量函数ASF来找极端点。你可能会问为什么ASF比单纯取最大值更好因为目标优化的个体往往不止一个单纯取某个目标的最大值可能落在前沿的边缘但不一定是边界支撑点。ASF通过极小的 \( \rho \) 扰动能让选择的点既贴近目标方向又不会因为退化问题陷入数值异常。截距计算失败还有一个典型场景当M个极端点构成的矩阵接近奇异时超平面不存在截距算不出来。为了处理这种情况实际代码里通常要加一个判断如果截距计算失败回退到 \( a_i \max_{x \in S_t \cup F_l} f_i(x) \)也就是把当前种群中第i个目标的最大值当截距。这种做法虽然粗略但至少能让归一化过程稳定跑下去。4.3 归一化失败时的对策归一化不是每次都顺风顺水。即使截距算出来了也可能遇到 \( a_i \leq 0 \) 的情况。这种情况通常发生在Pareto前沿的形状已经退化或者某一维目标函数在种群中的差异非常小导致截距为负。遇到 \( a_i \leq 0 \) 时不要直接崩溃退出。一般的策略是先把目标自适应地映射到一个固定区间比如 \( [0,1] \)然后忽略超平面截距的修正直接把 \( f_i^{norm} (f_i - \min) / (\max - \min) \)。这是很多开源库实际采用的回退策略虽然理论纯度没那么高但工程上非常稳定。从论文实现的角度看原始NSGA-III论文里对这个问题的处理其实也比较粗主要就是“遇到失败换一种归一化方法”。所以你写代码时没必要追求把归一化一步做到完美预留一个回退分支就够了。4.4 参考点关联的高效实现参考点关联这一步看起来简单就是算个体到每条参考线的垂直距离然后取最小值。但实际跑起来如果N500、H500、目标数M10每一代关联计算要跑25万次点到直线的距离每次距离计算又涉及M维向量运算累计开销其实不小。我碰到过跑一次500代实验光关联操作就占了总运行时间40%以上的情况。优化思路有两个方向。第一把参考点坐标预先算好存成矩阵不要每代重复生成。第二用向量化方式批量计算而不是用Python写两层for循环逐个体遍历。用NumPy或PyTorch这类支持广播的库一遍矩阵运算就能把整个种群的关联距离全算出来速度可以提升几十倍。还有个细节NSGA-III原始论文里关联的是“参考线”也就是从原点出发穿过参考点的射线。但有些实现简化成了“参考点”本身直接算欧氏距离。这两种实现会在参考点处于边界时产生差异。我个人建议用射线方式也就是垂直距离/投影方式这样更贴近论文并且处理高维边界时更稳定。5. NSGA-III与其他算法的横向对比与选型思路5.1 与NSGA-II、MOEA/D、SPEA2的对比表很多读者最想知道的是NSGA-III是不是全面碾压NSGA-II答案是否定的。它们各自有不同的适用区间。维度NSGA-IINSGA-IIIMOEA/DSPEA2核心多样性机制拥挤距离参考点生态位计数权重向量聚合最近邻密度估计目标数适用区间2-3个勉强4个3-15个高维2-10个依赖聚合函数2-3个解集均匀性中低维良好高维优秀有参考点保证依赖权重向量中低维良好计算复杂度低参考点关联带来额外开销低中等对归一化敏感度低高依赖于聚合函数形式低约束处理通用约束支配通用约束支配需额外处理通用约束支配从这个表能看出一个趋势NSGA-II和SPEA2适合经典的低维多目标问题两三个目标的情况下它们不仅简单而且效果很好。MOEA/D的权重向量可以自适应匹配Pareto前沿形状但如果前沿是非凸不连续的聚合函数的选择会变得很讲究。NSGA-III则天然为高维目标场景设计参考点让它在3个目标以上依然能给出均匀分布的解集。5.2 它不适合哪些场景适合哪些场景NSGA-III虽然在高维目标问题上很能打但并不是万能的。它有比较明显的适用边界。第一如果目标空间本身是极端非线性的参考点固定均匀分布可能和真实Pareto前沿形状严重不匹配。比如Pareto前沿是断开的、多片状的固定的参考点就会导致大量参考方向落在空白区域浪费种群个体。这种情况可以考虑自适应参考点版本比方说在进化过程中根据当前前沿形状动态调整参考点。第二如果目标个数非常多比如超过15个纯静态参考点的NSGA-III也会退化。因为参考点数量组合爆炸H若太小多样性锚点不足H若太大种群规模跟不上每个参考方向只有很少个体选择压力不够。此时更适合用一些近年来提出的新型算法比如基于目标降维或基于方向向量的方法。第三如果问题收敛本身很困难决策变量很多NSGA-III也不会比NSGA-II有质的提升。因为它的改进主要集中在“高维目标下的多样性保持”不是为收敛性发明的。收敛性还是要靠遗传算子、邻域搜索或者局部搜索来保证。适合的场景很清楚目标数3到10个之间、Pareto前沿相对完整连续、需要解集在目标空间里分布均匀的多目标优化问题。这些问题用NSGA-III跑基本都能得到一个让人满意的结果。5.3 一些值得尝试的后续改进方向实际用NSGA-III的过程中我研究过几个比较有效的变体在这里记录一下思路。自适应参考点方向是改进的第一大方向。固定的Das-Dennis参考点与问题特性无关但对不同问题的Pareto前沿理想的解分布可能完全不同。可以每隔若干代重新根据当前种群的极端点和均值来生成参考点让参考方向随着前沿形状调整。第二种改进方向是和其他局部搜索算子结合形成memetic算法。NSGA-III负责全局搜索局部搜索负责精细收敛两个阶段交替进行。这个方向在工程优化里非常实用。第三种是和约束处理结合。如果问题有大量约束可以直接用约束支配原则替换原论文里的支配关系即一个可行解总是支配不可行解两个不可行解中约束违反程度更小的占优。这样不需要额外修改NSGA-III的主体结构就能处理带约束的高维多目标问题。6. 我踩过的坑与调试心得6.1 连续问题不要无脑用二进制编码刚开始做实验时我以为NSGA-III和NSGA-II一样可以用二进制编码加简单交叉。结果在连续优化问题上二进制编码把精度限制死了Pareto前沿上很多细节区域根本搜不到。后来改成实数编码配SBX交叉和多项式变异收敛质量立刻上了一个台阶。SBX的分布指数 \( \eta_c \) 和变异分布指数 \( \eta_m \) 设置也值得注意。经验上 \( \eta_c \) 取15到20\( \eta_m \) 取15到20效果比较均衡。如果想让解集分布更广泛可以适当调大 \( \eta_c \)让子代更接近父代如果想让搜索范围更大可以适当调低。6.2 参考点关联速度慢的时候先别优化算法先看是不是循环没用向量化我一开始自己写的Python版NSGA-III跑8目标、N300的问题一代要跑三四秒500代下来得二十多分钟。后来发现瓶颈全在两层for循环的关联距离计算上。改成NumPy批量计算之后一代时间降到0.2秒左右提速了十几倍。所以我的建议是先把实现跑通再性能剖析。如果你发现每次迭代特别慢先定位是排序慢还是关联慢。排序用现成的高效实现关联距离优先向量化。千万不要一上来就上并行计算很多时候串行向量化就已经够用了。6.3 实验对比时要固定随机种子并关注IGD和HV两个指标做算法对比时最忌讳的是只跑一次就下结论。NSGA-III是随机算法不同随机种子的结果差异可以很大。我一般同一个参数配置跑11次或21次独立重复实验取中位数和四分位距然后看两个指标IGDInverted Generational Distance和HVHypervolume。IGD衡量的是算法求得的解集到真实Pareto前沿的平均距离需要你知道真实前沿常用于测试函数。HV衡量的是解集在目标空间里覆盖的超体积不需要真实前沿适合实际工程问题。这两个指标一起看一个管收敛性一个管多样性。有意思的是NSGA-III在HV指标上通常会比NSGA-II好但有时候在IGD上优势不明显。原因在于参考点机制保证的是均匀分布而IGD对分布均匀的要求和参考点并不完全等价。所以如果你在论文里要对比算法最好两个指标都报别只挑好看的说。6.4 先把可视化做出来再调参多目标优化有个很实际的调参技巧先把3目标问题的三维散点图做出来肉眼观察解集形状再决定怎么调参数。NSGA-III跑出来的结果三维图里应该能明显看到解集分布在一个均匀的三角形或者曲面上。如果某些区域明显稀疏优先检查参考点数量和分割数如果整体偏到一边优先检查归一化是否正常极端点计算是否出了错。我记得有一次跑3目标函数出来的解集全部挤在一个角落里三维图里只有一小团点。排查了半天最后发现是极端点计算用了简化版导致截距偏了归一化把整个目标空间压歪了。换成ASF方法之后问题迎刃而解。6.5 在处理约束时加约束违反度惩罚要小心有些代码实现会在目标函数上加惩罚项把约束问题转成无约束问题来跑。在NSGA-III上这么干要非常小心因为惩罚系数如果设置不合适会严重破坏目标函数的值域进而影响归一化和参考点关联的稳定性。更好的方案是用约束支配原则把约束信息放到支配判断里而不是融合进目标函数。这样归一化过程只用处理真正原始目标函数的值域不容易出幺蛾子。6.6 目标函数数量变化时要重新调整参考点数如果你的实验不是固定目标数而是要对比3目标、5目标、8目标的结果那你必须为每个目标数重新生成参考点。曾经有朋友偷懒用一套参考点跑了所有目标数结果5目标时解集分布乱成一锅粥。这个教训很简单——参考点数量和分割数必须跟目标数匹配不然算法的多样性引导就是无效的。写在最后的一点个人体会把NSGA-III从论文变成可用的代码再变成能稳定产出好结果的工具中间确实有不少弯路。最大的感受是NSGA-III的优秀并不全在参考点这一个机制上而是“非支配排序 归一化 参考点生态位选择”这三者配合得当。任何一个环节出错整个算法都会偏离理想行为。如果你想把它用到自己的问题上我给一个最实际的建议先不要急着改造算法或者加各种自适应机制把标准版NSGA-III跑透用测试函数验证实现正确性再把真实问题的目标函数封装进来。很多时候标准版已经够了真正不够的是你对问题本身的理解和对实验设计的把控。 NSGA-III完整指南：从原理到Python实现，高维多目标优化算法详解
做NSGA-III相关笔记的时候我一直有一个很强烈的感受网上讲NSGA-III的资料并不少但大部分都停留在“它比NSGA-II多了参考点”这种层面。真正到自己写代码、调参、跑实验的时候才发现一堆细节没被讲透。这篇笔记就把我从原理到实现再到踩坑的完整过程整理出来适合已经对多目标优化有一定基础、想真正落地使用NSGA-III的读者。目标只有一个让你看完之后能自己写出一个能稳定运行的NSGA-III而不是对着论文发愣。1. 从8目标优化翻车说起NSGA-II在高维目标下的崩溃1.1 为什么NSGA-II适合2-3个目标却处理不了10个目标我第一次用NSGA-II跑多目标问题的时候目标函数只有两个效果相当理想收敛快、解集均匀当时就觉得多目标优化不过如此。直到后来接手一个实际问题目标函数一口气给到8个NSGA-II的表现立刻让我清醒了——种群压根压不到Pareto前沿附近解集在后代迭代中还会整体漂移均匀性更是一塌糊涂。问题出在NSGA-II的保持多样性机制上。NSGA-II在环境选择时对同一非支配层里的个体用拥挤距离来排序优先保留拥挤距离大的个体。这个策略在2-3维目标空间里很好用因为它直观反映了“这个点附近是不是太空旷”可以补点进去。但维度一旦超过3个尤其是到5个、8个、10个目标时拥挤距离就开始失真了。为什么因为高维空间中每个个体附近的邻居数量会急剧减少距离差异也变得非常悬殊拥挤距离不再能精确反映解集在目标空间中的分布均匀性。换句话说它还能大概表示“稀疏”但已经没法保证“均匀”了。另一个核心问题是随着目标数增多非支配层里的个体占比会迅速上升。超立方体里随机采样能互相支配的点越来越少几乎所有点都落在同一个非支配层里。这时候NSGA-II最重要的排序筛选机制就失去了区分度后续选择几乎完全依赖拥挤距离而拥挤距离在高维又不可靠整个算法就在维护多样性的环节上崩掉了。很多论文会把这个现象称为“Pareto支配关系在高维空间中的失效”。你会看到随着目标数M增大一个解支配另一个解的概率按某种指数趋势下降这就导致非支配层变得异常庞大选择压力大幅降低。NSGA-III的出发点很简单——既然支配关系区分不了那么多解那就要在“同为非支配”的解之间找到一个比拥挤距离更稳定、更能体现分布偏好的标准来分高下。1.2 分解思路的卷入MOEA/D带来的启发在NSGA-III之前基于分解的多目标进化算法MOEA/D已经给我留下了非常深的印象。它不把多目标问题当整体去维护Pareto前沿而是先把多目标问题分解成一组单目标子问题每个子问题用一组权重向量定义然后让种群里的个体各自去优化对应的子问题通过子问题之间的邻居关系来协同进化。这种思路的优点是权重向量在目标空间里是均匀分布的只要你最终能让每个个体都收敛到各自权重向量对应的前沿区域解集的分布均匀性就有天然保障。这比在高维空间里计算距离可靠得多。NSGA-III最聪明的地方就是把MOEA/D的“权重均匀分布”思想借了过来但用的不是权重向量加聚合函数的方式而是引入参考点。参考点可以理解成你在目标空间中预先画好的一组“标尺”种群在进化时努力往这些标尺方向分配个体。只要每个参考点方向上都有解收敛过去解集自然就覆盖整个Pareto前沿而且分布均匀。所以我一直觉得NSGA-III并不是对NSGA-II的小修小补它实际上是把“基于支配”和“基于分解”两个流派的核心思想做了融合。非支配排序保证收敛性参考点机制保证多样性这套组合拳让它在高维目标问题上有了质的飞跃。2. NSGA-III的三大核心智力参考点、归一化与生态位选择2.1 参考点生成Das-Dennis方法与小H问题NSGA-III里最显眼的改动就是参考点。参考点不是随机撒的而是按照某种均匀结构生成的原始论文推荐用Das-Dennis方法也叫单纯形网格设计。说得具体一点它把M维目标空间当成一个单纯形每个参考点的坐标分量都从 \( \{0/k, 1/k, ..., k/k \} \) 里取值并且所有分量之和为1。这样生成的参考点数量有个组合公式$$H \binom{M p - 1}{p}$$其中M是目标函数个数p是每个目标方向上的分割份数。举个例子目标数M3分割数p4那么参考点数H C(34-1, 4) C(6,4) 15。如果想在3目标问题上用大约100个参考点可以把p设为9H算出来正好是55或者p13H105。种群规模N通常就取和H接近的值。这里有一个非常实际的问题就是随着M增大参考点数会组合爆炸。M5p8时H C(12,8) 495还算能接受但M10p哪怕取3H C(12,3) 220也勉强。可目标一旦到15个以上想生成上千个参考点C(N,k)的组合增长会把过程和存储都逼得很难受。处理办法通常有几种。第一种是降低分割份数p让参考点数量减下来但这会牺牲分布精度。第二种是随机生成一部分参考点嗯有不少实现会在参考点数量不够的时候用随机均匀采样来凑数。第三种是更高级的做法叫双层参考点生成就是同时在单纯形内部和边界上生成两层参考点在保留边界点重要性的同时增加内部点的覆盖。这个我在后面会稍微展开。实际编码时Das-Dennis参考点的生成可以用递归的方式来实现也就是先固定第一个维度再在剩下的M-1维里递归生成组合。网上很多现成代码都这么写但你们要留意顺序一不小心就会生成重复或者丢失点。2.2 归一化的数学原理理想点、极端点与截距参考点生成了但目标函数数值的范围跟参考点坐标根本不在一个数量级上直接算距离是没有意义的。所以在关联参考点之前必须先做归一化把每个目标上的数值都压缩到差不多同一个尺度里。NSGA-III的归一化分三步走。第一步计算理想点也就是种群中每个目标上的最小值组成的向量记为 \( z^{min} \)。第二步对每个个体用理想点做平移得到 \( f_i(x) f_i(x) - z_i^{min} \)。第三步求每个目标方向上的极端点。极端点的求法值得注意。对第i个目标要找一个个体让它在“主要看第i个目标”的标量函数下取值最小。实际中常用的是Wierzbicki的增强标量函数achievement scalarizing function形式大致是$$ASF(x) \max_{j1..M} \left( \frac{f_j(x)}{w_j} \right) \rho \sum_{j1..M} \frac{f_j(x)}{w_j}$$当我们要找第i个目标的极端点时就令权重向量 \( w_i 1 \)其他权重 \( w_j 10^{-6} \) 这种极小值。这样谁能让ASF最小谁就可以充当第i个目标的极端点。拿到M个极端点之后用这M个点构造一个M-1维的超平面然后计算这个超平面在每个目标轴上的截距 \( a_i \)。最后用截距做归一化$$f_i^{norm}(x) \frac{f_i(x)}{a_i} \frac{f_i(x) - z_i^{min}}{a_i}$$这个归一化处理做完之后所有目标函数的范围基本都落在 \( [0,1] \) 附近参考点坐标也在这个范围里后续计算垂直距离才有意义。这里最需要警惕的是当极端点构造超平面失败或者截距出现负值、极大值的时候这个归一化就废了。原因通常是某些目标上的极端点太接近导致超平面退化。我在第4部分会专门讲这个问题。2.3 关联操作与生态位计数NSGA-III的“拥挤度替代者”归一化完成后需要把每一个个体关联到离它最近的参考点上。这里说的“距离”不是欧氏点到点的距离而是个体到参考点所在直线的垂直距离。参考点一般是从原点出发、经过单纯形上那个坐标点的射线方向所以这个距离可以衡量这个个体在“该参考方向”上有多少偏离。每个个体找到最近的参考点后我们就统计每个参考点关联了多少个体这个数量记作 \( \rho_j \)。这个 \( \rho_j \) 就是NSGA-III替代NSGA-II拥挤距离的核心指标它的含义很直接这个参考方向上已经有多少个解了。生态位选择就是围绕 \( \rho_j \) 展开的。在需要从最后一个非支配层里挑个体补满种群的时候先找出 \( \rho_j \) 最小的参考点优先往这些冷门方向补人。如果某个参考点 \( \rho_j 0 \)但当前前沿面里正好有和它关联的个体那就无条件选一个进来让这个方向上从无到有。如果 \( \rho_j 0 \) 且当前层没有个体关联到它这个参考点就直接被忽略。如果 \( \rho_j 0 \)那就在关联到这个参考点的个体里挑垂直距离最小的进来让这个方向上的解更贴近参考方向。这套机制比拥挤距离好在哪好在它有明确的“分布目标”。每个参考点可以看成目标空间里的一个表示点参考点均匀按参考点补出来的个体就均匀。而拥挤距离只是局部密度估计高维下根本没有“均匀”的全局概念。2.4 与NSGA-II选择算子的区别把两代算法的选择算子放在一起对比区别就很清晰了。NSGA-II是“非支配排序 拥挤距离”NSGA-III是“非支配排序 参考点关联 生态位计数”。前者是一种相对被动的保持多样性方式它不知道所谓的“均匀”应该按什么全局标准来组织只是尽量在稀疏地方放点。后者是一种带引导的选择方式参考点在目标空间里画好了网格选择过程就是往网格上分配个体。这个差异带来的效果差异是很实际的。以目标数M3、种群大小N100为例NSGA-II偶尔会在Pareto前沿的某个局部区域堆出一大团点另一块区域却空荡荡NSGA-III因为参考点均匀分布在整个单纯形上只要进化代数足够每个参考方向附近都会分配到个体分布基本不会出现大片空洞。3. 把整个算法流程走一遍从初始化到环境选择3.1 种群初始化与参考点准备NSGA-III的起点和标准遗传算法一样先随机初始化N个个体每个个体是一组决策变量编码。不同的是你同时要生成H个参考点并确定种群规模和参考点数量的关系。比较推荐的做法是先算参考点数H再决定种群规模N。如果N正好等于H那最省心。如果N小于H就随机从H个参考点里选N个作为激活参考点。如果N大于H理论上也可以只要最后环境选择能通过生态位计数补满就行但通常不建议让N比H大太多否则部分方向会冗余堆积。我自己的实践习惯是在优化问题目标数M不超过8的情况下优先让H等于N或者H是N的近似值。这可以省掉很多调参时的心智负担。3.2 遗传操作与合并种群主循环的每一代都用遗传操作从当前种群P_t里生成子代种群Q_t。遗传操作的选择算子、交叉算子、变异算子可以根据决策变量的类型自由选择。如果决策变量是连续的可以选SBX交叉和多项式变异如果决策变量是离散的可以选模拟二进制交叉的变体或者直接用均匀交叉加位翻转变异。子代生成完之后把父代和子代合并成一个规模为2N的种群 \( R_t P_t \cup Q_t \)。这个操作和NSGA-II完全一致本质上是为了保证精英保留让父代里的好基因不至于在替换中丢失。3.3 逐层筛选非支配排序的边界处理接下来对 \( R_t \) 做快速非支配排序把种群划分成若干互不支配的前沿层 \( F_1, F_2, ... F_l \)。注意这一步和NSGA-II前端排序一样没有区别。真正的分水岭是当 \( F_1 \cup ... \cup F_l \) 的总个体数第一次大于等于N的时候。假如前l层的总个体数刚好等于N那就直接把 \( F_1 \cup ... \cup F_l \) 作为下一代种群不用做参考点选择这最省事。但在大多数情况下前l层加起来会超过N而 \( F_1 \cup ... \cup F_{l-1} \) 加起来又不到N。这时候就要从 \( F_l \) 这一层里挑一部分个体补满N。3.4 关键一步在前沿层F_l上做基于参考点的选择这一步是NSGA-III里最核心也最容易写错的地方。我先给出完整的处理流程。第一已经从 \( F_1 \cup ... \cup F_{l-1} \) 中确定了保留下来的个体集合 \( S_t \)接下来要在 \( F_l \) 中选 \( K N - |S_t| \) 个个体进下一代。第二对整个 \( S_t \cup F_l \) 做归一化。极端的思路是只对 \( S_t \) 做归一化但那样会导致某些进入 \( F_l \) 的个体坐标被扭曲所以正确做法是把这两部分合并起来一起算理想点和极端点。第三把 \( S_t \cup F_l \) 里的每个个体都关联到最近的参考点统计每个参考点当前关联的个体数 \( \rho_j \)。第四构造一个当前待激活参考点集合 \( J_{min} \{ j \, | \, \operatorname{arg\,min}_j \rho_j \} \)。意思就是找到所有 \( \rho_j \) 最小的参考点如果多个并列就都拿进来。第五从 \( J_{min} \) 里随机挑一个参考点j。如果 \( \rho_j 0 \)说明这个方向还没有个体那就优先从 \( F_l \) 中找出所有关联到参考点j的个体选垂直距离最小的那个加入下一代后面再更新 \( \rho_j \)把这个参考点从待激活集合里去掉。如果 \( F_l \) 中不存在关联到参考点j的个体那就直接把这个参考点废弃再随机挑下一个 \( J_{min} \) 里的参考点。如果 \( \rho_j 0 \)说明这个方向已经有个体了那就在所有关联到参考点j的 \( F_l \) 个体中选垂直距离最小的补进去。这个过程循环K次最终把下一代种群填满。最后用一句话总结这个流程先按支配关系分层淘汰弱者再用参考点方向引导补位保证收敛性的同时维持均匀性。这也是整个算法最值得品味的设计。4. 实现与参数细节代码层面最容易翻车的地方4.1 参考点数量与种群规模的匹配关系编程实现NSGA-III时我遇到过最无语的问题就是参考点数和种群规模不匹配。有人直接把种群规模改成和参考点数一样这通常没毛病。但有时候为了对比公平实验要求N固定为100而参考点数算出来是120或者84这就需要在生成参考点之后做一次筛选或补全。如果参考点数比N大一般就随机抽样出N个参考点来用。如果参考点数比N小我建议不要硬用宁可把参考点分割参数调大一点也别出现N远大于H的局面。因为参考点是多样性的“锚”锚少了算法就退化成往少数方向上堆个体均匀性反而比NSGA-II还差。有个经验值可以分享在目标数M3、N100的时候H取91到105都行M5、N200的时候H取190到220都行。重点不是H要精确等于N而是H不要和N差出一个量级以上。4.2 极端点计算与截距的数值稳定性极端点计算是NSGA-III实现里最容易踩的深坑。我刚开始复现的时候用的是一种简化方式对第i个目标直接找种群中 \( f_i(x) \) 最小的个体作为极端点。这样算出来的M个极端点在多数情况下也能用但一旦目标之间存在比较强的冲突或者前沿形状不规则简化方式就会选到不合适的点导致超平面截距计算出问题。更稳妥的做法是用增强标量函数ASF来找极端点。你可能会问为什么ASF比单纯取最大值更好因为目标优化的个体往往不止一个单纯取某个目标的最大值可能落在前沿的边缘但不一定是边界支撑点。ASF通过极小的 \( \rho \) 扰动能让选择的点既贴近目标方向又不会因为退化问题陷入数值异常。截距计算失败还有一个典型场景当M个极端点构成的矩阵接近奇异时超平面不存在截距算不出来。为了处理这种情况实际代码里通常要加一个判断如果截距计算失败回退到 \( a_i \max_{x \in S_t \cup F_l} f_i(x) \)也就是把当前种群中第i个目标的最大值当截距。这种做法虽然粗略但至少能让归一化过程稳定跑下去。4.3 归一化失败时的对策归一化不是每次都顺风顺水。即使截距算出来了也可能遇到 \( a_i \leq 0 \) 的情况。这种情况通常发生在Pareto前沿的形状已经退化或者某一维目标函数在种群中的差异非常小导致截距为负。遇到 \( a_i \leq 0 \) 时不要直接崩溃退出。一般的策略是先把目标自适应地映射到一个固定区间比如 \( [0,1] \)然后忽略超平面截距的修正直接把 \( f_i^{norm} (f_i - \min) / (\max - \min) \)。这是很多开源库实际采用的回退策略虽然理论纯度没那么高但工程上非常稳定。从论文实现的角度看原始NSGA-III论文里对这个问题的处理其实也比较粗主要就是“遇到失败换一种归一化方法”。所以你写代码时没必要追求把归一化一步做到完美预留一个回退分支就够了。4.4 参考点关联的高效实现参考点关联这一步看起来简单就是算个体到每条参考线的垂直距离然后取最小值。但实际跑起来如果N500、H500、目标数M10每一代关联计算要跑25万次点到直线的距离每次距离计算又涉及M维向量运算累计开销其实不小。我碰到过跑一次500代实验光关联操作就占了总运行时间40%以上的情况。优化思路有两个方向。第一把参考点坐标预先算好存成矩阵不要每代重复生成。第二用向量化方式批量计算而不是用Python写两层for循环逐个体遍历。用NumPy或PyTorch这类支持广播的库一遍矩阵运算就能把整个种群的关联距离全算出来速度可以提升几十倍。还有个细节NSGA-III原始论文里关联的是“参考线”也就是从原点出发穿过参考点的射线。但有些实现简化成了“参考点”本身直接算欧氏距离。这两种实现会在参考点处于边界时产生差异。我个人建议用射线方式也就是垂直距离/投影方式这样更贴近论文并且处理高维边界时更稳定。5. NSGA-III与其他算法的横向对比与选型思路5.1 与NSGA-II、MOEA/D、SPEA2的对比表很多读者最想知道的是NSGA-III是不是全面碾压NSGA-II答案是否定的。它们各自有不同的适用区间。维度NSGA-IINSGA-IIIMOEA/DSPEA2核心多样性机制拥挤距离参考点生态位计数权重向量聚合最近邻密度估计目标数适用区间2-3个勉强4个3-15个高维2-10个依赖聚合函数2-3个解集均匀性中低维良好高维优秀有参考点保证依赖权重向量中低维良好计算复杂度低参考点关联带来额外开销低中等对归一化敏感度低高依赖于聚合函数形式低约束处理通用约束支配通用约束支配需额外处理通用约束支配从这个表能看出一个趋势NSGA-II和SPEA2适合经典的低维多目标问题两三个目标的情况下它们不仅简单而且效果很好。MOEA/D的权重向量可以自适应匹配Pareto前沿形状但如果前沿是非凸不连续的聚合函数的选择会变得很讲究。NSGA-III则天然为高维目标场景设计参考点让它在3个目标以上依然能给出均匀分布的解集。5.2 它不适合哪些场景适合哪些场景NSGA-III虽然在高维目标问题上很能打但并不是万能的。它有比较明显的适用边界。第一如果目标空间本身是极端非线性的参考点固定均匀分布可能和真实Pareto前沿形状严重不匹配。比如Pareto前沿是断开的、多片状的固定的参考点就会导致大量参考方向落在空白区域浪费种群个体。这种情况可以考虑自适应参考点版本比方说在进化过程中根据当前前沿形状动态调整参考点。第二如果目标个数非常多比如超过15个纯静态参考点的NSGA-III也会退化。因为参考点数量组合爆炸H若太小多样性锚点不足H若太大种群规模跟不上每个参考方向只有很少个体选择压力不够。此时更适合用一些近年来提出的新型算法比如基于目标降维或基于方向向量的方法。第三如果问题收敛本身很困难决策变量很多NSGA-III也不会比NSGA-II有质的提升。因为它的改进主要集中在“高维目标下的多样性保持”不是为收敛性发明的。收敛性还是要靠遗传算子、邻域搜索或者局部搜索来保证。适合的场景很清楚目标数3到10个之间、Pareto前沿相对完整连续、需要解集在目标空间里分布均匀的多目标优化问题。这些问题用NSGA-III跑基本都能得到一个让人满意的结果。5.3 一些值得尝试的后续改进方向实际用NSGA-III的过程中我研究过几个比较有效的变体在这里记录一下思路。自适应参考点方向是改进的第一大方向。固定的Das-Dennis参考点与问题特性无关但对不同问题的Pareto前沿理想的解分布可能完全不同。可以每隔若干代重新根据当前种群的极端点和均值来生成参考点让参考方向随着前沿形状调整。第二种改进方向是和其他局部搜索算子结合形成memetic算法。NSGA-III负责全局搜索局部搜索负责精细收敛两个阶段交替进行。这个方向在工程优化里非常实用。第三种是和约束处理结合。如果问题有大量约束可以直接用约束支配原则替换原论文里的支配关系即一个可行解总是支配不可行解两个不可行解中约束违反程度更小的占优。这样不需要额外修改NSGA-III的主体结构就能处理带约束的高维多目标问题。6. 我踩过的坑与调试心得6.1 连续问题不要无脑用二进制编码刚开始做实验时我以为NSGA-III和NSGA-II一样可以用二进制编码加简单交叉。结果在连续优化问题上二进制编码把精度限制死了Pareto前沿上很多细节区域根本搜不到。后来改成实数编码配SBX交叉和多项式变异收敛质量立刻上了一个台阶。SBX的分布指数 \( \eta_c \) 和变异分布指数 \( \eta_m \) 设置也值得注意。经验上 \( \eta_c \) 取15到20\( \eta_m \) 取15到20效果比较均衡。如果想让解集分布更广泛可以适当调大 \( \eta_c \)让子代更接近父代如果想让搜索范围更大可以适当调低。6.2 参考点关联速度慢的时候先别优化算法先看是不是循环没用向量化我一开始自己写的Python版NSGA-III跑8目标、N300的问题一代要跑三四秒500代下来得二十多分钟。后来发现瓶颈全在两层for循环的关联距离计算上。改成NumPy批量计算之后一代时间降到0.2秒左右提速了十几倍。所以我的建议是先把实现跑通再性能剖析。如果你发现每次迭代特别慢先定位是排序慢还是关联慢。排序用现成的高效实现关联距离优先向量化。千万不要一上来就上并行计算很多时候串行向量化就已经够用了。6.3 实验对比时要固定随机种子并关注IGD和HV两个指标做算法对比时最忌讳的是只跑一次就下结论。NSGA-III是随机算法不同随机种子的结果差异可以很大。我一般同一个参数配置跑11次或21次独立重复实验取中位数和四分位距然后看两个指标IGDInverted Generational Distance和HVHypervolume。IGD衡量的是算法求得的解集到真实Pareto前沿的平均距离需要你知道真实前沿常用于测试函数。HV衡量的是解集在目标空间里覆盖的超体积不需要真实前沿适合实际工程问题。这两个指标一起看一个管收敛性一个管多样性。有意思的是NSGA-III在HV指标上通常会比NSGA-II好但有时候在IGD上优势不明显。原因在于参考点机制保证的是均匀分布而IGD对分布均匀的要求和参考点并不完全等价。所以如果你在论文里要对比算法最好两个指标都报别只挑好看的说。6.4 先把可视化做出来再调参多目标优化有个很实际的调参技巧先把3目标问题的三维散点图做出来肉眼观察解集形状再决定怎么调参数。NSGA-III跑出来的结果三维图里应该能明显看到解集分布在一个均匀的三角形或者曲面上。如果某些区域明显稀疏优先检查参考点数量和分割数如果整体偏到一边优先检查归一化是否正常极端点计算是否出了错。我记得有一次跑3目标函数出来的解集全部挤在一个角落里三维图里只有一小团点。排查了半天最后发现是极端点计算用了简化版导致截距偏了归一化把整个目标空间压歪了。换成ASF方法之后问题迎刃而解。6.5 在处理约束时加约束违反度惩罚要小心有些代码实现会在目标函数上加惩罚项把约束问题转成无约束问题来跑。在NSGA-III上这么干要非常小心因为惩罚系数如果设置不合适会严重破坏目标函数的值域进而影响归一化和参考点关联的稳定性。更好的方案是用约束支配原则把约束信息放到支配判断里而不是融合进目标函数。这样归一化过程只用处理真正原始目标函数的值域不容易出幺蛾子。6.6 目标函数数量变化时要重新调整参考点数如果你的实验不是固定目标数而是要对比3目标、5目标、8目标的结果那你必须为每个目标数重新生成参考点。曾经有朋友偷懒用一套参考点跑了所有目标数结果5目标时解集分布乱成一锅粥。这个教训很简单——参考点数量和分割数必须跟目标数匹配不然算法的多样性引导就是无效的。写在最后的一点个人体会把NSGA-III从论文变成可用的代码再变成能稳定产出好结果的工具中间确实有不少弯路。最大的感受是NSGA-III的优秀并不全在参考点这一个机制上而是“非支配排序 归一化 参考点生态位选择”这三者配合得当。任何一个环节出错整个算法都会偏离理想行为。如果你想把它用到自己的问题上我给一个最实际的建议先不要急着改造算法或者加各种自适应机制把标准版NSGA-III跑透用测试函数验证实现正确性再把真实问题的目标函数封装进来。很多时候标准版已经够了真正不够的是你对问题本身的理解和对实验设计的把控。