論文の概要: Improved Runtime Analysis of a Multi-Valued Compact Genetic Algorithm on Two Generalized OneMax Problems
- arxiv url: http://arxiv.org/abs/2503.21439v1
- Date: Thu, 27 Mar 2025 12:32:15 GMT
- ステータス: 翻訳完了
- システム内更新日: 2025-03-28 12:54:16.093282
- Title: Improved Runtime Analysis of a Multi-Valued Compact Genetic Algorithm on Two Generalized OneMax Problems
- Title（参考訳）: 2つの一般化された1Max問題に対する多値コンパクト遺伝的アルゴリズムの実行時解析の改善
- Authors: Sumit Adak, Carsten Witt,
- Abstract要約: G-OneMax関数上の多値cGA(r-cGA)の最初の理論的解析を行った。
ランタイムは高い確率でO(nr3 log2 n log r)であることを示す。
また,r-OneMax上でのr-cGAのランタイム解析を改良する。
- 参考スコア（独自算出の注目度）: 2.07180164747172
- License:
- Abstract: Recent research in the runtime analysis of estimation of distribution algorithms (EDAs) has focused on univariate EDAs for multi-valued decision variables. In particular, the runtime of the multi-valued cGA (r-cGA) and UMDA on multi-valued functions has been a significant area of study. Adak and Witt (PPSN 2024) and Hamano et al. (ECJ 2024) independently performed a first runtime analysis of the r-cGA on the r-valued OneMax function (r-OneMax). Adak and Witt also introduced a different r-valued OneMax function called G-OneMax. However, for that function, only empirical results were provided so far due to the increased complexity of its runtime analysis, since r-OneMax involves categorical values of two types only, while G-OneMax encompasses all possible values. In this paper, we present the first theoretical runtime analysis of the r-cGA on the G-OneMax function. We demonstrate that the runtime is O(nr^3 log^2 n log r) with high probability. Additionally, we refine the previously established runtime analysis of the r-cGA on r-OneMax, improving the previous bound to O(nr log n log r), which improves the state of the art by an asymptotic factor of log n and is tight for the binary case. Moreover, we for the first time include the case of frequency borders.
- Abstract（参考訳）: 分散アルゴリズム(EDAs)のランタイム解析における最近の研究は、多値決定変数に対する一変量EDAに着目している。
特に,多値関数における多値cGA(r-cGA)とUMDAのランタイムは重要な研究領域である。
Adak and Witt (PPSN 2024) と Hamano et al (ECJ 2024) は独立に、r値の OneMax 関数 (r-OneMax) 上の r-cGA の最初のランタイム解析を行った。
アダックとウィットは、G-OneMaxと呼ばれる異なるr値のOneMax関数も導入した。
しかし、この関数については、r-OneMaxは2つの型の分類値のみを含むのに対し、G-OneMaxは全ての可能な値を含むため、実行時解析の複雑さが増すため、これまで経験的な結果しか提供されなかった。
本稿では,G-OneMax関数上でのr-cGAの理論的ランタイム解析について述べる。
ランタイムは高い確率でO(nr^3 log^2 n log r)であることが示される。
さらに,r-OneMax上でのr-cGAのランタイム解析を改良し,従来のO(nr log n log r)とのバウンドを改善した。
また,周波数境界の場合も初めて含む。
関連論文リスト
- Runtime Analysis of the Compact Genetic Algorithm on the LeadingOnes Benchmark [9.044970217182117]
我々はLeadingOnes上でcGAの正式なランタイム解析を行う。
cGAの1つのパラメータ -- 仮説的な集団サイズと呼ばれる -- は、少なくとも問題サイズよりも多義的に大きい -- に対して、cGAがLeadingOnesの最適値をサンプリングしていることを証明する。
論文 参考訳（メタデータ） (2025-01-27T17:51:51Z) - A Runtime Analysis of the Multi-Valued Compact Genetic Algorithm on Generalized LeadingOnes [2.07180164747172]
我々は,r値のLeadingOnes関数上での複数値cGAのランタイム解析を行った。
r-LeadingOnes上のr-cGAのランタイムは、高い確率でO(n2r2 log3 n log2 r)であることが示される。
論文 参考訳（メタデータ） (2025-01-16T12:59:07Z) - 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) - Fixed-Budget Real-Valued Combinatorial Pure Exploration of Multi-Armed
Bandit [65.268245109828]
このアルゴリズムは,アクションクラスのサイズが指数関数的に大きい場合でも,最良のアクションを識別できる最初のアルゴリズムである。
CSAアルゴリズムの誤差確率の上限は指数の対数係数までの下界と一致することを示す。
提案手法を従来手法と実験的に比較し,アルゴリズムの性能が向上したことを示す。
論文 参考訳（メタデータ） (2023-10-24T09:47:32Z) - Improved Convergence Rate of Stochastic Gradient Langevin Dynamics with
Variance Reduction and its Application to Optimization [50.83356836818667]
勾配ランゲヴィン・ダイナミクスは非エプス最適化問題を解くための最も基本的なアルゴリズムの1つである。
本稿では、このタイプの2つの変種、すなわち、分散還元ランジュバンダイナミクスと再帰勾配ランジュバンダイナミクスを示す。
論文 参考訳（メタデータ） (2022-03-30T11:39:00Z) - Efficient Algorithms for Extreme Bandits [20.68824391770909]
我々は,学習者が最大の報酬を集めようとするマルチアーマッド・バンディットの変種であるExtreme Bandit問題に貢献する。
まず、報酬分布の尾部における軽度の仮定の下で、i.d確率変数の最大値の濃度について検討する。
次に,より適応性の高いQoMax-SDAアルゴリズムを提案し,解析する。
論文 参考訳（メタデータ） (2022-03-21T11:09:34Z) - Breaking the Linear Iteration Cost Barrier for Some Well-known
Conditional Gradient Methods Using MaxIP Data-structures [49.73889315176884]
条件勾配法(CGM)は現代の機械学習で広く使われている。
ほとんどの取り組みは、全体の実行時間を短縮する手段として、イテレーションの数を減らすことに重点を置いています。
本稿では,多くの基本最適化アルゴリズムに対して,イテレーション毎のコストがパラメータ数にサブ線形である最初のアルゴリズムを示す。
論文 参考訳（メタデータ） (2021-11-30T05:40:14Z) - Predicting parameters for the Quantum Approximate Optimization Algorithm
for MAX-CUT from the infinite-size limit [0.05076419064097732]
推定次数$d$のランダムエルドス・レーニグラフに適用したMAX-CUT上でのQAOAの性能を評価するための明示的なアルゴリズムを提案する。
この解析により、エルドス・レーニグラフ上のMAX-CUTのQAOAパラメータとシェリントン・カークパトリックモデルとの明示的なマッピングが得られる。
論文 参考訳（メタデータ） (2021-10-20T17:58:53Z) - Result Diversification by Multi-objective Evolutionary Algorithms with
Theoretical Guarantees [94.72461292387146]
両目的探索問題として結果の多様化問題を再構成し,多目的進化アルゴリズム(EA)を用いて解くことを提案する。
GSEMOが最適時間近似比1/2$を達成できることを理論的に証明する。
目的関数が動的に変化すると、GSEMOはこの近似比をランニングタイムで維持することができ、Borodinらによって提案されたオープンな問題に対処する。
論文 参考訳（メタデータ） (2021-10-18T14:00:22Z) - ROOT-SGD: Sharp Nonasymptotics and Near-Optimal Asymptotics in a Single Algorithm [71.13558000599839]
第一次アルゴリズムを用いて,厳密な凸と滑らかな非制約最適化問題の解法について検討する。
我々は,過去の勾配を平均化し,実装が容易な小説「Recursive One-Over-T SGD」を考案した。
有限サンプル, 漸近感覚, 感覚の両面において, 最先端の性能を同時に達成できることを実証する。
論文 参考訳（メタデータ） (2020-08-28T14:46:56Z) - Fast Objective & Duality Gap Convergence for Non-Convex Strongly-Concave
Min-Max Problems with PL Condition [52.08417569774822]
本稿では,深層学習(深層AUC)により注目度が高まっている,円滑な非凹部min-max問題の解法に焦点をあてる。
論文 参考訳（メタデータ） (2020-06-12T00:32:21Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。