Algorithmic Prompt-Augmentation for Efficient LLM-Based Heuristic Design for A* Search

📄 arXiv: 2601.19622v1 📥 PDF

作者: Thomas Bömer, Nico Koltermann, Max Disselnmeyer, Bastian Amberg, Anne Meyer

分类: cs.AI, math.OC

发布日期: 2026-01-27

备注: accepted at EvoStar conference; Code: https://github.com/tb-git-tud/a-ceoh-evolution-of-heuristics?tab=readme-ov-file

💡 一句话要点

提出算法提示增强的A-CEoH框架，高效利用LLM为A*搜索设计启发式函数。

🎯 匹配领域: 支柱九：具身大模型 (Embodied Foundation Models)

关键词: A*搜索 启发式函数 大型语言模型 提示工程 进化算法 自动化设计 上下文学习

📋 核心要点

  1. 手工设计启发式函数需要大量领域知识，且难以适应不同问题，限制了A*搜索等算法的效率。
  2. 提出A-CEoH框架，通过算法提示增强，将A*代码融入LLM提示中，利用上下文学习自动生成启发式函数。
  3. 实验表明，A-CEoH在单元负载预编组问题和滑动拼图问题上，显著提升了启发式函数的质量，甚至超越专家设计。

📝 摘要（中文）

启发式函数对于A等树搜索算法的性能至关重要，其准确性和效率直接影响搜索结果。传统上，这些启发式函数是手工设计的，需要大量的专业知识。大型语言模型（LLM）和进化框架的最新进展为自动化启发式设计打开了大门。本文扩展了启发式进化（EoH）框架，以研究A搜索的引导启发式的自动生成。我们引入了一种新颖的领域无关的提示增强策略，该策略将A*代码包含到提示中以利用上下文学习，命名为算法-上下文EoH（A-CEoH）。为了评估A-CeoH的有效性，我们研究了两个问题领域：单元负载预编组问题（UPMP），这是一个来自仓库物流的利基问题，以及经典的滑动拼图问题（SPP）。我们的计算实验表明，A-CEoH可以显著提高生成的启发式的质量，甚至优于专家设计的启发式函数。

🔬 方法详解

问题定义：论文旨在解决A*搜索算法中启发式函数设计高度依赖专家知识的问题。现有手工设计的启发式函数泛化能力弱，难以适应新的问题领域，且设计过程耗时耗力。利用LLM自动生成启发式函数是一个有潜力的方向，但如何有效地利用LLM的上下文学习能力是一个挑战。

核心思路：论文的核心思路是通过算法提示增强，将A*搜索算法的代码片段融入到LLM的提示中，使LLM能够更好地理解搜索过程和启发式函数的作用。这种方式利用了LLM的上下文学习能力，使其能够生成更有效的启发式函数。

技术框架：A-CEoH框架基于启发式进化（EoH）框架，并对其进行了扩展。整体流程包括：1) 初始化启发式函数种群；2) 使用A搜索算法评估每个启发式函数的性能；3) 使用进化算法（如遗传算法）选择和变异启发式函数；4) 使用算法提示增强策略，将A代码片段添加到LLM的提示中，生成新的启发式函数；5) 重复步骤2-4，直到满足停止条件。

关键创新：最重要的技术创新点是算法提示增强策略。与传统的EoH框架相比，A-CEoH通过将A*代码片段添加到LLM的提示中，使LLM能够更好地理解搜索过程和启发式函数的作用，从而生成更有效的启发式函数。这种方法是一种领域无关的提示增强策略，可以应用于不同的问题领域。

关键设计：关键设计包括：1) 如何选择合适的A*代码片段添加到提示中；2) 如何设计提示的格式，以便LLM能够有效地利用这些信息；3) 如何平衡LLM生成启发式函数的质量和效率；4) 使用遗传算法进行启发式函数的选择和变异，包括选择算子、交叉算子和变异算子的设计。

🖼️ 关键图片

fig_0
fig_1
fig_2

📊 实验亮点

实验结果表明，A-CEoH在单元负载预编组问题（UPMP）和滑动拼图问题（SPP）上均取得了显著的性能提升。在某些情况下，A-CEoH生成的启发式函数甚至优于专家设计的启发式函数，证明了该方法的有效性和优越性。

🎯 应用场景

该研究成果可广泛应用于路径规划、游戏AI、物流优化、机器人导航等领域，通过自动生成高质量的启发式函数，提高A*搜索等算法的效率，降低对人工设计的依赖，具有重要的实际应用价值和未来发展潜力。

📄 摘要（原文）

Heuristic functions are essential to the performance of tree search algorithms such as A, where their accuracy and efficiency directly impact search outcomes. Traditionally, such heuristics are handcrafted, requiring significant expertise. Recent advances in large language models (LLMs) and evolutionary frameworks have opened the door to automating heuristic design. In this paper, we extend the Evolution of Heuristics (EoH) framework to investigate the automated generation of guiding heuristics for A search. We introduce a novel domain-agnostic prompt augmentation strategy that includes the A* code into the prompt to leverage in-context learning, named Algorithmic - Contextual EoH (A-CEoH). To evaluate the effectiveness of A-CeoH, we study two problem domains: the Unit-Load Pre-Marshalling Problem (UPMP), a niche problem from warehouse logistics, and the classical sliding puzzle problem (SPP). Our computational experiments show that A-CEoH can significantly improve the quality of the generated heuristics and even outperform expert-designed heuristics.