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

Population-based LLM heuristic design can struggle to explore complex heuristic spaces, while handcrafted heuristics require task-specific expertise. The paper introduces MCTS-AHD, which organizes generated heuristics in a tree, and reports higher-quality heuristics across complex optimization tasks.

  • Problem

    Population-based LLM-AHD methods may fail to explore complex heuristic spaces, while handcrafted heuristics require labor-intensive, task-specific expertise.

    Source: §1 · pp. 1–2

  • Method

    MCTS-AHD organizes generated heuristics in a tree and uses Monte Carlo Tree Search with progressive widening to guide further heuristic evolution.

    Source: §1 · p. 2

  • Results

    Across four NP-hard CO problems, MCTS-AHD led LLM-based baselines on in-domain and out-of-domain sets, beat handcrafted ACO heuristics on all eight test sets, and surpassed DeepACO on TSP and MKP.

    Source: §1 · p. 2, §4.1 · p. 7

  • Takeaways & Limitations

    For NP-hard complex tasks, the findings support MCTS as a promising evolution method for LLM-based AHD compared with population-based evolutionary computation.

    Source: §6 · p. 8

    MCTS-AHD’s convergence speed can still be improved.

    Source: §6 · p. 8

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

MCTS-AHD uses a tree search to evolve LLM-generated heuristics, retaining opportunities to refine temporarily underperforming functions while focusing on stronger ones. The paper reports higher-quality heuristics than handcrafted and existing LLM-based AHD methods across complex optimization tasks.

Introduction

  • Manually crafted heuristics can be labor-intensive and depend on task-specific expertise, while GP-based AHD also depends on human-defined permissible operators.AHD seeks the best-performing heuristic among valid options; LLM-based AHD designs key functions within predefined general frameworks rather than building heuristics from scratch.Source: §1 · pp. 1–2
  • Population-based AHD methods discard inferior heuristics, even though LLM refinement may improve them, which can leave the search stuck in suboptimal local optima.Multiple populations and diversity metrics can reduce premature convergence but still fail to explore the complex heuristic space fully.Source: Figure 1 · p. 1, §1 · p. 2
  • MCTS-AHD is presented as the first tree-search method for LLM-based AHD, organizing generated heuristics in a tree and using progressive widening to guide further evolution.It allows temporarily underperforming heuristics to be refined while keeping focus on better-performing ones, supporting more comprehensive exploration of the heuristic space.Source: §1 · p. 2
  • MCTS-AHD adds a tree-special prompt strategy, exploration decay that linearly reduces branching over time, and a thought-alignment procedure for precise linguistic descriptions of functions..Source: §1 · p. 2
  • MCTS-AHD achieves significantly higher-quality heuristics than handcrafted heuristics and existing LLM-based AHD methods on NP-hard combinatorial optimization problems and a Bayesian Optimization-related task.The experiments implement MCTS-AHD with several general frameworks.Source: §1 · p. 2

2. Preliminary

AHD evaluates heuristics within a task-specific search space, while population-based LLM methods can reject temporarily weak candidates; MCTS provides a tree-search alternative, with progressive widening for large or changing action spaces.

2.1. Definition: AHD & LLM-based AHD

  • AHD seeks the best-performing heuristic h* in task-specific space H, estimating performance by evaluating its solutions over dataset D.Methods typically fix a general framework and design only a key heuristic function with specified inputs and outputs.Source: §2.1 · p. 2
  • Population-based LLM-AHD retains a heuristic only if it outperforms the current population’s worst, making worse-before-better search for h* difficult (Liu et al., 2024b; Ye et al., 2024a).These methods maintain a population of M heuristics and use evolutionary-computation updates.Source: §2.1 · pp. 2–3
  • MCTS-AHD’s LLM actions initialize, mutate, or cross over heuristics, and use tree-path reasoning over samples from root to leaf.The figure lists two mutation actions and two crossover actions, alongside initialization and tree-path reasoning.Source: §2.1 · p. 2, Figure 2 · p. 3

