G-LNS：面向LLM自动启发式设计的生成式大邻域搜索

用LLM协同进化破坏-修复算子对，自动设计大邻域搜索启发式，超越经典求解器

前置知识

组合优化问题（COP）

组合优化问题是在离散的候选解集合中寻找最优解的一类问题，典型代表包括旅行商问题（TSP，找最短回路遍历所有城市）和带容量约束的车辆路径问题（CVRP，用多辆车在容量限制下服务所有客户并最小化总路程）。这类问题通常是NP-hard的，精确求解在大规模实例上不可行，因此实践中依赖启发式算法在合理时间内找到高质量近似解。

G-LNS的核心目标就是为这类NP-hard问题自动生成高性能启发式算子，理解COP的基本设定是理解全文实验和动机的前提。

大邻域搜索（LNS）

LNS是一种元启发式算法框架，核心思想是通过交替执行'破坏'（destroy）和'修复'（repair）两个操作来探索解空间。破坏操作从当前解中移除一部分组件（如删除某些城市节点），产生一个部分解；修复操作将被移除的组件重新插入，产生一个新的完整解。这种'拆了重建'的策略比2-opt等小邻域操作能做更大幅度的结构重组，从而更容易跳出局部最优。LNS通常配合模拟退火（SA）接受准则来平衡探索和利用。

G-LNS的核心创新就是让LLM自动生成LNS的破坏和修复算子，而非人工设计。理解LNS的工作机制是理解本文方法的基石。

自动启发式设计（AHD）

AHD（也称Hyper-heuristic）旨在自动化地发现高性能启发式算法，而非人工设计。传统方法依赖遗传编程（GP）进化语法树表示的启发式规则。近年来，LLM被引入AHD框架（如FunSearch、EoH），将LLM作为变异算子来生成和改进启发式代码，形成'思考-代码'协同进化范式。LLM负责生成算法逻辑的自然语言描述和对应的Python实现代码。

G-LNS是在LLM-based AHD这个研究脉络上的突破性工作，理解AHD的现有范式才能体会到G-LNS将设计空间从'参数调优'扩展到'结构算子设计'的创新意义。

自适应大邻域搜索（ALNS）

ALNS是LNS的增强版本，维护一组破坏和修复算子的组合库（portfolio），并根据算子的历史表现动态调整其被选中的概率（通常用轮盘赌机制）。每次迭代中，ALNS根据当前权重随机选择一个破坏算子和一个修复算子执行，然后根据解的质量变化更新所选算子的权重——表现好的算子权重增加，表现差的权重降低。这种自适应机制使得ALNS能在不同搜索阶段自动切换策略。

G-LNS在评估阶段采用了ALNS的自适应评分机制来量化每个算子的贡献，这是其多episode评估和协同矩阵更新的技术基础。

协同进化（Co-evolution）

协同进化是进化计算中的一种策略，同时维护多个相互依赖的种群，在进化过程中让它们相互影响、共同进步。Potter和De Jong在1994年提出的合作协同进化框架中，不同种群代表问题的不同组成部分，评估时将不同种群的个体组合起来测试整体性能。G-LNS将这一思想应用于破坏算子和修复算子的双种群进化，因为LNS的效果高度依赖于破坏-修复算子对的配合质量。

G-LNS的核心创新之一就是提出协同评估机制和协同感知的交叉策略，这直接受到协同进化范式的启发，理解这个概念才能理解为什么单独进化破坏或修复算子会损失性能。

研究动机

现有的LLM自动启发式设计方法存在一个根本性的结构瓶颈：它们的搜索空间被限制在固定形式的启发式模板内。具体来说，大多数方法要么进化构造式启发式（constructive heuristics），即逐步构建解的优先级规则（如FunSearch、EoH），要么在固定邻域结构（如2-opt）内调优参数。构造式启发式遵循不可逆的决策轨迹——早期的次优决策很难通过后续规则调整来纠正，在TSP100上这类方法的最优性间隙通常超过10%。而基于固定邻域的方法（如进化GLS的惩罚函数），虽然允许迭代改进，但把邻域结构（如2-opt、or-opt）当作固定的先验，LLM只能做参数调优而无法做结构性的算法创新。更关键的是，LNS的效果高度依赖破坏和修复算子的耦合质量——破坏阶段决定了引入什么结构缺陷，修复阶段必须专门适配来重建这些缺陷。这种强耦合使得自动化的LNS设计特别困难，现有AHD框架基本无法处理。

