論文の概要: Solving the Quadratic Assignment Problem using Deep Reinforcement Learning

• arxiv url: http://arxiv.org/abs/2310.01604v1
• Date: Mon, 2 Oct 2023 19:55:15 GMT
• ステータス: 処理完了
• システム内更新日: 2023-10-04 18:56:00.990176
• Title: Solving the Quadratic Assignment Problem using Deep Reinforcement Learning
• Title（参考訳）: 深層強化学習を用いた二次割当て問題の解法
• Authors: Puneet S. Bagga, Arthur Delarue
• Abstract要約: Quadratic Assignment Problem (QAP) はNP-hard問題であり、特に解決が困難であることが証明されている。 30以上のサイズのQAPインスタンスを正確に解決する方法は知られていない。 深部強化学習を用いたQAPのオリジナルのクープマン・ベックマン定式化の解法を提案する。
• 参考スコア（独自算出の注目度）: 0.8158530638728501
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: The Quadratic Assignment Problem (QAP) is an NP-hard problem which has proven particularly challenging to solve: unlike other combinatorial problems like the traveling salesman problem (TSP), which can be solved to optimality for instances with hundreds or even thousands of locations using advanced integer programming techniques, no methods are known to exactly solve QAP instances of size greater than 30. Solving the QAP is nevertheless important because of its many critical applications, such as electronic wiring design and facility layout selection. We propose a method to solve the original Koopmans-Beckman formulation of the QAP using deep reinforcement learning. Our approach relies on a novel double pointer network, which alternates between selecting a location in which to place the next facility and a facility to place in the previous location. We train our model using A2C on a large dataset of synthetic instances, producing solutions with no instance-specific retraining necessary. Out of sample, our solutions are on average within 7.5% of a high-quality local search baseline, and even outperform it on 1.2% of instances.
• Abstract（参考訳）: 旅行セールスマン問題(TSP)のような他の組合せ問題とは異なり、高度な整数プログラミング技術を用いて数百から数千の場所を持つインスタンスに対して最適に解決できるが、30以上のサイズのQAPインスタンスを正確に解く方法は知られていない。 QAPの解決は、電子配線設計や設備配置選択など、多くの重要な応用のために重要である。 深部強化学習を用いたQAPのオリジナルのクープマン・ベックマン定式化の解法を提案する。 提案手法は,次の施設を配置する場所と,前の場所に設置する施設とを交互に選択する,新しい二重ポインタネットワークに依存する。 合成インスタンスの大規模なデータセット上でA2Cを使用してモデルをトレーニングし、インスタンス固有の再トレーニングを必要としないソリューションを生成します。 サンプルからすると、私たちのソリューションは、高品質なローカル検索ベースラインの7.5%以内で、インスタンスの1.2%よりも優れています。

関連論文リスト

• Learning Multiple Initial Solutions to Optimization Problems [52.9380464408756]
  厳密なランタイム制約の下で、同様の最適化問題を順次解決することは、多くのアプリケーションにとって不可欠である。 本稿では,問題インスタンスを定義するパラメータが与えられた初期解を多種多様に予測する学習を提案する。 提案手法は,すべての評価設定において有意かつ一貫した改善を実現し,必要な初期解の数に応じて効率よくスケールできることを実証した。
  論文  参考訳（メタデータ） (2024-11-04T15:17:19Z)
• Learning Solution-Aware Transformers for Efficiently Solving Quadratic Assignment Problem [27.33966993065248]
  本研究は,2次割当て問題(QAP)を効率的に解くための学習ベースソリューションに焦点を当てる。 QAPに関する現在の研究は、限られた規模と非効率性に悩まされている。 そこで本研究では,QAPの学習と改善のカテゴリにおける第1の解法を提案する。
  論文  参考訳（メタデータ） (2024-06-14T10:15:03Z)
• Solving the QAP by Two-Stage Graph Pointer Networks and Reinforcement Learning [0.22099217573031676]
  二次割当問題 (QAP) は、ここ数年研究されてきた実用的な最適化問題である。 QAPを解くための2段階グラフポインタネットワーク(GPN)と呼ばれる深層強化学習モデル。 2段階GPNは、ユークリッド旅行セールスマン問題(TSP)のために提案されたGPNに依存している。
  論文  参考訳（メタデータ） (2024-03-31T03:01:56Z)
• 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)
• Globally solving the Gromov-Wasserstein problem for point clouds in low dimensional Euclidean spaces [5.534626267734822]
  本稿では,低次元空間における2つの点間のGromov-Wasserstein問題を計算するための枠組みを提案する。 これは、AIと機械学習における一般的な問題である2つの構成または形状の類似性を定量化するために使用できる。
  論文  参考訳（メタデータ） (2023-07-18T08:20:56Z)
• A Novel Approach for Auto-Formulation of Optimization Problems [66.94228200699997]
  Natural Language for Optimization (NL4Opt) NeurIPS 2022コンペティションでは、最適化ソルバのアクセシビリティとユーザビリティの改善に重点を置いている。 本稿では,チームのソリューションについて述べる。 提案手法は,サブタスク1のF1スコアとサブタスク2の0.867の精度を達成し,それぞれ第4位,第3位を獲得した。
  論文  参考訳（メタデータ） (2023-02-09T13:57:06Z)
• 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 Sensor Placement Problems In Real Water Distribution Networks Using Adiabatic Quantum Computation [9.2810884211586]
  本稿では,水分配ネットワーク(WDN)に圧力センサを正しく配置する問題を最適化問題として定式化する。 センサ配置問題に対するQUBOとIsingの定式化について概説する。 本稿では,オープンソースのPythonライブラリであるPyQUBOを用いて,ハミルトニアンを最小化することで,この問題を解決するための詳細な手順を提案する。
  論文  参考訳（メタデータ） (2021-08-06T07:31:38Z)
• Larger Sparse Quadratic Assignment Problem Optimization Using Quantum Annealing and a Bit-Flip Heuristic Algorithm [0.4125187280299248]
  線形制約は、量子アニールで表現できる問題のサイズを減らす。 オーゼキ法により得られた解に対して,後処理ビットフリップアルゴリズムを適用し,スパースQAPの解法を提案する。 D-Wave Advantage を用いて,D-Wave Advantage を用いた QAP の高精度化に成功した。
  論文  参考訳（メタデータ） (2020-12-18T09:48:28Z)
• Fast Uncertainty Quantification for Deep Object Pose Estimation [91.09217713805337]
  深層学習に基づくオブジェクトポーズ推定は、しばしば信頼できない、自信過剰である。 本研究では,6-DoFオブジェクトのポーズ推定のための,シンプルで効率的かつプラグアンドプレイなUQ手法を提案する。
  論文  参考訳（メタデータ） (2020-11-16T06:51:55Z)
• Physarum Powered Differentiable Linear Programming Layers and Applications [48.77235931652611]
  一般線形プログラミング問題に対する効率的かつ微分可能な解法を提案する。 本稿では,ビデオセグメンテーションタスクとメタラーニングにおける問題解決手法について述べる。
  論文  参考訳（メタデータ） (2020-04-30T01:50:37Z)

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

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