論文の概要: Hard Problems are Easier for Success-based Parameter Control
- arxiv url: http://arxiv.org/abs/2204.05817v1
- Date: Tue, 12 Apr 2022 13:56:29 GMT
- ステータス: 処理完了
- システム内更新日: 2023-02-17 05:34:53.228756
- Title: Hard Problems are Easier for Success-based Parameter Control
- Title（参考訳）: 成功度に基づくパラメータ制御の難易度
- Authors: Mario Alejandro Hevia Fajardo and Dirk Sudholt
- Abstract要約: 進化的アルゴリズムにおける自己調整パラメータは、離散的な問題において最良の固定パラメータにマッチするか、より優れる。
簡単な斜面がない場合、自己調整が意図されたように機能することを示す。
本稿では,難易度の高い難易度の高い難易度の高い難易度関数のLeadingOnesと新しいクラスOneMaxBlocksについて論じる。
- 参考スコア（独自算出の注目度）: 0.0
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Recent works showed that simple success-based rules for self-adjusting
parameters in evolutionary algorithms (EAs) can match or outperform the best
fixed parameters on discrete problems. Non-elitism in a (1,$\lambda$) EA
combined with a self-adjusting offspring population size $\lambda$ outperforms
common EAs on the multimodal Cliff problem. However, it was shown that this
only holds if the success rate $s$ that governs self-adjustment is small
enough. Otherwise, even on OneMax, the self-adjusting (1,$\lambda$) EA
stagnates on an easy slope, where frequent successes drive down the offspring
population size. We show that self-adjustment works as intended in the absence
of easy slopes. We define everywhere hard functions, for which successes are
never easy to find and show that the self-adjusting (1,$\lambda$) EA is robust
with respect to the choice of success rates $s$. We give a general
fitness-level upper bound on the number of evaluations and show that the
expected number of generations is at most $O(d + \log(1/p_{\min}))$ where $d$
is the number of non-optimal fitness values and $p_{\min}$ is the smallest
probability of finding an improvement from a non-optimal search point. We
discuss implications for the everywhere hard function LeadingOnes and a new
class OneMaxBlocks of everywhere hard functions with tunable difficulty.
- Abstract（参考訳）: 近年の研究では、進化的アルゴリズム(EA)における自己調整パラメータの単純な成功に基づくルールは、離散的な問題において最適な固定パラメータに適合または優れることを示した。
1,$\lambda$) の EA における非楕円と自己調整オフスプリングサイズ$\lambda$ は、マルチモーダルクリフ問題において共通の EA よりも優れる。
しかし、これは自己調整を管理する成功率$s$が十分小さい場合にのみ成立することを示した。
さもなければ、onemaxでも、自己調整(1,$\lambda$)eaは容易な斜面で停滞し、頻繁な成功が子孫の個体数を減少させる。
傾斜が容易でないことを意図した自己調整が機能することを示す。
私たちはあらゆるハード関数を定義し、成功は決して見つけられず、自己調整(1,$\lambda$) eaが成功率($s$)の選択に関して堅牢であることを示す。
評価数に対する一般的なフィットネスレベル上限を与え、期待される世代数は最大$O(d + \log(1/p_{\min})$で、$d$は最適でないフィットネス値の数であり、$p_{\min}$は最適でない検索点から改善を見出す最小の確率であることを示す。
そこで我々は,難易度の高い難易度の高い難易度関数のLeadingOnesと新しいクラスOneMaxBlocksについて論じる。
関連論文リスト
- Nearly Minimax Optimal Regret for Learning Linear Mixture Stochastic
Shortest Path [80.60592344361073]
線形混合遷移カーネルを用いた最短経路(SSP)問題について検討する。
エージェントは繰り返し環境と対話し、累積コストを最小化しながら特定の目標状態に到達する。
既存の作業は、イテレーションコスト関数の厳密な下限や、最適ポリシーに対する期待長の上限を仮定することが多い。
論文 参考訳（メタデータ） (2024-02-14T07:52:00Z) - Revisiting Inexact Fixed-Point Iterations for Min-Max Problems: Stochasticity and Structured Nonconvexity [18.427215139020632]
1L 1$は、マルチレベルなCarloイテレーションであっても、最先端の問題を改善するために使用できることを示す。
解に関する唯一のホールドが新しい1L 1$理論である場合、不正確なハルパーネス推定器を1L 1$で解析する。
論文 参考訳（メタデータ） (2024-02-07T18:22:41Z) - Agnostically Learning Multi-index Models with Queries [54.290489524576756]
本稿では,ガウス分布下での非依存学習の課題に対するクエリアクセスのパワーについて検討する。
クエリアクセスは、MIMを不可知的に学習するためのランダムな例よりも大幅に改善されていることを示す。
論文 参考訳（メタデータ） (2023-12-27T15:50:47Z) - Hardest Monotone Functions for Evolutionary Algorithms [0.0]
自己調整する$(1,lambda)$-EAに対して、Adrial Dynamic BinVal (ADBV) は最適化する最も難しい動的単調関数である。
本稿では,探索点内の残零点数が$n/2$未満である場合に,ADBVと一致する関数スイッチング動的ビンVal(SDBV)を導入する。
論文 参考訳（メタデータ） (2023-11-13T16:13:30Z) - Larger Offspring Populations Help the $(1 + (\lambda, \lambda))$ Genetic
Algorithm to Overcome the Noise [76.24156145566425]
進化的アルゴリズムは、適合性の評価においてノイズに対して堅牢であることが知られている。
我々は$(lambda,lambda)$の遺伝的アルゴリズムがどんなにノイズに強いかを解析する。
論文 参考訳（メタデータ） (2023-05-08T08:49:01Z) - Best Policy Identification in Linear MDPs [70.57916977441262]
縮退した線形マルコフ+デルタ決定における最適同定問題について, 生成モデルに基づく固定信頼度設定における検討を行った。
複雑な非最適化プログラムの解としての下位境界は、そのようなアルゴリズムを考案する出発点として用いられる。
論文 参考訳（メタデータ） (2022-08-11T04:12:50Z) - Multi-block-Single-probe Variance Reduced Estimator for Coupled
Compositional Optimization [49.58290066287418]
構成問題の複雑さを軽減するために,MSVR (Multi-block-probe Variance Reduced) という新しい手法を提案する。
本研究の結果は, 試料の複雑さの順序や強靭性への依存など, 様々な面で先行して改善された。
論文 参考訳（メタデータ） (2022-07-18T12:03:26Z) - Focused Jump-and-Repair Constraint Handling for Fixed-Parameter
Tractable Graph Problems Closed Under Induced Subgraphs [3.495114525631289]
グラフ問題における不可能な子孫の確率的修復に使用できる調整されたジャンプ・アンド・リペア操作を備えた(1+1)EAについて検討する。
論文 参考訳（メタデータ） (2022-03-25T19:36:02Z) - Self-Adjusting Population Sizes for Non-Elitist Evolutionary Algorithms:
Why Success Rates Matter [0.0]
進化的アルゴリズム(EA)は、親や子孫のサイズや突然変異率など、いくつかのパラメータを持つ汎用的なオプティマイザである。
最近の理論的研究により、自己調整パラメータ制御機構は離散的な問題においてEAの最高の静的パラメータよりも優れていることが示されている。
論文 参考訳（メタデータ） (2021-04-12T16:44:54Z) - 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) - Nonconvex Zeroth-Order Stochastic ADMM Methods with Lower Function Query
Complexity [109.54166127479093]
ゼロ次法(ゼロ次法、英: Zeroth-order method)は、機械学習問題を解決するための効果的な最適化手法のクラスである。
本稿では,非有限項問題を解くために,より高速なゼロ階交互勾配法乗算器 (MMADMM) を提案する。
我々は、ZOMMAD法が、$epsilon$-stationary pointを見つけるために、より低い関数$O(frac13nfrac1)$を達成することができることを示す。
同時に、より高速なゼロオーダーオンラインADM手法(M)を提案する。
論文 参考訳（メタデータ） (2019-07-30T02:21:43Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。