論文の概要: DIMES: A Differentiable Meta Solver for Combinatorial Optimization Problems

• arxiv url: http://arxiv.org/abs/2210.04123v1
• Date: Sat, 8 Oct 2022 23:24:37 GMT
• ステータス: 処理完了
• システム内更新日: 2022-10-11 15:50:22.068177
• Title: DIMES: A Differentiable Meta Solver for Combinatorial Optimization Problems
• Title（参考訳）: DIMES: 組合せ最適化問題のための微分可能なメタソルバー
• Authors: Ruizhong Qiu, Zhiqing Sun, Yiming Yang
• Abstract要約: 深部強化学習(DRL)モデルはNP-hard Combinatorial Optimization問題を解決する上で有望な結果を示している。 本稿では,DIMESという新しいアプローチを提案することによって,大規模最適化におけるスケーラビリティの課題に対処する。 コストのかかる自己回帰的復号法や離散解の反復的洗練に苦しむ従来のDRL法とは異なり、DIMESは候補解の基底分布をパラメータ化するためのコンパクトな連続空間を導入する。 DIMESは、トラベリングセールスマン問題や最大独立セット問題のための大規模なベンチマークデータセットにおいて、最近のDRLベースの手法よりも優れていることを示す。
• 参考スコア（独自算出の注目度）: 41.57773395100222
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Recently, deep reinforcement learning (DRL) models have shown promising results in solving NP-hard Combinatorial Optimization (CO) problems. However, most DRL solvers can only scale to a few hundreds of nodes for combinatorial optimization problems on graphs, such as the Traveling Salesman Problem (TSP). This paper addresses the scalability challenge in large-scale combinatorial optimization by proposing a novel approach, namely, DIMES. Unlike previous DRL methods which suffer from costly autoregressive decoding or iterative refinements of discrete solutions, DIMES introduces a compact continuous space for parameterizing the underlying distribution of candidate solutions. Such a continuous space allows stable REINFORCE-based training and fine-tuning via massively parallel sampling. We further propose a meta-learning framework to enable the effective initialization of model parameters in the fine-tuning stage. Extensive experiments show that DIMES outperforms recent DRL-based methods on large benchmark datasets for Traveling Salesman Problems and Maximal Independent Set problems.
• Abstract（参考訳）: 近年, NP-hard Combinatorial Optimization (CO) 問題を解く上で, 深層強化学習(DRL)モデルが有望な結果を示している。 しかし、ほとんどのDRLソルバは、トラベルセールスマン問題(TSP)のようなグラフ上の組合せ最適化問題に対して数百のノードにしかスケールできない。 本稿では,新しい手法,すなわちdimsを提案することで,大規模組合せ最適化におけるスケーラビリティ問題に対処する。 コストのかかる自己回帰的復号法や離散解の反復的洗練に苦しむ従来のDRL法とは異なり、DIMESは候補解の基底分布をパラメータ化するためのコンパクトな連続空間を導入する。 このような連続空間は、安定的な強化ベースのトレーニングと超並列サンプリングによる微調整を可能にする。 さらに,モデルパラメータの微調整段階における効果的な初期化を可能にするメタ学習フレームワークを提案する。 DIMESは、トラベリングセールスマン問題や最大独立セット問題のための大規模なベンチマークデータセットにおいて、最近のDRLベースの手法よりも優れていることを示す。

関連論文リスト

• DISCO: Efficient Diffusion Solver for Large-Scale Combinatorial Optimization Problems [37.205311971072405]
  DISCOは、大規模な組合せ最適化問題に対する効率的な拡散解法である。 サンプリング空間は、解残基によって導かれるより有意義な領域に制約され、出力分布のマルチモーダルな性質は保たれる。 大規模なトラベリングセールスマン問題や最大独立セットのベンチマークに挑戦し、他の拡散手段よりも最大5.28倍の速度で推論を行う。
  論文  参考訳（メタデータ） (2024-06-28T07:36:31Z)
• Leader Reward for POMO-Based Neural Combinatorial Optimization [8.301694061287565]
  本稿では、最適解を生成するモデルの能力を高めるために、Lead Rewardを提案する。 我々は、Lead Rewardがモデルによって生成される最適なソリューションの品質を大幅に改善することを示した。
  論文  参考訳（メタデータ） (2024-05-22T19:27:03Z)