2.2. Monte Carlo Tree Search

  • MCTS selects child nodes by UCT using node quality Q and visit count N, then expands, simulates, and backpropagates results; iterations can yield high-quality states.Backpropagation updates Q and N along the path from the expanded node to the root.Source: §2.2 · p. 3
  • Progressive widening addresses MCTS’s limitations with extensive action options or changing environments by adding children as a node’s visit count increases.A new child is added when a condition based on the node’s child count is satisfied.Source: §2.2 · p. 3

3. MCTS-AHD

MCTS-AHD organizes generated heuristics in a tree to support more comprehensive exploration, using progressive widening and an exploration factor that decays over time. Its LLM actions evolve heuristics through initialization, mutation, crossover, and tree-path reasoning.

3. MCTS-AHD

  • MCTS-AHD stores generated heuristics as executable implementations and descriptions in an MCTS tree, using progressive widening to evolve them.The root is virtual; other nodes represent heuristics. The search uses selection, expansion, simulation, and backpropagation, and terminates after T performance evaluations.Source: §3 · p. 4, Figure 3 · p. 4

3.1. LLM-based actions in MCTS-AHD

  • LLM actions initialize heuristics, mutate mechanisms or parameters, and cross over designs, with e2 adapting a parent using a top-10 elite reference.Action e1 creates a new workflow from multiple existing heuristics; action e2 identifies beneficial traits in its reference heuristic.Source: §3.1 · p. 4
  • Tree-path action s1 analyzes unique heuristics along a leaf-to-root path for advantageous designs, while thought alignment generates descriptions after code to reduce code-description mismatch.Each action uses two LLM calls: the first generates Python code and the second produces a linguistic description of up to three sentences.Source: §3.1 · pp. 4–5

3.2. MCTS settings

  • MCTS-AHD repeats selection, expansion, simulation, and backpropagation until heuristic evaluations approach limit T; expanding a selected leaf creates 2k + 2 children, whose heuristics are evaluated and initialized with performance quality and visit count 1.With α = 0.5, progressive widening triggers e1 at qualifying root nodes and e2 at other qualifying nodes; e1 inputs are uniformly selected from 2 to 5 different MCTS subtrees.Source: §3.2 · p. 5

3.3. Exploration-Decay

  • The exploration-decay technique linearly reduces UCT’s exploration factor λ to encourage broad early exploration and convergence later, using λ0 = 0.1 across tasks.A larger λ favors exploration of temporarily inferior nodes, while a smaller λ favors nodes with higher quality values.Source: §3.3 · p. 5

4. Experiments

The experiments evaluate MCTS-AHD across NP-hard combinatorial optimization and Bayesian optimization tasks, using several general heuristic-design frameworks. Results show advantages over existing methods across multiple tasks and settings.

4. Experiments

  • The experiments cover NP-hard CO problems using step-by-step construction, ACO, and GLS, as well as cost-aware acquisition-function design for BO.CO tasks include TSP, KP, CVRP, MKP, online and offline BPP, and ASP; GLS and ASP results are in the appendices.Source: §4 · p. 5, §4.1 · p. 6, §4.2 · p. 7

4.1. MCTS-AHD for NP-hard CO Problems

  • For step-by-step construction, MCTS-AHD has significant advantages on almost all TSP and KP test sets and beats POMO on 200-node TSP and KP tests.The comparisons include manually designed heuristics, EoH, and FunSearch; POMO requires task-specific training.Source: Table 1 · p. 6, §4.1 · pp. 6–7
  • MCTS-AHD leads EoH and ReEvo on all in-domain ACO test sets across four CO problems, beats manual ACO heuristics on all eight test sets, and surpasses DeepACO on TSP and MKP.The four problems are TSP, CVRP, MKP, and offline BPP.Source: Table 2 · p. 7, §4.1 · p. 7
  • MCTS-AHD-designed online BPP heuristics show superior average performance across six test sets.The evaluation dataset contains four Weibull instance scales; the test-set table reports performance gaps to the lower bound.Source: Table 3 · p. 7, §4.1 · p. 7

