通过代价划分学习可接受启发式

arXiv cs.AI 论文
admissible-heuristics cost-partitioning optimal-planning graph-neural-networks machine-learning heuristic-search lagrangian-duality

摘要

本文提出了一种框架，利用拉格朗日对偶等价性为规划启发式学习可接受的代价划分，采用具有轴向自注意力机制的深度架构，从构造上保证可接受性。该方法声称是首个经过证明可保证可接受性的机器学习启发式。

arXiv:2606.04597v1 公告类型：新论文 摘要：可接受启发式对于最优规划至关重要，但由于存在高估风险，学习此类启发式仍面临挑战。代价划分能够在保持可接受性的同时融合多种抽象启发式，但在线计算最优划分的代价较高。我们提出了一种框架，通过利用代价划分与乘子预测之间的拉格朗日对偶等价性，学习推断可接受的代价划分。规划状态和模式被编码为带标签的图，并采用以动作为中心的 Weisfeiler-Leman 算法变体提取结构特征向量。一个具有轴向自注意力机制和 softmax 输出层的深度架构将这些特征映射为代价权重，从构造上满足划分约束，从而确保可接受性。实验表明，与次优划分基线相比，该方法减少了节点扩展数量，同时保持了严格的可接受性。据我们所知，这是首个经过证明能够保证可接受性的机器学习启发式。
查看原文
查看缓存全文

缓存时间: 2026/06/05 02:08 

# 通过代价划分学习可容许启发式函数
来源：https://arxiv.org/abs/2606.04597
查看PDF (https://arxiv.org/pdf/2606.04597)

> 摘要：可容许启发式函数对于最优规划至关重要，然而由于存在高估风险，学习此类启发式函数仍面临较大挑战。代价划分能够在保持可容许性的同时融合多个抽象启发式函数，但在线计算最优划分的代价十分高昂。我们提出了一种框架，通过利用代价划分与乘子预测之间的拉格朗日对偶等价关系，学习推断可容许的代价划分。规划状态与模式被编码为带标签的图，并采用以动作为中心的 Weisfeiler-Leman 算法变体提取结构特征向量。一种具有轴向自注意力机制和 softmax 输出层的深度架构将这些特征映射为代价权重，该权重在构造上即满足划分约束，从而确保可容许性。实验结果表明，与次优划分基线相比，该方法在保持严格可容许性的同时减少了节点扩展次数。据我们所知，这是首个能够保证可容许性的机器学习启发式函数。

## 提交历史

来自：Quentin Cappart \[查看邮箱 (https://arxiv.org/show-email/1f912d48/2606.04597)\] **\[v1\]** 2026年6月3日（周三）08:35:04 UTC（43 KB）

相似文章

AHD Agent：用于自动启发式设计的代理强化学习

arXiv cs.AI

本文介绍了 AHD Agent，这是一个利用代理强化学习（Agentic Reinforcement Learning）的框架，使大型语言模型（LLMs）能够通过动态交互求解环境，自主地为组合优化问题设计启发式方法。

潜在启发式搜索：自动化算法设计的连续优化

arXiv cs.AI

本文提出潜在启发式搜索（LHS）框架，将启发式发现转移到学习的连续潜在流形上，利用基于梯度的优化和归一化流，在大语言模型条件下生成新颖启发式算法，在TSP、CVRP、KSP和在线装箱问题上取得了有竞争力的结果。