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

尽管大型语言模型（LLMs）在启发式自动设计（AHD）方面展现出潜力，但现有方法通常围绕构造性优先规则或参数化局部搜索指导进行建模，限制了搜索空间到固定启发式形式。此类设计在结构探索能力上有限，难以逃离复杂组合优化问题（COPs）中的深层局部最优解。本文提出G-LNS，一种生成进化框架，将基于LLM的AHD扩展到大邻域搜索（LNS）算子的自动化设计。与以往独立进化解的方法不同，G-LNS利用LLMs协同进化紧密耦合的破坏和修复算子对。合作评估机制显式捕捉它们的交互，从而发现能够有效进行结构破坏和重建的互补操作逻辑。在具有挑战性的COP基准测试（如旅行商问题TSP和带容量约束的车辆路径问题CVRP）上的大量实验表明，G-LNS显著优于基于LLM的AHD方法以及强大的经典求解器。所发现的启发式方法不仅在减少计算预算的情况下实现了接近最优解，而且在多样且未见过的实例分布中表现出稳健的泛化能力。