論文の概要: Learning What to Defer for Maximum Independent Sets
- arxiv url: http://arxiv.org/abs/2006.09607v2
- Date: Mon, 29 Jun 2020 06:17:07 GMT
- ステータス: 処理完了
- システム内更新日: 2022-11-19 19:35:36.759810
- Title: Learning What to Defer for Maximum Independent Sets
- Title(参考訳): 最大独立集合に何を定義するかを学ぶ
- Authors: Sungsoo Ahn, Younggyo Seo, Jinwoo Shin
- Abstract要約: 本稿では,各段階における解の要素的決定を学習することにより,エージェントが適応的に段階数を縮小あるいは拡張する,新たなDRL方式を提案する。
提案手法を最大独立集合(MIS)問題に適用し、現状のDRL方式よりも大幅に改善したことを示す。
- 参考スコア(独自算出の注目度): 84.00112106334655
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Designing efficient algorithms for combinatorial optimization appears
ubiquitously in various scientific fields. Recently, deep reinforcement
learning (DRL) frameworks have gained considerable attention as a new approach:
they can automate the design of a solver while relying less on sophisticated
domain knowledge of the target problem. However, the existing DRL solvers
determine the solution using a number of stages proportional to the number of
elements in the solution, which severely limits their applicability to
large-scale graphs. In this paper, we seek to resolve this issue by proposing a
novel DRL scheme, coined learning what to defer (LwD), where the agent
adaptively shrinks or stretch the number of stages by learning to distribute
the element-wise decisions of the solution at each stage. We apply the proposed
framework to the maximum independent set (MIS) problem, and demonstrate its
significant improvement over the current state-of-the-art DRL scheme. We also
show that LwD can outperform the conventional MIS solvers on large-scale graphs
having millions of vertices, under a limited time budget.
- Abstract(参考訳): 組合せ最適化のための効率的なアルゴリズムを設計することは、様々な科学分野においてユビキタスに現れる。
近年、深層強化学習(DRL)フレームワークが新たなアプローチとして注目されており、対象問題に関する高度なドメイン知識に頼らずに解決器の設計を自動化することができる。
しかし、既存のDRLソルバは解の要素数に比例する複数の段階を用いて解を決定するため、大規模グラフへの適用性が著しく制限される。
本稿では,各段階における解の要素的決定を学習によって適応的に縮小あるいは拡張する,新しいDRL方式(LwD)を提案することにより,この問題を解決することを目的とする。
提案手法を最大独立集合(MIS)問題に適用し、現状のDRL方式よりも大幅に改善したことを示す。
また、LwDは、数百万の頂点を持つ大規模グラフ上で、限られた時間予算で従来のMIS解法よりも優れていることを示す。
関連論文リスト
- SEGO: Sequential Subgoal Optimization for Mathematical Problem-Solving [64.38649623473626]
大規模言語モデル(LLM)は人工知能の大幅な進歩を導いた。
数学的問題を解く能力を高めるために,textbfSEquential subtextbfGoal textbfOptimization (SEGO) という新しいフレームワークを提案する。
論文 参考訳(メタデータ) (2023-10-19T17:56:40Z) - Deep Reinforcement Learning Guided Improvement Heuristic for Job Shop
Scheduling [30.45126420996238]
本稿では,完全解の符号化にグラフ表現を用いる JSSP を解くための DRL 誘導型改良法を提案する。
本研究では,2つのモジュールからなるグラフニューラルネットワークに基づく表現スキームを設計し,改良プロセス中に遭遇したグラフ内の動的トポロジと異なるタイプのノードの情報を自動的に取得する。
古典的なベンチマーク実験により,本手法が学んだ改善方針は,最先端のDRL法よりも大きなマージンで優れていることが示された。
論文 参考訳(メタデータ) (2022-11-20T10:20:13Z) - Multi-Resource Allocation for On-Device Distributed Federated Learning
Systems [79.02994855744848]
本研究は,デバイス上の分散フェデレーション学習(FL)システムにおいて,レイテンシとエネルギー消費の重み付け和を最小化する分散マルチリソース割り当て方式を提案する。
システム内の各モバイルデバイスは、指定された領域内でモデルトレーニングプロセスを実行し、それぞれパラメータの導出とアップロードを行うための計算と通信資源を割り当てる。
論文 参考訳(メタデータ) (2022-11-01T14:16:05Z) - DIMES: A Differentiable Meta Solver for Combinatorial Optimization
Problems [41.57773395100222]
深部強化学習(DRL)モデルはNP-hard Combinatorial Optimization問題を解決する上で有望な結果を示している。
本稿では,DIMESという新しいアプローチを提案することによって,大規模最適化におけるスケーラビリティの課題に対処する。
コストのかかる自己回帰的復号法や離散解の反復的洗練に苦しむ従来のDRL法とは異なり、DIMESは候補解の基底分布をパラメータ化するためのコンパクトな連続空間を導入する。
DIMESは、トラベリングセールスマン問題や最大独立セット問題のための大規模なベンチマークデータセットにおいて、最近のDRLベースの手法よりも優れていることを示す。
論文 参考訳(メタデータ) (2022-10-08T23:24:37Z) - Towards Deployment-Efficient Reinforcement Learning: Lower Bound and
Optimality [141.89413461337324]
展開効率は、強化学習(RL)の多くの実世界の応用にとって重要な基準である
本稿では,「制約付き最適化」の観点から,デプロイ効率の高いRL(DE-RL)の理論的定式化を提案する。
論文 参考訳(メタデータ) (2022-02-14T01:31:46Z) - Reinforcement Learning for Adaptive Mesh Refinement [63.7867809197671]
マルコフ決定過程としてのAMRの新規な定式化を提案し,シミュレーションから直接改良政策を訓練するために深部強化学習を適用した。
これらのポリシーアーキテクチャのモデルサイズはメッシュサイズに依存しないため、任意に大きく複雑なシミュレーションにスケールします。
論文 参考訳(メタデータ) (2021-03-01T22:55:48Z) - Reversible Action Design for Combinatorial Optimization with
Reinforcement Learning [35.50454156611722]
強化学習(rl)は、これらの問題に取り組むための新しいフレームワークとして最近登場した。
最先端の実証性能を示すだけでなく、様々な種類のCOPに一般化する汎用RLフレームワークを提案します。
論文 参考訳(メタデータ) (2021-02-14T18:05:42Z) - Combining Deep Learning and Optimization for Security-Constrained
Optimal Power Flow [94.24763814458686]
セキュリティに制約のある最適電力フロー(SCOPF)は、電力システムの基本である。
SCOPF問題におけるAPRのモデル化は、複雑な大規模混合整数プログラムをもたらす。
本稿では,ディープラーニングとロバスト最適化を組み合わせた新しい手法を提案する。
論文 参考訳(メタデータ) (2020-07-14T12:38:21Z) - A General Large Neighborhood Search Framework for Solving Integer Linear
Programs [46.62993477453986]
我々は整数プログラムの解法に重点を置いており、我々のアプローチは大規模近傍探索(SLN)パラダイムに根ざしている。
我々のLSSフレームワークは、Gurobiのような最先端の商用解法と比較して、大幅に性能が向上することを示した。
論文 参考訳(メタデータ) (2020-03-29T23:08:14Z) - sKPNSGA-II: Knee point based MOEA with self-adaptive angle for Mission
Planning Problems [2.191505742658975]
いくつかの問題には、多くの非支配的な解をもたらす多くの目的がある。
本稿では,最も重要な解を得るために設計された新しいアルゴリズムを提案する。
このアルゴリズムは無人航空機(UAV)ミッション計画問題における実世界の応用に応用されている。
論文 参考訳(メタデータ) (2020-02-20T17:07:08Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。