本文的目标是G-LNS的目标是将LLM自动启发式设计的搜索空间从固定启发式形式扩展到LNS算子的结构设计，让LLM自动生成高性能的破坏-修复算子对。具体而言，框架要能在仅使用200代进化（相比基线方法的1000代，减少5倍的LLM调用预算）的情况下，进化出在TSP和CVRP上达到近最优解质量的算子，并且这些算子能在未见过的问题规模和分布上泛化。例如在CVRP200上，目标是超越OR-Tools求解器的解质量。

与已有工作不同的是，G-LNS抓住了一个被现有AHD工作忽视的关键点：LNS的破坏和修复算子之间存在强耦合关系，单独进化其中任何一个都会损失整体性能。现有方法要么只进化构造式规则，要么只进化参数，都无法触及LNS的核心——算子的结构逻辑。G-LNS的独特切入角度是：(1) 将LNS算子对作为进化的单元，而不是单个算子；(2) 引入协同矩阵（synergy matrix）显式记录算子对的配合效果；(3) 设计协同感知的联合交叉策略，确保修复算子专门适配破坏算子引入的结构缺陷。这种'拆解问题结构'的能力是构造式方法和固定邻域方法都做不到的。

核心方法

G-LNS的直觉可以用一个比喻来理解：想象一个装修队，有人负责拆墙（破坏算子），有人负责砌新墙（修复算子）。传统的AHD方法相当于只训练砌墙工人按固定图纸施工，或者只训练拆墙工人用固定工具拆墙。G-LNS则同时训练两个工种，并且让拆墙和砌墙的人配对协作——拆墙的人要考虑砌墙的人擅长怎么建，砌墙的人要专门适配拆墙留下的洞口形状。技术上，G-LNS维护两个独立的算子种群（破坏算子池 P_d 和修复算子池 P_r，各含 N=5 个算子），通过多episode评估机制量化每个算子的个体贡献和算子对的协同效果，然后利用LLM通过变异和交叉策略进化出新的算子。整个框架循环执行四个阶段：初始化、评估、种群管理、LLM驱动的进化。

G-LNS最核心的创新是协同感知的算子对共同进化。在评估阶段，框架不仅用全局适应度 F 跟踪每个算子的个体表现，还维护一个协同矩阵 S（N×N矩阵），其中 S_{ij} 记录破坏算子 d_i 和修复算子 r_j 配对时的累积奖励。在进化阶段，G-LNS从协同矩阵中选出配合最好的算子对，然后提示LLM将它们作为一个统一体来共同进化（Synergistic Joint Crossover, c2）——LLM被明确要求生成的新修复算子要专门适配新破坏算子引入的结构缺陷。这与现有AHD方法的本质区别在于：FunSearch/EoH只进化单个启发式函数，ReEvo用反思引导变异但仍是单体进化，而G-LNS显式建模并利用了算子间的结构性耦合关系。

方法步骤详情

G-LNS的完整流程如下。第一步：初始化。建立双种群架构，每个种群容量 N=5。先注入经典领域专家启发式作为种子（如TSP用Random Removal + Greedy Insertion），然后通过LLM的初始化动作（i1、i2）生成新算子填满种群。同时初始化三个指标结构：全局适应度向量 F、协同矩阵 S、自适应权重 W。第二步：评估。进行 K=10 个独立评估episode，每个episode从随机初始解开始执行 T=100 次LNS迭代。每次迭代中，用轮盘赌机制根据当前权重 W 选择破坏算子 d_i 和修复算子 r_j，执行破坏-修复操作得到新解 x'。根据 x' 的质量分层给予奖励 sigma（sigma_1 改进全局最优、sigma_2 改进当前解、sigma_3 SA接受、sigma_4 拒绝），然后更新三个指标：用平滑因子 lambda 更新权重 W，累积奖励到全局适应度 F，更新协同矩阵 S_{ij}。第三步：种群管理。每 K 个episode后，按全局适应度 F 排序，剪枝底部 M=2 个算子，然后重置 F 和 S 为零以确保公平竞争。第四步：LLM驱动的进化。通过三种策略填充空位：变异（m1逻辑进化/m2参数校准）、同质交叉（c1同类型算子特征重组）、协同联合交叉（c2基于协同矩阵选择最优配对共同进化）。所有生成的算子经过sanity check验证后才加入种群。

