論文の概要: A Two-stage Framework and Reinforcement Learning-based Optimization
Algorithms for Complex Scheduling Problems
- arxiv url: http://arxiv.org/abs/2103.05847v1
- Date: Wed, 10 Mar 2021 03:16:12 GMT
- ステータス: 処理完了
- システム内更新日: 2021-03-11 14:57:39.417003
- Title: A Two-stage Framework and Reinforcement Learning-based Optimization
Algorithms for Complex Scheduling Problems
- Title（参考訳）: 複素スケジューリング問題に対する2段階フレームワークと強化学習に基づく最適化アルゴリズム
- Authors: Yongming He, Guohua Wu, Yingwu Chen and Witold Pedrycz
- Abstract要約: 本稿では、強化学習(RL)と従来の運用研究(OR)アルゴリズムを組み合わせた2段階のフレームワークを開発する。
スケジューリング問題は,有限マルコフ決定過程 (MDP) と混合整数計画過程 (mixed-integer programming process) の2段階で解決される。
その結果,本アルゴリズムは,アジャイルな地球観測衛星スケジューリング問題に対して,安定かつ効率的に十分なスケジューリング計画を得ることができた。
- 参考スコア（独自算出の注目度）: 54.61091936472494
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: There hardly exists a general solver that is efficient for scheduling
problems due to their diversity and complexity. In this study, we develop a
two-stage framework, in which reinforcement learning (RL) and traditional
operations research (OR) algorithms are combined together to efficiently deal
with complex scheduling problems. The scheduling problem is solved in two
stages, including a finite Markov decision process (MDP) and a mixed-integer
programming process, respectively. This offers a novel and general paradigm
that combines RL with OR approaches to solving scheduling problems, which
leverages the respective strengths of RL and OR: The MDP narrows down the
search space of the original problem through an RL method, while the
mixed-integer programming process is settled by an OR algorithm. These two
stages are performed iteratively and interactively until the termination
criterion has been met. Under this idea, two implementation versions of the
combination methods of RL and OR are put forward. The agile Earth observation
satellite scheduling problem is selected as an example to demonstrate the
effectiveness of the proposed scheduling framework and methods. The convergence
and generalization capability of the methods are verified by the performance of
training scenarios, while the efficiency and accuracy are tested in 50
untrained scenarios. The results show that the proposed algorithms could stably
and efficiently obtain satisfactory scheduling schemes for agile Earth
observation satellite scheduling problems. In addition, it can be found that
RL-based optimization algorithms have stronger scalability than non-learning
algorithms. This work reveals the advantage of combining reinforcement learning
methods with heuristic methods or mathematical programming methods for solving
complex combinatorial optimization problems.
- Abstract（参考訳）: 多様性と複雑性のため、スケジューリングに効率的である一般的な解法はほとんど存在しない。
本研究では、強化学習(RL)と従来の運用研究(OR)のアルゴリズムを組み合わせ、複雑なスケジューリング問題に効率的に対処する2段階のフレームワークを開発する。
スケジューリング問題は,有限マルコフ決定過程 (MDP) と混合整数計画過程 (mixed-integer programming process) の2段階で解決される。
MDPはRLメソッドを通じて元の問題の検索空間を狭くし、混合整数プログラミングプロセスはORアルゴリズムによって解決される。
これら2つの段階は、終了基準が満たされるまで反復的にインタラクティブに行われる。
この考えの下では、RLとORの組み合わせ方法の2つの実装バージョンが提案される。
アジャイル地球観測衛星スケジューリング問題は、提案されたスケジューリングフレームワークと方法の有効性を示す例として選択される。
手法の収束と一般化能力は訓練シナリオの性能によって検証され、効率と精度は50の未訓練シナリオで検証される。
その結果,提案手法は,アジャイルな地球観測衛星スケジューリング問題に対して,安定かつ効率的に十分なスケジューリング計画を得ることができた。
さらに、RLに基づく最適化アルゴリズムは、非学習アルゴリズムよりもスケーラビリティが強いことが分かる。
本研究は,強化学習法とヒューリスティック法,数理計画法を組み合わせた複合組合せ最適化問題を解く利点を明らかにした。
関連論文リスト
- Stabilized Proximal-Point Methods for Federated Optimization [20.30761752651984]
非加速アルゴリズムの通信複雑性は、分散近位点アルゴリズムであるDANEによって達成される。
ハイブリッド投影近点法に着想を得て,新しい分散アルゴリズムS-DANEを提案する。
S-DANEは、S-DANEとして良好な局所計算効率を保ちながら、通信の複雑さを最もよく表すことを示す。
論文 参考訳（メタデータ） (2024-07-09T17:56:29Z) - 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) - Accelerating Cutting-Plane Algorithms via Reinforcement Learning
Surrogates [49.84541884653309]
凸離散最適化問題に対する現在の標準的なアプローチは、カットプレーンアルゴリズムを使うことである。
多くの汎用カット生成アルゴリズムが存在するにもかかわらず、大規模な離散最適化問題は、難易度に悩まされ続けている。
そこで本研究では,強化学習による切削平面アルゴリズムの高速化手法を提案する。
論文 参考訳（メタデータ） (2023-07-17T20:11:56Z) - Deep reinforcement learning applied to an assembly sequence planning
problem with user preferences [1.0558951653323283]
本稿では,アセンブリシーケンス計画問題におけるDRL手法の実装に対するアプローチを提案する。
提案手法では,RL環境のパラメトリックな動作を導入し,トレーニング時間とサンプル効率を改善する。
その結果,人的相互作用を伴う組立シーケンス計画問題への深層強化学習の適用の可能性が示唆された。
論文 参考訳（メタデータ） (2023-04-13T14:25:15Z) - On the Convergence of Distributed Stochastic Bilevel Optimization
Algorithms over a Network [55.56019538079826]
バイレベル最適化は、幅広い機械学習モデルに適用されている。
既存のアルゴリズムの多くは、分散データを扱うことができないように、シングルマシンの設定を制限している。
そこで我々は,勾配追跡通信機構と2つの異なる勾配に基づく分散二段階最適化アルゴリズムを開発した。
論文 参考訳（メタデータ） (2022-06-30T05:29:52Z) - An Overview and Experimental Study of Learning-based Optimization
Algorithms for Vehicle Routing Problem [49.04543375851723]
車両ルーティング問題(VRP)は典型的な離散最適化問題である。
多くの研究は、VRPを解決するための学習に基づく最適化アルゴリズムについて検討している。
本稿では、最近のこの分野の進歩を概観し、関連するアプローチをエンドツーエンドアプローチとステップバイステップアプローチに分割する。
論文 参考訳（メタデータ） (2021-07-15T02:13:03Z) - Towards Optimally Efficient Tree Search with Deep Learning [76.64632985696237]
本稿では,線形モデルから信号整数を推定する古典整数最小二乗問題について検討する。
問題はNPハードであり、信号処理、バイオインフォマティクス、通信、機械学習といった様々な応用でしばしば発生する。
本稿では, 深いニューラルネットワークを用いて, 単純化されたメモリバウンドA*アルゴリズムの最適推定を推定し, HATSアルゴリズムを提案する。
論文 参考訳（メタデータ） (2021-01-07T08:00:02Z) - Parallel Scheduling Self-attention Mechanism: Generalization and
Optimization [0.76146285961466]
本稿では,SAT(Satisfiability check)ソルバによって解決された小インスタンスの最適スケジューリングから導いた一般スケジューリングアルゴリズムを提案する。
余剰計算をスキップする際のさらなる最適化戦略も推進され、元の計算の約25%と50%の削減が達成される。
提案アルゴリズムは、入力ベクトルの数がアーキテクチャで利用可能な演算ユニットの数に割り切れる限り、問題のサイズにかかわらず適用可能である。
論文 参考訳（メタデータ） (2020-12-02T12:04:16Z) - Geometric Deep Reinforcement Learning for Dynamic DAG Scheduling [8.14784681248878]
本稿では,現実的なスケジューリング問題を解決するための強化学習手法を提案する。
高性能コンピューティングコミュニティにおいて一般的に実行されるアルゴリズムであるColesky Factorizationに適用する。
我々のアルゴリズムは,アクター・クリティカル・アルゴリズム (A2C) と組み合わせてグラフニューラルネットワークを用いて,問題の適応表現をオンザフライで構築する。
論文 参考訳（メタデータ） (2020-11-09T10:57:21Z) - Combining Deep Learning and Optimization for Security-Constrained
Optimal Power Flow [94.24763814458686]
セキュリティに制約のある最適電力フロー(SCOPF)は、電力システムの基本である。
SCOPF問題におけるAPRのモデル化は、複雑な大規模混合整数プログラムをもたらす。
本稿では,ディープラーニングとロバスト最適化を組み合わせた新しい手法を提案する。
論文 参考訳（メタデータ） (2020-07-14T12:38:21Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。