論文の概要: Self-Improvement for Neural Combinatorial Optimization: Sample without Replacement, but Improvement
- arxiv url: http://arxiv.org/abs/2403.15180v2
- Date: Tue, 11 Jun 2024 19:48:33 GMT
- ステータス: 処理完了
- システム内更新日: 2024-06-13 22:34:15.902531
- Title: Self-Improvement for Neural Combinatorial Optimization: Sample without Replacement, but Improvement
- Title（参考訳）: ニューラルネットワークによる最適化のための自己改善: 置き換えせずに、改善されたサンプル
- Authors: Jonathan Pirnay, Dominik G. Grimm,
- Abstract要約: 建設的ニューラル最適化の現在の手法は、通常、専門家ソリューションからの行動クローニングや強化学習からのポリシー勾配手法を用いてポリシーを訓練する。
各エポックにおける現在のモデルを用いて、ランダムなインスタンスに対して複数の解をサンプリングし、その後、教師付き模倣学習のための専門家の軌跡として最適な解を選択することにより、この2つを橋渡しする。
我々は,旅行セールスマン問題とキャパシタントカールーティング問題に対する我々のアプローチを評価し,本手法で訓練したモデルは,専門家データで訓練したモデルと同等の性能と一般化を実現する。
- 参考スコア（独自算出の注目度）: 1.1510009152620668
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: 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.
- Abstract（参考訳）: エンドツーエンド構築型ニューラルネットワーク最適化の現在の手法は、通常、専門家ソリューションからの行動クローニングや強化学習からのポリシー勾配手法を用いてポリシーを訓練する。
行動クローニングは単純であるが、高価な専門家のソリューションが必要であり、ポリシー勾配法は計算的に要求され、微調整が複雑であることが多い。
本研究では、各エポックにおける現在のモデルを用いてランダムなインスタンスに対する複数のソリューションをサンプリングし、その後、教師付き模倣学習の専門的軌跡として最適解を選択することにより、これら2つを橋渡しし、トレーニングプロセスを簡素化する。
最小限のサンプリングで徐々に改善する手法を実現するため,提案手法では,ラウンドワイド・確率的ビームサーチと,証明可能なポリシー改善から得られた更新戦略を組み合わせた手法を提案する。
この戦略は、ほとんど計算オーバーヘッドのないサンプルシーケンスの利点を利用して、ラウンド間のポリシーを洗練させる。
我々は,トラベリングセールスマン問題とキャパシタントカールーティング問題に対する我々のアプローチを評価する。
本手法で訓練したモデルでは,専門家データと同等の性能と一般化を実現している。
さらに,この手法をトランスフォーマーアーキテクチャを用いてジョブショップスケジューリング問題に適用し,既存の最先端手法よりも広いマージンで性能を向上する。
関連論文リスト
- Take a Step and Reconsider: Sequence Decoding for Self-Improved Neural Combinatorial Optimization [1.1510009152620668]
自己改善学習のための単純で問題に依存しないシーケンス復号法を提案する。
以前にサンプリングされたシーケンスを無視するためにポリシーを変更することで、目に見えない代替案のみを検討するように強制する。
本手法は,ジョブショップスケジューリング問題における従来のNCO手法よりも優れていた。
論文 参考訳（メタデータ） (2024-07-24T12:06:09Z) - Learning Optimal Deterministic Policies with Stochastic Policy Gradients [62.81324245896716]
政策勾配法(PG法)は連続強化学習(RL法)問題に対処する手法として成功している。
一般的には、収束(ハイパー)政治は、決定論的バージョンをデプロイするためにのみ学習される。
本稿では,サンプルの複雑性とデプロイされた決定論的ポリシのパフォーマンスのトレードオフを最適化するために,学習に使用する探索レベルの調整方法を示す。
論文 参考訳（メタデータ） (2024-05-03T16:45:15Z) - RLIF: Interactive Imitation Learning as Reinforcement Learning [56.997263135104504]
我々は,対話型模倣学習と類似するが,さらに実践的な仮定の下で,非政治強化学習によってパフォーマンスが向上できることを実証する。
提案手法は,ユーザ介入信号を用いた強化学習を報奨として利用する。
このことは、インタラクティブな模倣学習において介入する専門家がほぼ最適であるべきだという仮定を緩和し、アルゴリズムが潜在的に最適でない人間の専門家よりも改善される行動を学ぶことを可能にする。
論文 参考訳（メタデータ） (2023-11-21T21:05:21Z) - Optimizing Solution-Samplers for Combinatorial Problems: The Landscape
of Policy-Gradient Methods [52.0617030129699]
本稿では,DeepMatching NetworksとReinforcement Learningメソッドの有効性を解析するための新しい理論フレームワークを提案する。
我々の主な貢献は、Max- and Min-Cut、Max-$k$-Bipartite-Bi、Maximum-Weight-Bipartite-Bi、Traveing Salesman Problemを含む幅広い問題である。
本分析の副産物として,バニラ降下による新たな正則化プロセスを導入し,失効する段階的な問題に対処し,悪い静止点から逃れる上で有効であることを示す理論的および実験的証拠を提供する。
論文 参考訳（メタデータ） (2023-10-08T23:39:38Z) - Deep Reinforcement Learning for Exact Combinatorial Optimization:
Learning to Branch [13.024115985194932]
本稿では、強化学習(RL)パラダイムを用いた最適化において、データラベリングと推論の問題を解決するための新しいアプローチを提案する。
我々は模倣学習を用いてRLエージェントをブートストラップし、PPO(Proximal Policy)を使用してグローバルな最適なアクションを探索する。
論文 参考訳（メタデータ） (2022-06-14T16:35:58Z) - Sample-Efficient, Exploration-Based Policy Optimisation for Routing
Problems [2.6782615615913348]
本稿では,エントロピーに基づく新しい強化学習手法を提案する。
さらに、我々は、期待したリターンを最大化する、政治以外の強化学習手法を設計する。
我々のモデルは様々な経路問題に一般化可能であることを示す。
論文 参考訳（メタデータ） (2022-05-31T09:51:48Z) - A Boosting Approach to Reinforcement Learning [59.46285581748018]
複雑度が状態数に依存しない意思決定プロセスにおける強化学習のための効率的なアルゴリズムについて検討する。
このような弱い学習手法の精度を向上させることができる効率的なアルゴリズムを提供する。
論文 参考訳（メタデータ） (2021-08-22T16:00:45Z) - Contrastive Losses and Solution Caching for Predict-and-Optimize [19.31153168397003]
ノイズコントラスト法を用いて、サロゲート損失関数の族を動機付ける。
すべての予測と最適化アプローチのボトルネックに対処する。
非常に遅い成長率でさえ、最先端の手法の質に合わせるのに十分であることを示す。
論文 参考訳（メタデータ） (2020-11-10T19:09:12Z) - Lane-Merging Using Policy-based Reinforcement Learning and
Post-Optimization [0.0]
政策に基づく強化学習と局所最適化を組み合わせることで,2つの方法論のベストプラクティスを育成,合成する。
車両数の異なる車線変更シナリオを用いて提案手法の評価を行った。
論文 参考訳（メタデータ） (2020-03-06T12:57:25Z) - Learning with Differentiable Perturbed Optimizers [54.351317101356614]
本稿では,操作を微分可能で局所的に一定ではない操作に変換する手法を提案する。
提案手法は摂動に依拠し,既存の解法とともに容易に利用することができる。
本稿では,この枠組みが,構造化予測において発達した損失の族とどのように結びつくかを示し,学習課題におけるそれらの使用に関する理論的保証を与える。
論文 参考訳（メタデータ） (2020-02-20T11:11:32Z) - Reward-Conditioned Policies [100.64167842905069]
模倣学習には、ほぼ最適の専門家データが必要である。
実演なしで指導的学習を通じて効果的な政策を学べるか?
政策探索の原則的手法として,このようなアプローチを導出する方法を示す。
論文 参考訳（メタデータ） (2019-12-31T18:07:43Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。