論文の概要: Take a Step and Reconsider: Sequence Decoding for Self-Improved Neural Combinatorial Optimization
- arxiv url: http://arxiv.org/abs/2407.17206v1
- Date: Wed, 24 Jul 2024 12:06:09 GMT
- ステータス: 処理完了
- システム内更新日: 2024-07-25 14:04:14.537874
- Title: Take a Step and Reconsider: Sequence Decoding for Self-Improved Neural Combinatorial Optimization
- Title（参考訳）: ステップと再考:自己改善型ニューラルネットワーク最適化のためのシーケンスデコーディング
- Authors: Jonathan Pirnay, Dominik G. Grimm,
- Abstract要約: 自己改善学習のための単純で問題に依存しないシーケンス復号法を提案する。
以前にサンプリングされたシーケンスを無視するためにポリシーを変更することで、目に見えない代替案のみを検討するように強制する。
本手法は,ジョブショップスケジューリング問題における従来のNCO手法よりも優れていた。
- 参考スコア（独自算出の注目度）: 1.1510009152620668
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: The constructive approach within Neural Combinatorial Optimization (NCO) treats a combinatorial optimization problem as a finite Markov decision process, where solutions are built incrementally through a sequence of decisions guided by a neural policy network. To train the policy, recent research is shifting toward a 'self-improved' learning methodology that addresses the limitations of reinforcement learning and supervised approaches. Here, the policy is iteratively trained in a supervised manner, with solutions derived from the current policy serving as pseudo-labels. The way these solutions are obtained from the policy determines the quality of the pseudo-labels. In this paper, we present a simple and problem-independent sequence decoding method for self-improved learning based on sampling sequences without replacement. We incrementally follow the best solution found and repeat the sampling process from intermediate partial solutions. By modifying the policy to ignore previously sampled sequences, we force it to consider only unseen alternatives, thereby increasing solution diversity. Experimental results for the Traveling Salesman and Capacitated Vehicle Routing Problem demonstrate its strong performance. Furthermore, our method outperforms previous NCO approaches on the Job Shop Scheduling Problem.
- Abstract（参考訳）: Neural Combinatorial Optimization(NCO)における構成的アプローチは、組合せ最適化問題を有限マルコフ決定プロセスとして扱い、ニューラルネットワークによって導かれる一連の決定を通じてソリューションを段階的に構築する。
政策を訓練するために、近年の研究は強化学習と教師付きアプローチの限界に対処する「自己改善型」学習方法論へと移行しつつある。
ここでは、ポリシーは監督的な方法で反復的に訓練され、現在の方針から派生した解決策は擬似ラベルとして機能する。
これらの解がポリシーから得られる方法は、擬似ラベルの品質を決定する。
本稿では,置換のないサンプリングシーケンスに基づく自己改善学習のための,単純かつ問題に依存しないシーケンス復号法を提案する。
得られた最良の解を段階的に追従し、中間部分解からのサンプリングプロセスを繰り返す。
以前にサンプリングされたシーケンスを無視するためにポリシーを変更することで、見つからない代替案のみを考えることを強制し、解の多様性を増大させる。
トラベリングセールスマンとキャパシタントカールーティング問題の実験結果が,その性能を実証している。
さらに,本手法は,ジョブショップスケジューリング問題における従来のNCO手法よりも優れていた。
関連論文リスト
- Self-Improvement for Neural Combinatorial Optimization: Sample without Replacement, but Improvement [1.1510009152620668]
建設的ニューラル最適化の現在の手法は、通常、専門家ソリューションからの行動クローニングや強化学習からのポリシー勾配手法を用いてポリシーを訓練する。
各エポックにおける現在のモデルを用いて、ランダムなインスタンスに対して複数の解をサンプリングし、その後、教師付き模倣学習のための専門家の軌跡として最適な解を選択することにより、この2つを橋渡しする。
我々は,旅行セールスマン問題とキャパシタントカールーティング問題に対する我々のアプローチを評価し,本手法で訓練したモデルは,専門家データで訓練したモデルと同等の性能と一般化を実現する。
論文 参考訳（メタデータ） (2024-03-22T13:09:10Z) - 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) - Sample-Efficient Multi-Objective Learning via Generalized Policy
Improvement Prioritization [8.836422771217084]
マルチオブジェクト強化学習(MORL)アルゴリズムは、エージェントが異なる好みを持つ可能性のあるシーケンシャルな決定問題に対処する。
本稿では、一般化政策改善(GPI)を用いて、原則的、正式に派生した優先順位付けスキームを定義する新しいアルゴリズムを提案する。
実験により,本手法は多目的タスクの挑戦において,最先端のMORLアルゴリズムよりも優れていることを示す。
論文 参考訳（メタデータ） (2023-01-18T20:54:40Z) - Reinforcement Learning Methods for Wordle: A POMDP/Adaptive Control
Approach [0.3093890460224435]
我々は、新しい強化学習手法を用いて、人気のあるWordleパズルの解法に対処する。
Wordleパズルでは、比較的控えめな計算コストで最適に近いオンラインソリューション戦略が得られる。
論文 参考訳（メタデータ） (2022-11-15T03:46:41Z) - Learning Proximal Operators to Discover Multiple Optima [66.98045013486794]
非家族問題における近位演算子を学習するためのエンドツーエンド手法を提案する。
本手法は,弱い目的と穏やかな条件下では,世界規模で収束することを示す。
論文 参考訳（メタデータ） (2022-01-28T05:53:28Z) - Instance-Dependent Confidence and Early Stopping for Reinforcement
Learning [99.57168572237421]
強化学習(RL)のための様々なアルゴリズムは、その収束率の劇的な変動を問題構造の関数として示している。
この研究は、観察されたパフォーマンスの違いについて、textitexを説明する保証を提供する。
次の自然なステップは、これらの理論的保証を実際に有用なガイドラインに変換することです。
論文 参考訳（メタデータ） (2022-01-21T04:25:35Z) - Modularity in Reinforcement Learning via Algorithmic Independence in
Credit Assignment [79.5678820246642]
提案手法は, 事前決定の順序に対して, スパース変化のみを必要とする伝達問題に対して, 政策段階の手法よりも, より標本効率が高いことを示す。
我々は最近提案された社会的意思決定の枠組みをマルコフ決定プロセスよりもよりきめ細かい形式主義として一般化する。
論文 参考訳（メタデータ） (2021-06-28T21:29:13Z) - Logistic Q-Learning [87.00813469969167]
MDPにおける最適制御の正規化線形プログラミング定式化から導いた新しい強化学習アルゴリズムを提案する。
提案アルゴリズムの主な特徴は,広範に使用されているベルマン誤差の代わりとして理論的に音声として機能する,政策評価のための凸損失関数である。
論文 参考訳（メタデータ） (2020-10-21T17:14:31Z) - Adaptive Sampling for Best Policy Identification in Markov Decision
Processes [79.4957965474334]
本稿では,学習者が生成モデルにアクセスできる場合の,割引マルコフ決定(MDP)における最良の政治的識別の問題について検討する。
最先端アルゴリズムの利点を論じ、解説する。
論文 参考訳（メタデータ） (2020-09-28T15:22:24Z) - Constrained Combinatorial Optimization with Reinforcement Learning [0.30938904602244344]
本稿では,RL(Deep Reinforcement Learning)を用いた制約付き最適化問題に対処する枠組みを提案する。
我々は、その定式化における制約に対処するために、Neural Combinatorial Optimization(NCO)理論を拡張した。
その文脈では、ソリューションは環境との相互作用に基づいて反復的に構築されます。
論文 参考訳（メタデータ） (2020-06-22T03:13:07Z) - A State Aggregation Approach for Solving Knapsack Problem with Deep
Reinforcement Learning [3.614984020677526]
本稿では,knapsack問題の解法として,Deep Reinforcement Learning (DRL)アプローチを提案する。
状態集約ポリシーは、knapsack問題の各問題インスタンスに適用される。
ステートアグリゲーション戦略を用いた提案モデルは、より良いソリューションを提供するだけでなく、ステートアグリゲーションのないモデルよりも少ないタイムステップで学習する。
論文 参考訳（メタデータ） (2020-04-25T11:52:24Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。