Back

Monte Carlo Tree Search for Comprehensive Exploration in LLM-Based Automatic Heuristic Design

Zhi ZhengZhuoliang XieZhenkun WangBryan Hooi

article2025ICML56 citations

Proposes a Monte Carlo Tree Search framework for large language model-driven automatic heuristic design that retains and refines temporarily underperforming algorithms in a tree structure to escape local optima in complex optimization tasks.

Listen

Complex operational challenges across logistics, task scheduling, and industrial routing rely heavily on heuristic algorithms. Traditionally, developing these heuristics requires extensive manual engineering and domain expertise. While recent advances use Large Language Models (LLMs) to automate heuristic generation, existing systems depend on population-based evolutionary computation. These approaches immediately discard underperforming algorithms to maintain a pool of top candidates, causing the search process to converge prematurely into suboptimal local optima.

The article introduces and evaluates MCTS-AHD, a framework that integrates Monte Carlo Tree Search (MCTS) with LLM-based automatic heuristic design. The main objective is to establish whether organizing generated algorithms into a search tree—allowing exploration of temporarily lower-performing candidates—can discover significantly higher-performing heuristics across complex optimization tasks.

The authors conducted extensive computational experiments across multiple algorithmic frameworks, including step-by-step constructive methods, Ant Colony Optimization, Guided Local Search, and cost-aware Bayesian Optimization. The evaluation covered classic NP-hard combinatorial optimization problems such as the Traveling Salesman, Vehicle Routing, and Knapsack problems, alongside Bayesian optimization benchmarks. MCTS-AHD organizes all generated Python functions into a tree, applying tailored prompting strategies (mutation, crossover, and tree-path reasoning) and an exploration-decay mechanism. The authors compared the system against manual heuristics, deep neural combinatorial solvers, and leading population-based LLM frameworks across multiple model backbones, notably GPT-4o-mini and GPT-3.5-turbo.

MCTS-AHD consistently outperformed existing population-based LLM baselines and handcrafted methods across benchmark tasks. In constructive Traveling Salesman benchmarks, MCTS-AHD achieved an optimality gap of 9.69% at 50 nodes and 11.79% at 100 nodes, noticeably outperforming baseline LLM methods that achieved gaps around 12% to 15%. Across multiple Ant Colony Optimization routing and packing benchmarks, the method achieved top ranks, frequently outperforming specialized neural solvers like DeepACO. In Bayesian optimization, MCTS-AHD generated acquisition functions that achieved lower gaps on test functions where prior methods experienced performance collapses. Furthermore, statistical significance testing confirmed a clear performance advantage over elite population baselines with at least 96% confidence.

These results demonstrate that structured tree search avoids the premature stagnation common in population-based heuristic generation. Retaining temporarily inferior algorithms provides the necessary stepping stones to reach high-performing solutions. Operationally, MCTS-AHD generates high-performing algorithms within a few CPU hours and negligible API costs (approximately $0.30 per run), avoiding the multi-week, GPU-heavy training cycles required by neural optimization approaches.

Organizations addressing complex operational optimization should consider adopting tree-search-guided LLM frameworks in place of standard evolutionary baselines, particularly for complex heuristic spaces with rich linguistic problem formulations. Where immediate implementation is planned, practitioners should provide clear problem descriptions, as the method performs best in white-box settings rather than black-box formulations where problem metadata is obscured. Further development should explore hybridizing tree search with population methods to accelerate convergence speeds.

A key limitation is the framework's reduced effectiveness in black-box scenarios where semantic descriptions are stripped, as well as its current inability to automatically resolve execution bugs in unconstrained code search tasks. Nonetheless, the experimental findings provide strong confidence that MCTS-AHD is a robust, cost-effective framework for automatic heuristic engineering in well-specified optimization problems.

Guangdong Provincial Key Laboratory of Fully Actuated System Control Theory and TechnologyNational University of SingaporeSouthern University of Science and Technologydomain knowledgeevolutionary computationlanguage modelLLM-based automatic heuristic designMonte Carlo Tree Searchhyper-heuristic approach
arXiv: 2501.08603zz1358m/MCTS-AHD-master

No sufficiently relevant recommendations were found.

Cover for Monte Carlo Tree Search for Comprehensive Exploration in LLM-Based Automatic Heuristic Design

Abstract

Handcrafting heuristics for solving complex optimization tasks (e.g., route planning and task allocation) is a common practice but requires extensive domain knowledge. Recently, Large Language Model (LLM)-based automatic heuristic design (AHD) methods have shown promise in generating high-quality heuristics without manual interventions. Existing LLM-based AHD methods employ a population to maintain a fixed number of top-performing LLM-generated heuristics and introduce evolutionary computation (EC) to iteratively enhance the population. However, these population-based procedures cannot fully develop the potential of each heuristic and are prone to converge into local optima. To more comprehensively explore the space of heuristics, this paper proposes to use Monte Carlo Tree Search (MCTS) for LLM-based heuristic evolution. The proposed MCTS-AHD method organizes all LLM-generated heuristics in a tree structure and can better develop the potential of temporarily underperforming heuristics. In experiments, MCTS-AHD delivers significantly higher-quality heuristics on various complex tasks. Our code is available³.

Topics

domain knowledgeevolutionary computationlanguage modellarge language modelsoptimizationtabu searchcompiler optimizationsheuristic evaluationheuristic approachesoptimization problems

Keywords

LLM-based automatic heuristic designMonte Carlo Tree Searchhyper-heuristic approachautomatic algorithm configurationtree-path reasoningAnt Colony OptimizationGenetic ProgrammingBayesian optimization

