論文の概要: Runtime Analysis of a Compact Genetic Algorithm on a Truly Multi-valued OneMax Function

• arxiv url: http://arxiv.org/abs/2605.29477v2
• Date: Mon, 01 Jun 2026 13:55:11 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-06-02 18:24:16.734673
• Title: Runtime Analysis of a Compact Genetic Algorithm on a Truly Multi-valued OneMax Function
• Title（参考訳）: 完全多値OneMax関数を用いたコンパクト遺伝的アルゴリズムの実行時解析
• Authors: Martin S. Krejca, Carsten Witt,
• Abstract要約: Adak and Witt (GECCO 2025) は、多値のOneMax関数上でのcGA (multi-valued compact genetic algorithm) の最初のランタイム解析を発表した。 アップデートの強度の最適な選択は、$textrmObigl(n r3 log2, n)log (r)bigr)$から$textrmObigl(n rlog3(n)log3(r)bigr)$に改善します。
• 参考スコア（独自算出の注目度）: 5.478764356647438
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Recently, the runtime analysis of multi-valued estimation-of-distribution algorithms in the framework of Ben Jedidia et al. (TCS 2024) has made significant advancements. However, almost all existing analyses are limited to multi-valued objective functions that in each dimension only distinguish between two types, also called categories, of values and hence can be treated with similar methods as pseudo-Boolean problems. Only recently, Adak and Witt (GECCO 2025) have presented a first runtime analysis of a multi-valued compact genetic algorithm (cGA) on the multi-valued OneMax function G-OneMax$\colon \{0,\dots,r-1\}^n \to \mathbf{N}$ defined by G-OneMax$(x_1,\dots,x_n)=\sum_{i=1}^n {x}_i$ and truly depending on all $r$ categories. We improve their runtime result from $\textrm{O}\bigl(n r^3 \log^2( n)\log (r)\bigr)$ to $\textrm{O}\bigl(n r \log^3(n)\log^3(r)\bigr)$, both for an optimal choice of the update strength $K$. Our result matches, up to polylogarithmic factors, the existing bound for the simpler $r$-valued OneMax function depending essentially only on two values and analyzed in several previous works. To show the new bound, we use improved drift theorems for processes with high self-loop probabilities and specifically derived concentration inequalities to analyze how probability mass in the multi-valued cGA moves into successively smaller and smaller intervals of the $r$-valued frequency matrix.
• Abstract（参考訳）: 近年,Ben Jedidia et al (TCS 2024) のフレームワークにおける多値分布推定アルゴリズムのランタイム解析が大幅に進歩している。 しかし、既存のほとんどの分析は多値目的関数に限られており、各次元において、値の圏と呼ばれる2つの型を区別するだけで、従って擬ブール問題と同様の方法で扱うことができる。 つい最近になって、Adak and Witt (GECCO 2025) は、G-OneMax 関数 G-OneMax$\colon \{0,\dots,r-1\}^n \to \mathbf{N}$ を G-OneMax$(x_1,\dots,x_n)=\sum_{i=1}^n {x}_i$ で定義し、真にすべての$r$ のカテゴリに依存する、多値コンパクト遺伝アルゴリズム (cGA) の最初のランタイム解析を発表した。 我々は、その実行結果を $\textrm{O}\bigl(n r^3 \log^2(n)\log (r)\bigr)$から $\textrm{O}\bigl(n r \log^3(n)\log^3(r)\bigr)$に改善する。 以上の結果から,より単純な$r$値のOneMax関数に対する既存の境界は,基本的に2つの値にのみ依存し,いくつかの先行研究で解析された。 新しい境界を示すために、高自己ループ確率および特に誘導された濃度不等式を持つプロセスに対して改良されたドリフト定理を用いて、多値cGAの確率質量が$r$値の周波数行列の連続的に小さい間隔に移動するかを分析する。

関連論文リスト

• First Mathematical Runtime Analyses of Multi-Objective Evolutionary Algorithms for Multi-Valued Decision Variables [23.47753638129204]
  二項決定空間上で定義された問題は、多目的進化アルゴリズムの理論において集中的に研究されている。 有限値 $r > 2$ の値を取る決定変数を扱うMOEAには、今のところ数学的ランタイム解析は存在しない。 多値決定変数を扱う場合、古典的MOEAは重大な問題に遭遇しないことが示される。
  論文  参考訳（メタデータ） (2026-05-14T13:42:52Z)
