論文の概要: Theoretical Study of Optimizing Rugged Landscapes with the cGA
- arxiv url: http://arxiv.org/abs/2211.13801v1
- Date: Thu, 24 Nov 2022 21:10:15 GMT
- ステータス: 処理完了
- システム内更新日: 2022-11-28 15:33:22.008425
- Title: Theoretical Study of Optimizing Rugged Landscapes with the cGA
- Title(参考訳): cGAを用いた荒地景観の最適化に関する理論的研究
- Authors: Tobias Friedrich, Timo K\"otzing, Frank Neumann, Aishwarya
Radhakrishnan
- Abstract要約: 私たちは、各フィットネス値にノイズを加えることでOneMax関数を頑丈にします。
にもかかわらず、cGA は n ( 1 - epsilon) 個の数 1 の解を見つけることができる。
対照的に、 RLS と (1+1) EA は高い確率で n(1/2+o(1)) 個の 1 の解しか見つからない。
- 参考スコア(独自算出の注目度): 17.84551868483591
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Estimation of distribution algorithms (EDAs) provide a distribution - based
approach for optimization which adapts its probability distribution during the
run of the algorithm. We contribute to the theoretical understanding of EDAs
and point out that their distribution approach makes them more suitable to deal
with rugged fitness landscapes than classical local search algorithms.
Concretely, we make the OneMax function rugged by adding noise to each fitness
value. The cGA can nevertheless find solutions with n(1 - \epsilon) many 1s,
even for high variance of noise. In contrast to this, RLS and the (1+1) EA,
with high probability, only find solutions with n(1/2+o(1)) many 1s, even for
noise with small variance.
- Abstract(参考訳): 分散アルゴリズム(EDAs)の推定は、アルゴリズムの実行中に確率分布を適応させる最適化のための分布に基づくアプローチを提供する。
我々はedasの理論的理解に寄与し,それらの分散アプローチにより,従来の局所探索アルゴリズムよりも頑丈なフィットネス環境に適応できることを指摘した。
具体的には、各フィットネス値にノイズを加えてOneMax関数を頑丈にする。
にもかかわらず、cGA は n(1 - \epsilon) 個の 1 の解を見つけることができる。
これとは対照的に、高い確率で RLS と (1+1) EA は n(1/2+o(1)) 個の 1 の解しか見つからない。
関連論文リスト
- Runtime Analysis of a Multi-Valued Compact Genetic Algorithm on Generalized OneMax [2.07180164747172]
一般化されたOneMax関数の最初のランタイム解析を提供する。
r-cGAはこのr値のOneMax問題を効率的に解くことを示す。
実験の最後には、多値OneMax関数の別の変種が期待されるランタイムに関する予想を述べる。
論文 参考訳(メタデータ) (2024-04-17T10:40:12Z) - Quality-Diversity Algorithms Can Provably Be Helpful for Optimization [24.694984679399315]
QD(Quality-Diversity)アルゴリズムは、ハイパフォーマンスだが多様なソリューションのセットを見つけることを目的としている。
本稿では,厳密な実行時間解析によってQDアルゴリズムの最適化能力に光を当てようとしている。
論文 参考訳(メタデータ) (2024-01-19T07:40:24Z) - Distributed Extra-gradient with Optimal Complexity and Communication
Guarantees [60.571030754252824]
複数のプロセッサ/ワーカー/クライアントがローカルなデュアルベクトルにアクセス可能なマルチGPU設定において、モノトン変分不等式(VI)問題を考察する。
モノトーンVI問題に対するデファクトアルゴリズムであるExtra-gradientは、通信効率が良くないように設計されている。
そこで本稿では,VI の解法に適した非バイアスで適応的な圧縮手法である量子化一般化外部勾配 (Q-GenX) を提案する。
論文 参考訳(メタデータ) (2023-08-17T21:15:04Z) - Optimal design of the Barker proposal and other locally-balanced
Metropolis-Hastings algorithms [0.2148535041822524]
We study the class of first-order local- Balanced Metropolis--Hastings algorithm introduced in Livingstone & Zanella (2021)
クラス内で特定のアルゴリズムを選択するには、ユーザは、$g(t) = tg (1/t)$を満たすバランス関数 $g:mathbbR to mathbbR$と、提案のためのノイズ分布を選択する必要がある。
ベイカー提案における雑音分布の最適選択、ガウス雑音分布下でのバランス関数の最適選択、一階局所バランスアルゴリズムの最適選択を導出する。
論文 参考訳(メタデータ) (2022-01-04T13:06:50Z) - Near-Optimal High Probability Complexity Bounds for Non-Smooth
Stochastic Optimization with Heavy-Tailed Noise [63.304196997102494]
アルゴリズムが高い確率で小さな客観的残差を与えることを理論的に保証することが不可欠である。
既存の非滑らか凸最適化法は、負のパワーまたは対数的な信頼度に依存する境界の複雑さを持つ。
クリッピングを用いた2つの勾配法に対して, 新たなステップサイズルールを提案する。
論文 参考訳(メタデータ) (2021-06-10T17:54:21Z) - Projected Stochastic Gradient Langevin Algorithms for Constrained
Sampling and Non-Convex Learning [0.0]
ランジュバンアルゴリズムは付加ノイズを持つ手法である。
ランジュバンアルゴリズムは何十年もチェーンカルロ(ミロン)で使われてきた
学習にとって、それはそれがそれが事実であるということであり、それが事実であるということであり、それが事実であるということであり、それが事実であるということであり、それが事実であるということであり、それがそれが事実であるということであり、それがそれがそれが事実であるということであるということであるということが、それが事実であるということであるということが、それが事実であるということであることを示している。
論文 参考訳(メタデータ) (2020-12-22T16:19:20Z) - Convergence of adaptive algorithms for weakly convex constrained
optimization [59.36386973876765]
モローエンベロープの勾配のノルムに対して$mathcaltilde O(t-1/4)$収束率を証明する。
我々の分析では、最小バッチサイズが1ドル、定数が1位と2位のモーメントパラメータが1ドル、そしておそらくスムーズな最適化ドメインで機能する。
論文 参考訳(メタデータ) (2020-06-11T17:43:19Z) - Learning Halfspaces with Tsybakov Noise [50.659479930171585]
テュバコフ雑音の存在下でのハーフスペースの学習可能性について検討する。
真半空間に関して誤分類誤差$epsilon$を達成するアルゴリズムを与える。
論文 参考訳(メタデータ) (2020-06-11T14:25:02Z) - Private Stochastic Convex Optimization: Optimal Rates in Linear Time [74.47681868973598]
本研究では,凸損失関数の分布から得られた個体群損失を最小化する問題について検討する。
Bassilyらによる最近の研究は、$n$のサンプルを与えられた過剰な人口損失の最適境界を確立している。
本稿では,余剰損失に対する最適境界を達成するとともに,$O(minn, n2/d)$グラデーション計算を用いて凸最適化アルゴリズムを導出する2つの新しい手法について述べる。
論文 参考訳(メタデータ) (2020-05-10T19:52:03Z) - Hardness of Random Optimization Problems for Boolean Circuits,
Low-Degree Polynomials, and Langevin Dynamics [78.46689176407936]
アルゴリズムの族は高い確率でほぼ最適な解を生成できないことを示す。
ブール回路の場合、回路複雑性理論で知られている最先端境界を改善する。
論文 参考訳(メタデータ) (2020-04-25T05:45:59Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。