論文の概要: OneMax is not the Easiest Function for Fitness Improvements
- arxiv url: http://arxiv.org/abs/2204.07017v1
- Date: Thu, 14 Apr 2022 15:13:40 GMT
- ステータス: 処理完了
- システム内更新日: 2023-02-17 00:07:59.491313
- Title: OneMax is not the Easiest Function for Fitness Improvements
- Title（参考訳）: OneMaxはフィットネス改善のための最も簡単な機能ではない
- Authors: Marc Kaufmann, Maxime Larcher, Johannes Lengler, Xun Zou
- Abstract要約: 1:lambda)$-EAの集団サイズを制御するために、$ (1:s+1)$ successルールを研究します。
OneMaxは、改善ステップの発見に関して、最も簡単なフィットネスランドスケープではないことを示す。
- 参考スコア（独自算出の注目度）: 7.111443975103329
- License: http://creativecommons.org/licenses/by-nc-nd/4.0/
- Abstract: We study the $(1:s+1)$ success rule for controlling the population size of
the $(1,\lambda)$-EA. It was shown by Hevia Fajardo and Sudholt that this
parameter control mechanism can run into problems for large $s$ if the fitness
landscape is too easy. They conjectured that this problem is worst for the
OneMax benchmark, since in some well-established sense OneMax is known to be
the easiest fitness landscape. In this paper we disprove this conjecture and
show that OneMax is not the easiest fitness landscape with respect to finding
improving steps.
As a consequence, we show that there exists $s$ and $\varepsilon$ such that
the self-adjusting $(1,\lambda)$-EA with $(1:s+1)$-rule optimizes OneMax
efficiently when started with $\varepsilon n$ zero-bits, but does not find the
optimum in polynomial time on Dynamic BinVal. Hence, we show that there are
landscapes where the problem of the $(1:s+1)$-rule for controlling the
population size of the $(1, \lambda)$-EA is more severe than for OneMax.
- Abstract（参考訳）: 我々は、$(1,\lambda)$-EAの集団サイズを制御するために、$(1:s+1)$ successルールを研究する。
Hevia Fajardo と Sudholt は、このパラメータ制御機構がフィットネスランドスケープが簡単すぎると、大きな$s$で問題に陥ることを示した。
彼らは、この問題がonemaxベンチマークにとって最悪のものであると推測した。
本稿では、この予想を否定し、onemaxが改善ステップを見つける上で最も簡単なフィットネス環境ではないことを示す。
その結果、$(1,\lambda)$-ea を$(1:s+1)$-rule で自己調整することで$\varepsilon n$ zero-bits で開始すると 1max を効率的に最適化できるが、動的binval における多項式時間の最適値を見いだせない $s$ と $\varepsilon$ が存在する。
したがって、$(1, \lambda)$-ea の人口サイズを制御するための$(1:s+1)$-rule という問題は onemax よりも厳しいものである。
関連論文リスト
- Two-Timescale Gradient Descent Ascent Algorithms for Nonconvex Minimax Optimization [77.3396841985172]
我々は、構造化された非極小最適化問題の解法として、2時間勾配上昇(TTGDA)を統一的に解析する。
我々の貢献はTTGDAアルゴリズムを設計することであり、設定を超えて効果的です。
論文 参考訳（メタデータ） (2024-08-21T20:14:54Z) - Hard Problems are Easier for Success-based Parameter Control [0.0]
進化的アルゴリズムにおける自己調整パラメータは、離散的な問題において最良の固定パラメータにマッチするか、より優れる。
簡単な斜面がない場合、自己調整が意図されたように機能することを示す。
本稿では,難易度の高い難易度の高い難易度の高い難易度関数のLeadingOnesと新しいクラスOneMaxBlocksについて論じる。
論文 参考訳（メタデータ） (2022-04-12T13:56:29Z) - Self-adjusting Population Sizes for the $(1, \lambda)$-EA on Monotone
Functions [7.111443975103329]
突然変異率$c/n$ for $cle 1$で、1:s+1)$-successルールで集団サイズを適応的に制御する。
この$c=1$のセットアップは1maxで$s1$で効率的であるが、$s ge 18$で非効率的であることを示す。
論文 参考訳（メタデータ） (2022-04-01T15:46:12Z) - Nonconvex-Nonconcave Min-Max Optimization with a Small Maximization
Domain [11.562923882714093]
Y f(x,y) における max_y の $min_x 形式の最適化問題における近似一階定常点の探索問題について検討する。
我々のアプローチは、関数 $f(x,cdot)$ を $k 次テイラー近似($y$ で)に置き換え、ほぼ定常点を $Y$ で見つけることに依存する。
論文 参考訳（メタデータ） (2021-10-08T07:46:18Z) - Self-Adjusting Population Sizes for Non-Elitist Evolutionary Algorithms:
Why Success Rates Matter [0.0]
進化的アルゴリズム(EA)は、親や子孫のサイズや突然変異率など、いくつかのパラメータを持つ汎用的なオプティマイザである。
最近の理論的研究により、自己調整パラメータ制御機構は離散的な問題においてEAの最高の静的パラメータよりも優れていることが示されている。
論文 参考訳（メタデータ） (2021-04-12T16:44:54Z) - Private Stochastic Convex Optimization: Optimal Rates in $\ell_1$
Geometry [69.24618367447101]
対数要因まで $(varepsilon,delta)$-differently private の最適過剰人口損失は $sqrtlog(d)/n + sqrtd/varepsilon n.$ です。
損失関数がさらなる滑らかさの仮定を満たすとき、余剰損失は$sqrtlog(d)/n + (log(d)/varepsilon n)2/3で上界(対数因子まで)であることが示される。
論文 参考訳（メタデータ） (2021-03-02T06:53:44Z) - Projection Efficient Subgradient Method and Optimal Nonsmooth
Frank-Wolfe Method [54.93433440034386]
実現可能な$epsilon$-suboptimalソリューションは、$O(epsilon-1)$ POコールと最適な$O(epsilon-2)$ FOコールのみを使用します。
提案手法は,POおよびLMOコールのコストがかかる問題に対して,最先端技術に対する大幅な高速化を実現するものであることを確認した。
論文 参考訳（メタデータ） (2020-10-05T08:16:56Z) - The Complexity of Constrained Min-Max Optimization [29.57458485068705]
十分大きな局所点 min-max が存在することが保証されていることを示す。
さらに重要なこととして、近似的な固定勾配 Descent/Ascent 近似が完成することを示す。
この結果は、2つの基本的な最適化問題の指数関数近似を初めて示したものである。
論文 参考訳（メタデータ） (2020-09-21T05:54:12Z) - Streaming Complexity of SVMs [110.63976030971106]
本稿では,ストリーミングモデルにおけるバイアス正規化SVM問題を解く際の空間複雑性について検討する。
両方の問題に対して、$frac1lambdaepsilon$の次元に対して、$frac1lambdaepsilon$よりも空間的に小さいストリーミングアルゴリズムを得ることができることを示す。
論文 参考訳（メタデータ） (2020-07-07T17:10:00Z) - Maximizing Determinants under Matroid Constraints [69.25768526213689]
我々は、$det(sum_i in Sv_i v_i v_itop)$が最大になるような基底を$S$$$$M$とする問題を研究する。
この問題は、実験的なデザイン、商品の公平な割り当て、ネットワーク設計、機械学習など、さまざまな分野に現れている。
論文 参考訳（メタデータ） (2020-04-16T19:16:38Z) - On Gradient Descent Ascent for Nonconvex-Concave Minimax Problems [86.92205445270427]
非コンミニマックス問題、$min_mathbfx max_mathhidoty f(mathbfdoty)$を効率的に考える。
論文 参考訳（メタデータ） (2019-06-02T03:03:45Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。