简介：一份用于装配生产线任务平衡问题（ALB）的遗传算法MATLAB源代码，面向工业工程、机械制造与智能计算方向的科研人员及学生。算法在陈永卿等提出的混合遗传算法基础上改进，支持任务优先矩阵、任务时间与体积属性、时间节拍及工位体积约束等输入，通过变异退火、交叉与选择操作迭代搜索工位负载平衡方案。资源包仅含1个docx文档，大小55KB，涵盖主程序与子函数调用关系、参数含义说明以及多条收敛曲线的输出实现。算法输出最优个体编码、装配方案、目标函数值及适应值、工位个数、时间与空间利用率等收敛曲线，便于读者理解遗传算法在装配线平衡中的编码、评估与寻优细节。已有3164人浏览学习，适合用于课程设计、毕业设计或生产排程优化算法的移植参考与二次开发。

1. 装配生产线任务平衡问题的遗传算法：为什么值得自己写一遍 MATLAB

车间里最头疼的不是设备故障，而是装配线上某个工位堆满在制品、后面工位却在等料。停产损失是按分钟算的，而人工调整一次排产方案往往要花掉半天。装配生产线任务平衡问题（ALB）要回答的就是：在节拍固定的前提下，把任务合理分配到最少工位；或者工位数固定时，把节拍压到最短。很多工程师第一反应是找现成工具箱，但产线约束一多，商用求解器反而不如自己写遗传算法灵活。

这篇笔记要解决的是「用遗传算法（GA）解装配线平衡问题，并用 MATLAB 从零写出可用源代码」。我会先把模型讲清楚，再给一套能直接跑的数据和完整代码，最后交代参数怎么调、容易在哪里翻车。写完之后，你能拿着这套代码改自己的任务时间和前置关系，跑出工位分配方案，也能看懂网上各种版本源码的思路差异。

2. 先把模型立住：装配线平衡问题的两类目标与三种约束

装配线平衡问题在运筹学里属于组合优化，本质上是在处理「任务之间有先后依赖、单个任务时间又不同」的排序与分组问题。建模的清晰程度直接决定后面遗传算法设计和代码质量，所以第一步先把数学形式记牢。

2.1 第一类问题与第二类问题：最小化工位数与最小化节拍

装配线平衡问题按目标函数分成两大类。第一类问题（ALBP-I）在节拍 C 给定的前提下，最小化工位数量 m。第二类问题（ALBP-II）在工位数量 m 给定的前提下，最小化节拍 C。实际产线规划中，第一类更常见——客户订单的产能需求决定了节拍，你要做的是用最少工位把产线搭出来；第二类出现在产线改造场景，场地和人员数量受限，想压缩节拍提升产能。

第一类问题的数学模型可以这样描述：有 n 个任务，每个任务 i 有处理时间 t_i，任务之间存在前置约束（前置任务没做完，当前任务不能开工）。目标是把任务分配到若干工位，每个工位内所有任务时间之和不超过节拍 C，同时每个任务的前置任务必须被分配到编号更小的工位或同一工位内更早的位置。目标函数就是 min m。

第二类问题反过来，给定工位数量 m，要求每个工位负荷尽量小，目标函数是 min C = max(各工位任务时间之和)。两种目标在遗传算法里的差异只体现在适应度函数上，第 6 章我会给出改法。

2.2 前置约束的表达方式：用 cell 数组维护前驱任务集合

MATLAB 里表达前置约束，我推荐用 cell 数组。每个元素precedence{i}存放任务 i 的所有直接前驱任务编号，没有前驱的任务存空数组[]。比如任务 2 必须在任务 1 完成后才能开始，就写precedence{2} = 1；任务 5 需要任务 3 和任务 4 都完成，就写precedence{5} = [3 4]。

选择 cell 数组而不是邻接矩阵，原因有三个。第一，装配线前置关系通常是稀疏的，每个任务的前驱一般只有一两个，邻接矩阵 n x n 大部分是零，浪费内存还不好读。第二，解码时要频繁查询「任务 i 的前置任务是否都已完成」，cell 数组直接取precedence{i}做all()判断，代码最简洁。第三，打印排产结果时，mat2str 可以直接把前驱列表转成字符串输出，调试方便。

