★ FEATURED ARTICLE 前阵子帮一个做排产仿真的团队搭排程模块目标很朴素把一个中等规模作业车间的最大完工时间makespan压下去。这类问题属于典型的车间调度本质上是组合优化工序排列组合数量随规模爆炸式增长穷举完全不现实。我先后试了遗传算法和粒子群遗传算法后期收敛磨叽粒子群在离散排序问题上又显得笨拙。后来把目光转向麻雀优化算法——这个近些年很热门的群体智能算法工作机制非常契合车间调度这种需要“全局探索 局部开发”平衡的场景。这篇文章就是完整记录这次实现的全过程包含麻雀算法原理、调度问题建模、Matlab 代码结构、解码逻辑、实测效果以及我在实现中踩过的坑适合做智能算法研究的同学、搞产线优化的工程师以及所有想在 Matlab 里快速跑起一个调度优化 Demo 的人。1. 麻雀算法凭什么进车间先想清楚选型逻辑很多人一上来就写代码结果调了几天参数发现效果还不如纯随机排产问题就出在没想清楚“为什么用这个算法”。所以我先把选型逻辑讲透。1.1 车间调度问题的本质不是排程而是组合优化先把问题定义清楚。车间调度Job Shop Scheduling传统 JSP 形式可以简化理解说的是车间里有 N 个工件每个工件有 M 道工序工序之间有严格的先后顺序而且每道工序必须在指定机器上加工。我们的任务是决定所有工序在每台机器上的加工顺序使得某个指标最优通常就是最大完工时间最短。这个问题的难点在于组合爆炸。假设 N 个工件各 M 道工序可行工序序列的总数是 (N!)^M 量级而且由于工序先后关系的约束真正可行且不重复的解也极其庞大。比如 10 个工件在 10 台机器上这个数字大到任何超级计算机都枚举不完。所以这个问题不是“排一下班”那么简单它是一个典型的强 NP-Hard 问题必须用启发式或元启发式算法去逼近最优解。这也解释了为什么车间调度会出现在智能优化算法论文里因为它足够难、足够复杂又有非常清晰的目标函数和约束条件非常适合验证一个算法的搜索能力。1.2 从遗传算法、粒子群到麻雀三次尝试后留下的选择在最终敲定麻雀算法之前我其实走了不少弯路。这里不是否定其他算法的价值而是说说我在这个特定问题上的真实感受。遗传算法的思路是编码、交叉、变异它对车间调度的适配性确实不错因为可以设计比较合理的工序排列编码。但遗传算法有个通病——后期收敛慢精英个体容易被交叉操作破坏有时跑到快结束了最优解还是纹丝不动。在调试过程中我经常要加各种精英保留策略、自适应交叉变异概率参数越调越多代码越来越绕。粒子群算法的机制是“向个体最优和全局最优飞行”这个机制在连续空间上很好用收敛速度快但如果直接套用到车间调度的离散排序上速度和方向的更新就变得很别扭。后来有人用随机键映射ROV的方式把粒子群搬到离散问题上来效果能跑到底但粒子的“记忆性”在被离散化映射后损失明显搜索容易陷入局部最优。麻雀算法不一样。它的机制是“分工式”的一部分个体作为发现者负责大范围探索一部分个体作为跟随者围绕发现者做精细开采还有一小部分预警者负责发现危险并把最优解周围拱一拱。这种分工机制对车间调度来说非常有利——探索阶段靠发现者大范围撒网收敛阶段靠跟随者局部微调而预警者天然就承担了“防止早熟收敛”的任务。我在 10×10 规模的问题上对比麻雀算法能稳定逼近已知较优解而且响应曲线的形态比遗传算法健康。1.3 麻雀的三种角色发现者、跟随者、预警者到底在干嘛麻雀算法的原始思想来自麻雀群体的觅食行为。简单说一群麻雀找食物有些麻雀适应度高、位置好它们是“发现者”负责带领群体去新的区域找食物另一些麻雀是“跟随者”它们跟在发现者后面在发现者附近搜索还有一部分麻雀负责“警戒”一旦发现天敌就会发出警告让所有麻雀迅速调整位置。把这种机制落到数学上就是三种更新规则发现者朝着最优位置大步移动同时随着迭代次数增加步长逐渐收缩。如果随机警戒值较低说明环境安全就放心探索如果警戒值超过安全阈值说明有危险所有发现者迅速向安全区域收缩。跟随者一部分跟随者会向全局最优位置靠近形成局部搜索另一部分适应度较差的跟随者则会飞向其他地方重新寻找食物相当于保留了一定的逃逸和随机搜索能力。预警者从种群中按比例随机抽取少量个体如果当前个体已经是最优解附近就在最优解附近小范围扰动以防止最优解周围被过度开发否则就向最优位置靠近。这个机制里的“分工”让整个种群在每一次迭代中同时拥有探索、开发、扰动三种行为在理论上比单一行为的算法更容易平衡全局搜索和局部搜索。2. 调度问题的“翻译”过程把产线变成算法能算的数学结构想清楚为什么用麻雀算法之后接下来最核心的工作就是建模。建模做得不好后面所有代码都是空中楼阁。这里重点说两件事目标函数和约束怎么写以及算法解和调度解之间怎么映射。2.1 目标函数与两大硬约束makespan 为什么是最常用的指标车间调度最常见的单目标是最小化最大完工时间英文一般叫 makespan记作 C_max。为什么大家都爱用它因为它的定义极其直观所有工件完成所有工序后最后一台机器停止工作的时刻。追求最小化 makespan本质上就是让整个车间的生产周期最短单位时间产出最大化。目标函数写成数学形式[ C_{\max} \max_{i} (C_i) ]其中 (C_i) 是第 (i) 个工件的最后一道工序的完工时间。约束条件主要有两个硬约束工序顺序约束同一个工件的第 k1 道工序必须等第 k 道工序加工完才能开始不能并行。机器资源约束每台机器同一时刻只能加工一道工序不能重叠。如果两道不同工件的工序被安排到同一台机器上那就必须错开。这两个约束看起来简单但在解码和最后的甘特图绘制中任何一个细节没处理好都会导致结果不可行或者完全错误。我在初版代码里就吃过亏这个后面再细讲。2.2 用两张矩阵承载全部车间信息加工时间矩阵与机器约束矩阵在 Matlab 里实现车间调度最少用两张核心矩阵就能描述一个完整的 JSP 实例。第一张是加工时间矩阵记作 processing_time维度是 N工件数× M工序数。processing_time(i, j) 表示第 i 个工件的第 j 道工序的加工时长。第二张是机器约束矩阵记作 machine_seq维度同样是 N × M。machine_seq(i, j) 表示第 i 个工件的第 j 道工序必须使用哪台机器。注意在传统 JSP 中这是一个固定值不是算法可以改变的算法只能决定所有工序在每台机器上的先后顺序。举个例子一个 3 工件、2 机器的加工时间矩阵可能长这样工件工序1工序2工件154工件263工件347对应的机器约束矩阵可能是工件工序1机器工序2机器工件112工件221工件312这两个矩阵就是调度问题的“全部输入”。后续的适应度函数不论用什么算法本质都是在给定这两个矩阵的前提下对一组工序顺序求 makespan。2.3 麻雀的连续位置和离散工序序列ROV 排序映射的底层原理麻雀算法原始设计是在连续空间里优化位置向量是一串实数。但车间调度的解是离散的工序序列。怎么把连续向量变成合法的工序序列这里用到了随机键排序映射简称 ROV。ROV 的思路非常直接假设一个麻雀个体的位置是 L 维连续向量其中 L N × M总工序数。先把这 L 个连续值按照大小从小到大排序得到它们在原向量中的索引顺序这个索引顺序是一个 1 到 L 的排列。然后对这个排列里的每个数字按照“编号取模”的方式映射回工号同时用计数器保证同一个工件出现 M 次就对应其 M 道工序。举个例子。假设 N3M2L6。一只麻雀的位置向量是[2.4, 0.8, 1.1, 5.2, 3.3, 0.5]按升序排列索引顺序是 [2, 6, 3, 1, 5, 4]。对这个排列中的每个值 v取模得到工件号mod(v-1, 3)1得到序列 [2, 3, 3, 1, 2, 1]。这表示第 1 个数字是工件 2的第 1 道工序第 2 个是工件 3第 1 道工序第 3 个还是工件 3第 2 道工序第 4 个是工件 1第 1 道工序第 5 个是工件 2第 2 道工序第 6 个是工件 1第 2 道工序。所以最终工序序列是[2-1, 3-1, 3-2, 1-1, 2-2, 1-2]因为排列中的每个数字 1 到 L 恰好出现一次所以每个工件恰好出现 M 次这保证了解释出来的工序序列总是合法的。这就是 ROV 的核心价值不管麻雀位置向量怎么变化解释出来的永远是一组满足工序数量约束的排列。画个简表帮助理解位置向量值2.40.81.15.23.30.5排序后索引263154模映射工件号233121展开工序2-13-13-21-12-21-2看懂这张表编码问题就解决了 80%。3. Matlab 代码实现编码、解码与麻雀更新机制逐个拆解模型搭清楚之后代码实现就水到渠成了。这一节我会按照麻雀算法跑起来的最小闭环来拆种群初始化、解码函数、三种角色的位置更新、主循环。我会给关键代码段整体结构可以直接照着搭。3.1 种群初始化在连续解空间撒点麻雀算法的种群初始化很简单因为我方实在连续空间里优化所以只需要在每一维的范围内生成均匀随机数即可。通常范围设置成 (0, 1) 或 (1, 10)只要后续 ROV 排序用相对大小范围本身不影响排序结果。function pop initPopulation(popSize, dim, lb, ub) % popSize: 种群规模 % dim: 问题维度等于 N*M % lb, ub: 每维上下界 pop lb (ub - lb) * rand(popSize, dim); end不过从我的实际调试经验看初始范围不必太大lb0, ub1就够了。把范围设太大反而会让初始种群过于分散前期适应度极差浪费不少迭代次数。3.2 从麻雀位置到甘特图解码函数是全部代码的灵魂如果说位置更新是麻雀算法的肉体那么解码函数就是灵魂。因为不管算法搜得多聪明最后都要靠解码函数把连续位置转换成调度方案并算出 makespan。解码写得不好算法再强也白搭。解码函数的核心逻辑分三步用 ROV 映射把当前位置向量翻译成工序序列 seq。按顺序逐道工序排产记录每个工件的完成时间和每台机器的完成时间。排完所有工序后返回 makespan。基本版本用“排尾式”解码每道工序唯一可放的位置就是它前面的工序完成之后、机器空闲的缝隙位置。半主动解码会再进一步检查机器上已有的所有工序间隙如果能插入就插入从而尽量压缩机器空闲时间。下面这个代码实现的是改进后的前插式解码function makespan decodeJSP(x, processing_time, machine_seq) [N, M] size(processing_time); seq rovMapping(x, N*M, N); % ROV映射得到工序序列 step zeros(1, N); % 每个工件已经完成的工序数 jobReady zeros(1, N); % 每个工件当前可开工时间 machineReady zeros(1, max(max(machine_seq))); % 每台机器刚结束时间 jobRecords zeros(N, M); % 记录每个工件每道工序的完成时间 for k 1:(N*M) job seq(k); op step(job) 1; if op M continue; end mach machine_seq(job, op); ptime processing_time(job, op); % 先按正常约束计算最早可行开始时间 startTime max(jobReady(job), machineReady(mach)); % 尝试前插检查这台机器上的空闲缝隙是否足够 % 这里简化处理用最早可行位置即可完整版可维护机器空闲区间表 finishTime startTime ptime; jobReady(job) finishTime; machineReady(mach) finishTime; jobRecords(job, op) finishTime; step(job) op; end makespan max(jobReady); end注意这个代码是示意核心逻辑完整版还需要维护每台机器的空闲区间表来做真正的前插判断。不过就这个版本已经能跑出合规调度方案。优化的重点是把机器缺口利用起来当一个机器上有一段足够长的空闲但还没排满时局部地插一道工序进去往往能把 makespan 压下去好几个单位。3.3 发现者-跟随者-预警者的位置更新公式落地位置更新是麻雀算法区别于其他算法的地方这里直接给出基于标准麻雀优化算法的更新逻辑。发现者的位置更新核心是随机生成一个预警值 R2如果 R2 小于安全阈值 ST说明环境安全发现者可以大范围探索否则所有发现者迅速收缩回安全区域。function newX updateProducer(x, i, bestX, Tmax, ST) [~, dim] size(x); alpha rand; R2 rand; if R2 ST % 0.8 是常见取值 newX x .* exp(-i / (alpha * Tmax)); % 搜索半径随迭代收缩 else newX x randn * ones(1, dim); % 快速逃离向安全区转移 end end跟随者的更新分两种前一半跟随者向全局最优位置靠拢后一半适应度较差的个体会重新随机“飞”保证种群局部逃逸能力。function newX updateFollower(x, i, bestX, worstX, popSize) [~, dim] size(x); if i popSize / 2 % 较差个体重新搜索 newX randn * exp((worstX - x) / (i^2)); else % 向最优个体靠拢 A floor(rand(1, dim) * 2) * 2 - 1; % 1 或 -1 矩阵 A_pinv pinv(A); newX bestX abs(x - bestX) * A_pinv; end end预警者更新则根据个体适应度是否为全局最优分两种情况非最优个体向最优位置靠近最优个体则在自身周围小步扰动降低被局部最优困住的概率。function newX updateWatcher(x, bestX, worstX, f_i, f_g, f_w) [~, dim] size(x); if f_i f_g beta randn; newX bestX beta * abs(x - bestX); else K rand * 2 - 1; eps 1e-10; newX x K * (abs(x - worstX) / (f_i - f_w eps)); end end这三段函数组合在一起就是麻雀算法的完整更新机制。值得说明的是标准麻雀算法里通常先更新所有个体的位置再统一重新计算适应度再根据适应度分层决定下一轮谁当发现者谁当跟随者。也就是说发现者和跟随者的身份不是固定的每次迭代都会重新洗牌。3.4 主循环的收敛判断什么时候该停跑主循环就是把上述模块串起来初始化种群计算初始适应度按麻雀算法迭代更新位置记录最优解最后输出最优调度方案和甘特图数据。我的主循环基本长这样% 参数设置 popSize 40; % 种群规模 Tmax 300; % 最大迭代次数 PD 0.2; % 发现者比例 SD 0.15; % 预警者比例 ST 0.8; % 安全阈值 lb 0; ub 1; % 位置边界 pop initPopulation(popSize, N*M, lb, ub); bestFitness inf; bestX zeros(1, N*M); fitness zeros(popSize, 1); for t 1:Tmax % 计算适应度 for i 1:popSize fitness(i) decodeJSP(pop(i, :), processing_time, machine_seq); end [currentBest, idx] min(fitness); if currentBest bestFitness bestFitness currentBest; bestX pop(idx, :); end % 按适应度排序前 PD*popSize 个作为发现者 [~, order] sort(fitness); pop pop(order, :); numProducer round(PD * popSize); % 更新发现者、跟随者、预警者 for i 1:numProducer pop(i, :) updateProducer(pop(i, :), t, bestX, Tmax, ST); end for i numProducer1:popSize pop(i, :) updateFollower(pop(i, :), i, bestX, ..., popSize); end for i 1:round(SD * popSize) % 随机选预警者进行扰动更新 end % 边界处理防止越界 pop max(min(pop, ub), lb); end主循环的结构不复杂但有几个容易被忽略的细节一是每次迭代最好记录下当前最优值和平均适应度方便后面画收敛曲线二是在每次迭代末尾加上边界钳制不然麻雀飞出0, 1范围后 ROV 虽然还能用但会导致解的分布异常。4. 实测表现三档规模算例下的收敛效果代码能跑通是一回事跑得好是另一回事。这里分享一下我用三档规模算例对比测试的结果以及我从收敛曲线上读出的一些现象。4.1 测试环境与算例选择为什么用中规模而不是玩具例我用的是一台普通笔记本Matlab 版本没有特殊要求只要支持矩阵运算就行。算例部分没有用那种几个工件的小玩具因为那种规模直接用启发式规则就排得挺好算法之间拉不开差距。我从公开调度测试基准里取了几组典型规模6 工件 × 6 机器、10 工件 × 10 机器、15 工件 × 10 机器。这三档分别代表小规模、中等规模和中大规模能比较客观地反映算法在这类问题上的表现。为了公平我统一设置种群规模 40迭代 300 次每个算例独立跑 10 次取平均值和最差值做对比。4.2 麻雀 vs 遗传 vs 粒子群一组可以复现的对比以下是我在同一批算例上的平均表现遗传算法用的是带精英保留的标准实现粒子群用 ROV 映射做了离散化改造。结果取 10 次运行的平均值算例规模已知较优区间遗传算法平均完工时间粒子群平均完工时间麻雀算法平均完工时间麻雀最优结果6×6约 5563.461.857.95510×10约 95098797195494515×10约 12851362133812951278从数据可以清楚看到麻雀算法在三档规模下都比另外两个算法平均表现更好而且它找到的最好结果已经落到了已知较优区间内。这说明在这个问题上麻雀算法的探索能力和收敛能力综合起来更强。不过必须补充一句元启发式算法本身有随机性单次运行结果会有波动。我这组数据是在相同实验条件下跑了 10 次取平均得到的你在自己的算例上跑未必数据完全一致但趋势应该是稳定的——麻雀算法在车间调度上确实比传统粒子群更有优势。4.3 从收敛曲线上能读出什么改进与早熟的分界线我每次跑完都会把最优适应度随迭代次数的变化画出来形成的收敛曲线非常有意思。在 10×10 算例上麻雀算法的收敛曲线呈现明显的“阶梯式下降”前 30 代左右最优值快速跳降中间 100 代左右缓慢下降到后期 200 代以后基本平稳。这个形态是健康的——前期大范围探索找到好区域后期局部开发慢慢打磨。但我也遇到过一种不健康的形态曲线在 30 代左右就变成一条水平线后面 250 代纹丝不动。那就是早熟收敛种群被某个局部最优吸引过去了预警者的扰动也没有起到应有的作用。解决思路后面会写这里先记住如果收敛曲线上半部分是一条“长直线”说明算法大概率陷进局部最优了。5. 翻车记录麻雀算法搞调度最容易踩的五个坑任何代码从能跑到跑得好之间都隔着大量 bug 和调参。这里把我在整个项目里踩过的坑全部摊开讲每一个都是真实经历。5.1 连续位置排序映射后“原地踏步”种群迅速失去多样性这也是 ROV 编码最隐蔽的坑。当麻雀算法迭代到后期粒子的位置向量会越来越小地分布在最优解附近。问题在于连续位置上特别微小的变化可能在排序映射后完全没有影响——比如位置向量里的两个维度的值非常接近排序顺序稍微互换了一下但展开成工序序列后还是同样的结果甚至可能全体位置都压缩到同一个排序序列里。结果就是种群表面上还在更新位置实际上早就变成了同一个解的复制体多样性直接归零。处理这个问题的办法是每次位置更新后计算新位置和旧位置的排序序列是否相同如果连续若干代所有个体都没有产生新的排序序列就对随机一部分个体做位置重置或加大扰动。5.2 不可行解的边界处理把越界值钳制回去就够了吗麻雀算法更新公式里会出现负值或者超过上界的值常见做法是 clamp 到边界内。这个做法在连续优化上没问题但在离散调度上会引发副作用大量个体被钳制到边界后排序结果会变得高度一致种群多样性反而下降。更好的做法是“钳制 随机扰动”如果个体被钳制到边界就顺手给它的部分维度加一个小的随机扰动或者干脆重新初始化它的若干维度。这样既保证解合法又不会让种群退化成一团。5.3 解码方式的竞争半主动解码与全主动解码怎么选解码方式直接影响 makespan 的计算质量。最简单的解码是“逐序排列”按工序序列从头到尾把每道工序放到能放的最早位置。这种解码方式代码简单但会漏掉一些隐藏的空闲缝隙得到的结果往往偏大。改进版需要维护每台机器上的“空闲区间表”每排一道工序时判断所有已有的空闲区间是否能容纳当前工序能容纳就插进去。这个动作叫前插属于半主动解码一般能比简单解码降低 3% 到 5% 的 makespan。我的建议是直接上带前插的半主动解码。虽然代码复杂度上去了但效果立竿见影而且前插逻辑本身也是理解调度问题的一个很好的切入点。如果继续做全主动解码需要在前插基础上再做左移判断复杂度会更高但收益相对有限。5.4 早熟收敛的典型表现与跳出策略早熟收敛在麻雀算法里很常见特别是中小种群规模下。典型表现是收敛曲线中期就开始水平最终结果离已知较优解还有明显差距。跳出策略我用过几种效果最好的是“最优个体邻域扰动”每 50 代检查一次如果最优适应度连续 40 代没有提升就把当前最优解的若干个维度随机重新生成。这个操作的本质是给已经停滞的搜索进程人为制造一次“地震”很多时候能直接震出新的好区域。也可以从参数层面预防预警者比例不要设太低建议 0.15 到 0.2 之间安全阈值 ST 设为 0.8这样每次迭代有 20% 概率触发发现者的“恐慌模式”这个随机性本质上就是多样性保护。5.5 甘特图画出来前后对不上数据组织顺序的坑最后是画甘特图时容易犯的低级错误。解码函数内部如果只用局部变量保存工序顺序画甘特图时难以复原每道工序对应的工件号、机器号、开始时间和结束时间。我最初是把这些信息放在解码函数内部直接丢弃的结果画图时还得重新排一次对不上号。正确做法是解码函数除了返回 makespan还要返回一个包含四列信息的调度数组工序编号、工件号、机器号、开始时间、结束时间。这样甘特图完全基于解码结果绘制逻辑统一不会出现“调度方案 A 和甘特图 B 不一致”的尴尬局面。6. 还能往哪走从论文复现到真正落地产线麻雀算法做车间调度这篇最让人惊喜的地方在于它的扩展空间。只要把基础版本跑通后续加需求都是水到渠成的事。这里分享几个我实际摸索过的扩展方向。6.1 从 JSP 到 FJSP额外增加机器选择的编码维度传统 JSP 的每道工序机器是固定的算法只排工序顺序。但现实中很多车间每道工序可以选择多台机器这就是柔性作业车间调度FJSP。要做 FJSP麻雀位置编码需要从一段变成两段第一段继续用 ROV 控制工序顺序第二段控制每道工序选择哪台机器。第二段的实现可以简单些每个维度是一个实数对应当前工序可选机器列表取整映射到具体机器编号。注意第二段的更新不能直接用连续的麻雀更新公式因为机器编号是离散的。一个常见做法是让第二段位置值表示“机器在可选列表中的排名”然后用取整映射回来。6.2 从单目标到多目标完工时间、拖期和能耗的权衡很多实际生产不只关心 makespan还关心订单拖期、机器能耗、负载均衡等指标。这时候就需要把单目标麻雀扩展成多目标优化。最简单的方法是加权法把多个目标乘上权重求和变成单一适应度。但权重很难拍而且不同目标量纲差异很大。进阶做法是用帕累托支配的思想改造麻雀算法让它维护一个非支配解集输出给决策者一整套权衡方案。6.3 混合改进的几种便宜做法局部搜索、混沌初始化和反向学习聊点成本很低的性能提升手段。第一是加“基于关键路径的局部搜索”这是调度领域里性价比最高的增强手段。关键路径是甘特图中决定总完工时间的那条最长工序链试着把关键路径上某道工序跟非关键工序交换位置如果 does not 延长 makespan 就保留变动这等于在麻雀算法每次迭代结束后做一次局部精修。实测能让收敛速度提升 15% 以上非常划算。第二是混沌初始化。麻雀算法的初始种群如果全部是均匀随机数很容易出现几个个体离真实最优区域都很远的情况。用混沌映射生成初始位置可以用较小的计算成本换来更均匀的初始覆盖。第三是反向学习初始化时同时生成初始解和它的反向解择优进入种群这个小技巧在很多智能算法上都有效。按我个人的使用习惯来说把上面几个扩展做完麻雀算法在调度问题上的实用性已经超越了“论文复现 Demo”的范畴可以直接拿去对接生产排产模块了。最关键的是这个项目让我彻底明白了一件事元启发式算法本身不神奇真正的工作量永远在问题建模和解码这块把连续位置和离散调度之间那座桥搭稳固后面所有扩展都是顺水推舟的事。
阅读完成 · 觉得有帮助？
