論文の概要: 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解法よりも優れていることを示す。

関連論文リスト

• Multiobjective Vehicle Routing Optimization with Time Windows: A Hybrid Approach Using Deep Reinforcement Learning and NSGA-II [52.083337333478674]
  本稿では、時間窓を用いた多目的車両ルーティング問題(MOVRPTW)に対処するために、ウェイト・アウェア・ディープ・強化学習(WADRL)手法を提案する。 WADRLの結果を最適化するために非支配的ソート遺伝的アルゴリズム-II (NSGA-II) 法を用いる。
  論文  参考訳（メタデータ） (2024-07-18T02:46:06Z)
• Joint Demonstration and Preference Learning Improves Policy Alignment with Human Feedback [58.049113055986375]
  我々は、報酬モデルとポリシーをトレーニングするために、AIHF(Alignment with Integrated Human Feedback)と呼ばれる単一ステージアプローチを開発する。 提案した手法は、一般的なアライメントアルゴリズムに容易に還元し、活用できる、効率的なアルゴリズムの集合を認めている。 本研究では,LLMにおけるアライメント問題と,MuJoCoにおけるロボット制御問題を含む広範な実験により,提案手法の有効性を実証する。
  論文  参考訳（メタデータ） (2024-06-11T01:20:53Z)
• Flow of Reasoning:Training LLMs for Divergent Problem Solving with Minimal Examples [12.48027669682156]
  推論のフローは、最小限のデータで推論の品質と多様性を改善することを目的としています。 FoR は DAG 構造推論グラフ上のマルコフフローとして多段階 LLM 推論を定式化する。 実験によると、限られたトレーニング例で、FoRは多様な創造的で高品質なソリューションの発見を可能にする。
  論文  参考訳（メタデータ） (2024-06-09T07:06:58Z)
• Deep Reinforcement Learning Guided Improvement Heuristic for Job Shop Scheduling [30.45126420996238]
  本稿では,完全解の符号化にグラフ表現を用いる JSSP を解くための DRL 誘導型改良法を提案する。 本研究では,2つのモジュールからなるグラフニューラルネットワークに基づく表現スキームを設計し,改良プロセス中に遭遇したグラフ内の動的トポロジと異なるタイプのノードの情報を自動的に取得する。 古典的なベンチマーク実験により,本手法が学んだ改善方針は,最先端のDRL法よりも大きなマージンで優れていることが示された。
  論文  参考訳（メタデータ） (2022-11-20T10:20:13Z)
• 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)
• sKPNSGA-II: Knee point based MOEA with self-adaptive angle for Mission Planning Problems [2.191505742658975]
  いくつかの問題には、多くの非支配的な解をもたらす多くの目的がある。 本稿では,最も重要な解を得るために設計された新しいアルゴリズムを提案する。 このアルゴリズムは無人航空機(UAV)ミッション計画問題における実世界の応用に応用されている。
  論文  参考訳（メタデータ） (2020-02-20T17:07:08Z)

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

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