Improving Existing Optimization Algorithms with LLMs
作者: Camilo Chacón Sartori, Christian Blum
分类: cs.AI, cs.CL, cs.LG, cs.SE
发布日期: 2025-02-12
💡 一句话要点
利用大型语言模型改进现有优化算法，提升组合优化性能
🎯 匹配领域: 支柱九：具身大模型 (Embodied Foundation Models)
关键词: 大型语言模型 组合优化 启发式算法 元启发式算法 算法优化
📋 核心要点
- 现有组合优化算法的启发式设计依赖专家知识，耗时且难以泛化到不同问题。
- 利用LLM的预训练知识，自动生成并评估启发式算法，加速优化算法的改进过程。
- 实验表明，GPT-4o生成的启发式算法在CMSA算法中表现优于人工设计的启发式算法，尤其是在大规模图上。
📝 摘要（中文）
本文探讨了将大型语言模型（LLM）集成到优化算法中，从而创造强大的协同效应并开启令人兴奋的研究机会。本文研究了LLM如何增强现有的优化算法。利用其预训练的知识，我们展示了LLM提出创新启发式变体和实现策略的能力。为了评估这一点，我们应用了一种非平凡的优化算法，即构造、合并、解决和适应（CMSA）——一种用于组合优化问题的混合元启发式算法，该算法在解决方案构造阶段结合了一种启发式算法。我们的结果表明，GPT-4o提出的替代启发式算法优于CMSA的专家设计的启发式算法，并且性能差距在更大和更密集的图上扩大。
🔬 方法详解
问题定义：论文旨在解决组合优化问题中启发式算法设计依赖专家知识、效率低下的问题。现有方法通常需要人工设计启发式规则，过程耗时且难以保证性能，尤其是在问题规模增大或问题特性变化时，人工设计的启发式算法可能无法达到最优效果。
核心思路：论文的核心思路是利用大型语言模型（LLM）的预训练知识和生成能力，自动生成并评估启发式算法。通过提示工程，引导LLM生成针对特定组合优化问题的启发式规则，并将其集成到现有的优化算法框架中。这种方法旨在减少对人工设计的依赖，并加速启发式算法的迭代和优化过程。
技术框架：论文采用的整体框架是将LLM作为启发式算法的生成器，并将其与现有的优化算法（CMSA）相结合。具体流程如下：1) 使用提示工程，向LLM描述组合优化问题和CMSA算法的构造阶段；2) LLM基于问题描述生成候选的启发式规则；3) 将LLM生成的启发式规则集成到CMSA算法的构造阶段；4) 使用标准测试集评估集成了LLM生成启发式规则的CMSA算法的性能；5) 将评估结果反馈给LLM，用于进一步优化启发式规则。
关键创新：论文的关键创新在于利用LLM自动生成启发式算法，并将其集成到现有的优化算法框架中。与传统的人工设计启发式算法相比，这种方法具有以下优势：1) 减少了对专家知识的依赖；2) 加速了启发式算法的迭代和优化过程；3) 能够生成更具创新性的启发式规则。
关键设计：论文的关键设计包括：1) 提示工程的设计，如何有效地向LLM描述组合优化问题和CMSA算法的构造阶段，以引导LLM生成高质量的启发式规则；2) 如何将LLM生成的启发式规则集成到CMSA算法中，并保证算法的稳定性和效率；3) 如何设计评估指标，以有效地评估集成了LLM生成启发式规则的CMSA算法的性能。
🖼️ 关键图片
📊 实验亮点
实验结果表明，GPT-4o生成的启发式算法在CMSA算法中表现优于人工设计的启发式算法。具体来说，在更大和更密集的图上，GPT-4o生成的启发式算法的性能提升更加显著。这表明LLM在生成复杂问题的启发式算法方面具有巨大的潜力，能够超越人工设计的水平。
🎯 应用场景
该研究成果可应用于各种组合优化问题，如旅行商问题、车辆路径问题、调度问题等。通过利用LLM自动生成启发式算法，可以降低算法设计的门槛，加速算法的开发和部署，并提高算法的性能。此外，该方法还可以用于优化算法的自动化调参和算法组合，从而进一步提高优化算法的效率和鲁棒性。
📄 摘要（原文）
The integration of Large Language Models (LLMs) into optimization has created a powerful synergy, opening exciting research opportunities. This paper investigates how LLMs can enhance existing optimization algorithms. Using their pre-trained knowledge, we demonstrate their ability to propose innovative heuristic variations and implementation strategies. To evaluate this, we applied a non-trivial optimization algorithm, Construct, Merge, Solve and Adapt (CMSA) -- a hybrid metaheuristic for combinatorial optimization problems that incorporates a heuristic in the solution construction phase. Our results show that an alternative heuristic proposed by GPT-4o outperforms the expert-designed heuristic of CMSA, with the performance gap widening on larger and denser graphs. Project URL: https://imp-opt-algo-llms.surge.sh/