論文の概要: Runtime Analysis of Restricted Tournament Selection for Bimodal
Optimisation
- arxiv url: http://arxiv.org/abs/2201.06485v1
- Date: Mon, 17 Jan 2022 15:57:22 GMT
- ステータス: 処理完了
- システム内更新日: 2023-02-28 22:46:08.659300
- Title: Runtime Analysis of Restricted Tournament Selection for Bimodal
Optimisation
- Title（参考訳）: バイモーダル最適化のための制限トーナメント選択の実行時間解析
- Authors: Edgar Covantes Osuna and Dirk Sudholt
- Abstract要約: 本稿では,制限されたトーナメント選択(RTS)をEA(mu$+1)に埋め込んだ,厳密な実行時解析について述べる。
ウィンドウサイズ$w$が十分大きい場合、RTSが$rm T Small WOM Small AX$ で両方のオプティマを効率的に見つけることを証明します。
我々は,トーナメント・エンハンスアウトの個人を選抜するRTSの変種を考える。それはより多様なトーナメントを生み出し,一方のニッチが他方のニッチを乗っ取るのを防ぐのに効果的である。
- 参考スコア（独自算出の注目度）: 0.0
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Niching methods have been developed to maintain the population diversity, to
investigate many peaks in parallel and to reduce the effect of genetic drift.
We present the first rigorous runtime analyses of restricted tournament
selection (RTS), embedded in a ($\mu$+1) EA, and analyse its effectiveness at
finding both optima of the bimodal function ${\rm T{\small WO}M{\small AX}}$.
In RTS, an offspring competes against the closest individual, with respect to
some distance measure, amongst $w$ (window size) population members (chosen
uniformly at random with replacement), to encourage competition within the same
niche. We prove that RTS finds both optima on ${\rm T{\small WO}M{\small AX}}$
efficiently if the window size $w$ is large enough. However, if $w$ is too
small, RTS fails to find both optima even in exponential time, with high
probability. We further consider a variant of RTS selecting individuals for the
tournament \emph{without} replacement. It yields a more diverse tournament and
is more effective at preventing one niche from taking over the other. However,
this comes at the expense of a slower progress towards optima when a niche
collapses to a single individual. Our theoretical results are accompanied by
experimental studies that shed light on parameters not covered by the
theoretical results and support a conjectured lower runtime bound.
- Abstract（参考訳）: ニチング法は個体群多様性を維持し、多くのピークを並行して調査し、遺伝的ドリフトの効果を減らすために開発された。
本稿では,制限トーナメント選択 (RTS) の最初の厳密な実行時解析を行い,2モーダル関数 ${\rm T{\small WO}M{\small AX}}$ の最適性を求める上での有効性について述べる。
rtsでは、子孫は距離測定に関して最も近い個人と競い合っており、同じニッチ内で競争を促進するためにw$(ウィンドウサイズ)の人口構成者(チョーゼンはランダムに交換される)の間で競う。
ウィンドウサイズ$w$ が十分大きい場合、rts が${\rm t{\small wo}m{\small ax}}$ で両方のオプティマを見つけることが証明される。
しかし、$w$ が小さすぎると、RTS は指数時間でも両方のオプティマを見つけることができず、確率が高い。
さらに、トーナメントの代替となる「emph{without}」の個人を選択するRTSの変種についても検討する。
より多様なトーナメントをもたらし、一方のニッチが他方のニッチを乗っ取るのを防ぐ効果がある。
しかしこれは、ニッチが1つの個人に崩壊すると、オプティマへの進行が遅くなるためである。
我々の理論的結果は、理論的結果でカバーされていないパラメータに光を当て、予想されたより低いランタイムバウンドをサポートする実験的研究を伴う。
関連論文リスト
- Exploration by Optimization with Hybrid Regularizers: Logarithmic Regret
with Adversarial Robustness in Partial Monitoring [46.30750729936261]
敵環境における最適境界を実現するための最適化による探索(ExO)が提案された。
まず,ハイブリッド正規化器を用いたExOの新しいフレームワークと解析手法を構築した。
特に、$O(sum_a neq a* k2 log T / Delta_a)$で、$a*$は最適なアクションであり、$Delta_a$はアクションの亜最適ギャップである。
論文 参考訳（メタデータ） (2024-02-13T09:34:22Z) - (Accelerated) Noise-adaptive Stochastic Heavy-Ball Momentum [7.095058159492494]
ヘビーボール運動量(SHB)は、機械学習モデルのトレーニングに一般的に用いられ、勾配降下の反復よりも経験的な改善を提供することが多い。
SHB は小サイズが $kappa の閾値 $b* よりも大きい場合に加速できることを示す。
論文 参考訳（メタデータ） (2024-01-12T18:17:28Z) - Settling the Sample Complexity of Online Reinforcement Learning [92.02082223856479]
バーンインコストを発生させることなく、最小限の最適後悔を実現する方法を示す。
最適値/コストや一定の分散といった問題依存量の影響を明らかにするために、我々の理論を拡張します。
論文 参考訳（メタデータ） (2023-07-25T15:42:11Z) - Stochastic Approximation Approaches to Group Distributionally Robust
Optimization [96.26317627118912]
群分散ロバスト最適化(GDRO)
オンライン学習技術は、各ラウンドに必要なサンプル数をm$から1$に減らし、同じサンプルを保持する。
分布依存収束率を導出できる重み付きGDROの新規な定式化。
論文 参考訳（メタデータ） (2023-02-18T09:24:15Z) - Minimax-Optimal Multi-Agent RL in Zero-Sum Markov Games With a
Generative Model [50.38446482252857]
2人プレイのゼロサムマルコフゲームは多エージェント強化学習においておそらく最も基本的な設定である。
我々は,$$ widetildeObiggを用いて,$varepsilon$-approximate Markov NEポリシーを学習する学習アルゴリズムを開発した。
我々は、分散型量の役割を明確にするFTRLに対する洗練された後悔境界を導出する。
論文 参考訳（メタデータ） (2022-08-22T17:24:55Z) - Running Time Analysis of the Non-dominated Sorting Genetic Algorithm II
(NSGA-II) using Binary or Stochastic Tournament Selection [27.270523212333018]
本稿では,LOTZ,OneMinMax,COCZを解くための標準NSGA-IIのランニング時間解析について述べる。
具体的には、LOTZが$O(n3)$、OneMinMaxとCOCZが$O(n2log n)$であることを示す。
また, ランニングタイム上界はLOTZに強く, OneMinMax と COCZ にほぼ密であることを示す実験も行われた。
論文 参考訳（メタデータ） (2022-03-22T09:10:50Z) - PDPGD: Primal-Dual Proximal Gradient Descent Adversarial Attack [92.94132883915876]
最先端のディープニューラルネットワークは、小さな入力摂動に敏感である。
対向騒音に対するロバスト性を改善するための多くの防御法が提案されている。
敵の強靭さを評価することは 極めて困難であることが分かりました
論文 参考訳（メタデータ） (2021-06-03T01:45:48Z) - 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) - 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) - Toward Adversarial Robustness via Semi-supervised Robust Training [93.36310070269643]
アドリラルな例は、ディープニューラルネットワーク(DNN)に対する深刻な脅威であることが示されている。
R_stand$ と $R_rob$ の2つの異なるリスクを共同で最小化することで、新しい防御手法であるロバストトレーニング(RT)を提案する。
論文 参考訳（メタデータ） (2020-03-16T02:14:08Z) - Curse of Dimensionality on Randomized Smoothing for Certifiable
Robustness [151.67113334248464]
我々は、他の攻撃モデルに対してスムースな手法を拡張することは困難であることを示す。
我々はCIFARに関する実験結果を示し,その理論を検証した。
論文 参考訳（メタデータ） (2020-02-08T22:02:14Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。