論文の概要: A Runtime Analysis of the Multi-Valued Compact Genetic Algorithm on Generalized LeadingOnes

• arxiv url: http://arxiv.org/abs/2501.09514v2
• Date: Thu, 23 Jan 2025 10:37:42 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-01-24 15:56:52.433665
• Title: A Runtime Analysis of the Multi-Valued Compact Genetic Algorithm on Generalized LeadingOnes
• Title（参考訳）: 一般化リードワンを用いた多値コンパクト遺伝的アルゴリズムの実行時解析
• Authors: Sumit Adak, Carsten Witt,
• Abstract要約: 我々は,r値のLeadingOnes関数上での複数値cGAのランタイム解析を行った。 r-LeadingOnes上のr-cGAのランタイムは、高い確率でO(n2r2 log3 n log2 r)であることが示される。
• 参考スコア（独自算出の注目度）: 2.07180164747172
• License:
• Abstract: In the literature on runtime analyses of estimation of distribution algorithms (EDAs), researchers have recently explored univariate EDAs for multi-valued decision variables. Particularly, Jedidia et al. gave the first runtime analysis of the multi-valued UMDA on the r-valued LeadingOnes (r-LeadingOnes) functions and Adak et al. gave the first runtime analysis of the multi-valued cGA (r-cGA) on the r-valued OneMax function. We utilize their framework to conduct an analysis of the multi-valued cGA on the r-valued LeadingOnes function. Even for the binary case, a runtime analysis of the classical cGA on LeadingOnes was not yet available. In this work, we show that the runtime of the r-cGA on r-LeadingOnes is O(n^2r^2 log^3 n log^2 r) with high probability.
• Abstract（参考訳）: 分散アルゴリズム(EDAs)の推定のランタイム解析に関する文献において、研究者は近年、多値決定変数に対する一変量EDAについて検討している。 特にJedidiaらは、r値のLeadingOnes(r-LeadingOnes)関数上で、UMDAの最初のランタイム解析を行い、Adakらはr値のOneMax関数上で、複数の値のcGA(r-cGA)の最初のランタイム解析を行った。 我々は,それらのフレームワークを用いて,r値のLeadingOnes関数上の多値cGAの分析を行う。 バイナリの場合でさえ、LeadingOnesの古典的なcGAのランタイム分析はまだ利用できなかった。 本稿では、r-LeadingOnes上のr-cGAのランタイムは、高い確率でO(n^2r^2 log^3 n log^2 r)であることが示される。

関連論文リスト

• Near-Tight Runtime Guarantees for Many-Objective Evolutionary Algorithms [10.165640083594573]
  従来のベンチマークでは,SEMO,グローバルSEMO,SMS-EMOAアルゴリズムのほぼ28のランタイム保証が証明されている。 このような厳密な境界がこれらのMOEAの多目的利用に対して証明されたのはこれが初めてである。
  論文  参考訳（メタデータ） (2024-04-19T09:46:59Z)
• 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)
• On the Stability and Generalization of Triplet Learning [55.75784102837832]
  トリプルトラーニング(トリプルトラーニング)、すなわちトリプルトデータから学ぶことは、コンピュータビジョンタスクに大きな注目を集めている。 本稿では,安定解析を利用した三重項学習の一般化保証について検討する。
  論文  参考訳（メタデータ） (2023-02-20T07:32:50Z)
• A Mathematical Runtime Analysis of the Non-dominated Sorting Genetic Algorithm III (NSGA-III) [9.853329403413701]
  NSGA-II (Non-Maninated Sorting Genetic Algorithm II) は、実世界の応用において最も顕著な多目的進化アルゴリズムである。 NSGA-IIIは2つ以上の目的をうまく扱うことを目的としたNSGA-IIの改良である。
  論文  参考訳（メタデータ） (2022-11-15T15:10:36Z)
• 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)
• Multi-task Learning of Order-Consistent Causal Graphs [59.9575145128345]
  我々は、$K関連ガウス非巡回グラフ(DAG)の発見問題を考える。 マルチタスク学習環境下では, 線形構造方程式モデルを学習するためのMLE ($l_1/l$-regularized maximum chance estimator) を提案する。 理論的には、関係するタスクにまたがるデータを活用することで、因果順序を復元する際のサンプルの複雑さをより高めることができることを示す。
  論文  参考訳（メタデータ） (2021-11-03T22:10:18Z)
• A general sample complexity analysis of vanilla policy gradient [101.16957584135767]
  政策勾配(PG)は、最も一般的な強化学習(RL)問題の1つである。 PG軌道の「バニラ」理論的理解は、RL問題を解く最も一般的な方法の1つである。
  論文  参考訳（メタデータ） (2021-07-23T19:38:17Z)
• Revisiting the Complexity Analysis of Conflict-Based Search: New Computational Techniques and Improved Bounds [5.158632635415881]
  最適解に対する最先端のアプローチは Conflict-Based Search (CBS) である CBSの複雑性分析を再検討し、最悪の場合のアルゴリズムの実行時間に厳密な制限を与える。
  論文  参考訳（メタデータ） (2021-04-18T07:46:28Z)
• Approximation Algorithms for Sparse Principal Component Analysis [57.5357874512594]
  主成分分析(PCA)は、機械学習と統計学において広く使われている次元削減手法である。 スパース主成分分析(Sparse principal Component Analysis)と呼ばれる,スパース主成分負荷を求める様々な手法が提案されている。 本研究では,SPCA問題に対するしきい値の精度,時間,近似アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2020-06-23T04:25:36Z)
• On the Convergence Rate of Projected Gradient Descent for a Back-Projection based Objective [58.33065918353532]
  我々は、最小二乗(LS)の代替として、バックプロジェクションに基づく忠実度項を考える。 LS項ではなくBP項を用いることで最適化アルゴリズムの繰り返しを少なくすることを示す。
  論文  参考訳（メタデータ） (2020-05-03T00:58:23Z)
• A Simplified Run Time Analysis of the Univariate Marginal Distribution Algorithm on LeadingOnes [9.853329403413701]
  単変量分布アルゴリズム(UMDA)における実行時間保証の強化を実証する。 より少ない選択率によるランタイムゲインを示す。 同様の仮定の下では、我々の上界と定数因子に一致する境界が高い確率で成り立つことを証明している。
  論文  参考訳（メタデータ） (2020-04-10T10:20:05Z)

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

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