★ FEATURED ARTICLE 做算法选型笔记的第14天我把目光落在了一个几乎绕不开的主题上多目标优化算法。起因是接手的那个调度系统优化项目卡壳了——生产线上同时要管订单完工时间、设备利用率和能耗成本三个指标互相打架怎么调参数都不对劲。当时我下意识把所有目标加权成一个综合得分权重调了两周业务那边还是一句这权重谁定的就把方案打回来了。后来才想明白这压根不是权重怎么设的问题而是这类问题的数学结构决定了加权求和这套思路本身就很难走通。这个项目让我彻底把多目标优化的底子补了一遍从Pareto支配到NSGA-II、MOEA/D再到实际落地时的评价指标和调参经验踩过的坑不少但收获也很大。这篇笔记我把完整思路和代码都整理出来了既适合正要入门多目标优化的新手也能给已经在做进化算法、但觉得结果不对劲的老手一些对照参考。1. 为什么加权求和不是万能的——多目标问题的本质1.1 从单目标到多目标一个调度系统的真实困惑单目标优化很好理解评价函数只有一个比如最小化订单总完工时间搜索空间里存在一个明确的最优值算法只要一直往那个方向逼近就行。但现实里的问题几乎从来不会这么干净。调度系统里我至少要同时看三个维度完工时间越短越好设备利用率越高越好总能耗越低越好。问题就出在同时两个字上。压缩完工时间的常规做法是加开设备、增加并行工序、缩短排队等待这直接导致能耗上升设备利用率想要拉满就得让机器一直不停地跑可产量不满时硬排产会白白耗电完工时间还不一定好看。三个目标之间是互相牵制的一个目标好一点另两个往往就差一点。一开始我做的是加权求和score w1 * 完工时间 w2 * 设备空闲率 w3 * 能耗再把三个值归一化到同一量纲。想法挺美好实操起来全是坑。第一权重值本身就是拍脑袋凭什么完工时间是0.5能耗是0.2业务解释不清楚我也不服气。第二量纲差异很大完工时间可能是几百分钟能耗可能是几千千瓦时归一化方法和权重直接耦合换一种归一化最优解就变了。第三也是最硬伤的一点——加权和本质是把多目标强行压成一维这样永远只会在Pareto前沿的一个点上兜圈子找不到完整的权衡方案集。这个认知转过来之后我才开始认真研究多目标问题的数学本质也就是Pareto那一套体系。1.2 Pareto支配与Pareto前沿把最优解变成一组候选解多目标优化首先得回答一个问题在没有办法把所有目标同时做好的情况下什么样的解算好上学时最常听到的词是Pareto支配。两个解A和B如果A在所有目标上都不比B差而且至少有一个目标strictly优于B就说A支配B。被支配的解可以直接淘汰因为它全面落后但两个解各有胜负时——比如A的完工时间短但能耗高B的能耗低但完工时间长——它们谁也不支配谁这时候两个都不能轻易扔。所有不被任何其他解支配的解组成的就是Pareto最优解集在目标空间里连成的那条线或那个面叫Pareto前沿。从实际业务出发可以把Pareto理解成挑房子。面积和总价两个目标一套房面积大价格低另一套面积小价格高前者全面碾压后者可以直接排除但遇到面积大总价也高的户型和面积小总价低的户型选哪个纯粹是个人偏好问题它俩都站在Pareto前沿上。做多目标优化本质上就是把那一堆各有优劣、但都比别的解全面占优的候选方案摆出来让有决策权的人去选而不是替人拍板。注意Pareto最优解集里的解数量可能很多太大了就没法给决策者用了。所以算法的另一个隐藏任务是在保证前沿质量的前提下让解的数量可控、分布可读。1.3 多目标优化算法要同时管好三件事收敛、多样、均匀想明白Pareto之后我看算法的眼光就变了。一个多目标进化算法不管叫什么名字骨子里都在平衡三件事收敛性解集要尽量贴近真实的Pareto前沿不能停在距离前沿老远的地方自嗨。多样性解集要覆盖前沿的各个区间不能全部挤在一个角落里否则等于只会做一种风格的方案。均匀性解在目标空间里分布均匀让业务方看的时候能清晰地感知多花10%的能耗能把工期压缩多少这种连续的权衡关系。这三个目标互相也有张力。追求收敛算法容易早熟收敛到一个局部前沿区域追求多样性种群可能被带到一些收敛很差的地方。好算法都是在边上走钢丝。后面聊NSGA-II、MOEA/D的时候你会反复看到它们各自用什么机制去压这三块——这也是判断一个算法靠不靠谱的核心视角。2. 主流多目标进化算法的思想脉络与适用场景2.1 NSGA-II非支配排序加拥挤距离最通用的那个起点NSGA-II是2002年Deb等人提出来的真正的基操级算法到今天依然是应用最广泛的多目标进化算法之一。实际项目里你没想清楚用啥好的时候默认先上NSGA-II通常不会错。它的核心机制有两条。第一条叫非支配排序每一代把种群里的个体按Pareto支配关系分层第一层是当前谁都干不掉它的解第二层是去掉第一层之后剩下的解里谁也都干不掉它的以此类推。分完层之后第一层优先保第二层次之层数靠后的直接淘汰。这一手保证了收敛方向——好的解永远有更高的存活优先级。第二条叫拥挤距离。同一层里如果还要做取舍就引入了一个几何指标计算每个个体和它相邻个体在每个目标轴上的距离之和。这个值越大说明它周围越空、越稀罕越值得留反之说明它周围挤满了同类解留着意义不大。这个搜空点的机制就是为了保多样性不让大家窝在一个区域里内卷。NSGA-II的整个选择流程是父代子代合并成2N规模按非支配层级从前往后填新种群填到某层装不下时按拥挤距离从大到小取够数。它的优势是参数少几乎不需要你来调什么花哨的超参实现也很直白效果在2到3个目标的问题上相当能打复杂度O(MN²)。缺点也很明显目标数量一旦上到4个以上绝大多数个体都互不支配分层机制失灵选择压力骤降结果会非常拉胯。这也是后面为什么会有NSGA-III的原因。2.2 MOEA/D分解思想把多目标拆成多个单目标MOEA/D和NSGA-II走的是完全不同的路子。它不搞非支配排序而是把多目标问题分解成一组单目标子问题每个子问题配一个权重向量比如用加权和或者切比雪夫聚合把多个目标叠成一个标量函数。种群里的每个个体专职负责一个子问题优化的方向就是把这个子问题的标量值压到最低。关键在于权重向量不是乱定的而是在目标空间里均匀撒开。解分布的多样性全靠这组权重向量的均匀程度来保证这是它和NSGA-II最大的区别——多样性是结构性地内置在算法里的。理解MOEA/D有一个很好的类比一个大工程所有人都在做同一件事容易打架且摸不到全局更好的做法是把工程拆成一堆方向明确的小组每个组负责一个方向小组之间通过领域结构互相交换信息。MOEA/D就是那个把方向预先定好、各小组各司其职、偶尔串门聊两句的组织方式。我在实际项目里喜欢用MOEA/D的场景有两个一是目标数恰好2到3个二是希望最终前沿的均匀性非常好、给决策者当筛选表来用。它的计算量通常比NSGA-II低一些因为每个个体只和邻域内的几个体比较不用做全局非支配排序。但想用它得先花心思把权重向量和邻域半径调好否则会出现解集覆盖不全的问题。2.3 SPEA2与PESA2存档策略和网格密度控制除了NSGA-II和MOEA/DSPEA2和PESA2也值得一提。SPEA2的核心是引入一个外部存档专门保存当前找到的非支配解同时给每个个体分配一个强度值——被它支配的解越多它在选择时越占优。密度估计用的是k近邻机制距离越远越稀疏的个体越优先保留。PESA2的思路又不一样它把目标空间划分成超网格每个网格统计解的数量网格里解越少这个区域的个体在配对选择时越容易胜出。这本质上是一种更直接的地理多样性控制策略。说实话这两个算法在实际工程里出镜率没有前两个高但它们的思路很有意思一个告诉你好东西要单独存起来护住另一个告诉你少人去的区域价值更高。读懂了它们再回头看其他算法的设计基本就是它们在收敛与多样之间做的不同取舍。2.4 高维目标问题与NSGA-III四个以上目标怎么办前面反复提到目标一多NSGA-II就顶不住。这事的根因是维度诅咒目标数上来之后任意两个个体互不支配的概率急剧升高种群几乎全员都是Pareto前沿层排序根本分不出好坏算法退化成随机漫游。高维场景下真正站出来的是NSGA-III。它的思路是在NSGA-II的非支配排序基础上把拥挤距离换成了参考点机制。算法先根据目标数量在超平面上生成一组均匀分布的参考点每一层里再根据个体与参考点的关联情况挑选优先选那些关联到还没有解占位的参考点的个体。这样多样性有了保证而且可以适应3到15个目标的问题。选算法这件事我习惯先问三个问题目标数量是多少、评估一次目标函数贵不贵、决策者最终要的是精确数值还是权衡趋势。下面这张表是我常用的选型参考算法核心思想适合的目标数主要缺点NSGA-II非支配排序 拥挤距离2-3高维目标选择压力不足MOEA/D分解为单目标子问题2-3解分布依赖权重向量设计SPEA2外部存档 强度Pareto2-3存档和密度计算较复杂PESA2超网格密度控制2-3网格大小需要手工设定NSGA-III参考点引导选择3-15参考点设置依赖目标数先验表里这个适合的目标数不是死的但作为第一关筛选基本够用。目标一旦超过15个进化算法的表现普遍都比较吃力很多团队会转去做基于梯度或启发式分解的思路那又是另一个话题了。3. 从问题建模到算法落地的完整实操链路3.1 把业务问题写成数学形式决策变量、目标函数、约束算法归算法工程落地的第一关永远是怎么把业务问题翻译成数学形式。我以车间调度问题简化版为例拆一下。假设有若干订单每单包含多道工序每道工序可以分配给不同机器我要同时优化完工时间、拖期总时长、总能耗。建模的时候要明确三块决策变量每道工序分配到的机器、工序在机器上的加工顺序。在算法里这就是染色体的形态和长度。目标函数最小化makespan最大完工时间、最小化总拖期、最小化总能耗。三个目标互相冲突正好是典型多目标形态。约束条件同一订单的工序有先后依赖同一时刻一台机器只能加工一个工序加工时间不得为负。这一步最关键的坑是约束必须显式列出来目标也必须显式列出来。很多人拿业务问题就直接套算法模板结果决策变量定义模糊约束写在代码注释里没落到算法逻辑里最后种的个体大量违反现实规则算法跑起来全是无效解。我建议建模时单独写一页纸把变量—目标—约束三栏列清楚再做任何编码工作。3.2 编码方式与初始化策略为什么我不建议纯随机初始化建模定了下一步是编码。常见的选择有实数编码、二进制编码、排列编码具体用哪个取决于决策变量的自然结构。连续优化问题用实数编码最顺调度排产这类天然有先后顺序的用排列编码更合适每个基因位是工序序号一整条染色体就是一份完整的工序顺序表。初始化上很多人图省事直接uniform随机撒。但纯随机有一个明显的问题算法的起点离可行域和好的性能区域太远前面几十代全在瞎跑浪费宝贵的评估次数。我实际常用的做法是混合初始化——大部分个体随机生成掺一小部分用启发式规则产生的解。比如调度问题里可以混入按最短加工时间优先SPT和按最早交期优先EDD排出来的解。就这一步操作常常能让同样的预算下收敛速度明显提升算是一个性价比极高的技巧。3.3 交叉变异与约束处理推荐顺序是编码规避 修复 罚函数编码和初始化定了之后就要配交叉和变异算子。实数编码经典搭配是模拟二进制交叉SBX加多项式变异排列编码一般用部分匹配交叉PMX或者顺序交叉变异用交换两个位置的交换变异或者把一小段逆序的逆序变异。约束处理这块是我踩坑比较多的环节三个主流办法的优先级我盘得很清楚编码规避设计编码本身就不允许产生违反约束的个体。调度问题里用排列编码天然满足工序先后顺序这就是编码规避能用的地方一定先用它没有任何额外的超参数。修复法个体生成了但违反了约束就写一个repair函数把不可行的地方修到可行。比如容量约束超了就把多余的任务往后挪一直挪到满足约束为止。成本是要多写一个修复逻辑但效果稳定。罚函数法在目标函数上加一项罚值让不可行解的适应度变差。这是兜底方案因为惩罚系数本身非常难调——罚重了算法不敢越雷池半步容易陷在局部罚轻了溶液里全在约束边缘反复横跳浪费进化代数。我现在的决策顺序很清楚能编码规避就编码规避规避不干净写修复函数两个都做不了才考虑罚函数。罚函数这个选项我不到万不得已不用因为调罚值消耗的精力往往比把前两种做扎实多得多。3.4 用Python快速跑通一个多目标优化Demo理论说再多不如跑一个Demo来得实在。Python生态里pymoo库是很顺手的多目标优化工具封装了NSGA-II、MOEA/D等主流算法。核心代码可以短到几行import numpy as np from pymoo.algorithms.moo.nsga2 import NSGA2 from pymoo.problems import get_problem from pymoo.optimize import minimize from pymoo.visualization.scatter import Scatter problem get_problem(zdt1) algorithm NSGA2(pop_size100) res minimize(problem, algorithm, (n_gen, 200), seed42) print(res.F.shape) # 输出最后一代非支配解的目标值 plot Scatter() plot.add(res.F) plot.show()ZDT1是经典双目标测试问题pop_size100进化200代res.F就是最后一代的非支配解在目标空间里的坐标。散点图画出来以后能看到一条从左到右弯曲下降的Pareto前沿曲线——这就是标准的理想结果。如果手头是自己的业务问题可以继承Problem类自定义问题from pymoo.core.problem import Problem class MyProblem(Problem): def __init__(self): # n_var决策变量个数n_obj目标个数n_ieq_constr不等式约束个数 super().__init__(n_var2, n_obj2, n_ieq_constr1, xl0, xu1) def _evaluate(self, X, out, *args, **kwargs): f1 X[:, 0] f2 (1 10 * X[:, 1]) * (1 - (X[:, 0] / (1 10 * X[:, 1])) ** 2) g X[:, 0] X[:, 1] - 0.5 out[F] np.column_stack([f1, f2]) out[G] g.reshape(-1, 1) # pymoo默认约束为 0 problem MyProblem() algorithm NSGA2(pop_size50) res minimize(problem, algorithm, (n_gen, 100), seed42)注意pymoo里的不等式约束默认形式是G 0所以g x0 x1 - 0.5只有小于等于0的个体才可行。能把这段代码跑通后面替换成自己的目标函数就只剩体力活了。第一次跑业务问题时强烈建议先把目标函数和约束单独在代码外验证一遍正确性再丢进算法里否则算法跑出来的结果出了问题你根本分不清是算法毛病还是目标函数写错。4. 评价指标与参数调优如何判断算法到底好不好4.1 三个常用评价指标GD、IGD、HV以及它们的适用边界算法跑完了怎么量化地说它好还是不好这是多目标优化里特别容易被忽略的一环。我在项目里常用的指标是三个GD、IGD和HV。GD世代距离衡量的是解集到真实Pareto前沿的平均最短距离它只看收敛性不看多样性。一个解集哪怕全挤在同一个点只要这个点离前沿近GD就很小。IGD反世代距离反过来从真实Pareto前沿上的每个点出发计算它们到解集最近点的距离再取平均。正因为是从前沿反过来找解集它同时惩罚两件事解集离前沿太远距离大以及前沿某个区域没有被解集覆盖找不到近点距离也大。也就是说IGD对收敛和多样性都敏感是评测时很常用的指标。HV超体积指标和前面两个不一样它不需要知道真实前沿。做法是在目标空间里取一个参考点通常是每个目标方向上一组比当前所有解都差的坐标然后计算解集在目标空间里覆盖的超体积。这个指标越大说明解集在目标空间里拓的张越大收敛和多样性都好。也正因为HV不依赖真实前沿实际业务里它是我最常用的指标——很多情况下你根本不知道真实前沿长什么样去网上找一个参考前沿来算IGD会引入额外误差直接用HV反而干净。提示在标准测试问题ZDT、DTLZ系列上做对比时IGD和HV都可以用因为参考前沿已知但在自己的业务问题上直接用HV更稳妥。4.2 参数怎么调种群、代数、交叉变异概率的经验值参数调优这块我先把我在多数场景下当默认值的配置列出来参数常用范围我常用的默认值调整方向说明种群大小50-200100问题越复杂、目标越多越需要大种群但评估成本高时反而要压缩迭代代数100-500200以HV收敛曲线为准曲线平缓再停交叉概率0.8-0.90.9太低会导致后代与父代差异过小、探索不足变异概率1/n 附近1/nn是决策变量个数太大接近随机搜索SBX eta_c15-3020越大子代越像父代越小越激进多项式变异 eta_m15-2020控制变异后个体偏离父代的幅度这里稍微解释几个容易踩的。变异概率很多教程会直接给一个0.01但更好的起点是1/nn是决策变量个数。因为变异概率的本质含义是平均每个个体有多少个基因位会被扰动如果n有30个变量变异概率0.01意味着平均每个个体只有0.3个变量发生变异整体实质上退化成纯交叉在搜索。反过来变异概率设到0.5以上种群就变成随机漫游了。SBX的eta_c控制的是子代围绕父代的分散程度eta_c大子代和父代长得像收敛稳但探索慢eta_c小探索强但容易震荡。实操调参我建议不要一来就全参数网格搜索。先固定种群和代数跑一组实验看HV曲线观察在什么代数HV基本不动了再考虑加代数还是修正变异概率。多数情况下HV不再增长时就是该停的点了继续加代数只是浪费算力。4.3 多目标算法对比实验的正确姿势很多人做对比实验的时候每个算法只跑一次就下结论这是非常危险的。进化算法有随机性种子换一下结果可能就差出一大截。正确的做法至少应该做到每个算法用多个随机种子独立运行一般至少10次追求统计学严谨可以到30次每次运行保持同样的种群大小、迭代预算、评估预算否则叫不公平对比计算评价指标的均值和标准差不要只看均值不看方差有条件的话做非参数显著性检验比如Wilcoxon秩和检验直接比均值容易误判记录实验配置的全套参数方便复现和后期回溯。这里有个容易被忽视的细节不同算法的种群大小和交叉变异算子参数应该各自调优到合理水平后再对比而不是全部共用同一组参数然后说A算法比B算法强。后者比的是参数设置不是算法本身。5. 实战踩坑记录多目标优化落地中的四个真实问题5.1 坑1目标函数太贵进化几十代就跑不动了理论算法默认评估是廉价的但现实世界不是。我遇到过一次用仿真模拟评估排产方案单次评估要几十秒按100个个体跑200代算要2万次评估等于跑差不多10天这在项目周期里完全不可接受。这种情况下我有三招按性价比排序并行评估pymoo里可以并行计算种群个体开了多进程后评估耗时能直接除以CPU核数。降采样仿真评估从全量仿真降成少量采样再近似损失一点精度换一个数量级的提速。代理模型用高斯过程或神经网络先拟合目标函数进化过程中大部分评估走代理模型每隔几代用真实仿真校正一次。这个路子效果好但工程量大适合目标函数特别昂贵且后续要反复优化的场景。这三招里并行评估和降采样通常一两周内就能落地代理模型需要先攒数据、训模型我一般留给长期项目用。5.2 坑2约束处理不当种群一直在不可行域里震荡另一个高频踩坑点来自约束。之前在某次排产优化里产量约束是硬约束我用罚函数处理罚值设得偏大结果种群倒是很快全跑到可行域里了但目标函数值停在很差的区域不敢动调小一点大量个体又回到不可行区域整个种群震荡得厉害。说白了罚函数这个参数就是一把双刃剑。后来换成了修复法每生成一个新个体就检查产量是否满足约束不满足就把工序往后挪直到满足。代价只是多写一个修复函数但之后整个演化过程就顺了很多种群也稳定HV曲线也明显更平滑。这个教训直接固化成了3.3里那套编码规避 修复 罚函数的优先级。5.3 坑3只看IGD不看HV差点把好算法给否了还有一次调参我同时用IGD和HV观察实验效果。IGD的数值一直下不来我以为算法退化差点把一整套配置推翻重来。后来仔细排查才发现我估算的那个真实前沿本身质量不高——它是用另一套快速解法粗跑的前沿区域覆盖不全。而HV那边其实一直稳定上涨说明算法表现并不差。这件事给我一个很深的印象指标本身也是一个需要审计的对象。用IGD的前提是参考前沿可信如果参考前沿来源不明或精度不够那IGD值的波动根本反映不了算法好坏。从此之后我业务项目默认看HVIGD只在标准测试问题上做论文式对比才用。5.4 效率技巧缓存、早停、先小后大最后分享几个提升开发效率的小习惯缓存重复评估进化算法在后期有大量重复或者接近重复的个体把算过的目标值按决策变量的哈希存一下再遇到同样的解直接查表。搜索空间不大或者约束较强时效果立竿见影。早停策略不用死磕固定代数连续20代HV增长不足0.1%就提前结束能省下不少算力。先小后大正式跑大种群之前先用小种群比如pop_size30把代码、约束、指标全链路验证一遍。小规模下发现问题的时间和成本都低一个数量级确认没问题再上正式规模。多目标优化算法用到现在我最大的体会是它的价值不在于自动给出一个最佳答案而是给你一张完整的选择地图。当我把Pareto前沿画出来摆在业务方面前告诉对方想压缩工期就得接受更高的能耗决策反而好做很多远比在会议室里争论权重0.6还是0.4更高效。最后分享一个小技巧多目标优化的结果拿到手一定要先做可视化把每个解的关键业务指标列进一张可筛选的表格主动过滤掉那些明显不可能被接受的极端解再交给决策者能省掉不少扯皮的工夫。这套流程走通之后多目标优化在我这里就不再是个理论概念而是一个真正能落地的决策工具了。
阅读完成 · 觉得有帮助？
实战：从原理到代码实现)
