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

虽然大语言模型（LLM）近来在自动启发式设计（AHD）中展现出前景，但现有方法通常围绕构造性优先规则或参数化局部搜索引导来构建 AHD，从而将搜索空间限制在固定的启发式形式内。这类设计进行结构探索的能力有限，难以在复杂的组合优化问题（COP）中逃离深度局部最优。在这项工作中，我们提出 G-LNS，一个生成式演化框架，将基于 LLM 的 AHD 扩展到大邻域搜索（LNS）算子的自动设计。与以往孤立演化启发式的方法不同，G-LNS 利用 LLM 共同演化紧密耦合的破坏与修复算子对。协作评估机制显式捕捉二者的交互，使得能够发现互补的算子逻辑，共同执行有效的结构破坏与重建。在具有挑战性的组合优化基准（如旅行商问题（TSP）和带容量约束的车辆路径问题（CVRP））上的大量实验表明，G-LNS 显著优于基于 LLM 的 AHD 方法以及强大的经典求解器。所发现的启发式不仅能在更低的计算预算下取得接近最优的解，还在多样且未见过的实例分布上表现出稳健的泛化能力。