⏶2
HeurAgenix：利用大型语言模型解决复杂组合优化挑战
发表
由 
Xianliang Yang 提交
Xianliang Yang 提交作者: Xianliang Yang, Ling Zhang, Haolong Qian, Lei Song, Jiang Bian
Xianliang Yang, Ling Zhang, Haolong Qian, Lei Song, Jiang Bian摘要
启发式算法在解决组合优化（CO）问题中扮演着至关重要的角色，然而传统设计严重依赖人工专业知识，难以泛化到不同实例。我们引入了 HeurAgenix，这是一个由大型语言模型（LLM）驱动的两阶段超启发式框架，它首先演化启发式算法，然后自动从中进行选择。在启发式演化阶段，HeurAgenix 利用 LLM 将种子启发式解决方案与更高质量的解决方案进行比较，并提取可重用的演化策略。在问题解决过程中，它在 LLM 感知能力的指导下，为每个问题状态动态选择最有前景的启发式算法。为了灵活性，该选择器可以是最先进的 LLM，也可以是经过微调的轻量级模型，具有更低的推理成本。为了缓解组合优化复杂性导致的可靠监督稀缺问题，我们使用双重奖励机制微调轻量级启发式选择器，该机制联合利用选择偏好和状态感知的信号，从而在嘈杂的注释下实现稳健选择。在典型基准上的广泛实验表明，HeurAgenix 不仅超越了现有的基于 LLM 的超启发式算法，而且与专用求解器持平或更优。代码可在 https://github.com/microsoft/HeurAgenix 获取。
本文介绍了HeurAgenix，一个端到端、LLM驱动的超启发式框架。该框架首先通过对比式、数据驱动的演化阶段，演化出一个多样化的启发式池，然后通过结合基于LLM的过滤和测试时缩放，为每个问题状态自适应地选择最有前途的启发式方法。为了以低成本实现实时部署，LLM选择器被蒸馏成一个经过微调的轻量级模型，该模型采用双奖励机制（基于偏好的结果奖励+上下文感知奖励）进行训练。在五个经典组合优化基准（TSP、CVRP、MKP、JSSP和MaxCut）上，HeurAgenix始终优于现有基于LLM的超启发式方法，并达到或超越了专用求解器。