2.3 输入数据约定：任务时间表、约束表与节拍的检查清单

写代码前先把数据按统一格式准备好。任务时间用一个行向量taskTimes，索引就是任务编号，比如taskTimes(3) = 6表示任务 3 耗时 6 分钟。前置约束用上面的 cell 数组。节拍是一个标量cycleTime。

数据检查清单我一般过三遍：第一，length(taskTimes)是否等于length(precedence)，数量不对解码一定越界；第二，max(taskTimes) <= cycleTime是否满足，任何任务时间大于节拍，这个任务永远塞不进任何工位，算法结果无意义；第三，用拓扑排序检查前置约束是否有环，有环会直接让解码器死循环。前面两条检查用assert写进代码最省事，第三条我放在第 5 章排查里展开。

3. 遗传算法求解装配线平衡的三个关键设计

遗传算法解组合优化问题的核心不在「像不像生物进化」，而在「编码方式、解码方式、适应度函数」这三件套是否匹配问题结构。装配线平衡问题最大的难点是前置约束——普通随机生成的解几乎必然违反约束，所以编码设计要能天然避开非法解。

3.1 为什么选优先级实数编码：可行性不用修，解码器兜底

常见的错误做法是把染色体直接编码成任务序列（一个排列），然后用交叉变异去维护排列合法性。排列编码本身没错，但交叉算子必须用 PMX、顺序交叉这类专门为排列设计的算子，否则子代必然出现重复任务、缺失任务，每次都要修，修完解的质量还不可控。对于初学者，这条血泪路最容易走歪。

我用的方案是优先级实数编码：染色体是一个长度等于任务数 n 的实数向量，第 i 个基因位的数值表示任务 i 的优先级，数值越大越优先调度。这种编码下，任意随机向量都是一个合法个体，因为解码器会先按前置约束过滤候选集，再从候选集里挑优先级最高的任务。可行性由解码器兜底，交叉变异随便做都不会产生非法解，遗传算法的搜索效率会高很多。

3.2 解码器两步走：拓扑排序加顺序装箱

解码器把一条染色体翻译成具体的工位分配方案，分两步。第一步，拓扑排序：从所有未分配任务中，筛出那些前置任务已全部完成的任务作为候选集，在候选集里选优先级最高的任务加入序列，重复直到所有任务排完。因为每一步都在候选集里选，生成的任务序列天然满足前置约束。第二步，顺序装箱：按这个拓扑序列依次把任务放进工位，检查当前工位剩余时间是否够用，够就放入，不够就开新工位。

顺序装箱用的是 First-Fit 策略，实现简单且速度快。它不保证得到全局最优的工位分配，但遗传算法的机制决定了它不需要每次解码都最优——种群靠多代进化逐步逼近最优，解码太快反而是优势，能省下时间给更多迭代。如果你想在解码阶段就做更精细的搜索，可以把 First-Fit 换成 Best-Fit（遍历已有工位选剩余空间最紧张但放得下的），这个改进我放在第 6 章。

3.3 适应度函数：工位数量最小化加负荷均衡惩罚

适应度函数的第一个版本通常写成fitness = 1 / nStations，工位数越少适应度越大。跑起来会发现一个尴尬情况：很多个体工位数相同，适应度完全相同，选择压力不足，种群进化到后期几乎是随机漂移。

我一般会在分母上加一个负荷均衡惩罚项，变成：

fitness = 1 / (nStations + beta * imbalance);

其中imbalance用各工位已用时间与均值之差的归一化标准差来度量，beta是惩罚系数。这样有两个好处：当最小工位数还没达到时，算法优先压工位数；当两个个体工位数相同时，负荷分布更均衡的那个胜出，产线实际运行时不均衡的瓶颈效应会小很多。beta一般取 0.2 到 0.5，太大容易在工位数还没压下来时就过度追求均衡，反而拖慢收敛。

4. 核心源代码：主程序与三个算子的 MATLAB 实现