Table of Contents

  • 1. Introduction
  • 2. Preliminary
  • 2.1. Definition: AHD & LLM-based AHD
  • 2.2. Monte Carlo Tree Search
  • 3. MCTS-AHD
  • 3.1. LLM-based actions in MCTS-AHD
  • 3.2. MCTS settings
  • 3.3. Exploration-Decay
  • 4. Experiments
  • 4.1. MCTS-AHD for NP-hard CO Problems
  • 4.2. MCTS-AHD for Other Complex Tasks
  • 5. Discussion
  • 5.1. Ablation on Parameters and Components
  • 5.2. MCTS versus Population-based EC
  • Ability of MCTS-AHD in Escaping from Local Optima
  • 6. Conclusion
  • Impact Statement
  • Acknowledgements
  • References
  • A. Related Work
  • A.1. AHD
  • A.2. Neural Combinatorial Optimization (NCO)
  • A.3. LLM for EC
  • A.4. LLM for AHD
  • A.5. LLM for CO
  • A.6. LLM Inference with MCTS
  • A.7. LLM for Code Generation
  • A.8. Connection to General LLM Applications
  • B. Definition of Tasks
  • B.1. NP-hard CO Problems
  • B.2. Cost-Aware Acquisition Function Design in Bayesian Optimization
  • C. Definition of General Frameworks
  • C.1. Step-by-Step Construction
  • C.2. Ant Colony Optimization
  • C.3. Guided Local Search
  • C.4. Bayesian Optimization
  • D. Details of Evaluations & Experiments
  • E. Detailed Methodology
  • E.1. Prompts of MCTS Actions
  • E.2. The Prompt of the Thought-Alignment Process
  • E.3. Examples of LLM Outputs
  • E.4. Total Algorithm
  • F. Experiment Details
  • F.1. Designing Heuristics with the Step-by-step Construction Framework for ASP
  • F.2. Guided Local Search Framework
  • F.3. Time Consumption of MCTS-AHD Heuristic Evolution
  • F.4. P-values for Significance
  • F.5. MCTS-AHD with Other LLMs
  • F.6. Application on General Optimization Tasks
  • F.7. Results on TSPLib: Compare to GP-based AHD Methods
  • F.8. Compare to LLM-as-Optimizer Methods
  • F.9. Discussion: Ablation of Other Parameters
  • F.10. Discussion: The Advantage Scope of MCTS
  • G. Examples of Evolution
  • H. Baselines & Licenses
  • H.1. License

