多目标优化与NSGA系列算法笔记

一、多目标优化基础1.1 为什么需要 Pareto单目标那套失效了单目标问题中最优有明确定义存在一个解使得对于所有可行解 x都有。但现实问题往往有多个互相冲突的目标。例如设计一款手机方案价格越低越好性能越低越好即延迟A2000100B300060C2500120D400090此时问哪个最优没有意义A 便宜但慢B 快但贵。C 被 A 全面碾压更贵且更慢可以直接扔掉但 A 和 B 之间谁也不能替代谁。Pareto 的作用就是在没有统一标尺时给出一个不依赖主观权重的好解判定标准。1.2 核心定义Pareto 支配Dominance设目标是极小化。称支配dominate记作当且仅当所有目标都不差且至少有一个严格更好。即对于所有 i并且存在某个 j使得。回到上表A 支配 C2000 2500 且 100 120→ C 淘汰A 和 B 互不支配A 价格优B 性能优→ 都保留B 支配 D3000 4000 且 60 90→ D 淘汰。1.3 Pareto 最优解集与 Pareto 前沿Pareto 最优解非支配解不被可行域中任何其它解支配的解。概念在哪含义Pareto 最优解集Pareto Set决策空间x 的空间所有非支配解的集合 {x^*}Pareto 前沿Pareto Front目标空间F 的空间这些解对应的目标向量集合 {F(x^*)}上例中Pareto 解集 {A, B}Pareto 前沿 {(2000, 100), (3000, 60)}。在二维图上画出来就是一条向左下方凸出的折线——这条线上的每一点都不能再改善一个目标而不牺牲另一个。1.4 多解问题多解问题找到一组解使得每个都是最小值。这正是小生境算法要完成的任务。传统优化算法每次只能输出一个最优解但小生境算法在一次运行中就能输出多个解覆盖目标函数的所有峰全局最优 有价值的局部最优。1.5 三个容易踩的坑Pareto 最优 ≠ 全局最好。它只是没法白嫖改进前沿上可能有一堆很烂的妥协解比如极贵又极慢的方案也可能在前沿上如果它是唯一高性能选项。选出最终方案仍需人为决策常用方法理想点法、TOPSIS、最大最小满意度。前沿可能是非凸、不连续、甚至高维曲面。目标数时叫很多目标优化Many-objective此时几乎所有解都互不支配支配关系失去筛选力需要改用基于指标的方法如 IBEA、NSGA-III 用参考点。弱支配若只满足对所有 i 有而没有严格小于叫弱支配不能用来淘汰解。代码实现时一定要写对那个存在严格小于的判断条件。二、NSGA-II2.1 早期 NSGA 的缺陷由 Srinivas 和 Deb 于 1994 年提出全称 Non-dominated Sorting Genetic Algorithm。核心思想用层代替标量适应度。对当前种群做非支配排序把种群分层第一层所有不被任何人支配的个体把拿走后剩下的里面再做一次非支配排序得到第二层依此类推。层号 伪适应度层号越小越好最优。同一层内用适应度共享Fitness Sharing拉开距离防止挤成一团。三个硬伤缺陷后果没有精英保留机制父代的好解可能在交叉变异中丢失导致收敛慢甚至退化依赖共享半径该参数必须人工指定且对结果极其敏感用户往往只能盲目试凑计算复杂度高M 为目标数N 为种群规模种群稍大就很慢2.2 NSGA-II 的三处关键改进由 Deb、Pratap、Agarwal、Meyarivan 于 2002 年提出IEEE Trans. on Evolutionary Computation全称 Non-dominated Sorting Genetic Algorithm II。针对上述三点逐一做了改进。改进 1快速非支配排序 —— 复杂度从 O(MN^3) 降到 O(MN^2)对每个个体 p 维护两个量支配 p 的个体数被多少个体压制被 p 支配的个体集合p 压制了谁排序过程所有 0 的个体放入第一层没人压得住它们对中的每个 p遍历其里的每个 q令因为压制者之一已被划入更优层若某个 q 的减到 0说明它的压制者已全部归位将其放入下一层重复上述步骤直到所有个体分层完毕这样每个个体对最多被比较一次复杂度降为。改进 2拥挤距离Crowding Distance—— 干掉 \sigma_{share}同一层内部不再使用共享函数改用拥挤距离衡量个体的周围有多空。拥挤距离的计算方法对每个目标 m取个体 i 在该目标上相邻两个体的目标值之差除以该目标的最大最小值范围然后将所有目标上的差值求和。边界个体最左/最右的拥挤距离设为无穷大以保证前沿端点永远被保留。直观理解拥挤距离大意味着周围空旷应当优先保留以撑开前沿的形状距离小则意味着过于拥挤可被淘汰。这与小生境的适应度共享是同一个目的但不需要任何可调参数。由此定义拥挤比较算子个体 i 优于 j当且仅当或者且。即先比层号层号相同时比谁更空旷。改进 3精英保留策略 —— 保证收敛这是 NSGA-II 收敛性提升的关键。每一代的流程如下 父代种群N 个Q_t 交叉变异产生的子代N 个R_t P_t 与 Q_t 的并集合并成 2NF 快速非支配排序(R_t)得到P_{t1} 依次把塞进去直到装不下最后一层按拥挤距离从大到小挑满 N 个。合并 2N 再截断回 N意味着父代里的优秀个体绝不会因为运气差而被丢掉——这是标准的 () 精英机制。同时由于比较是在父代子代的并集上进行的算法天然趋向 Pareto 前沿。2.3 完整算法流程初始化 P_0随机 N 个→ 评估 → 合并 R_t P_t \cup Q_t精英保留→ 快速非支配排序 → 填不满一层时用拥挤距离挑 → 锦标赛选择用→ 交叉 变异 → Q_{t1} → 评估 → 回到合并。停止条件达到最大代数或前沿在一定代数内不再明显推进。2.4 约束处理NSGA-II 的隐藏亮点NSGA-II 还给出了一个极其实用的约束支配constraint-domination规则无需引入罚函数参数个体 i 约束支配 j当且仅当1i 可行而 j 不可行或2两者都不可行且 i 的约束违反总量更小或3两者都可行且 i 在通常意义下支配 j。这意味着可行解永远优于不可行解不可行解之间比谁违规更少。这个设计让算法能自动从不可行域逼近可行边界比调罚因子 \rho 省心得多。2.5 实践要点与常见坑种群规模要够一般前沿才能铺得平滑。N 太小会导致前沿变成几个孤立的点。必须做目标归一化拥挤距离公式的分母是。如果某个目标的量级远大于其他距离计算会被大尺度目标主导前沿分布随之变形。交叉概率高、变异概率低常用模拟二进制交叉 SBXn 为变量维数。别用 NSGA-II 做单目标退化成单目标后它就等于普通 GA 加精英保留没有任何额外优势。最终怎么选一个解算法输出的是一整条前沿工程落地仍需决策。常用方法包括理想点法最小化到 utopia 点的距离、TOPSIS 或最大最小满意度法。验证方式先用 ZDT1~ZDT6双目标、已知解析前沿跑通计算 HVHypervolume或 IGD 指标确认无误后再上真实问题。三、NSGA-III3.1 Many-Objective Optimization 问题当目标数量从传统的 2 个、3 个增加到 4 个甚至更多时就进入了所谓的Many-Objective Optimization也就是超多目标优化。这里最关键的问题不是简单地说目标多了所以计算量变大而是Pareto 支配关系本身的区分能力开始下降。因为目标数量增加以后一个解要支配另一个解需要在更多目标上同时满足不差并且至少一个目标严格更好。因此随着目标维数增加随机种群中的非支配解比例会迅速增加。最终就可能出现一种情况大量解全部属于第一 Pareto 前沿。如果大量解都属于 F_1那么单纯依靠 Pareto rank 就很难进一步区分这些解。这意味着NSGA-II 原来非常重要的排名优先机制在高维目标空间中的区分能力下降了。因此问题就变成如果大家都是第一前沿到底应该保留哪些解这时候仅仅依靠拥挤距离进行局部密度判断就面临更大的挑战。3.2 NSGA-III 核心思想NSGA-III 的核心思想可以概括成一句话用预定义的参考点引导多目标搜索向不同方向覆盖。NSGA-II 更强调哪里比较拥挤而 NSGA-III 更强调我希望搜索覆盖哪些方向具体来说NSGA-III 会在归一化的目标空间中预先设置多个参考点。这些参考点分布在一个单纯形simplex上。每一个参考点实际上可以理解成一个期望搜索方向。算法希望最终得到的解能够覆盖这些不同方向。因此 NSGA-III 的多样性维护不是单纯地看某个解附近拥不拥挤而是建立了一个更加显式的发展方向覆盖机制。3.3 NSGA-III 整体框架从整体框架来看NSGA-III 和 NSGA-II 其实非常像首先同样是父代 子代形成合并种群然后同样进行非支配排序。NSGA-III 并不是完全推翻 NSGA-II它保留了很多 NSGA-II 的基本框架。真正发生变化的是如何进行多样性维护和最后的环境选择。NSGA-II 使用的是 Crowding Distance拥挤距离而 NSGA-III 则使用自适应归一化、参考点关联、小生境保留。3.4 参考点的生成NSGA-III 使用 Das 和 Dennis 提出的系统方法来生成参考点。基本思想是在一个归一化的单纯形单位超平面上均匀地放置参考点。这里有一个参数 p可以把它理解成每一个目标方向被划分成多少个等间隔。参考点数量为其中 M 是目标数量p 是划分数H 是最终得到的参考点数量。举一个三目标的例子如果 (M3)(p4)那么最终得到 (H15) 个参考点。这些参考点就相当于提前规定了一组搜索方向。当然除了这种系统生成的方法也可以根据实际问题或者决策者偏好设置自定义参考点。3.5 自适应归一化在真正进行关联之前还有一个非常关键的问题不同目标的尺度可能完全不一样。例如第一个目标可能在 0 到 10000 之间变化第二个目标可能只有 0 到 1。如果直接计算距离那么尺度大的目标就可能对距离产生更大的影响。所以 NSGA-III 需要先进行自适应归一化。这一过程大致可以分成五步确定理想点在当前种群中每个目标分别取得到的最小值平移对目标值进行平移使理想点变成原点寻找极端点通过 ASFAchievement Scalarizing Function寻找各个目标方向上的极端点确定截距利用这些极端点确定相应的截距归一化根据截距对目标值进行归一化为什么叫自适应因为它不是提前固定一个归一化范围而是根据当前进化过程中种群的实际情况动态计算。这样才能让参考点和当前种群处于一个具有可比性的目标空间中。3.6 关联操作Association完成归一化以后就进入 NSGA-III 非常核心的关联操作。它主要分三步把参考点转化成参考线从原点出发经过参考点向外延伸。每一个参考点实际上对应一个方向计算垂直距离计算每个解到每一条参考线的垂直距离不是解到参考点的普通欧氏距离而是解到参考方向/参考线的垂直距离关联对于每一个解找到距离它最近的参考线然后把这个解关联到对应的参考点这样完成以后整个种群中的解就被分配到了不同的搜索方向上。3.7 小生境保留Niche Preservation这是 NSGA-III 环境选择中非常关键的一步。核心变量 \rho_j 表示第 j 个参考点当前已经有多少个解被选入下一代。主要考虑两种情况\rho_j 0这个参考方向目前还没有解被选中优先覆盖这个方向选择距离该方向最近的候选解。这样可以保证这个方向至少得到一个解。\rho_j 0这个方向已经有解被选择了为了避免这个方向过度集中从该方向的候选解中随机选择一个。因此NSGA-III 的核心思想就是优先补充没有被覆盖的方向而对于已经覆盖的方向则不再一味选择距离最近的解。这样能够让不同参考方向之间保持比较好的覆盖。3.8 NSGA-III 完整环境选择流程父代和子代合并进行非支配排序得到不断把完整前沿加入下一代当加入某一个前沿以后超过种群规模 N 时进入关键的环境选择阶段对当前候选解进行自适应归一化根据归一化后的目标值将每个解关联到最近的参考方向统计每一个参考方向已经选择了多少个解优先考虑目前没有被覆盖的参考方向时选最近的已经覆盖的方向时随机选不断重复直到下一代种群达到 N概括Pareto 排名负责筛选较好的前沿归一化负责统一目标尺度关联负责确定解属于哪个方向小生境保留负责保证不同方向的覆盖。3.9 NSGA-II vs NSGA-III 对比特性NSGA-IINSGA-III核心机制非支配排序 拥挤距离 精英保留非支配排序 参考点 自适应归一化 小生境保留 精英保留多样性维护拥挤距离局部密度参考点机制方向覆盖高维表现目标数时性能崩塌支配抵抗专为高维设计表现更优计算复杂度O(MN^2)O(MN^2) 归一化/关联额外开销适用场景低维2~3维、约束复杂问题高维\ge 4 维many-objective 问题参数依赖无特殊参数参考点分布参数 p核心区别一句话NSGA-II 更强调哪里比较拥挤NSGA-III 更强调哪些方向需要覆盖。从 NSGA-II 到 NSGA-III本质上体现的是多目标优化中多样性维护思想的变化——从局部密度驱动逐渐转向显式方向驱动。3.10 为什么就崩目标维度升高时空间中任意两点互不支配的概率急剧上升导致几乎整个种群都挤在 F_1 层。此时非支配排序失去筛选力搜索退化为接近随机游走。这被称为支配抵抗dominance resistance。解决办法是换用 NSGA-III它放弃拥挤距离改用一组预先定义的参考点reference points将个体关联到最近的参考方向上进行选择从而在高维目标空间维持多样性。