PaperlayerView exact revision on arXiv

Source-linked AI summary

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

Zhi Zheng, Zhuoliang Xie, Zhenkun Wang, Bryan Hooi

arXiv:2501.08603v3cs.AI

TL;DR

Complex heuristic design is labor-intensive and population-based LLM methods may discard temporarily weak but promising functions, limiting exploration. MCTS-AHD organizes generated heuristics in a tree and uses MCTS to evolve them more comprehensively, achieving higher-quality heuristics across complex tasks. Its convergence speed remains improvable.

  • Problem

    Manual heuristic design requires extensive task-specific expertise, while population-based LLM-AHD methods can discard temporarily underperforming heuristics and become trapped in local optima.

  • Method

    MCTS-AHD organizes all generated heuristic functions in a tree and applies MCTS with progressive widening, tree-path prompting, thought alignment, and exploration decay.

  • Results

    MCTS-AHD achieves significantly higher-quality heuristics than handcrafted heuristics and existing LLM-based AHD methods across NP-hard optimization and Bayesian Optimization-related tasks.

  • Takeaways & Limitations

    MCTS is presented as a more promising evolution method than population-based evolutionary computation for comprehensive exploration in LLM-based AHD.

  • Takeaways & Limitations

    MCTS-AHD's convergence speed can still be improved, motivating future MCTS-population hybrid methods for better evolution efficiency.

Abstract

from arXiv · show

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.

1. Introduction

Manual heuristic design is effective for complex optimization tasks but labor-intensive and dependent on expert knowledge. LLM-based AHD reduces manual intervention, yet population-based evolution can discard promising heuristics and become trapped in local optima; MCTS-AHD addresses this through tree-based exploration.

  • Manual heuristics support complex optimization applications but require intricate workflows, parameter settings, and task-specific expertise.
  • LLM-based AHD designs high-quality heuristics without manual intervention within predefined general frameworks.
  • Population-based LLM evolution eliminates inferior heuristics, preventing a worse-before-better refinement path and potentially trapping search in suboptimal local optima.
  • MCTS-AHD organizes generated heuristics in a tree and enables refinement of temporarily underperforming functions while retaining focus on stronger ones.
  • MCTS-AHD additionally uses tree-special prompting, thought alignment, and exploration decay to support heuristic refinement and search across diverse tasks.

2. Preliminary

AHD searches a predefined heuristic space using performance evaluations, while LLM-based AHD evolves heuristics through population-based prompts. MCTS supplies a tree-search alternative that preserves generated functions, selects promising states, and expands the search progressively.

  • 2.1. Definition: AHD & LLM-based AHD: AHD searches for the best-performing heuristic h* in a feasible heuristic space H for a task P.
  • 2.1. Definition: AHD & LLM-based AHD: The performance function g evaluates heuristic solutions on a task-specific dataset D using the objective function f.
  • 2.1. Definition: AHD & LLM-based AHD: LLM-based AHD maintains a fixed population and prompts LLMs to generate heuristics from existing members using mutation- or crossover-like strategies.
  • 2.2. Monte Carlo Tree Search: MCTS-AHD stores generated executable heuristics and descriptions in a tree, using mutation, crossover, tree-path reasoning, and exploration decay for evolution.
  • 2.2. Monte Carlo Tree Search: MCTS repeatedly selects the child with the highest UCT value, expands it, simulates quality, and backpropagates updated quality and visit values.
  • 2.2. Monte Carlo Tree Search: Progressive widening gradually adds child nodes as visit counts increase, adapting MCTS to extensive or dynamically changing action spaces.

3. MCTS-AHD

