論文の概要: Deep Reinforcement Learning for Exact Combinatorial Optimization: Learning to Branch

• arxiv url: http://arxiv.org/abs/2206.06965v1
• Date: Tue, 14 Jun 2022 16:35:58 GMT
• ステータス: 処理完了
• システム内更新日: 2022-06-15 14:08:15.815687
• Title: Deep Reinforcement Learning for Exact Combinatorial Optimization: Learning to Branch
• Title（参考訳）: Exact Combinatorial Optimizationのための深層強化学習:ブランチへの学習
• Authors: Tianyu Zhang, Amin Banitalebi-Dehkordi, and Yong Zhang
• Abstract要約: 本稿では、強化学習(RL)パラダイムを用いた最適化において、データラベリングと推論の問題を解決するための新しいアプローチを提案する。 我々は模倣学習を用いてRLエージェントをブートストラップし、PPO(Proximal Policy)を使用してグローバルな最適なアクションを探索する。
• 参考スコア（独自算出の注目度）: 13.024115985194932
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Branch-and-bound is a systematic enumerative method for combinatorial optimization, where the performance highly relies on the variable selection strategy. State-of-the-art handcrafted heuristic strategies suffer from relatively slow inference time for each selection, while the current machine learning methods require a significant amount of labeled data. We propose a new approach for solving the data labeling and inference latency issues in combinatorial optimization based on the use of the reinforcement learning (RL) paradigm. We use imitation learning to bootstrap an RL agent and then use Proximal Policy Optimization (PPO) to further explore global optimal actions. Then, a value network is used to run Monte-Carlo tree search (MCTS) to enhance the policy network. We evaluate the performance of our method on four different categories of combinatorial optimization problems and show that our approach performs strongly compared to the state-of-the-art machine learning and heuristics based methods.
• Abstract（参考訳）: 分岐とバウンドは組合せ最適化の体系的列挙法であり、性能は変数選択戦略に大きく依存する。 最先端の手作りヒューリスティック戦略は、選択毎に比較的遅い推論時間に苦しむ一方で、現在の機械学習手法ではかなりの量のラベル付きデータを必要とする。 本稿では,強化学習(rl)パラダイムを用いた組合せ最適化におけるデータラベリングと推論遅延問題を解決するための新しい手法を提案する。 我々は模倣学習を用いてRLエージェントをブートストラップし、次いでPPO(Proximal Policy Optimization)を用いてグローバルな最適行動を探る。 次に、値ネットワークを用いてモンテカルロ木探索(mcts)を行い、ポリシーネットワークを強化する。 本手法は,組合せ最適化問題の4つのカテゴリについて性能評価を行い,最先端の機械学習やヒューリスティックスに基づく手法と比較して,高い性能を示す。

関連論文リスト

• Enhancing Spectrum Efficiency in 6G Satellite Networks: A GAIL-Powered Policy Learning via Asynchronous Federated Inverse Reinforcement Learning [67.95280175998792]
  ビームフォーミング,スペクトルアロケーション,リモートユーザ機器(RUE)アソシエイトを最適化するために,GAILを利用した新しいポリシー学習手法を提案する。 手動チューニングなしで報酬関数を自動的に学習するために、逆RL(IRL)を用いる。 提案手法は従来のRL手法よりも優れており,コンバージェンスと報酬値の14.6%の改善が達成されている。
  論文  参考訳（メタデータ） (2024-09-27T13:05:02Z)
• Reinforcement Learning as an Improvement Heuristic for Real-World Production Scheduling [0.0]
  1つの有望なアプローチは、RLエージェントを改善として訓練することであり、小さな変更を適用することで反復的に改善される最適以下のソリューションから始まる。 本手法を実世界の多目的生産スケジューリング問題に適用する。 当社のアプローチを、業界パートナの本当のデータを使って、他のアプローチと比較し、その優れたパフォーマンスを実証しました。
  論文  参考訳（メタデータ） (2024-09-18T12:48:56Z)
