論文の概要: Boosting Generalization in Diffusion-Based Neural Combinatorial Solver via Energy-guided Sampling

• arxiv url: http://arxiv.org/abs/2502.12188v1
• Date: Sat, 15 Feb 2025 08:04:00 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-02-19 14:08:09.998111
• Title: Boosting Generalization in Diffusion-Based Neural Combinatorial Solver via Energy-guided Sampling
• Title（参考訳）: エネルギー誘導サンプリングによる拡散型ニューラルコンビネーティブソルバーの高速化
• Authors: Haoyu Lei, Kaiwen Zhou, Yinchuan Li, Zhitang Chen, Farzan Farnia,
• Abstract要約: 拡散に基づくニューラルネットワーク最適化(NCO)は、解生成のための離散拡散モデルを学習し、手作りのドメイン知識を排除し、NP完全(NPC)問題の解決に有効であることを示した。 既存のNCO手法は、クロススケールおよびクロスプロブレムの一般化において課題に直面し、従来の解法と比較して高いトレーニングコストがかかる。 我々は,拡散型NCOソルバのクロススケールおよびクロスプロブレムの一般化能力を,追加の訓練を必要とせずに向上させる,一般エネルギー誘導サンプリングフレームワークを提案する。
• 参考スコア（独自算出の注目度）: 27.898573891403075
• License:
• Abstract: Diffusion-based Neural Combinatorial Optimization (NCO) has demonstrated effectiveness in solving NP-complete (NPC) problems by learning discrete diffusion models for solution generation, eliminating hand-crafted domain knowledge. Despite their success, existing NCO methods face significant challenges in both cross-scale and cross-problem generalization, and high training costs compared to traditional solvers. While recent studies have introduced training-free guidance approaches that leverage pre-defined guidance functions for zero-shot conditional generation, such methodologies have not been extensively explored in combinatorial optimization. To bridge this gap, we propose a general energy-guided sampling framework during inference time that enhances both the cross-scale and cross-problem generalization capabilities of diffusion-based NCO solvers without requiring additional training. We provide theoretical analysis that helps understanding the cross-problem transfer capability. Our experimental results demonstrate that a diffusion solver, trained exclusively on the Traveling Salesman Problem (TSP), can achieve competitive zero-shot solution generation on TSP variants, such as Prize Collecting TSP (PCTSP) and the Orienteering Problem (OP), through energy-guided sampling across different problem scales.
• Abstract（参考訳）: 拡散に基づくニューラルネットワーク最適化(NCO)は、解生成のための離散拡散モデルを学習し、手作りのドメイン知識を排除し、NP完全(NPC)問題の解決に有効であることを示した。 彼らの成功にもかかわらず、既存のNCO手法は、クロススケールおよびクロスプロブレムの一般化において大きな課題に直面し、従来の解法と比較して高いトレーニングコストがかかる。 近年、ゼロショット条件生成のための事前定義されたガイダンス関数を利用するトレーニングフリーガイダンス手法が提案されているが、このような手法は組合せ最適化において広く研究されていない。 このギャップを埋めるために,拡散型NCOソルバのクロススケールおよびクロスプロブレムの一般化能力を向上させるため,追加のトレーニングを必要とせず,一般エネルギー誘導型サンプリングフレームワークを提案する。 我々は,クロスプロブレム伝達能力の理解を支援する理論的解析を行う。 実験結果から,TSP(Traveing Salesman Problem)に特化して訓練された拡散解法は,TSP(PCTSP)やOP(Orienteering Problem)といったTSPの変種に対して,異なる問題スケールにわたるエネルギー誘導サンプリングによって,競争力のあるゼロショットソリューション生成を実現することができることが示された。

関連論文リスト

• Preventing Local Pitfalls in Vector Quantization via Optimal Transport [77.15924044466976]
  我々はシンクホーンアルゴリズムを用いて最適な輸送問題を最適化する新しいベクトル量子化法であるOptVQを紹介する。 画像再構成タスクの実験では,OptVQが100%のコードブック利用を実現し,現在最先端のVQNを超越していることが示された。
  論文  参考訳（メタデータ） (2024-12-19T18:58:14Z)
