論文の概要: Tensor Network Generator-Enhanced Optimization for Traveling Salesman Problem

• arxiv url: http://arxiv.org/abs/2602.20175v1
• Date: Thu, 12 Feb 2026 21:18:19 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-03-02 07:21:25.643377
• Title: Tensor Network Generator-Enhanced Optimization for Traveling Salesman Problem
• Title（参考訳）: テンソル・ネットワーク・ジェネレータによるトラベリングセールスマン問題の最適化
• Authors: Ryo Sakai, Chen-Yu Liu,
• Abstract要約: 本稿では、旅行セールスマン問題(TSP)に対するテンソルネットワークジェネレータ強化最適化(TN-GEO)フレームワークの適用について述べる。 提案手法では,自動微分可能な行列積状態(MPS)を生成モデルとして,テンソルネットワークのBornマシンを用いる。 局所的な相関に注目する$k$-site variantsは、フルMPSの場合よりもよい結果を示す。
• 参考スコア（独自算出の注目度）: 12.04919729571293
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We present an application of the tensor network generator-enhanced optimization (TN-GEO) framework to address the traveling salesman problem (TSP), a fundamental combinatorial optimization challenge. Our approach employs a tensor network Born machine based on automatically differentiable matrix product states (MPS) as the generative model, using the Born rule to define probability distributions over candidate solutions. Unlike approaches based on binary encoding, which require $N^2$ variables and penalty terms to enforce valid tour constraints, we adopt a permutation-based formulation with integer variables and use autoregressive sampling with masking to guarantee that every generated sample is a valid tour by construction. We also introduce a $k$-site MPS variant that learns distributions over $k$-grams (consecutive city subsequences) using a sliding window approach, enabling parameter-efficient modeling for larger instances. Experimental validation on TSPLIB benchmark instances with up to 52 cities demonstrates that TN-GEO can outperform classical heuristics including swap and 2-opt hill-climbing. The $k$-site variants, which put more focus on local correlations, show better results compared to the full-MPS case.
• Abstract（参考訳）: 本稿では,基本組合せ最適化問題である旅行セールスマン問題(TSP)に対するテンソルネットワークジェネレータ強化最適化(TN-GEO)フレームワークの適用について述べる。 提案手法では,自動微分行列積状態(MPS)を生成モデルとするテンソルネットワークBornを用いて,候補解上の確率分布を定義する。 有効なツアー制約を強制するために$N^2$変数とペナルティ項を必要とするバイナリエンコーディングに基づくアプローチとは異なり、整数変数による置換ベースの定式化を採用し、マスキングによる自己回帰サンプリングを用いて、生成されたサンプルがすべて構成による有効なツアーであることを保証している。 また、スライディングウインドウアプローチを用いて、$k$-site MPS バリアントを導入し、$k$-grams (consecutive city subsequences) 以上の分布を学習し、より大きなインスタンスに対するパラメータ効率のモデリングを可能にする。 最大52都市でのTSPLIBベンチマークの検証実験により、TN-GEOはスワップや2オプトヒルクライミングなどの古典的ヒューリスティックよりも優れていることが示された。 局所的な相関に重きを置く$k$-siteは、フルMPSの場合よりも良い結果を示す。

関連論文リスト

• Generative Diffusion Models for Resource Allocation in Wireless Networks [74.84410305593006]
  我々は、専門家を模倣し、最適な分布から新しいサンプルを生成するポリシーを訓練する。 生成したサンプルの逐次実行により,ほぼ最適性能を実現する。 電力制御のケーススタディにおいて数値的な結果を示す。
  論文  参考訳（メタデータ） (2025-04-28T21:44:31Z)
• Combining Local Symmetry Exploitation and Reinforcement Learning for Optimised Probabilistic Inference -- A Work In Progress [2.2164989053903805]
  グラフィカルモデルにおける変数除去による効率的な確率的推論は最適な除去順序を必要とする。 我々は、テンソルネットワークにおける効率的な収縮順序を見つけるために強化学習アプローチを適用する。 推論中に特定の構造を活用することで、中間結果のコンパクトな符号化を導入することができることを示す。
  論文  参考訳（メタデータ） (2025-03-11T18:00:23Z)
