大语言模型为组合优化发现互补启发式方法

组合优化（CO）在科学、工程和工业中至关重要，但为每种新问题变体设计有效启发式方法需要深厚的领域知识和数月的专家迭代。本文提出了 LACE（LLM-driven Algorithm Construction via Complementary Evolution，基于互补演化的 LLM 驱动算法构建），该框架将算法设计分解为输入模式、输出模式、工具库和启发式组合（即 I-O-T-H 接口），并通过受时间约束的互补演化来改进该组合。该接口定义了一个经过验证的问题契约，引导大语言模型的能力集中于高层算法推理，而非特定问题的实现；互补演化则迭代生成并选择能够在严格运行时间预算内解决异构实例的专门启发式方法。在 36 个经典 CO-Bench 问题上，LACE 的平均得分为 0.945，而现有最强的基于 LLM 的方法为 0.870，直接使用 LLM 提示且无任何框架则为 0.571，表明增益来自框架而非模型。在四个结构全新的问题上，LACE 达到 0.97–0.99，而五个现有基于 LLM 的基线方法未能产生任何可行算法。这些结果表明，此类问题的有效算法发现可以在很大程度上实现自动化。

(来源：Nature)