MCTS-AHD evolves LLM-generated heuristics in a tree, retaining temporarily underperforming candidates for further development while balancing exploration and exploitation. It combines multiple LLM actions, progressive widening, evaluation-based simulation, and exploration decay to search heuristic spaces until a performance limit is reached.

  • MCTS-AHD preserves all generated heuristics in a tree whose non-root nodes represent executable heuristic implementations with linguistic descriptions.The virtual root represents no heuristic, while other nodes retain the history and structure of generated heuristics.
  • LLM-based actions in MCTS-AHD: LLM-based evolution combines initialization, mutation, crossover, and tree-path reasoning actions to generate new heuristic functions.Mutation changes mechanisms, formulas, or parameter settings; crossover combines existing designs, while tree-path reasoning analyzes evolutionary histories from leaves to the root.
  • LLM-based actions in MCTS-AHD: A thought-alignment process generates concise linguistic descriptions after heuristic code generation, requiring two LLM calls for each MCTS action.The second call summarizes the generated Python implementation in up to three sentences and is significantly shorter than the first.
  • MCTS-AHD uses selection, expansion, simulation, and backpropagation, terminating after T heuristic performance evaluations.Simulation evaluates newly generated heuristics on dataset D and assigns their performance g(h) as node quality.
  • MCTS settings: MCTS-AHD uses progressive widening to re-explore non-leaf nodes, applying crossover e1 at the root and e2 at other qualifying nodes.The e1 action samples heuristics from 2 to 5 different subtrees, while e2 uses an elite set of high-performing heuristics.
  • Exploration-Decay: The exploration factor λ is linearly decayed so MCTS explores temporarily inferior nodes earlier and concentrates on higher-quality nodes later.MCTS-AHD sets λ0 = 0.1 for all tasks to preserve generalization ability across tasks.

4. Experiments

MCTS-AHD is evaluated across NP-hard combinatorial optimization problems and a Bayesian Optimization task using multiple general frameworks and baselines. Across these settings, it generally outperforms handcrafted heuristics and existing LLM-based AHD methods, with especially broad gains on CO benchmarks.

  • Experimental scope: The experiments cover NP-hard CO problems and Cost-aware Acquisition Function design for Bayesian Optimization using step-by-step construction, ACO, GLS, and BO frameworks.Evaluations include TSP, KP, CVRP, MKP, online and offline BPP, ASP, and synthetic BO instances.
  • Step-by-step construction: Table 1 evaluates TSP and KP heuristics on six test sets containing 1,000 instances each, with in-domain scales emphasized because AHD generalization is not guaranteed.LLM-based methods are run three times and averaged; LKH and OR-Tools provide optimal references for TSP and KP.
  • Step-by-step construction: MCTS-AHD designs better 200-node TSP and KP heuristics than the task-specific-training NCO method POMO.The comparison highlights performance beyond methods requiring task-specific training.
  • Online BPP: MCTS-AHD achieves superior average performance across six online BPP test sets.The online BPP evaluation uses four Weibull instances with diverse scales, and Table 3 reports gaps to the lower bound averaged over three runs.
  • ACO framework: MCTS-AHD significantly outperforms EoH and ReEvo across all in-domain and out-of-domain ACO test sets for TSP, CVRP, MKP, and offline BPP.It also consistently surpasses manually designed ACO heuristics in all eight test sets and exceeds DeepACO on TSP and MKP test sets.
  • Bayesian Optimization: MCTS-AHD-designed BO heuristic CAFs outperform handcrafted heuristics and EoH in six of twelve synthetic instances.The study uses Ackley and Rastrigin evaluation instances plus ten additional synthetic instances, with five independent trials and a sampling budget of 12.

5. Discussion