• Regularized second-order optimization of tensor-network Born machines [2.8834278113855896]
  ボルンマシン(英: Born Machine、TNBM)は、データ分布を学習するための量子インスパイアされた生成モデルである。 TNBMの鍵となるボトルネックは、この問題によく使用される損失関数の対数的性質である。 そこで本研究では,TNBMトレーニングにおける2次最適化手法を改良し,収束率と最適化モデルの品質を大幅に向上させる。
  論文  参考訳（メタデータ） (2025-01-30T19:00:04Z)
• Multi-view Bayesian optimisation in reduced dimension for engineering design [0.9626666671366836]
  目的あるいは制約関数を表す入力設計変数と出力データの両方を考慮した多視点学習戦略を導入する。 確率的最小二乗(PPLS)を用いて,設計変数から潜伏変数への直交写像を学習する。 提案した確率論的最小二乗ベイズ最適化(PPLS-BO)戦略を,その決定論的手法,部分最小二乗ベイズ最適化(PLS-BO)および古典的ベイズ最適化と比較した。
  論文  参考訳（メタデータ） (2025-01-02T22:03:00Z)
• Delta-AI: Local objectives for amortized inference in sparse graphical models [64.5938437823851]
  スパース確率的グラフィカルモデル(PGM)における補正推論のための新しいアルゴリズムを提案する。 提案手法は, PGMにおける変数のサンプリングをエージェントが行う一連の行動とみなす場合, エージェントのポリシー学習目的において, PGMの疎結合が局所的な信用割当を可能にするという観察に基づいている。 合成PGMからサンプリングし、スパース因子構造を持つ潜在変数モデルを訓練するための$Delta$-AIの有効性について説明する。
  論文  参考訳（メタデータ） (2023-10-03T20:37:03Z)
• Stochastic Approximation Approaches to Group Distributionally Robust Optimization and Beyond [89.72693227960274]
  本稿では,グループ分散ロバスト最適化 (GDRO) を,$m$以上の異なる分布をうまく処理するモデルを学習する目的で検討する。 各ラウンドのサンプル数を$m$から1に抑えるため、GDROを2人でプレイするゲームとして、一方のプレイヤーが実行し、他方のプレイヤーが非公開のマルチアームバンディットのオンラインアルゴリズムを実行する。 第2のシナリオでは、最大リスクではなく、平均的最上位k$リスクを最適化し、分散の影響を軽減することを提案する。
  論文  参考訳（メタデータ） (2023-02-18T09:24:15Z)
• Symmetric Tensor Networks for Generative Modeling and Constrained Combinatorial Optimization [72.41480594026815]
  ポートフォリオ最適化からロジスティクスに至るまで、制約付き最適化問題は業界に多い。 これらの問題の解決における主要な障害の1つは、有効な検索空間を制限する非自明なハード制約の存在である。 本研究では、Ax=bという形の任意の整数値等式制約をU(1)対称ネットワーク(TN)に直接エンコードし、それらの適用性を量子に着想を得た生成モデルとして活用する。
  論文  参考訳（メタデータ） (2022-11-16T18:59:54Z)
• Transformers meet Stochastic Block Models: Attention with Data-Adaptive Sparsity and Cost [53.746169882193456]
  最近の研究は、自己注意の二次的コストを克服するために、様々なスパークアテンションモジュールを提案している。 本稿では,それぞれの注意を混合メンバーシップブロックモデルで表現することで,両方の問題を解決するモデルを提案する。 我々のモデルは、以前の効率的な変種とオリジナルのトランスフォーマーより優れており、十分に注目されています。
  論文  参考訳（メタデータ） (2022-10-27T15:30:52Z)
• Federated Learning Using Variance Reduced Stochastic Gradient for Probabilistically Activated Agents [0.0]
  本稿では,各エージェントが各反復において任意の選択の確率を持つような最適解に対して,分散低減と高速収束率の両方を達成する2層構造を持つフェデレートラーニング(FL)のアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2022-10-25T22:04:49Z)
• GEO: Enhancing Combinatorial Optimization with Classical and Quantum Generative Models [62.997667081978825]
  我々は、生成モデルとして知られる機械学習モデルを活用する新しいフレームワークを導入し、最適化問題を解決する。 我々は、テンソルネットワークマシンに依存するGEOの量子インスパイアされたバージョンに注力する。 関数呼び出し数に対する固定予算が与えられた場合、その目標が最小限の最小値を求める場合、その優れた性能を示す。
  論文  参考訳（メタデータ） (2021-01-15T18:18:38Z)

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

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