4.2. MCTS-AHD for Other Complex Tasks

  • MCTS-AHD-designed cost-aware acquisition functions outperform handcrafted heuristics and EoH on six of twelve synthetic BO instances.The evaluation used two synthetic instances for heuristic evolution and ten additional instances for testing, with sampling budget 12 and five independent trials.Source: §4.2 · p. 7

5. Discussion

The discussion evaluates MCTS-AHD’s components and contrasts its exploration and convergence with population-based methods, while identifying settings in which its advantages are expected to be greater.

5.1. Ablation on Parameters and Components

  • Removing Progressive Widening, Thought-alignment, or Exploration-decay degrades performance on at least one of TSP or KP compared with MCTS-AHD.The ablation variants were evaluated on step-by-step heuristics; Table 5 reports average optimality gaps over three runs in the cited comparison.Source: §5.1 · p. 8, Table 5 · p. 8
  • Variants without LLM-based actions s1, m1, or m2 produce worse heuristics on at least one task, underscoring the actions’ importance and the benefit of the organized tree structure.Actions e1 and e2, associated with Progressive Widening, cannot be ablated individually.Source: §5.1 · p. 8, Table 5 · p. 8
  • Although TSP and KP may prefer different λ0 settings, the default λ0 = 0.1 generally produces good-quality heuristics.The parameter sensitivity results are reported in the last two lines of Table 5.Source: §5.1 · p. 8, Table 5 · p. 8

5.2. MCTS versus Population-based EC

  • Population-based baselines converge early, while MCTS-AHD reaches significantly better performance through quick, continuous updates when designing TSP step-by-step heuristics and BO CAFs.The authors attribute this to MCTS-AHD’s ability to manage inferior but potentially useful heuristics and explore the heuristic space more comprehensively.Source: §5.2 · p. 8, Figure 4 · p. 8
  • MCTS-AHD is claimed to have greater advantages over population-based baselines in scenarios with more complex heuristic spaces or more descriptive knowledge.The paper analyzes these claims with experiments in Appendix F.8.Source: §5.2 · p. 8

6. Conclusion … A.7. LLM for Code Generation

The conclusion presents MCTS-AHD as an MCTS-based approach to comprehensive heuristic-space exploration; the related-work appendix reviews AHD, NCO, LLM-based evolution and CO methods, MCTS inference, and code generation.

6. Conclusion

  • MCTS-AHD applies MCTS to LLM-based AHD, explores the heuristic space comprehensively, and designs higher-quality heuristics for complex NP-hard tasks than population-based EC.The authors identify convergence speed as a limitation and propose future MCTS-population hybrids to improve evolution efficiency.Source: §6 · p. 8

A.1. AHD

  • AHD searches a heuristic space for strong heuristics; GP is effective but requires handcrafted mutation and crossover operators (Mei et al., 2022; Duflo et al., 2019; Sánchez-Díaz et al., 2021).AHD commonly uses evolutionary algorithms to update heuristics (Stützle & López-Ibáñez, 2019).Source: §A.1 · p. 14

A.2. Neural Combinatorial Optimization (NCO)

  • MCTS-AHD heuristics outperform advanced NCO methods POMO and DeepACO on 10 out of 16 test sets, while LLM-based AHD needs only linguistic task descriptions.The passage contrasts this with NCO’s task-specific framework and network designs and potentially days or weeks of GPU training.Source: §A.2 · p. 14

A.3. LLM for EC

A.4. LLM for AHD

  • Population-based LLM-AHD initializes heuristics, selects operators and parents, generates code with an LLM, then evaluates and updates the population until its budget is reached.Invalid heuristics are discarded, and population updates depend on heuristic performance.Source: §A.4 · pp. 14–15

