用蒙特卡洛树搜索提升大模型自动生成启发式算法的探索能力
Monte Carlo Tree Search for Comprehensive Exploration in LLM-Based Automatic Heuristic Design
- 将大模型生成的启发式算法组织成树结构，动态评估与演化
- 在多个复杂任务上生成的启发式质量显著优于传统方法
- 适合需要高质量启发式算法的优化问题研究者
为解决复杂优化任务（如路径规划和任务分配）中手工设计启发式规则耗时且依赖领域知识的问题，近年来基于大语言模型（LLM）的自动启发式设计（AHD）方法展现出潜力，可在无需人工干预的情况下生成高质量启发式。现有基于LLM的AHD方法通常采用种群机制维护一组表现最优的启发式，并引入进化计算（EC）进行迭代优化。然而，这类种群方法难以充分挖掘每个启发式的潜力，易陷入局部最优。本文提出使用蒙特卡洛树搜索（MCTS）实现更全面的启发式空间探索。所提MCTS-AHD方法将所有LLM生成的启发式组织成树形结构，能更好激发暂时表现不佳但具潜力的启发式。实验表明，MCTS-AHD在多种复杂任务上均生成了显著更优的启发式。代码已公开。
原文摘要 · Abstract (English)
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.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。