Knowls

  1. Knowl 1 — MCTS-AHD searches over a persistent tree of executable heuristics

    model/method

    MCTS-AHD uses a virtual root with no heuristic; every other node stores an LLM-generated executable Python heuristic and its linguistic description. Given a task, a predefined solving framework, an evaluation dataset DD, and an evaluation budget TT, it first creates initial heuristic nodes, evaluates them, and then repeatedly selects a node, generates and evaluates child heuristics, and propagates their values through the tree. It returns the heuristic with the best observed performance g(h)g(h), where gg is the task’s evaluation measure and is oriented so that larger values are better.

    For a node ncn_c and one of its children cc, selection uses

    UCT⁡(c)=Q(c)−qmin⁡qmax⁡−qmin⁡+λln⁡(N(nc)+1)N(c).\operatorname{UCT}(c)=\frac{Q(c)-q_{\min}}{q_{\max}-q_{\min}}+\lambda\sqrt{\frac{\ln(N(n_c)+1)}{N(c)}}.

    Here Q(n)Q(n) is a node’s quality, N(n)N(n) its visit count, and qmin⁡q_{\min} and qmax⁡q_{\max} the lowest and highest quality values encountered in the search; λ\lambda is the exploration factor. Starting at the root, the algorithm repeatedly follows the child with the largest UCT value until it reaches a leaf or the maximum tree depth. Newly generated heuristics are evaluated on DD, assigned Q=g(h)Q=g(h) and N=1N=1, and used to update the elite set and quality bounds. Backpropagation sets each ancestor’s quality to the maximum quality among its children and its visit count to the sum of its children’s visit counts. Search ends when the evaluation budget is reached. The paper uses a maximum tree depth of 1010.

  2. Knowl 2 — Six LLM actions generate and refine heuristic nodes

    model/method

    MCTS-AHD uses six actions to initialize or expand its heuristic tree. Initialization action i1i1 generates a heuristic from scratch. Mutation action m1m1 modifies an existing heuristic’s mechanisms or formulas, while m2m2 changes its parameter settings. Crossover action e1e1 uses several existing heuristics to prompt for a substantially different design. Crossover action e2e2 takes a parent and a reference heuristic, asking the LLM to retain the parent’s form while incorporating useful traits from the reference; the reference comes from the dynamically updated elite set of the ten highest-performing heuristics. Tree-path reasoning action s1s1 supplies the distinct heuristics, descriptions, and performances along a path from a selected leaf toward the root, and asks for a new heuristic informed by that history; it is skipped if the path contains only one unique heuristic.

    Prompts specify the task, the general solving framework, and the key function’s inputs and outputs. Except for initialization, they also provide existing heuristic implementations and descriptions. The generated artifact is Python code for a heuristic function.

  3. Knowl 3 — Progressive widening allocates new branches as nodes gain visits

    model/method

    MCTS-AHD uses progressive widening to revisit promising non-leaf nodes as the elite reference set and search context evolve. A node nn is allowed another child when ⌊N(n)α⌋≥∣Children⁡(n)∣\lfloor N(n)^\alpha\rfloor\geq |\operatorname{Children}(n)|, where N(n)N(n) is its visit count, Children⁡(n)\operatorname{Children}(n) is its set of children, and α=0.5\alpha=0.5 in the reported experiments. When the virtual root meets this condition, MCTS-AHD generates the new child with action e1e1; at other nodes it uses e2e2. For root expansions, the e1e1 prompt draws heuristics from two to five different subtrees. Widening is checked during selection, and any resulting heuristic is evaluated and incorporated into backpropagation.

  4. Knowl 4 — Exploration decreases linearly over the evaluation budget

    equation

    MCTS-AHD decays the exploration term in its UCT selection rule linearly as evaluations are used:

    λ=λ0T−tT.\lambda=\lambda_0\frac{T-t}{T}.

    Here TT is the total heuristic-evaluation budget, tt is the number of evaluations used so far, and λ0\lambda_0 is the initial exploration factor. The paper fixes λ0=0.1\lambda_0=0.1 across tasks. The intended effect is to explore temporarily lower-quality nodes more early in the search, then increasingly favor high-quality nodes later.

  5. Knowl 5 — Thought alignment generates descriptions from the heuristic code

    model/method

    Each MCTS-AHD heuristic generation uses two LLM calls. The first call, using the selected action prompt, produces the heuristic’s Python implementation and a brief design idea. The second call receives both the design idea and code and generates a more informative description, limited to fewer than three sentences, that reflects the implementation’s actual variables, priorities, parameters, and structure. This code-first description procedure is intended to reduce mismatches between generated code and its description that can occur when the LLM describes a heuristic before writing it. The paper reports that the second call is much shorter than the first and does not cause a severe increase in runtime or token cost.

  6. Knowl 6 — TSP and knapsack construction results favor MCTS-AHD on larger test scales

    empirical result

    In step-by-step construction experiments, the key function repeatedly chooses the next TSP city or knapsack item. The evaluation datasets contain 64 instances each: 50-city TSP and 100-item knapsack with capacity W=25W=25. Results below are averages over three runs with GPT-4o-mini; test sets contain 1,000 instances each. TSP objective values are minimized, while knapsack objective values are maximized.

    For TSP with 50, 100, and 200 cities, MCTS-AHD obtains objective values and optimality gaps of 6.2256.225 (9.69%), 8.6848.684 (11.79%), and 12.12012.120 (13.71%). EoH obtains 6.3946.394 (12.67%), 8.8948.894 (14.49%), and 12.43712.437 (16.68%), respectively. For knapsack with 50 items and W=12.5W=12.5, 100 items and W=25W=25, and 200 items and W=25W=25, MCTS-AHD obtains 20.01520.015 (0.11%), 40.25240.252 (0.05%), and 57.42357.423 (0.04%); EoH obtains 19.99319.993 (0.22%), 40.23140.231 (0.10%), and 57.39957.399 (0.09%). Thus MCTS-AHD improves on EoH across these six reported test settings, although its results remain short of the optima. The paper also reports that MCTS-AHD outperforms the manually designed greedy construction heuristic on the larger TSP tests and the task-trained POMO method on the 200-city TSP and 200-item knapsack tests.

  7. Knowl 7 — ACO experiments show gains over handcrafted ACO but not every learned baseline

    empirical result

    The paper evaluates heuristics designed for the ant-colony-optimization (ACO) framework on eight test sets, each containing 64 instances. MCTS-AHD uses GPT-4o-mini, and its reported objective values and optimality gaps are: TSP with 50 and 100 cities, 5.8015.801 (0.00%) and 8.1798.179 (0.00%); CVRP with 50 and 100 customers, 9.2869.286 (4.48%) and 15.78215.782 (5.70%); multiple knapsack with 100 and 200 items, 23.26923.269 (0.03%) and 42.49842.498 (0.00%); offline bin packing with 500 and 1,000 items, 204.094204.094 (0.48%) and 407.323407.323 (0.53%).

    Across these settings, MCTS-AHD beats the manually designed ACO baseline in all eight. It also beats DeepACO on the two TSP and two multiple-knapsack tests. The results are not uniformly best among learned methods: for example, DeepACO performs better on both CVRP tests, and on multiple-knapsack with 100 items HSEvo’s objective value of 23.27623.276 is slightly higher than MCTS-AHD’s 23.26923.269. The evidence therefore supports gains over handcrafted ACO and selected learned baselines, not universal dominance.

  8. Knowl 8 — Results extend to online packing, Bayesian optimization, and local search

    empirical result

    MCTS-AHD was evaluated beyond the main construction and ACO settings. For online bin packing, six test configurations each contain five Weibull-generated instances; the reported metric is gap to a lower bound. MCTS-AHD’s gaps are 2.45%, 0.50%, 1.06%, 0.32%, 0.74%, and 0.26%, averaging 0.89%. The corresponding average gaps are 0.99% for Funsearch and 1.17% for EoH.

    For cost-aware Bayesian optimization, cost-aware acquisition functions were evolved with a sampling budget of 12 and tested on 12 synthetic instances using an evaluation budget of 30 and 10 trials. MCTS-AHD’s acquisition functions outperform both the handcrafted acquisition functions and EoH on six of the twelve instances. In guided local search for TSP, MCTS-AHD produces optimality gaps of 0.0060%, 0.2106%, 0.9495%, and 1.5985% for 100, 200, 500, and 1,000 cities, respectively; its results improve on EoH at three of those four scales. On Gym MountainCar-v0, the reported average steps to reach the goal are 115.0 for MCTS-AHD, 117.6 for ReEvo, and 140.3 for EoH.

  9. Knowl 9 — Ablations support the proposed search components and actions

    empirical result

    Ablations evaluated step-by-step construction heuristics on TSP-50 and 100-item knapsack (KP-100); the metrics are optimality gaps, with lower values better. The original MCTS-AHD results are 10.661% and 0.059%. Removing progressive widening changes the gaps to 12.132% and 0.064%; removing thought alignment gives 11.640% and 0.061%; removing exploration decay gives 11.606% and 0.064%. Removing tree-path action s1s1 gives 11.919% and 0.062%, removing mutation m1m1 gives 10.921% and 0.083%, and removing mutation m2m2 gives 11.679% and 0.061%. Each ablation is worse than the original on at least one task, supporting the contribution of these components and actions.

    Changing the initial exploration factor also produces task-dependent results: λ0=0.05\lambda_0=0.05 gives gaps of 11.080% on TSP-50 and 0.056% on KP-100, while λ0=0.2\lambda_0=0.2 gives 12.124% and 0.034%. The default λ0=0.1\lambda_0=0.1 is therefore a generally useful shared setting in the paper’s experiments, rather than the best choice for every task individually.

  10. Knowl 10 — Performance is weaker without task descriptions, and convergence remains a limitation

    limitation

    MCTS-AHD’s results are less consistent in black-box settings, where descriptions of the task and framework are withheld and function input names are removed. In black-box ACO experiments, its objective values are 5.830 on TSP, 9.444 on CVRP, 23.191 on multiple knapsack, and 205.375 on offline bin packing. Compared with EoH, MCTS-AHD is slightly better on TSP but worse on the other three settings (the multiple-knapsack objective is maximized; the other listed objectives are minimized). The paper suggests that such settings are challenging because the LLM must generate high-quality heuristics from fewer descriptive cues, but presents this as an explanation rather than a proven cause.

    The authors also identify convergence speed as an open limitation and propose hybridizing MCTS with population-based search as future work. MCTS-AHD is designed to refine a key function within an existing solving framework; the paper notes that it cannot be directly applied when a problem has no such heuristic framework. In a code-search experiment, it was ineffective because the method could not handle code bugs.