这一章给完整可运行的 MATLAB 代码。我用的示例数据是 10 个任务的装配线，总任务时间 50，节拍 10，理论下界 5 个工位，且人工可排出 5 工位方案，适合用来验证算法正确性。

4.1 主程序骨架：参数设置与进化循环

主程序保存为main_ALB.m。注意开头用rng(42)固定随机种子，否则每次运行结果都不同，排错会非常痛苦。

%% 装配线任务平衡问题：遗传算法主程序 % 目标：固定节拍 cycleTime，最小化工位数量 % 编码：实数优先级向量，第 i 个基因位对应任务 i 的优先级 clear; clc; rng(42); % 固定随机种子，保证结果可复现 %% 1. 输入数据：任务时间与前置约束 taskTimes = [4 6 5 2 3 7 3 4 6 10]; % 各任务处理时间 nTasks = length(taskTimes); cycleTime = 10; % 产线节拍 precedence = cell(nTasks, 1); precedence{1} = []; precedence{2} = 1; precedence{3} = []; precedence{4} = 3; precedence{5} = [3 4]; precedence{6} = [2 5]; precedence{7} = 6; precedence{8} = 7; precedence{9} = 8; precedence{10} = [6 9]; %% 2. 遗传算法参数 popSize = 120; % 种群规模 maxGen = 300; % 最大迭代代数 pc = 0.90; % 交叉概率 pm = 0.20; % 变异概率 eliteNum = 4; % 精英保留数量 tourSize = 3; % 锦标赛选择规模 beta = 0.3; % 负荷均衡惩罚系数 %% 3. 初始化种群（均匀随机） pop = rand(popSize, nTasks); %% 4. 进化主循环 bestFitness = zeros(maxGen, 1); bestStations = zeros(maxGen, 1); for gen = 1:maxGen % 4.1 计算每个个体的适应度 fitness = zeros(popSize, 1); nStationsAll = zeros(popSize, 1); for i = 1:popSize [fitness(i), nStationsAll(i)] = albFitness(pop(i, :), ... taskTimes, precedence, cycleTime, beta); end % 4.2 精英保留：适应度最高的几个个体直接复制到下一代 [~, idx] = sort(fitness, 'descend'); elite = pop(idx(1:eliteNum), :); % 4.3 选择-交叉-变异生成新种群 newPop = zeros(popSize, nTasks); newPop(1:eliteNum, :) = elite; for k = eliteNum+1:2:popSize % 锦标赛选择两个父代 p1 = tournamentSelect(pop, fitness, tourSize); p2 = tournamentSelect(pop, fitness, tourSize); % 按交叉概率执行两点交叉 if rand < pc [c1, c2] = twoPointCrossover(p1, p2); else c1 = p1; c2 = p2; end % 按变异概率执行交换变异 if rand < pm, c1 = swapMutate(c1); end if rand < pm, c2 = swapMutate(c2); end if k+1 <= popSize newPop(k, :) = c1; newPop(k+1, :) = c2; else newPop(k, :) = c1; % 种群大小为奇数时最后只剩一个 end end pop = newPop; bestFitness(gen) = max(fitness); bestStations(gen) = min(nStationsAll); % 每 20 代打印一次进度，避免刷屏 if mod(gen, 20) == 0 fprintf('第 %3d 代 | 最佳适应度 %.4f | 最优工位数 %d\n', ... gen, bestFitness(gen), bestStations(gen)); end end %% 5. 输出最优解 [~, bestIdx] = max(fitness); bestChrom = pop(bestIdx, :); seq = topoSequence(bestChrom, precedence, nTasks); [nStations, stationAssign, stationTimes] = packSequence(seq, taskTimes, cycleTime); fprintf('\n=== 最优解 ===\n'); fprintf('工位数: %d (理论下界 %d)\n', nStations, ceil(sum(taskTimes) / cycleTime)); for s = 1:nStations tasksInStation = find(stationAssign == s); fprintf('工位 %d: 任务 %s | 负荷 %.1f\n', ... s, mat2str(tasksInStation), stationTimes(s)); end

