用大模型+树搜索自动优化启发式算法，提升组合优化求解效果。
Planning of Heuristics: Strategic Planning on Large Language Models with Monte Carlo Tree Search for Automating Heuristic Optimization
- 结合大模型反思与蒙特卡洛树搜索，迭代改进启发式策略。
- 在旅行商和流水线调度问题上超越人工设计与现有自动化方法。
- 适合想用AI自动生成高效优化算法的研究者和工程师。
启发式算法在解决组合优化问题（COPs）方面取得了巨大成功。然而，人工设计的启发式算法需要大量领域知识和测试时间。由于大语言模型（LLMs）具备强大的内容理解与生成能力，且知识覆盖多个领域，因此有望实现启发式算法的自动优化。为此，我们提出「启发式规划」（PoH），一种将LLM自我反思与蒙特卡洛树搜索（MCTS）相结合的优化方法。PoH通过评估生成的启发式（状态）并提供改进建议（动作），根据评估结果（奖励）迭代优化，有效模拟未来状态以搜索更高奖励路径。本文将PoH应用于旅行商问题（TSP）和流水车间调度问题（FSSP）。实验结果表明，PoH优于人工设计的启发式及基于LLM的其他自动启发式设计方法，在大规模实例上达到当前最优性能，实现了基于大模型的启发式自动优化新高度。
原文摘要 · Abstract (English)
Heuristics have achieved great success in solving combinatorial optimization problems~(COPs). However, heuristics designed by humans require too much domain knowledge and testing time. Since Large Language Models~(LLMs) possess strong capabilities to understand and generate content with a knowledge base that covers various domains, they offer potential ways to automatically optimize heuristics. To this end, we propose Planning of Heuristics~(PoH), an optimization method that integrates LLM self-reflection with Monte Carlo Tree Search, a well-known planning algorithm. PoH iteratively refines generated heuristics by evaluating their performance and providing improvement suggestions. Our method enables to iteratively evaluate the generated heuristics~(states) and improve them based on the improvement suggestions~(actions) and evaluation results~(rewards), by effectively simulating future states to search for paths with higher rewards. In this paper, we apply PoH to solve the Traveling Salesman Problem and the Flow Shop Scheduling Problem. The experimental results show that PoH outperforms hand-crafted heuristics and other Automatic Heuristic Design methods based on LLMs, and achieves the state-of-the-art performance in automating heuristic optimization with LLMs to solve tested COPs, especially with large sizes.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。