arXiv:2606.10321cs.LGcs.AI2026-06

提出无基准策略优化方法,解决神经组合优化训练不稳问题。

Baseline-Free Policy Optimization for Neural Combinatorial Optimization

  • 用轨迹分组归一化优势,彻底取消梯度估计中的基准项。
  • 在TSP-100上避免训练崩溃,性能稳定在成本9.8左右。
  • 无需外部基准,适合对训练稳定性要求高的组合优化场景。

神经组合优化(NCO)通过自回归策略求解路径规划问题。标准训练算法REINFORCE需维护并定期更新一个冻结的策略副本作为基线以降低方差,但该基线在复杂实例上会产生噪声梯度,导致训练不稳定。本文评估了来自大语言模型对齐领域的组相对策略优化(GRPO),该方法通过在采样轨迹组内归一化优势,完全消除基线依赖。在RL4CO框架下的TSP与CVRP基准测试中,五种强化学习算法对比显示:(i) GRPO在TSP-100上避免了REINFORCE出现的训练崩溃——性能从成本9.8骤降至52.1且无法恢复;(ii) 在相同梯度更新次数下,GRPO解的质量仅比强基线POMO低2%,且无需外部基线;(iii) P3O(另一种成对偏好算法)在TSP上表现良好,但在CVRP上波动较大。结果表明,GRPO是神经组合优化中极具前景的无基准替代方案,尤其适用于基线依赖训练易失效的场景。

原文摘要 · Abstract (English)

Neural combinatorial optimization (NCO) trains autoregressive policies to solve routing problems. The standard training algorithm, REINFORCE with a rollout baseline, requires maintaining and periodically updating a frozen copy of the policy for variance reduction. This baseline introduces a structural vulnerability: on harder instances, a poor baseline produces noisy gradient estimates that can destabilize training. We evaluate Group Relative Policy Optimization (GRPO), an algorithm from large language model alignment that eliminates the baseline entirely by normalizing advantages within groups of sampled trajectories. In a controlled comparison of five RL algorithms on TSP and CVRP benchmarks within the RL4CO framework, we find that: (i) GRPO avoids the training collapse observed with REINFORCE on TSP-100, where performance degrades from cost 9.8 to 52.1 immediately after the warmup phase and does not recover under extended training; (ii) at matched gradient updates, GRPO achieves solution quality within 2% of POMO, a strong AM-based multi-start baseline, while requiring no external baseline; and (iii) P3O, a pairwise preference algorithm also from the alignment literature, is competitive on TSP but shows higher variability on CVRP. These results identify GRPO as a promising baseline-free alternative for NCO, particularly in settings where baseline-dependent training becomes fragile.

强化学习组合优化无基准路径规划

Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。