💬 NLP

PathWise: Planning through World Model for Automated Heuristic Design via Self-Evolving LLMs

PathWise 是一种新颖的多智能体框架，通过将组合优化中的自动化启发式设计过程建模为 entailment 图上的状态感知序贯决策任务，从而以战略规划和自我演进的推理取代短视的试错，以实现更快的收敛和更好的泛化能力。

原作者： Oguzhan Gungordu, Siheng Xiong, Faramarz Fekri

发布于 2026-05-26

📖 1 分钟阅读☕ 轻松阅读

原作者： Oguzhan Gungordu, Siheng Xiong, Faramarz Fekri

原始论文采用 CC BY 4.0 许可（http://creativecommons.org/licenses/by/4.0/）。 ✨ 这是对下方论文的AI生成解释。它不是由作者撰写或认可的。如需技术准确性，请参阅原始论文。阅读完整免责声明

以下是关于PathWise论文的解读，已用通俗易懂的语言并辅以生动的类比进行翻译。

宏观图景：教导机器人发明更优规则

想象你面对一个巨大且凌乱的拼图（例如旅行商问题，即送货员需要找到访问 100 个城市的最佳最短路线）。为了解决这个问题，人类通常会编写“规则”（启发式算法）来指导计算机如何选择下一个城市。

长期以来，计算机尝试利用大语言模型（LLMs）（即那种能写文章或代码的同类人工智能）自动编写这些规则。然而，以往的方法有点像一位厨师试图通过随机向锅里扔食材、尝一口味道，然后寄希望于好运来发明新食谱。它们经常重复犯错，忘记过去的成功经验，或者陷入死循环，反复尝试同样的糟糕点子。

PathWise是一个新系统，它改变了这一过程。它不再进行随机猜测，而是像一个聪明且善于自我反思的建筑师，通过构建自身思维过程的地图，从而更快地设计出更优的规则。

核心问题：过往人工智能的“失忆症”

该论文指出，以往用于设计这些规则的人工智能方法存在两个主要缺陷：

它们遗忘了过去：它们将每一次新的尝试都视为第一次，忽略了从过往失败中吸取的教训。
它们缺乏洞察力：它们不理解规则为何有效或为何失败，仅仅关注最终得分。

这导致了“短视”的结果，人工智能浪费了时间，反复重新发现同样的糟糕点子。

解决方案：PathWise（“世界模型”方法）

PathWise 通过将设计过程视为一个带有存档功能的电子游戏来解决这一问题。它使用了一种称为**蕴含图（Entailment Graph）**的特殊结构。

将蕴含图想象成一张思想的族谱：

节点（人物）：每个节点代表人工智能创建的一个特定规则（启发式算法）。
边（关系）：连接它们的线条展示了规则是如何从一个衍生到另一个的。人工智能是组合了两个想法？还是微调了其中一个？
记忆：这张图记住了整个历史。它知道“规则 B"是对“规则 A"的轻微改进，而“规则 C"之所以失败，是因为它忽略了交通模式。

工作原理：三方代理团队

PathWise 不仅仅使用一个人工智能，而是使用一个由三个专业化代理组成的团队协同工作，这就像一支电影制作团队：

1. 导演（策略代理）

角色：该代理查看“族谱”（图），并决定下一步行动。
行动：它选择哪些过往规则作为“父母”，并撰写一份“剧本”（指令），告诉下一个代理如何混合它们。
类比：想象一位导演看着分镜脚本说：“让我们采用第 3 场的灯光和第 5 场的镜头角度，但让画面更暗一些。”

2. 演员（世界模型代理）

角色：该代理接收导演的剧本，并实际编写代码（新规则）。
行动：它根据指令生成实际的计算机程序。
类比：这就是阅读剧本并演绎场景的演员。它努力将导演的愿景变为现实。

3. 评论家（评论代理）

