論文の概要: A Game-Theoretic Approach for Improving Generalization Ability of TSP Solvers

• arxiv url: http://arxiv.org/abs/2110.15105v2
• Date: Fri, 29 Oct 2021 09:06:30 GMT
• ステータス: 処理完了
• システム内更新日: 2021-11-01 11:41:36.456150
• Title: A Game-Theoretic Approach for Improving Generalization Ability of TSP Solvers
• Title（参考訳）: TSPソルバの一般化能力向上のためのゲーム理論的アプローチ
• Authors: Chenguang Wang, Yaodong Yang, Oliver Slumbers, Congying Han, Tiande Guo, Haifeng Zhang, Jun Wang
• Abstract要約: トレーニング可能なEmphrとemphData Generatorの間に2つのプレイヤーゼロサムフレームワークを導入する。 本稿では,トラベリングセールスマン問題におけるタスクにおいて,最も一般化可能なパフォーマンスを実現するためのフレームワークについて述べる。
• 参考スコア（独自算出の注目度）: 16.98434288039677
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: In this paper, we shed new light on the generalization ability of deep learning-based solvers for Traveling Salesman Problems (TSP). Specifically, we introduce a two-player zero-sum framework between a trainable \emph{Solver} and a \emph{Data Generator}, where the Solver aims to solve the task instances provided by the Generator, and the Generator aims to generate increasingly difficult instances for improving the Solver. Grounded in \textsl{Policy Space Response Oracle} (PSRO) methods, our two-player framework outputs a population of best-responding Solvers, over which we can mix and output a combined model that achieves the least exploitability against the Generator, and thereby the most generalizable performance on different TSP tasks. We conduct experiments on a variety of TSP instances with different types and sizes. Results suggest that our Solvers achieve the state-of-the-art performance even on tasks the Solver never meets, whilst the performance of other deep learning-based Solvers drops sharply due to over-fitting. On real-world instances from \textsc{TSPLib}, our method also attains a \textbf{12\%} improvement, in terms of optimal gap, over the best baseline model. To demonstrate the principle of our framework, we study the learning outcome of the proposed two-player game and demonstrate that the exploitability of the Solver population decreases during training, and it eventually approximates the Nash equilibrium along with the Generator.
• Abstract（参考訳）: 本稿では,ディープラーニングに基づくトラベリングセールスマン問題(TSP)の一般化能力に新たな光を当てた。 具体的には、トレーニング可能な \emph{Solver} と \emph{Data Generator} の間に2つのプレイヤーゼロサムフレームワークを導入し、Solver は、Generator が提供するタスクインスタンスの解決を目的としており、Generator は、Solver を改善するためにますます難しいインスタンスを生成することを目的としている。 原文(投稿日:2019/09/09)へのリンク oracle (psro) メソッドを基礎として、2人のプレイヤーが最善の対応ソルバの集団を出力し、ジェネレータに対して最小のエクスプロイト可能性を達成する結合モデルを組み合わせて出力し、異なるtspタスクで最も一般的なパフォーマンスを得ることができます。 異なるタイプとサイズを持つ様々なTSPインスタンスで実験を行う。 結果から, 解答者は解答者が決して満たさないタスクでも最先端のパフォーマンスを達成できるが, 他の深層学習型解答者の性能は過剰フィッティングにより急激に低下することが示唆された。 実世界における \textsc{tsplib} からのインスタンスでは、最適なベースラインモデルに対する最適なギャップの観点から、この手法は \textbf{12\%} の改善も達成する。 本手法の原理を実証するために,提案する2人プレイゲームの学習結果を調査し,学習中にソルバ集団の活用性が低下することを示すとともに,最終的にジェネレータとナッシュ均衡を近似する。

関連論文リスト

• Neural Solver Selection for Combinatorial Optimization [23.449310200885893]
  本稿では,特徴抽出,選択モデル,選択戦略を含むニューラルソルバのコーディネートを行うための,最初の汎用フレームワークを提案する。 提案するフレームワークは,インスタンスを効果的に分散し,結果として得られる複合解法により性能が大幅に向上することを示す。
  論文  参考訳（メタデータ） (2024-10-13T02:05:41Z)
• Leveraging Constraint Programming in a Deep Learning Approach for Dynamically Solving the Flexible Job-Shop Scheduling Problem [1.3927943269211593]
  本稿では,制約プログラミング(CP)をディープラーニング(DL)ベースの方法論に統合し,両者の利点を活用することを目的とする。 本稿では,CP が生成する最適解を用いて DL モデルを訓練し,高品質なデータからモデルを学習する手法を提案する。 我々のハイブリッドアプローチは3つの公開FJSSPベンチマークで広範囲にテストされ、5つの最先端DRLアプローチよりも優れた性能を示している。
  論文  参考訳（メタデータ） (2024-03-14T10:16:57Z)
