論文の概要: Geometric Deep Reinforcement Learning for Dynamic DAG Scheduling
- arxiv url: http://arxiv.org/abs/2011.04333v1
- Date: Mon, 9 Nov 2020 10:57:21 GMT
- ステータス: 処理完了
- システム内更新日: 2022-09-28 01:08:35.565751
- Title: Geometric Deep Reinforcement Learning for Dynamic DAG Scheduling
- Title（参考訳）: 動的DAGスケジューリングのための幾何学的深部強化学習
- Authors: Nathan Grinsztajn, Olivier Beaumont, Emmanuel Jeannot, Philippe Preux
- Abstract要約: 本稿では,現実的なスケジューリング問題を解決するための強化学習手法を提案する。
高性能コンピューティングコミュニティにおいて一般的に実行されるアルゴリズムであるColesky Factorizationに適用する。
我々のアルゴリズムは,アクター・クリティカル・アルゴリズム (A2C) と組み合わせてグラフニューラルネットワークを用いて,問題の適応表現をオンザフライで構築する。
- 参考スコア（独自算出の注目度）: 8.14784681248878
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: In practice, it is quite common to face combinatorial optimization problems
which contain uncertainty along with non-determinism and dynamicity. These
three properties call for appropriate algorithms; reinforcement learning (RL)
is dealing with them in a very natural way. Today, despite some efforts, most
real-life combinatorial optimization problems remain out of the reach of
reinforcement learning algorithms.
In this paper, we propose a reinforcement learning approach to solve a
realistic scheduling problem, and apply it to an algorithm commonly executed in
the high performance computing community, the Cholesky factorization. On the
contrary to static scheduling, where tasks are assigned to processors in a
predetermined ordering before the beginning of the parallel execution, our
method is dynamic: task allocations and their execution ordering are decided at
runtime, based on the system state and unexpected events, which allows much
more flexibility. To do so, our algorithm uses graph neural networks in
combination with an actor-critic algorithm (A2C) to build an adaptive
representation of the problem on the fly.
We show that this approach is competitive with state-of-the-art heuristics
used in high-performance computing runtime systems. Moreover, our algorithm
does not require an explicit model of the environment, but we demonstrate that
extra knowledge can easily be incorporated and improves performance. We also
exhibit key properties provided by this RL approach, and study its transfer
abilities to other instances.
- Abstract（参考訳）: 実際、非決定性や動的性とともに不確実性を含む組合せ最適化問題に直面することは極めて一般的である。
これら3つの特性は適切なアルゴリズムを必要とし、強化学習(RL)はそれらを非常に自然な方法で処理している。
今日、いくつかの努力にもかかわらず、現実の組合せ最適化問題は強化学習アルゴリズムの範囲外である。
本稿では,現実的なスケジューリング問題を解くための強化学習手法を提案し,高性能コンピューティングコミュニティで一般的に実行されるアルゴリズムであるcholesky factorizationに適用する。
並列実行開始前に所定の順序でタスクをプロセッサに割り当てる静的スケジューリングとは対照的に、我々のメソッドは動的である:タスク割り当てとその実行順序は、システム状態と予期しないイベントに基づいて実行時に決定される。
そこで本アルゴリズムでは,グラフニューラルネットワークとアクタ-クリティックアルゴリズム(a2c)を組み合わせることで,問題の適応表現をオンザフライで構築する。
このアプローチは、高性能コンピューティングランタイムシステムで使用される最先端のヒューリスティックと競合することを示す。
さらに,このアルゴリズムは環境の明示的なモデルを必要としないが,追加知識が組み込まれやすく,性能が向上することを示す。
また、このRLアプローチで提供される重要な特性を示し、他のインスタンスへの転送能力について検討する。
関連論文リスト
- Reinforcement Learning for Adaptive Resource Scheduling in Complex System Environments [8.315191578007857]
そこで本研究では,Q-ラーニングに基づく新しいコンピュータシステムの性能最適化と適応型ワークロード管理スケジューリングアルゴリズムを提案する。
対照的に、強化学習アルゴリズムであるQラーニングは、システムの状態変化から継続的に学習し、動的スケジューリングとリソース最適化を可能にする。
この研究は、将来の大規模システムにおけるAI駆動適応スケジューリングの統合の基礎を提供し、システムのパフォーマンスを高め、運用コストを削減し、持続可能なエネルギー消費をサポートするスケーラブルでインテリジェントなソリューションを提供する。
論文 参考訳（メタデータ） (2024-11-08T05:58:09Z) - Offline reinforcement learning for job-shop scheduling problems [1.3927943269211593]
本稿では,複雑な制約を伴う最適化問題に対して,新しいオフラインRL法を提案する。
我々のアプローチは、エッジ属性のアクションを符号化し、専門家ソリューションの模倣と期待される報酬のバランスをとる。
本手法がジョブショップスケジューリングおよびフレキシブルジョブショップスケジューリングベンチマークに与える影響を実証する。
論文 参考訳（メタデータ） (2024-10-21T07:33:42Z) - Multi-Objective Optimization Using Adaptive Distributed Reinforcement Learning [8.471466670802815]
本稿では,多目的・マルチエージェント強化学習(MARL)アルゴリズムを提案する。
我々はエッジクラウドコンピューティングを用いたITS環境でアルゴリズムをテストする。
また,本アルゴリズムは,モジュール化および非同期オンライントレーニング手法により,様々な実用上の問題にも対処する。
論文 参考訳（メタデータ） (2024-03-13T18:05:16Z) - Accelerating Exact Combinatorial Optimization via RL-based
Initialization -- A Case Study in Scheduling [1.3053649021965603]
本研究の目的は、最適化問題に対処する機械学習(ML)を用いた革新的なアプローチを開発することである。
1) 粗粒スケジューラとしての解法, 2) 解緩和, 3) ILPによる正確な解法の3つのステップを含む新しい2段階のRL-to-ILPスケジューリングフレームワークを導入する。
提案フレームワークは, 正確なスケジューリング手法と比較して, 最大128ドルの高速化を実現しつつ, 同一のスケジューリング性能を示す。
論文 参考訳（メタデータ） (2023-08-19T15:52:43Z) - Improved Algorithms for Neural Active Learning [74.89097665112621]
非パラメトリックストリーミング設定のためのニューラルネットワーク(NN)ベースの能動学習アルゴリズムの理論的および経験的性能を改善する。
本研究では,SOTA(State-of-the-art (State-the-art)) 関連研究で使用されるものよりも,アクティブラーニングに適する人口減少を最小化することにより,2つの後悔の指標を導入する。
論文 参考訳（メタデータ） (2022-10-02T05:03:38Z) - Stabilizing Q-learning with Linear Architectures for Provably Efficient
Learning [53.17258888552998]
本研究では,線形関数近似を用いた基本的な$Q$-learningプロトコルの探索変種を提案する。
このアルゴリズムの性能は,新しい近似誤差というより寛容な概念の下で,非常に優雅に低下することを示す。
論文 参考訳（メタデータ） (2022-06-01T23:26:51Z) - Accelerated Policy Learning with Parallel Differentiable Simulation [59.665651562534755]
微分可能シミュレータと新しいポリシー学習アルゴリズム(SHAC)を提案する。
本アルゴリズムは,スムーズな批判機能により局所最小化の問題を軽減する。
現状のRLと微分可能なシミュレーションベースアルゴリズムと比較して,サンプル効率と壁面時間を大幅に改善した。
論文 参考訳（メタデータ） (2022-04-14T17:46:26Z) - SOLO: Search Online, Learn Offline for Combinatorial Optimization
Problems [4.777801093677586]
我々は,機械スケジューリングやルーティング,割当てといった実世界のアプリケーションで問題を研究する。
RL(Reinforcement Learning)とプランニングを組み合わせた手法を提案する。
この方法は、オフラインでも、オンラインでも、問題のコンポーネントが事前に分かっておらず、むしろ意思決定プロセス中に現れるような、問題の変種にも等しく適用することができる。
論文 参考訳（メタデータ） (2021-04-04T17:12:24Z) - A Two-stage Framework and Reinforcement Learning-based Optimization
Algorithms for Complex Scheduling Problems [54.61091936472494]
本稿では、強化学習(RL)と従来の運用研究(OR)アルゴリズムを組み合わせた2段階のフレームワークを開発する。
スケジューリング問題は,有限マルコフ決定過程 (MDP) と混合整数計画過程 (mixed-integer programming process) の2段階で解決される。
その結果,本アルゴリズムは,アジャイルな地球観測衛星スケジューリング問題に対して,安定かつ効率的に十分なスケジューリング計画を得ることができた。
論文 参考訳（メタデータ） (2021-03-10T03:16:12Z) - Evolving Reinforcement Learning Algorithms [186.62294652057062]
メタラーニング強化学習アルゴリズムの手法を提案する。
学習アルゴリズムはドメインに依存しないため、トレーニング中に見えない新しい環境に一般化することができる。
従来の制御タスク、gridworld型タスク、atariゲームよりも優れた一般化性能を得る2つの学習アルゴリズムに注目した。
論文 参考訳（メタデータ） (2021-01-08T18:55:07Z) - Combining Deep Learning and Optimization for Security-Constrained
Optimal Power Flow [94.24763814458686]
セキュリティに制約のある最適電力フロー(SCOPF)は、電力システムの基本である。
SCOPF問題におけるAPRのモデル化は、複雑な大規模混合整数プログラムをもたらす。
本稿では,ディープラーニングとロバスト最適化を組み合わせた新しい手法を提案する。
論文 参考訳（メタデータ） (2020-07-14T12:38:21Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。