論文の概要: On the Difficulty of Generalizing Reinforcement Learning Framework for Combinatorial Optimization

• arxiv url: http://arxiv.org/abs/2108.03713v1
• Date: Sun, 8 Aug 2021 19:12:04 GMT
• ステータス: 処理完了
• システム内更新日: 2021-08-10 15:12:49.690713
• Title: On the Difficulty of Generalizing Reinforcement Learning Framework for Combinatorial Optimization
• Title（参考訳）: 組合せ最適化のための強化学習フレームワークの一般化の難しさについて
• Authors: Mostafa Pashazadeh, Kui Wu
• Abstract要約: 現実の応用とグラフ上の組合せ最適化問題(COP)は、コンピュータサイエンスにおける標準的な課題である。 このアプローチの基本原理は、ノードのローカル情報とグラフ構造化データの両方を符号化するグラフニューラルネットワーク(GNN)をデプロイすることである。 我々は,クラウド上のセキュリティ対応電話機のクローン割り当てを古典的二次代入問題 (QAP) として,深層RLモデルが他の難題の解法に一般的に適用可能であるか否かを調査する。
• 参考スコア（独自算出の注目度）: 6.935838847004389
• License: http://creativecommons.org/licenses/by-nc-sa/4.0/
• Abstract: Combinatorial optimization problems (COPs) on the graph with real-life applications are canonical challenges in Computer Science. The difficulty of finding quality labels for problem instances holds back leveraging supervised learning across combinatorial problems. Reinforcement learning (RL) algorithms have recently been adopted to solve this challenge automatically. The underlying principle of this approach is to deploy a graph neural network (GNN) for encoding both the local information of the nodes and the graph-structured data in order to capture the current state of the environment. Then, it is followed by the actor to learn the problem-specific heuristics on its own and make an informed decision at each state for finally reaching a good solution. Recent studies on this subject mainly focus on a family of combinatorial problems on the graph, such as the travel salesman problem, where the proposed model aims to find an ordering of vertices that optimizes a given objective function. We use the security-aware phone clone allocation in the cloud as a classical quadratic assignment problem (QAP) to investigate whether or not deep RL-based model is generally applicable to solve other classes of such hard problems. Extensive empirical evaluation shows that existing RL-based model may not generalize to QAP.
• Abstract（参考訳）: 現実の応用とグラフ上の組合せ最適化問題(COP)は、コンピュータサイエンスにおける標準的な課題である。 問題インスタンスの品質ラベルを見つけることの難しさは、組合せ問題にまたがる教師あり学習を活用することを妨げる。 強化学習(RL)アルゴリズムはこの課題を自動解決するために最近採用されている。 このアプローチの基本原理は、環境の現在の状態をキャプチャするために、ノードのローカル情報とグラフ構造化データの両方を符号化するグラフニューラルネットワーク(GNN)をデプロイすることである。 次に、アクターは、問題固有のヒューリスティックを自分自身で学習し、最終的に良い解に到達するために各州で情報的決定を行う。 近年の研究では、トラベルセールスマン問題(英語版)のようなグラフ上の組合せ問題群に焦点をあて、与えられた目的関数を最適化する頂点の順序を求めることを目的としている。 我々は,クラウド上のセキュリティ対応電話機のクローン割り当てを古典的二次代入問題 (QAP) として,深層RLモデルが他の難題の解法に一般的に適用可能であるか否かを調査する。 大規模な経験的評価は、既存のRLモデルがQAPに一般化されないことを示している。

関連論文リスト

• Decision-focused Graph Neural Networks for Combinatorial Optimization [62.34623670845006]
  最適化問題に取り組むための新たな戦略は、従来のアルゴリズムに代わるグラフニューラルネットワーク(GNN)の採用である。 GNNや従来のアルゴリズムソルバがCOの領域で人気が高まっているにもかかわらず、それらの統合利用とエンドツーエンドフレームワークにおけるそれらの相関について限定的な研究がなされている。 我々は、GNNを利用してCO問題に補助的なサポートで対処する決定に焦点を当てたフレームワークを導入する。
  論文  参考訳（メタデータ） (2024-06-05T22:52:27Z)
