論文の概要: Runtime Analysis for Permutation-based Evolutionary Algorithms
- arxiv url: http://arxiv.org/abs/2207.04045v4
- Date: Sat, 20 Apr 2024 08:49:17 GMT
- ステータス: 処理完了
- システム内更新日: 2024-04-24 01:41:46.250262
- Title: Runtime Analysis for Permutation-based Evolutionary Algorithms
- Title（参考訳）: 置換に基づく進化的アルゴリズムの実行時解析
- Authors: Benjamin Doerr, Yassine Ghannane, Marouane Ibn Brahim,
- Abstract要約: ビットストリングの場合のように、スクランブル演算子の重み付きバージョンは、ジャンプサイズが$m$のジャンプ関数において、$mTheta(m)$の順序の高速化につながることを示す。
短い経験的分析によりこれらの知見が裏付けられるが、また、ヴォイド突然変異率のような小さな実装の詳細が重要な違いをもたらすことも明らかである。
- 参考スコア（独自算出の注目度）: 9.044970217182117
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: While the theoretical analysis of evolutionary algorithms (EAs) has made significant progress for pseudo-Boolean optimization problems in the last 25 years, only sporadic theoretical results exist on how EAs solve permutation-based problems. To overcome the lack of permutation-based benchmark problems, we propose a general way to transfer the classic pseudo-Boolean benchmarks into benchmarks defined on sets of permutations. We then conduct a rigorous runtime analysis of the permutation-based $(1+1)$ EA proposed by Scharnow, Tinnefeld, and Wegener (2004) on the analogues of the LeadingOnes and Jump benchmarks. The latter shows that, different from bit-strings, it is not only the Hamming distance that determines how difficult it is to mutate a permutation $\sigma$ into another one $\tau$, but also the precise cycle structure of $\sigma \tau^{-1}$. For this reason, we also regard the more symmetric scramble mutation operator. We observe that it not only leads to simpler proofs, but also reduces the runtime on jump functions with odd jump size by a factor of $\Theta(n)$. Finally, we show that a heavy-tailed version of the scramble operator, as in the bit-string case, leads to a speed-up of order $m^{\Theta(m)}$ on jump functions with jump size $m$. A short empirical analysis confirms these findings, but also reveals that small implementation details like the rate of void mutations can make an important difference.
- Abstract（参考訳）: 進化的アルゴリズム(EA)の理論解析は、過去25年間に擬ブール最適化問題において大きな進歩を遂げてきたが、EAが置換に基づく問題を解決する方法に関する散発的な理論的な結果のみが存在する。
置換に基づくベンチマークの欠如を克服するため,従来の擬似ブールベンチマークを置換集合上で定義されたベンチマークに転送する一般的な方法を提案する。
次に、Scharnow, Tinnefeld, Wegener (2004) が提案した置換に基づく$(1+1)$ EAの厳密な実行時解析を、LeadingOnes と Jump ベンチマークの類似で実施する。
後者は、ビットストリングと異なり、置換を$\sigma$を別の$\tau$に変換するのがどれほど難しいかを決定するハミング距離だけでなく、$\sigma \tau^{-1}$の正確なサイクル構造も示している。
このため、より対称なスクランブル突然変異作用素も考慮する。
単純な証明に繋がるだけでなく、奇妙なジャンプサイズを持つジャンプ関数のランタイムを$\Thetaの係数で削減する。
(n)$。
最後に、ビットストリングの場合のように、スクランブル演算子の重み付きバージョンが$m^{\Thetaの高速化につながることを示す。
(m)}$ on jump function with jump size $m$
短い経験的分析によりこれらの知見が裏付けられるが、また、ヴォイド突然変異率のような小さな実装の詳細が重要な違いをもたらすことも明らかである。
関連論文リスト
- Sum-of-Squares inspired Quantum Metaheuristic for Polynomial Optimization with the Hadamard Test and Approximate Amplitude Constraints [76.53316706600717]
最近提案された量子アルゴリズムarXiv:2206.14999は半定値プログラミング(SDP)に基づいている
SDPにインスパイアされた量子アルゴリズムを2乗和に一般化する。
この結果から,本アルゴリズムは大きな問題に適応し,最もよく知られた古典学に近似することが示唆された。
論文 参考訳（メタデータ） (2024-08-14T19:04:13Z) - Quantum One-Wayness of the Single-Round Sponge with Invertible Permutations [49.1574468325115]
スポンジハッシュは、広く使われている暗号ハッシュアルゴリズムのクラスである。
これまでのところ、不規則な置換は根本的なオープンな問題のままである。
ランダムな2n$-bit置換でゼロペアを見つけるには、少なくとも$Omega(2n/2)$多くのクエリが必要である。
論文 参考訳（メタデータ） (2024-03-07T18:46:58Z) - Tight Runtime Bounds for Static Unary Unbiased Evolutionary Algorithms on Linear Functions [0.44241702149260353]
Witt は (1+1) 進化的アルゴリズムの標準的なビット変異は任意の線形関数の最適値を見つけるのに時間を必要とすることを示した。
この結果は、標準ビット突然変異が任意の未バイアス突然変異演算子に置き換えられた場合にどのように一般化されるかを検討する。
論文 参考訳（メタデータ） (2023-02-23T21:09:15Z) - Fourier Analysis Meets Runtime Analysis: Precise Runtimes on Plateaus [9.853329403413701]
本研究では, 離散フーリエ解析に基づく新しい手法を提案し, 進化的アルゴリズムがプラトーに費やす時間を解析する。
また、この手法を用いて、$(1+1)$進化アルゴリズムのランタイムを、有効サイズ2ell-1$の$n/ell$高原からなる新しいベンチマークで解析する。
論文 参考訳（メタデータ） (2023-02-16T01:46:06Z) - Multi-block-Single-probe Variance Reduced Estimator for Coupled
Compositional Optimization [49.58290066287418]
構成問題の複雑さを軽減するために,MSVR (Multi-block-probe Variance Reduced) という新しい手法を提案する。
本研究の結果は, 試料の複雑さの順序や強靭性への依存など, 様々な面で先行して改善された。
論文 参考訳（メタデータ） (2022-07-18T12:03:26Z) - Exact Paired-Permutation Testing for Structured Test Statistics [67.71280539312536]
構造化されたテスト統計群のペア置換テストに対して,効率的な正確なアルゴリズムを提案する。
我々の正確なアルゴリズムはモンテカルロ近似よりも10ドル速く、共通のデータセットに20000ドルのサンプルがある。
論文 参考訳（メタデータ） (2022-05-03T11:00:59Z) - Towards a Stronger Theory for Permutation-based Evolutionary Algorithms [8.34061303235504]
古典的な擬似ブールベンチマークを、置換の集合上で定義されたベンチマークに転送する。
我々は、Scharnow, Tinnefeld, Wegenerによって提案された置換に基づく$(+1)$ EAの厳密なランタイム解析を行う。
我々は、スクランブル作用素の重み付きバージョンが、ビットストリングの場合のように、ジャンプサイズを持つジャンプ関数の次数$mTheta(m)$の高速化につながることを観察する。
論文 参考訳（メタデータ） (2022-04-15T20:36:35Z) - E-detectors: a nonparametric framework for sequential change detection [86.15115654324488]
逐次的変化検出のための基本的かつ汎用的なフレームワークを開発する。
私たちの手順は、平均走行距離のクリーンで無症状な境界が伴います。
統計的および計算効率の両方を達成するために,これらの混合物を設計する方法を示す。
論文 参考訳（メタデータ） (2022-03-07T17:25:02Z) - Batch Bayesian Optimization on Permutations using Acquisition Weighted
Kernels [86.11176756341114]
決定点プロセスに基づく新しい効率的なバッチ取得方法であるLAWを紹介します。
本研究では,理論特性の知見を得るための後悔分析法を提案する。
二次代入などの置換を含むいくつかの標準問題に対する手法を評価する。
論文 参考訳（メタデータ） (2021-02-26T10:15:57Z) - Theoretical Analyses of Multiobjective Evolutionary Algorithms on
Multimodal Objectives [15.56430085052365]
OJZJ問題(OJZJ problem)は、古典的なジャンプ関数のベンチマークに同型な2つの目的からなる双目的問題である。
確率1のSEMOは、実行時に関係なく、完全なParetoフロントを計算していないことを証明します。
また、より厳密な制限付き$frac 32 e nk+1 pm o(nk+1)$を示す。
論文 参考訳（メタデータ） (2020-12-14T03:07:39Z) - The $(1+(\lambda,\lambda))$ Genetic Algorithm for Permutations [0.0]
我々は、$(lambda,lambda)$の遺伝的アルゴリズムが、$O(n2)$のフィットネスクエリで最適であることを示す。
また,Hamと呼ばれる置換に基づく問題に対して,このアルゴリズムの最初の解析を行った。
論文 参考訳（メタデータ） (2020-04-18T17:04:57Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。