• Learning Rate-Free Reinforcement Learning: A Case for Model Selection with Non-Stationary Objectives [22.06443176759265]
  モデル選択は強化学習アルゴリズムの失敗モードを改善するのに有効であることを示す。 本研究では,モデル選択法を用いて学習速度を最適に選択する学習速度自由強化学習のためのモデル選択フレームワークを提案する。
  論文  参考訳（メタデータ） (2024-08-07T18:55:58Z)
• Unleashing the Potential of Large Language Models as Prompt Optimizers: An Analogical Analysis with Gradient-based Model Optimizers [108.72225067368592]
  本稿では,大規模言語モデル(LLM)に基づくプロンプトの設計について検討する。 モデルパラメータ学習における2つの重要な要素を同定する。 特に、勾配に基づく最適化から理論的な枠組みや学習手法を借用し、改良された戦略を設計する。
  論文  参考訳（メタデータ） (2024-02-27T15:05:32Z)
• Machine Learning Insides OptVerse AI Solver: Design Principles and Applications [74.67495900436728]
  本稿では,Huawei CloudのOpsVerse AIソルバに機械学習(ML)技術を統合するための総合的研究について述べる。 本稿では,実世界の多面構造を反映した生成モデルを用いて,複雑なSATインスタンスとMILPインスタンスを生成する手法を紹介する。 本稿では,解解器性能を著しく向上させる,最先端パラメータチューニングアルゴリズムの導入について詳述する。
  論文  参考訳（メタデータ） (2024-01-11T15:02:15Z)
• Online Network Source Optimization with Graph-Kernel MAB [62.6067511147939]
  大規模ネットワークにおける最適なソース配置をオンラインで学習するためのグラフカーネルマルチアームバンディットアルゴリズムであるGrab-UCBを提案する。 適応グラフ辞書モデルを用いて,ネットワークプロセスを記述する。 我々は、ネットワークパラメータに依存する性能保証を導出し、シーケンシャルな意思決定戦略の学習曲線にさらに影響を及ぼす。
  論文  参考訳（メタデータ） (2023-07-07T15:03:42Z)
• Improved Algorithms for Neural Active Learning [74.89097665112621]
  非パラメトリックストリーミング設定のためのニューラルネットワーク(NN)ベースの能動学習アルゴリズムの理論的および経験的性能を改善する。 本研究では,SOTA(State-of-the-art (State-the-art)) 関連研究で使用されるものよりも,アクティブラーニングに適する人口減少を最小化することにより,2つの後悔の指標を導入する。
  論文  参考訳（メタデータ） (2022-10-02T05:03:38Z)
• Sample-Efficient, Exploration-Based Policy Optimisation for Routing Problems [2.6782615615913348]
  本稿では,エントロピーに基づく新しい強化学習手法を提案する。 さらに、我々は、期待したリターンを最大化する、政治以外の強化学習手法を設計する。 我々のモデルは様々な経路問題に一般化可能であることを示す。
  論文  参考訳（メタデータ） (2022-05-31T09:51:48Z)
• Reinforcement Learning for Branch-and-Bound Optimisation using Retrospective Trajectories [72.15369769265398]
  機械学習は分岐のための有望なパラダイムとして登場した。 分岐のための単純かつ効果的なRLアプローチであるレトロ分岐を提案する。 我々は現在最先端のRL分岐アルゴリズムを3～5倍に上回り、500の制約と1000の変数を持つMILP上での最高のILメソッドの性能の20%以内である。
  論文  参考訳（メタデータ） (2022-05-28T06:08:07Z)
• Meta Learning Black-Box Population-Based Optimizers [0.0]
  人口ベースのブラックボックス一般化を推論するメタラーニングの利用を提案する。 メタロス関数は,学習アルゴリズムが検索動作を変更することを促進し,新たなコンテキストに容易に適合できることを示す。
  論文  参考訳（メタデータ） (2021-03-05T08:13:25Z)
• Reinforcement Learning for Variable Selection in a Branch and Bound Algorithm [0.10499611180329801]
  現実世界のインスタンスのパターンを活用して、与えられた問題に最適化された新しいブランチ戦略をスクラッチから学習します。 本稿では,この課題に特化して設計された新しい強化学習手法であるFMSTSを提案する。
  論文  参考訳（メタデータ） (2020-05-20T13:15:48Z)

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

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