論文の概要: The Compact Genetic Algorithm Struggles on Cliff Functions
- arxiv url: http://arxiv.org/abs/2204.04904v1
- Date: Mon, 11 Apr 2022 07:10:53 GMT
- ステータス: 処理完了
- システム内更新日: 2023-02-17 08:19:57.879718
- Title: The Compact Genetic Algorithm Struggles on Cliff Functions
- Title（参考訳）: コンパクトな遺伝的アルゴリズムは崖の関数に苦しむ
- Authors: Frank Neumann, Dirk Sudholt, Carsten Witt
- Abstract要約: CLIFF関数のcGAについて検討し、非溶血性進化アルゴリズムと人工免疫システムが期待通りに最適化できることが示されている。
合理的な仮定では、崖の位置をサンプリングするときに負のドリフトがある。
実験の結果、期待される最適化時間が$nTheta(n)$から$2Theta(n)$に落ちるような$K$の位相遷移が存在することが示唆されている。
- 参考スコア（独自算出の注目度）: 11.228244128564512
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: The compact genetic algorithm (cGA) is an non-elitist estimation of
distribution algorithm which has shown to be able to deal with difficult
multimodal fitness landscapes that are hard to solve by elitist algorithms. In
this paper, we investigate the cGA on the CLIFF function for which it has been
shown recently that non-elitist evolutionary algorithms and artificial immune
systems optimize it in expected polynomial time. We point out that the cGA
faces major difficulties when solving the CLIFF function and investigate its
dynamics both experimentally and theoretically around the cliff. Our
experimental results indicate that the cGA requires exponential time for all
values of the update strength $K$. We show theoretically that, under sensible
assumptions, there is a negative drift when sampling around the location of the
cliff. Experiments further suggest that there is a phase transition for $K$
where the expected optimization time drops from $n^{\Theta(n)}$ to
$2^{\Theta(n)}$.
- Abstract（参考訳）: コンパクトな遺伝的アルゴリズム (cGA) は分散アルゴリズムの非エリート的推定であり、エリート的アルゴリズムによって解決が難しい困難なマルチモーダルなフィットネスランドスケープに対処できることが示されている。
本稿では,CLIFF関数のcGAについて検討し,非エリート進化アルゴリズムと人工免疫システムが期待される多項式時間で最適化できることを最近明らかにした。
我々は,cgaが崖関数の解法において大きな困難に直面していることを指摘し,その力学を実験的および理論的に崖の周囲で検討した。
以上の結果から,cGAは更新強度のすべての値に対して指数時間を必要とすることが示唆された。
理論的には, 合理的な仮定の下では, 崖の周囲をサンプリングすると負のドリフトが発生する。
さらに実験によれば、k$ の相転移があり、そこでは期待された最適化時間は $n^{\theta(n)$ から $2^{\theta(n)$ に低下する。
関連論文リスト
- Matching the Statistical Query Lower Bound for k-sparse Parity Problems with Stochastic Gradient Descent [83.85536329832722]
勾配勾配降下(SGD)は,$d$次元ハイパーキューブ上の$k$パリティ問題を効率的に解くことができることを示す。
次に、SGDでトレーニングされたニューラルネットワークがどのようにして、小さな統計的エラーで$k$-parityの問題を解決するかを実証する。
論文 参考訳（メタデータ） (2024-04-18T17:57:53Z) - Detection-Recovery Gap for Planted Dense Cycles [72.4451045270967]
期待帯域幅$n tau$とエッジ密度$p$をエルドホス=R'enyiグラフ$G(n,q)$に植え込むモデルを考える。
低次アルゴリズムのクラスにおいて、関連する検出および回復問題に対する計算しきい値を特徴付ける。
論文 参考訳（メタデータ） (2023-02-13T22:51:07Z) - Hidden Progress in Deep Learning: SGD Learns Parities Near the
Computational Limit [36.17720004582283]
この研究は、$k$sparseパリティを$n$bitsで学習するレンズを通してそのような探索を行う。
データセットのサイズと実行時間をスケールアップする際、ニューラルネットワークは驚くほどの位相遷移を示す。
論文 参考訳（メタデータ） (2022-07-18T17:55:05Z) - Improved Convergence Rate of Stochastic Gradient Langevin Dynamics with
Variance Reduction and its Application to Optimization [50.83356836818667]
勾配ランゲヴィン・ダイナミクスは非エプス最適化問題を解くための最も基本的なアルゴリズムの1つである。
本稿では、このタイプの2つの変種、すなわち、分散還元ランジュバンダイナミクスと再帰勾配ランジュバンダイナミクスを示す。
論文 参考訳（メタデータ） (2022-03-30T11:39:00Z) - A Robust Phased Elimination Algorithm for Corruption-Tolerant Gaussian
Process Bandits [118.22458816174144]
そこで本稿では,エポックで動作するロバストな除去型アルゴリズムを提案し,探索と頻繁な切替を併用して,小さなアクションサブセットを選択し,各アクションを複数タイミングで実行する。
我々のアルゴリズムであるGP Robust Phased Elimination (RGP-PE) は、探索とエクスプロイトによる汚職に対するロバストネスのバランスに成功している。
GPバンディット設定におけるロバスト性の最初の実証的研究を行い,アルゴリズムが様々な敵攻撃に対してロバストであることを示す。
論文 参考訳（メタデータ） (2022-02-03T21:19:36Z) - Inferring Hidden Structures in Random Graphs [13.031167737538881]
本研究では,ランダムなグラフ上に植えられた群集群集の検出と復元の2つの推論問題について検討する。
我々は、パラメータ $(n,k,q)$ や $Gamma_k$ の特定の性質の観点から、構造を検出・復元するための下限を導出し、これらの下限を達成するための計算学的に最適なアルゴリズムを示す。
論文 参考訳（メタデータ） (2021-10-05T09:39:51Z) - Hardness of Random Optimization Problems for Boolean Circuits,
Low-Degree Polynomials, and Langevin Dynamics [78.46689176407936]
アルゴリズムの族は高い確率でほぼ最適な解を生成できないことを示す。
ブール回路の場合、回路複雑性理論で知られている最先端境界を改善する。
論文 参考訳（メタデータ） (2020-04-25T05:45:59Z) - NeCPD: An Online Tensor Decomposition with Optimal Stochastic Gradient
Descent [1.0953917735844645]
マルチウェイオンラインデータに基づく$(N)Nにおける非効率的な問題に対して,NeCPDという新しい効率的な分解アルゴリズムを提案する。
さらに,本手法を構造的データセットを用いた実生活モニタリングの分野に適用する。
論文 参考訳（メタデータ） (2020-03-18T04:44:05Z) - Better Theory for SGD in the Nonconvex World [2.6397379133308214]
大規模な非最適化問題は、現代の機械学習ではユビキタスである。
我々は, 広範囲の合成ミニバッチサイズがグラディエントDescent (SG) 問題に与える影響について実験を行った。
論文 参考訳（メタデータ） (2020-02-09T09:56:06Z) - Towards Better Understanding of Adaptive Gradient Algorithms in
Generative Adversarial Nets [71.05306664267832]
適応アルゴリズムは勾配の歴史を用いて勾配を更新し、深層ニューラルネットワークのトレーニングにおいてユビキタスである。
本稿では,非コンケーブ最小値問題に対するOptimisticOAアルゴリズムの変種を解析する。
実験の結果,適応型GAN非適応勾配アルゴリズムは経験的に観測可能であることがわかった。
論文 参考訳（メタデータ） (2019-12-26T22:10:10Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。