角色：这些代理观看表演并提供反馈。
行动：它们将新规则与旧规则进行比较。如果新规则更好，它们会告诉导演：“干得漂亮，继续保持！”如果更差，它们会说：“那个灯光太暗了；试试别的。”
类比：这些是影评人和导演的助理。它们不仅仅说“好”或“坏”；它们解释为什么，以便导演能改进下一份剧本。

秘密武器：“状态感知”规划

PathWise 的魔力在于，它不仅仅关注当前的得分，而是审视整个旅程。

旧方法：“我试了这个，失败了。让我们尝试一个完全不同的东西。”
PathWise 方法：“我试了这个，失败了，因为我忽略了到下一个城市的距离。我也试过那个，效果很好。让我们将第二次尝试中的距离逻辑与第一次尝试中的速度逻辑结合起来。”

通过保持这种“有状态的记忆”，PathWise 避免了重复犯错，并在成功的基础上进行构建，从而实现了更快的收敛（更快地找到最佳解决方案）。

结果：更快且更智能

该论文在多种复杂谜题（如卡车路线规划、装箱问题以及旅行商问题）上测试了 PathWise。

速度：与其他方法相比，PathWise 用更少的尝试次数找到了更好的解决方案。它更快地到达了“终点线”。
质量：它发明的规则优于人类或其他人工智能方法所制作的规则。
通用性：它能很好地与不同类型的人工智能模型（“骨干”）配合，并适用于不同规模的问题。

总结类比

想象你正在尝试发明完美的三明治。

旧人工智能：你做一个三明治，吃掉它，如果味道不好，你就把它扔掉，然后毫无记忆地随机制作一个全新的三明治，完全不记得你加了什么。
PathWise：你保留一本食谱日记。当你制作三明治时，你记录下你具体做了什么。如果味道不好，你阅读日记，意识到盐放多了，并记下这一点。下次，你请一位“评论家”审查你的日记，它会告诉你：“不要只是猜测；使用周二那个低盐的食谱，但加上周一的奶酪。”

PathWise 就是这套聪明的食谱日记系统，它允许人工智能从自身历史中学习，从而为复杂问题发明更好的解决方案。

技术摘要：PathWise

问题陈述

自动化启发式设计（AHD）旨在自动生成组合优化问题（COP）的启发式算法，从而减少对人工专家设计方案的依赖。虽然大型语言模型（LLM）近期通过集成到进化搜索过程中实现了 AHD，但现有框架存在显著局限。基于种群的方法通常依赖固定的进化规则和静态提示模板，导致启发式生成短视、评估冗余以及过早收敛。基于树的方法（如使用蒙特卡洛树搜索 MCTS 的方法）则强加由性能统计驱动而非由对搜索景观的语义理解驱动的分层结构。关键在于，当前方法缺乏对启发式如何推导、编辑如何在代际间传播、以及修改为何成功或失败的有状态语义表示。这导致 LLM 调用效率低下，且无法有效延续过去的决策。

方法论

作者提出了PathWise（通过世界模型规划以实现基于自进化 LLM 的自动化启发式设计），这是一种新颖的多智能体推理框架，将启发式生成构建为在蕴含图上的序列决策过程。该图充当搜索轨迹的紧凑、有状态记忆。

核心组件

