論文の概要: Learning with Local Search MCMC Layers

• arxiv url: http://arxiv.org/abs/2505.14240v1
• Date: Tue, 20 May 2025 11:47:42 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-05-21 14:49:53.147007
• Title: Learning with Local Search MCMC Layers
• Title（参考訳）: 局所探索MCMC層を用いた学習
• Authors: Germain Vivier-Ardisson, Mathieu Blondel, Axel Parmentier,
• Abstract要約: 不正確な解法による学習に理論的に根ざしたアプローチを導入する。 局所探索で使用される問題固有近傍系を提案分布に変換する。 時間窓を用いた大規模動的車両ルーティング問題に対する我々のアプローチを実証する。
• 参考スコア（独自算出の注目度）: 11.772298193297013
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Integrating combinatorial optimization layers into neural networks has recently attracted significant research interest. However, many existing approaches lack theoretical guarantees or fail to perform adequately when relying on inexact solvers. This is a critical limitation, as many operations research problems are NP-hard, often necessitating the use of neighborhood-based local search heuristics. These heuristics iteratively generate and evaluate candidate solutions based on an acceptance rule. In this paper, we introduce a theoretically-principled approach for learning with such inexact combinatorial solvers. Inspired by the connection between simulated annealing and Metropolis-Hastings, we propose to transform problem-specific neighborhood systems used in local search heuristics into proposal distributions, implementing MCMC on the combinatorial space of feasible solutions. This allows us to construct differentiable combinatorial layers and associated loss functions. Replacing an exact solver by a local search strongly reduces the computational burden of learning on many applications. We demonstrate our approach on a large-scale dynamic vehicle routing problem with time windows.
• Abstract（参考訳）: 組合せ最適化レイヤをニューラルネットワークに統合することは、最近、大きな研究関心を集めている。 しかし、既存の多くのアプローチは理論的な保証を欠いており、不正確な解法に依存する場合、適切に実行できない。 これは、多くの操作研究問題はNPハードであり、しばしば近隣の局所探索ヒューリスティックの使用を必要とするため、決定的な制限である。 これらのヒューリスティックスは、受理規則に基づいて候補解を反復的に生成し、評価する。 本稿では,このような不正確な組合せ解法を用いて学習するための理論的原理的アプローチを提案する。 シミュレーションアニーリングとメトロポリス・ハスティングス(Metropolis-Hastings)の接続にインスパイアされた我々は,局所探索ヒューリスティックで使用される問題固有の近隣系を提案分布に変換することを提案し,実現可能なソリューションの組合せ空間にMCMCを実装した。 これにより、微分可能な組合せ層と関連する損失関数を構築することができる。 局所探索による正確な解法の置き換えは、多くのアプリケーションにおける学習の計算負担を強く軽減する。 時間窓を用いた大規模動的車両ルーティング問題に対する我々のアプローチを実証する。

関連論文リスト

• A Random-Key Optimizer for Combinatorial Optimization [0.0]
  Random-Key Hubs (RKO) は最適化問題に適した汎用的で効率的な局所探索手法である。 ランダムキーの概念を用いて、RKOは解をランダムキーのベクトルとしてエンコードし、後に問題固有のデコーダを介して実現可能な解へとデコードする。 RKOフレームワークは古典的メタヒューリスティクスの多元体を組み合わせ、それぞれが独立して、あるいは並列に動作可能であり、エリートソリューションプールを通じてソリューション共有が促進される。
  論文  参考訳（メタデータ） (2024-11-06T22:23:29Z)
• Spatial-temporal-demand clustering for solving large-scale vehicle routing problems with time windows [0.0]
  本稿では,クラスタリングを用いて顧客をグループ化するDRI(Decompose-route-improve)フレームワークを提案する。 その類似度基準は、顧客の空間的、時間的、需要データを含む。 本研究では,解答サブプロブレム間でプルーンド局所探索(LS)を適用し,全体の解法を改善する。
  論文  参考訳（メタデータ） (2024-01-20T06:06:01Z)
• MARLIN: Soft Actor-Critic based Reinforcement Learning for Congestion Control in Real Networks [63.24965775030673]
  そこで本研究では,汎用的な渋滞制御(CC)アルゴリズムを設計するための新しい強化学習(RL)手法を提案する。 我々の解であるMARLINは、Soft Actor-Criticアルゴリズムを用いてエントロピーとリターンの両方を最大化する。 我々は,MARLINを実ネットワーク上で訓練し,実ミスマッチを克服した。
  論文  参考訳（メタデータ） (2023-02-02T18:27:20Z)
