論文の概要: Swap-based Deep Reinforcement Learning for Facility Location Problems in Networks

• arxiv url: http://arxiv.org/abs/2312.15658v1
• Date: Mon, 25 Dec 2023 09:00:25 GMT
• ステータス: 処理完了
• システム内更新日: 2023-12-27 17:03:21.766988
• Title: Swap-based Deep Reinforcement Learning for Facility Location Problems in Networks
• Title（参考訳）: ネットワークにおける施設配置問題に対するスワップベース深層強化学習
• Authors: Wenxuan Guo, Yanyan Xu, Yaohui Jin
• Abstract要約: グラフ上の施設位置問題は、実世界ではユビキタスであり、非常に重要である。 p-median問題とグラフ上の施設配置問題に対処するスワップベースフレームワークを提案する。 また,複雑なグラフ構造に対する意識を示す新しい強化学習モデルも導入する。
• 参考スコア（独自算出の注目度）: 11.613708854129037
• License: http://creativecommons.org/licenses/by-nc-sa/4.0/
• Abstract: Facility location problems on graphs are ubiquitous in real world and hold significant importance, yet their resolution is often impeded by NP-hardness. Recently, machine learning methods have been proposed to tackle such classical problems, but they are limited to the myopic constructive pattern and only consider the problems in Euclidean space. To overcome these limitations, we propose a general swap-based framework that addresses the p-median problem and the facility relocation problem on graphs and a novel reinforcement learning model demonstrating a keen awareness of complex graph structures. Striking a harmonious balance between solution quality and running time, our method surpasses handcrafted heuristics on intricate graph datasets. Additionally, we introduce a graph generation process to simulate real-world urban road networks with demand, facilitating the construction of large datasets for the classic problem. For the initialization of the locations of facilities, we introduce a physics-inspired strategy for the p-median problem, reaching more stable solutions than the random strategy. The proposed pipeline coupling the classic swap-based method with deep reinforcement learning marks a significant step forward in addressing the practical challenges associated with facility location on graphs.
• Abstract（参考訳）: グラフ上の施設位置問題は実世界でユビキタスであり、重要な意味を持つが、その解決はしばしばNPハードネスによって妨げられる。 近年,このような古典的問題に対処するための機械学習手法が提案されているが,これは筋電図構築パターンに限られており,ユークリッド空間における問題のみを考えることができる。 これらの制約を克服するために, p-median問題とグラフ上の施設配置問題に対処する汎用スワップベースフレームワークと, 複雑なグラフ構造を意識した新しい強化学習モデルを提案する。 提案手法は,ソリューションの品質と実行時間のバランスを両立させ,複雑なグラフデータセットにおける手作りのヒューリスティックを上回っている。 さらに,従来の問題に対する大規模データセット構築を容易にし,オンデマンドで現実の都市道路網をシミュレートするグラフ生成プロセスを導入する。 施設の配置を初期化するために, p-median問題に対する物理に触発された戦略を導入し, ランダム戦略よりもより安定な解に到達した。 従来のスワップ法と深層強化学習を結合したパイプラインは,グラフ上の施設配置に関わる現実的な課題に対処する上で,大きな一歩となる。

関連論文リスト

• CHARME: A chain-based reinforcement learning approach for the minor embedding problem [16.24890195949869]
  本稿では,CHARME という名前の小さな埋め込み問題に対処するために,強化学習(RL)技術を利用した新しい手法を提案する。 CHARMEには、ポリシーモデリングのためのグラフニューラルネットワーク(GNN)アーキテクチャ、ソリューションの有効性を保証する状態遷移アルゴリズム、効果的なトレーニングのための順序探索戦略の3つの重要なコンポーネントが含まれている。 詳細では、CHARME は Minorminer や ATOM のような高速な埋め込み法に比べて優れた解が得られる。
  論文  参考訳（メタデータ） (2024-06-11T10:12:10Z)
• Decision-focused Graph Neural Networks for Combinatorial Optimization [62.34623670845006]
  最適化問題に取り組むための新たな戦略は、従来のアルゴリズムに代わるグラフニューラルネットワーク(GNN)の採用である。 GNNや従来のアルゴリズムソルバがCOの領域で人気が高まっているにもかかわらず、それらの統合利用とエンドツーエンドフレームワークにおけるそれらの相関について限定的な研究がなされている。 我々は、GNNを利用してCO問題に補助的なサポートで対処する決定に焦点を当てたフレームワークを導入する。
  論文  参考訳（メタデータ） (2024-06-05T22:52:27Z)
