Leveraging Large Language Models to Develop Heuristics for Emerging Optimization Problems

📄 arXiv: 2503.03350v1 📥 PDF

作者: Thomas Bömer, Nico Koltermann, Max Disselnmeyer, Laura Dörr, Anne Meyer

分类: cs.AI

发布日期: 2025-03-05

备注: Under review LION19: The 19th Learning and Intelligent OptimizatioN Conference

💡 一句话要点

提出CEoH框架，利用大语言模型为新兴优化问题自动生成启发式算法。

🎯 匹配领域: 支柱九：具身大模型 (Embodied Foundation Models)

关键词: 大语言模型 启发式算法 组合优化 自动化 上下文学习

📋 核心要点

  1. 手动设计组合优化问题的启发式算法成本高昂，且依赖于设计者的专业知识，存在局限性。
  2. CEoH框架通过结合问题描述，增强LLM在生成启发式算法时的上下文学习能力，从而提升生成质量。
  3. 实验表明，CEoH能使较小LLM生成更高质量的启发式算法，甚至超越大型模型，并具备良好的可扩展性。

📝 摘要（中文）

组合优化问题通常依赖启发式算法来生成高效的解决方案。然而，手动设计启发式算法耗费资源且受设计者专业知识的限制。人工智能，特别是大型语言模型（LLM）的最新进展，展示了通过进化框架自动生成启发式算法的潜力。目前的研究主要集中在旅行商问题和在线装箱问题等广为人知的组合优化问题上，以设计构造性启发式算法。本研究以单元负载预编组问题为例，探讨了LLM是否能有效地为尚未得到广泛研究的利基优化问题生成启发式算法。我们提出了启发式算法的上下文进化（CEoH）框架，它是启发式算法进化（EoH）框架的扩展，它结合了特定问题的描述，以增强启发式算法生成过程中的上下文学习。通过计算实验，我们评估了CEoH和EoH，并比较了结果。结果表明，CEoH使较小的LLM能够更一致地生成高质量的启发式算法，甚至优于较大的模型。较大的模型在有或没有上下文提示的情况下都表现出强大的性能。生成的启发式算法表现出对不同实例配置的可扩展性。

🔬 方法详解

问题定义：论文旨在解决新兴的、研究较少的组合优化问题，例如单元负载预编组问题，其难点在于缺乏针对性的启发式算法。现有方法依赖人工设计，耗时且效果受限。

核心思路：核心思路是利用大型语言模型（LLM）的强大生成能力，通过进化框架自动生成针对特定问题的启发式算法。通过提供问题描述，增强LLM对问题的理解，从而生成更有效的启发式策略。

技术框架：论文提出了Contextual Evolution of Heuristics (CEoH) 框架，它是 Evolution of Heuristics (EoH) 框架的扩展。CEoH框架包含以下主要阶段：1) 问题描述：提供关于优化问题的详细信息。2) LLM启发式算法生成：利用LLM生成候选启发式算法。3) 评估：在问题实例上评估生成的启发式算法的性能。4) 进化：根据性能反馈，通过变异和交叉等操作进化启发式算法。

关键创新：关键创新在于将问题上下文信息融入到LLM的启发式算法生成过程中。传统的EoH框架主要依赖LLM自身的知识，而CEoH通过提供问题描述，显著提升了LLM的上下文学习能力，使其能够更好地理解问题并生成更有效的启发式算法。

关键设计：CEoH的关键设计包括：1) 问题描述的构建：如何有效地将问题信息编码为LLM可以理解的提示。2) 进化策略的选择：采用何种变异和交叉算子来进化启发式算法。3) 评估指标的选取：选择合适的指标来衡量启发式算法的性能，例如解的质量和运行时间。论文中使用了不同的LLM模型，并比较了它们在有无上下文信息下的性能表现。

🖼️ 关键图片

fig_0
fig_1
fig_2

📊 实验亮点

实验结果表明，CEoH框架能够使较小的LLM更一致地生成高质量的启发式算法，甚至优于较大的模型。例如，在单元负载预编组问题上，使用CEoH框架的较小模型在性能上超越了未使用上下文信息的大型模型。此外，生成的启发式算法表现出对不同实例配置的可扩展性，证明了该方法的鲁棒性。

🎯 应用场景

该研究成果可应用于各种新兴的组合优化问题，例如物流优化、资源调度、生产计划等。通过自动生成启发式算法，可以降低人工设计成本，提高问题求解效率，并为解决复杂优化问题提供新的思路。未来，该方法有望扩展到更广泛的优化领域，并与其他AI技术相结合，实现更智能的优化求解。

📄 摘要（原文）

Combinatorial optimization problems often rely on heuristic algorithms to generate efficient solutions. However, the manual design of heuristics is resource-intensive and constrained by the designer's expertise. Recent advances in artificial intelligence, particularly large language models (LLMs), have demonstrated the potential to automate heuristic generation through evolutionary frameworks. Recent works focus only on well-known combinatorial optimization problems like the traveling salesman problem and online bin packing problem when designing constructive heuristics. This study investigates whether LLMs can effectively generate heuristics for niche, not yet broadly researched optimization problems, using the unit-load pre-marshalling problem as an example case. We propose the Contextual Evolution of Heuristics (CEoH) framework, an extension of the Evolution of Heuristics (EoH) framework, which incorporates problem-specific descriptions to enhance in-context learning during heuristic generation. Through computational experiments, we evaluate CEoH and EoH and compare the results. Results indicate that CEoH enables smaller LLMs to generate high-quality heuristics more consistently and even outperform larger models. Larger models demonstrate robust performance with or without contextualized prompts. The generated heuristics exhibit scalability to diverse instance configurations.