• A General Framework for Learning from Weak Supervision [93.89870459388185]
  本稿では、新しいアルゴリズムを用いて、弱監督(GLWS)から学習するための一般的な枠組みを紹介する。 GLWSの中心は期待最大化(EM)の定式化であり、様々な弱い監督源を順応的に収容している。 また,EM計算要求を大幅に単純化する高度なアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2024-02-02T21:48:50Z)
• Graph Q-Learning for Combinatorial Optimization [44.8086492019594]
  グラフニューラルネットワーク(GNN)は,グラフデータの予測と推論の問題を解くのに有効であることが示されている。 本稿では,GNNを組合せ最適化問題に適用できることを示す。
  論文  参考訳（メタデータ） (2024-01-11T01:15:28Z)
• 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)
• Solving the vehicle routing problem with deep reinforcement learning [0.0]
  本稿では,NP-Hard 問題のクラスに属する有名な問題である Vehicle Routing Problem (VRP) に対する RL の適用について述べる。 第2フェーズでは、アクターと批評家の背後にあるニューラルアーキテクチャが確立され、畳み込みニューラルネットワークに基づいたニューラルアーキテクチャを採用することが選択された。 広範囲なインスタンスで行った実験では、アルゴリズムが優れた一般化能力を持ち、短時間で良い解に達することが示されている。
  論文  参考訳（メタデータ） (2022-07-30T12:34:26Z)
• A Differentiable Approach to Combinatorial Optimization using Dataless Neural Networks [20.170140039052455]
  我々は、ソリューションを生成するニューラルネットワークのトレーニングにデータを必要としないという、根本的に異なるアプローチを提案する。 特に、最適化問題をニューラルネットワークに還元し、データレストレーニングスキームを用いて、それらのパラメータが関心の構造をもたらすように、ネットワークのパラメータを洗練する。
  論文  参考訳（メタデータ） (2022-03-15T19:21:31Z)
• Learning to Detect Critical Nodes in Sparse Graphs via Feature Importance Awareness [53.351863569314794]
  クリティカルノード問題(CNP)は、削除が残余ネットワークのペア接続性を最大に低下させるネットワークから臨界ノードの集合を見つけることを目的としている。 本研究は,ノード表現のための特徴重要度対応グラフアテンションネットワークを提案する。 ダブルディープQネットワークと組み合わせて、初めてCNPを解くエンドツーエンドのアルゴリズムを作成する。
  論文  参考訳（メタデータ） (2021-12-03T14:23:05Z)
• A Bi-Level Framework for Learning to Solve Combinatorial Optimization on Graphs [91.07247251502564]
  本稿では,2つの世界の長所を結合するハイブリッドな手法を提案する。この手法では,グラフを最適化する上層学習手法とバイレベルフレームワークを開発する。 このような二段階のアプローチは、元のハードCOでの学習を単純化し、モデルキャパシティの需要を効果的に軽減することができる。
  論文  参考訳（メタデータ） (2021-06-09T09:18:18Z)
• Reversible Action Design for Combinatorial Optimization with Reinforcement Learning [35.50454156611722]
  強化学習(rl)は、これらの問題に取り組むための新しいフレームワークとして最近登場した。 最先端の実証性能を示すだけでなく、様々な種類のCOPに一般化する汎用RLフレームワークを提案します。
  論文  参考訳（メタデータ） (2021-02-14T18:05:42Z)
• Graph Ordering: Towards the Optimal by Learning [69.72656588714155]
  グラフ表現学習は、ノード分類、予測、コミュニティ検出など、多くのグラフベースのアプリケーションで顕著な成功を収めている。 しかし,グラフ圧縮やエッジ分割などのグラフアプリケーションでは,グラフ表現学習タスクに還元することは極めて困難である。 本稿では,このようなアプリケーションの背後にあるグラフ順序付け問題に対して,新しい学習手法を用いて対処することを提案する。
  論文  参考訳（メタデータ） (2020-01-18T09:14:16Z)

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

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