用递归编码器复用计算，让组合优化模型更快更高效。
Recurrent State Encoders for Efficient Neural Combinatorial Optimization
- 引入递归编码器，利用前一步状态嵌入提升计算效率。
- 层数减少3倍仍保持同等或更好性能，显著降低延迟。
- 适用于TSP、CVRP、OP等组合优化问题，适合实际部署。
神经组合优化（NCO）的主流方法是构建式算法，即神经网络逐个添加解的组成部分直至形成完整解。我们发现，相邻步骤间状态变化通常很小，因为每次仅有一个节点被加入解中并从状态中移除。因此，高效的模型应能复用先前步骤的计算。为此，我们提出一种递归编码器，其状态嵌入不仅基于当前状态，还结合了前一状态的嵌入。实验表明，该递归编码器在仅需非递归编码器1/3层数的情况下，性能相当或更优，显著提升推理速度。我们在旅行商问题（TSP）、容量受限车辆路径问题（CVRP）和定向旅行者问题（OP）三个问题上验证了该方法的有效性，并将其集成到大邻域搜索算法中，展示了其实际应用价值。
原文摘要 · Abstract (English)
The primary paradigm in Neural Combinatorial Optimization (NCO) consists of construction methods, where a neural network is trained to sequentially add one solution component at a time until a complete solution is formed. We observe that the typical changes to the state between two steps are small, since usually only the node added to the solution is removed from the state. An efficient model should be able to reuse computation from prior steps. To that end, we propose a recurrent encoder that computes state embeddings based not only on the current state but also on embeddings from the previous state. We show that this recurrent encoder can achieve equivalent or better performance than a non-recurrent encoder even with $3\times$ fewer layers, thus significantly improving latency. We demonstrate our findings on three different problems: the Traveling Salesman Problem (TSP), the Capacitated Vehicle Routing Problem (CVRP), and the Orienteering Problem (OP), and integrate the models into a large neighborhood search algorithm to showcase the practical relevance of our findings.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。