★ FEATURED ARTICLE 如果你常跟组合优化问题打交道一定遇到过这种局面问题听起来不复杂就是一组排班、一条路径、一批分配但数据量一上来精确求解器跑几分钟甚至几十分钟业务侧完全等不起。我自己的一个调度类实验也是这样任务规模从几千涨到几万之后原来的求解方案在时间上彻底不可用。后来我把核心引擎切成了局部搜索Local Search实现到跑通只用了很短时间单次求解压到秒级解质量也还处在可接受范围内。那以后我越来越觉得局部搜索不是“凑合用的土办法”而是一个非常值得优先考虑的工程化算法。这篇文章就围绕局部搜索展开它到底解决什么问题、动手前要定哪三件事、邻域怎么设计、卡在局部最优怎么办以及我实际编码时踩过的一些坑。1. 先搞清楚局部搜索和精确求解的分工很多人一听“启发式”“近似”这类词就先皱眉头好像不用精确算法就是偷懒。真实工程里的情况完全不是这样。组合优化问题的规模一旦上去精确算法本质是在和指数爆炸赛跑绝大多数时候跑不完。1.1 精确算法的天花板有多硬以旅行商问题为例20个城市看起来不大穷举所有环路的数量已经是千万亿级别到100个城市任何精确算法都很难在合理时间内给出全局最优。更麻烦的是现实问题还往往叠加排课里的师生冲突、调度里的资源占用、路径里的时间窗等一堆约束模型规模会快速膨胀。在这个背景下“必须找到全局最优”很多时候是一个伪需求。业务方真正要的通常是一个“能在几分钟甚至几秒内算出来、质量比现在的人工方案明显更好、且稳定可控”的解。这个需求恰恰是局部搜索擅长的事情。1.2 局部搜索的核心假设好解旁边通常还有好解局部搜索的思路特别朴素先拿到一个完整可行解然后在这个解的“附近”寻找更优解一直迭代到找不到明显改进为止。它不要求你一次性看出全局最优只需要相信“稍微改动现有方案结果可能变得更好”。用下山来类比你站在一片丘陵地带上看不到全貌但可以通过“脚下哪个方向在下降”逐步靠近谷底。局部搜索就是那个只看脚下一亩三分的登山者。它不保证最后找的是整个地区最低点但在大多数真实问题上这种策略非常有效。1.3 局部搜索与贪心算法、动态规划的关系这一点值得专门讲清楚因为三者的关系总被混淆。贪心算法从空解开始每一步做一个局部意义上最好的选择全程基本不回退动态规划依赖“最优子结构”把问题拆成子问题再组合但状态空间很容易爆炸局部搜索则完全走另一条路——先有一个完整解然后在完整解上反复做“小修改”允许因为改坏了再改回来。这三者不是对立的。我在实际工作中最常见的组合是用贪心快速构造一个还不错的初始解再用局部搜索继续打磨。动态规划也能在局部搜索中扮演子模块角色比如用来精确求解某个小范围子问题。方法起始状态搜索方向最优性保证典型适用规模精确求解无解从模型出发穷举/分支剪枝全局最优小规模、结构特殊贪心空解逐步构造单向向前不保证大规模常用于构造初始解动态规划子问题逐层递推自底向上看问题结构状态可控的中小规模局部搜索完整解邻域内来回调整局部最优大规模、要求快速出解2. 动手之前的三个关键选择局部搜索实现起来门槛不高但“能跑”和“跑出好结果”之间差别往往在动手前就已经决定了。解表示、评估函数、初始解这三件事值得先想清楚再写代码。2.1 解表示数据结构直接决定邻域操作成本很多人觉得解表示不过是个数据结构随便选就行。实际上你选一辆车邻域操作就跑在这辆车上交换、插入、逆转这些操作的复杂度是由表示方式决定的。最常见的几类表示排列类用数组保存顺序适合路径规划、任务排序。交换两个下标的元素是 O(1)但判断交换后是否有意义可能要 O(n)。分配类用“任务 → 槽位”的映射数组适合排课、车间调度、资源分配。比如slot[i]表示第 i 个任务被分配到的槽位。位向量类用 0/1 数组表示选哪些元素入集适合子集选择、特征选择。我踩过的教训是如果一开始用了“元素在数组里”的排列表示后来又突然想加“把一段任务换个位置整体移动”的算子实现成本会突然变高。所以动手前最好把打算用的算子列出来再倒推解表示。顺序反了后面处处别扭。2.2 评估函数不一定要等于真正的业务目标评估函数是局部搜索的“裁判”。每次比较两个解的优劣裁判要能快速给出结论。工程上常见的一个误区是试图用完整业务仿真器来做评估。仿真器确实准但一次评估可能就要几秒搜索根本跑不动。更合理的做法是用一个可快速计算的“代理指标 惩罚项”来引导搜索。比如调度问题中真正的业务指标可能是综合延误、加班成本、客户满意度但你没法在每秒钟几千次的比较里都把这些算一遍。于是可以只用“总延误时间”加“冲突惩罚”先引导搜索到达一个低延误区域最后再用仿真器对前几个候选解做精评。关于惩罚项权重的提醒权重太低搜索会产出大量不可行解权重太高搜索又会缩在保守区域不敢尝试。合理的做法是先看冲突数量级和目标指标数量级把权重设成“一次冲突造成的损害约等于一次明显的目标恶化”。2.3 初始解随机、贪心、还是现有方案局部搜索从哪个解起步直接影响收敛速度和最终质量。随机初始解保留的多样性最好但需要大量迭代去“爬坡”贪心初始解通常质量不错搜索可以更快收敛但也可能把搜索困在贪心偏向的区域里。我的常规做法是先用一个线性时间的贪心构造解比如按截止时间排序、按最近邻排序跑一轮局部搜索然后换几个随机种子重新开局对比多条搜索轨迹的结果。如果几条轨迹结果差得不大说明搜索基本稳定如果结果忽高忽低说明解空间崎岖需要加强“逃逸”策略而不是单纯增加迭代次数。2.4 增量计算局部搜索快起来的真正秘密这一点必须单独说。局部搜索每一轮都要评估很多邻域候选如果每次都从头完整计算目标函数开销会被白白放大几十上百倍。正确的姿势是计算“增量”。比如路径问题中交换两个相邻城市整条路径长度的变化只取决于被断开的两条边和重新连上的两条边不需要把所有城市加一遍。调度问题里移动一个任务只需要更新与该任务相关的完成时间和后续任务受影响的部分。增量计算的本质是把完整的 O(n) 评估降成 O(1) 到 O(局部范围)。局部搜索能跑到秒级很多时候靠的不是巧妙的算法而是把增量计算做到位了。3. 邻域设计整个局部搜索的灵魂解表示定了评估函数能跑了下一步就是邻域。邻域是整个局部搜索的灵魂因为搜索每一步都在“邻居”里找更好的解。邻域设计得好不好直接决定搜索效率和最终质量。3.1 邻域到底指什么给定一个解 x做一次“移动”能得到的所有新解组成的集合就是 x 的邻域 N(x)。衡量一个移动的成本、一个邻域的规模也决定了每次迭代能看多远。例如旅行商问题中“交换两个城市”产生的邻域规模大约 n(n-1)/2“逆转一段连续序列”产生的邻域规模同样是 n(n-1)/2。邻域大看得广但每一轮评估的开销也大邻域小跑得快但容易早早卡住。3.2 三种常用算子交换、插入、逆转我整理一下最常用的三种算子它们几乎能覆盖大多数工程问题算子移动效果邻域规模适合问题交换两个元素互换位置n(n-1)/2分配、排课、调度插入把一个元素移动到另一个位置n(n-1)序列优化、排序逆转把一段连续区域反转n(n-1)/2TSP、路径规划、物流为什么要区分这些因为同一个问题可以用不同算子表达但效果差很多。路径规划里交换两个城市经常把路径打断成好几段逆转却天然保持一种“不交叉”的结构因此 2-opt 类逆转往往比交换效果好得多。如果只想着“通用”就很容易错过这类问题专属的强算子。3.3 邻域太大怎么办候选集和采样当 n 上万的时候n² 规模的邻域依然很大扫描一遍就够受的。工程上一般有三种做法。第一是构建候选集candidate list不是所有邻居都值得试比如路径问题中只选取“当前连线距离很长”的节点作为候选对象按长度排个序每次只看前 K 个。第二是随机采样每次随机抽几十上百个候选移动而不是全扫描。第三是变邻域搜索Variable Neighborhood Search先用小邻域快速改进小邻域改进不动了再切换到大邻域继续。3.4 选择移动best improvement 还是 first improvement拿到一批候选邻居后怎么挑两种典型策略best improvement把整个邻域全看一遍选改进量最大的那个移动。每轮质量更高但开销大。first improvement按某种顺序看候选只要碰到一个比当前解好的立刻移动。开销小且实测在大多数问题上效率更高。我的经验是搜索初期用 first improvement 快速下降等改进不明显了再用 best improvement 完整扫一遍确认是否真的到了局部最优。这样既快也不会漏掉邻近的明显改进。3.5 邻域操作的三个隐患第一生成重复解。如果操作逻辑写得不对一个移动可能生成和当前解一模一样的解白白浪费评估次数。第二反向移动导致回环。交换 A 和 B紧接着又交换 B 和 A解回到原处。这种问题需要靠禁忌表或状态记录来防。第三移动破坏可行性。比如把任务移动到一个已经满时间的槽位如果没有约束检查评估函数会放行一堆不可行方案。4. 卡在局部最优逃逸策略怎么选不管邻域设计得多好局部搜索最终都会走进一个“无论怎么移动都不再改进”的状态这就是局部最优。问题在于局部最优不等于全局最优。工程实践里如何从坑里跳出来往往比初始搜索更重要。4.1 局部最优为什么这么常见从数学上说解 x 是局部最优是指对任意邻居 y ∈ N(x)都有 f(y) ≥ f(x)。也就是说只要你用的邻域找遍了没有更优解搜索就停在这个坑里。在大规模问题上局部最优解的数量极多山脊和沟壑纵横交错从哪条路下山大概率进的是不同的坑。这很像下棋时只顾眼前一步每一步都“不吃亏”可能走成一个平庸局面而全局最优方案往往要求你先接受一步“吃亏”才能翻盘。4.2 最朴素也最好用的方法重启如果不做任何高级改动最简单有效的策略就是“多起点重启”随机生成若干个初始解分别做局部搜索最后取所有局部最优里最好的那个。这个方法的优点是好实现、毛病少特别适合评估函数不贵、单次局部搜索很快的场景。我通常的做法是先用固定时间预算跑 10 到 50 次重启如果结果差异不大说明问题相对平滑重启次数不需要太多如果差异很大说明问题崎岖光靠重启可能不够。4.3 模拟退火用温度接受“差解”模拟退火是跳出局部最优最经典的方法之一。它的思路是差解不一定立刻拒绝而是以一定概率接受这个概率随温度下降逐渐变小。具体逻辑是从当前解产生一个邻域候选 c如果 f(c)f(x) 就接受否则以 exp(-Δ/T) 的概率接受它其中 Δf(c)-f(x)T 是当前温度。温度高时接受差解概率很高搜索接近随机游走温度慢慢降下来搜索逐渐收紧到下山模式。在实践中决定退火效果的关键是冷却进度。初始温度通常设置为“最差候选也有 80% 到 95% 概率被接受”的量级降温系数常用 0.95 到 0.995每个温度下要跑足够次数的内层迭代。几何降温虽然朴素但胜在稳定、易调。4.4 禁忌搜索记住最近做过的事禁忌搜索的精髓是“记忆”。它维护一张禁忌表记录最近若干步做过的移动在下一轮禁止重复这些移动。比如路径问题中刚交换过城市 A 和 B接下来几轮就不允许再做“交换 A 和 B”这个操作逼着搜索走一条新路。禁忌表太短防不住回环太长搜索空间被过度限制。经验上禁忌长度是问题规模平方根量级的常见起步值再根据实际效果微调。禁忌搜索在排列/调度类问题上非常稳定我遇到这类问题时常常第一个想起它。4.5 扰动式迭代局部搜索迭代局部搜索Iterated Local SearchILS的思路更直接在局部搜索得到一个局部最优后不要随机重启而是在这个解附近做一次“暴力扰动”然后再做局部搜索。扰动的幅度很关键。太小很快就又落回同样的坑太大等于退化成随机重启。实用经验是路径问题可以随机做几次 2-opt 逆转序列问题可以随机重排一个连续片段。扰动后往往能找到新的下降路径。4.6 我的选择口诀如果只能说几句我会这样概括时间紧先用重启邻域操作容易回环就上禁忌表目标函数粗糙、上下乱跳用模拟退火更稳追求质量在时间预算内做迭代局部搜索加扰动。5. 工程实现里的细节终止条件、随机性与性能局部搜索的算法骨架不难但我见过不少实现跑不出效果问题往往不在理论层面而在循环结构、停止条件和一堆细节上。5.1 一个干净的主循环下面这段伪代码是我常用的模板核心是“连续多少轮没有改进就停止”def local_search(init_sol, neighbor_gen, evaluate, max_no_improve100): current init_sol best current no_improve 0 while no_improve max_no_improve: candidate neighbor_gen(current) if candidate is None: break if evaluate(candidate) evaluate(current): current candidate if evaluate(current) evaluate(best): best current no_improve 0 else: no_improve 1 return best注意这里每次只取一个候选first improvement 的简化版。如果要求 best improvement需要先跑完整个邻域收集最优移动再统一应用。5.2 终止条件设计实际系统里我很少只用一个停止条件而是叠加三层最大迭代数防止极端情况下无限循环。无改进代数比如连续 200 轮没有刷新最优值就停。时间预算工程上最实用的一条。算法在外部计时到达时限立刻返回当前最优解。给算法设置时间预算还有一个附带好处便于和旧方案做公平对比。大家都有同样的时间上限谁解质量高听谁的。5.3 随机性与可复现性局部搜索往往带随机性这不丢人但必须可控。工程上最容易被忽视的一个细节是随机种子如果不固定 seed每次运行结果都不一样评估和调参会非常痛苦。我的习惯是程序启动时记录全局 seed每次实验保存使用的 seed 和初始解。对比不同策略时用同一组 seed 集合跑结果才有可比性。5.4 真正影响性能的三个点局部搜索的耗时通常不在循环本身而在评估函数。第一个优化点是增量计算这个前面已经说过。第二个是缓存高频出现的解状态把评估结果存下来命中缓存直接返回。第三个是数据预加载把静态数据坐标、时间窗、资源表提前准备好别在评估里反复查数据库或做复杂计算。numba或者 PyPy 这类优化工具我也试过但实话实说这些都不如把评估函数从 O(n) 改成 O(1) 带来的提升明显。5.5 我踩过的几个典型坑接受相等的解导致死循环如果邻域生成可能返回当前解且你的比较条件是搜索会原地打转。建议比较用严格再单独记录最优。惩罚权重没有归一化冲突惩罚和优化目标量级相差太大或太小都会让搜索行为异常。邻域生成里漏了边界情况比如“把最后一个元素移动到第一个位置”这种环绕操作经常被写成 bug。无改进计数逻辑写错有的实现把“本轮没有找到改进”和“全局没有刷新最优”混为一谈导致过早停止。建议分开两个计数器一个管连续下降一个管全局最优更新。6. 用一个完整示例把过程串一遍排产任务分配理论说多了容易飘我用一个简化的调度示例完整走一遍流程。假设要把 n 个任务分配到 m 台设备上每个任务有处理时间和截止时间目标是让总延误最小。这是一个很典型的局部搜索应用场景。6.1 问题与解表示任务按顺序放在每台设备的处理队列里。解表示用一个字典或二维列表每台设备对应一个任务序列。# 示例结构 solution { 0: [3, 1, 5], # 设备0依次处理任务3、1、5 1: [2, 4, 6], # 设备1依次处理任务2、4、6 }这种表示对“把一个任务从一台设备挪到另一台设备”的操作很友好对“交换两个任务”也容易实现。6.2 评估函数与增量更新总延误是所有任务完成时间减去截止时间的正值之和。完整计算是 O(n)但移动一个任务时只需要重新计算被移动任务所在设备以及受影响后续任务的完成时间。实际代码里我会单独写一个delta_after_move函数专门计算移动带来的延误变化。6.3 邻域算子与初始解我用了两个算子随机挑一个任务插入到另一台设备的某个位置随机交换两个不同设备的任务。初始解则用“按截止时间升序排序后依次放入最早可用设备”的贪心方案。跑一轮局部搜索后结果往往比初始解有明显改善。我用一组模拟数据测过初始解的总延误在 4800 左右局部搜索后降到 900 上下差距肉眼可见。而这一切只花了几百次迭代。6.4 一个小型可运行骨架下面是一个极简可运行的局部搜索骨架核心逻辑就几十行。真实项目里要扩充的通常是邻域生成和增量评估而非搜索主循环。import random def evaluate(schedule, durations, deadlines): delay 0 for device, task_list in schedule.items(): t 0 for task in task_list: t durations[task] delay max(0, t - deadlines[task]) return delay def neighbor(schedule, tasks): # 简单版随机换两个不同设备上的任务 devices list(schedule.keys()) a, b random.sample(devices, 2) if not schedule[a] or not schedule[b]: return schedule i random.randrange(len(schedule[a])) j random.randrange(len(schedule[b])) new_schedule {k: list(v) for k, v in schedule.items()} new_schedule[a][i], new_schedule[b][j] new_schedule[b][j], new_schedule[a][i] return new_schedule def local_search(init, durations, deadlines, max_no_improve100): cur init best_val evaluate(cur, durations, deadlines) no_improve 0 while no_improve max_no_improve: cand neighbor(cur, durations) val evaluate(cand, durations, deadlines) if val best_val: cur cand best_val val no_improve 0 else: no_improve 1 return cur, best_val这一段没有任何魔法但它就是一个可以继续往里填东西的骨架。把邻域换成候选集、把评估改成增量计算就完全工业可用。6.5 示例里值得注意的体会在这个示例里我第一次犯的错是把“设备里没有任务时交换”的边界漏掉了程序偶尔崩溃后来加了空队列判断运行才稳定。另一个体会是贪心初始解给局部搜索帮了大忙——如果直接从完全随机初始解开始收敛需要的迭代次数会明显更多。如果你手头正好有一个“解已经能算出来但就是不够好、不够快”的问题我建议先别急着上复杂的进化计算。把解表示、邻域算子和增量评估这三样东西做好局部搜索大概率已经能给你一个眼前一亮的结果真到了瓶颈再加模拟退火或禁忌表去逃逸。这是我把一个需要几十分钟的求解过程压到秒级后最深的体会——局部搜索不是退而求其次的补丁它本身就是一个值得优先考虑的设计选项。
阅读完成 · 觉得有帮助？
