論文の概要: Runtime Analysis of the Compact Genetic Algorithm on the LeadingOnes Benchmark

• arxiv url: http://arxiv.org/abs/2501.16250v1
• Date: Mon, 27 Jan 2025 17:51:51 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-01-28 13:58:57.701947
• Title: Runtime Analysis of the Compact Genetic Algorithm on the LeadingOnes Benchmark
• Title（参考訳）: LeadingOnesベンチマークによるコンパクト遺伝的アルゴリズムの実行時解析
• Authors: Marcel Chwiałkowski, Benjamin Doerr, Martin S. Krejca,
• Abstract要約: 我々はLeadingOnes上でcGAの正式なランタイム解析を行う。 cGAの1つのパラメータ -- 仮説的な集団サイズと呼ばれる -- は、少なくとも問題サイズよりも多義的に大きい -- に対して、cGAがLeadingOnesの最適値をサンプリングしていることを証明する。
• 参考スコア（独自算出の注目度）: 9.044970217182117
• License:
• Abstract: The compact genetic algorithm (cGA) is one of the simplest estimation-of-distribution algorithms (EDAs). Next to the univariate marginal distribution algorithm (UMDA) -- another simple EDA -- , the cGA has been subject to extensive mathematical runtime analyses, often showcasing a similar or even superior performance to competing approaches. Surprisingly though, up to date and in contrast to the UMDA and many other heuristics, we lack a rigorous runtime analysis of the cGA on the LeadingOnes benchmark -- one of the most studied theory benchmarks in the domain of evolutionary computation. We fill this gap in the literature by conducting a formal runtime analysis of the cGA on LeadingOnes. For the cGA's single parameter -- called the hypothetical population size -- at least polylogarithmically larger than the problem size, we prove that the cGA samples the optimum of LeadingOnes with high probability within a number of function evaluations quasi-linear in the problem size and linear in the hypothetical population size. For the best hypothetical population size, our result matches, up to polylogarithmic factors, the typical quadratic runtime that many randomized search heuristics exhibit on LeadingOnes. Our analysis exhibits some noteworthy differences in the working principles of the two algorithms which were not visible in previous works.
• Abstract（参考訳）: コンパクト遺伝的アルゴリズム (cGA) は、最も単純な分布推定アルゴリズム(EDAs)の1つである。 もうひとつの単純なEDAであるUMDA(univariate marginal distribution algorithm)に続いて、cGAは広範な数学的ランタイム解析の対象となり、しばしば競合するアプローチと同等あるいはそれ以上のパフォーマンスを示す。 しかし、UMDAや他の多くのヒューリスティックスとは対照的に、私たちは進化計算の領域において最も研究されている理論ベンチマークの一つであるLeadingOnesベンチマークにおいて、cGAの厳密な実行時解析を欠いている。我々はこのギャップを、LeadingOnesのcGAの正式な実行時解析によって埋めている。 最も仮説的な人口規模では、多くのランダム化されたサーチヒューリスティックスがLeadingOnesで示している典型的な二次的ランタイムであるポリ対数的因子まで、結果が一致します。 この2つのアルゴリズムの動作原理には,従来の研究では見られなかった重要な違いがある。

関連論文リスト

• 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)
• AcceleratedLiNGAM: Learning Causal DAGs at the speed of GPUs [57.12929098407975]
  既存の因果探索法を効率的に並列化することにより,数千次元まで拡張可能であることを示す。 具体的には、DirectLiNGAMの因果順序付けサブプロデューサに着目し、GPUカーネルを実装して高速化する。 これにより、遺伝子介入による大規模遺伝子発現データに対する因果推論にDirectLiNGAMを適用することで、競争結果が得られる。
  論文  参考訳（メタデータ） (2024-03-06T15:06:11Z)
• An Application of a Multivariate Estimation of Distribution Algorithm to Cancer Chemotherapy [59.40521061783166]
  癌に対する化学療法治療は、多数の相互作用する変数と制約を持つ複雑な最適化問題である。 より洗練されたアルゴリズムは、このような複雑な問題に対してより良いパフォーマンスをもたらすことが示される。 我々は、この問題における多数の相互作用によって、より洗練されたアルゴリズムが妨げられていることが原因であると仮定する。
  論文  参考訳（メタデータ） (2022-05-17T15:28:46Z)
