[LG]《Recurrent State Encoders for Efficient Neural Combinatorial Optimization》T Dernedde, D Thyssens, L Schmidt-Thieme [University of Hildesheim] (2025)
神经组合优化中的效率革新：基于递归状态编码器的新范式
• 传统神经组合优化(NCO)利用构造方法逐步生成解，但各步骤状态变化微小，通常只移除已选节点，导致大量计算冗余。
• 本文提出递归状态编码器，通过结合当前状态与上一步的嵌入，实现状态嵌入的高效更新，显著减少重复计算。
• 递归编码器参数量仅为传统编码器的1/3，推理延迟降低1.8-4倍，且性能不降反升，适用于TSP（旅行商问题）、CVRP（容量受限车辆路径问题）和OP（定向问题）。
• 设计中引入超参数k，控制每k步重新用基础编码器计算嵌入，灵活权衡准确性与效率，且模型对k的变化表现出惊人鲁棒性。
• 结合大邻域搜索(LNS)算法，递归模型在实际搜索任务中展现出更优的时间-质量平衡，远超当前主流基线方法。
• 模型训练采用模仿学习，降低复杂度，未来可进一步结合强化学习或自我提升策略提升性能。
• 递归编码器的优势主要得益于仅需学习状态间的“差异”，而非完整状态，使得模型更专注于关键变化，提升泛化能力和推理速度。
• 该方法适合状态演变平滑、后续状态与前一状态高度相似的组合优化问题，未来需探索其在更复杂状态变化问题中的适用性。
心得：
1. 利用状态间差异而非全量重新编码，显著减轻了编码器负担，推动NCO向更高效方向发展。
2. 递归结构天然适合序列决策中的渐进变化，高效复用历史信息兼顾准确性，体现模型设计对问题结构深刻理解。
3. 将递归编码与大邻域搜索结合，架构层面与搜索策略协同优化，提高了实际应用中的性能和效率。
详见🔗arxiv.org/abs/2509.05084
神经组合优化递归神经网络旅行商问题车辆路径问题大邻域搜索高效推理
