論文の概要: A Rigorous Runtime Analysis of the $(1 + (\lambda, \lambda))$ GA on Jump
Functions
- arxiv url: http://arxiv.org/abs/2004.06702v4
- Date: Tue, 23 Nov 2021 10:22:16 GMT
- ステータス: 処理完了
- システム内更新日: 2022-12-13 09:15:43.431206
- Title: A Rigorous Runtime Analysis of the $(1 + (\lambda, \lambda))$ GA on Jump
Functions
- Title（参考訳）: ジャンプ関数上の$(1 + (\lambda, \lambda)$ GAの厳密な実行時解析
- Authors: Denis Antipov, Benjamin Doerr, Vitalii Karavaev
- Abstract要約: 我々は,このアルゴリズムの最初の実行時解析を,ジャンプ関数ベンチマークであるマルチモーダル問題クラス上で実施する。
ジャンプ関数の局所最適性を残すという孤立した問題に対して、$(n/k)k/2 eTheta(k)$のランタイムにつながる証明可能な最適パラメータを決定する。
- 参考スコア（独自算出の注目度）: 8.34061303235504
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: The $(1 + (\lambda,\lambda))$ genetic algorithm is a younger evolutionary
algorithm trying to profit also from inferior solutions. Rigorous runtime
analyses on unimodal fitness functions showed that it can indeed be faster than
classical evolutionary algorithms, though on these simple problems the gains
were only moderate.
In this work, we conduct the first runtime analysis of this algorithm on a
multimodal problem class, the jump functions benchmark. We show that with the
right parameters, the \ollga optimizes any jump function with jump size $2 \le
k \le n/4$ in expected time $O(n^{(k+1)/2} e^{O(k)} k^{-k/2})$, which
significantly and already for constant~$k$ outperforms standard mutation-based
algorithms with their $\Theta(n^k)$ runtime and standard crossover-based
algorithms with their $\tilde{O}(n^{k-1})$ runtime guarantee.
For the isolated problem of leaving the local optimum of jump functions, we
determine provably optimal parameters that lead to a runtime of $(n/k)^{k/2}
e^{\Theta(k)}$. This suggests some general advice on how to set the parameters
of the \ollga, which might ease the further use of this algorithm.
- Abstract（参考訳）: 1 + (\lambda,\lambda))$ 遺伝的アルゴリズムは、劣った解から利益を得ようとする若い進化的アルゴリズムである。
一様フィットネス関数の厳密な実行時解析は、古典的な進化的アルゴリズムよりも実際は高速であることを示したが、これらの単純な問題では利得は適度にしかなかった。
本研究では,マルチモーダル問題クラスであるjump functions benchmark上で,このアルゴリズムの最初の実行時解析を行う。
適切なパラメータで、 \ollga はジャンプサイズが 2 のジャンプ関数を最適化する。 $O(n^{(k+1)/2} e^{O(k)} k^{-k/2})$ は、すでに$\Theta(n^k)$ ランタイムと $\tilde{O}(n^{k-1})$ ランタイム保証で標準突然変異ベースのアルゴリズムより優れています。
ジャンプ関数の局所最適性を残すという孤立した問題に対して、$(n/k)^{k/2} e^{\Theta(k)}$のランタイムにつながる証明可能な最適パラメータを決定する。
これは \ollga のパラメータの設定方法に関する一般的なアドバイスを示唆しており、このアルゴリズムのさらなる使用が容易になる可能性がある。
関連論文リスト
- A Scalable Algorithm for Individually Fair K-means Clustering [77.93955971520549]
Jung et al. と Mahabadi et al が導入した個別フェア (p$, $k$) クラスタリング問題に対するスケーラブルなアルゴリズムを提案する。
クラスタリングは、各$xin P$に対して$delta(x)$ of $x$の範囲内で中心となる場合、個別にフェアと呼ばれる。
我々は,従来よりもアルゴリズムがはるかに高速であるだけでなく,低コストのソリューションを生み出すことを実証的に示す。
論文 参考訳（メタデータ） (2024-02-09T19:01:48Z) - Run Time Bounds for Integer-Valued OneMax Functions [0.9012198585960443]
探索空間 $mathbbZn$ を多値決定変数 $0,ldots,r-1n$ の観点から考える。
ステップサイズ適応のRSSが$Theta(n cdot log(|a|_1))$の最適化時間を達成することを示す。
本稿では,これらのアルゴリズムを離散探索空間に対するCMA-ESの変種と比較し,実験的な解析を行った。
論文 参考訳（メタデータ） (2023-07-21T18:49:06Z) - An Oblivious Stochastic Composite Optimization Algorithm for Eigenvalue
Optimization Problems [76.2042837251496]
相補的な合成条件に基づく2つの難解なミラー降下アルゴリズムを導入する。
注目すべきは、どちらのアルゴリズムも、目的関数のリプシッツ定数や滑らかさに関する事前の知識なしで機能する。
本稿では,大規模半確定プログラム上での手法の効率性とロバスト性を示す。
論文 参考訳（メタデータ） (2023-06-30T08:34:29Z) - Larger Offspring Populations Help the $(1 + (\lambda, \lambda))$ Genetic
Algorithm to Overcome the Noise [76.24156145566425]
進化的アルゴリズムは、適合性の評価においてノイズに対して堅牢であることが知られている。
我々は$(lambda,lambda)$の遺伝的アルゴリズムがどんなにノイズに強いかを解析する。
論文 参考訳（メタデータ） (2023-05-08T08:49:01Z) - 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) - Bayesian Optimistic Optimisation with Exponentially Decaying Regret [58.02542541410322]
現在の実用的なBOアルゴリズムは、$mathcalO(fraclogNsqrtN)$から$mathcalO(e-sqrtN)$まで、$N$は評価の数である。
本稿では,boと木に基づく楽観的楽観化の概念を絡み合うことにより,無音環境における後悔を改善できる可能性について検討する。
次数$mathcal O(N-sqrt)で指数的再帰を達成できる最初の実践的手法であるBOOアルゴリズムを提案する。
論文 参考訳（メタデータ） (2021-05-10T13:07:44Z) - An Extended Jump Function Benchmark for the Analysis of Randomized
Search Heuristics [4.38301148531795]
幅のフィットネスが低い谷を含むジャンプ関数の拡張クラス $textscJump_k,delta$ を提案します。
この新しいクラスは、特にグローバルな最適点から遠く離れている場合に、より広いフィットネスバレーでの実験を可能にすることを示す。
論文 参考訳（メタデータ） (2021-05-07T07:21:10Z) - Parameter-free Stochastic Optimization of Variationally Coherent
Functions [19.468067110814808]
我々は$mathbbRdilon上で関数のクラスを1次最適化するためのアルゴリズムを設計・解析する。
この2つを同時に実現したのは初めてである。
論文 参考訳（メタデータ） (2021-01-30T15:05:34Z) - Streaming Complexity of SVMs [110.63976030971106]
本稿では,ストリーミングモデルにおけるバイアス正規化SVM問題を解く際の空間複雑性について検討する。
両方の問題に対して、$frac1lambdaepsilon$の次元に対して、$frac1lambdaepsilon$よりも空間的に小さいストリーミングアルゴリズムを得ることができることを示す。
論文 参考訳（メタデータ） (2020-07-07T17:10:00Z) - 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) - The $(1+(\lambda,\lambda))$ Genetic Algorithm for Permutations [0.0]
我々は、$(lambda,lambda)$の遺伝的アルゴリズムが、$O(n2)$のフィットネスクエリで最適であることを示す。
また,Hamと呼ばれる置換に基づく問題に対して,このアルゴリズムの最初の解析を行った。
論文 参考訳（メタデータ） (2020-04-18T17:04:57Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。