論文の概要: SOLO: Search Online, Learn Offline for Combinatorial Optimization
Problems
- arxiv url: http://arxiv.org/abs/2104.01646v2
- Date: Thu, 8 Apr 2021 12:48:09 GMT
- ステータス: 処理完了
- システム内更新日: 2021-04-09 11:48:09.159774
- Title: SOLO: Search Online, Learn Offline for Combinatorial Optimization
Problems
- Title（参考訳）: SOLO: オンライン検索, 組合せ最適化問題のオフライン学習
- Authors: Joel Oren, Chana Ross, Maksym Lefarov, Felix Richter, Ayal Taitler,
Zohar Feldman, Christian Daniel, Dotan Di Castro
- Abstract要約: 我々は,機械スケジューリングやルーティング,割当てといった実世界のアプリケーションで問題を研究する。
RL(Reinforcement Learning)とプランニングを組み合わせた手法を提案する。
この方法は、オフラインでも、オンラインでも、問題のコンポーネントが事前に分かっておらず、むしろ意思決定プロセス中に現れるような、問題の変種にも等しく適用することができる。
- 参考スコア（独自算出の注目度）: 4.777801093677586
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: We study combinatorial problems with real world applications such as machine
scheduling, routing, and assignment. We propose a method that combines
Reinforcement Learning (RL) and planning. This method can equally be applied to
both the offline, as well as online, variants of the combinatorial problem, in
which the problem components (e.g., jobs in scheduling problems) are not known
in advance, but rather arrive during the decision-making process. Our solution
is quite generic, scalable, and leverages distributional knowledge of the
problem parameters. We frame the solution process as an MDP, and take a Deep
Q-Learning approach wherein states are represented as graphs, thereby allowing
our trained policies to deal with arbitrary changes in a principled manner.
Though learned policies work well in expectation, small deviations can have
substantial negative effects in combinatorial settings. We mitigate these
drawbacks by employing our graph-convolutional policies as non-optimal
heuristics in a compatible search algorithm, Monte Carlo Tree Search, to
significantly improve overall performance. We demonstrate our method on two
problems: Machine Scheduling and Capacitated Vehicle Routing. We show that our
method outperforms custom-tailored mathematical solvers, state of the art
learning-based algorithms, and common heuristics, both in computation time and
performance.
- Abstract（参考訳）: 本研究では,マシンスケジューリング,ルーティング,割り当てといった実世界のアプリケーションにおける組合せ問題について検討する。
強化学習(RL)と計画を組み合わせる手法を提案する。
この方法は、オフラインでもオンラインでも、問題コンポーネント(例えばスケジューリング問題におけるジョブ)が事前に知られておらず、意思決定プロセス中に到着するコンビネータ問題でも同じように適用することができる。
私たちのソリューションは非常に汎用的でスケーラブルで、問題パラメータの分散知識を活用しています。
我々は、解法プロセスをMDPとして構成し、状態がグラフとして表現されるディープQラーニングアプローチを採用し、訓練されたポリシーが原則化された方法で任意の変更に対処できるようにする。
学習されたポリシーは期待通りに機能するが、小さな偏差は組合せ設定においてかなりの負の効果を持つ。
これらの欠点を、互換性のある探索アルゴリズムであるモンテカルロ木探索において、グラフ畳み込みポリシーを非最適ヒューリスティックとして利用することで軽減し、全体的な性能を大幅に向上させる。
提案手法は, マシンスケジューリングとキャパシタ付き車両ルーティングの2つの問題について実証する。
本手法は, 計算時間と性能の両方において, 独自に調整した数学解法, 美術学習に基づくアルゴリズム, および共通ヒューリスティックスよりも優れていることを示す。
関連論文リスト
- Offline reinforcement learning for job-shop scheduling problems [1.3927943269211593]
本稿では,複雑な制約を伴う最適化問題に対して,新しいオフラインRL法を提案する。
我々のアプローチは、エッジ属性のアクションを符号化し、専門家ソリューションの模倣と期待される報酬のバランスをとる。
本手法がジョブショップスケジューリングおよびフレキシブルジョブショップスケジューリングベンチマークに与える影響を実証する。
論文 参考訳（メタデータ） (2024-10-21T07:33:42Z) - 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) - Learning to Optimize Permutation Flow Shop Scheduling via Graph-based
Imitation Learning [70.65666982566655]
置換フローショップスケジューリング(PFSS)は製造業で広く使われている。
我々は,より安定かつ正確に収束を加速する専門家主導の模倣学習を通じてモデルを訓練することを提案する。
我々のモデルのネットワークパラメータはわずか37%に減少し、エキスパートソリューションに対する我々のモデルの解のギャップは平均6.8%から1.3%に減少する。
論文 参考訳（メタデータ） (2022-10-31T09:46:26Z) - Deep Reinforcement Learning for Exact Combinatorial Optimization:
Learning to Branch [13.024115985194932]
本稿では、強化学習(RL)パラダイムを用いた最適化において、データラベリングと推論の問題を解決するための新しいアプローチを提案する。
我々は模倣学習を用いてRLエージェントをブートストラップし、PPO(Proximal Policy)を使用してグローバルな最適なアクションを探索する。
論文 参考訳（メタデータ） (2022-06-14T16:35:58Z) - Solving the capacitated vehicle routing problem with timing windows
using rollouts and MAX-SAT [4.873362301533824]
車両ルーティングはNPハード最適化問題のよく知られたクラスである。
最近の強化学習の取り組みは有望な代替手段である。
本稿では,強化学習,政策展開,満足度を組み合わせたハイブリッドアプローチを提案する。
論文 参考訳（メタデータ） (2022-06-14T06:27:09Z) - Ranking Cost: Building An Efficient and Scalable Circuit Routing Planner
with Evolution-Based Optimization [49.207538634692916]
そこで我々は、効率よくトレーニング可能なルータを形成するための新しい回路ルーティングアルゴリズム、Randing Costを提案する。
提案手法では,A*ルータが適切な経路を見つけるのに役立つコストマップと呼ばれる新しい変数群を導入する。
我々のアルゴリズムはエンドツーエンドで訓練されており、人工データや人間の実演は一切使用しない。
論文 参考訳（メタデータ） (2021-10-08T07:22:45Z) - A Bi-Level Framework for Learning to Solve Combinatorial Optimization on
Graphs [91.07247251502564]
本稿では,2つの世界の長所を結合するハイブリッドな手法を提案する。この手法では,グラフを最適化する上層学習手法とバイレベルフレームワークを開発する。
このような二段階のアプローチは、元のハードCOでの学習を単純化し、モデルキャパシティの需要を効果的に軽減することができる。
論文 参考訳（メタデータ） (2021-06-09T09:18:18Z) - 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) - Geometric Deep Reinforcement Learning for Dynamic DAG Scheduling [8.14784681248878]
本稿では,現実的なスケジューリング問題を解決するための強化学習手法を提案する。
高性能コンピューティングコミュニティにおいて一般的に実行されるアルゴリズムであるColesky Factorizationに適用する。
我々のアルゴリズムは,アクター・クリティカル・アルゴリズム (A2C) と組み合わせてグラフニューラルネットワークを用いて,問題の適応表現をオンザフライで構築する。
論文 参考訳（メタデータ） (2020-11-09T10:57:21Z) - Learning with Differentiable Perturbed Optimizers [54.351317101356614]
本稿では,操作を微分可能で局所的に一定ではない操作に変換する手法を提案する。
提案手法は摂動に依拠し,既存の解法とともに容易に利用することができる。
本稿では,この枠組みが,構造化予測において発達した損失の族とどのように結びつくかを示し,学習課題におけるそれらの使用に関する理論的保証を与える。
論文 参考訳（メタデータ） (2020-02-20T11:11:32Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。