蕴含图（ $G = (V, E)$ ）：
- 与标准的进化树或种群不同，蕴含图编码了推导历史。
- 节点（ $v$ ）： 表示包含启发式代码（ $h$ ）、自然语言推导理由（ $\kappa$ ）、算法描述（ $d$ ）、性能指标（ $P(h; D)$ ）以及父代元数据（$PM$）的元组。
- 边（ $E$ ）： 连接父代集合与子节点，编码了从父代推导子代所使用的具体理由。
- 这种结构允许系统基于推导历史来调节未来决策，而不是将步骤视为孤立的采样事件。
多智能体系统：
该框架通过跨越两个时间尺度（外层种群更新和内层蕴含步骤）的规划、执行和反思协调循环运行：
- 策略智能体（ $\pi_p$ ）： 充当高层规划器。它观察当前状态（蕴含图的前沿），并提出由选定的父节点集合（ $S$ ）和自然语言推导理由（ $\kappa$ ）定义的元组所构成的动作。这使得策略能够动态发明新的算子类型，而不是依赖固定模板。
- 世界模型智能体（ $\pi_{wm}$ ）： 充当低层执行器。它将策略的高层动作转化为可执行的启发式代码（ rollout），并以选定的父节点和指令为条件。
- 批判者智能体：
  - 策略批判者（ $\pi_{p\_critic}$ ）： 分析策略动作（父节点选择和指令）的结果，提供路由反思以指导未来的进化策略。
  - 世界模型批判者（ $\pi_{wm\_critic}$ ）： 比较表现最好和最差的启发式 rollout，提供关于代码合成质量的反馈，指导世界模型优化算法结构和效率。
搜索过程：
- 外层循环： 维护根节点种群。
- 内层循环： 在当前种群的基础上增量构建蕴含图。在每一步，系统采样多个动作和 rollout，选择最佳结果节点，并更新图。
- 多样性机制： 为防止低多样性输出，PathWise 采用提示级多样性（使用探索性短语扰动提示）和状态洗牌（随机化节点顺序以减轻位置偏差）。

主要贡献

混合图 - 种群公式： 作者提出了一种公式，其中蕴含图编码推导理由和性能历史，作为策略与世界模型交互的共享状态。
协调的多智能体框架： 一个系统，其中策略智能体控制进化策略，世界模型执行代码生成，批判者智能体提供路由反思，从而在不更新 LLM 参数的情况下实现自进化、状态感知的启发式生成。
提示级多样性： 确保父节点选择和启发式 rollout 多样性的机制，从而在蕴含图上实现更广泛的探索。
实证验证： 广泛的实验表明，PathWise 以 fewer 评估发现了更强的启发式，实现了更快的收敛，并在各种 COP 中有效地扩展到更大的问题规模。

实验结果

PathWise 在多个 NP-hard COP 上进行了评估，包括旅行商问题（TSP）、背包问题（KP）、带容量约束的车辆路径问题（CVRP）、多背包问题（MKP）、定向问题（OP）和装箱问题（BPP）。该框架在三种搜索范式下进行了测试：逐步构建、蚁群优化（ACO）和引导局部搜索（GLS）。

性能： PathWise 持续优于最先进的基于 LLM 的 AHD 基线（FunSearch、EoH、ReEvo、HSEvo、MCTS-AHD）以及人工设计的启发式算法。它在域内和域外测试集上均实现了更低的最优性差距。
效率： PathWise 更快地收敛到更优的启发式。在几项实验中，PathWise 仅用 500 次评估就取得了优于基线的性能，而基线被允许进行 1000 次评估。
可扩展性： 该方法表现出对更大问题规模（例如 $N=200$ 的 TSP， $N=500$ 的 KP）和不同 LLM 骨干网络（GPT-4o-mini、GPT-5-nano，具有不同的推理级别）的强泛化能力。
消融研究： 移除批判者智能体或多样性机制会显著降低性能，证实了状态感知反馈和探索的必要性。

意义与主张

该论文声称，PathWise 代表了从“试错进化”向“通过推理进行状态感知规划”的转变。通过将启发式发现视为蕴含图上的序列决策过程，该系统能够延续过去的决策，并在代际间重用或避免推导信息。

作者强调，PathWise 是免训练的，因为它不更新 LLM 参数；相反，它利用 LLM 的预训练知识，并通过自然语言反思加以强化。其意义在于能够通过提供搜索过程的结构化记忆来克服现有 AHD 方法的短视，从而减少冗余评估，并更有效地发现复杂组合问题的高质量启发式。这项工作表明，基于推导历史的结构化推理是扩展基于 LLM 的自动化算法设计的关键组成部分。