論文の概要: Attention-based Reinforcement Learning for Combinatorial Optimization: Application to Job Shop Scheduling Problem
- arxiv url: http://arxiv.org/abs/2401.16580v2
- Date: Mon, 18 Mar 2024 17:57:22 GMT
- ステータス: 処理完了
- システム内更新日: 2024-03-20 23:31:36.375664
- Title: Attention-based Reinforcement Learning for Combinatorial Optimization: Application to Job Shop Scheduling Problem
- Title（参考訳）: 組合せ最適化のための注意に基づく強化学習:ジョブショップスケジューリング問題への応用
- Authors: Jaejin Lee, Seho Kee, Mani Janakiram, George Runger,
- Abstract要約: 本研究では,ジョブショップスケジューリング問題に特化して設計された,革新的な注意力に基づく強化学習手法を提案する。
この研究の鍵となる発見は、提案手法で訓練を受けた学習者が、初期訓練セットに含まれない大規模問題に再利用できることである。
- 参考スコア（独自算出の注目度）: 2.024210754085351
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Job shop scheduling problems represent a significant and complex facet of combinatorial optimization problems, which have traditionally been addressed through either exact or approximate solution methodologies. However, the practical application of these solutions is often challenged due to the complexity of real-world problems. Even when utilizing an approximate solution approach, the time required to identify a near-optimal solution can be prohibitively extensive, and the solutions derived are generally not applicable to new problems. This study proposes an innovative attention-based reinforcement learning method specifically designed for the category of job shop scheduling problems. This method integrates a policy gradient reinforcement learning approach with a modified transformer architecture. A key finding of this research is the ability of our trained learners within the proposed method to be repurposed for larger-scale problems that were not part of the initial training set. Furthermore, empirical evidence demonstrates that our approach surpasses the results of recent studies and outperforms commonly implemented heuristic rules. This suggests that our method offers a promising avenue for future research and practical application in the field of job shop scheduling problems.
- Abstract（参考訳）: ジョブショップスケジューリング問題は組合せ最適化問題の重要かつ複雑な側面を表しており、これは伝統的に正確な解法または近似解法によって解決されてきた。
しかし、現実の問題の複雑さのために、これらのソリューションの実践的な応用がしばしば挑戦される。
近似解法を利用する場合であっても、近似解を特定するのに必要な時間は禁じられ、導出された解は一般に新しい問題に適用できない。
本研究では,ジョブショップスケジューリング問題に特化して設計された,革新的な注意力に基づく強化学習手法を提案する。
この方法は、ポリシー勾配強化学習アプローチと、改良されたトランスフォーマーアーキテクチャを統合する。
この研究の鍵となる発見は、提案手法で訓練を受けた学習者が、初期訓練セットに含まれない大規模問題に再利用できることである。
さらに,本手法が最近の研究結果を上回り,一般に実施されているヒューリスティックルールを上回ることを示す実証的証拠が得られた。
このことから,本手法は,求人スケジューリング問題における今後の研究・実践の道筋として有望なものであることが示唆された。
関連論文リスト
- Learning Joint Models of Prediction and Optimization [56.04498536842065]
Predict-Then-Thenフレームワークは、機械学習モデルを使用して、最適化問題の未知のパラメータを、解決前の機能から予測する。
本稿では,共同予測モデルを用いて観測可能特徴から最適解を直接学習する手法を提案する。
論文 参考訳（メタデータ） (2024-09-07T19:52:14Z) - Combinatorial Optimization with Policy Adaptation using Latent Space Search [44.12073954093942]
本稿では,複雑なNPハード問題を解くために,パフォーマンスアルゴリズムを設計するための新しいアプローチを提案する。
我々の検索戦略は11の標準ベンチマークタスクにおける最先端のアプローチよりも優れていることを示す。
論文 参考訳（メタデータ） (2023-11-13T12:24:54Z) - Thought Propagation: An Analogical Approach to Complex Reasoning with Large Language Models [62.96551299003463]
大規模言語モデルの複雑な推論能力を高めるために,textbftextitThought Propagation (TP)を提案する。
TP はまず LLM に対して,入力問題に関連する類似問題の集合を提案し,解決するよう促す。
TPは、類似問題の結果を再利用して、新しいソリューションを直接生成したり、スクラッチから得られた初期ソリューションを修正するための知識集約的な実行プランを導出する。
論文 参考訳（メタデータ） (2023-10-06T01:40:09Z) - Reinforcement Learning Approach for Multi-Agent Flexible Scheduling
Problems [0.0]
本研究では,スケジューリング問題に対する強化学習手法を提案する。
特に,本研究では,ジョブショップスケジューリング問題に対して,検索スペースを削減したオープンAIジム環境を提供する。
論文 参考訳（メタデータ） (2022-10-07T16:31:01Z) - Solving the capacitated vehicle routing problem with timing windows
using rollouts and MAX-SAT [4.873362301533824]
車両ルーティングはNPハード最適化問題のよく知られたクラスである。
最近の強化学習の取り組みは有望な代替手段である。
本稿では,強化学習,政策展開,満足度を組み合わせたハイブリッドアプローチを提案する。
論文 参考訳（メタデータ） (2022-06-14T06:27:09Z) - Efficient lifting of symmetry breaking constraints for complex
combinatorial problems [9.156939957189502]
この作業は、Answer Set Programmingのためのモデルベースのアプローチの学習フレームワークと実装を拡張します。
Inductive Logic Programming System ILASPに新たなコンフリクト解析アルゴリズムを組み込む。
論文 参考訳（メタデータ） (2022-05-14T20:42:13Z) - Learning Proximal Operators to Discover Multiple Optima [66.98045013486794]
非家族問題における近位演算子を学習するためのエンドツーエンド手法を提案する。
本手法は,弱い目的と穏やかな条件下では,世界規模で収束することを示す。
論文 参考訳（メタデータ） (2022-01-28T05:53:28Z) - Discovering Diverse Solutions in Deep Reinforcement Learning [84.45686627019408]
強化学習アルゴリズムは通常、特定のタスクの単一のソリューションを学ぶことに限定される。
連続的あるいは離散的な低次元潜在変数に条件付きポリシーを訓練することにより、無限に多くの解を学習できるRL法を提案する。
論文 参考訳（メタデータ） (2021-03-12T04:54:31Z) - 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) - Importance Weighted Policy Learning and Adaptation [89.46467771037054]
政治外学習の最近の進歩の上に構築された,概念的にシンプルで,汎用的で,モジュール的な補完的アプローチについて検討する。
このフレームワークは確率論的推論文学のアイデアにインスパイアされ、堅牢な非政治学習と事前の行動を組み合わせる。
提案手法は,メタ強化学習ベースラインと比較して,ホールドアウトタスクにおける競合適応性能を実現し,複雑なスパース・リワードシナリオにスケールすることができる。
論文 参考訳（メタデータ） (2020-09-10T14:16:58Z) - Reinforcement Learning for Combinatorial Optimization: A Survey [12.323976053967066]
最適化問題を解決する多くの伝統的なアルゴリズムは、解決を逐次構築する手工芸品を使用する。
強化学習(Reinforcement Learning, RL)は、エージェントを監督的または自己監督的な方法で訓練することにより、これらの検索を自動化する優れた代替手段を提案する。
論文 参考訳（メタデータ） (2020-03-07T16:19:45Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。