主程序的流程是标准的遗传算法框架：初始化 → 计算适应度 → 精英保留 → 选择交叉变异 → 更新种群 → 循环。pc = 0.90表示 90% 的配对个体执行交叉，pm = 0.20表示每个子代个体有 20% 概率执行一次变异，这个概率针对单个个体而不是单个基因位，设置太高会让搜索退化成随机扰动。eliteNum = 4保证历史上最好的几个解不会因为交叉变异被破坏。

4.2 选择、交叉、变异算子：锦标赛、两点交叉与交换变异

选择算子用锦标赛选择，本质是随机抽几个个体，让适应度最高的胜出。锦标赛规模tourSize控制选择压力，设为 3 是经验值——太大容易过早收敛到局部最优，太小会让搜索过于随机。以下三个文件分别保存为tournamentSelect.m、twoPointCrossover.m、swapMutate.m。

function winner = tournamentSelect(pop, fitness, tourSize) % 锦标赛选择：随机抽取 tourSize 个个体，返回适应度最高者 n = size(pop, 1); idx = randperm(n, tourSize); % 随机抽 tourSize 个下标 [~, best] = max(fitness(idx)); % 找适应度最高的那个 winner = pop(idx(best), :); end

function [c1, c2] = twoPointCrossover(p1, p2) % 两点交叉：直接交换父代染色体的一段基因 % 优先级实数编码不产生重复基因，因此不需要 PMX 修复 n = length(p1); points = sort(randperm(n-1, 2)); % 随机两个断点，升序排列 a = points(1) + 1; % 交换区间的起点 b = points(2); % 交换区间的终点 c1 = p1; c2 = p2; c1(a:b) = p2(a:b); % 子代1从父代2取一段 c2(a:b) = p1(a:b); % 子代2从父代1取一段 end

function chrom = swapMutate(chrom) % 交换变异：随机交换两个基因位的优先级值 n = length(chrom); idx = randperm(n, 2); % 随机两个不同位置 chrom(idx) = chrom(flip(idx)); % 交换两个位置的值 end

两点交叉实现的逻辑说明：randperm(n-1, 2)返回两个不同的随机断点，排序后确定交换区间。之所以取[points(1)+1, points(2)]而不是直接取断点本身，是为了保证交换区间至少包含一个基因位且覆盖范围可控。这里不需要 PMX 是因为优先级编码中同一个任务只出现在固定基因位，不存在排列编码里那种「一个值重复出现两次、另一个值丢失」的冲突，子代永远合法。

交换变异每次只交换两个任务对应的优先级值。值得强调的是：变异强度由pm控制，一次变异只动两个位置，避免大范围扰动摧毁已经积累的优质基因片段。如果你发现收敛到局部最优，优先调大pm到 0.3 而不是改成多基因变异。

4.3 运行结果与最优解输出

配套的解码函数有三个，分别保存为albFitness.m、topoSequence.m、packSequence.m。先把适应度函数写出来，它内部调用另外两个。

function [fitVal, nStations] = albFitness(chromosome, taskTimes, precedence, cycleTime, beta) % 适应度函数：工位数越少越好，工位负荷越均衡越好 seq = topoSequence(chromosome, precedence, length(taskTimes)); [nStations, ~, stationTimes] = packSequence(seq, taskTimes, cycleTime); meanTime = mean(stationTimes); imbalance = sqrt(mean((stationTimes - meanTime).^2)) / cycleTime; fitVal = 1 / (nStations + beta * imbalance); % 分母越小，适应度越大 end

function seq = topoSequence(chromosome, precedence, nTasks) % 拓扑排序：按优先级生成满足前置约束的任务序列 seq = zeros(1, nTasks); assigned = false(1, nTasks); % 记录任务是否已排入序列 for step = 1:nTasks candidates = find(~assigned); % 所有未分配任务 valid = false(size(candidates)); for j = 1:length(candidates) task = candidates(j); pre = precedence{task}; if isempty(pre) || all(assigned(pre)) valid(j) = true; % 前置任务全部完成才进入候选池 end end pool = candidates(valid); [~, bestPos] = max(chromosome(pool)); % 候选池中优先级最高 seq(step) = pool(bestPos); assigned(pool(bestPos)) = true; % 标记为已分配 end end