A.5. LLM for CO

  • LLM-as-optimizer methods iteratively improve solutions, while LLM-as-solver methods fine-tune LLMs for CO instances; both have limitations on complex problems.The passage describes high reasoning demands and limited results on large instances for optimizer methods, and training-environment and coordinate-tokenization challenges for solver methods.Source: §A.5 · p. 15

A.6. LLM Inference with MCTS

  • MCTS-AHD represents each tree node as a complete executable function and description, and uses measured task performance rather than self-evaluation or rollout for simulation.Other LLM MCTS approaches may represent nodes as complete answers or as reasoning steps (Feng et al., 2023).Source: §A.6 · p. 15

A.7. LLM for Code Generation

  • Unlike code-generation tasks judged by algorithm tests, LLM-based AHD must explore the heuristic space and optimize code through parameter settings and detailed designs.Brandfonbrener et al. (2024) also uses MCTS with progressive widening for code generation, but its procedure differs from MCTS-AHD.Source: §A.7 · p. 15

B. Definition of Tasks … C.4. Bayesian Optimization

The paper defines six NP-hard combinatorial optimization tasks and evaluates heuristic design across step-by-step construction, ACO, GLS, and cost-aware Bayesian optimization (BO).

B.1. NP-hard CO Problems

  • Experiments cover TSP, CVRP, KP, MKP, ASP, and BPP, with BPP evaluated in both online and offline settings.The tasks span routing, knapsack, admissible-set, and bin-packing problems.Source: §B.1 · pp. 16–17

B.2. Cost-Aware Acquisition Function Design in Bayesian Optimization

  • The cost-aware acquisition-function design subsection directs readers to C.4 for its relevant introduction.Source: §B.2 · p. 17

C. Definition of General Frameworks

C.1. Step-by-Step Construction

  • In step-by-step construction, the shared heuristic function repeatedly prioritizes candidates during solution extension, covering TSP, KP, ASP, and online BPP.The function selects a node or item, scores a vector for inclusion in the admissible set, or scores bins for an arriving item.Source: §C.1 · p. 18

C.2. Ant Colony Optimization

  • ACO combines pheromone trails updated from solution quality with a problem-specific heuristic matrix; MCTS-AHD designs that matrix for TSP, CVRP, MKP, and offline BPP.Ants construct solutions probabilistically from pheromone and heuristic information, followed by pheromone updates.Source: §C.2 · p. 18

C.3. Guided Local Search

  • GLS uses local search and penalties to escape local optima; its KGLS implementation perturbs TSP solutions using a knowledge matrix before 2-opt and relocate searches.The paper runs 1,200 iterations per instance and sets the number of perturbations per solution to 30.Source: §C.3 · p. 19

C.4. Bayesian Optimization

  • Cost-aware BO uses a cost-aware acquisition function (CAF) to balance objective optimization with evaluation cost, with evolution capped at 12 samples and testing budgeted at 30.MCTS-AHD and EoH each run five independent evolution trials; reported testing results average 10 trials.Source: §C.4 · pp. 19–20

D. Details of Evaluations & Experiments … E.2. The Prompt of the Thought-Alignment Process

The evaluation setup specifies task-dependent budgets and datasets, while the MCTS action prompts define how heuristics are generated and refined. A second LLM call aligns each heuristic’s description with its implementation.

