简介这份Python实现的NSGA-II多目标优化算法资源包面向算法研究者与相关方向开发者提供可直接运行的Jupyter代码示例用于理解非支配排序遗传算法在多目标问题上的求解流程。压缩包共10个文件以ipynb交互式笔记本为主另有py脚本、PDF讲解文档及txt使用说明整体大小仅518KB轻量易获取。已有94人浏览学习该资源适合初探多目标优化的读者。内容围绕NSGA-II核心流程展开涵盖初始种群生成、分层排序、密度评估、精英保留策略、遗传算子应用与收敛判定等关键环节讲解从问题建模到迭代执行的完整路径。所附帕累托最优解选择方法的PDF说明配合Python脚本与交互式笔记可帮助读者在掌握算法内在机理的同时完成结果提取与多维可视化分析。1. 多目标优化不是找“一个答案”而是找一整片候选解同时追上两个目标往往不是炒菜加点盐的事。你在做排班调度时想同时最小化人力成本、最大化订单按时完成率做选型时想同时压低采购价、提升可靠性与交付速度。任何一个目标单独看都有解但放在一起解就不再是“一个点”而是一整片两两互有胜负的方案。NSGA-II就是帮你把这整片候选解找出来的算法它的中文全称是非支配排序遗传算法第二代眼下仍然是最常用的多目标优化基线之一。这篇文章会在Jupyter里用Python手写一遍NSGA-II把非支配排序、拥挤度距离、锦标赛选择、SBX交叉、多项式变异和精英保留全部落地成可运行的代码再用ZDT测试集验证实现没写错。适合正要解决多目标工程问题、又不想把现成库当黑匣子用的开发者阅读跟着代码走一遍之后换到自己的问题上很容易。2. NSGA-II守住多样性和收敛性的三个核心机制2.1 非支配排序先解决“谁比谁好”多目标优化里最棘手的是没有一个全局统一的“好”。解A成本低但完成率低解B完成率高但成本高到底谁好算法里用的是帕累托支配关系如果A在所有目标上都不差于B并且至少在一个目标上严格优于B就说A支配B。A被支配就说明B至少有理由替代它。按这个规则逐对比较整个种群被分成若干层第一层是所有不被任何解支配的个体它们构成当前的非支配前沿也就是你最终想要的那片候选解第二层是去掉第一层之后剩下的不被支配的个体以此类推。为什么不用加权求和把多个目标捏成一个权重一旦定死凹形成本曲面上会有一些本来值得保留的中间方案被丢掉而且权重本身就是主观选择业务上常常说不清楚。NSGA-II的做法更聪明先按支配关系分层层数越小越好再在同层里用拥挤度区分优劣保收敛又保分布。这部分的复杂度是 O(MN²)M是目标个数N是种群大小。二维三维目标用双循环直接算就是我没有为它做太多优化因为教学中可读性优先。等你真把种群做到500以上、目标做到5个以上再考虑用基于角度或网格的近似方法也不迟。2.2 拥挤度距离防止所有解挤在一个角落纯按支配关系分层有个致命问题第一前沿上的解可以全部聚在目标空间的很小的一个区域里支配关系却认为它们同样优秀。用户拿到这种结果会崩溃因为几十个候选解实际上没有差别。NSGA-II用拥挤度距离解决这个问题。拥挤度的计算思路是对某个前沿上的所有个体按每一个目标轴分别排序两端点的拥挤度直接置为无穷大中点的拥挤度累加它在当前目标方向上相邻两个点的归一化距离。所有目标都累加完拥挤度越大说明这个解周围的同类越少值得优先保留拥挤度小说明它身边已经挤满了人淘汰它不影响多样性。精英保留阶段执行“先比层数层数相同比拥挤度”的规则算法在收敛和分布之间由此找到平衡。实现时要注意拥挤度归一化用的是每个目标自己的最大值和最小值不能拿两个量纲差很大的目标直接算绝对值距离否则数值小的目标在拥挤度里完全失去发言权。这一点在第五章专门展开放进避坑清单。2.3 精英保留父代子代合并后再择优最早一代遗传算法通常是父代生成子代后就整体替换这样导致一个问题好不容易出现的好解可能因为交叉变异运气差下一代里就断了。NSGA-II用的是加号选择不是逗号选择。每轮迭代先生成规模为N的子代然后把父代和子代合并成一个2N的池子在这个池里做一次非支配排序和拥挤度分配按前文说的规则挑出N个个体进入下一代。这个机制意味着上一代里质量最高的解无论如何都不会丢除非它们被同样优秀且更分散的解挤掉。工程实践中精英保留带来的收敛稳定性比调大变异概率有用得多。我见过的多数实现跑偏问题都不是出在算法框架上而是出在细节比如合并之后忘了更新拥挤度数组、截断个体时下标错位、或者排序方向写反。先理解这三件事再进入代码后面就不会手忙脚乱。3. 在Jupyter里从零实现NSGA-II完整代码与参数说明3.1 先定义目标函数用ZDT1做试验场我习惯先拿带已知最优解集的测试函数验证算法再换到自己的问题上否则你根本分不清代码写错了还是问题本身太难。ZDT1是个经典双目标测试问题决策变量30个真实前沿是 f2 1 - sqrt(f1) 这条曲线拿来当第一个实验对象非常合适。import numpy as np import matplotlib.pyplot as plt def zdt1(x): # x 是决策变量向量长度 n_var n len(x) f1 x[0] # g 函数负责制造目标间的冲突 g 1 9 * np.sum(x[1:]) / (n - 1) f2 g * (1 - np.sqrt(f1 / g)) return [f1, f2]这个函数设计的巧妙之处在于f1只由第一个决策变量决定f2受其余所有变量共同影响。最小化两个目标时x[0]越小f1越小但g变化时f2也会跟着变两个目标之间产生了竞争关系于是需要NSGA-II去找到帕累托前沿。真正的ZDT1问题里所有变量范围是 [0,1]所以后续交叉变异的边界都先按这个写。3.2 非支配排序与拥挤度距离NSGA-II的分层核心非支配排序我按经典写法实现维护两个信息每个个体被多少个其他个体支配以及它支配了哪些个体。先找出不被任何个体支配的放入第一前沿然后对被第一前沿支配的个体把计数减一减到零就进入第二前沿循环往复。def fast_non_dominated_sort(fitness): # fitness: (N, M) 二维数组N 个个体M 个目标值 n fitness.shape[0] dominated_count np.zeros(n, dtypeint) dominated_set [[] for _ in range(n)] fronts [[]] for i in range(n): for j in range(n): if i j: continue # 判断 i 是否支配 j if all(fitness[i] fitness[j]) and any(fitness[i] fitness[j]): dominated_set[i].append(j) elif all(fitness[j] fitness[i]) and any(fitness[j] fitness[i]): dominated_count[i] 1 if dominated_count[i] 0: fronts[0].append(i) k 0 while fronts[k]: next_front [] for i in fronts[k]: for j in dominated_set[i]: dominated_count[j] - 1 if dominated_count[j] 0: next_front.append(j) k 1 fronts.append(next_front) return fronts[:-1]双循环逐对比较是这里时间复杂度的主要来源N100时完全可接受N500时每代排序会明显变慢。这段逻辑里最需要注意的是判定条件里“所有目标不差”和“至少一个目标更优”必须同时成立只写小于号会丢解只写小于等于会把完全相同的解也误判成互相支配。拥挤度距离按目标轴逐维处理端点给无限大中间点累加相邻归一化距离。def crowding_distance(fitness, front): # front 是前沿个体的索引列表 dist np.zeros(len(front)) m fitness.shape[1] for obj in range(m): front_sorted sorted(front, keylambda idx: fitness[idx, obj]) dist[front_sorted[0]] np.inf dist[front_sorted[-1]] np.inf f_min fitness[front_sorted[0], obj] f_max fitness[front_sorted[-1], obj] if f_max - f_min 1e-12: continue for i in range(1, len(front_sorted) - 1): prev_idx front_sorted[i - 1] next_idx front_sorted[i 1] dist[front_sorted[i]] (fitness[next_idx, obj] - fitness[prev_idx, obj]) / (f_max - f_min) return dist参数层面值得说的是归一化如果不除以 f_max - f_min量纲大的目标会主导拥挤度导致种群在另一个目标方向上过度聚集。inf给端点是为了保护前沿两端的候选解不被轻易淘汰这个设计在做截断选择时特别关键否则每次迭代两端点都容易被牺牲掉前沿会逐渐缩水。3.3 锦标赛选择、SBX交叉与多项式变异种群进化的驱动力来自选择与遗传算子。选择我采用二元锦标赛随机抽两个个体先比非支配层数层数小的胜出层数相同则比拥挤度拥挤度大的留下。这个规则和精英保留的判断口径完全一致保证选择压力始终指向“更优且更分散”的个体。def tournament_selection(rank, crowd_dist, k2): n len(rank) selected [] for _ in range(n): competitors np.random.choice(n, k, replaceFalse) best competitors[0] for idx in competitors[1:]: if rank[idx] rank[best]: best idx elif rank[idx] rank[best] and crowd_dist[idx] crowd_dist[best]: best idx selected.append(best) return selectedk2是标准配置k增大选择压力变强种群多样性下降k1就退化成随机选择收敛很慢。这里返回的是索引数组后面主循环拿它去父代种群取个体。交叉我采用模拟二进制交叉SBX它专为实数编码设计能让两个父代在中点附近产生两个对称的子代配合分布指数eta_c控制子代偏离父代的程度。变异用多项式变异在个体周围做小范围扰动。def sbx_crossover(p1, p2, eta_c20, prob_c0.9, lb0.0, ub1.0): n len(p1) c1 p1.copy() c2 p2.copy() if np.random.rand() prob_c: return c1, c2 for i in range(n): if np.random.rand() 0.5: if abs(p1[i] - p2[i]) 1e-12: continue x1, x2 min(p1[i], p2[i]), max(p1[i], p2[i]) u np.random.rand() if u 0.5: beta (2 * u) ** (1 / (eta_c 1)) else: beta (1 / (2 * (1 - u))) ** (1 / (eta_c 1)) c1[i] np.clip(0.5 * ((x1 x2) - beta * (x2 - x1)), lb, ub) c2[i] np.clip(0.5 * ((x1 x2) beta * (x2 - x1)), lb, ub) return c1, c2 def polynomial_mutation(child, eta_m20, prob_m0.1, lb0.0, ub1.0): for i in range(len(child)): if np.random.rand() prob_m: u np.random.rand() if u 0.5: delta (2 * u) ** (1 / (eta_m 1)) - 1 else: delta 1 - (2 * (1 - u)) ** (1 / (eta_m 1)) child[i] np.clip(child[i] delta, lb, ub) return childeta_c越大子代越贴近父代收敛精细但探索性差eta_c太小则子代分布过于激进。常用区间是 [10, 30]。eta_m同理常用[15, 25]。变异概率prob_m一般设0.1交叉概率prob_c设0.9这两个值的直觉是交叉负责大范围重组变异负责局部微调前者频率高、后者力度小。3.4 主循环父代子代合并后的精英保留所有零件齐全之后主循环就是把这些步骤按顺序串起来初始化种群→计算目标值→非支配排序拥挤度→进入迭代每一代先锦标赛选择出父代索引交叉变异生成子代再与父代合并成2N的池子重新排序与分配拥挤度截断保留前N个个体进入下一代。def nsga2(problem, n_var30, pop_size100, generations250, lb0.0, ub1.0, eta_c20, prob_c0.9, eta_m20, prob_m0.1): # 初始化种群 population np.random.uniform(lb, ub, (pop_size, n_var)) fitness np.array([problem(ind) for ind in population]) fronts fast_non_dominated_sort(fitness) rank np.zeros(pop_size, dtypeint) crowd np.zeros(pop_size) for f_idx, front in enumerate(fronts): cd crowding_distance(fitness, front) for i, idx in enumerate(front): rank[idx] f_idx crowd[idx] cd[i] for gen in range(generations): # 选择、交叉、变异生成子代 parent_idx tournament_selection(rank, crowd, k2) parents population[parent_idx] offspring [] for i in range(0, pop_size, 2): p1, p2 parents[i], parents[i 1] c1, c2 sbx_crossover(p1, p2, eta_c, prob_c, lb, ub) offspring.append(polynomial_mutation(c1, eta_m, prob_m, lb, ub)) offspring.append(polynomial_mutation(c2, eta_m, prob_m, lb, ub)) offspring np.array(offspring[:pop_size]) # 合并父代与子代精英保留 combined_pop np.vstack([population, offspring]) combined_fitness np.array([problem(ind) for ind in combined_pop]) fronts fast_non_dominated_sort(combined_fitness) crowd np.zeros(2 * pop_size) new_pop [] for front in fronts: cd_front crowding_distance(combined_fitness, front) for i, idx in enumerate(front): crowd[idx] cd_front[i] if len(new_pop) len(front) pop_size: new_pop.extend(front) else: remaining pop_size - len(new_pop) front_sorted sorted(front, keylambda idx: crowd[idx], reverseTrue) new_pop.extend(front_sorted[:remaining]) break population combined_pop[new_pop] fitness combined_fitness[new_pop] rank np.array([new_pop.index(i) for i in range(pop_size)]) # 占位后续统一更新 # 重新计算 rank确保与 population 对应 fronts fast_non_dominated_sort(fitness) rank np.zeros(pop_size, dtypeint) for f_idx, front in enumerate(fronts): for idx in front: rank[idx] f_idx return population, fitness, fronts, rank调用方式很简单跑250代ZDT1在普通笔记本上大概几十秒每一代都在屏幕上能看到结果在逐步逼近那条理论曲线。np.random.seed(42) pop, fitness, fronts, rank nsga2(zdt1, n_var30, pop_size100, generations250) pf_idx fronts[0] pf fitness[pf_idx] plt.scatter(pf[:, 0], pf[:, 1], s18, csteelblue) plt.xlabel(f1) plt.ylabel(f2) plt.show()主循环里容易忽略的一步是截断后个体的rank和crowd必须基于新种群重新计算。我在代码里在每代结束时重新调用了一次快速非支配排序就是为了防止下一轮锦标赛选择用旧层数坑人。代码写完后把整个notebook保存一份建议再导出成.py留档这个动作在Jupyter里只需一行命令jupyter nbconvert --to script 你的文件名.ipynb以后再复用就不用把每个cell重新复制一遍。4. 用ZDT测试集验证理论前沿画出来算法对不对一目了然4.1 ZDT1 / ZDT2 / ZDT3三种典型前沿形态只跑ZDT1说明不了问题因为它太“温和”前沿是一条光滑凸曲线。我一般同时测ZDT2和ZDT3ZDT2前沿是凹的可以检验算法是不是只擅长凸问题ZDT3的前沿是不连续断开的几段用来检验种群分布能力。def zdt2(x): n len(x) f1 x[0] g 1 9 * np.sum(x[1:]) / (n - 1) f2 g * (1 - (f1 / g) ** 2) return [f1, f2] def zdt3(x): n len(x) f1 x[0] g 1 9 * np.sum(x[1:]) / (n - 1) f2 g * (1 - np.sqrt(f1 / g) - (f1 / g) * np.sin(10 * np.pi * f1)) return [f1, f2]三个函数的结构几乎一样差异只在f2的构造公式。ZDT2的凹前沿对算法是压力测试因为凹区域里解与解之间的支配关系更复杂ZDT3的间断前沿考验的是拥挤度机制能否把个体分布到每一段上去。把问题名作为参数传进画图函数就能同时画三个实验的散点和理论前沿。4.2 生成Pareto前沿图并与理论前沿对比验证的核心是把算法找到的点叠加到理论前沿上肉眼观察二者是否贴合。贴合程度高说明收敛没问题点在曲线上分布是否均匀说明多样性有没有做好。def plot_result(fitness, fronts, problem_name): pf_idx fronts[0] pf fitness[pf_idx] plt.figure(figsize(6, 5)) plt.scatter(pf[:, 0], pf[:, 1], s16, csteelblue, labelNSGA-II) f1 np.linspace(0, 1, 300) if problem_name ZDT1: f2 1 - np.sqrt(f1) elif problem_name ZDT2: f2 1 - f1 ** 2 elif problem_name ZDT3: f2 1 - np.sqrt(f1) - f1 * np.sin(10 * np.pi * f1) valid f2 0 f1, f2 f1[valid], f2[valid] plt.plot(f1, f2, r--, linewidth1.5, labelTrue PF) plt.xlabel(f1) plt.ylabel(f2) plt.legend() plt.title(f{problem_name} Pareto Front) plt.show() np.random.seed(42) pop, fitness, fronts, rank nsga2(zdt2, n_var30, pop_size100, generations250) plot_result(fitness, fronts, ZDT2)跑ZDT3时如果发现有些前沿段的端点处缺个体不用急着改代码先检查是不是变异概率太低导致探索能力不足把prob_m从0.1提到0.2通常就能改善。判断标准不是“点都贴线”而是“每一段上都有点且点的间隔大致均匀”。4.3 参数对结果的影响用对比实验代替玄学调参参数调优时我更喜欢成组对比而不是一个一个试。固定随机种子后只改一个参数跑同一问题记录前沿形态。下面这张表是我的常用参照不同机器和问题会有出入但趋势是稳定的。参数组合设置通常观察到的现象默认eta_c20, eta_m20, prob_m0.1前沿贴合理论曲线分布均匀变异概率过高prob_m0.5收敛变慢前沿出现明显散点交叉指数过小eta_c2子代过度发散前沿边缘有毛刺种群过小pop_size30前沿点过少中间出现空腔代数过短generations50前沿右端明显短缺未收敛彻底把这个实验放在同一个notebook里连续跑每次只改一处记录到表格。别小看这个步骤很多参数组合只在特定问题下成立你不做对比实验换到自己工程问题时大概率会翻车。5. NSGA-II避坑指南五个常见的翻车现场5.1 交叉后变量越界前沿整体塌缩现象跑了50代以后种群的所有个体在部分维度上挤在边界值前沿不再是平滑曲线而是一条边界上的折线。原因SBX的beta展开会让子代跑出决策变量边界clip虽然把数值压回界内但如果父代本身已经接近边界反复clip会让这些维度锁死在边界上失去后续变化能力。解决交叉变异后统一按lb和ub重新clip同时每轮检查一下种群在各维度上的方差如果某一维方差接近零说明这个维度已经退化需要针对性地恢复变异。ZDT4这类原始变量范围不是[0,1]的问题我会在目标函数内部做变量映射而不是把整个算法都改成支持范围数组。5.2 拥挤度排序方向写反多样性反而恶化现象前沿上的点密集成两三个团中间大片空白拥挤度机制完全失效。原因截断阶段递归排序时把reverseTrue写成了默认升序预留的个体全是拥挤度最小的那些彼此挤在一起的解反而被保留下来。解决翻到截断代码处检查front_sorted的排序参数保留层内个体时一定要按拥挤度降序。这个小错误非常隐蔽因为代码不报错结果就是图越来越丑。我在这个坑上浪费过一整个下午最后是逐行对比参考实现才发现的。5.3 子代生成时没有深拷贝父代被原地修改现象每一代的父代和子代看起来几乎完全一样收敛速度异常快但结果质量很差多次运行之间波动极大。原因生成子代时写了child parent而不是child parent.copy()SBX和变异函数里对child的修改同时改写了父代相当于这一代什么都没变化。解决所有从父代构造子代的地方一律先.copy()。二维数组做切片后变异也一样先把切片独立出来再动手。这是遗传算法实现里最容易踩的血泪坑几乎每个初学者都会中一次招。5.4 随机种子不固定调参调出幻觉现象同一组参数昨天跑出来前沿完美今天跑出来缺了一半你以为是系统负载影响了Jupyter实际上每代都在掷骰子。原因种群初始化和每一轮的随机选择都没有固定不同运行之间差异天然存在小种群时尤其明显。解决对比实验前固定np.random.seed(42)每一个参数配置跑10次取中位数结果再下结论。我自己的习惯是写一个seeds [0, 1, 2]的循环三个种子都输出任何一个明显异常都要回去查代码而不是换一个种子让结果“变好看”。5.5 目标值量纲差距大拥挤度被大目标垄断现象两个目标数量级差100倍以上时前沿在数值小的目标方向上挤压成一排多样性明显偏科。原因拥挤度归一化虽然写了但如果用的是sigmoid、对数缩放或绝对值方案量纲问题依然存在或者干脆忘了除以 f_max - f_min。解决拥挤度里每个目标方向各自归一化代码里已经实现。换到工程问题上时先打印每个目标的最小最大值确认量级再决定是否做对数变换。记住一句话拥挤度衡量的永远是“相对稀疏程度”不是绝对距离。6. 进阶验证IGD指标量化效果并把约束加进工程问题6.1 IGD用一个数字代替肉眼判断看前沿图能发现明显问题但细微的收敛差距肉眼看不出来。我强烈建议在notebook里加一个倒转世代距离指标IGD在真实前沿上均匀采很多参考点对每个参考点找算法解里离它最近的那个求这些最近距离的平均值。IGD越小越好0表示算法解完全覆盖了理论前沿。def igd(algo_front, true_front): # algo_front: 算法找到的 (N, M) 数组 # true_front: 理论前沿采样点 (P, M) 数组 dists [] for tp in true_front: d np.min(np.sqrt(np.sum((algo_front - tp) ** 2, axis1))) dists.append(d) return np.mean(dists) f1_true np.linspace(0, 1, 500) f2_true 1 - np.sqrt(f1_true) true_front np.column_stack([f1_true, f2_true]) print(IGD , igd(pf, true_front))用IGD做参数对比比看图客观得多默认参数跑出IGD约0.005左右时小参数变化引起的差别很可能只有0.001量级肉眼完全看不出但数字能告诉你谁更接近理论前沿。6.2 罚函数给NSGA-II加上工程约束真实工程问题几乎都带约束比如成本不能超过预算、温度必须低于某个阈值。常见做法是把约束违反量放大后加到每个目标值上违反越严重个体越差自然会被非支配排序淘汰。def constrained_problem(x): f1 x[0] g 1 9 * np.sum(x[1:]) / (len(x) - 1) f2 g * (1 - np.sqrt(f1 / g)) # 约束x[0] 不能超过 0.4违反量乘以缩放系数 violation max(0, x[0] - 0.4) * 10.0 return [f1 violation, f2 violation]惩罚系数10.0只是个起点工程上要按目标量级调整让“违反约束”带来的目标是真实目标的2到5倍约束才有足够淘汰压力。系数太小约束形同虚设太大则会让违反个体瞬间被排除反而丢失边界附近的可行解。我的习惯是拿到一个新工程问题先跑三个随机种子再算IGD观察稳定性确认算法本身没毛病才去调参数。这套顺序帮我省下大量无效尝试也把很多“玄学调参”变成了可复现的实验记录。希望帮到你。本文还有配套的精品资源点击获取