The discussion reports component ablations, parameter sensitivity, and comparisons showing that MCTS-AHD more comprehensively explores heuristic space than population-based evolution. Its advantage is especially associated with retaining and refining temporarily inferior heuristics, although its convergence speed remains improvable.

  • 5. Discussion: The discussion evaluates MCTS-AHD across complex application scenarios, including BO cost-aware acquisition-function design, alongside ablations and population-based comparisons.Table 4 describes gaps to optimal using manually designed and LLM-designed CAFs, with repeated runs and trials.
  • 5.1. Ablation on Parameters and Components: MCTS-AHD ablations show clear performance degradation on at least one task when Progressive Widening, Thought-alignment, or Exploration-decay is removed.The variants design step-by-step heuristics for TSP and KP, with average optimality gaps reported over three runs.
  • 5.1. Ablation on Parameters and Components: Removing expansion actions s1, m1, or m2 produces worse heuristics in at least one task, highlighting the significance of these LLM-based actions.The importance of s1 also supports the contribution of MCTS-AHD’s organized tree structure.
  • 5.1. Ablation on Parameters and Components: The default exploration setting λ0 = 0.1 exhibits generally good quality despite TSP and KP having different parameter preferences.This sensitivity analysis indicates that the default setting performs reasonably across the evaluated tasks.
  • 5.2. MCTS versus Population-based EC: MCTS-AHD can refine inferior but potentially valuable heuristics, enabling more comprehensive exploration of heuristic space and avoiding local optima.Population-based baselines show early performance convergence, whereas MCTS-AHD reaches significantly better performance through quick and continuous updates.
  • 5.2. MCTS versus Population-based EC: MCTS-AHD is claimed to have greater advantages when heuristic spaces are more complex or application scenarios contain more descriptive knowledge.The paper analyzes these advantage scopes in Appendix F.8.

6. Conclusion

The paper positions MCTS-AHD as an MCTS-based alternative to population-based evolutionary procedures for automatic heuristic design. It concludes that comprehensive heuristic-space exploration supports higher-quality heuristics for complex NP-hard tasks, while acknowledging that convergence speed remains a limitation.

  • 6. Conclusion: The paper concludes that MCTS-AHD comprehensively explores heuristic space and designs higher-quality heuristics for NP-hard complex tasks.It presents MCTS as a promising evolution method compared with population-based EC for LLM-based AHD.
  • 6. Conclusion: MCTS-AHD is introduced as the first application of MCTS to LLM-based automatic heuristic design.The method organizes LLM-generated heuristics within an MCTS-based evolution procedure.
  • Related Work: Automatic Heuristic Design, also called Hyper-Heuristics, seeks the best-performing heuristic among an extensive set of valid heuristics.Evolutionary algorithms are described as a general search strategy for updating heuristic algorithms automatically.
  • A.2. Neural Combinatorial Optimization (NCO): Neural Combinatorial Optimization trains neural networks for decision-making and can be viewed as a special kind of Hyper-Heuristic with a parameterized heuristic space.Its solving process supplies the general framework while training searches for parameter settings.
  • Related Work: Compared with NCO, LLM-based AHD is described as more efficient, applicable, and easier to implement for NP-hard combinatorial optimization problems.The passage contrasts days or weeks of GPU-based NCO training with generating a high-quality heuristic in a few hours without GPU requirements.
  • Related Work: Population-based LLM-AHD methods initialize heuristics, select operators and parents, and prompt LLMs to generate new heuristic functions iteratively.These procedures use mutation or crossover-style prompts within predefined general frameworks.

B. Definition of Tasks

The paper evaluates MCTS-AHD across NP-hard combinatorial optimization tasks and uses it to design key heuristic functions within predefined solving frameworks.

  • Problem Settings: The experiments cover TSP, CVRP, KP, MKP, ASP, and both online and offline BPP settings.These are six representative NP-hard combinatorial optimization problems, with online and offline variants for BPP.
  • Problem Settings: TSP seeks a shortest tour visiting each city once and returning to the start.Feasible tours satisfy degree-two constraints and exclude subtours shorter than the full tour.
  • Problem Settings: CVRP plans capacity-constrained vehicle routes from and back to a depot while serving customers and minimizing travel distance.Each route begins and ends at the depot, and customer demands must respect vehicle capacity.
  • Problem Settings: KP maximizes the value of items loaded into a capacity-limited knapsack, with each item selectable at most once.The instances sample item values and weights uniformly and use specified capacities for different item counts.
  • Frameworks: MCTS-AHD designs key functions inside general frameworks such as step-by-step construction, GLS, ACO, and BO-based CAF design.The step-by-step framework repeatedly assigns candidate priorities while constructing feasible solutions.
  • Frameworks: In the step-by-step framework, task-specific functions select TSP nodes, KP items, ASP vectors, or bins for online BPP.Each function uses the task’s available state information, such as distances, item values and weights, or remaining capacities.

