用大模型自动设计新优化问题的启发式算法,效果优于人工设计。
Leveraging Large Language Models to Develop Heuristics for Emerging Optimization Problems
- 基于上下文提示的进化框架,让大模型生成针对特定问题的启发式算法。
- 小模型在加入问题描述后,性能超越大模型,且结果更稳定。
- 方法适用于冷门优化问题,适合自动化算法设计的研究者。
组合优化问题通常依赖启发式算法生成高效解。但人工设计启发式成本高,受限于设计者经验。近年来,大语言模型(LLMs)在人工智能领域取得进展,可通过进化框架实现启发式自动生成。现有研究仅聚焦于旅行商问题、在线装箱问题等经典问题。本研究探讨大模型能否有效为尚未广泛研究的新兴优化问题生成启发式算法,以单元载荷预调度问题为例。提出上下文启发式进化(CEoH)框架,作为原进化启发式(EoH)框架的扩展,通过引入问题特定描述增强上下文学习能力。通过计算实验评估CEoH与EoH的表现并进行对比。结果显示,CEoH使较小的LLM更一致地生成高质量启发式算法,甚至优于大型模型;大模型无论是否使用上下文提示均表现稳健。生成的启发式算法对多种实例配置具备可扩展性。
原文摘要 · Abstract (English)
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.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。