• Learning to Control Local Search for Combinatorial Optimization [4.243592852049962]
  一般化の動物園と問題固有の局所探索の変種は、近似解を計算するのによく用いられる。 本稿では,そのような局所探索アルゴリズムの3つの独立したアルゴリズム的側面を同定し,最適化プロセス上でのシーケンシャルな選択を形式化する。 我々は、NeuroLSがオペレーティングリサーチの汎用ローカルサーチコントローラと最新の機械学習ベースのアプローチの両方より優れていることを示す。
  論文  参考訳（メタデータ） (2022-06-27T10:48:56Z)
• Reinforcement Learning for Branch-and-Bound Optimisation using Retrospective Trajectories [72.15369769265398]
  機械学習は分岐のための有望なパラダイムとして登場した。 分岐のための単純かつ効果的なRLアプローチであるレトロ分岐を提案する。 我々は現在最先端のRL分岐アルゴリズムを3～5倍に上回り、500の制約と1000の変数を持つMILP上での最高のILメソッドの性能の20%以内である。
  論文  参考訳（メタデータ） (2022-05-28T06:08:07Z)
• Frequent Itemset-driven Search for Finding Minimum Node Separators in Complex Networks [61.2383572324176]
  本稿では,データマイニングにおける頻繁なアイテムセットマイニングの概念をよく知られたメメティック検索フレームワークに統合する,頻繁なアイテムセット駆動探索手法を提案する。 頻繁なアイテムセット組換え演算子を反復的に使用して、高品質なソリューションで頻繁に発生するアイテムセットに基づいた有望な子孫ソリューションを生成する。 特に、29個の新しい上界を発見し、以前の18個の最もよく知られた境界と一致する。
  論文  参考訳（メタデータ） (2022-01-18T11:16:40Z)
• Towards Optimally Efficient Tree Search with Deep Learning [76.64632985696237]
  本稿では,線形モデルから信号整数を推定する古典整数最小二乗問題について検討する。 問題はNPハードであり、信号処理、バイオインフォマティクス、通信、機械学習といった様々な応用でしばしば発生する。 本稿では, 深いニューラルネットワークを用いて, 単純化されたメモリバウンドA*アルゴリズムの最適推定を推定し, HATSアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2021-01-07T08:00:02Z)
• Distributed Optimization, Averaging via ADMM, and Network Topology [0.0]
  センサローカライゼーションの現実問題において,ネットワークトポロジと異なるアルゴリズムの収束率の関係について検討する。 また、ADMMと持ち上げマルコフ連鎖の間の興味深い関係を示すとともに、その収束を明示的に特徴づける。
  論文  参考訳（メタデータ） (2020-09-05T21:44:39Z)
• Iterative Algorithm Induced Deep-Unfolding Neural Networks: Precoding Design for Multiuser MIMO Systems [59.804810122136345]
  本稿では,AIIDNN(ディープ・アンフォールディング・ニューラルネット)を一般化した,ディープ・アンフォールディングのためのフレームワークを提案する。 古典的重み付き最小二乗誤差(WMMSE)反復アルゴリズムの構造に基づく効率的なIAIDNNを提案する。 提案したIAIDNNは,計算複雑性を低減した反復WMMSEアルゴリズムの性能を効率よく向上することを示す。
  論文  参考訳（メタデータ） (2020-06-15T02:57:57Z)
• Learning to Accelerate Heuristic Searching for Large-Scale Maximum Weighted b-Matching Problems in Online Advertising [51.97494906131859]
  バイパルタイトbマッチングはアルゴリズム設計の基本であり、経済市場や労働市場などに広く適用されている。 既存の正確で近似的なアルゴリズムは、通常そのような設定で失敗する。 我々は、以前の事例から学んだ知識を活用して、新しい問題インスタンスを解決するtextttNeuSearcherを提案する。
  論文  参考訳（メタデータ） (2020-05-09T02:48:23Z)
• Reinforcement Learning for Combinatorial Optimization: A Survey [12.323976053967066]
  最適化問題を解決する多くの伝統的なアルゴリズムは、解決を逐次構築する手工芸品を使用する。 強化学習(Reinforcement Learning, RL)は、エージェントを監督的または自己監督的な方法で訓練することにより、これらの検索を自動化する優れた代替手段を提案する。
  論文  参考訳（メタデータ） (2020-03-07T16:19:45Z)

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

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