arXiv cs.AI· Ruogu Chen, Jie Han·· 11 小时前AI 评分34
EDISCO：面向欧几里得组合优化的等变离散扩散模型
EDISCO: Equivariant DIScrete Diffusion for Euclidean Combinatorial Optimization
AI 导读
EDISCO 是首个在节点索引解上具有精确 E(2) 不变生成分布的离散扩散模型，用于 TSP、CVRP 等欧几里得组合优化问题。它结合 E(2) 等变边评分网络与离散边变量上的类别连续时间马尔可夫链，在 100 至 10000 节点合成 TSP 和 50 至 2000 客户 CVRP 上超越此前学习型 SOTA 求解器，且仅用 33-50% 的训练样本。
正文 · AI 翻译
摘要：欧几里得组合优化问题（ECOPs），例如旅行商问题（TSP）和带容量约束的车辆路径问题（CVRP），在二维欧几里得群 E(2) 下具有固有的对称性，包括旋转、反射和平移。现有的基于学习的方法，包括近期的基于扩散的方法，依赖数据增强或正则化来近似 E(2)-等变性。本文提出 EDISCO，这是首个针对 ECOP 的离散扩散模型，其在节点索引解上具有精确的 E(2)-不变生成分布。EDISCO 引入了 E(2)-等变边评分网络，并结合离散边变量上的分类连续时间马尔可夫链，精确后验采样提供了高效的多步推理。这一设计赋予 EDISCO 局部几何归纳偏置：具有相同相对几何和组合上下文的边邻域无论绝对位置或方向如何都被一致地表示，从而使学习比非等变方法更高效，推理更稳健。EDISCO 在 100 至 10000 个节点的合成 TSP 和 50 至 2000 个客户的 CVRP 上优于先前基于学习的最先进求解器，同时仅使用 33-50% 的训练实例。仅在均匀合成数据上训练，EDISCO 在空间分布偏移和 CVRP 约束紧度偏移下也优于竞争的基于学习基线。代码可在 此 https URL 获取。
| 注释： | 45 页，8 幅图，18 张表，已被 NeurIPS 2026 接收 |
| 主题： | 机器学习（cs.LG）；人工智能（cs.AI） |
| 引用为： | arXiv:2610.04953 [cs.LG] |
| （或 arXiv:2610.04953v2 [cs.LG] 用于此版本） | |
| https://doi.org/10.48550/arXiv.2610.04953 由 DataCite 颁发的 arXiv DOI |
提交历史
来自：Ruogu Chen [查看电子邮件]
[v1]
2026 年 10 月 4 日星期日 04:55:19 UTC（540 KB）
[v2]
2026 年 10 月 19 日星期一 18:44:19 UTC（547 KB）
来源：arXiv cs.AI · arxiv.org