論文の概要: An Improved Reinforcement Learning Algorithm for Learning to Branch
- arxiv url: http://arxiv.org/abs/2201.06213v1
- Date: Mon, 17 Jan 2022 04:50:11 GMT
- ステータス: 処理完了
- システム内更新日: 2022-01-19 14:48:24.780533
- Title: An Improved Reinforcement Learning Algorithm for Learning to Branch
- Title(参考訳): 分岐学習のための強化学習アルゴリズムの改良
- Authors: Qingyu Qu, Xijun Li, Yunfan Zhou, Jia Zeng, Mingxuan Yuan, Jie Wang,
Jinhu Lv, Kexin Liu and Kun Mao
- Abstract要約: ブランチ・アンド・バウンド(B&B)は最適化の一般的な方法である。
本稿では,新しい強化学習に基づくB&Bアルゴリズムを提案する。
提案アルゴリズムの性能を3つの公開研究ベンチマークで評価した。
- 参考スコア(独自算出の注目度): 12.27934038849211
- License: http://creativecommons.org/licenses/by-nc-nd/4.0/
- Abstract: Most combinatorial optimization problems can be formulated as mixed integer
linear programming (MILP), in which branch-and-bound (B\&B) is a general and
widely used method. Recently, learning to branch has become a hot research
topic in the intersection of machine learning and combinatorial optimization.
In this paper, we propose a novel reinforcement learning-based B\&B algorithm.
Similar to offline reinforcement learning, we initially train on the
demonstration data to accelerate learning massively. With the improvement of
the training effect, the agent starts to interact with the environment with its
learned policy gradually. It is critical to improve the performance of the
algorithm by determining the mixing ratio between demonstration and
self-generated data. Thus, we propose a prioritized storage mechanism to
control this ratio automatically. In order to improve the robustness of the
training process, a superior network is additionally introduced based on Double
DQN, which always serves as a Q-network with competitive performance. We
evaluate the performance of the proposed algorithm over three public research
benchmarks and compare it against strong baselines, including three classical
heuristics and one state-of-the-art imitation learning-based branching
algorithm. The results show that the proposed algorithm achieves the best
performance among compared algorithms and possesses the potential to improve
B\&B algorithm performance continuously.
- Abstract(参考訳): ほとんどの組合せ最適化問題は混合整数線形計画 (milp) として定式化でき、分岐・境界 (b\&b) は一般に広く使われる手法である。
近年,機械学習と組合せ最適化の交差において,分岐学習がホットな研究トピックとなっている。
本稿では,新しい強化学習に基づくB\&Bアルゴリズムを提案する。
オフラインの強化学習と同様に、最初はデモデータをトレーニングして、学習を大規模に加速します。
トレーニング効果の改善により、エージェントは学習したポリシーで環境と徐々に対話し始める。
実演データと自己生成データの混合比を決定することにより,アルゴリズムの性能を向上させることが重要である。
そこで本研究では,この比率を自動的に制御する優先記憶機構を提案する。
トレーニングプロセスの堅牢性を改善するため、競争性能のQネットワークとして常に機能するDouble DQNに基づいて、優れたネットワークが導入された。
提案アルゴリズムを3つの公開研究ベンチマークで評価し,古典的ヒューリスティックスと1つの最先端の模倣学習に基づく分岐アルゴリズムを含む,強力なベースラインと比較した。
その結果,提案アルゴリズムは比較アルゴリズムの中で最高の性能を達成でき,b\&bアルゴリズムの性能を継続的に向上できる可能性が示唆された。
関連論文リスト
- Applying Incremental Learning in Binary-Addition-Tree Algorithm for Dynamic Binary-State Network Reliability [0.08158530638728499]
Binary-Addition-Treeアルゴリズム(BAT)は、ネットワークの信頼性と最適化問題を解決する強力な暗黙列挙法である。
漸進的な学習を導入することで、新たなデータやネットワークの変更に直面すると、BATが適応し、そのパフォーマンスを反復的に改善できるようになります。
論文 参考訳(メタデータ) (2024-09-24T04:13:03Z) - Stochastic Unrolled Federated Learning [85.6993263983062]
本稿では,UnRolled Federated Learning (SURF)を導入する。
提案手法は,この拡張における2つの課題,すなわち,非学習者へのデータセット全体の供給の必要性と,フェデレート学習の分散的性質に対処する。
論文 参考訳(メタデータ) (2023-05-24T17:26:22Z) - The Cascaded Forward Algorithm for Neural Network Training [61.06444586991505]
本稿では,ニューラルネットワークのための新しい学習フレームワークであるCascaded Forward(CaFo)アルゴリズムを提案する。
FFとは異なり、我々のフレームワークは各カスケードブロックのラベル分布を直接出力する。
我々のフレームワークでは、各ブロックは独立して訓練できるので、並列加速度システムに容易に展開できる。
論文 参考訳(メタデータ) (2023-03-17T02:01:11Z) - Improved Algorithms for Neural Active Learning [74.89097665112621]
非パラメトリックストリーミング設定のためのニューラルネットワーク(NN)ベースの能動学習アルゴリズムの理論的および経験的性能を改善する。
本研究では,SOTA(State-of-the-art (State-the-art)) 関連研究で使用されるものよりも,アクティブラーニングに適する人口減少を最小化することにより,2つの後悔の指標を導入する。
論文 参考訳(メタデータ) (2022-10-02T05:03:38Z) - On the Convergence of Distributed Stochastic Bilevel Optimization
Algorithms over a Network [55.56019538079826]
バイレベル最適化は、幅広い機械学習モデルに適用されている。
既存のアルゴリズムの多くは、分散データを扱うことができないように、シングルマシンの設定を制限している。
そこで我々は,勾配追跡通信機構と2つの異なる勾配に基づく分散二段階最適化アルゴリズムを開発した。
論文 参考訳(メタデータ) (2022-06-30T05:29:52Z) - Stabilizing Q-learning with Linear Architectures for Provably Efficient
Learning [53.17258888552998]
本研究では,線形関数近似を用いた基本的な$Q$-learningプロトコルの探索変種を提案する。
このアルゴリズムの性能は,新しい近似誤差というより寛容な概念の下で,非常に優雅に低下することを示す。
論文 参考訳(メタデータ) (2022-06-01T23:26:51Z) - Benchmarking Simulation-Based Inference [5.3898004059026325]
確率的モデリングの最近の進歩は、確率の数値的評価を必要としないシミュレーションに基づく推論アルゴリズムを多数もたらした。
推論タスクと適切なパフォーマンス指標を備えたベンチマークを,アルゴリズムの初期選択とともに提供する。
性能指標の選択は重要であり、最先端のアルゴリズムでさえ改善の余地があり、逐次推定によりサンプリング効率が向上することがわかった。
論文 参考訳(メタデータ) (2021-01-12T18:31:22Z) - Evolving Reinforcement Learning Algorithms [186.62294652057062]
メタラーニング強化学習アルゴリズムの手法を提案する。
学習アルゴリズムはドメインに依存しないため、トレーニング中に見えない新しい環境に一般化することができる。
従来の制御タスク、gridworld型タスク、atariゲームよりも優れた一般化性能を得る2つの学習アルゴリズムに注目した。
論文 参考訳(メタデータ) (2021-01-08T18:55:07Z) - Geometric Deep Reinforcement Learning for Dynamic DAG Scheduling [8.14784681248878]
本稿では,現実的なスケジューリング問題を解決するための強化学習手法を提案する。
高性能コンピューティングコミュニティにおいて一般的に実行されるアルゴリズムであるColesky Factorizationに適用する。
我々のアルゴリズムは,アクター・クリティカル・アルゴリズム (A2C) と組み合わせてグラフニューラルネットワークを用いて,問題の適応表現をオンザフライで構築する。
論文 参考訳(メタデータ) (2020-11-09T10:57:21Z) - Hyperspectral Unmixing Network Inspired by Unfolding an Optimization
Problem [2.4016406737205753]
ハイパースペクトル画像(HSI)アンミックスタスクは本質的に逆問題であり、最適化アルゴリズムによってよく解決される。
本稿では,U-ADMM-AENetとU-ADMM-BUNetという2つの新しいネットワークアーキテクチャを提案する。
本研究は,機械学習の文献において,展開された構造が対応する解釈を見つけることを示し,提案手法の有効性をさらに示すものである。
論文 参考訳(メタデータ) (2020-05-21T18:49:45Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。