D. Details of Evaluations & Experiments

The evaluation compares MCTS-AHD with LLM-based baselines under controlled budgets and describes the prompting actions used to generate and evolve heuristic functions.

  • Evaluation Setup: Evaluation budgets are set to T = 2,000 for online BPP and T = 1,000 for other tasks.These settings are designed to provide a similar maximum number of evaluations to the referenced baseline procedures.
  • Evaluation Setup: For online BPP, the evaluation dataset uses varying scales because a fixed 5,000-item, W=100 setting can fail at other scales.The varying-scale setup addresses this evaluation-scope issue without claiming broader generalization beyond the described datasets.
  • Evaluation Setup: MCTS-AHD uses fixed LLM temperature and shared tree parameters, including NI = 4, H = 10, k = 2, λ0 = 0.1, and α = 0.5.The listed parameters are applied across the involved tasks.
  • MCTS Actions: MCTS-AHD uses initialization, crossover, mutation, and tree-path reasoning actions to generate heuristics from scratch or existing heuristic contexts.Tree-path reasoning supplies diverse heuristics along a leaf-to-root path, while crossover actions combine or contrast heuristics from selected subtrees or elite sets.

E.3. Examples of LLM Outputs

The examples illustrate how MCTS-AHD prompts LLMs to produce task-specific heuristic logic and how its tree-search procedure expands, evaluates, and updates candidate heuristics.

  • TSP Output: For TSP, an example heuristic combines immediate distance, connection strength, and projected remaining-route cost.The reported weights prioritize immediate distance at 1.2 and connection strength at 0.6.
  • CAF Output: For cost-aware BO, an example CAF combines improvement over the best observed value, uncertainty, evaluation cost, remaining budget, and historical variance.The output description says these factors are combined to favor high expected returns with low associated costs.
  • CAF Output: The CAF code applies risk adjustment, cost-effectiveness with exponential cost decay, budget scaling, and min-max normalization.These operations use predicted means and standard deviations, evaluation costs, remaining budget, and training-history variance.
  • MCTS Procedure: Algorithm 1 organizes MCTS-AHD around initialization followed by selection, expansion, simulation, and backpropagation over a heuristic tree.Progressive widening controls expansion, newly generated heuristics are evaluated on dataset D, and the method uses the action set {i1, e1, e2, m1, m2, s1}.
  • Additional Applications: The method is also applied to ASP, GLS-based TSP penalty heuristics, and other framework-task combinations.The ASP experiment designs a priority function, while the GLS experiment evaluates generated penalty heuristics on TSP200 instances.
  • Significance Analysis: Across four application scenarios, MCTS-AHD has at least 96% confidence of leading EoH in the reported significance analysis.The paper uses p-values because heuristic-design performance follows an implicit distribution and three runs alone do not establish significant differences.

F.5. Results on TSPLib: Compare to GP-based AHD Methods

On TSPLib instances with fewer than 500 nodes, MCTS-AHD is compared with manually designed, GP-based, and LLM-based heuristic methods using average optimality gap.

  • TSPLib Comparison: The reported comparison includes Christofides, Greedy, Nearest insertion, Nearest-greedy, GHPP, EoH, and ReEvo.The manually designed methods’ results are drawn from the cited prior article, while MCTS-AHD, EoH, and ReEvo are evaluated as described.
  • TSPLib Comparison: MCTS-AHD surpasses manually designed baselines, the GP-based AHD method GHPP, and LLM-based baselines in average optimality gap.The comparison uses TSPLib instances with fewer than 500 nodes and averages three runs with different starting nodes for the LLM-based methods.

