前阵子帮一个做排产仿真的团队搭排程模块,目标很朴素:把一个中等规模作业车间的最大完工时间(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) 个工件的最后一道工序的完工时间。
约束条件主要有两个硬约束:
- 工序顺序约束:同一个工件的第 k+1 道工序,必须等第 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 |
|---|---|---|
| 工件1 | 5 | 4 |
| 工件2 | 6 | 3 |
| 工件3 | 4 | 7 |
对应的机器约束矩阵可能是:
| 工件 | 工序1机器 | 工序2机器 |
|---|---|---|
| 工件1 | 1 | 2 |
| 工件2 | 2 | 1 |
| 工件3 | 1 | 2 |
这两个矩阵就是调度问题的“全部输入”。后续的适应度函数,不论用什么算法,本质都是在给定这两个矩阵的前提下,对一组工序顺序求 makespan。
2.3 麻雀的连续位置和离散工序序列:ROV 排序映射的底层原理
麻雀算法原始设计是在连续空间里优化,位置向量是一串实数。但车间调度的解是离散的工序序列。怎么把连续向量变成合法的工序序列?这里用到了随机键排序映射,简称 ROV。
ROV 的思路非常直接:假设一个麻雀个体的位置是 L 维连续向量,其中 L = N × M(总工序数)。先把这 L 个连续值按照大小从小到大排序,得到它们在原向量中的索引顺序,这个索引顺序是一个 1 到 L 的排列。然后对这个排列里的每个数字,按照“编号取模”的方式映射回工号,同时用计数器保证同一个工件出现 M 次就对应其 M 道工序。
举个例子。假设 N=3,M=2,L=6。一只麻雀的位置向量是:
[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.4 | 0.8 | 1.1 | 5.2 | 3.3 | 0.5 |
|---|---|---|---|---|---|---|
| 排序后索引 | 2 | 6 | 3 | 1 | 5 | 4 |
| 模映射工件号 | 2 | 3 | 3 | 1 | 2 | 1 |
| 展开工序 | 2-1 | 3-1 | 3-2 | 1-1 | 2-2 | 1-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不过从我的实际调试经验看,初始范围不必太大,lb=0, ub=1就够了。把范围设太大反而会让初始种群过于分散,前期适应度极差,浪费不少迭代次数。
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 = numProducer+1: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 | 约 55 | 63.4 | 61.8 | 57.9 | 55 |
| 10×10 | 约 950 | 987 | 971 | 954 | 945 |
| 15×10 | 约 1285 | 1362 | 1338 | 1295 | 1278 |
从数据可以清楚看到,麻雀算法在三档规模下都比另外两个算法平均表现更好,而且它找到的最好结果已经落到了已知较优区间内。这说明在这个问题上,麻雀算法的探索能力和收敛能力综合起来更强。
不过必须补充一句:元启发式算法本身有随机性,单次运行结果会有波动。我这组数据是在相同实验条件下跑了 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”的范畴,可以直接拿去对接生产排产模块了。最关键的是,这个项目让我彻底明白了一件事:元启发式算法本身不神奇,真正的工作量永远在问题建模和解码这块,把连续位置和离散调度之间那座桥搭稳固,后面所有扩展都是顺水推舟的事。