简介：这份资源围绕双种群遗传算法求解装配线平衡问题（ALBP）展开，面向运筹优化、工业工程与智能算法方向的学习者和研究者，尤其适合需要复现经典案例、验证算法性能的读者。压缩包共13个文件，以10个m脚本和3个mat数据文件为主，脚本覆盖适应度计算、解码、选择、交叉、变异、种群初始化与绘图等完整流程，mat文件则保存任务时间与算例数据，整体约13KB，结构紧凑、便于直接运行调试。资源以Jackson平衡问题为测试实例，通过双种群演化增强解空间探索、抑制早熟收敛，帮助读者理解如何以最小化生产周期为目标完成工作站任务分配。目前已有1289人学习下载，可作为课程设计、论文实验或算法对比的参考素材，从中获取建模思路、参数设置经验与结果可视化方法。
1. 双种群遗传算法解决装配线平衡问题：一份能跑通产线节拍优化的源码包
装配线平衡这件事，做过产线排产的人都知道它有多磨人。工位节拍卡在 52 秒，客户要求压到 45 秒，工位数还不能加，工序之间的先后约束又像一张网，手工调一版方案能耗掉一整个下午。这份《双种群遗传算法解决装配线平衡问题.rar》就是冲着这类场景来的——它把线平衡优化抽象成带约束的组合优化问题，用双种群遗传算法去搜工位任务分配方案，目标是最小化节拍、均衡各工位负荷。适合谁？做 IE 的、做排产算法的、写运筹优化课程设计的，以及手头有一堆工序表和先后约束、想拿算法跑一版可行解对比手工方案的从业者。它不是一个能直接对接 MES 的成品系统，而是一套可读、可改、可复现的算法实现，核心价值在于把「双种群」这个容易讲不清的机制落成了能跑的代码。
2. 双种群遗传算法解线平衡：原理、编码与选型理由
2.1 为什么线平衡问题值得上遗传算法
装配线平衡问题（Assembly Line Balancing Problem，ALBP）的经典形式是：给定一组作业任务，每个任务有作业时间，任务之间存在先后约束，要求把任务分配到若干工位上，使得各工位作业时间尽量接近、工位数尽量少、节拍尽量小。它的搜索空间随任务数呈阶乘级增长，20 个任务的全排列就是 2.4×10^18 量级，穷举根本不现实。这类问题属于 NP-hard，精确算法（分支定界、动态规划）在任务数上到三四十个之后基本就顶不住了。
遗传算法在这里的优势是：不要求目标函数可导，能直接处理先后约束这种离散逻辑，种群并行搜索不容易陷进单一局部最优。但标准单种群遗传算法有个老毛病——早熟收敛。种群多样性掉得太快，几十代之后个体长得都差不多，交叉出来的还是那批解，搜索就停滞了。双种群机制就是针对这个痛点来的：把种群拆成两个，各自按不同策略进化，再定期交流优秀个体，用种群间的差异维持整体多样性。常见做法是让一个种群偏探索、一个种群偏开发，或者两个种群用不同的交叉变异参数，避免整锅汤一个味道。
2.2 双种群的分工与交流机制
这份源码里双种群的核心设计，是把种群分成两个独立演化的子群，各自维护自己的种群数组和适应度。两个子群在进化策略上有区分，一个侧重全局探索（变异率偏高、交叉方式偏随机），一个侧重局部开发（变异率偏低、保留精英更激进）。每隔若干代做一次种群间交流，把各自最优的若干个体迁移到对方种群，替换掉对方最差的个体。
这个迁移操作是双种群的关键。迁移太频繁，两个种群很快趋同，等于白拆；迁移太稀疏，两个种群各玩各的，交流带来的增益体现不出来。源码里迁移间隔和迁移个体数是可调参数，我一般会先把迁移间隔设成总代数的十分之一左右，迁移个体数取种群规模的 5% 到 10%，跑几组对比再定。下面这段是种群初始化和迁移逻辑的骨架，参数含义我写在注释里：
import random def init_population(n_tasks, pop_size): # 每个个体是一个任务序列，需满足先后约束 population = [] for _ in range(pop_size): seq = list(range(n_tasks)) random.shuffle(seq) seq = repair_order(seq) # 修复成满足先后约束的拓扑序 population.append(seq) return population def migrate(pop_a, pop_b, fit_a, fit_b, migrate_num): # 把 A 中适应度最好的 migrate_num 个个体迁到 B，替换 B 中最差的 idx_a = sorted(range(len(fit_a)), key=lambda i: fit_a[i], reverse=True)[:migrate_num] idx_b = sorted(range(len(fit_b)), key=lambda i: fit_b[i])[:migrate_num] for src, dst in zip(idx_a, idx_b): pop_b[dst] = pop_a[src][:] fit_b[dst] = fit_a[src] return pop_b, fit_b逻辑说明：init_population生成的是任务编号的排列，但排列必须满足先后约束，所以用repair_order做一次拓扑修复，把违反约束的顺序调整过来。migrate做的是单向精英迁移，把 A 群头部个体覆盖到 B 群尾部。参数上，pop_size太小（比如低于 20）多样性不够，太大（超过 200）单代计算变慢，中小规模线平衡问题一般取 50 到 100 比较稳。migrate_num别超过种群规模的 15%，否则 B 群会被 A 群同化得太快。
2.3 适应度函数与约束处理
线平衡的适应度不能只看节拍，还得把工位负荷均衡度算进去，否则算法会给出一个节拍很小但个别工位闲得发慌的方案。源码里适应度是节拍和均衡指数的加权组合，权重可调。约束处理用的是修复加惩罚的混合方式：先后约束在解码阶段直接修复，工位数约束用惩罚项加在适应度上。
def fitness(individual, task_time, n_stations, precedence): # 按顺序把任务贪心分配到工位，超过节拍就开新工位 stations = [[]] load = [0] for task in individual: t = task_time[task] if load[-1] + t <= cycle_time_guess: stations[-1].append(task) load[-1] += t else: stations.append([task]) load.append(t) cycle = max(load) balance = sum((cycle - l) ** 2 for l in load) / len(load) penalty = 0 if len(stations) > n_stations: penalty = (len(stations) - n_stations) * 1000 return -(cycle + 0.3 * balance + penalty)逻辑说明：解码时按个体给出的任务顺序依次往工位里塞，塞不下就开新工位，这是线平衡里最常用的贪心解码。cycle_time_guess是预估节拍，可以先用理论下界（总作业时间除以工位数）起步。balance是各工位空闲时间的方差，越小越均衡。penalty处理工位超限，系数 1000 要远大于节拍量级，保证超限个体被淘汰。权重 0.3 是均衡项的系数，想让方案更均衡就调大，想优先压节拍就调小。
3. 从工序表到可执行方案：数据准备与跑通流程
3.1 输入数据的组织方式
这份源码对输入数据的要求不复杂，核心就三样：任务编号、每个任务的作业时间、任务之间的先后约束。先后约束一般用「前置任务列表」表示，比如任务 5 必须在任务 2 和任务 3 之后，就记成5: [2, 3]。数据通常放在一个文本或 CSV 里，源码读取后转成内部结构。
我一般会把工序数据整理成下面这种格式，一行一个任务，字段用逗号隔开，最后一列是前置任务编号（没有就留空）：
task_id,time,predecessors 1,12, 2,8,1 3,15,1 4,7,2 5,10,"2,3" 6,9,4 7,14,"5,6"读取和解析的代码大致是这样，注意前置任务字段可能带引号和逗号，解析时要处理：
import csv def load_tasks(path): task_time = {} precedence = {} with open(path, encoding="utf-8") as f: reader = csv.DictReader(f) for row in reader: tid = int(row["task_id"]) task_time[tid] = float(row["time"]) preds = row["predecessors"].strip() if preds: precedence[tid] = [int(p) for p in preds.split(",")] else: precedence[tid] = [] return task_time, precedence逻辑说明：task_time是任务到作业时间的映射，precedence是任务到前置任务列表的映射。这里用csv.DictReader按列名读，比按位置读更抗字段顺序变化。参数上，作业时间单位要统一（秒或分钟都行，但全程一致），前置任务编号必须都在任务表里存在，否则拓扑修复会报错。常见翻车点是 CSV 里前置任务字段用了中文逗号，split(",")切不开，读进来会变成一整个字符串，跑起来约束全乱。
3.2 主循环与参数配置
主流程就是初始化两个种群、循环进化、定期迁移、记录最优。下面这段是主循环骨架，把双种群的节奏串起来：
def run(task_time, precedence, n_stations, pop_size=80, generations=300, pc=0.8, pm=0.1, migrate_gap=30, migrate_num=6): n = len(task_time) pop_a = init_population(n, pop_size) pop_b = init_population(n, pop_size) best = None for gen in range(generations): fit_a = [fitness(ind, task_time, n_stations, precedence) for ind in pop_a] fit_b = [fitness(ind, task_time, n_stations, precedence) for ind in pop_b] pop_a = evolve(pop_a, fit_a, pc, pm) pop_b = evolve(pop_b, fit_b, pc * 0.9, pm * 0.5) # B 群偏开发 if gen % migrate_gap == 0: pop_b, fit_b = migrate(pop_a, pop_b, fit_a, fit_b, migrate_num) cur = max(pop_a + pop_b, key=lambda ind: fitness(ind, task_time, n_stations, precedence)) if best is None or fitness(cur, task_time, n_stations, precedence) > fitness(best, task_time, n_stations, precedence): best = cur return best逻辑说明：A 群用标准交叉变异率（pc=0.8、pm=0.1）偏探索，B 群把交叉率和变异率都压低（乘 0.9 和 0.5）偏开发，这是双种群分工最省事的实现方式。migrate_gap=30表示每 30 代迁移一次，generations=300时大约迁移 10 次。参数怎么定：任务数少（20 以内）时种群 50、代数 200 就够；任务数上到 50 以上，种群建议 100 到 150、代数 500 起步，否则搜索不充分。pc一般 0.7 到 0.9，pm一般 0.05 到 0.2，变异率太高会退化成随机搜索。
3.3 结果输出与方案还原
跑完之后要把最优个体还原成「哪个任务分到哪个工位」的方案，而不是只给一个任务序列。还原逻辑和解码逻辑一致，输出成表格方便对照：
def decode(individual, task_time, cycle_time_guess): stations = [[]] load = [0] for task in individual: t = task_time[task] if load[-1] + t <= cycle_time_guess: stations[-1].append(task) load[-1] += t else: stations.append([task]) load.append(t) return stations, load stations, load = decode(best, task_time, cycle_time_guess) for i, (tasks, l) in enumerate(zip(stations, load), 1): print(f"工位{i}: 任务{tasks} 负荷{l}") print(f"节拍: {max(load)} 工位数: {len(stations)}")逻辑说明：decode返回每个工位的任务列表和负荷，打印出来就是一份可直接拿去和手工方案对比的分配表。cycle_time_guess这里要传和适应度函数里一致的值，否则还原出的工位数和适应度评估时对不上，会出现「算法说 5 个工位、还原出来 6 个」的玄学现象。输出后重点看两件事：节拍是否达到目标、各工位负荷是否接近，如果某个工位负荷明显偏低，说明均衡项权重还可以再调大。
4. 避坑与排查：双种群遗传算法跑线平衡的五个常见翻车点
4.1 现象：算法收敛很快但解质量差，几十代就不动了
原因：种群多样性过早丢失，多半是变异率太低或者初始化种群太单一。如果初始化时所有个体都用同一个随机种子附近的排列，开局就没什么差异。解决：把pm提到 0.15 以上试一组，初始化时确保每个个体独立随机；双种群这边检查迁移是不是太频繁，migrate_gap小于 10 代时两个种群会迅速趋同，把间隔拉到 20 到 50 代之间。
4.2 现象：跑出来的方案违反先后约束，任务顺序明显不对
原因：交叉或变异之后没有做约束修复。标准单点交叉会把父代的片段直接拼起来，拼出来的序列很可能违反先后关系。解决：在每次交叉变异后强制调用repair_order做拓扑修复，或者在解码阶段用「只从当前可执行任务里选」的贪心解码，从根上避免非法序列。源码里修复函数是关键，别图省事跳过。
4.3 现象：节拍压下去了，但工位负荷差得离谱，一个工位忙死一个闲死
原因：适应度函数里均衡项权重太低，算法只盯着节拍优化。解决：把均衡项系数从 0.3 往上调，比如 0.5 到 1.0，重新跑对比。另一个办法是在解码时加平滑策略，开新工位前先看看当前工位能不能塞下后面的小任务，减少碎片化分配。
4.4 现象：任务数一多就跑得特别慢，单代要好几秒
原因：适应度计算里反复做了解码，而解码是 O(n) 的，种群大、代数多时累积起来很可观。解决：把适应度缓存起来，同一个个体不重复算；解码时用增量方式更新工位负荷，别每次从头遍历。任务数超过 80 时，考虑把种群规模控制在 100 以内，靠增加代数而不是堆种群来提升解质量。
4.5 现象：每次运行结果都不一样，没法复现
原因：随机种子没固定。遗传算法本身是随机搜索，不设种子每次初始化、交叉、变异都不同。解决：在程序开头固定random.seed(42)，调试和对比参数时保证可复现；正式出方案时可以跑多次取最优，但每次的种子要记录在日志里，方便回溯。
5. 进阶调参与验证：让双种群真正跑出比单种群更好的解
双种群不是拆成两个就自动变强，得验证它确实比单种群好，否则就是白搭计算量。我的习惯是拿同一份工序数据，跑三组对比：标准单种群、双种群无迁移、双种群带迁移。评价指标看三个——最优节拍、达到最优的代数、多次运行的节拍标准差。如果双种群带迁移在节拍上没优势，但标准差明显更小，说明它胜在稳定性，这在产线场景里其实更有价值，因为方案波动小意味着可预期。
参数调优上，双种群最值得动的是迁移间隔和两个种群的参数差异。下面这张表是我在中小规模线平衡问题（30 到 60 个任务）上常用的参数区间，可以直接作为起点：
| 参数 | 常用区间 | 作用 | 调大后果 |
|---|---|---|---|
| pop_size | 50 到 150 | 种群规模 | 单代变慢，多样性提升 |
| generations | 200 到 800 | 进化代数 | 耗时线性增长 |
| pc | 0.7 到 0.9 | 交叉率 | 过高破坏优良个体 |
| pm | 0.05 到 0.2 | 变异率 | 过高退化为随机搜索 |
| migrate_gap | 20 到 50 | 迁移间隔 | 过小导致种群趋同 |
| migrate_num | 种群 5% 到 10% | 迁移个体数 | 过大同化过快 |
验证方法上，除了看节拍，还要做约束校验：把输出的工位分配方案逐条对照先后约束表，确认没有任务排在前置任务之前。这一步别偷懒，算法内部修复过不代表输出还原时不会出错，尤其是解码参数和适应度参数不一致的时候。我一般会写一个独立的校验脚本，把方案读进来重新检查一遍约束和工位数，通过了才算这份方案能用。
还有个容易被忽略的点：理论下界。总作业时间除以目标工位数就是节拍的理论下界，算法跑出来的节拍如果离下界很远，要么是约束太紧、要么是搜索不充分。先算下界再评估结果，心里才有杆秤，不会看到一个比手工方案好的解就以为到极限了。
从那以后我每次跑这类线平衡算法，都强制走一遍「固定种子、算理论下界、独立校验约束」这三步，少一步都不敢把方案交出去。希望帮到你。
本文还有配套的精品资源，点击获取