Coverage note — Detailed per-instance TSPLib comparisons, additional LLM-model evaluations, significance-test tables, and secondary hyperparameter analyses are omitted because they supplement rather than define the central MCTS-AHD method and its main cross-task evidence.

References

  1. 1.Abgaryan, H., Harutyunyan, A., and Cazenave, T. Llms can schedule. arXiv preprint arXiv:2408.06993, 2024.
  2. 2.Alhindi, A., Alhindi, A., Alhejali, A., Alsheddy, A., Tairan, N., and Alhakami, H. Moea/d-gls: a multiobjective memetic algorithm using decomposition and guided local search. Soft Computing, 23:9605–9615, 2019.
  3. 3.Ansari, Z. N. and Daxini, S. D. A state-of-the-art review on meta-heuristics application in remanufacturing. Archives of Computational Methods in Engineering, 29(1):427–470, 2022.
  4. 4.Arnold, F. and Sorensen, K. Knowledge-guided local search for the vehicle routing problem. Computers & Operations Research, 105:32–46, 2019.
  5. 5.Arnold, F., Gendreau, M., and Sorensen, K. Efficiently solving very large-scale routing problems. Computers & operations research, 107:32–42, 2019.
  6. 6.Asani, E. O., Okeyinka, A. E., and Adebiyi, A. A. A computation investigation of the impact of convex hull subtour on the nearest neighbour heuristic. In 2023 International Conference on Science, Engineering and Business for Sustainable Development Goals (SEB-SDG), volume 1, pp. 1–7. IEEE, 2023.
  7. 7.Ausiello, G., Crescenzi, P., Gambosi, G., Kann, V., Marchetti-Spaccamela, A., and Protasi, M. Complexity and approximation: Combinatorial optimization problems and their approximability properties. Springer Science & Business Media, 2012.
  8. 8.Bäck, T., Fogel, D. B., and Michalewicz, Z. Handbook of evolutionary computation. Release, 97(1):B1, 1997.
  9. 9.Bello, I., Pham, H., Le, Q. V., Norouzi, M., and Bengio, S. Neural combinatorial optimization with reinforcement learning. arXiv preprint arXiv:1611.09940, 2016.
  10. 10.Berto, F., Hua, C., Zepeda, N. G., Hottung, A., Wouda, N., Lan, L., Park, J., Tierney, K., and Park, J. Routefinder: Towards foundation models for vehicle routing problems. arXiv preprint arXiv:2406.15007, 2024.
  11. 11.Biggs, N. The traveling salesman problem a guided tour of combinatorial optimization, 1986.
  12. 12.Blot, A., Hoos, H. H., Jourdan, L., Kessaci-Marmion, M.-É., and Trautmann, H. Mo-paramils: A multi-objective automatic algorithm configuration framework. In Learning and Intelligent Optimization: 10th International Conference, LION 10, Ischia, Italy, May 29–June 1, 2016, Revised Selected Papers 10, pp. 32–47. Springer, 2016.
  13. 13.Brandfonbrener, D., Henniger, S., Raja, S., Prasad, T., Loughridge, C. R., Cassano, F., Hu, S. R., Yang, J., Byrd, W. E., Zinkov, R., et al. Vermcts: Synthesizing multi-step programs using a verifier, a large language model, and tree search. In The 4th Workshop on Mathematical Reasoning and AI at NeurIPS’24, 2024.
  14. 14.Brecklinghaus, J. and Hougardy, S. The approximation ratio of the greedy algorithm for the metric traveling salesman problem. Operations Research Letters, 43(3):259–261, 2015.
  15. 15.Browne, C. B., Powley, E., Whitehouse, D., Lucas, S. M., Cowling, P. I., Rohlfshagen, P., Tavener, S., Perez, D., Samothrakis, S., and Colton, S. A survey of monte carlo tree search methods. IEEE Transactions on Computational Intelligence and AI in games, 4(1):1–43, 2012.
  16. 16.Burke, E. K., Gendreau, M., Hyde, M., Kendall, G., Ochoa, G., Ozcan, E., and Qu, R. Hyper-heuristics: A survey of the state of the art. Journal of the Operational Research Society, 64(12):1695–1724, 2013.
  17. 17.Burke, E. K., Hyde, M. R., Kendall, G., Ochoa, G., Özcan, E., and Woodward, J. R. A classification of hyper-heuristic approaches: revisited. Handbook of metaheuristics, pp. 453–477, 2019.
  18. 18.Cantu-Paz, E. et al. A survey of parallel genetic algorithms. Calculateurs paralleles, reseaux et systems repartis, 10 (2):141–171, 1998.
  19. 19.Castineiras, I., De Cauwer, M., and O’Sullivan, B. Weibull-based benchmarks for bin packing. In International Conference on Principles and Practice of Constraint Programming, pp. 207–222. Springer, 2012.
  20. 20.Christofides, N. Worst-case analysis of a new heuristic for the travelling salesman problem. In Operations Research Forum, volume 3, pp. 20. Springer, 2022.
  21. 21.Coulom, R. Computing “elo ratings” of move patterns in the game of go. ICGA journal, 30(4):198–208, 2007.
  22. 22.Dainese, N., Merler, M., Alakuijala, M., and Marttinen, P. Generating code world models with large language models guided by monte carlo tree search. arXiv preprint arXiv:2405.15383, 2024.
  23. 23.Dat, P. V. T., Doan, L., and Binh, H. T. T. Hsevo: Elevating automatic heuristic design with diversity-driven harmony search and genetic algorithm using llms. arXiv preprint arXiv:2412.14995, 2024.
  24. 24.DeLorenzo, M., Chowdhury, A. B., Gohil, V., Thakur, S., Karri, R., Garg, S., and Rajendran, J. Make every move count: Llm-based high-quality rtl code generation using mcts. arXiv preprint arXiv:2402.03289, 2024.
  25. 25.Desale, S., Rasool, A., Andhale, S., and Rane, P. Heuristic and meta-heuristic algorithms and their relevance to the real world: a survey. Int. J. Comput. Eng. Res. Trends, 351(5):2349–7084, 2015.
  26. 26.Dorigo, M., Birattari, M., and Stutzle, T. Ant colony optimization. IEEE computational intelligence magazine, 1 (4):28–39, 2006.
  27. 27.Drakulic, D., Michel, S., and Andreoli, J.-M. Goal: A generalist combinatorial optimization agent learning. arXiv preprint arXiv:2406.15079, 2024.
  28. 28.Duflo, G., Kieffer, E., Brust, M. R., Danoy, G., and Bouvry, P. A gp hyper-heuristic approach for generating tsp heuristics. In 2019 IEEE International Parallel and Distributed Processing Symposium Workshops (IPDPSW), pp. 521–529. IEEE, 2019.
  29. 29.Eiben, A. E. and Smith, J. E. Introduction to evolutionary computing. Springer, 2015.
  30. 30.Feng, X., Wan, Z., Wen, M., McAleer, S. M., Wen, Y., Zhang, W., and Wang, J. Alphazero-like tree-search can guide large language model decoding and training. arXiv preprint arXiv:2309.17179, 2023.
  31. 31.Fischetti, M., Lodi, A., and Toth, P. Exact methods for the asymmetric traveling salesman problem. The traveling salesman problem and its variations, pp. 169–205, 2007.
  32. 32.Fu, Z.-H., Qiu, K.-B., and Zha, H. Generalize a small pre-trained model to arbitrarily large tsp instances. In Proceedings of the AAAI conference on artificial intelligence, volume 35, pp. 7474–7482, 2021.
  33. 33.Gao, C., Shang, H., Xue, K., Li, D., and Qian, C. Towards generalizable neural solvers for vehicle routing problems via ensemble with transferrable local policy, 2024.
  34. 34.Guo, P.-F., Chen, Y.-H., Tsai, Y.-D., and Lin, S.-D. Towards optimizing with large language models. arXiv preprint arXiv:2310.05204, 2023.
  35. 35.Hadi, M. U., Qureshi, R., Shah, A., Irfan, M., Zafar, A., Shaikh, M. B., Akhtar, N., Wu, J., Mirjalili, S., et al. A survey on large language models: Applications, challenges, limitations, and practical usage. Authorea Preprints, 2023.
  36. 36.Hadi, M. U., Al Tashi, Q., Shah, A., Qureshi, R., Muneer, A., Irfan, M., Zafar, A., Shaikh, M. B., Akhtar, N., Wu, J., et al. Large language models: a comprehensive survey of its applications, challenges, limitations, and future prospects. Authorea Preprints, 2024.
  37. 37.He, K., Zhang, X., Ren, S., and Sun, J. Deep residual learning for image recognition. In Proceedings of the IEEE conference on computer vision and pattern recognition, pp. 770–778, 2016.
  38. 38.He, Q., Head, K. L., and Ding, J. Heuristic algorithm for priority traffic signal control. Transportation research record, 2259(1):1–7, 2011.
  39. 39.Helsgaun, K. An extension of the lin-kernighan-helsgaun tsp solver for constrained traveling salesman and vehicle routing problems. Roskilde: Roskilde University, 12:966–980, 2017.
  40. 40.Hemberg, E., Moskal, S., and O’Reilly, U.-M. Evolving code with a large language model. Genetic Programming and Evolvable Machines, 25(2):21, 2024.
  41. 41.Hendrycks, D., Basart, S., Kadavath, S., Mazeika, M., Arora, A., Guo, E., Burns, C., Puranik, S., He, H., Song, D., et al. Measuring coding challenge competence with apps. arXiv preprint arXiv:2105.09938, 2021.
  42. 42.Huang, L., Yu, W., Ma, W., Zhong, W., Feng, Z., Wang, H., Chen, Q., Peng, W., Feng, X., Qin, B., et al. A survey on hallucination in large language models: Principles, taxonomy, challenges, and open questions. ACM Transactions on Information Systems, 2023.
  43. 43.Huang, X., Liu, W., Chen, X., Wang, X., Wang, H., Lian, D., Wang, Y., Tang, R., and Chen, E. Understanding the planning of llm agents: A survey. arXiv preprint arXiv:2402.02716, 2024.
  44. 44.Hudson, B., Li, Q., Malencia, M., and Prorok, A. Graph neural network guided local search for the traveling salesperson problem. arXiv preprint arXiv:2110.05291, 2021.
  45. 45.Jiang, X., Wu, Y., Wang, Y., and Zhang, Y. Unco: Towards unifying neural combinatorial optimization through large language model. arXiv preprint arXiv:2408.12214, 2024.
  46. 46.Kambhampati, S., Valmeekam, K., Guan, L., Verma, M., Stechly, K., Bhambri, S., Saldyt, L., and Murthy, A. Llms can’t plan, but can help planning in llm-modulo frameworks. arXiv preprint arXiv:2402.01817, 2024.
  47. 47.Kim, M., Choi, S., Kim, H., Son, J., Park, J., and Bengio, Y. Ant colony sampling with gflownets for combinatorial optimization. arXiv preprint arXiv:2403.07041, 2024.
  48. 48.Kocsis, L. and Szepesvari, C. Bandit based monte-carlo planning. In European conference on machine learning, pp. 282–293. Springer, 2006.
  49. 49.Kool, W., Van Hoof, H., and Welling, M. Attention, learn to solve routing problems! arXiv preprint arXiv:1803.08475, 2018.
  50. 50.Korte, B. H., Vygen, J., Korte, B., and Vygen, J. Combinatorial optimization, volume 1. Springer, 2011.
  51. 51.Kwon, Y.-D., Choo, J., Kim, B., Yoon, I., Gwon, Y., and Min, S. Pomo: Policy optimization with multiple optima for reinforcement learning. Advances in Neural Information Processing Systems, 33:21188–21198, 2020.
  52. 52.Kwon, Y.-D., Choo, J., Yoon, I., Park, M., Park, D., and Gwon, Y. Matrix encoding networks for neural combinatorial optimization. Advances in Neural Information Processing Systems, 34:5138–5149, 2021.
  53. 53.Lam, R., Willcox, K., and Wolpert, D. H. Bayesian optimization with a finite budget: An approximate dynamic programming approach. Advances in Neural Information Processing Systems, 29, 2016.
  54. 54.Langdon, W. B. and Poli, R. Foundations of genetic programming. Springer Science & Business Media, 2013.
  55. 55.Lange, R., Tian, Y., and Tang, Y. Large language models as evolution strategies. In Proceedings of the Genetic and Evolutionary Computation Conference Companion, pp. 579–582, 2024.
  56. 56.Lee, E. H., Perrone, V., Archambeau, C., and Seeger, M. Cost-aware bayesian optimization. arXiv preprint arXiv:2003.10870, 2020a.
  57. 57.Lee, J., Jeon, W., Kim, G.-H., and Kim, K.-E. Monte-carlo tree search in continuous action spaces with value gradients. In Proceedings of the AAAI conference on artificial intelligence, volume 34, pp. 4561–4568, 2020b.
  58. 58.Lehman, J., Gordon, J., Jain, S., Ndousse, K., Yeh, C., and Stanley, K. O. Evolution through large models. In Handbook of Evolutionary Machine Learning, pp. 331–366. Springer, 2023.
  59. 59.Lin, S. and Kernighan, B. W. An effective heuristic algorithm for the traveling-salesman problem. Operations research, 21(2):498–516, 1973.
  60. 60.Liu, F., Tong, X., Yuan, M., and Zhang, Q. Algorithm evolution using large language model. arXiv preprint arXiv:2311.15249, 2023a.
  61. 61.Liu, F., Lin, X., Wang, Z., Zhang, Q., Xialiang, T., and Yuan, M. Multi-task learning for routing problem with cross-problem zero-shot generalization. In Proceedings of the 30th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, pp. 1898–1908, 2024a.
  62. 62.Liu, F., Xialiang, T., Yuan, M., Lin, X., Luo, F., Wang, Z., Lu, Z., and Zhang, Q. Evolution of heuristics: Towards efficient automatic algorithm design using large language model. In Forty-first International Conference on Machine Learning, 2024b.
  63. 63.Liu, F., Yao, Y., Guo, P., Yang, Z., Lin, X., Tong, X., Yuan, M., Lu, Z., Wang, Z., and Zhang, Q. A systematic survey on large language models for algorithm design. arXiv preprint arXiv:2410.14716, 2024c.
  64. 64.Liu, F., Zhang, R., Xie, Z., Sun, R., Li, K., Lin, X., Wang, Z., Lu, Z., and Zhang, Q. Llm4ad: A platform for algorithm design with large language model. arXiv preprint arXiv:2412.17287, 2024d.
  65. 65.Liu, S., Chen, C., Qu, X., Tang, K., and Ong, Y.-S. Large language models as evolutionary optimizers. In 2024 IEEE Congress on Evolutionary Computation (CEC), pp. 1–8. IEEE, 2024e.
  66. 66.Liu, W., Wang, H., Wang, J., Li, R., Yue, C., and Zhang, Y. Fr: Folded rationalization with a unified encoder. Advances in Neural Information Processing Systems, 35:6954–6966, 2022.
  67. 67.Liu, W., Wang, J., Wang, H., Li, R., Deng, Z., Zhang, Y., and Qiu, Y. D-separation for causal self-explanation. Advances in Neural Information Processing Systems, 36:43620–43633, 2023b.
  68. 68.Liu, W., Wang, J., Wang, H., Li, R., Qiu, Y., Zhang, Y., Han, J., and Zou, Y. Decoupled rationalization with asymmetric learning rates: A flexible lipschitz restraint. In Proceedings of the 29th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, pp. 1535–1547, 2023c.
  69. 69.Liu, W., Deng, Z., Niu, Z., Wang, J., Wang, H., Zhang, Y., and Li, R. Is the mmi criterion necessary for interpretability? degenerating non-causal features to plain noise for self-rationalization. Advances in Neural Information Processing Systems, 37:117636–117656, 2024f.
  70. 70.Liu, W., Wang, H., Wang, J., Deng, Z., Zhang, Y., Wang, C., and Li, R. Enhancing the rationale-input alignment for self-explaining rationalization. In 2024 IEEE 40th International Conference on Data Engineering (ICDE), pp. 2218–2230. IEEE, 2024g.
  71. 71.Liu, W., Deng, Z., Niu, Z., Wang, J., Wang, H., and Li, R. Exploring practical gaps in using cross entropy to implement maximum mutual information criterion for rationalization. Transactions of the Association for Computational Linguistics, 13:577–594, 2025.
  72. 72.Lopez-Ibáñez, M., Dubois-Lacoste, J., Cáceres, L. P., Birattari, M., and Stutzle, T. The irace package: Iterated racing for automatic algorithm configuration. Operations Research Perspectives, 3:43–58, 2016.
  73. 73.Luo, F., Lin, X., Zhong, M., Liu, F., Wang, Z., Sun, J., and Zhang, Q. Learning to insert for constructive neural vehicle routing solver. arXiv preprint arXiv:2505.13904, 2025a.
  74. 74.Luo, F., Wu, Y., Zheng, Z., and Wang, Z. Rethinking neural combinatorial optimization for vehicle routing problems with different constraint tightness degrees, 2025b. URL https://arxiv.org/abs/2505.24627.
  75. 75.Luong, P., Nguyen, D., Gupta, S., Rana, S., and Venkatesh, S. Adaptive cost-aware bayesian optimization. Knowledge-Based Systems, 232:107481, 2021.
  76. 76.Lusby, R. M., Larsen, J., Ehrgott, M., and Ryan, D. An exact method for the double tsp with multiple stacks. International Transactions in Operational Research, 17 (5):637–652, 2010.
  77. 77.Ma, Y., Li, J., Cao, Z., Song, W., Zhang, L., Chen, Z., and Tang, J. Learning to iteratively solve routing problems with dual-aspect collaborative transformer. Advances in Neural Information Processing Systems, 34:11096–11107, 2021.
  78. 78.Ma, Y., Cao, Z., and Chee, Y. M. Learning to search feasible and infeasible regions of routing problems with flexible neural k-opt. In Advances in Neural Information Processing Systems, volume 36, 2023.
  79. 79.Mei, Y., Chen, Q., Lensen, A., Xue, B., and Zhang, M. Explainable artificial intelligence by genetic programming: A survey. IEEE Transactions on Evolutionary Computation, 27(3):621–641, 2022.
  80. 80.Merz, P. and Freisleben, B. Genetic local search for the tsp: New results. In Proceedings of 1997 IEEE International Conference on Evolutionary Computation (ICEC’97), pp. 159–164. IEEE, 1997.
  81. 81.Meyerson, E., Nelson, M. J., Bradley, H., Gaier, A., Moradi, A., Hoover, A. K., and Lehman, J. Language model crossover: Variation through few-shot prompting. arXiv preprint arXiv:2302.12170, 2023.
  82. 82.Mockus, J. On bayesian methods for seeking the extremum. In Proceedings of the IFIP Technical Conference, pp. 400–404, 1974.
  83. 83.Naveed, H., Khan, A. U., Qiu, S., Saqib, M., Anwar, S., Usman, M., Akhtar, N., Barnes, N., and Mian, A. A comprehensive overview of large language models. arXiv preprint arXiv:2307.06435, 2023.
  84. 84.Qi, Z., Ma, M., Xu, J., Zhang, L. L., Yang, F., and Yang, M. Mutual reasoning makes smaller llms stronger problem-solvers. arXiv preprint arXiv:2408.06195, 2024.
  85. 85.Rajendran, C. Heuristic algorithm for scheduling in a flow-shop to minimize total flowtime. International Journal of Production Economics, 29(1):65–73, 1993.
  86. 86.Reinelt, G. Tsplib—a traveling salesman problem library. ORSA journal on computing, 3(4):376–384, 1991.
  87. 87.Romera-Paredes, B., Barekatain, M., Novikov, A., Balog, M., Kumar, M. P., Dupont, E., Ruiz, F. J., Ellenberg, J. S., Wang, P., Fawzi, O., et al. Mathematical discoveries from program search with large language models. Nature, 625 (7995):468–475, 2024.
  88. 88.Rosenkrantz, D. J., Stearns, R. E., and Lewis, II, P. M. An analysis of several heuristics for the traveling salesman problem. SIAM journal on computing, 6(3):563–581, 1977.
  89. 89.Sanchez-Díaz, X., Ortiz-Bayliss, J. C., Amaya, I., Cruz-Duarte, J. M., Conant-Pablos, S. E., and Terashima-Marín, H. A feature-independent hyper-heuristic approach for solving the knapsack problem. Applied Sciences, 11(21):10209, 2021.
  90. 90.Sengupta, L., Mariescu-Istodor, R., and Fränti, P. Which local search operator works best for the open-loop tsp? Applied Sciences, 9(19):3985, 2019.
  91. 91.Shahriari, B., Swersky, K., Wang, Z., Adams, R. P., and De Freitas, N. Taking the human out of the loop: A review of bayesian optimization. Proceedings of the IEEE, 104 (1):148–175, 2015.
  92. 92.Shi, W. W., Han, W., and Si, W. C. A hybrid genetic algorithm based on harmony search and its improving. In Informatics and Management Science I, pp. 101–109. Springer, 2013.
  93. 93.Shinn, N., Cassano, F., Gopinath, A., Narasimhan, K., and Yao, S. Reflexion: Language agents with verbal reinforcement learning. Advances in Neural Information Processing Systems, 36, 2024.
  94. 94.Silver, D., Huang, A., Maddison, C. J., Guez, A., Sifre, L., Van Den Driessche, G., Schrittwieser, J., Antonoglou, I., Panneershelvam, V., Lanctot, M., et al. Mastering the game of go with deep neural networks and tree search. nature, 529(7587):484–489, 2016.
  95. 95.Snoek, J., Larochelle, H., and Adams, R. P. Practical bayesian optimization of machine learning algorithms. Advances in neural information processing systems, 25, 2012.
  96. 96.Stutzle, T. and López-Ibáñez, M. Automated design of metaheuristic algorithms. Handbook of metaheuristics, pp. 541–579, 2019.
  97. 97.Sui, J., Ding, S., Xia, B., Liu, R., and Bu, D. Neuralgls: learning to guide local search with graph convolutional network for the traveling salesman problem. Neural Computing and Applications, 36(17):9687–9706, 2024.
  98. 98.Swiechowski, M., Godlewski, K., Sawicki, B., and Mandziuk, J. Monte carlo tree search: A review of recent modifications and applications. Artificial Intelligence Review, 56(3):2497–2562, 2023.
  99. 99.Tan, C. S., Mohd-Mokhtar, R., and Arshad, M. R. A comprehensive review of coverage path planning in robotics using classical and heuristic algorithms. IEEE Access, 9:119310–119342, 2021.
  100. 100.Tuononen, J. Analysis of rebuild local search operator for tsp. Master’s thesis, Ita-Suomen yliopisto, 2022.
  101. 101.Vaswani, A., Shazeer, N., Parmar, N., Uszkoreit, J., Jones, L., Gomez, A. N., Kaiser, Ł., and Polosukhin, I. Attention is all you need. Advances in neural information processing systems, 30, 2017.
  102. 102.Vinyals, O., Fortunato, M., and Jaitly, N. Pointer networks. Advances in neural information processing systems, 28, 2015.
  103. 103.Voudouris, C. and Tsang, E. Guided local search and its application to the traveling salesman problem. European journal of operational research, 113(2):469–499, 1999.
  104. 104.Wang, Z., Yu, J., Ma, D., Chen, Z., Wang, Y., Li, Z., Xiong, F., Wang, Y., Tang, L., Zhang, W., et al. Rare: Retrieval-augmented reasoning modeling. arXiv preprint arXiv:2503.23513, 2025.
  105. 105.Wei, J., Wang, X., Schuurmans, D., Bosma, M., Xia, F., Chi, E., Le, Q. V., Zhou, D., et al. Chain-of-thought prompting elicits reasoning in large language models. Advances in neural information processing systems, 35:24824–24837, 2022.
  106. 106.Weston, J. and Sukhbaatar, S. System 2 attention (is something you might need too). arXiv preprint arXiv:2311.11829, 2023.
  107. 107.Williams, C. K. and Rasmussen, C. E. Gaussian processes for machine learning, volume 2. MIT press Cambridge, MA, 2006.
  108. 108.Wu, Y., Song, W., Cao, Z., Zhang, J., and Lim, A. Learning improvement heuristics for solving routing problems.. IEEE Transactions on Neural Networks and Learning Systems, 2021.
  109. 109.Wu, Z., Qi, Q., Zhuang, Z., Sun, H., and Wang, J. Pre-tokenization of numbers for large language models. In The Second Tiny Papers Track at ICLR 2024, 2024.
  110. 110.Xin, L., Song, W., Cao, Z., and Zhang, J. Neurolkh: Combining deep learning model with lin-kernighan-helsgaun heuristic for solving the traveling salesman problem. Advances in Neural Information Processing Systems, 34:7472–7483, 2021.
  111. 111.Yang, C., Wang, X., Lu, Y., Liu, H., Le, Q. V., Zhou, D., and Chen, X. Large language models as optimizers, 2024. URL https://arxiv.org/abs/2309.03409.
  112. 112.Yao, S., Liu, F., Lin, X., Lu, Z., Wang, Z., and Zhang, Q. Multi-objective evolution of heuristic using large language model. arXiv preprint arXiv:2409.16867, 2024a.
  113. 113.Yao, S., Yu, D., Zhao, J., Shafran, I., Griffiths, T., Cao, Y., and Narasimhan, K. Tree of thoughts: Deliberate problem solving with large language models. Advances in Neural Information Processing Systems, 36, 2024b.
  114. 114.Yao, Y., Liu, F., Cheng, J., and Zhang, Q. Evolve cost-aware acquisition functions using large language models. In International Conference on Parallel Problem Solving from Nature, pp. 374–390. Springer, 2024c.
  115. 115.Ye, H., Wang, J., Cao, Z., Berto, F., Hua, C., Kim, H., Park, J., and Song, G. Reevo: Large language models as hyper-heuristics with reflective evolution. arXiv preprint arXiv:2402.01145, 2024a.
  116. 116.Ye, H., Wang, J., Cao, Z., Liang, H., and Li, Y. Deepaco: neural-enhanced ant systems for combinatorial optimization. Advances in Neural Information Processing Systems, 36, 2024b.
  117. 117.Ye, H., Wang, J., Liang, H., Cao, Z., Li, Y., and Li, F. Glop: Learning global partition and local construction for solving large-scale routing problems in real-time. In Proceedings of the AAAI Conference on Artificial Intelligence, 2024c.
  118. 118.Yin, H., Kononova, A. V., Back, T., and van Stein, N. Controlling the mutation in large language models for the efficient evolution of algorithms. arXiv preprint arXiv:2412.03250, 2024.
  119. 119.Yu, H. and Liu, J. Deep insights into automated optimization with large language models and evolutionary algorithms. arXiv preprint arXiv:2410.20848, 2024.
  120. 120.Zhang, D., Huang, X., Zhou, D., Li, Y., and Ouyang, W. Accessing gpt-4 level mathematical olympiad solutions via monte carlo tree self-refine with llama-3 8b. arXiv preprint arXiv:2406.07394, 2024a.
  121. 121.Zhang, D., Zhoubian, S., Hu, Z., Yue, Y., Dong, Y., and Tang, J. Rest-mcts*: Llm self-training via process reward guided tree search. arXiv preprint arXiv:2406.03816, 2024b.
  122. 122.Zhang, Y., Pan, Y., Wang, Y., and Cai, J. Pybench: Evaluating llm agent on various real-world coding tasks. arXiv preprint arXiv:2407.16732, 2024c.
  123. 123.Zheng, Z. and Lee, W. S. Reasoning-cv: Fine-tuning powerful reasoning llms for knowledge-assisted claim verification. arXiv preprint arXiv:2505.12348, 2025.
  124. 124.Zheng, Z., Yao, S., Li, G., Han, L., and Wang, Z. Pareto improver: Learning improvement heuristics for multi-objective route planning. IEEE Transactions on Intelligent Transportation Systems, 2023.
  125. 125.Zheng, Z., Yao, S., Wang, Z., Tong, X., Yuan, M., and Tang, K. Dpn: Decoupling partition and navigation for neural solvers of min-max vehicle routing problems. arXiv preprint arXiv:2405.17272, 2024a.
  126. 126.Zheng, Z., Zhou, C., Xialiang, T., Yuan, M., and Wang, Z. Udc: A unified neural divide-and-conquer framework for large-scale combinatorial optimization problems. arXiv preprint arXiv:2407.00312, 2024b.
  127. 127.Zhou, A., Yan, K., Shlapentokh-Rothman, M., Wang, H., and Wang, Y.-X. Language agent tree search unifies reasoning acting and planning in language models. arXiv preprint arXiv:2310.04406, 2023.