D. Details of Evaluations & Experiments

  • MCTS-AHD uses a maximum of T = 2,000 evaluations for online BPP and T = 1,000 for other tasks.The budgets were chosen to be similar to baseline evaluation counts.Source: D. Details of Evaluations & Experiments · p. 20
  • For online BPP, the evaluation dataset varies instance characteristics and scales to avoid heuristics that fail beyond the baseline’s 5,000-item, W=100 setting.For most other tasks, MCTS-AHD adopts the evaluation-dataset settings of LLM-based baselines; Table 6 presents dataset compositions.Source: D. Details of Evaluations & Experiments · p. 20, Table 6 · p. 20
  • Across tasks, MCTS-AHD fixes temperature at 1.0, NI = 4, H = 10, k = 2, λ0 = 0.1, and α = 0.5; the evaluation uses several specified pretrained LLMs.The listed models include GPT-4o-mini, GPT-3.5-turbo, Claude-3.5-sonnet, DeepSeek-v3, and Qwen2.5-Coder-32b-Instruct.Source: D. Details of Evaluations & Experiments · p. 20

E.1. Prompts of MCTS Actions

  • The initial action i1 asks the LLM to design a heuristic from scratch, while crossover e1 requests a distinct heuristic informed by 2 to 5 root-subtree heuristics.The prompt includes the existing heuristics’ code, descriptions, and performance.Source: §E.1 · p. 21
  • Crossover e2 combines a parent heuristic with a reference sampled from the 10-member elite set, asking for a new design based on the parent and the reference’s advantages.The reference is sampled with priority based on its rank.Source: §E.1 · p. 22
  • Mutation m1 introduces mechanisms or code segments into an input heuristic, whereas m2 seeks different parameter settings for that heuristic.Both actions receive an existing heuristic’s description and implementation.Source: §E.1 · pp. 22–23
  • Tree-path action s1 uses diverse heuristics on a leaf-to-root path as context for a better heuristic, and is skipped when the path contains only one unique heuristic.Source: §E.1 · p. 23

E.2. The Prompt of the Thought-Alignment Process

  • After an action produces a design idea and implementation, a second LLM call uses a thought-alignment prompt to create a more detailed description grounded in the code’s critical design choices.The prompt asks for fewer than three sentences and calls attention to variable priorities, parameters, and code structure.Source: §E.2 · p. 24

E.3. Examples of LLM Outputs … F.4. MCTS-AHD with Other LLMs

MCTS-AHD organizes generated heuristics in a tree, with LLM-driven expansion and evaluation, and is tested across optimization tasks, search frameworks, and language models. The reported results include strong comparisons with existing methods and evidence of an advantage over EoH.

E.3. Examples of LLM Outputs

  • Each heuristic generation uses two LLM calls: one to produce code and another to describe it, with examples covering TSP path selection and cost-aware Bayesian optimization.The TSP example weights immediate distance at 1.2 and connection strength at 0.6; the cost-aware example combines improvement, uncertainty, evaluation cost, and remaining budget.Source: §E.3 · pp. 25–26

E.4. Total Algorithm

  • MCTS-AHD initializes a heuristic tree, then uses progressive widening and four stages: selection, LLM-driven expansion, evaluation, and max-Q backpropagation.The algorithm sets maximal depth H=10, uses k=2 mutations per expansion, and updates an elite set when new top-ten heuristics emerge.Source: §E.4 · p. 27

F.1. Designing Heuristics with the Step-by-step Construction Framework for ASP

  • MCTS-AHD achieves the best results on most ASP test sets across four scales, using a priority function evaluated on an instance with n=15 and w=10.The admissible-set size has a theoretical upper bound, which the study uses as optimal.Source: §F.1 · p. 28

F.2. Guided Local Search Framework

  • MCTS-AHD refines KGLS on TSP200 and TSP500 and generally outperforms other LLM-based AHD methods using GPT-4o-mini.The evaluation uses ten TSP200 instances and 1,200 GLS local-search iterations for heuristic design and testing.Source: §F.2 · p. 28, Table 8 · p. 28

F.3. P-values for Significance

  • At least 96% confidence supports the hypothesis that MCTS-AHD leads EoH in each of four application scenarios.The comparison uses up to ten heuristics per method and single-tailed t-tests.Source: §F.3 · p. 29, Table 9 · p. 29