function [nStations, stationAssign, stationTimes] = packSequence(seq, taskTimes, cycleTime) % 顺序装箱：按拓扑序列把任务装入工位，剩余时间不够就开新工位 nTasks = length(seq); stationAssign = zeros(1, nTasks); % 记录每个任务所属工位 stationTimes = []; % 记录每个工位的已用时间 currentStation = 1; remainingTime = cycleTime; for k = 1:nTasks task = seq(k); t = taskTimes(task); if t <= remainingTime % 当前工位剩余时间足够，放入 stationAssign(task) = currentStation; remainingTime = remainingTime - t; else % 放不下，新开工位 stationTimes(end + 1) = cycleTime - remainingTime; currentStation = currentStation + 1; stationAssign(task) = currentStation; remainingTime = cycleTime - t; end end stationTimes(end + 1) = cycleTime - remainingTime; nStations = currentStation; end

topoSequence的时间复杂度是 O(n²)，对几十个任务的装配线足够快。参数说明：chromosome是优先级向量，数值大的任务优先；assigned是布尔数组，避免任务被重复排入序列；valid数组逐任务检查前置约束，保证输出的序列一定合法。packSequence里需要注意：如果某个任务时间恰好等于remainingTime，它会落入t <= remainingTime分支，工位刚好填满，逻辑正确；只有当t > remainingTime时才开新站，所以工位负荷永远不会超过节拍。

跑完这段代码，你会在命令行看到类似「工位数: 5 (理论下界 5)」的输出，说明算法找到了最优解。如果看到工位数是 6，大概率是pm太小或者maxGen不够，按第 5 章的排查思路处理。

5. 跑装配线平衡的遗传算法避坑：5 个高频翻车点与排查方法

遗传算法这类启发式算法最大的特点就是「不报错不等于正确」。代码能跑出结果，不代表结果合理。这一章记录我在实际调试装配线平衡代码时遇到的 5 个高频问题，全部按「现象 → 原因 → 解决」展开。

5.1 前置约束有环：解码器直接卡死

现象：程序运行后长时间没有输出，按 Ctrl+C 中断后发现卡在topoSequence里。

原因：前置约束存在环，比如任务 A 的前驱是 B，任务 B 的前驱又是 A。此时每一轮迭代的候选池都为空，pool(bestPos)索引越界或陷入死循环。很多产线数据是从结构树导入的，稍不留神就会出现回边。

解决：在任何一次进化之前，先跑一次纯拓扑排序，统计能排出的任务数量。如果排出的任务数小于nTasks，直接报错停止。检查代码很简单：

testSeq = topoSequence(rand(1, nTasks), precedence, nTasks); assert(length(testSeq) == nTasks, '前置约束存在环，请检查输入数据');

这行断言放在主程序初始化之后，代价极小，能省掉后面所有莫名其妙的运行卡顿。

5.2 任务时间超过节拍：工位负荷出现负数

现象：输出的stationTimes出现大于cycleTime的数值，甚至某些工位时间显示为负。

原因：输入数据里存在taskTimes(i) > cycleTime的任务。packSequence在放不下时会执行remainingTime = cycleTime - t，如果t > cycleTime，剩余时间直接变成负数，后续任务全部错乱。

解决：在读取数据后加两个断言，第一判断最大任务时间是否小于等于节拍，第二判断任务总数和前置约束数量是否一致：

assert(max(taskTimes) <= cycleTime, '存在任务时间超过节拍，请调整节拍或拆分任务'); assert(length(taskTimes) == length(precedence), '任务时间与前置约束数量不匹配');

实际产线里，如果真有任务时间超过节拍，通常的做法是把该任务拆成多个工位协同完成，或者在瓶颈工位增加并行工位，而不是硬塞给遗传算法。

5.3 适应度区分度不足：进化到第 50 代就停滞

现象：最优工位数在前几十代就稳定在某个值，比如 6，后面 200 代完全不动，输出一直报 6。

原因：适应度函数如果是1 / nStations，当种群中大量个体的工位数都是 6 时，它们的适应度完全相同，锦标赛选择在它们之间没有区分度，交叉变异再多也无法引导搜索方向。