Citation

MLA
Zheng, Z., et al. “Monte Carlo Tree Search for Comprehensive Exploration in LLM-Based Automatic Heuristic Design”. arXiv, 2025, https://doi.org/10.48550/arxiv.2501.08603.
APA
Zheng, Z., Xie, Z., Wang, Z., & Hooi, B. (2025). Monte Carlo Tree Search for Comprehensive Exploration in LLM-Based Automatic Heuristic Design. arXiv. https://doi.org/10.48550/arxiv.2501.08603
Chicago
Zheng, Z., Z. Xie, Z. Wang, and B. Hooi. 2025. “Monte Carlo Tree Search for Comprehensive Exploration in LLM-Based Automatic Heuristic Design”. Preprint, ArXiv. https://doi.org/10.48550/arxiv.2501.08603.
Harvard
Zheng, Z. et al. (2025) “Monte Carlo Tree Search for Comprehensive Exploration in LLM-Based Automatic Heuristic Design”. arXiv. Available at: https://doi.org/10.48550/arxiv.2501.08603.
Vancouver
1. Zheng Z, Xie Z, Wang Z, Hooi B (2025) Monte Carlo Tree Search for Comprehensive Exploration in LLM-Based Automatic Heuristic Design. https://doi.org/10.48550/arxiv.2501.08603

BibTeX

@misc{https://doi.org/10.48550/arxiv.2501.08603,
  doi = {10.48550/ARXIV.2501.08603},
  url = {https://arxiv.org/abs/2501.08603},
  author = {Zheng, Zhi and Xie, Zhuoliang and Wang, Zhenkun and Hooi, Bryan},
  keywords = {Artificial Intelligence (cs.AI), FOS: Computer and information sciences, FOS: Computer and information sciences},
  title = {Monte Carlo Tree Search for Comprehensive Exploration in LLM-Based Automatic Heuristic Design},
  publisher = {arXiv},
  year = {2025},
  copyright = {arXiv.org perpetual, non-exclusive license}
}
Metadata:DOI registry

Source Code

This paper has an official code repository available. Click below to access the source code.

View Repository

Access the Paper

This paper is available from its original source. Click below to access the PDF.

Open PDF
License: https://creativecommons.org/licenses/by/4.0/