論文の概要: Estimate Hitting Time by Hitting Probability for Elitist Evolutionary Algorithms

• arxiv url: http://arxiv.org/abs/2506.15602v1
• Date: Wed, 18 Jun 2025 16:25:05 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-06-19 19:35:51.738975
• Title: Estimate Hitting Time by Hitting Probability for Elitist Evolutionary Algorithms
• Title（参考訳）: 進化的アルゴリズムにおける隠れ確率による隠れ時間の推定
• Authors: Jun He, Siang Yew Chong, Xin Yao,
• Abstract要約: 本稿では,線形境界係数を計算するために,ヒット確率のドリフト解析と呼ばれる新しい手法を提案する。 ヒット確率を計算するために明示的な式を構築し、推定プロセスを大幅に単純化する。 ファシビリティルールとグリーディ修復をそれぞれ組み込んだクナップサック問題に対する2つのアルゴリズムを比較した。
• 参考スコア（独自算出の注目度）: 4.605031905884542
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Drift analysis is a powerful tool for analyzing the time complexity of evolutionary algorithms. However, it requires manual construction of drift functions to bound hitting time for each specific algorithm and problem. To address this limitation, general linear drift functions were introduced for elitist evolutionary algorithms. But calculating linear bound coefficients effectively remains a problem. This paper proposes a new method called drift analysis of hitting probability to compute these coefficients. Each coefficient is interpreted as a bound on the hitting probability of a fitness level, transforming the task of estimating hitting time into estimating hitting probability. A novel drift analysis method is then developed to estimate hitting probability, where paths are introduced to handle multimodal fitness landscapes. Explicit expressions are constructed to compute hitting probability, significantly simplifying the estimation process. One advantage of the proposed method is its ability to estimate both the lower and upper bounds of hitting time and to compare the performance of two algorithms in terms of hitting time. To demonstrate this application, two algorithms for the knapsack problem, each incorporating feasibility rules and greedy repair respectively, are compared. The analysis indicates that neither constraint handling technique consistently outperforms the other.
• Abstract（参考訳）: ドリフト分析は進化的アルゴリズムの時間的複雑さを分析する強力なツールである。 しかし,各アルゴリズムや問題に対して,ドリフト関数を手動で構築する必要がある。 この制限に対処するため、エリート的進化アルゴリズムに一般的な線形ドリフト関数を導入した。 しかし、線形有界係数を効果的に計算することは問題である。 本稿では,これらの係数を計算するために,打撃確率のドリフト解析と呼ばれる新しい手法を提案する。 各係数は、フィットネスレベルの打点確率のバウンドとして解釈され、打点時間を推定して打点確率を推定するタスクが変換される。 そこで,マルチモーダルなフィットネスランドスケープを扱うために,新たなドリフト解析手法を開発し,ヒット確率を推定する。 ヒット確率を計算するために明示的な式を構築し、推定プロセスを大幅に単純化する。 提案手法の利点の1つは、打点時間の下限と上限の両方を推定し、打点時間の観点から2つのアルゴリズムの性能を比較することである。 この応用を実証するために, 実現可能性ルールとグリーディ修復をそれぞれ組み込んだ, クナップサック問題の2つのアルゴリズムを比較した。 この分析は、制約ハンドリング手法が他方よりも一貫して優れていることを示唆している。

関連論文リスト

• Pathwise optimization for bridge-type estimators and its applications [49.1574468325115]
  パスワイズ法は、ペナライズされた推定器の完全な経路を効率的に計算することができる。 これらのアルゴリズムを離散時間で観測されたプロセスのペナル化推定に適用する。
  論文  参考訳（メタデータ） (2024-12-05T10:38:29Z)
• Stochastic Optimization for Non-convex Problem with Inexact Hessian Matrix, Gradient, and Function [99.31457740916815]
  信頼領域(TR)と立方体を用いた適応正則化は、非常に魅力的な理論的性質を持つことが証明されている。 TR法とARC法はヘッセン関数,勾配関数,関数値の非コンパクトな計算を同時に行うことができることを示す。
  論文  参考訳（メタデータ） (2023-10-18T10:29:58Z)
• Contraction-Guided Adaptive Partitioning for Reachability Analysis of Neural Network Controlled Systems [5.359060261460183]
  非線形フィードバックループにおける区間値到達可能集合の推定値を改善するための収縮誘導適応分割アルゴリズムを提案する。 ニューラルネットワーク検証ステップとリーチビリティパーティショニングレイヤの分離を活用することで、アルゴリズムは計算コストの少ない精度の向上を提供することができる。 本稿では,現状の手法と比較して,ランタイムのごく一部において,到達可能な集合推定の精度が大幅に向上したことを報告する。
  論文  参考訳（メタデータ） (2023-04-07T14:43:21Z)
• Linearized Wasserstein dimensionality reduction with approximation guarantees [65.16758672591365]
  LOT Wassmap は、ワーッサーシュタイン空間の低次元構造を明らかにするための計算可能なアルゴリズムである。 我々は,LOT Wassmapが正しい埋め込みを実現し,サンプルサイズの増加とともに品質が向上することを示す。 また、LOT Wassmapがペア距離計算に依存するアルゴリズムと比較して計算コストを大幅に削減することを示す。
  論文  参考訳（メタデータ） (2023-02-14T22:12:16Z)
• Fast Computation of Optimal Transport via Entropy-Regularized Extragradient Methods [75.34939761152587]
  2つの分布間の最適な輸送距離の効率的な計算は、様々な応用を促進するアルゴリズムとして機能する。 本稿では,$varepsilon$加法精度で最適な輸送を計算できるスケーラブルな一階最適化法を提案する。
  論文  参考訳（メタデータ） (2023-01-30T15:46:39Z)
• Single-Timescale Stochastic Nonconvex-Concave Optimization for Smooth Nonlinear TD Learning [145.54544979467872]
  本稿では,各ステップごとに1つのデータポイントしか必要としない2つの単一スケールシングルループアルゴリズムを提案する。 本研究の結果は, 同時一次および二重側収束の形で表される。
  論文  参考訳（メタデータ） (2020-08-23T20:36:49Z)
• High-dimensional macroeconomic forecasting using message passing algorithms [0.0]
  この仕様における推論は、係数の高次元ベクトルを縮小するベイジアン階層的先行法を用いて進行する。 一般化近似メッセージパッシング(GAMP)アルゴリズムはアルゴリズムの複雑さが低く、簡単に並列化可能である。
  論文  参考訳（メタデータ） (2020-04-23T23:10:04Z)
• Stochastic Optimization for Regularized Wasserstein Estimators [10.194798773447879]
  ワッサーシュタイン推定器勾配の正規化版を、自然次元のサブ線形なステップ毎の時間で解くアルゴリズムを導入する。 このアルゴリズムは他のタスクにも拡張可能であることを示し、その中にはWasserstein Barycentersの推定も含まれる。
  論文  参考訳（メタデータ） (2020-02-20T12:04:05Z)

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

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