日本フィジカルAI新聞

世界のフィジカルAIを、日本語で。

組合せ最適化arXiv:2606.10321

ベースライン不要のニューラル組合せ最適化のための方策最適化

Baseline-Free Policy Optimization for Neural Combinatorial Optimization

シェア:XThreadsFacebookLINEはてブBluesky

ニューラル組合せ最適化の訓練で、従来のREINFORCEが使うロールアウトベースラインを廃し、グループ内の利点を正規化するGRPOを導入。TSPやCVRPで訓練崩壊を回避し、ベースライン不要でPOMOに匹敵する性能を達成した。

詳しい要約

1. どんなもの?

ニューラル組合せ最適化(NCO)において、自己回帰ポリシーを訓練するための新しい強化学習アルゴリズムを評価した研究。 - 対象問題:TSPとCVRPのルーティング問題 - 使用フレームワーク:RL4CO - 比較した5つのRLアルゴリズム:REINFORCE(rollout baseline付き)、GRPO、P3O、POMOなど - 主な主張:GRPOはベースライン不要で安定した訓練を実現し、POMOに匹敵する解品質を達成

2. 先行研究と比べてどこがすごい?

従来の標準訓練アルゴリズムであるREINFORCE with rollout baselineは、分散低減のために凍結したポリシーのコピーを維持・更新する必要があり、難しいインスタンスではベースラインが不十分だと勾配推定がノイズを含み訓練が不安定になる構造的脆弱性があった。 - GRPOはベースラインを完全に排除し、サンプル軌跡のグループ内でアドバンテージを正規化する - TSP-100でREINFORCEはウォームアップ直後にコスト9.8から52.1へ性能劣化し回復しないが、GRPOは訓練崩壊を回避 - 同一勾配更新回数でGRPOはPOMO(強力なAMベースのマルチスタートベースライン)の解品質の2%以内を達成し、外部ベースラインを必要としない

3. 技術・手法の肝は?

GRPO(Group Relative Policy Optimization)をNCOに適用。 - 大規模言語モデルアラインメント由来のアルゴリズム - サンプルされた軌跡のグループ内でアドバンテージを正規化することで、ベースラインを不要にする - ベースラインの維持・更新が不要 - 比較対象としてP3O(ペアワイズ選好アルゴリズム)も評価

4. どうやって有効だと検証した?

RL4COフレームワーク内でTSPとCVRPベンチマークを用い、5つのRLアルゴリズムを制御比較。 - TSP-100でREINFORCEの訓練崩壊(コスト9.8→52.1)を確認し、GRPOがそれを回避することを実証 - 同一勾配更新回数でGRPOがPOMOの解品質の2%以内を達成 - P3OはTSPで競争力があるがCVRPで変動性が高いことを示した

5. 議論はある?

GRPOはベースライン不要の有望な代替手法であり、特にベースライン依存の訓練が脆弱になる設定で有効であると結論。 - P3OはTSPでは競争力があるがCVRPでは変動性が高い - 限界や今後の課題についての具体的な議論は要旨からは不明

6. 次に読むべき論文は?

要旨で参照・比較されている研究: - REINFORCE with rollout baseline - POMO(AM-based multi-start baseline) - P3O(pairwise preference algorithm) - GRPO(Group Relative Policy Optimization) - RL4COフレームワーク 関連手法として、NCOにおける他の強化学習アルゴリズムやアラインメント由来の手法も読む価値がある。

※ AIが要旨から生成した要約です。正確性は原文をご確認ください。

著者: Carlos S. Sepúlveda, Gonzalo A. Ruz

分類: cs.LG, cs.AI, cs.RO, math.OC

原文アブストラクト

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.

関連論文

  1. 1Boston Dynamics、車輪付きAtlasの研究試作機を紹介研究・技術
  2. 2newmoとKDDIが資本業務提携 2028年に堺市で自動運転タクシー商用化目指す提携・買収
  3. 3GXOとApptronik、Apolloの物流現場試験を拡大 最大1,000台の展開を構想量産・展開
  4. 4NVIDIA、CoRLでGR00T 2とIsaac Lab 3.0を発表新製品・発表
  5. 5UC BerkeleyとNVIDIAの研究者、AIエージェントでロボット制御コードを仮想環境で改善研究・技術

PR・アフィリエイト広告

FRONTIER(GPU搭載BTOパソコン)

FRONTIER(GPU搭載BTOパソコン)の公式広告バナーFRONTIERでGPU搭載PCを見る ↗
PR本紙発行元 EmplifAI