简介基于 NSGA-II 算法的插板式编码多目标优化调度模型是武汉理工大学2020年数学建模暑期培训的完整课题成果。该资源聚焦生产调度中的多目标优化难题面向数学建模参赛者、算法学习者与运筹优化从业者系统讲解非支配排序、拥挤距离、精英保留策略等 NSGA-II 核心机制并通过插板式编码将任务执行时长与时间窗口约束结构化表达便于开展交叉与变异操作。压缩包约 12.33MB包含论文全文与配套实现代码读者可对照论文深入理解算法设计思路、模型构建流程和代码实现细节。目前已有 72 人学习浏览适合希望在真实课题中掌握多目标优化调度方法的读者对提升数学建模能力、解决实际排产问题具有直接参考价值。1. 从固定编码到插板式编码调度问题为什么需要可变长度染色体多目标调度里最容易被低估的问题不是算法而是染色体怎么编码。工序数量固定时标准作业车间编码一串工序编号按先后展开很好用一旦每个工件的加工工序数可变固定长度染色体要么留出一堆空位要么强迫所有个体等长——解空间里真实可行解只占一小区块NSGA-II 的大量搜索都浪费在无效维度上。插板式编码的思路很直接染色体由两部分组成前段是工件工序的有序序列后段是一组升序的插板位置插板把序列切成若干段批次每个批次对应一段连续加工。板位一动调度结构就变工序个数再多也能在编码长度不变的前提下切出适配的结果。下面按编码设计、模型建立、NSGA-II 机制、最小实现、参数排错这条线把整套做法讲完。2. 插板式编码的染色体结构与调度目标设定2.1 染色体由工序序列和插板位置双段组成设工件集合为 J工件 j 包含 n_j 道工序总工序数 N Σ n_j。染色体的前半段是长度 N 的整数数组元素为工件 ID工件 j 恰好出现 n_j 次称为工序序列后半段是长度 k 的升序整数数组k 在 [1, N-1] 之间由初始化时随机决定取值范围是 (1, N)称为插板位置。举例两个工件各有 4 道工序N 8一条染色体可以是[1, 1, 1, 1, 2, 2, 2, 2] [3, 6]插板位置 3 和 6 把工序序列切成三段。第 1 段是位置 1~3工件 1 的前 3 道第 2 段是位置 4~6工件 1 的第 4 道加工件 2 的前 2 道第 3 段是位置 7~8工件 2 的后 2 道。插板式编码与固定长度编码的核心差别在于固定长度编码下工件 ID 的重复次数和排列位置都必须预先定死而插板式编码把“某个工件安排在哪一段、每段放几道工序”这个问题交给了进化过程。板段短工序之间交错频繁板段长批量连续加工。插板位置的调整直接改变分批方式。2.2 解码规则板段约束下的工序排序解码规则需要把染色体翻译成一张可执行的时间表。常见做法是采用半主动解码同一个插板段内的工序严格按序列顺序加工段与段之间也按段序号先后执行同一工件的工序遵循工艺顺序约束。解码伪代码如下# job_seq: 工序序列cut_points: 升序插板位置 # ops[job] [(机器1, 时间1), (机器2, 时间2), ...] def decode(job_seq, cut_points, ops): prev_end [0] * num_jobs # 每个工件上一道工序结束时刻 avail [0] * num_machines # 每台机器的可用时刻 op_cnt [0] * num_jobs # 每个工件已排工序数 plan [] segment_start 0 for cut in cut_points [len(job_seq)]: for idx in range(segment_start, cut): job job_seq[idx] op op_cnt[job] op_cnt[job] 1 machine, time ops[job][op] start max(prev_end[job], avail[machine]) end start time prev_end[job] end avail[machine] end plan.append((job, op, machine, start, end)) segment_start cut return plan这段解码的关键在start max(prev_end[job], avail[machine])前一道工序没完成本道不能开工机器被占用也要排队。板段对加工顺序的约束通过遍历顺序体现段外的工序不会插入到段内。要注意两点。第一把工序追加到机器末尾是简化实现真实调度中同一个板段内可能出现更早可插入的空隙工程上会改成“查找最早可插入区间”的插入式解码代价是解码耗时上升但排程质量明显改善。第二插板位置必须严格升序变异或交叉后如果不检查可能产生重复位置或越界位置需要在代码里做修复。2.3 两个目标最大完工时间与最大机器负载基于解码结果两个目标函数设置如下最大完工时间makespan[ F_1 C_{\max} \max_{j \in J, k \in [1,n_j]} C_{jk} ]最大机器负载即所有机器中累计加工时间最长的一台[ F_2 M_{\max} \max_{m \in M} \sum_{j,k} t_{jk}^m \cdot x_{jk}^m ]其中 (x_{jk}^m) 表示工件 j 第 k 道工序是否在机器 m 上加工(t_{jk}^m) 是加工耗时。符号含义J, M工件集合、机器集合n_j工件 j 的工序总数C_{jk}工件 j 第 k 道工序的完工时刻t_{jk}^m工序 (j,k) 在机器 m 上的加工时间x_{jk}^m0-1 决策变量工序 (j,k) 是否在机 m 加工约束条件有三个层面同一工件的工序必须按工艺路线顺序执行同一台机器同一时刻只能加工一道工序每道工序只能在一台机器上加工。上述解码规则天然满足这三条约束这也是用解码方式处理调度问题比直接做约束优化的好处。2.4 为什么选 NSGA-II 而不是加权求和把两个目标加权成单目标的做法在这个模型下有两个直接问题权重系数需要先验知识且加权和无法找到非凸 Pareto 前沿上的解。NSGA-II 通过非支配排序同时维护一整条前沿面不依赖权重结果里直接得到一组权衡方案建模竞赛里可以画散点图向评委说明解的分布。这也是 NSGA-II 成为多目标调度最常见的基准算法的原因。3. NSGA-II 的筛选机制与针对插板式编码的算子适配3.1 快速非支配排序按支配关系分层NSGA-II 的第一步是对种群做快速非支配排序。个体 p 支配个体 q 的条件是p 的所有目标不劣于 q且至少有一个目标严格优于 q。排序过程维护两个量支配 p 的个体数 (n_p) 和被 p 支配的个体集合 (S_p)。def fast_nondominated_sort(P): S {p: [] for p in P} n {p: 0 for p in P} for p in P: for q in P: if dominates(p, q): S[p].append(q) elif dominates(q, p): n[p] 1 fronts [] current [p for p in P if n[p] 0] while current: fronts.append(current) next_front [] for p in current: for q in S[p]: n[q] - 1 if n[q] 0: next_front.append(q) current next_front return fronts逐层剥离的思路是先找出所有不被任何个体支配的个体作为第一层前沿再把这一层个体从支配关系中移除下一轮重复。算法复杂度是 (O(MN^2))M 是目标数N 是种群规模对两个目标的调度问题完全够用。需要注意dominates函数的比较逻辑两个目标都必须纳入判断只比较一个目标会破坏分层结果。3.2 拥挤度距离让前沿均匀铺开分层只区分优劣不区分同一层内个体的分布。拥挤度距离的作用是惩罚扎堆的解。对某一层前沿按每个目标分别排序边界个体的距离设为无穷大内部个体的距离取相邻两个体在该目标上的归一化差值之和[ d_i \sum_{m1}^{M} \frac{f_m(i1) - f_m(i-1)}{f_m^{\max} - f_m^{\min}} ]拥挤度计算在每一代要对两个目标各做一次排序加上前面的非支配排序这一代的额外开销约 (O(MN\log N))可以忽略。3.3 锦标赛选择与精英保留的比较规则选择父代时采用二元锦标赛随机取两个个体当前沿序号不同时选前沿序号小的同层时选拥挤度大的。这个规则保证进化压力偏向支配层高的解同时保留前沿内部的多样性。精英保留则是把父代和子代合并成 2N 大小的种群按前沿逐层填入下一代放不下的那一层按拥挤度从大到小取。阶段比较对象优先条件锦标赛选择随机两个个体前沿序号小者优先同层取拥挤度大者精英保留同一前沿内个体拥挤度大者优先存活精英保留跨层不同前沿前沿序号小者整体优先3.4 插板式编码下的交叉与变异算子通用 NSGA-II 的交叉变异针对二进制或实数编码设计用在插板式编码上必须改造。工序序列段要保证每个工件 ID 出现次数恰好等于其工序数普通两点交叉会破坏这个约束需要采用顺序交叉子代从一个父代继承部分位置的工件剩余位置按另一个父代的工件顺序填充。插板位置段相对独立可以采用掩码交叉交叉后对子代插板做排序去重和边界修复。变异分两路工序序列段随机交换两个不同工件的工序位置插板段以一定概率把某个插板位置左右移动一个随机量或者重新采样一个新位置。插板变异的效果是改变分批边界工序交换改变的是段内细节两者负责的搜索粒度不同配合使用才能兼顾全局和局部搜索。4. 用 Python 复现插板式编码与 NSGA-II 的最小调度器4.1 个体表示、初始化与解码实现完整代码里把上面的 decode 函数落成可直接运行的版本。为了演示假设 3 台机器、3 个工件每个工件有 4 道工序工序的可选机器和耗时用字典表达。import random random.seed(42) num_jobs, num_machines 3, 3 ops { 0: [(0, 5), (1, 4), (2, 3)], 1: [(2, 4), (0, 3), (1, 5)], 2: [(1, 2), (2, 6), (0, 4)], } # 每个工件工序数不足一批时循环取这里简化设计为固定 3 道 total_ops sum(len(v) for v in ops.values()) def init_individual(): job_seq [] for j, item in ops.items(): job_seq.extend([j] * len(item)) random.shuffle(job_seq) k random.randint(1, total_ops - 1) cut_points sorted(random.sample(range(1, total_ops), k)) return job_seq, cut_points def decode(job_seq, cut_points): prev_end [0] * num_jobs avail [0] * num_machines op_cnt [0] * num_jobs plan [] segment_start 0 for cut in cut_points [len(job_seq)]: for idx in range(segment_start, cut): job job_seq[idx] op op_cnt[job] op_cnt[job] 1 machine, time ops[job][op] start max(prev_end[job], avail[machine]) end start time prev_end[job] end avail[machine] end plan.append((job, op, machine, start, end)) segment_start cut return plan这里init_individual中随机打乱的是工件 ID 序列k随机决定插板数量sample保证升序且不重复。初始化阶段如果发现解码结果明显失衡某台机器一直空闲可以考虑限制插板数量在总工序数的 30%~70% 范围内。4.2 目标评估与快速非支配排序解码之后要算出每个个体的目标值。基于plan里的end字段最大完工时间是所有工序结束时刻的最大值机器负载则按机器维度累加工时。def evaluate(job_seq, cut_points): plan decode(job_seq, cut_points) makespan max(end for *_ , start, end in plan) load [0] * num_machines for job, op, machine, start, end in plan: load[machine] ops[job][op][0][1] # 简化取第一候选用时 return makespan, max(load)拥挤度计算按第 3 章公式实现注意两个目标量纲不同必须先按各自的最大最小值做归一化。边界个体的距离直接设为大数实际代码里常用float(inf)但在合并排序时要注意inf不能参与比较运算比较前要做替换或把边界值设为一个远大于所有距离的有限数。def crowding_distance(front, objs): dist {ind: 0.0 for ind in front} for m in range(2): front.sort(keylambda ind: objs[ind][m]) f_min, f_max objs[front[0]][m], objs[front[-1]][m] if f_max f_min: continue dist[front[0]] float(inf) dist[front[-1]] float(inf) for i in range(1, len(front) - 1): dist[front[i]] (objs[front[i 1]][m] - objs[front[i - 1]][m]) / (f_max - f_min) return distfront.sort用的是 Python 默认的元组比较这里个体用索引表示objs是目标值字典按第 m 维排序。目标值完全相同的两个个体会出现分母为零的情况代码里用f_max f_min跳过。4.3 主循环与参数配置主循环把前面所有模块串起来初始化种群 → 评估 → 非支配排序 → 锦标赛选择 → 交叉变异 → 合并父代子代 → 精英保留 → 输出前沿。def nsga2(pop_size100, generations200, crossover_rate0.9, mutation_rate0.1): population [init_individual() for _ in range(pop_size)] objs {i: evaluate(*population[i]) for i in range(pop_size)} for _ in range(generations): fronts fast_nondominated_sort(population, objs) distances {} for front in fronts: distances.update(crowding_distance(front, objs)) parents tournament_selection(population, objs, distances) offspring crossover_and_mutation(parents, crossover_rate, mutation_rate) combined population offspring combined_objs {i: evaluate(*combined[i]) for i in range(len(combined))} next_pop, next_objs elitist_selection(combined, combined_objs, pop_size) population, objs next_pop, next_objs return population, objs def tournament_selection(pop, objs, distances): pop_size len(pop) selected [] for _ in range(pop_size): a, b random.sample(range(pop_size), 2) if fronts[a] fronts[b] or (fronts[a] fronts[b] and distances[a] distances[b]): winner a else: winner b selected.append(pop[winner]) return selected注意这里fronts变量在主循环中被重新赋值锦标赛选择需要用到每个个体所在的前沿层号实际代码里要在非支配排序后保存front_of_individual字典供选择阶段使用。交叉和变异函数内部要处理插板段的修复逻辑保证升序和范围有效。参数推荐范围说明种群规模50 ~ 200工序总数大时取 150 以上进化代数100 ~ 500看前沿是否还动不动则提前停交叉概率0.8 ~ 0.95过低收敛慢过高破坏优秀插板结构变异概率0.05 ~ 0.2插板段变异建议单独调大锦标赛规模2增大到 3 会加快收敛但损失多样性generations建议先跑 100 代看前沿形状再决定是否续跑。收敛慢的常见原因是变异率偏低不是代数不够。5. 参数整定与收敛性排错的三类信号5.1 前沿形状检查两个目标是否真正冲突输出前沿后第一件事是画散点图。横轴 makespan纵轴最大机器负载正常情况下应该是一条从左上到右下的曲线或带状分布。如果散点图只有一两个点大概率是种群提前收敛或者插板位置初始化范围太窄。如果散点图呈竖直线条说明两个目标的冲突没有被有效探索需要检查机器分配逻辑工序的可选机器集合如果只有一台机器目标 F2 实际上是常数这时应该增加一个与排序相关的目标比如总提前/拖期惩罚。5.2 插板数量的分布漂移每一代统计种群中插板数量 k 的平均值和方差。初始化时k 是均匀随机取的进化几代后通常会向某个方向收敛。如果 k 过早集中到某个值说明插板数量上的多样性不足交叉和变异对插板段的破坏力度不够。调试方向如下表现象可能原因调整手段前沿只有少量点选择压力过强锦标赛规模降回 2交叉率降 0.1插板数量收敛过快插板段变异率过低单独提高插板变异的触发概率前沿连续多代不动变异步长太小插板位置 ±Δ 的 Δ 从 1 改为 3~5目标函数波动剧烈交叉率过高降到 0.8同时增大种群规模5.3 一种可执行的收敛验证技巧不依赖画图直接量化种群多样性每隔 20 代记录当前前沿中被支配层为 1 的个体在目标空间两两之间的平均欧氏距离。具体方法是取出最优前沿个体对每对个体的两个目标值做归一化求欧氏距离后取平均。这个平均距离连续 30 代下降幅度小于 1% 时说明前沿已经稳定可以终止进化。对应检查代码python -c import numpy as np d [pairwise_distance(front_i) for front_i in history] print(np.mean(np.diff(d[-30:]) / np.abs(d[-30:]))) 这段命令输出最后 30 代前沿平均距离的平均变化率。正值说明前沿还在扩展接近 0 或负值说明收敛。配合每代把 Pareto 前沿及插板数量分布导出到 CSV可以后续用表格软件直接分析。判断收敛后再做一次局部搜索把前沿中每个个体的插板位置逐一微调并检查目标值是否改善这是 NSGA-II 类算法避免过早停止的常用收尾手段。本文还有配套的精品资源点击获取 插板式编码结合NSGA-II的多目标调度算法详解
简介基于 NSGA-II 算法的插板式编码多目标优化调度模型是武汉理工大学2020年数学建模暑期培训的完整课题成果。该资源聚焦生产调度中的多目标优化难题面向数学建模参赛者、算法学习者与运筹优化从业者系统讲解非支配排序、拥挤距离、精英保留策略等 NSGA-II 核心机制并通过插板式编码将任务执行时长与时间窗口约束结构化表达便于开展交叉与变异操作。压缩包约 12.33MB包含论文全文与配套实现代码读者可对照论文深入理解算法设计思路、模型构建流程和代码实现细节。目前已有 72 人学习浏览适合希望在真实课题中掌握多目标优化调度方法的读者对提升数学建模能力、解决实际排产问题具有直接参考价值。1. 从固定编码到插板式编码调度问题为什么需要可变长度染色体多目标调度里最容易被低估的问题不是算法而是染色体怎么编码。工序数量固定时标准作业车间编码一串工序编号按先后展开很好用一旦每个工件的加工工序数可变固定长度染色体要么留出一堆空位要么强迫所有个体等长——解空间里真实可行解只占一小区块NSGA-II 的大量搜索都浪费在无效维度上。插板式编码的思路很直接染色体由两部分组成前段是工件工序的有序序列后段是一组升序的插板位置插板把序列切成若干段批次每个批次对应一段连续加工。板位一动调度结构就变工序个数再多也能在编码长度不变的前提下切出适配的结果。下面按编码设计、模型建立、NSGA-II 机制、最小实现、参数排错这条线把整套做法讲完。2. 插板式编码的染色体结构与调度目标设定2.1 染色体由工序序列和插板位置双段组成设工件集合为 J工件 j 包含 n_j 道工序总工序数 N Σ n_j。染色体的前半段是长度 N 的整数数组元素为工件 ID工件 j 恰好出现 n_j 次称为工序序列后半段是长度 k 的升序整数数组k 在 [1, N-1] 之间由初始化时随机决定取值范围是 (1, N)称为插板位置。举例两个工件各有 4 道工序N 8一条染色体可以是[1, 1, 1, 1, 2, 2, 2, 2] [3, 6]插板位置 3 和 6 把工序序列切成三段。第 1 段是位置 1~3工件 1 的前 3 道第 2 段是位置 4~6工件 1 的第 4 道加工件 2 的前 2 道第 3 段是位置 7~8工件 2 的后 2 道。插板式编码与固定长度编码的核心差别在于固定长度编码下工件 ID 的重复次数和排列位置都必须预先定死而插板式编码把“某个工件安排在哪一段、每段放几道工序”这个问题交给了进化过程。板段短工序之间交错频繁板段长批量连续加工。插板位置的调整直接改变分批方式。2.2 解码规则板段约束下的工序排序解码规则需要把染色体翻译成一张可执行的时间表。常见做法是采用半主动解码同一个插板段内的工序严格按序列顺序加工段与段之间也按段序号先后执行同一工件的工序遵循工艺顺序约束。解码伪代码如下# job_seq: 工序序列cut_points: 升序插板位置 # ops[job] [(机器1, 时间1), (机器2, 时间2), ...] def decode(job_seq, cut_points, ops): prev_end [0] * num_jobs # 每个工件上一道工序结束时刻 avail [0] * num_machines # 每台机器的可用时刻 op_cnt [0] * num_jobs # 每个工件已排工序数 plan [] segment_start 0 for cut in cut_points [len(job_seq)]: for idx in range(segment_start, cut): job job_seq[idx] op op_cnt[job] op_cnt[job] 1 machine, time ops[job][op] start max(prev_end[job], avail[machine]) end start time prev_end[job] end avail[machine] end plan.append((job, op, machine, start, end)) segment_start cut return plan这段解码的关键在start max(prev_end[job], avail[machine])前一道工序没完成本道不能开工机器被占用也要排队。板段对加工顺序的约束通过遍历顺序体现段外的工序不会插入到段内。要注意两点。第一把工序追加到机器末尾是简化实现真实调度中同一个板段内可能出现更早可插入的空隙工程上会改成“查找最早可插入区间”的插入式解码代价是解码耗时上升但排程质量明显改善。第二插板位置必须严格升序变异或交叉后如果不检查可能产生重复位置或越界位置需要在代码里做修复。2.3 两个目标最大完工时间与最大机器负载基于解码结果两个目标函数设置如下最大完工时间makespan[ F_1 C_{\max} \max_{j \in J, k \in [1,n_j]} C_{jk} ]最大机器负载即所有机器中累计加工时间最长的一台[ F_2 M_{\max} \max_{m \in M} \sum_{j,k} t_{jk}^m \cdot x_{jk}^m ]其中 (x_{jk}^m) 表示工件 j 第 k 道工序是否在机器 m 上加工(t_{jk}^m) 是加工耗时。符号含义J, M工件集合、机器集合n_j工件 j 的工序总数C_{jk}工件 j 第 k 道工序的完工时刻t_{jk}^m工序 (j,k) 在机器 m 上的加工时间x_{jk}^m0-1 决策变量工序 (j,k) 是否在机 m 加工约束条件有三个层面同一工件的工序必须按工艺路线顺序执行同一台机器同一时刻只能加工一道工序每道工序只能在一台机器上加工。上述解码规则天然满足这三条约束这也是用解码方式处理调度问题比直接做约束优化的好处。2.4 为什么选 NSGA-II 而不是加权求和把两个目标加权成单目标的做法在这个模型下有两个直接问题权重系数需要先验知识且加权和无法找到非凸 Pareto 前沿上的解。NSGA-II 通过非支配排序同时维护一整条前沿面不依赖权重结果里直接得到一组权衡方案建模竞赛里可以画散点图向评委说明解的分布。这也是 NSGA-II 成为多目标调度最常见的基准算法的原因。3. NSGA-II 的筛选机制与针对插板式编码的算子适配3.1 快速非支配排序按支配关系分层NSGA-II 的第一步是对种群做快速非支配排序。个体 p 支配个体 q 的条件是p 的所有目标不劣于 q且至少有一个目标严格优于 q。排序过程维护两个量支配 p 的个体数 (n_p) 和被 p 支配的个体集合 (S_p)。def fast_nondominated_sort(P): S {p: [] for p in P} n {p: 0 for p in P} for p in P: for q in P: if dominates(p, q): S[p].append(q) elif dominates(q, p): n[p] 1 fronts [] current [p for p in P if n[p] 0] while current: fronts.append(current) next_front [] for p in current: for q in S[p]: n[q] - 1 if n[q] 0: next_front.append(q) current next_front return fronts逐层剥离的思路是先找出所有不被任何个体支配的个体作为第一层前沿再把这一层个体从支配关系中移除下一轮重复。算法复杂度是 (O(MN^2))M 是目标数N 是种群规模对两个目标的调度问题完全够用。需要注意dominates函数的比较逻辑两个目标都必须纳入判断只比较一个目标会破坏分层结果。3.2 拥挤度距离让前沿均匀铺开分层只区分优劣不区分同一层内个体的分布。拥挤度距离的作用是惩罚扎堆的解。对某一层前沿按每个目标分别排序边界个体的距离设为无穷大内部个体的距离取相邻两个体在该目标上的归一化差值之和[ d_i \sum_{m1}^{M} \frac{f_m(i1) - f_m(i-1)}{f_m^{\max} - f_m^{\min}} ]拥挤度计算在每一代要对两个目标各做一次排序加上前面的非支配排序这一代的额外开销约 (O(MN\log N))可以忽略。3.3 锦标赛选择与精英保留的比较规则选择父代时采用二元锦标赛随机取两个个体当前沿序号不同时选前沿序号小的同层时选拥挤度大的。这个规则保证进化压力偏向支配层高的解同时保留前沿内部的多样性。精英保留则是把父代和子代合并成 2N 大小的种群按前沿逐层填入下一代放不下的那一层按拥挤度从大到小取。阶段比较对象优先条件锦标赛选择随机两个个体前沿序号小者优先同层取拥挤度大者精英保留同一前沿内个体拥挤度大者优先存活精英保留跨层不同前沿前沿序号小者整体优先3.4 插板式编码下的交叉与变异算子通用 NSGA-II 的交叉变异针对二进制或实数编码设计用在插板式编码上必须改造。工序序列段要保证每个工件 ID 出现次数恰好等于其工序数普通两点交叉会破坏这个约束需要采用顺序交叉子代从一个父代继承部分位置的工件剩余位置按另一个父代的工件顺序填充。插板位置段相对独立可以采用掩码交叉交叉后对子代插板做排序去重和边界修复。变异分两路工序序列段随机交换两个不同工件的工序位置插板段以一定概率把某个插板位置左右移动一个随机量或者重新采样一个新位置。插板变异的效果是改变分批边界工序交换改变的是段内细节两者负责的搜索粒度不同配合使用才能兼顾全局和局部搜索。4. 用 Python 复现插板式编码与 NSGA-II 的最小调度器4.1 个体表示、初始化与解码实现完整代码里把上面的 decode 函数落成可直接运行的版本。为了演示假设 3 台机器、3 个工件每个工件有 4 道工序工序的可选机器和耗时用字典表达。import random random.seed(42) num_jobs, num_machines 3, 3 ops { 0: [(0, 5), (1, 4), (2, 3)], 1: [(2, 4), (0, 3), (1, 5)], 2: [(1, 2), (2, 6), (0, 4)], } # 每个工件工序数不足一批时循环取这里简化设计为固定 3 道 total_ops sum(len(v) for v in ops.values()) def init_individual(): job_seq [] for j, item in ops.items(): job_seq.extend([j] * len(item)) random.shuffle(job_seq) k random.randint(1, total_ops - 1) cut_points sorted(random.sample(range(1, total_ops), k)) return job_seq, cut_points def decode(job_seq, cut_points): prev_end [0] * num_jobs avail [0] * num_machines op_cnt [0] * num_jobs plan [] segment_start 0 for cut in cut_points [len(job_seq)]: for idx in range(segment_start, cut): job job_seq[idx] op op_cnt[job] op_cnt[job] 1 machine, time ops[job][op] start max(prev_end[job], avail[machine]) end start time prev_end[job] end avail[machine] end plan.append((job, op, machine, start, end)) segment_start cut return plan这里init_individual中随机打乱的是工件 ID 序列k随机决定插板数量sample保证升序且不重复。初始化阶段如果发现解码结果明显失衡某台机器一直空闲可以考虑限制插板数量在总工序数的 30%~70% 范围内。4.2 目标评估与快速非支配排序解码之后要算出每个个体的目标值。基于plan里的end字段最大完工时间是所有工序结束时刻的最大值机器负载则按机器维度累加工时。def evaluate(job_seq, cut_points): plan decode(job_seq, cut_points) makespan max(end for *_ , start, end in plan) load [0] * num_machines for job, op, machine, start, end in plan: load[machine] ops[job][op][0][1] # 简化取第一候选用时 return makespan, max(load)拥挤度计算按第 3 章公式实现注意两个目标量纲不同必须先按各自的最大最小值做归一化。边界个体的距离直接设为大数实际代码里常用float(inf)但在合并排序时要注意inf不能参与比较运算比较前要做替换或把边界值设为一个远大于所有距离的有限数。def crowding_distance(front, objs): dist {ind: 0.0 for ind in front} for m in range(2): front.sort(keylambda ind: objs[ind][m]) f_min, f_max objs[front[0]][m], objs[front[-1]][m] if f_max f_min: continue dist[front[0]] float(inf) dist[front[-1]] float(inf) for i in range(1, len(front) - 1): dist[front[i]] (objs[front[i 1]][m] - objs[front[i - 1]][m]) / (f_max - f_min) return distfront.sort用的是 Python 默认的元组比较这里个体用索引表示objs是目标值字典按第 m 维排序。目标值完全相同的两个个体会出现分母为零的情况代码里用f_max f_min跳过。4.3 主循环与参数配置主循环把前面所有模块串起来初始化种群 → 评估 → 非支配排序 → 锦标赛选择 → 交叉变异 → 合并父代子代 → 精英保留 → 输出前沿。def nsga2(pop_size100, generations200, crossover_rate0.9, mutation_rate0.1): population [init_individual() for _ in range(pop_size)] objs {i: evaluate(*population[i]) for i in range(pop_size)} for _ in range(generations): fronts fast_nondominated_sort(population, objs) distances {} for front in fronts: distances.update(crowding_distance(front, objs)) parents tournament_selection(population, objs, distances) offspring crossover_and_mutation(parents, crossover_rate, mutation_rate) combined population offspring combined_objs {i: evaluate(*combined[i]) for i in range(len(combined))} next_pop, next_objs elitist_selection(combined, combined_objs, pop_size) population, objs next_pop, next_objs return population, objs def tournament_selection(pop, objs, distances): pop_size len(pop) selected [] for _ in range(pop_size): a, b random.sample(range(pop_size), 2) if fronts[a] fronts[b] or (fronts[a] fronts[b] and distances[a] distances[b]): winner a else: winner b selected.append(pop[winner]) return selected注意这里fronts变量在主循环中被重新赋值锦标赛选择需要用到每个个体所在的前沿层号实际代码里要在非支配排序后保存front_of_individual字典供选择阶段使用。交叉和变异函数内部要处理插板段的修复逻辑保证升序和范围有效。参数推荐范围说明种群规模50 ~ 200工序总数大时取 150 以上进化代数100 ~ 500看前沿是否还动不动则提前停交叉概率0.8 ~ 0.95过低收敛慢过高破坏优秀插板结构变异概率0.05 ~ 0.2插板段变异建议单独调大锦标赛规模2增大到 3 会加快收敛但损失多样性generations建议先跑 100 代看前沿形状再决定是否续跑。收敛慢的常见原因是变异率偏低不是代数不够。5. 参数整定与收敛性排错的三类信号5.1 前沿形状检查两个目标是否真正冲突输出前沿后第一件事是画散点图。横轴 makespan纵轴最大机器负载正常情况下应该是一条从左上到右下的曲线或带状分布。如果散点图只有一两个点大概率是种群提前收敛或者插板位置初始化范围太窄。如果散点图呈竖直线条说明两个目标的冲突没有被有效探索需要检查机器分配逻辑工序的可选机器集合如果只有一台机器目标 F2 实际上是常数这时应该增加一个与排序相关的目标比如总提前/拖期惩罚。5.2 插板数量的分布漂移每一代统计种群中插板数量 k 的平均值和方差。初始化时k 是均匀随机取的进化几代后通常会向某个方向收敛。如果 k 过早集中到某个值说明插板数量上的多样性不足交叉和变异对插板段的破坏力度不够。调试方向如下表现象可能原因调整手段前沿只有少量点选择压力过强锦标赛规模降回 2交叉率降 0.1插板数量收敛过快插板段变异率过低单独提高插板变异的触发概率前沿连续多代不动变异步长太小插板位置 ±Δ 的 Δ 从 1 改为 3~5目标函数波动剧烈交叉率过高降到 0.8同时增大种群规模5.3 一种可执行的收敛验证技巧不依赖画图直接量化种群多样性每隔 20 代记录当前前沿中被支配层为 1 的个体在目标空间两两之间的平均欧氏距离。具体方法是取出最优前沿个体对每对个体的两个目标值做归一化求欧氏距离后取平均。这个平均距离连续 30 代下降幅度小于 1% 时说明前沿已经稳定可以终止进化。对应检查代码python -c import numpy as np d [pairwise_distance(front_i) for front_i in history] print(np.mean(np.diff(d[-30:]) / np.abs(d[-30:]))) 这段命令输出最后 30 代前沿平均距离的平均变化率。正值说明前沿还在扩展接近 0 或负值说明收敛。配合每代把 Pareto 前沿及插板数量分布导出到 CSV可以后续用表格软件直接分析。判断收敛后再做一次局部搜索把前沿中每个个体的插板位置逐一微调并检查目标值是否改善这是 NSGA-II 类算法避免过早停止的常用收尾手段。本文还有配套的精品资源点击获取