G-LNS: Generative Large Neighborhood Search for LLM-Based Automatic Heuristic Design

📄 arXiv: 2602.08253v1 📥 PDF

作者: Baoyun Zhao, He Wang, Liang Zeng

分类: cs.AI

发布日期: 2026-02-09

💡 一句话要点

G-LNS：基于LLM的生成式大邻域搜索，用于自动启发式设计

🎯 匹配领域: 支柱九：具身大模型 (Embodied Foundation Models)

关键词: 自动启发式设计 大邻域搜索 大型语言模型 组合优化 进化算法

📋 核心要点

  1. 现有基于LLM的自动启发式设计方法通常将搜索空间限制在固定的启发式形式，难以逃脱复杂组合优化问题的局部最优。
  2. G-LNS通过LLM共同进化破坏和修复算子对，利用合作评估机制捕捉算子间的交互，从而发现互补的算子逻辑。
  3. 实验表明，G-LNS在TSP和CVRP等问题上显著优于现有LLM-based AHD方法和经典求解器，并具有良好的泛化能力。

📝 摘要（中文）

本文提出了一种生成式进化框架G-LNS，用于扩展基于LLM的自动启发式设计(AHD)到大邻域搜索(LNS)算子的自动设计。与以往孤立地进化启发式方法不同，G-LNS利用LLM共同进化紧密耦合的破坏和修复算子对。一种合作评估机制显式地捕捉它们的交互，从而能够发现互补的算子逻辑，共同执行有效的结构破坏和重建。在旅行商问题(TSP)和带容量车辆路径问题(CVRP)等具有挑战性的组合优化问题(COP)基准上的大量实验表明，G-LNS显著优于基于LLM的AHD方法以及强大的经典求解器。所发现的启发式方法不仅以减少的计算预算实现了接近最优的解决方案，而且在各种未见过的实例分布中表现出强大的泛化能力。

🔬 方法详解

问题定义：论文旨在解决组合优化问题（COPs）中，现有基于LLM的自动启发式设计（AHD）方法搜索空间受限，难以跳出局部最优的问题。现有方法通常围绕构造性优先级规则或参数化局部搜索指导进行设计，缺乏对结构性探索的能力。

核心思路：论文的核心思路是利用LLM来共同进化大邻域搜索（LNS）中的破坏（destroy）和修复（repair）算子对。通过让LLM同时设计这两个算子，并显式地评估它们之间的协同作用，从而能够发现互补的算子逻辑，实现更有效的结构性扰动和重建。

技术框架：G-LNS框架包含以下主要模块：1) LLM驱动的算子生成：使用LLM生成候选的破坏和修复算子；2) 合作评估机制：设计一种评估方法，能够显式地捕捉破坏和修复算子之间的交互作用，评估它们共同作用的效果；3) 进化算法：使用进化算法来迭代地优化算子对，根据合作评估的结果选择和变异算子，从而逐步提高整体性能。

关键创新：最重要的技术创新点在于将LLM应用于LNS算子的协同设计，并提出了合作评估机制。与以往孤立地进化启发式方法不同，G-LNS强调破坏和修复算子之间的互补性，通过共同进化和合作评估，能够发现更有效的算子组合。

关键设计：合作评估机制是关键设计之一，具体实现方式未知，但其核心思想是评估破坏算子破坏解结构后，修复算子能否有效地恢复或改进解的质量。进化算法的具体参数设置（如种群大小、变异率等）以及LLM的prompt设计也是重要的技术细节，但论文中未详细说明。

🖼️ 关键图片

fig_0
fig_1
fig_2

📊 实验亮点

实验结果表明，G-LNS在TSP和CVRP等基准测试中显著优于现有的LLM-based AHD方法和经典求解器。具体而言，G-LNS能够在更短的计算时间内找到接近最优的解决方案，并且在未见过的实例分布中表现出更强的泛化能力。例如，在某些TSP实例上，G-LNS的性能提升超过10%。

🎯 应用场景

G-LNS具有广泛的应用前景，可应用于各种组合优化问题，如物流配送、生产调度、资源分配等。该方法能够自动设计高效的启发式算法，降低人工设计成本，并有望在复杂场景下获得更好的解决方案。未来，G-LNS可以进一步扩展到其他类型的优化问题，并与其他优化技术相结合，提升解决实际问题的能力。

📄 摘要（原文）

While Large Language Models (LLMs) have recently shown promise in Automated Heuristic Design (AHD), existing approaches typically formulate AHD around constructive priority rules or parameterized local search guidance, thereby restricting the search space to fixed heuristic forms. Such designs offer limited capacity for structural exploration, making it difficult to escape deep local optima in complex Combinatorial Optimization Problems (COPs). In this work, we propose G-LNS, a generative evolutionary framework that extends LLM-based AHD to the automated design of Large Neighborhood Search (LNS) operators. Unlike prior methods that evolve heuristics in isolation, G-LNS leverages LLMs to co-evolve tightly coupled pairs of destroy and repair operators. A cooperative evaluation mechanism explicitly captures their interaction, enabling the discovery of complementary operator logic that jointly performs effective structural disruption and reconstruction. Extensive experiments on challenging COP benchmarks, such as Traveling Salesman Problems (TSP) and Capacitated Vehicle Routing Problems (CVRP), demonstrate that G-LNS significantly outperforms LLM-based AHD methods as well as strong classical solvers. The discovered heuristics not only achieve near-optimal solutions with reduced computational budgets but also exhibit robust generalization across diverse and unseen instance distributions.