論文の概要: A State Aggregation Approach for Solving Knapsack Problem with Deep Reinforcement Learning

• arxiv url: http://arxiv.org/abs/2004.12117v1
• Date: Sat, 25 Apr 2020 11:52:24 GMT
• ステータス: 処理完了
• システム内更新日: 2022-12-09 21:09:35.939215
• Title: A State Aggregation Approach for Solving Knapsack Problem with Deep Reinforcement Learning
• Title（参考訳）: 深層強化学習を用いた Knapsack 問題解決のための状態集約手法
• Authors: Reza Refaei Afshar and Yingqian Zhang and Murat Firat and Uzay Kaymak
• Abstract要約: 本稿では,knapsack問題の解法として,Deep Reinforcement Learning (DRL)アプローチを提案する。 状態集約ポリシーは、knapsack問題の各問題インスタンスに適用される。 ステートアグリゲーション戦略を用いた提案モデルは、より良いソリューションを提供するだけでなく、ステートアグリゲーションのないモデルよりも少ないタイムステップで学習する。
• 参考スコア（独自算出の注目度）: 3.614984020677526
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: This paper proposes a Deep Reinforcement Learning (DRL) approach for solving knapsack problem. The proposed method consists of a state aggregation step based on tabular reinforcement learning to extract features and construct states. The state aggregation policy is applied to each problem instance of the knapsack problem, which is used with Advantage Actor Critic (A2C) algorithm to train a policy through which the items are sequentially selected at each time step. The method is a constructive solution approach and the process of selecting items is repeated until the final solution is obtained. The experiments show that our approach provides close to optimal solutions for all tested instances, outperforms the greedy algorithm, and is able to handle larger instances and more flexible than an existing DRL approach. In addition, the results demonstrate that the proposed model with the state aggregation strategy not only gives better solutions but also learns in less timesteps, than the one without state aggregation.
• Abstract（参考訳）: 本稿では,knapsack問題の解法として,Deep Reinforcement Learning (DRL)アプローチを提案する。 提案手法は,表型強化学習に基づく状態集約ステップから構成し,特徴と構成状態を抽出する。 状態集約ポリシは、アドバンテージアクター批評家(A2C)アルゴリズムで使用されるknapsack問題の各問題インスタンスに適用され、各ステップでアイテムが順次選択されるポリシーをトレーニングする。 本発明の方法は、構成解法であり、最終解が得られるまで、アイテムを選択する工程を繰り返す。 実験の結果,本手法はすべてのテストインスタンスに対して最適に近い解を提供し,グレディアルゴリズムより優れ,既存のDRL手法よりも大きなインスタンスを処理し,より柔軟であることがわかった。 さらに, 状態集約戦略を用いた提案モデルが, 状態集約戦略のないモデルよりも優れた解を与えるだけでなく, 少ない時間ステップで学習できることを示した。

関連論文リスト

• Take a Step and Reconsider: Sequence Decoding for Self-Improved Neural Combinatorial Optimization [1.1510009152620668]
  自己改善学習のための単純で問題に依存しないシーケンス復号法を提案する。 以前にサンプリングされたシーケンスを無視するためにポリシーを変更することで、目に見えない代替案のみを検討するように強制する。 本手法は,ジョブショップスケジューリング問題における従来のNCO手法よりも優れていた。
  論文  参考訳（メタデータ） (2024-07-24T12:06:09Z)
• 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, Exploration-Based Policy Optimisation for Routing Problems [2.6782615615913348]
  本稿では,エントロピーに基づく新しい強化学習手法を提案する。 さらに、我々は、期待したリターンを最大化する、政治以外の強化学習手法を設計する。 我々のモデルは様々な経路問題に一般化可能であることを示す。
  論文  参考訳（メタデータ） (2022-05-31T09:51:48Z)
• Instance-Dependent Confidence and Early Stopping for Reinforcement Learning [99.57168572237421]
  強化学習(RL)のための様々なアルゴリズムは、その収束率の劇的な変動を問題構造の関数として示している。 この研究は、観察されたパフォーマンスの違いについて、textitexを説明する保証を提供する。 次の自然なステップは、これらの理論的保証を実際に有用なガイドラインに変換することです。
  論文  参考訳（メタデータ） (2022-01-21T04:25:35Z)
• A Boosting Approach to Reinforcement Learning [59.46285581748018]
  複雑度が状態数に依存しない意思決定プロセスにおける強化学習のための効率的なアルゴリズムについて検討する。 このような弱い学習手法の精度を向上させることができる効率的なアルゴリズムを提供する。
  論文  参考訳（メタデータ） (2021-08-22T16:00:45Z)
• Adaptive Sampling for Best Policy Identification in Markov Decision Processes [79.4957965474334]
  本稿では,学習者が生成モデルにアクセスできる場合の,割引マルコフ決定(MDP)における最良の政治的識別の問題について検討する。 最先端アルゴリズムの利点を論じ、解説する。
  論文  参考訳（メタデータ） (2020-09-28T15:22:24Z)
• Variance-Reduced Off-Policy Memory-Efficient Policy Search [61.23789485979057]
  政治政策の最適化は強化学習において難しい問題である。 オフポリシーアルゴリズムはメモリ効率が高く、オフポリシーサンプルから学ぶことができる。
  論文  参考訳（メタデータ） (2020-09-14T16:22:46Z)
• Combining Deep Learning and Optimization for Security-Constrained Optimal Power Flow [94.24763814458686]
  セキュリティに制約のある最適電力フロー(SCOPF)は、電力システムの基本である。 SCOPF問題におけるAPRのモデル化は、複雑な大規模混合整数プログラムをもたらす。 本稿では,ディープラーニングとロバスト最適化を組み合わせた新しい手法を提案する。
  論文  参考訳（メタデータ） (2020-07-14T12:38:21Z)
• Robust Reinforcement Learning using Least Squares Policy Iteration with Provable Performance Guarantees [3.8073142980733]
  本稿では,ロバストマルコフ決定過程(RMDP)におけるモデルレス強化学習の課題について述べる。 本稿では、まず、ポリシー評価のための多段階オンラインモデルフリー学習アルゴリズムであるRobust Least Squares Policy Evaluationアルゴリズムを提案する。 次に,ロバスト・ラスト・スクエアズ・ポリシー・イテレーション (RLSPI) アルゴリズムを提案し,ロバスト・ラスト・スクエアズ・ポリシーを最適に学習する。
  論文  参考訳（メタデータ） (2020-06-20T16:26:50Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。