简介面向工业工程、运筹优化与生产管理方向的学习者和算法实践者这份MATLAB实现的装配线平衡问题代码包围绕双种群遗传算法展开可用于复现任务分配、工作站划分与生产周期最小化的求解流程。包内共13个文件以10个m脚本和3个mat数据文件为主m文件覆盖种群初始化、适应度计算、解码、选择、交叉、变异及结果绘制等环节mat文件存放算例数据与运行结果压缩包约13KB体量轻便、结构紧凑。已有1289人学习下载说明其在课程实验、竞赛练习与算法入门中具有一定参考度。读者可据此理解双种群独立演化如何增强搜索多样性、缓解早熟收敛并借助Jackson平衡问题实例验证编码解码与算子设计还可调整种群规模、交叉和变异概率、停止条件等参数观察周期时间与工作站数量变化为结合工人技能、设备限制等现实约束的建模提供可运行的起点。1. 装配线平衡为什么值得用双种群遗传算法啃一条产线的节拍账某电子装配车间客户要求 45 秒节拍线上 32 道工序、8 个工位。实测第 3 工位 68 秒第 7 工位 22 秒后面一堆人站着等前道。这就是装配线平衡问题ALB的日常给定任务集、任务时间、优先关系把任务分进工位让工位数最少、节拍最小、负荷最平。工序过 40 道之后分支定界和整数规划在十分钟内基本给不出能用的解启发式就得上场。双种群遗传算法解决的是单种群 GA 那个玄学问题——迭代到 80 代左右群体全长得一样交叉不出新东西只会在局部最优附近打转。两个群体分工、定期交换精英能把多样性多撑几百代。这套东西适合离散制造的工艺工程师和做排产系统的开发者拿到一个.rar别急着双击先搞清楚它建的是什么模型。2. 把装配线翻译成算法能吃的模型优先图、节拍与工位约束写代码之前要先承认一件事装配线平衡的难点不在算法在建模。任务时间填错一个数、优先关系漏一条边后面跑出来的工位数再漂亮也是错的。这一章把现场那张工艺卡片翻译成算法能直接吃的三个对象任务时间向量、优先关系图、节拍。2.1 优先关系图与任务时间向量怎么落地工艺卡片上的信息一般长这样任务编号、任务名称、标准工时、紧前工序。落到代码里就是三个数组——t[i]是任务 i 的工时preds[i]是任务 i 的直接前置任务集合succ由preds反推。优先关系必须是偏序不能成环现场偶尔会画出 A 等 B、B 等 A 的鬼图通常是工艺员把装配顺序和物流顺序混在一张表上了。字段含义常见填写错误task_id任务唯一编号重号导数据时被覆盖t单件标准工时秒填成批量总工时preds直接前置任务集合只填最近一道漏掉间接前置cycle_time节拍用理论产能反算没扣换型任务时间的口径要统一。我一般要求工艺给的是「稳定生产状态下的人工 设备工时」不含宽放。宽放放在节拍里扣不要两边都扣否则模型会系统性偏乐观。2.2 三个目标函数工位数、平滑指数、节拍ALB 有三类经典目标。第一类是最小化工位数给定节拍问最少几个工位能装下。第二类是最小化节拍给定工位数问最快多久出一件。第三类是平滑指数工位数和节拍都定了让各工位负荷尽量接近减少等待浪费。平滑指数常用这个形式SI sqrt(sum((C - load[k])^2) / K)C是节拍load[k]是第 k 个工位的负荷K是工位数。SI 越小线越平。实际项目里我一般做加权工位数权重最高因为少一个工位就是实打实的人力成本SI 作为第二目标防止算法给出「7 个工位但 6 个闲着」这种纸面最优。提示目标函数别一上来就搞三目标 Pareto。先把工位数压到理论下界附近再在工位数相同的解集里挑 SI 最小的工程上好解释产线也愿意接。2.3 一个最小可跑的数据结构与可行性校验下面这段是模型的底座后面所有算子都挂在它上面。拓扑校验必须做宁可启动时报错也别让算法跑两小时才发现数据成环。from dataclasses import dataclass dataclass class ALBInstance: n: int # 任务数 t: list # t[i] 任务 i 的工时秒 preds: list # preds[i] 是任务 i 的直接前置任务集合 cycle_time: int # 节拍秒 def topo_check(self): Kahn 拓扑排序校验优先关系是否有环 indeg [len(ps) for ps in self.preds] succ [[] for _ in range(self.n)] for i, ps in enumerate(self.preds): for p in ps: succ[p].append(i) stack [i for i, d in enumerate(indeg) if d 0] seen 0 while stack: u stack.pop() seen 1 for v in succ[u]: indeg[v] - 1 if indeg[v] 0: stack.append(v) return seen self.n # False 表示存在环 def lower_bound_stations(self): 工位数理论下界总工时除以节拍向上取整 import math return math.ceil(sum(self.t) / self.cycle_time)topo_check返回False就直接终止别往下走。lower_bound_stations给的是一个很松的下界但它足够用来判断「算法结果到底离谱不离谱」。32 道工序、总工时 340 秒、节拍 45 秒下界是 8如果算法给出 11 个工位那基本可以判定解码器或者算子出了问题不用去调参。2.4 任务数上到 100 以后稀疏表示比邻接矩阵省事小规模数据用邻接矩阵无所谓100 个任务也就是 1 万個格子。但现场数据经常带批次一个车间十几条线、每条线几十道工序矩阵一多内存就上去了。我一般直接用set存前置关系判断preds[i] done是集合包含比遍历布尔数组快写起来也短。这个选择在 200 个任务以内差别不明显但到 500 以上稀疏表示的初始化时间能差一个数量级。3. 双种群遗传算法怎么设计两个群体分工与共享机制单种群 GA 在 ALB 上翻车通常不是因为算子写得差是因为搜索过程太早同质化。装配线平衡的解空间有个特点任务顺序上很小的一个交换可能导致后面整段工位划分全变。单一种群在 100 代左右就会把这类「结构不一样」的解淘汰干净剩下的都是同一个局部最优的变体。3.1 单种群为什么会早熟一次多样性塌陷的观察我做过一个对比32 个任务、节拍 45 秒种群 120交叉率 0.9变异率 0.1。记录每代种群中不同工位数的解的数量。前 40 代还有 6 种不同工位数到 90 代只剩 2 种150 代之后全部收敛到 10 个工位而理论下界是 8。增加变异率到 0.3 能拖慢收敛但解的质量开始抖每次跑结果都不一样这种「靠变异率续命」的做法在生产环境里没法交代。塌陷的根因是选择压力。锦标赛选择每代都在砍掉适应度靠后的个体而 ALB 的适应度地形是台阶状的——工位数从 10 降到 9 需要一连串协同变化单点变异跨不过去。两个种群的价值就在于让一部分个体在另一条地形上先走几步再把走通的路传回来。3.2 种群 A 与种群 B 的分工编码与初始化差异我的做法是两个种群用同一种编码但初始化策略和目标偏好不同。种群 A 走「工位数优先」初始解用位置权重法生成把任务按「后续任务总工时」降序排贪心装箱初始个体普遍工位数低但负荷不均。种群 B 走「平滑优先」初始解随机打散再修复工位数偏高但各工位负荷接近。编码统一用随机键每个任务一个实数优先权prio[i]解码时按优先权从大到小做拓扑排序得到任务序列再按首次适应装箱。这样交叉变异作用在实数向量上永远不会产生违反优先关系的非法序列省掉一大类修复逻辑。两个种群的差异体现在初始化和选择时的适应度权重上不体现在编码上移民的时候可以直接换。维度种群 A种群 B初始化位置权重启发式随机 修复适应度偏好工位数权重 0.8SI 权重 0.6变异率0.120.25规模60603.3 交叉、变异算子与移民策略交叉用模拟二进制交叉SBX作用在优先权向量上分布指数取 15。SBX 的好处是子代在两个父代附近连续分布不像单点交叉那样把向量切碎。变异用高斯扰动标准差按1/n缩放n 是任务数任务越多单次扰动越小避免大实例上一步跳太远。移民策略是双种群的核心。每 20 代做一次从 A 取适应度前 5 的个体替换 B 中最差的 5 个同时从 B 取前 5 替换 A 中最差的 5 个。注意是双向且等量单向移民会让一个种群迅速吃掉另一个。移民之后不清空精英精英始终保留在原种群。注意移民周期不要设得太短。试过每 5 代移民一次两个种群在 30 代内就同质化了等于白搭。20 到 30 代是比较稳的区间规模大的实例可以放宽到 40。3.4 参数表规模、交叉率、变异率、移民周期参数取值调整方向单种群规模50 至 80小于 40 多样性不够交叉率0.85 至 0.95低于 0.7 搜索停滞变异率 A / B0.12 / 0.25B 低了解不掉负荷不均移民周期20 至 30 代太短同质化太长等于两个独立 GA移民个体数种群的 8% 至 10%太多破坏本群结构精英保留每群 2 个保证历史最优不丢最大代数500 至 800配合停滞终止停滞阈值80 代无改进省时间比固定代数稳这些数不是拍脑袋来的。交叉率 0.9 对应的是「每代几乎全部个体参与重组」ALB 的解需要大范围重组才能跨过工位数的台阶变异率 B 高是因为它承担了扰动负荷分布的任务。参数之间是耦合的改一个要连带看另一个后面第 5 章会讲几个典型的连锁反应。4. 手写一版能跑的双种群 GA编码、解码与迭代主循环这一章把上一章的设计落成能跑的代码。不依赖任何第三方优化库numpy只用来生成随机数和存种群核心逻辑全在手写函数里方便改算子也方便出问题时打断点。4.1 两段式编码优先权向量 拓扑排序解码染色体就是一个长度 n 的实数向量。任务 i 的优先权是prio[i]值越大越先排。解码分两步先按优先权做拓扑排序得到任务序列再按序列贪心装箱。拓扑排序用堆每次从入度为 0 的任务里挑优先权最大的这样得到的序列天然满足优先关系。import heapq import numpy as np def priority_to_sequence(prio, inst): 按优先权从大到小做拓扑排序返回满足优先关系的任务序列 indeg [len(ps) for ps in inst.preds] succ [[] for _ in range(inst.n)] for i, ps in enumerate(inst.preds): for p in ps: succ[p].append(i) heap [(-prio[i], i) for i in range(inst.n) if indeg[i] 0] heapq.heapify(heap) seq [] while heap: _, u heapq.heappop(heap) seq.append(u) for v in succ[u]: indeg[v] - 1 if indeg[v] 0: heapq.heappush(heap, (-prio[v], v)) if len(seq) ! inst.n: return None # 优先关系成环数据有问题 return seq-prio[i]取负数是因为 Python 的堆是小顶堆。序列长度不等于 n 说明图里有环返回None让上层处理不要在这里抛异常否则整个种群评估会中断。这个函数每评估一个个体就调一次是热点任务数上到 300 以后可以考虑缓存succ现在这样写是为了可读。4.2 解码器按节拍贪心装箱拿到序列之后装箱。首次适应按顺序取任务能塞进已有工位就塞第一个装得下的塞不下就新开一个工位。这个策略对 ALB 不算最优但足够快而且和现场「任务不能跨工位、工位有节拍上限」的约束对得上。def decode(seq, inst, cycle_time): 首次适应装箱返回每个工位的任务列表和负荷 stations, loads [], [] for task in seq: placed False for k in range(len(stations)): if loads[k] inst.t[task] cycle_time: stations[k].append(task) loads[k] inst.t[task] placed True break if not placed: stations.append([task]) loads.append(inst.t[task]) return stations, loads def evaluate(seq, inst, cycle_time, w_station0.8): 适应度工位数为主平滑指数为辅越小越好 if seq is None: return float(inf), None stations, loads decode(seq, inst, cycle_time) k len(stations) si (sum((cycle_time - x) ** 2 for x in loads) / k) ** 0.5 # 平滑指数归一化到和工位数同一量级 score w_station * k (1 - w_station) * (si / cycle_time) return score, (stations, loads)w_station是工位数权重种群 A 用 0.8种群 B 用 0.5。si / cycle_time是为了把平滑指数压到和工位数可比的范围否则 SI 动辄几十加权就没意义了。返回的二元组里第二项留着给结果导出用避免重复解码。4.3 双种群主循环与精英保留主循环的结构是初始化两个种群 → 各自评估 → 各自选择交叉变异 → 精英保留 → 到周期就移民。用np.random.default_rng(seed)固定随机源同一份数据同一组参数能复现出问题才好查。def sbx(p1, p2, rng, eta15.0): 模拟二进制交叉作用在优先权向量上 u rng.random(len(p1)) beta np.where(u 0.5, (2 * u) ** (1 / (eta 1)), (1 / (2 * (1 - u))) ** (1 / (eta 1))) c1 0.5 * ((1 beta) * p1 (1 - beta) * p2) c2 0.5 * ((1 - beta) * p1 (1 beta) * p2) return c1, c2 def mutate(p, rng, sigma): 高斯扰动sigma 建议取 1/n return p rng.normal(0, sigma, sizelen(p)) def tournament(pop, fits, rng, k3): idx rng.integers(0, len(pop), sizek) best idx[np.argmin(fits[idx])] return pop[best].copy() def run_dual_ga(inst, cfg, seed42): rng np.random.default_rng(seed) n inst.n # 初始化A 用位置权重启发式B 用随机 def init_A(): return rng.normal(0.5, 0.1, sizen) def init_B(): return rng.random(n) popA np.array([init_A() for _ in range(cfg[size_A])]) popB np.array([init_B() for _ in range(cfg[size_B])]) def eval_pop(pop, w): fits np.empty(len(pop)) for i, p in enumerate(pop): seq priority_to_sequence(p, inst) fits[i], _ evaluate(seq, inst, inst.cycle_time, w) return fits best_global, best_score None, float(inf) for gen in range(cfg[max_gen]): fitA eval_pop(popA, cfg[w_A]) fitB eval_pop(popB, cfg[w_B]) # 记录全局最优 for pop, fits in ((popA, fitA), (popB, fitB)): j int(np.argmin(fits)) if fits[j] best_score: best_score fits[j] best_global pop[j].copy() # 精英保留 生成新一代 newA [popA[int(np.argmin(fitA))].copy()] newB [popB[int(np.argmin(fitB))].copy()] while len(newA) cfg[size_A]: p1, p2 tournament(popA, fitA, rng), tournament(popA, fitA, rng) c1, _ sbx(p1, p2, rng) newA.append(mutate(c1, rng, 1.0 / n)) while len(newB) cfg[size_B]: p1, p2 tournament(popB, fitB, rng), tournament(popB, fitB, rng) c1, _ sbx(p1, p2, rng) newB.append(mutate(c1, rng, 2.0 / n)) popA, popB np.array(newA), np.array(newB) # 周期性双向移民 if (gen 1) % cfg[migrate_every] 0: m cfg[migrants] topA popA[np.argsort(fitA)[:m]] topB popB[np.argsort(fitB)[:m]] popB[-m:] topA popA[-m:] topB return best_global, best_score几个地方值得说明。精英保留只留 1 个是因为第 5 章会看到留多了种群会僵化移民直接覆盖最差的 m 个位置固定便于日志追踪。mutate的标准差在 A 里是1/nB 里是2/n和参数表里的变异率差异对应。best_global每代更新不依赖最后一次评估避免最后一代被移民拉低。4.4 收敛曲线与结果落盘跑完之后要能看出发生了什么不能只拿一个数。我一般落三类东西每代两个种群的最优适应度、平均适应度、不同工位数的解的数量。第三个数是多样性指标比单纯看适应度有用它能提前告诉你种群是不是要塌了。import csv def dump_result(path, best_prio, inst, cycle_time): seq priority_to_sequence(best_prio, inst) stations, loads decode(seq, inst, cycle_time) with open(path, w, newline, encodingutf-8) as f: w csv.writer(f) w.writerow([station, load_sec, tasks]) for k, (tasks, load) in enumerate(zip(stations, loads), 1): w.writerow([k, load, .join(map(str, tasks))]) return stations, loads导出的 CSV 直接贴给工艺看工位号和负荷两列最直观。任务列用空格分隔方便复制到排产表。落盘路径按「线体-节拍-种子」命名跑多组参数对比时不会乱。收敛曲线用matplotlib画两张图适应度和多样性横轴代数纵轴分别是分数和工位数种类数肉眼判断早熟比看日志快。5. 调参与踩坑排查跑不动、跑不准、跑不稳分别看哪里下面这几条是按「现象 → 原因 → 解决」记的都是实际跑的时候遇到的没有一条是理论推演。排序按出现频率第一条最常被问。5.1 现象解码后工位数比理论下界多两个怎么调参数都没用原因多半不是算法问题是任务时间口径。检查t数组里有没有任务工时大于节拍cycle_time。只要有一个任务单独就超节拍装箱器就会给它开一个独占工位工位数直接多一个后面全乱。另一个高频原因是优先关系把几条本可以并行的支路串成了链拓扑排序后任务被迫排先后。解决启动时加断言max(t) cycle_time不满足就报出是哪个任务。然后画出优先图找「最长路径 ÷ 节拍」这个下界它比总工时下界更紧。如果最长路径算出来就是 9算法给 10 是合理的不要硬压。5.2 现象两个种群收敛到同一个解移民之后没有任何变化原因移民个体数太少或者周期太短两个种群在还没分化之前就被拉平了。也可能是两个种群的适应度权重设得一样比如都 0.8分工名存实亡。解决把移民周期从 10 拉到 25移民数降到种群的 8%。检查w_A和w_B至少差 0.2。还不行就给 B 的初始化解强制加一轮局部搜索让它先走到和 A 不同的工位数上再开始移民。5.3 现象结果每次跑都不一样最好的一次 9 个工位差的一次 11 个原因变异率过高加上种群规模偏小搜索过程本身就在抖。ALB 的适应度台阶状地形对随机性很敏感60 个个体、变异率 0.3 的组合基本等于每次重新随机采样。解决固定随机种子先跑 10 个种子看分布取中位数而不是最好值做评估。把变异率降到 0.12 至 0.15种群规模提到 80。生产环境用的解应该是「10 个种子里 8 个都能到 9 个工位」的那种不是某一次撞上的。5.4 现象任务数上到 300 以后内存涨得很快跑 200 代要几个小时原因每个个体评估都重新建一次succ表priority_to_sequence里那个双层循环是 O(n e)被调用种群规模 × 代数次。另外种群用list存 numpy 数组跨境拷贝开销大。解决把succ提到ALBInstance初始化时建一次函数里只读。种群用np.ndarray二维数组存不要用list of array。评估时能批量的部分向量化拓扑排序那一步没法向量化就保持循环但可以只对前 20% 的个体做精确评估、其余用近似适应度粗筛这是我常用的加速手段。5.5 现象解码时抛出KeyError或者死循环任务列表对不上原因任务编号不连续。工艺表里删除过工序ID 是 1、2、5、7代码里按range(n)建数组索引 3、4 是空的。另一种是前置任务里写了不存在的 ID。解决入口处做一次 ID 重映射把原始 ID 映射到 0 到 n-1映射表单独存导出结果时再映射回去。前置任务集合里出现越界 ID 直接报错不要静默跳过——跳过一条前置边出来的解看着合理实际装不出来。6. 从能跑到敢上线用下界、基线给双种群 GA 的结果上三道保险算法跑出 9 个工位工艺问一句「凭什么信」你得答得上来。我的做法是三道校验缺一道都不往排产表里灌。第一道理论下界。算两个总工时除以节拍向上取整最长优先路径除以节拍向上取整取大者。结果是 9算法给 9直接收工算法给 10就要能说清楚为什么多一个——通常是某个工位的任务组合卡在节拍边界上。第二道基线对比。用 LPT最长处理时间优先贪心跑一遍它不需要优先关系只给一个「无约束装箱」的参考值。双种群 GA 的结果如果比 LPT 还差说明优先关系或者解码器有问题不是参数问题。第三道小规模精确解对照。从线上抽 15 到 20 个任务的子集用整数规划求最优和 GA 在同规模下的结果比。差距在 0 到 1 个工位以内这套实现才算可信。回灌排产表之前还有三个校验必须做每个任务恰好出现一次、每个工位的负荷不超过节拍、每个任务的前置任务所在工位号不大于它自己的工位号。第三条最容易被忽略也是我翻过车的地方。有一次算法结果只输出了工位号和任务列表没输出工位顺序排产系统按工位号从小到大排结果一个后道工序被放到了前道工序前面现场装到一半发现装不进去整条线停了四十分钟。血泪经验是工位号必须显式落盘而且要和物理线体的流向一致不能靠数组下标隐式表达。提示结果文件里加一列「工位物理序号」和现场贴的工位牌一一对应。算法内部的工位编号只用于计算别直接当生产序号用。我现在跑完一组参数会先把收敛曲线和多样性曲线并排看一眼再看下界差几个工位最后抽一个解手工装一遍。这套动作做熟了也就十分钟比上线之后返工便宜太多。双种群遗传算法解决装配线平衡问题难点从来不在「双种群」这三个字在数据口径、在约束有没有漏、在结果敢不敢签字。把这几件事做扎实算法本身反而是最省心的那一环。希望帮到你。本文还有配套的精品资源点击获取