論文の概要: Generalization and Completeness of Stochastic Local Search Algorithms

• arxiv url: http://arxiv.org/abs/2601.14212v1
• Date: Tue, 20 Jan 2026 18:17:45 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-01-21 22:47:23.447587
• Title: Generalization and Completeness of Stochastic Local Search Algorithms
• Title（参考訳）: 確率的局所探索アルゴリズムの一般化と完全性
• Authors: Daniel Loscos, Narciso Marti-Oliet, Ismael Rodriguez,
• Abstract要約: 局所探索(SLS)アルゴリズムを一意な形式モデルに一般化する。 このモデルには、2つの重要な構成要素がある: できるだけ大きいように設計された共通構造と、できるだけ小さいことを意図したパラメトリック構造である。 SLSアルゴリズムのチューリング完全性を証明するために,本モデルを用いた。
• 参考スコア（独自算出の注目度）: 0.0
• License: http://creativecommons.org/licenses/by-nc-nd/4.0/
• Abstract: We generalize Stochastic Local Search (SLS) heuristics into a unique formal model. This model has two key components: a common structure designed to be as large as possible and a parametric structure intended to be as small as possible. Each heuristic is obtained by instantiating the parametric part in a different way. Particular instances for Genetic Algorithms (GA), Ant Colony Optimization (ACO), and Particle Swarm Optimization (PSO) are presented. Then, we use our model to prove the Turing-completeness of SLS algorithms in general. The proof uses our framework to construct a GA able to simulate any Turing machine. This Turing-completeness implies that determining any non-trivial property concerning the relationship between the inputs and the computed outputs is undecidable for GA and, by extension, for the general set of SLS methods (although not necessarily for each particular method). Similar proofs are more informally presented for PSO and ACO.
• Abstract（参考訳）: 確率的局所探索(SLS)ヒューリスティックスを独自の形式モデルに一般化する。 このモデルには、2つの重要な構成要素がある: できるだけ大きいように設計された共通構造と、できるだけ小さいことを意図したパラメトリック構造である。 各ヒューリスティックは、パラメトリック部分を異なる方法でインスタンス化することによって得られる。 遺伝的アルゴリズム(GA)、アントコロニー最適化(ACO)、粒子群最適化(PSO)について述べる。 次に,SLSアルゴリズムのチューリング完全性を証明するために,本モデルを用いた。 この証明は我々のフレームワークを用いて任意のチューリングマシンをシミュレートできるGAを構築する。 このチューリング完全性は、入力と計算された出力の関係に関するどんな非自明な性質もGAでは決定不能であり、拡張によってSLS法の一般的な集合に対しては決定不能であることを意味する(ただし、それぞれのメソッドでは必ずしもそうではない)。 同様の証明はより非公式に PSO と ACO に提示される。

関連論文リスト

• Computational-Statistical Gaps in Gaussian Single-Index Models [77.1473134227844]
  単次元モデル(Single-Index Models)は、植木構造における高次元回帰問題である。 我々は,統計的クエリ (SQ) と低遅延多項式 (LDP) フレームワークの両方において,計算効率のよいアルゴリズムが必ずしも$Omega(dkstar/2)$サンプルを必要とすることを示した。
  論文  参考訳（メタデータ） (2024-03-08T18:50:19Z)
• LieDetect: Detection of representation orbits of compact Lie groups from point clouds [0.0]
  我々は、その軌道の有限標本からコンパクトリー群の表現を推定する新しいアルゴリズムを提案する。 表現型の知識は、その軌道の再構成を可能にするが、これは作用を生成するリー群を特定するのに役立つ。 このアルゴリズムは, 画像解析, 調和解析, 密度推定, 等変ニューラルネットワーク, 化学コンフォメーション空間, 古典力学システムにおける実時間応用と同様に, 次元32までの合成データに対して試験される。
  論文  参考訳（メタデータ） (2023-07-26T18:32:43Z)
• Amortized Inference for Causal Structure Learning [72.84105256353801]
  因果構造を学習することは、通常、スコアまたは独立テストを使用して構造を評価することを伴う探索問題を引き起こす。 本研究では,観測・干渉データから因果構造を予測するため,変分推論モデルを訓練する。 我々のモデルは、実質的な分布シフトの下で頑健な一般化能力を示す。
  論文  参考訳（メタデータ） (2022-05-25T17:37:08Z)
• Formalization of a Stochastic Approximation Theorem [0.22940141855172028]
  近似アルゴリズムは、ターゲットが不明な環境でターゲット値を近似するために使用される反復的な手順である。 もともとは1951年にRobinsとMonroによって発表された論文で、近似の分野は飛躍的に成長し、応用領域に影響を与えている。
  論文  参考訳（メタデータ） (2022-02-12T02:31:14Z)
• Statistically Meaningful Approximation: a Case Study on Approximating Turing Machines with Transformers [50.85524803885483]
  本研究は,統計的学習性を示すために近似ネットワークを必要とする統計有意(SM)近似の形式的定義を提案する。 回路とチューリングマシンの2つの機能クラスに対するSM近似について検討する。
  論文  参考訳（メタデータ） (2021-07-28T04:28:55Z)
• Dynamic programming by polymorphic semiring algebraic shortcut fusion [1.9405875431318445]
  動的プログラミング(動的プログラミング、英: Dynamic Programming、DP)は、難解問題の効率的かつ正確な解法のためのアルゴリズム設計パラダイムである。 本稿では,セミリングに基づくDPアルゴリズムを体系的に導出するための厳密な代数形式について述べる。
  論文  参考訳（メタデータ） (2021-07-05T00:51:02Z)
• Fractal Structure and Generalization Properties of Stochastic Optimization Algorithms [71.62575565990502]
  最適化アルゴリズムの一般化誤差は、その一般化尺度の根底にあるフラクタル構造の複雑性'にバウンドできることを示す。 さらに、特定の問題(リニア/ロジスティックレグレッション、隠れ/層ニューラルネットワークなど)とアルゴリズムに対して、結果をさらに専門化します。
  論文  参考訳（メタデータ） (2021-06-09T08:05:36Z)

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

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