arXiv:2602.08253cs.AI2026-02被引 8

用大模型自动设计可破坏重构建的搜索算子,解决复杂优化难题。

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

  • 让大模型协同演化破坏与重建算子,形成互补机制。
  • 在TSP和CVRP上逼近最优解,计算开销更低。
  • 适合想自动化设计优化算法的研究者与工程师。

尽管大语言模型(LLM)在自动启发式设计(AHD)中展现出潜力,但现有方法通常围绕构造性优先规则或参数化局部搜索引导展开,限制了启发式结构的探索空间,难以摆脱复杂组合优化问题(COPs)中的深局部极值。本文提出G-LNS,一种基于生成进化的框架,将LLM驱动的AHD扩展至大型邻域搜索(LNS)算子的自动设计。不同于以往孤立演化启发式的方法,G-LNS利用LLM协同演化紧密耦合的破坏与重建算子对。通过协作评估机制显式捕捉二者交互,实现有效结构破坏与重构的协同。在旅行商问题(TSP)和带容量约束的车辆路径问题(CVRP)等挑战性基准上的大量实验表明,G-LNS显著优于现有基于LLM的AHD方法及强经典求解器。所发现的启发式不仅以更少计算预算达到近优解,且在多样化的未见实例分布上表现出稳健泛化能力。

原文摘要 · Abstract (English)

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.

自动设计组合优化大模型搜索算子

Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。