• Improved Runtime Analysis of a Multi-Valued Compact Genetic Algorithm on Two Generalized OneMax Problems [2.07180164747172]
  G-OneMax関数上の多値cGA(r-cGA)の最初の理論的解析を行った。 ランタイムは高い確率でO(nr3 log2 n log r)であることを示す。 また,r-OneMax上でのr-cGAのランタイム解析を改良する。
  論文  参考訳（メタデータ） (2025-03-27T12:32:15Z)
• SoS Certificates for Sparse Singular Values and Their Applications: Robust Statistics, Subspace Distortion, and More [37.208622097149714]
  我々は、最大$|M u|$で境界を証明できる新しいアップタイムアルゴリズムの族を与える。 我々の認証アルゴリズムは, Sum-of-Squares階層を必須に活用する。
  論文  参考訳（メタデータ） (2024-12-30T18:59:46Z)
• Runtime Analysis of a Multi-Valued Compact Genetic Algorithm on Generalized OneMax [2.07180164747172]
  一般化されたOneMax関数の最初のランタイム解析を提供する。 r-cGAはこのr値のOneMax問題を効率的に解くことを示す。 実験の最後には、多値OneMax関数の別の変種が期待されるランタイムに関する予想を述べる。
  論文  参考訳（メタデータ） (2024-04-17T10:40:12Z)
• Revisiting Inexact Fixed-Point Iterations for Min-Max Problems: Stochasticity and Structured Nonconvexity [18.427215139020632]
  1L 1$は、マルチレベルなCarloイテレーションであっても、最先端の問題を改善するために使用できることを示す。 解に関する唯一のホールドが新しい1L 1$理論である場合、不正確なハルパーネス推定器を1L 1$で解析する。
  論文  参考訳（メタデータ） (2024-02-07T18:22:41Z)
• Do you know what q-means? [42.96240569413475]
  古典的な$varepsilon$-$k$-meansアルゴリズムは、ロイドのアルゴリズムの1つの反復の近似バージョンを時間的複雑さで実行する。 また,時間的複雑さを考慮した$q$-means量子アルゴリズムも提案する。
  論文  参考訳（メタデータ） (2023-08-18T17:52:12Z)
• Provably Efficient Reinforcement Learning via Surprise Bound [66.15308700413814]
  本稿では,一般値関数近似を用いた効率の良い強化学習アルゴリズムを提案する。 本アルゴリズムは, 線形設定と疎高次元線形設定の両方に適用した場合に, 合理的な後悔境界を達成できる。
  論文  参考訳（メタデータ） (2023-02-22T20:21:25Z)
• TURF: A Two-factor, Universal, Robust, Fast Distribution Learning Algorithm [64.13217062232874]
  最も強力で成功したモダリティの1つは、全ての分布を$ell$距離に近似し、基本的に最も近い$t$-piece次数-$d_$の少なくとも1倍大きい。 本稿では,この数値をほぼ最適に推定する手法を提案する。
  論文  参考訳（メタデータ） (2022-02-15T03:49:28Z)
• Finding Global Minima via Kernel Approximations [90.42048080064849]
  関数評価のみに基づく滑らかな関数のグローバル最小化を考える。 本稿では,近似関数を共同でモデル化し,大域的最小値を求める手法を検討する。
  論文  参考訳（メタデータ） (2020-12-22T12:59:30Z)
• Hybrid Stochastic-Deterministic Minibatch Proximal Gradient: Less-Than-Single-Pass Optimization with Nearly Optimal Generalization [83.80460802169999]
  HSDMPGは、学習モデル上で過大なエラーの順序である$mathcalObig(1/sttnbig)$を達成可能であることを示す。 損失係数について、HSDMPGは学習モデル上で過大なエラーの順序である$mathcalObig(1/sttnbig)$を達成できることを示す。
  論文  参考訳（メタデータ） (2020-09-18T02:18:44Z)
• Streaming Complexity of SVMs [110.63976030971106]
  本稿では,ストリーミングモデルにおけるバイアス正規化SVM問題を解く際の空間複雑性について検討する。 両方の問題に対して、$frac1lambdaepsilon$の次元に対して、$frac1lambdaepsilon$よりも空間的に小さいストリーミングアルゴリズムを得ることができることを示す。
  論文  参考訳（メタデータ） (2020-07-07T17:10:00Z)

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

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