简介一份用于装配生产线任务平衡问题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 eliteNum1: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 k1 popSize newPop(k, :) c1; newPop(k1, :) 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), :); endfunction [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取一段 endfunction 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); % 分母越小适应度越大 endfunction 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 endfunction [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; endtopoSequence的时间复杂度是 O(n²)对几十个任务的装配线足够快。参数说明chromosome是优先级向量数值大的任务优先assigned是布尔数组避免任务被重复排入序列valid数组逐任务检查前置约束保证输出的序列一定合法。packSequence里需要注意如果某个任务时间恰好等于remainingTime它会落入t remainingTime分支工位刚好填满逻辑正确只有当t remainingTime时才开新站所以工位负荷永远不会超过节拍。跑完这段代码你会在命令行看到类似「工位数: 5 (理论下界 5)」的输出说明算法找到了最优解。如果看到工位数是 6大概率是pm太小或者maxGen不够按第 5 章的排查思路处理。5. 跑装配线平衡的遗传算法避坑5 个高频翻车点与排查方法遗传算法这类启发式算法最大的特点就是「不报错不等于正确」。代码能跑出结果不代表结果合理。这一章记录我在实际调试装配线平衡代码时遇到的 5 个高频问题全部按「现象 → 原因 → 解决」展开。5.1 前置约束有环解码器直接卡死现象程序运行后长时间没有输出按 CtrlC 中断后发现卡在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); % 第二类问题最小化最大负荷这种扩展对于有场地限制的产线改造非常实用。我的习惯是先把第一类问题的代码跑通、验证正确再复制改造为第二类避免两个目标混在一个版本里互相干扰。另一个我更推荐的实用习惯是每代都把精英个体的染色体单独保存到矩阵里而不是只保存适应度数值。这样进化结束后你可以随时把任意一代的精英重新解码观察工位分配随迭代的演变过程如果客户中途改了节拍也可以用精英染色体直接重算不必重新跑完整进化流程。这比只输出一个最终答案的方案在现场沟通时好用得多——你能告诉对方「这个方案在第几代就收敛了稳定性如何」而不是甩一个黑匣子结果。这套代码我在类似产线场景里改过很多次最大的体会是参数需要按产线规模调但编码和解码器一旦设计正确几乎不需要大改。如果你准备把这道题用到真实产线先从这套优先级编码开始永远不要把排列编码和它混用。希望帮到你。本文还有配套的精品资源点击获取
简介一份用于装配生产线任务平衡问题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 eliteNum1: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 k1 popSize newPop(k, :) c1; newPop(k1, :) 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), :); endfunction [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取一段 endfunction 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); % 分母越小适应度越大 endfunction 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 endfunction [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; endtopoSequence的时间复杂度是 O(n²)对几十个任务的装配线足够快。参数说明chromosome是优先级向量数值大的任务优先assigned是布尔数组避免任务被重复排入序列valid数组逐任务检查前置约束保证输出的序列一定合法。packSequence里需要注意如果某个任务时间恰好等于remainingTime它会落入t remainingTime分支工位刚好填满逻辑正确只有当t remainingTime时才开新站所以工位负荷永远不会超过节拍。跑完这段代码你会在命令行看到类似「工位数: 5 (理论下界 5)」的输出说明算法找到了最优解。如果看到工位数是 6大概率是pm太小或者maxGen不够按第 5 章的排查思路处理。5. 跑装配线平衡的遗传算法避坑5 个高频翻车点与排查方法遗传算法这类启发式算法最大的特点就是「不报错不等于正确」。代码能跑出结果不代表结果合理。这一章记录我在实际调试装配线平衡代码时遇到的 5 个高频问题全部按「现象 → 原因 → 解决」展开。5.1 前置约束有环解码器直接卡死现象程序运行后长时间没有输出按 CtrlC 中断后发现卡在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); % 第二类问题最小化最大负荷这种扩展对于有场地限制的产线改造非常实用。我的习惯是先把第一类问题的代码跑通、验证正确再复制改造为第二类避免两个目标混在一个版本里互相干扰。另一个我更推荐的实用习惯是每代都把精英个体的染色体单独保存到矩阵里而不是只保存适应度数值。这样进化结束后你可以随时把任意一代的精英重新解码观察工位分配随迭代的演变过程如果客户中途改了节拍也可以用精英染色体直接重算不必重新跑完整进化流程。这比只输出一个最终答案的方案在现场沟通时好用得多——你能告诉对方「这个方案在第几代就收敛了稳定性如何」而不是甩一个黑匣子结果。这套代码我在类似产线场景里改过很多次最大的体会是参数需要按产线规模调但编码和解码器一旦设计正确几乎不需要大改。如果你准备把这道题用到真实产线先从这套优先级编码开始永远不要把排列编码和它混用。希望帮到你。本文还有配套的精品资源点击获取