F.6. Compare to LLM-as-Optimizer Methods

LLM-as-optimizer methods can perform well on very-small TSP instances, but their solution optimization fails to converge as scale increases. MCTS-AHD is compared against these methods on TSP20 and TSP50.

  • LEMA and OPRO provide better solutions than MCTS-AHD on very-small-scale TSP20 instances.
  • At TSP50 scale, LEMA and OPRO fail to achieve convergence in LLM-based solution optimization.
  • Table 12 compares optimality gaps for MCTS-AHD, LEMA, and OPRO on 1,000-instance TSP20 and TSP50 test sets using GPT-3.5-turbo.

F.7. Discussion: Ablation of Other Parameters

The discussion examines parameter settings, heuristic-space complexity, and application scope. MCTS-AHD’s advantage is stronger for complex heuristic spaces but weaker in black-box settings.

  • Parameter ablations: Ablations assess λ −0 = 0.1, Progressive Widening, Thought Alignment, Exploration decay, and MCTS-AHD’s expansion actions.
  • Parameter ablations: NI = 10 has no significant effect compared with NI = 4, indicating that four initial heuristic samples are sufficient.
  • Parameter ablations: Progressive widening limits root level-1 nodes to at most ⌊T α⌋ under T total evaluations.
  • Heuristic-space complexity: MCTS-AHD’s lead over EoH tends to increase as estimated heuristic-space size n grows.
  • Application scope: In black-box settings, MCTS-AHD’s effectiveness decreases and it leads only on the TSP task, suggesting stronger performance with richer descriptions.
  • Application scope: The authors attribute black-box weakness partly to reliance on LLM generation quality when only limited MCTS expansions are available.

G. Examples of Evolution

The examples illustrate MCTS-AHD exploring heuristic-evolution trees beyond the currently best-performing heuristics. In a step-by-step TSP construction example, expansion from a non-top-10 node ultimately reaches the best heuristic.

  • TSP example: MCTS-AHD expands potential child nodes from heuristics outside the top 10 and ultimately reaches the best heuristic.
  • Comparison: Population-based methods focus on top-performance heuristics and can become trapped when those heuristics no longer produce improvements in one LLM operation.
  • TSP example: The TSP example uses a step-by-step construction framework and displays MCTS links, evolution steps, and the performance range of the top 10 heuristics.
  • Expansion traces: The examples include expansions at t = 502, 528, 611, 810, 985, 996 and actions e2, m2, m2, m2, s1, s1, respectively.
  • Workflow: Figure 6 shows two heuristic-evolution examples with node performance values g(·) and one of six expansion actions recorded at each node.

H. Baselines & Licenses

The experiments compare MCTS-AHD with manually designed, neural combinatorial-optimization, AHD, and LLM-based AHD baselines. Baseline settings, seed functions, implementations, and licenses are documented.

  • Experimental baselines: Optimal values use LKH3 for TSP with RUNS = 10 and MAX TRAILS = 1,0000, and Google OR-Tools for KP.
  • Experimental baselines: Manual baselines include Greedy Construct, ACO, KGLS, EI, EIpu, and EI-cools across the evaluated design tasks.
  • Experimental baselines: NCO baselines include POMO, DeepACO, VRP-DACT, and NeuOpt, with specified operation and augmentation settings for fair comparison.
  • Experimental baselines: LLM-based AHD baselines are Funsearch, EoH, ReEvo, and HSEvo, using their reported evolution settings such as population sizes M = 20 or M = 10.
  • Comparison settings: MCTS-AHD uses the same seed functions for several baselines and shows broader applicability and superior performance in most application scenarios without requiring seed-function design.
  • Licenses: Baseline licenses and URLs are listed in Table 15, whose caption identifies it as a summary of licenses.
Loading 2501.08603v3…