論文の概要: 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つのカテゴリについて性能評価を行い,最先端の機械学習やヒューリスティックスに基づく手法と比較して,高い性能を示す。
関連論文リスト
- Unleashing the Potential of Large Language Models as Prompt Optimizers:
An Analogical Analysis with Gradient-based Model Optimizers [115.2038169433773]
本稿では,大規模言語モデル(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) - Efficient Reinforcemen Learning via Decoupling Exploration and
Utilization [9.67983570115056]
本研究は,OPARL(Optimistic and Pessimistic Actor Reinforcement Learning)の新たな枠組みを提案する。
OPARLは、探索に特化した楽観的なアクターと、利用に焦点を当てた悲観的なアクターという、ユニークなデュアルアクターアプローチを採用している。
実験と理論的研究は、OPARLが応用と探索のためのエージェントの能力を改善することを実証している。
論文 参考訳(メタデータ) (2023-12-26T09:03:23Z) - Online Network Source Optimization with Graph-Kernel MAB [62.6067511147939]
大規模ネットワークにおける最適なソース配置をオンラインで学習するためのグラフカーネルマルチアームバンディットアルゴリズムであるGrab-UCBを提案する。
適応グラフ辞書モデルを用いて,ネットワークプロセスを記述する。
我々は、ネットワークパラメータに依存する性能保証を導出し、シーケンシャルな意思決定戦略の学習曲線にさらに影響を及ぼす。
論文 参考訳(メタデータ) (2023-07-07T15:03:42Z) - On Equivalent Optimization of Machine Learning Methods [1.9573380763700712]
学習速度,バッチサイズ,層幅,データセット,アクティベーション関数の選択が,トレーニング中のネットワークパラメータの等価あるいは等価な進化につながる場合の一般的な特徴を示す。
その結果, バッチサイズ比, 層幅, データセットの性質(手書きと合成) およびアクティベーション関数が共役性に影響を及ぼすことがわかった。
論文 参考訳(メタデータ) (2023-02-17T22:15:20Z) - 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) - Efficient Model-Based Multi-Agent Mean-Field Reinforcement Learning [89.31889875864599]
マルチエージェントシステムにおける学習に有効なモデルベース強化学習アルゴリズムを提案する。
我々の理論的な貢献は、MFCのモデルベース強化学習における最初の一般的な後悔の限界である。
コア最適化問題の実用的なパラメトリゼーションを提供する。
論文 参考訳(メタデータ) (2021-07-08T18:01:02Z) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。