F.4. MCTS-AHD with Other LLMs

  • Claude-3.5-sonnet, DeepSeek-v3, and Qwen2.5-Coder-32b-Instruct beat handcrafted heuristics on TSP and KP, while GPT-4o-mini performs best on every test set.The non-GPT models also outperform POMO on KP; Table 10 averages each MCTS-AHD result over three runs.Source: §F.4 · p. 29, Table 10 · p. 29

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

On TSPLib instances with fewer than 500 nodes, MCTS-AHD’s heuristic surpasses manually designed heuristics, GHPP, and LLM-based AHD baselines in average optimality gap.

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

  • The comparison covers TSPLib instances with fewer than 500 nodes and uses GHPP results and manual-heuristic results reported by Duflo et al. (2019).Manual baselines include Christofides, Greedy, Nearest insertion, and nearest-greedy.Source: §F.5 · p. 30
  • On TSPLib, MCTS-AHD's heuristic surpasses manually designed baselines, GHPP, and LLM-based AHD baselines in average optimality gap; EoH, ReEvo, and MCTS-AHD were run three times per instance with different starting nodes.Table 11 reports each instance’s optimality gap and marks the overall best heuristic in bold.Source: §F.5 · p. 30, Table 11 · p. 30
  • EoH and MCTS-AHD use their best-performing step-by-step constructive heuristics across three GPT-4o-mini runs; ReEvo uses its reported best heuristic.EoH, ReEvo, and MCTS-AHD are each run three times per instance with different starting nodes, and average performance is reported.Source: §F.5 · p. 30, Table 11 · p. 30

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

LLM-as-optimizer methods LEMA and OPRO can provide better solutions than MCTS-AHD on very-small TSP20 instances, but fail to converge as the scale increases to TSP50.

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

  • LEMA and OPRO can provide better solutions than MCTS-AHD on very-small TSP20 instances, but fail to converge on TSP50 as scale increases.Table 12 compares optimality gaps on 1,000-instance TSP20 and TSP50 test sets; all methods use GPT-3.5-turbo.Source: Table 12 · p. 30, §F.6 · p. 30

F.7. Discussion: Ablation of Other Parameters · F.8. Discussion: The Advantage Scope of MCTS

MCTS-AHD’s advantage over EoH tends to grow in more complex heuristic spaces, while its effectiveness declines in black-box settings. Ablations indicate that several alternative parameter settings do not significantly degrade performance.

F.7. Discussion: Ablation of Other Parameters

  • The defaults use NI = 4 as sufficient initial sampling, α = 0.5 to balance tree depth and progressive widening, and k = 2 to exploit LLM randomness across search directions.The authors characterize MCTS-AHD as not sensitive to these parameter settings.Source: §F.7 · p. 31
  • Changing NI from 4 to 10, α from 0.5 to 0.6, or k from 2 to 1 does not significantly degrade performance.The reported MCTS-AHD variant performances are averaged over five runs.Source: §F.7 · p. 31, Table 13 · p. 31

F.8. Discussion: The Advantage Scope of MCTS

  • MCTS-AHD’s lead over EoH tends to grow as estimated heuristic-space size increases, suggesting it is better suited to more complex spaces.The analysis estimates space size from the number of linearly independent sub-functions in top heuristics; Figure 5 plots this estimate against the optimality-gap lead.Source: Figure 5 · p. 31, §F.8 · p. 32
  • In black-box settings, MCTS-AHD leads only on TSP, indicating weaker effectiveness when fewer task descriptions are available.The discussion contrasts these settings with white-box cases, which provide more descriptions.Source: §F.8 · p. 32, Table 14 · p. 32
  • The authors attribute MCTS-AHD’s complex-space advantage to broader exploration and its ability to escape local optima.This is offered as an explanation for its stronger performance in application scenarios with complex heuristic spaces.Source: §F.8 · p. 32
  • Black-box tasks challenge MCTS-AHD because limited expansions make success more dependent on LLM generation quality, which those settings may not ensure.Population-based methods use more rounds of LLM operations on heuristics, whereas MCTS performs limited expansion on each heuristic.Source: §F.8 · p. 32