• GASE: Graph Attention Sampling with Edges Fusion for Solving Vehicle Routing Problems [6.084414764415137]
  車両のルーティング問題を解決するためにEdges Fusionフレームワークを用いた適応型グラフ注意サンプリングを提案する。 提案手法は,既存の手法を2.08%-6.23%上回り,より強力な一般化能力を示す。
  論文  参考訳（メタデータ） (2024-05-21T03:33:07Z)
• Symmetry-preserving graph attention network to solve routing problems at multiple resolutions [1.9304772860080408]
  問題解決のために,最初の完全同変モデルとトレーニングを導入する。 入力グラフのマルチスケール構造を捉えることが不可欠である。 本稿では,Equi Graph Attention Network (mEGAT) アーキテクチャと組み合わせたマルチレゾリューション方式を提案する。
  論文  参考訳（メタデータ） (2023-10-24T06:22:20Z)
• Neural combinatorial optimization beyond the TSP: Existing architectures under-represent graph structure [9.673093148930876]
  我々は、最近のニューラルネットワークが実際に重要なグラフ問題にどのように適用できるのか、その分析を行う。 距離問題の構造的表現を増大させることは、多目的自律型問題解決者を学ぶという、まだ曖昧な目標に向けた有望なステップであることを示す。
  論文  参考訳（メタデータ） (2022-01-03T14:14:28Z)
• Physics informed neural networks for continuum micromechanics [68.8204255655161]
  近年,応用数学や工学における多種多様な問題に対して,物理情報ニューラルネットワークの適用が成功している。 グローバルな近似のため、物理情報ニューラルネットワークは、最適化によって局所的な効果と強い非線形解を表示するのに困難である。 実世界の$mu$CT-Scansから得られた不均一構造における非線形応力, 変位, エネルギー場を, 正確に解くことができる。
  論文  参考訳（メタデータ） (2021-10-14T14:05:19Z)
• On the Difficulty of Generalizing Reinforcement Learning Framework for Combinatorial Optimization [6.935838847004389]
  現実の応用とグラフ上の組合せ最適化問題(COP)は、コンピュータサイエンスにおける標準的な課題である。 このアプローチの基本原理は、ノードのローカル情報とグラフ構造化データの両方を符号化するグラフニューラルネットワーク(GNN)をデプロイすることである。 我々は,クラウド上のセキュリティ対応電話機のクローン割り当てを古典的二次代入問題 (QAP) として,深層RLモデルが他の難題の解法に一般的に適用可能であるか否かを調査する。
  論文  参考訳（メタデータ） (2021-08-08T19:12:04Z)
• Decentralized Personalized Federated Learning for Min-Max Problems [79.61785798152529]
  本稿では,より広い範囲の最適化問題を含むサドル点問題に対して,PFLを初めて検討した。 この問題に対処するための新しいアルゴリズムを提案し、滑らかな(強く)凸-(強く)凹点問題を理論的に解析する。 両線形問題に対する数値実験と, 対向雑音を有するニューラルネットワークは, 提案手法の有効性を実証する。
  論文  参考訳（メタデータ） (2021-06-14T10:36:25Z)
• Spatial-spectral Hyperspectral Image Classification via Multiple Random Anchor Graphs Ensemble Learning [88.60285937702304]
  本稿では,複数のランダムアンカーグラフアンサンブル学習(RAGE)を用いた空間スペクトルHSI分類手法を提案する。 まず、各選択されたバンドのより記述的な特徴を抽出し、局所的な構造と領域の微妙な変化を保存するローカルバイナリパターンを採用する。 次に,アンカーグラフの構成に適応隣接代入を導入し,計算複雑性を低減した。
  論文  参考訳（メタデータ） (2021-03-25T09:31:41Z)
• Differentiable Causal Discovery from Interventional Data [141.41931444927184]
  本稿では、介入データを活用可能なニューラルネットワークに基づく理論的基盤化手法を提案する。 提案手法は,様々な環境下での美術品の状態と良好に比較できることを示す。
  論文  参考訳（メタデータ） (2020-07-03T15:19:17Z)
• Local Propagation in Constraint-based Neural Network [77.37829055999238]
  ニューラルネットワークアーキテクチャの制約に基づく表現について検討する。 本稿では,いわゆるアーキテクチャ制約を満たすのに適した簡単な最適化手法について検討する。
  論文  参考訳（メタデータ） (2020-02-18T16:47:38Z)

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

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