• Liner Shipping Network Design with Reinforcement Learning [1.833650794546064]
  本稿では,Liner Shipping Network Design Problem (LSNDP) に対処する新しい強化学習フレームワークを提案する。 提案手法では,ALIBをベースとしたマルチコモディティ・フロー・ソルバと統合したモデルレス強化学習アルゴリズムをネットワーク設計に適用する。
  論文  参考訳（メタデータ） (2024-11-13T22:49:16Z)
• Optimization by Parallel Quasi-Quantum Annealing with Gradient-Based Sampling [0.0]
  本研究では、連続緩和による勾配に基づく更新と準量子アナリング(QQA)を組み合わせた別のアプローチを提案する。 数値実験により,本手法はiSCOと学習型解法に匹敵する性能を有する汎用解法であることが示された。
  論文  参考訳（メタデータ） (2024-09-02T12:55:27Z)
• DiffSG: A Generative Solver for Network Optimization with Diffusion Model [75.27274046562806]
  拡散生成モデルはより広い範囲の解を考えることができ、学習パラメータによるより強力な一般化を示す。 拡散生成モデルの本質的な分布学習を利用して高品質な解を学習する新しいフレームワークを提案する。
  論文  参考訳（メタデータ） (2024-08-13T07:56:21Z)
• Instance-Conditioned Adaptation for Large-scale Generalization of Neural Combinatorial Optimization [15.842155380912002]
  本研究は,ニューラル最適化の大規模一般化のための新しいインスタンス・コンディション適応モデル(ICAM)を提案する。 特に,NCOモデルのための強力なインスタンス条件付きルーティング適応モジュールを設計する。 我々は,ラベル付き最適解を使わずに,モデルがクロススケールな特徴を学習することのできる,効率的な3段階強化学習ベーストレーニング手法を開発した。
  論文  参考訳（メタデータ） (2024-05-03T08:00:19Z)
• An Efficient Learning-based Solver Comparable to Metaheuristics for the Capacitated Arc Routing Problem [67.92544792239086]
  我々は,高度メタヒューリスティックスとのギャップを著しく狭めるため,NNベースの解法を導入する。 まず,方向対応型注意モデル(DaAM)を提案する。 第2に、教師付き事前学習を伴い、堅牢な初期方針を確立するための教師付き強化学習スキームを設計する。
  論文  参考訳（メタデータ） (2024-03-11T02:17:42Z)
• Rethinking Clustered Federated Learning in NOMA Enhanced Wireless Networks [60.09912912343705]
  本研究では,新しいクラスタ化フェデレーション学習(CFL)アプローチと,非独立かつ同一に分散した(非IID)データセットを統合することのメリットについて検討する。 データ分布における非IIDの度合いを測定する一般化ギャップの詳細な理論的解析について述べる。 非IID条件によって引き起こされる課題に対処する解決策は、特性の分析によって提案される。
  論文  参考訳（メタデータ） (2024-03-05T17:49:09Z)
• Operator Learning Enhanced Physics-informed Neural Networks for Solving Partial Differential Equations Characterized by Sharp Solutions [10.999971808508437]
  そこで我々は,OL-PINN(Operator Learning Enhanced Physics-informed Neural Networks)と呼ばれる新しいフレームワークを提案する。 提案手法は, 強い一般化能力を実現するために, 少数の残差点しか必要としない。 精度を大幅に向上すると同時に、堅牢なトレーニングプロセスも保証する。
  論文  参考訳（メタデータ） (2023-10-30T14:47:55Z)
• 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)
• Stochastic Unrolled Federated Learning [85.6993263983062]
  本稿では,UnRolled Federated Learning (SURF)を導入する。 提案手法は,この拡張における2つの課題,すなわち,非学習者へのデータセット全体の供給の必要性と,フェデレート学習の分散的性質に対処する。
  論文  参考訳（メタデータ） (2023-05-24T17:26:22Z)
• Learning to Solve Routing Problems via Distributionally Robust Optimization [14.506553345693536]
  ルーティング問題を解決するための最近のディープモデルでは、トレーニング用のノードの単一分布が想定されており、分散一般化能力を著しく損なう。 この問題に対処するために、群分布的ロバストな最適化(グループDRO)を活用し、異なる分布群に対する重み付けと深層モデルのパラメータを、トレーニング中にインターリーブされた方法で共同で最適化する。 また、畳み込みニューラルネットワークに基づくモジュールを設計し、ディープモデルがノード間のより情報に富んだ潜在パターンを学習できるようにする。
  論文  参考訳（メタデータ） (2022-02-15T08:06:44Z)

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

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