解决：把适应度换成带负荷均衡惩罚的版本，即1 / (nStations + beta * imbalance)。同样工位数为 6 的个体，负荷标准差小的胜出。这个改动会让算法在工位数相同的解里继续优化负荷分布，并且大量的实验表明，均衡惩罚项间接提升了搜索到更少工位数的概率，因为它保住了「接近最优」的解。

5.4 随机种子没固定：结果不可复现

现象：同一份代码连续运行两次，一次得到 5 个工位，另一次得到 6 个工位；或者调试时发现改了一个无关参数，结果大变。

原因：rand、randperm依赖全局随机数流，每次打开 MATLAB 的随机种子不同，整个进化过程就完全不同。这在调试交叉算子时极具迷惑性——你以为是算子写错了，其实是随机性带来的噪音。

解决：主程序开头固定rng(42)，调试阶段不要改。等到最终要产出真实方案的阶段，跑 10 轮随机种子，取工位数最少、负荷最均衡的解作为最终方案。固定种子的意义不是消除随机性，而是让每次调试的对照实验在相同条件下进行。

5.5 交叉算子选错：排列编码和优先级编码不是一回事

现象：套用网上的排列编码遗传算法代码，用 PMX 交叉算子跑本问题，要么报索引错误，要么结果很差。

原因：PMX 是为「染色体是任务排列」设计的算子，它的核心动作是修复重复基因。我的优先级编码采用「基因位 = 任务编号，基因值 = 优先级」的结构，基因位之间天然独立，PMX 的修复逻辑反而会破坏基因与任务的对应关系。交叉算子必须与编码方式匹配，这是遗传算法里最容易踩的隐形坑。

解决：优先级编码用普通两点交叉或均匀交叉即可，不要用 PMX、顺序交叉。如果你拿到的源码是排列编码，先花十分钟把它的解码器看懂，再决定是否改造为自己的编码。直接替换算子是一种危险的玄学操作，结果不可控。

6. 验证与进阶：用已知最优算例确认正确性，向第二类问题扩展

遗传算法给出的结果是否正确，必须有一个参照物。我用前面这份 10 任务数据做一个验证：总任务时间sum(taskTimes) = 50，节拍cycleTime = 10，理论下界是ceil(50/10) = 5个工位。人工可以排出 5 工位方案：工位 1 放任务 1、2（负荷 10），工位 2 放任务 3、4、5（负荷 10），工位 3 放任务 6、7（负荷 10），工位 4 放任务 8、9（负荷 10），工位 5 放任务 10（负荷 10）。这是一个完美的满负荷方案，因此最优解一定是 5。你运行代码后如果得到 5，说明编码、解码、选择、交叉、变异整套逻辑没有致命错误；如果得到 6，按第 5 章排查参数。

向第二类问题扩展只需要改两处。第一，解码器不再按固定节拍装箱，而是给定工位数量numStations，把任务按拓扑序装入这numStations个工位，记录每个工位的负荷。第二，适应度函数改成工位最大负荷的倒数：

fitVal = 1 / max(stationTimes); % 第二类问题：最小化最大负荷

这种扩展对于有场地限制的产线改造非常实用。我的习惯是先把第一类问题的代码跑通、验证正确，再复制改造为第二类，避免两个目标混在一个版本里互相干扰。

另一个我更推荐的实用习惯是：每代都把精英个体的染色体单独保存到矩阵里，而不是只保存适应度数值。这样进化结束后，你可以随时把任意一代的精英重新解码，观察工位分配随迭代的演变过程；如果客户中途改了节拍，也可以用精英染色体直接重算，不必重新跑完整进化流程。这比只输出一个最终答案的方案，在现场沟通时好用得多——你能告诉对方「这个方案在第几代就收敛了，稳定性如何」，而不是甩一个黑匣子结果。

这套代码我在类似产线场景里改过很多次，最大的体会是：参数需要按产线规模调，但编码和解码器一旦设计正确，几乎不需要大改。如果你准备把这道题用到真实产线，先从这套优先级编码开始，永远不要把排列编码和它混用。希望帮到你。

本文还有配套的精品资源，点击获取