技术新颖性

G-LNS的技术新颖性体现在三个层面。第一，设计空间的跃迁：从进化标量启发式函数或固定模板内的参数，跃迁到进化可执行的LNS算子代码。这是从'优化规则'到'设计算法结构'的范式转变，使得搜索过程能执行复杂的拓扑变换而非仅做局部调整。第二，协同评估机制：引入协同矩阵 S 显式捕获破坏-修复算子对的配合效果，这在现有AHD工作中是全新的——之前的方法要么单独评估每个启发式（FunSearch、EoH），要么评估启发式集合但不建模内部耦合（EoH-S）。第三，协同联合交叉（c2）：这是首个在进化算子层面建模结构耦合的交叉策略，通过提示LLM将高协同配对作为统一体来进化，确保修复逻辑专门适配破坏逻辑。此外，自适应评分机制中的分层奖励系统（sigma_1 > sigma_2 > sigma_3 > sigma_4）为进化提供了比平坦奖励更精确的反馈信号。

实验结果

G-LNS在TSP和CVRP两个经典COP上进行了全面实验，结果显著优于所有基线。在TSP上，G-LNS在TSP10和TSP20上达到0.00%和0.01%的最优性间隙（LKH-3为基准），在TSP50上仅0.37%，TSP100上1.10%，TSP200上1.31%，全面优于所有LLM-based AHD方法。特别是TSP200上，G-LNS的1.31%远低于Evo-MCTS的10.20%和MCTS-AHD(ACO)的6.22%。在CVRP上表现更为突出：CVRP10间隙1.44%，CVRP20为2.20%，CVRP50为1.29%，而在CVRP100和CVRP200上G-LNS分别达到0.00%间隙——不仅超越所有LLM基线（它们的间隙通常超过10%），还优于OR-Tools求解器（CVRP100间隙2.09%，CVRP200间隙1.27%）。在计算效率方面，G-LNS在CVRP100上仅需约70秒达到最优解，而OR-Tools分配了320秒仍未能完全收敛，MCTS-AHD(ACO)则需要1110秒。在泛化性测试中，G-LNS在TSPLib上平均间隙仅2.8%（EoH-S为9.1%），在CVRPLib Set F上从EoH-S的40.1%降至15.9%。消融实验验证了各组件的必要性：去掉变异（w/o Mut.）TSP50间隙从0.37%升至1.55%，去掉协同交叉（w/o Syn.）CVRP50间隙从1.29%升至1.87%，去掉自适应权重（w/o Adapt.）也有明显退化。此外在OVRP（开放式车辆路径问题）上，G-LNS在OVRP200上达到0.00%间隙，而OR-Tools为2.05%，EoH为36.67%，展现了在不同问题变体上的鲁棒性。

查看结构化数据

任务	指标	本文	基线	提升
TSP200	Optimality Gap	1.31%	Evo-MCTS 10.20%	降低8.89个百分点
CVRP100	Optimality Gap	0.00%	OR-Tools 2.09%	超越经典求解器
CVRP200	Optimality Gap	0.00%	OR-Tools 1.27%	超越经典求解器
TSPLib	Avg Optimality Gap	2.8%	EoH-S 9.1%	降低6.3个百分点
CVRPLib Set F	Avg Optimality Gap	15.9%	EoH-S 40.1%	降低24.2个百分点
CVRPLib Set X	Avg Optimality Gap	11.2%	EoH-S 19.1%	降低7.9个百分点
OVRP200	Optimality Gap	0.00%	OR-Tools 2.05%	超越经典求解器
TSP50	Optimality Gap	0.37%	Evo-MCTS 7.82%	降低7.45个百分点

