Planning of Heuristics: Strategic Planning on Large Language Models with Monte Carlo Tree Search for Automating Heuristic Optimization
This addresses the need for efficient heuristic optimization in combinatorial optimization, reducing reliance on human expertise and testing time, though it is incremental as it builds on existing LLM and planning methods.
The paper tackles the problem of automating heuristic design for combinatorial optimization problems by proposing Planning of Heuristics (PoH), which integrates LLM self-reflection with Monte Carlo Tree Search, and it outperforms hand-crafted heuristics and other LLM-based methods, achieving state-of-the-art performance on problems like the Traveling Salesman Problem and Flow Shop Scheduling Problem, especially for large sizes.
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.