• Self-Labeling the Job Shop Scheduling Problem [15.723699332053558]
  生成モデルは複数の解をサンプリングし、問題の目的に応じて最良の解を擬似ラベルとして使用することにより訓練可能であることを示す。 旅行セールスマン問題に適用することで,様々なパラメータに対するSLIMのロバスト性とその一般性を証明する。
  論文  参考訳（メタデータ） (2024-01-22T11:08:36Z)
• Promoting Generalization for Exact Solvers via Adversarial Instance Augmentation [62.738582127114704]
  Adarは、模倣学習ベース(ILベース)と強化学習ベース(RLベース)の両方の一般化を理解し、改善するためのフレームワークである。
  論文  参考訳（メタデータ） (2023-10-22T03:15:36Z)
• Maximize to Explore: One Objective Function Fusing Estimation, Planning, and Exploration [87.53543137162488]
  我々はtextttMEX というオンライン強化学習(オンラインRL)フレームワークを提案する。 textttMEXは、自動的に探索エクスプロイトのバランスをとりながら、見積もりと計画コンポーネントを統合する。 様々な MuJoCo 環境では,ベースラインを安定的なマージンで上回り,十分な報酬を得られる。
  論文  参考訳（メタデータ） (2023-05-29T17:25:26Z)
• ASP: Learn a Universal Neural Solver! [16.98189196303338]
  これらの一般化問題に対処するため、Oracleは ASP: Adaptive Staircase Policy Space Response を提案します。 ASPは2つのコンポーネントで構成されている。 この結果から、ASPは、未知の分布や様々なスケールに適応し、優れたパフォーマンスを実現するために、ニューラルネットワークを探索し、適応するのに役立つことが示唆された。
  論文  参考訳（メタデータ） (2023-03-01T12:47:14Z)
• Learning To Dive In Branch And Bound [95.13209326119153]
  グラフニューラルネットワークを用いて特定の潜水構造を学習するためのL2Diveを提案する。 我々は、変数の割り当てを予測するために生成モデルを訓練し、線形プログラムの双対性を利用して潜水決定を行う。
  論文  参考訳（メタデータ） (2023-01-24T12:01:45Z)
• Learning to Solve Routing Problems via Distributionally Robust Optimization [14.506553345693536]
  ルーティング問題を解決するための最近のディープモデルでは、トレーニング用のノードの単一分布が想定されており、分散一般化能力を著しく損なう。 この問題に対処するために、群分布的ロバストな最適化(グループDRO)を活用し、異なる分布群に対する重み付けと深層モデルのパラメータを、トレーニング中にインターリーブされた方法で共同で最適化する。 また、畳み込みニューラルネットワークに基づくモジュールを設計し、ディープモデルがノード間のより情報に富んだ潜在パターンを学習できるようにする。
  論文  参考訳（メタデータ） (2022-02-15T08:06:44Z)
• Combining Deep Learning and Optimization for Security-Constrained Optimal Power Flow [94.24763814458686]
  セキュリティに制約のある最適電力フロー(SCOPF)は、電力システムの基本である。 SCOPF問題におけるAPRのモデル化は、複雑な大規模混合整数プログラムをもたらす。 本稿では,ディープラーニングとロバスト最適化を組み合わせた新しい手法を提案する。
  論文  参考訳（メタデータ） (2020-07-14T12:38:21Z)
• SUNRISE: A Simple Unified Framework for Ensemble Learning in Deep Reinforcement Learning [102.78958681141577]
  SUNRISEは単純な統一アンサンブル法であり、様々な非政治的な深層強化学習アルゴリズムと互換性がある。 SUNRISEは, (a) アンサンブルに基づく重み付きベルマンバックアップと, (b) 最上位の自信境界を用いて行動を選択する推論手法を統合し, 効率的な探索を行う。
  論文  参考訳（メタデータ） (2020-07-09T17:08:44Z)
• Forgetful Experience Replay in Hierarchical Reinforcement Learning from Demonstrations [55.41644538483948]
  本稿では,複雑な視覚環境において,エージェントが低品質な実演を行えるようにするためのアプローチの組み合わせを提案する。 提案した目標指向のリプレイバッファ構築により,エージェントはデモにおいて複雑な階層的タスクを解くためのサブゴールを自動的に強調することができる。 私たちのアルゴリズムに基づくこのソリューションは、有名なMineRLコンペティションのすべてのソリューションを破り、エージェントがMinecraft環境でダイヤモンドをマイニングすることを可能にする。
  論文  参考訳（メタデータ） (2020-06-17T15:38:40Z)

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

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