• Learning Adaptive Evolutionary Computation for Solving Multi-Objective Optimization Problems [3.3266268089678257]
  本稿では, 深層強化学習(DRL)を用いた適応パラメータ制御とMOEAを統合したフレームワークを提案する。 DRLポリシは、最適化中のソリューションに対する突然変異の強度と確率を決定する値を適応的に設定するように訓練されている。 学習されたポリシーは転送可能であることを示す。つまり、単純なベンチマーク問題で訓練されたポリシーは、複雑な倉庫最適化問題を解決するために直接適用可能である。
  論文  参考訳（メタデータ） (2022-11-01T22:08:34Z)
• Pareto Set Learning for Neural Multi-objective Combinatorial Optimization [6.091096843566857]
  多目的最適化(MOCO)の問題は、現実世界の多くのアプリケーションで見られる。 我々は,与えられたMOCO問題に対するパレート集合全体を,探索手順を伴わずに近似する学習ベースアプローチを開発した。 提案手法は,多目的走行セールスマン問題,マルチコンディショニング車両ルーティング問題,複数クナップサック問題において,ソリューションの品質,速度,モデル効率の面で,他の方法よりも優れていた。
  論文  参考訳（メタデータ） (2022-03-29T09:26:22Z)
• Neural Stochastic Dual Dynamic Programming [99.80617899593526]
  我々は、問題インスタンスを断片的線形値関数にマッピングすることを学ぶトレーニング可能なニューラルモデルを導入する。 $nu$-SDDPは、ソリューションの品質を犠牲にすることなく、問題解決コストを大幅に削減できる。
  論文  参考訳（メタデータ） (2021-12-01T22:55:23Z)
• Meta-Learning-based Deep Reinforcement Learning for Multiobjective Optimization Problems [11.478548460936837]
  本稿では,簡潔なメタラーニングに基づくDRLアプローチを提案する。 最初にメタモデルをメタラーニングで訓練する。 メタモデルは、対応するサブ問題に対するサブモデルを導出するためのいくつかの更新ステップで微調整される。
  論文  参考訳（メタデータ） (2021-05-06T15:09:35Z)
• Modeling the Second Player in Distributionally Robust Optimization [90.25995710696425]
  我々は、最悪のケース分布を特徴付けるために神経生成モデルを使うことを議論する。 このアプローチは多くの実装と最適化の課題をもたらします。 提案されたアプローチは、同等のベースラインよりも堅牢なモデルを生み出す。
  論文  参考訳（メタデータ） (2021-03-18T14:26:26Z)
• Combining Deep Learning and Optimization for Security-Constrained Optimal Power Flow [94.24763814458686]
  セキュリティに制約のある最適電力フロー(SCOPF)は、電力システムの基本である。 SCOPF問題におけるAPRのモデル化は、複雑な大規模混合整数プログラムをもたらす。 本稿では,ディープラーニングとロバスト最適化を組み合わせた新しい手法を提案する。
  論文  参考訳（メタデータ） (2020-07-14T12:38:21Z)
• Automatically Learning Compact Quality-aware Surrogates for Optimization Problems [55.94450542785096]
  未知パラメータで最適化問題を解くには、未知パラメータの値を予測し、これらの値を用いて問題を解くための予測モデルを学ぶ必要がある。 最近の研究によると、複雑なトレーニングモデルパイプラインのレイヤーとして最適化の問題を含めると、観測されていない意思決定の繰り返しを予測することになる。 我々は,大規模最適化問題の低次元サロゲートモデルを学習することにより,解の質を向上させることができることを示す。
  論文  参考訳（メタデータ） (2020-06-18T19:11:54Z)
• Learning What to Defer for Maximum Independent Sets [84.00112106334655]
  本稿では,各段階における解の要素的決定を学習することにより,エージェントが適応的に段階数を縮小あるいは拡張する,新たなDRL方式を提案する。 提案手法を最大独立集合(MIS)問題に適用し、現状のDRL方式よりも大幅に改善したことを示す。
  論文  参考訳（メタデータ） (2020-06-17T02:19:31Z)

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

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