Self-Improvement for Neural Combinatorial Optimization: Sample without Replacement, but Improvement
作者: Jonathan Pirnay, Dominik G. Grimm
分类: cs.LG
发布日期: 2024-03-22 (更新: 2024-06-11)
备注: Published in Transactions on Machine Learning Research (TMLR) (06/2024)
期刊: Transactions on Machine Learning Research (TMLR) 06/2024, Featured Certification
💡 一句话要点
提出一种新方法以简化神经组合优化的训练过程
🎯 匹配领域: 支柱二：RL算法与架构 (RL & Architecture)
关键词: 神经组合优化 强化学习 行为克隆 随机束搜索 策略改进 作业车间调度 旅行商问题 车辆路径问题
📋 核心要点
- 现有的神经组合优化方法在训练过程中依赖于昂贵的专家数据或复杂的策略梯度方法，导致效率低下。
- 本研究提出了一种通过多次采样和选择最佳解决方案来简化训练过程的方法，结合了随机束搜索和策略改进。
- 实验结果显示，所提方法在旅行商问题和容量车辆路径问题上表现出与专家数据相当的性能，并在作业车间调度问题上超越了现有方法。
📝 摘要（中文）
当前的端到端构造神经组合优化方法通常依赖于专家解决方案进行行为克隆或使用强化学习的策略梯度方法进行训练。尽管行为克隆简单，但需要昂贵的专家解决方案，而策略梯度方法通常计算复杂且难以微调。本研究通过在每个训练周期中使用当前模型对随机实例进行多次采样，并选择最佳解决方案作为监督模仿学习的专家轨迹，从而简化训练过程。为实现逐步改进的解决方案，本文引入了一种结合轮次随机束搜索与可证明策略改进的更新策略的方法。我们在旅行商问题和容量车辆路径问题上评估了该方法，结果表明，使用该方法训练的模型在性能和泛化能力上与使用专家数据训练的模型相当。此外，我们还将该方法应用于作业车间调度问题，使用基于变换器的架构，显著超越现有的最先进方法。
🔬 方法详解
问题定义：本论文旨在解决神经组合优化中训练效率低下的问题，现有方法依赖于专家数据或复杂的策略梯度，导致训练成本高且难以调优。
核心思路：提出通过在每个训练周期中对随机实例进行多次采样，并选择最佳解决方案作为专家轨迹，从而简化训练过程，结合随机束搜索与策略改进以实现逐步优化。
技术框架：整体流程包括：1) 使用当前模型对随机实例进行多次采样；2) 选择最佳解决方案作为专家轨迹；3) 通过结合随机束搜索和策略改进更新模型。
关键创新：最重要的创新在于通过几乎没有计算开销的方式，在轮次之间利用采样序列的优势来精炼策略，这一方法有效地降低了对专家数据的依赖。
关键设计：在模型训练中，采用了轮次随机束搜索的策略，并设计了相应的损失函数以优化模型性能，确保在不同问题上都能实现良好的泛化能力。
🖼️ 关键图片
📊 实验亮点
实验结果表明，使用本方法训练的模型在旅行商问题和容量车辆路径问题上表现出与专家数据相当的性能。此外，在作业车间调度问题上，所提方法的性能显著超越了现有的最先进方法，提升幅度达到XX%。
🎯 应用场景
该研究的潜在应用领域包括物流优化、生产调度和资源分配等问题，能够为实际工业场景提供高效的解决方案。未来，该方法可能在更多组合优化问题中展现出广泛的适用性和实际价值。
📄 摘要（原文）
Current methods for end-to-end constructive neural combinatorial optimization usually train a policy using behavior cloning from expert solutions or policy gradient methods from reinforcement learning. While behavior cloning is straightforward, it requires expensive expert solutions, and policy gradient methods are often computationally demanding and complex to fine-tune. In this work, we bridge the two and simplify the training process by sampling multiple solutions for random instances using the current model in each epoch and then selecting the best solution as an expert trajectory for supervised imitation learning. To achieve progressively improving solutions with minimal sampling, we introduce a method that combines round-wise Stochastic Beam Search with an update strategy derived from a provable policy improvement. This strategy refines the policy between rounds by utilizing the advantage of the sampled sequences with almost no computational overhead. We evaluate our approach on the Traveling Salesman Problem and the Capacitated Vehicle Routing Problem. The models trained with our method achieve comparable performance and generalization to those trained with expert data. Additionally, we apply our method to the Job Shop Scheduling Problem using a transformer-based architecture and outperform existing state-of-the-art methods by a wide margin.