局限与改进

尽管G-LNS取得了显著成果，仍存在以下局限。首先，进化过程仍依赖LLM的质量——框架使用DeepSeek-V3.2作为核心LLM，不同LLM可能产生不同的算子质量，论文未讨论对LLM能力的敏感性。其次，G-LNS在小规模实例上优势不明显，例如CVRP10上间隙1.44%虽优于其他AHD方法但仍高于OR-Tools的0.00%，说明在简单问题上经典方法仍有优势。第三，虽然G-LNS将LLM调用次数减少了5倍（200代 vs 1000代），但每代的评估成本较高（10个episode × 100次迭代），总体计算开销的详细分析不够充分。第四，实验仅在TSP、CVRP和OVRP三个路由问题上验证，对其他类型的COP（如调度问题、装箱问题）的适用性尚未探索。第五，进化过程的随机性方面，论文提到进行了3次独立运行，但未报告方差或置信区间，使得结果的统计显著性难以评估。

独立分析的弱点

G-LNS有几个值得关注的弱点。第一，种群规模偏小：破坏和修复算子池各仅 N=5 个算子，这意味着进化搜索的多样性受限。在复杂问题上，更大的种群可能发现更多样的算子逻辑，但也会增加评估成本。改进方向可以是引入层次化的种群结构或自适应种群大小机制。第二，评估效率瓶颈：每次评估需要运行 K=10 个episode，每个episode T=100 次迭代，这对大规模实例（如CVRP200）的单次评估就很耗时。可以考虑引入代理模型（surrogate model）或早停机制来减少不必要的完整评估。第三，算子可解释性不足：虽然论文展示了进化出的ACSR和PSWR等算子的代码，但这些算子的逻辑相当复杂（包含多层条件分支和随机策略），缺乏对'为什么这个算子有效'的深入分析。改进方向可以是引入代码简化或规则提取机制，使进化出的算子更易理解和部署。第四，跨问题泛化未验证：算子在TSP上进化后仅在同一问题的不同规模上测试，未尝试跨问题迁移（如TSP算子迁移到VRP），这限制了框架的通用性价值。

未来方向

作者提出的未来方向包括将G-LNS扩展到多目标优化场景，以及探索在路由问题之外的更广泛组合优化问题（如调度、装箱）上的适用性。基于G-LNS的成果，还可以延伸以下方向：(1) 层次化算子设计——不仅进化破坏-修复算子对，还进化更高层的算子选择策略，形成多层自动设计架构；(2) 在线自适应——将进化出的算子库部署到实际场景中，结合在线学习动态调整算子选择概率，而非使用固定的最优算子对；(3) 与NCO方法融合——将G-LNS进化出的结构化算子与神经网络的快速推理能力结合，用神经网络近似算子中的计算密集部分（如距离计算），实现更快的推理速度；(4) 约束处理——将框架扩展到更复杂的约束类型（如时间窗、多车型），测试协同进化机制在约束密集环境下的效果。

复现评估

G-LNS的代码已在GitHub开源（https://github.com/zboyn/G-LNS），这大大降低了复现门槛。框架使用的LLM是DeepSeek-V3.2，这是一个开源模型，研究者可以自行部署或通过API调用。实验数据集方面，训练使用16个随机生成的TSP50/CVRP50实例，测试使用TSPLib和CVRPLib标准基准库，这些都是公开可获取的。算力需求方面，进化过程需要200代 × 每代多次LLM调用 + 评估运行，对GPU资源有一定需求（用于运行DeepSeek-V3.2），但论文报告的总推理时间（如CVRP100约70秒完成500次迭代）表明评估阶段的计算开销可控。整体复现难度中等——代码框架和数据都已提供，主要挑战在于LLM的调用成本和进化过程的随机性可能导致不同运行间的结果差异。

G-LNS：面向LLM自动启发式设计的生成式大邻域搜索 G-LNS: Generative Large Neighborhood Search for LLM-Based Automatic Heuristic Design