論文の概要: Solving the QAP by Two-Stage Graph Pointer Networks and Reinforcement Learning
- arxiv url: http://arxiv.org/abs/2404.00539v1
- Date: Sun, 31 Mar 2024 03:01:56 GMT
- ステータス: 処理完了
- システム内更新日: 2024-04-04 03:10:31.572675
- Title: Solving the QAP by Two-Stage Graph Pointer Networks and Reinforcement Learning
- Title（参考訳）: 2段階グラフポインタネットワークによるQAPの解法と強化学習
- Authors: Satoko Iida, Ryota Yasudo,
- Abstract要約: 二次割当問題 (QAP) は、ここ数年研究されてきた実用的な最適化問題である。
QAPを解くための2段階グラフポインタネットワーク(GPN)と呼ばれる深層強化学習モデル。
2段階GPNは、ユークリッド旅行セールスマン問題(TSP)のために提案されたGPNに依存している。
- 参考スコア（独自算出の注目度）: 0.22099217573031676
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Quadratic Assignment Problem (QAP) is a practical combinatorial optimization problems that has been studied for several years. Since it is NP-hard, solving large problem instances of QAP is challenging. Although heuristics can find semi-optimal solutions, the execution time significantly increases as the problem size increases. Recently, solving combinatorial optimization problems by deep learning has been attracting attention as a faster solver than heuristics. Even with deep learning, however, solving large QAP is still challenging. In this paper, we propose the deep reinforcement learning model called the two-stage graph pointer network (GPN) for solving QAP. Two-stage GPN relies on GPN, which has been proposed for Euclidean Traveling Salesman Problem (TSP). First, we extend GPN for general TSP, and then we add new algorithms to that model for solving QAP. Our experimental results show that our two-stage GPN provides semi-optimal solutions for benchmark problem instances from TSPlib and QAPLIB.
- Abstract（参考訳）: 二次割当問題 (QAP) は、ここ数年研究されてきた実用的な組合せ最適化問題である。
NPハードであるため、QAPの大きな問題を解くことは困難である。
ヒューリスティックスは準最適解を見つけることができるが、問題のサイズが大きくなるにつれて実行時間が大幅に増加する。
近年,ディープラーニングによる組合せ最適化問題の解法が,ヒューリスティックスよりも高速な解法として注目されている。
しかし、ディープラーニングであっても、大規模なQAPの解決は依然として難しい。
本稿では,QAPを解くための2段階グラフポインタネットワーク(GPN)と呼ばれる深層強化学習モデルを提案する。
2段階GPNは、ユークリッド旅行セールスマン問題 (TSP) のために提案されたGPNに依存している。
まず,一般TSPのためのGPNを拡張し,そのモデルに新たなアルゴリズムを加えてQAPを解く。
実験の結果,TSPlibとQAPLIBのベンチマーク問題インスタンスに対して,2段階GPNが半最適解であることがわかった。
関連論文リスト
- Sum-of-Squares inspired Quantum Metaheuristic for Polynomial Optimization with the Hadamard Test and Approximate Amplitude Constraints [76.53316706600717]
最近提案された量子アルゴリズムarXiv:2206.14999は半定値プログラミング(SDP)に基づいている
SDPにインスパイアされた量子アルゴリズムを2乗和に一般化する。
この結果から,本アルゴリズムは大きな問題に適応し,最もよく知られた古典学に近似することが示唆された。
論文 参考訳（メタデータ） (2024-08-14T19:04:13Z) - Towards Less Greedy Quantum Coalition Structure Generation in Induced Subgraph Games [3.6021182997326022]
100%再生可能エネルギーへの移行には、マイクログレードと呼ばれる有能なプロシューマーのサブセットに分割するなど、エネルギーネットワークを管理する新しい技術が必要である。
最適な方法で行うことは、誘導サブグラフゲームにおける結合構造生成問題に抽象化できるため、難しい最適化問題である。
本研究は,GCS-Qをソリューション品質の面で上回りうるかどうかを検証し,より控えめなQAベースのアプローチを提案する。
論文 参考訳（メタデータ） (2024-08-08T10:54:56Z) - Learning Solution-Aware Transformers for Efficiently Solving Quadratic Assignment Problem [27.33966993065248]
本研究は,2次割当て問題(QAP)を効率的に解くための学習ベースソリューションに焦点を当てる。
QAPに関する現在の研究は、限られた規模と非効率性に悩まされている。
そこで本研究では,QAPの学習と改善のカテゴリにおける第1の解法を提案する。
論文 参考訳（メタデータ） (2024-06-14T10:15:03Z) - Optimizing Solution-Samplers for Combinatorial Problems: The Landscape
of Policy-Gradient Methods [52.0617030129699]
本稿では,DeepMatching NetworksとReinforcement Learningメソッドの有効性を解析するための新しい理論フレームワークを提案する。
我々の主な貢献は、Max- and Min-Cut、Max-$k$-Bipartite-Bi、Maximum-Weight-Bipartite-Bi、Traveing Salesman Problemを含む幅広い問題である。
本分析の副産物として,バニラ降下による新たな正則化プロセスを導入し,失効する段階的な問題に対処し,悪い静止点から逃れる上で有効であることを示す理論的および実験的証拠を提供する。
論文 参考訳（メタデータ） (2023-10-08T23:39:38Z) - iPINNs: Incremental learning for Physics-informed neural networks [66.4795381419701]
物理インフォームドニューラルネットワーク(PINN)は、最近偏微分方程式(PDE)を解く強力なツールとなっている。
本稿では,新しいタスクのパラメータを追加せずに連続的に複数のタスクを学習できるインクリメンタルPINNを提案する。
提案手法は,PDEごとに個別のサブネットワークを作成し,従来のサブネットワークと重なり合うようにすることで,最も単純なPDEから複数のPDEを学習する。
論文 参考訳（メタデータ） (2023-04-10T20:19:20Z) - On the Global Convergence of Fitted Q-Iteration with Two-layer Neural
Network Parametrization [33.12181620473604]
本稿では,2層型ReLUニューラルネットワークを用いたQ-Iterationについて検討し,アルゴリズムの複雑さの保証を求める。
このアプローチは,オーダー最適化である $tildemathcalO (1/epsilon2)$ のサンプル複雑性を実現する。
論文 参考訳（メタデータ） (2022-11-14T19:00:24Z) - Learning to Detect Critical Nodes in Sparse Graphs via Feature Importance Awareness [53.351863569314794]
クリティカルノード問題(CNP)は、削除が残余ネットワークのペア接続性を最大に低下させるネットワークから臨界ノードの集合を見つけることを目的としている。
本研究は,ノード表現のための特徴重要度対応グラフアテンションネットワークを提案する。
ダブルディープQネットワークと組み合わせて、初めてCNPを解くエンドツーエンドのアルゴリズムを作成する。
論文 参考訳（メタデータ） (2021-12-03T14:23:05Z) - Learning the Markov Decision Process in the Sparse Gaussian Elimination [0.0]
スパースガウス除去のための学習に基づくアプローチを提案する。
スパースソルバの主モジュールに対するQ-Learningアルゴリズムを提案する。
論文 参考訳（メタデータ） (2021-09-30T08:56:39Z) - Accelerating Quadratic Optimization with Reinforcement Learning [39.64039435793601]
強化学習は、収束を加速するためにパラメータをチューニングするためのポリシーを学ぶことができるかを示す。
我々のポリシーであるRLQPは最先端のQPソルバを最大3倍に上回ります。
RLQPは、異なるアプリケーションから異なる次元と構造を持つ以前に見られなかった問題に驚くほどよく一般化する。
論文 参考訳（メタデータ） (2021-07-22T17:59:10Z) - Q-Match: Iterative Shape Matching via Quantum Annealing [64.74942589569596]
形状対応を見つけることは、NP-hard quadratic assignment problem (QAP)として定式化できる。
本稿では,アルファ拡大アルゴリズムに触発されたQAPの反復量子法Q-Matchを提案する。
Q-Match は、実世界の問題にスケールできるような長文対応のサブセットにおいて、反復的に形状マッチング問題に適用できる。
論文 参考訳（メタデータ） (2021-05-06T17:59:38Z) - Deep Policy Dynamic Programming for Vehicle Routing Problems [89.96386273895985]
本稿では,学習ニューラルの強みと動的プログラミングアルゴリズムの強みを組み合わせた深層ポリシー動的プログラミング(d pdp)を提案する。
D PDPは、例の解からエッジを予測するために訓練されたディープニューラルネットワークから派生したポリシーを使用して、DP状態空間を優先し、制限する。
本研究では,旅行セールスマン問題 (TSP) と車両ルーティング問題 (VRP) の枠組みを評価し,ニューラルネットワークが(制限された)DPアルゴリズムの性能を向上させることを示す。
論文 参考訳（メタデータ） (2021-02-23T15:33:57Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。