Fugu-MT 論文翻訳(概要): Asymptotical Analysis of the $(1+(λ,λ))$ GA Escape Time from Local Optima on Jump Functions

論文の概要: Asymptotical Analysis of the $(1+(λ,λ))$ GA Escape Time from Local Optima on Jump Functions

arxiv url: http://arxiv.org/abs/2607.14278v1
Date: Wed, 15 Jul 2026 18:37:48 GMT
ステータス: 翻訳完了
システム内更新日: 2026-07-17 17:01:32.88752
Title: Asymptotical Analysis of the $(1+(λ,λ))$ GA Escape Time from Local Optima on Jump Functions
Title（参考訳）: 1+(λ,λ)= GA のジャンプ関数上の局所オプティマからの脱出時間に関する漸近解析
Abstract要約: 本稿では,確率論からの極限定理に基づく進化的アルゴリズムのランタイム解析へのアプローチを開発する。この研究の主な成果は、Antipov, Doerr and Karavaev (2022) の業績から得られる脱走時間に対する上限の締め付けである。
参考スコア（独自算出の注目度）: 0.5156484100374058
License: http://creativecommons.org/licenses/by/4.0/
Abstract: The paper develops the approach to the runtime analysis of evolutionary algorithms on the basis of limit theorems from probability theory. We consider the family of Jump$_k$ benchmark functions, defined on the search space of binary strings of length $n$, parametrized by the integer $k$, which have multiple local optima at the Hamming distance $k$ from a unique global optimum. In this work, we consider the genetic algorithm $(1+(λ,λ)) GA$ from (Doerr, Doerr and Ebel, 2015) with tunable parameters of the mutation rate $p$, crossover bias $c$, and two intermediate population sizes $λ_M$ and $λ_C$, and study the time it escapes from the plateau in the case of Jump$_k$ fitness function when $np$ tends to infinity. The main result of this work is a tightened upper bound on the escape time from the work of Antipov, Doerr and Karavaev (2022). Besides that, the obtained bound applies to a wider range of algorithm parameters.
Abstract（参考訳）: 本稿では,確率論からの極限定理に基づく進化的アルゴリズムのランタイム解析へのアプローチを開発する。我々は、長さ$n$のバイナリ文字列の探索空間上で定義されるJump$_k$ベンチマーク関数の族を考える。本研究では,突然変異率$p$,クロスオーバーバイアス$c$,中間集団サイズ$λ_M$と$λ_C$のチューナブルパラメータを持つGA$(Doerr, Doerr, Ebel, 2015)からGA$((1+(λ,λ))を考える。この作品の主な成果は、アンティポフ、ドルル、カラヴァエフ(2022年)の著作から逃れる時間に固定された上限である。さらに、得られた境界はより広い範囲のアルゴリズムパラメータに適用できる。

関連論文リスト

Anytime Analysis on BinVal: Adaptive Parameters Help [0.0]
我々は、BinValをフィットネス機能として利用して、様々なアルゴリズムの固定目標実行時間を分析する。固定目標実行時間は o(n)$ で、定数 $varepsilon > 0$ が 0 に近いのは、このアルゴリズムに対して $mathcalOleft(k1+varepsilonright)$ である。
論文参考訳（メタデータ） (2026-04-08T11:47:10Z)
Beyond likelihood ratio bias: Nested multi-time-scale stochastic approximation for likelihood-free parameter estimation [49.78792404811239]
確率分析形式が不明なシミュレーションベースモデルにおける推論について検討する。我々は、スコアを同時に追跡し、パラメータ更新を駆動する比率のないネスト型マルチタイムスケール近似(SA)手法を用いる。我々のアルゴリズムは、オリジナルのバイアス$Obig(sqrtfrac1Nbig)$を排除し、収束率を$Obig(beta_k+sqrtfracalpha_kNbig)$から加速できることを示す。
論文参考訳（メタデータ） (2024-11-20T02:46:15Z)
Achieving Tight $O(4^k)$ Runtime Bounds on Jump$_k$ by Proving that Genetic Algorithms Evolve Near-Maximal Population Diversity [1.8434042562191815]
我々は、$(mu+1)$-$lambda_c$-GAの集団の多様性が、ほぼ完全な多様性の均衡に収束することを示した。また、この分析は、JUMP$_k、delta$、HURDLEなどの他のユニタリ化関数にも拡張可能であることを示す。
論文参考訳（メタデータ） (2024-04-10T14:50:43Z)
Nearly Minimax Optimal Regret for Learning Linear Mixture Stochastic Shortest Path [80.60592344361073]
線形混合遷移カーネルを用いた最短経路(SSP)問題について検討する。エージェントは繰り返し環境と対話し、累積コストを最小化しながら特定の目標状態に到達する。既存の作業は、イテレーションコスト関数の厳密な下限や、最適ポリシーに対する期待長の上限を仮定することが多い。
論文参考訳（メタデータ） (2024-02-14T07:52:00Z)
Mind the gap: Achieving a super-Grover quantum speedup by jumping to the end [114.3957763744719]
本稿では,数種類のバイナリ最適化問題に対して,厳密な実行保証を有する量子アルゴリズムを提案する。このアルゴリズムは、$n$非依存定数$c$に対して、時間で$O*(2(0.5-c)n)$の最適解を求める。また、$k$-spinモデルからのランダムなインスタンスの多数と、完全に満足あるいはわずかにフラストレーションされた$k$-CSP式に対して、文 (a) がそうであることを示す。
論文参考訳（メタデータ） (2022-12-03T02:45:23Z)
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)
Optimal Robust Linear Regression in Nearly Linear Time [97.11565882347772]
学習者が生成モデル$Y = langle X,w* rangle + epsilon$から$n$のサンプルにアクセスできるような高次元頑健な線形回帰問題について検討する。 i) $X$ is L4-L2 hypercontractive, $mathbbE [XXtop]$ has bounded condition number and $epsilon$ has bounded variance, (ii) $X$ is sub-Gaussian with identity second moment and $epsilon$ is
論文参考訳（メタデータ） (2020-07-16T06:44:44Z)
Streaming Complexity of SVMs [110.63976030971106]
本稿では,ストリーミングモデルにおけるバイアス正規化SVM問題を解く際の空間複雑性について検討する。両方の問題に対して、$frac1lambdaepsilon$の次元に対して、$frac1lambdaepsilon$よりも空間的に小さいストリーミングアルゴリズムを得ることができることを示す。
論文参考訳（メタデータ） (2020-07-07T17:10:00Z)
Optimal Mutation Rates for the $(1+\lambda)$ EA on OneMax [1.0965065178451106]
我々は、最適な突然変異率の分析を、OneMax問題の2つの変種に拡張する。すべての集団サイズを2i mid 0 le i le 18$で計算します。我々の結果は、一般的な進化的アプローチを測ることのできる低い境界を提供するばかりではない。
論文参考訳（メタデータ） (2020-06-20T01:23:14Z)
Runtime Analysis of a Heavy-Tailed $(1+(\lambda,\lambda))$ Genetic Algorithm on Jump Functions [9.853329403413701]
ジャンプ関数は、n(k + 1)/2k-k/2eO(k)$フィットネス評価のみの期待実行時に、ジャンプサイズ$k$で最適化できる。ジャンプサイズが最大$n/4$のすべてのジャンプ関数上の分布パラメータを自然に選択したこのアルゴリズムは、前回の作業で得られる最良のインスタンス固有パラメータに近い性能を持つことを示す。
論文参考訳（メタデータ） (2020-06-05T15:57:55Z)
A Rigorous Runtime Analysis of the $(1 + (\lambda, \lambda))$ GA on Jump Functions [8.34061303235504]
我々は,このアルゴリズムの最初の実行時解析を,ジャンプ関数ベンチマークであるマルチモーダル問題クラス上で実施する。ジャンプ関数の局所最適性を残すという孤立した問題に対して、$(n/k)k/2 eTheta(k)$のランタイムにつながる証明可能な最適パラメータを決定する。
論文参考訳（メタデータ） (2020-04-14T17:54:12Z)

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