論文の概要: Harnessing the edge of chaos for combinatorial optimization

• arxiv url: http://arxiv.org/abs/2508.17655v2
• Date: Tue, 26 Aug 2025 04:05:59 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-08-27 13:17:04.075544
• Title: Harnessing the edge of chaos for combinatorial optimization
• Title（参考訳）: 組合せ最適化のためのカオスのエッジの調和
• Authors: Hayato Goto, Ryo Hidaka, Kosuke Tatsumura,
• Abstract要約: シミュレーション分岐 (SB) により, 大規模問題に対してほぼ100%の成功確率が得られることを示す。 2,000変数問題に対する解法時間は、GSBベースのマシンにより10ミリ秒に短縮される。
• 参考スコア（独自算出の注目度）: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Nonlinear dynamical systems with continuous variables can be used for solving combinatorial optimization problems with discrete variables. In particular, numerical simulations of them can be used as heuristic algorithms with a desirable property, namely, parallelizability, which allows us to execute them in a massively parallel manner using cutting-edge many-core processors, leading to ultrafast performance. However, the dynamical-system approaches with continuous variables are usually less accurate than conventional approaches with discrete variables such as simulated annealing. To improve the solution accuracy of a representative dynamical system-based algorithm called simulated bifurcation (SB), which was found from classical simulation of a quantum nonlinear oscillator network exhibiting quantum bifurcation, here we generalize it by introducing nonlinear control of individual bifurcation parameters and show that the generalized SB (GSB) can achieve almost 100% success probabilities for some large-scale problems. As a result, the time to solution for a 2,000-variable problem is shortened to 10 ms by a GSB-based machine, which is two orders of magnitude shorter than the best known value, 1.3 s, previously obtained by an SB-based machine. To examine the reason for the ultrahigh performance, we investigated chaos in the GSB changing the nonlinear-control strength and found that the dramatic increase of success probabilities happens near the edge of chaos. That is, the GSB can find a solution with high probability by harnessing the edge of chaos. This finding suggests that dynamical-system approaches to combinatorial optimization will be enhanced by harnessing the edge of chaos, opening a broad possibility to tackle intractable combinatorial optimization problems by nature-inspired approaches.
• Abstract（参考訳）: 連続変数を持つ非線形力学系は、離散変数との組合せ最適化問題を解くのに利用できる。 特に、これらの数値シミュレーションは、並列化性という望ましい特性を持つヒューリスティックなアルゴリズムとして使用することができ、これにより、最先端のマルチコアプロセッサを用いて並列に実行でき、超高速な性能を実現することができる。 しかし、連続変数を持つ力学系アプローチは、通常、シミュレーションアニールのような離散変数を持つ従来のアプローチよりも正確ではない。 量子分岐を示す量子非線形発振器ネットワークの古典的シミュレーションから得られたSB(simulated bifurcation)と呼ばれる代表力学系に基づくアルゴリズムの解の精度を改善するために、個別分岐パラメータの非線形制御を導入して一般化SB(GSB)が大規模問題に対してほぼ100%の成功確率を達成することを示す。 その結果、2000変数問題に対する解法時間は、GSBベースのマシンによって10ミリ秒に短縮され、これはSBベースのマシンで以前に取得した最もよく知られた値である1.3秒よりも2桁短い。 超高機能化の理由を検討するために,非線形制御強度を変化させるGSBのカオスを調査し,カオスの端付近で成功確率の劇的な増加が生じることを示した。 すなわち、GSBはカオスの端を利用することによって、高い確率で解を見つけることができる。 この発見は、カオスのエッジを活用することで、結合最適化に対する動的システムアプローチが強化されることを示唆し、自然に着想を得たアプローチによって、難解な組合せ最適化問題に取り組む可能性を広げている。

関連論文リスト

• Go With the Flow: Fast Diffusion for Gaussian Mixture Models [16.07896640031724]
  シュロディンガーブリッジ (Schrodinger Bridges, SBs) は、有限時間で操る拡散過程であり、与えられた初期分布を、適切なコスト関数を最小化する。 そこで本研究では,低次元問題を解くための一組の実行可能なポリシーの解析的パラメトリゼーションを提案する。 本稿では,オートエンコーダの潜伏空間における画像から画像への変換,マルチマージ運動量SB問題を用いたセルダイナミクスの学習など,低画像化におけるこのアプローチの可能性を示す。
  論文  参考訳（メタデータ） (2024-12-12T08:40:22Z)
• Provable Accuracy Bounds for Hybrid Dynamical Optimization and Sampling [1.5551894637785635]
  本稿では,Langevin Diffusion (BLD) アルゴリズムをブロックすることにより,ハイブリッド LNLS の非漸近収束を保証する。 デバイスの変化が有限であれば、ステップ時間、雑音強度、関数パラメータの2-ワッサーシュタインバイアスに明確な境界を与える。
  論文  参考訳（メタデータ） (2024-10-08T22:03:41Z)
• Analysis of the Non-variational Quantum Walk-based Optimisation Algorithm [0.0]
  本稿では,多種多様な最適化問題を解くために設計された非変分量子アルゴリズムを詳細に紹介する。 このアルゴリズムは、増幅状態の繰り返しの準備と測定から最適解とほぼ最適解を返す。
  論文  参考訳（メタデータ） (2024-07-29T13:54:28Z)
• Accelerated First-Order Optimization under Nonlinear Constraints [61.98523595657983]
  我々は、制約付き最適化のための一階アルゴリズムと非滑らかなシステムの間で、新しい一階アルゴリズムのクラスを設計する。 これらのアルゴリズムの重要な性質は、制約がスパース変数の代わりに速度で表されることである。
  論文  参考訳（メタデータ） (2023-02-01T08:50:48Z)
• Faster Algorithm and Sharper Analysis for Constrained Markov Decision Process [56.55075925645864]
  制約付き意思決定プロセス (CMDP) の問題点について検討し, エージェントは, 複数の制約を条件として, 期待される累積割引報酬を最大化することを目的とする。 新しいユーティリティ・デュアル凸法は、正規化ポリシー、双対正則化、ネステロフの勾配降下双対という3つの要素の新たな統合によって提案される。 これは、凸制約を受ける全ての複雑性最適化に対して、非凸CMDP問題が$mathcal O (1/epsilon)$の低い境界に達する最初の実演である。
  論文  参考訳（メタデータ） (2021-10-20T02:57:21Z)
• High Probability Complexity Bounds for Non-Smooth Stochastic Optimization with Heavy-Tailed Noise [51.31435087414348]
  アルゴリズムが高い確率で小さな客観的残差を与えることを理論的に保証することが不可欠である。 非滑らか凸最適化の既存の方法は、信頼度に依存した複雑性境界を持つ。 そこで我々は,勾配クリッピングを伴う2つの手法に対して,新たなステップサイズルールを提案する。
  論文  参考訳（メタデータ） (2021-06-10T17:54:21Z)
• Adaptive pruning-based optimization of parameterized quantum circuits [62.997667081978825]
  Variisyハイブリッド量子古典アルゴリズムは、ノイズ中間量子デバイスの使用を最大化する強力なツールである。 我々は、変分量子アルゴリズムで使用されるそのようなアンサーゼを「効率的な回路訓練」(PECT)と呼ぶ戦略を提案する。 すべてのアンサッツパラメータを一度に最適化する代わりに、PECTは一連の変分アルゴリズムを起動する。
  論文  参考訳（メタデータ） (2020-10-01T18:14:11Z)

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

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