論文の概要: Enhanced Convergence in p-bit Based Simulated Annealing with Partial Deactivation for Large-Scale Combinatorial Optimization Problems

• arxiv url: http://arxiv.org/abs/2601.15561v1
• Date: Thu, 22 Jan 2026 01:01:35 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-01-23 21:37:20.46262
• Title: Enhanced Convergence in p-bit Based Simulated Annealing with Partial Deactivation for Large-Scale Combinatorial Optimization Problems
• Title（参考訳）: 大規模組合せ最適化問題に対する部分的不活性化を用いたp-bit型シミュレーションアニールの収束性向上
• Authors: Naoya Onizawa, Takahiro Hanyu,
• Abstract要約: pビット間の予期せぬ振動に起因する問題について検討する。 これらの振動はイジングモデルのエネルギー削減を妨げ、複雑なタスクにおけるpSAの実行を妨げている。 時間平均pSA(TApSA)と停止pSA(SpSA)の2つの新しい手法を提案する。
• 参考スコア（独自算出の注目度）: 1.2375561840897742
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: This article critically investigates the limitations of the simulated annealing algorithm using probabilistic bits (pSA) in solving large-scale combinatorial optimization problems. The study begins with an in-depth analysis of the pSA process, focusing on the issues resulting from unexpected oscillations among p-bits. These oscillations hinder the energy reduction of the Ising model and thus obstruct the successful execution of pSA in complex tasks. Through detailed simulations, we unravel the root cause of this energy stagnation, identifying the feedback mechanism inherent to the pSA operation as the primary contributor to these disruptive oscillations. To address this challenge, we propose two novel algorithms, time average pSA (TApSA) and stalled pSA (SpSA). These algorithms are designed based on partial deactivation of p-bits and are thoroughly tested using Python simulations on maximum cut benchmarks that are typical combinatorial optimization problems. On the 16 benchmarks from 800 to 5,000 nodes, the proposed methods improve the normalized cut value from 0.8% to 98.4% on average in comparison with the conventional pSA.
• Abstract（参考訳）: 本稿では、大規模組合せ最適化問題の解法において、確率ビット(pSA)を用いたシミュレーションアニールアルゴリズムの限界を批判的に検討する。 この研究は、p-bit間の予期せぬ振動に起因する問題に焦点を当て、pSAプロセスの詳細な分析から始まった。 これらの振動はイジングモデルのエネルギー削減を妨げるため、複雑なタスクにおけるpSAの実行を妨げている。 詳細なシミュレーションにより、このエネルギー停滞の根本原因を解明し、これらの破壊的振動の主要因としてpSA操作に固有のフィードバック機構を同定した。 この課題に対処するために、時間平均pSA(TApSA)と停止pSA(SpSA)の2つの新しいアルゴリズムを提案する。 これらのアルゴリズムは、pビットの部分的不活性化に基づいて設計され、典型的な組合せ最適化問題である最大カットベンチマークでPythonシミュレーションを用いて徹底的にテストされる。 800ノードから5,000ノードまでの16のベンチマークでは、従来のpSAと比較して、通常のカット値が0.8%から98.4%に改善されている。

関連論文リスト

• LPBSA: Enhancing Optimization Efficiency through Learner Performance-based Behavior and Simulated Annealing [4.939986309170004]
  LPBSAは、Learner Performance-based Behavior (LPB)とSimulated Annealing (SA)をハイブリッドアプローチで組み合わせた高度な最適化アルゴリズムである。 LPBSAはLPBよりも優れた性能を示し、PSO、FDO、LEO、GAといった確立したアルゴリズムと競合する。
  論文  参考訳（メタデータ） (2024-12-23T16:57:47Z)
• Optimizing LPB Algorithms using Simulated Annealing [4.939986309170004]
  本研究は, 改良されたアルゴリズムの作業手順を, 主集団に提供し, 良質な集団と悪質な集団に分割することによって概説する。 その結果、人口が増加し、効率が向上し、PBSAの性能が検証された。
  論文  参考訳（メタデータ） (2024-12-22T13:17:26Z)
• Parameter optimization comparison in QAOA using Stochastic Hill Climbing with Random Re-starts and Local Search with entangled and non-entangled mixing operators [0.0]
  本研究では,Hill Climbing with Random Restarts (SHC-RR) の有効性を検討した。 以上の結果から,SHC-RRはLSアプローチよりも優れており,より単純な最適化機構にもかかわらず優れた有効性を示した。
  論文  参考訳（メタデータ） (2024-05-14T20:12:17Z)
• Fast Shapley Value Estimation: A Unified Approach [71.92014859992263]
  冗長な手法を排除し、単純で効率的なシェープリー推定器SimSHAPを提案する。 既存手法の解析において、推定器は特徴部分集合からランダムに要約された値の線形変換として統一可能であることを観察する。 実験により,SimSHAPの有効性が検証され,精度の高いShapley値の計算が大幅に高速化された。
  論文  参考訳（メタデータ） (2023-11-02T06:09:24Z)
• Provably Efficient UCB-type Algorithms For Learning Predictive State Representations [55.00359893021461]
  逐次決定問題は、予測状態表現(PSR)によってモデル化された低ランク構造が認められる場合、統計的に学習可能である 本稿では,推定モデルと実モデル間の全変動距離を上限とする新しいボーナス項を特徴とする,PSRに対する最初のUCB型アプローチを提案する。 PSRに対する既存のアプローチとは対照的に、UCB型アルゴリズムは計算的トラクタビリティ、最優先の準最適ポリシー、モデルの精度が保証される。
  論文  参考訳（メタデータ） (2023-07-01T18:35:21Z)
• A Deep Unrolling Model with Hybrid Optimization Structure for Hyperspectral Image Deconvolution [50.13564338607482]
  本稿では,DeepMixと呼ばれるハイパースペクトルデコンボリューション問題に対する新しい最適化フレームワークを提案する。 これは3つの異なるモジュール、すなわちデータ一貫性モジュール、手作りの正規化器の効果を強制するモジュール、および装飾モジュールで構成されている。 本研究は,他のモジュールの協調作業によって達成される進歩を維持するために設計された,文脈を考慮した認知型モジュールを提案する。
  論文  参考訳（メタデータ） (2023-06-10T08:25:16Z)
• Matching Pursuit Based Scheduling for Over-the-Air Federated Learning [67.59503935237676]
  本稿では,フェデレートラーニング手法を用いて,オーバー・ザ・エアラーニングのための低複雑さデバイススケジューリングアルゴリズムのクラスを開発する。 最先端の提案方式と比較すると,提案方式は極めて低効率なシステムである。 提案手法の有効性は,CIFARデータセットを用いた実験により確認した。
  論文  参考訳（メタデータ） (2022-06-14T08:14:14Z)
• Adaptive Sampling for Best Policy Identification in Markov Decision Processes [79.4957965474334]
  本稿では,学習者が生成モデルにアクセスできる場合の,割引マルコフ決定(MDP)における最良の政治的識別の問題について検討する。 最先端アルゴリズムの利点を論じ、解説する。
  論文  参考訳（メタデータ） (2020-09-28T15:22:24Z)
• Statistical Efficiency of Thompson Sampling for Combinatorial Semi-Bandits [56.31950477139053]
  半帯域フィードバック(CMAB)を用いたマルチアームバンディットの検討 我々は Combinatorial Thompson Smpling Policy (CTS) の変種を解析する。 この最終結果は,Y Combinatorial Bandit Policy (ESCB) の効率的なサンプリングに代わるものだ。
  論文  参考訳（メタデータ） (2020-06-11T17:12:11Z)

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

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