• Mathematical Runtime Analysis for the Non-Dominated Sorting Genetic Algorithm II (NSGA-II) [16.904475483445452]
  NSGA-IIにも実行時解析が可能であることを示す。 NSGA-IIは,パレートフロントの4倍の大きさの個体群を持つため,SEMOアルゴリズムやGSEMOアルゴリズムと同じランタイム保証を満たす。
  論文  参考訳（メタデータ） (2021-12-16T03:00:20Z)
• Fractal Structure and Generalization Properties of Stochastic Optimization Algorithms [71.62575565990502]
  最適化アルゴリズムの一般化誤差は、その一般化尺度の根底にあるフラクタル構造の複雑性'にバウンドできることを示す。 さらに、特定の問題(リニア/ロジスティックレグレッション、隠れ/層ニューラルネットワークなど)とアルゴリズムに対して、結果をさらに専門化します。
  論文  参考訳（メタデータ） (2021-06-09T08:05:36Z)
• Quantum Algorithms for Data Representation and Analysis [68.754953879193]
  機械学習におけるデータ表現のための固有problemsの解を高速化する量子手続きを提供する。 これらのサブルーチンのパワーと実用性は、主成分分析、対応解析、潜在意味解析のための入力行列の大きさのサブ線形量子アルゴリズムによって示される。 その結果、入力のサイズに依存しない実行時のパラメータは妥当であり、計算モデル上の誤差が小さいことが示され、競合的な分類性能が得られる。
  論文  参考訳（メタデータ） (2021-04-19T00:41:43Z)
• Convergence Analysis of Homotopy-SGD for non-convex optimization [43.71213126039448]
  ホモトピー法とSGDを組み合わせた一階述語アルゴリズム、Gradienty-Stoch Descent (H-SGD)を提案する。 いくつかの仮定の下で、提案した問題の理論的解析を行う。 実験の結果,H-SGDはSGDより優れていた。
  論文  参考訳（メタデータ） (2020-11-20T09:50:40Z)
• Generalized Matrix Factorization: efficient algorithms for fitting generalized linear latent variable models to large data arrays [62.997667081978825]
  一般化線形潜在変数モデル(GLLVM)は、そのような因子モデルを非ガウス応答に一般化する。 GLLVMのモデルパラメータを推定する現在のアルゴリズムは、集約的な計算を必要とし、大規模なデータセットにスケールしない。 本稿では,GLLVMを高次元データセットに適用するための新しい手法を提案する。
  論文  参考訳（メタデータ） (2020-10-06T04:28:19Z)
• Approximation Algorithms for Sparse Principal Component Analysis [57.5357874512594]
  主成分分析(PCA)は、機械学習と統計学において広く使われている次元削減手法である。 スパース主成分分析(Sparse principal Component Analysis)と呼ばれる,スパース主成分負荷を求める様々な手法が提案されている。 本研究では,SPCA問題に対するしきい値の精度,時間,近似アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2020-06-23T04:25:36Z)
• From Understanding Genetic Drift to a Smart-Restart Parameter-less Compact Genetic Algorithm [15.56430085052365]
  遺伝的なドリフトのない体制では、実行期間は人口規模にほぼ比例する。 本稿では,遺伝的アルゴリズムのパラメータレスバージョンを提案する。
  論文  参考訳（メタデータ） (2020-04-15T15:12:01Z)
• A Simplified Run Time Analysis of the Univariate Marginal Distribution Algorithm on LeadingOnes [9.853329403413701]
  単変量分布アルゴリズム(UMDA)における実行時間保証の強化を実証する。 より少ない選択率によるランタイムゲインを示す。 同様の仮定の下では、我々の上界と定数因子に一致する境界が高い確率で成り立つことを証明している。
  論文  参考訳（メタデータ） (2020-04-10T10:20:05Z)

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

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