用分支级信念替代节点评估，提升大模型启发式设计的搜索效率
Beyond the Node: Clade-level Selection for Efficient MCTS in Automatic Heuristic Design
- 以分支为单位聚合评估结果，构建贝叶斯信念分布
- 在复杂组合优化问题上性能超越现有方法，计算成本降低显著
- 适合需要高效探索的自动化启发式设计场景
尽管蒙特卡洛树搜索（MCTS）在基于大语言模型（LLM）的自动启发式设计（AHD）中展现出潜力，但在受限计算预算下存在过度开发的问题。为此，我们提出Clade-AHD框架，将节点级点估计替换为分支级贝叶斯信念。通过将后代评估结果聚合为贝塔分布，并在此信念上执行汤普森采样，该方法显式建模不确定性，从而在稀疏且嘈杂的评估条件下引导更可靠的探索。在复杂组合优化问题上的大量实验表明，Clade-AHD持续优于当前最优方法，同时显著降低计算成本。代码已公开：https://github.com/Mriya0306/Clade-AHD。
原文摘要 · Abstract (English)
While Monte Carlo Tree Search (MCTS) shows promise in Large Language Model (LLM) based Automatic Heuristic Design (AHD), it suffers from a critical over-exploitation tendency under the limited computational budgets required for heuristic evaluation. To address this limitation, we propose Clade-AHD, an efficient framework that replaces node-level point estimates with clade-level Bayesian beliefs. By aggregating descendant evaluations into Beta distributions and performing Thompson Sampling over these beliefs, Clade-AHD explicitly models uncertainty to guide exploration, enabling more reliable decision-making under sparse and noisy evaluations. Extensive experiments on complex combinatorial optimization problems demonstrate that Clade-AHD consistently outperforms state-of-the-art methods while significantly reducing computational cost. The source code is publicly available at: https://github.com/Mriya0306/Clade-AHD.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。