G. Examples of Evolution

The examples show MCTS-AHD exploring heuristic trees beyond top-performing candidates, including expanding a lower-ranked TSP node to reach the best heuristic, while population-based methods risk local optima by focusing on top performers.

G. Examples of Evolution

  • MCTS-AHD’s two evolution examples illustrate comprehensive exploration across two tasks (Figure 6).The figure shows heuristic performance values and the expansion action at each tree node.Source: G. Examples of Evolution · p. 32, Figure 6 · p. 33
  • For TSP, MCTS-AHD expands a node outside the top 10 heuristics and ultimately reaches the best heuristic.The example uses a step-by-step construction framework; the top 10 performance range is shaded yellow.Source: G. Examples of Evolution · p. 32, Figure 6 · p. 33
  • Population-based methods such as EoH, ReEvo, and HSEvo focus on top performers and can become trapped when one operation yields no better top-10 heuristic.The paper contrasts this with MCTS-AHD’s ability to develop worse-performing but potentially useful heuristics.Source: G. Examples of Evolution · p. 32

H. Baselines & Licenses · H.1. License

The section documents the comparison baselines and their implementation settings, including seed-function choices and cases where baselines are unavailable. It also points to a table summarizing baseline licenses.

H. Baselines & Licenses

  • LKH3 uses RUNS = 10 and MAX TRAILS = 1,0000 for TSP optimal values, while Google OR-Tools supplies KP optimal values.These optimal values are reported for Tables 1 and 8.Source: H. Baselines & Licenses · p. 34
  • Manual baselines include Greedy Construct, ACO, KGLS (Arnold & S¨orensen, 2019), and EI, EIpu, and EI-cools for CAF design in BO.KGSL uses the distance matrix as its heuristic matrix; ACO uses DeepACO, while EI results follow Yao et al. (2024c).Source: H. Baselines & Licenses · p. 34
  • NCO baselines are POMO (Kwon et al., 2020), DeepACO (Ye et al., 2024b), VRP-DACT (Ma et al., 2021), and NeuOpt.For Table 1, POMO uses a single start without augmentations; VRP-DACT and NeuOpt use maximum operation T = 1200.Source: H. Baselines & Licenses · p. 34
  • The TSPLib AHD comparison uses GHPP results reported by Duflo et al. (2019).Source: H. Baselines & Licenses · p. 34
  • LLM-based AHD baselines are Funsearch, EoH (Liu et al., 2024b), ReEvo (Ye et al., 2024a), and HSEvo (Dat et al., 2024).The paper follows their evolutionary parameter settings, including population size M = 20 for online BPP and M = 10 for other tasks; Funsearch needs 10 relatively independent populations, and ReEvo can become unavailable when elite individuals share an objective value.Source: H. Baselines & Licenses · p. 34
  • MCTS-AHD shows better applicability and superior performance in most scenarios without requiring seed-function design; ReEvo and HSEvo are unavailable in some settings, including KP and ACO.The paper does not report ReEvo or HSEvo effects in those settings.Source: H. Baselines & Licenses · p. 34
  • Baselines Funsearch, ReEvo, and HSEvo use the same seed functions: framework-specific seeds, random selection for step-by-step TSP and ASP, and Romera-Paredes et al. (2024)'s best-known function for online BPP.ReEvo and HSEvo can be difficult to use for KP when a suitable seed is hard to find without adding substantial expert knowledge.Source: H. Baselines & Licenses · p. 34

H.1. License

  • Table 15 summarizes the licenses of the baselines.The section states that baseline licenses and URLs are listed there.Source: §H.1 · p. 34, Table 15 · p. 34

Related papers

Loading 2501.08603v3…