用离线强化学习超越经典启发式算法，解决旅行商问题
Offline Decision Transformers for Neural Combinatorial Optimization: Surpassing Heuristics on the Traveling Salesman Problem
- 用决策变换器从启发式解数据中学习，不依赖在线训练
- 在所有测试实例上均优于四种经典启发式算法
- 适合想提升组合优化性能的研究者和工程师
组合优化问题如旅行商问题在工业中至关重要，但属于NP难问题。神经组合优化虽有潜力，但依赖在线强化学习限制了部署，也未充分利用数十年积累的算法知识。本文提出将离线强化学习框架决策变换器应用于该问题，直接从启发式解数据集中学习更优策略，目标不仅是模仿，更是合成并超越现有方法。具体地，(i) 引入指针网络处理节点选择中的实例相关、可变动作空间；(ii) 采用分位数回归进行乐观的返奖预估条件建模，这对最优值差异大的实例尤为关键。实验表明，该方法在所有测试实例上均生成质量更高的路径，显著优于所训练的四种经典启发式算法，证明离线强化学习能挖掘并突破现有领域知识的性能边界。
原文摘要 · Abstract (English)
Combinatorial optimization problems like the Traveling Salesman Problem are critical in industry yet NP-hard. Neural Combinatorial Optimization has shown promise, but its reliance on online reinforcement learning (RL) hampers deployment and underutilizes decades of algorithmic knowledge. We address these limitations by applying the offline RL framework, Decision Transformer, to learn superior strategies directly from datasets of heuristic solutions; it aims to not only to imitate but to synthesize and outperform them. Concretely, we (i) integrate a Pointer Network to handle the instance-dependent, variable action space of node selection, and (ii) employ expectile regression for optimistic conditioning of Return-to-Go, which is crucial for instances with widely varying optimal values. Experiments show that our method consistently produces higher-quality tours than the four classical heuristics it is trained on, demonstrating the potential of offline RL to unlock and exceed the performance embedded in existing domain knowledge.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。