論文の概要: Hardest Monotone Functions for Evolutionary Algorithms

• arxiv url: http://arxiv.org/abs/2311.07438v1
• Date: Mon, 13 Nov 2023 16:13:30 GMT
• ステータス: 処理完了
• システム内更新日: 2023-11-14 13:47:55.578064
• Title: Hardest Monotone Functions for Evolutionary Algorithms
• Title（参考訳）: 進化アルゴリズムのための最も難しい単調関数
• Authors: Marc Kaufmann and Maxime Larcher and Johannes Lengler and Oliver Sieberling
• Abstract要約: 自己調整する$(1,lambda)$-EAに対して、Adrial Dynamic BinVal (ADBV) は最適化する最も難しい動的単調関数である。 本稿では,探索点内の残零点数が$n/2$未満である場合に,ADBVと一致する関数スイッチング動的ビンVal(SDBV)を導入する。
• 参考スコア（独自算出の注目度）: 0.0
• License: http://creativecommons.org/licenses/by-nc-nd/4.0/
• Abstract: The study of hardest and easiest fitness landscapes is an active area of research. Recently, Kaufmann, Larcher, Lengler and Zou conjectured that for the self-adjusting $(1,\lambda)$-EA, Adversarial Dynamic BinVal (ADBV) is the hardest dynamic monotone function to optimize. We introduce the function Switching Dynamic BinVal (SDBV) which coincides with ADBV whenever the number of remaining zeros in the search point is strictly less than $n/2$, where $n$ denotes the dimension of the search space. We show, using a combinatorial argument, that for the $(1+1)$-EA with any mutation rate $p \in [0,1]$, SDBV is drift-minimizing among the class of dynamic monotone functions. Our construction provides the first explicit example of an instance of the partially-ordered evolutionary algorithm (PO-EA) model with parameterized pessimism introduced by Colin, Doerr and F\'erey, building on work of Jansen. We further show that the $(1+1)$-EA optimizes SDBV in $\Theta(n^{3/2})$ generations. Our simulations demonstrate matching runtimes for both static and self-adjusting $(1,\lambda)$ and $(1+\lambda)$-EA. We further show, using an example of fixed dimension, that drift-minimization does not equal maximal runtime.
• Abstract（参考訳）: 最も硬く、最も易しいフィットネスランドスケープの研究は、活発な研究領域である。 近年、Kaufmann, Larcher, Lengler and Zou は、自己調整の $(1,\lambda)$-EA に対して、Adversarial Dynamic BinVal (ADBV) は最適化する最も難しい動的単調関数であると予想している。 探索点内の残零点数が厳密には$n/2$未満である場合,$n$が検索空間の次元を表すとき, ADBV と一致する関数 Switching Dynamic BinVal (SDBV) を導入する。 1+1)$-EAの変異率$p \in [0,1]$の場合、SDBVは動的単調関数のクラスの中でドリフト最小化されていることを示す。 我々の構成は、Jansenの業績に基づくColin, Doerr, F\'ereyによって導入されたパラメータ化悲観的な部分順序進化アルゴリズム(PO-EA)モデルの例の最初の明示的な例を提供する。 さらに、$(1+1)$-EAは$\Theta(n^{3/2})$ジェネレーションでSDBVを最適化する。 我々のシミュレーションでは、静的および自己調整の両方のランタイムを、$(1,\lambda)$と$(1+\lambda)$-EAで表しています。 さらに,固定次元の例を用いて,ドリフト最小化が最大ランタイムに等しくないことを示す。

関連論文リスト

• Proven Runtime Guarantees for How the MOEA/D Computes the Pareto Front From the Subproblem Solutions [9.044970217182117]
  分解に基づく多目的進化アルゴリズム(MOEA/D)は、与えられた多目的関数$f$を直接最適化するのではなく、共進化的に$f$の単目的サブプロブレム$N + 1$を最適化する。 我々は、標準突然変異演算子のみを持つMOEA/Dが、OneMinMaxベンチマークのPareto全体を計算する方法について、初めて分析する。 パワーローに対する我々の全体的な境界は、MOEA/D が$N = O(nbeta - 1)$ に対して最も良く、結果として$O(n) となることを示唆している。
  論文  参考訳（メタデータ） (2024-05-02T05:32:19Z)
• Kernelized Normalizing Constant Estimation: Bridging Bayesian Quadrature and Bayesian Optimization [51.533164528799084]
  小さい相対誤差内で正規化定数を推定するために、難易度は$lambda$の値に依存する。 関数評価がノイズである場合でも,このパターンは真であることがわかった。
  論文  参考訳（メタデータ） (2024-01-11T07:45:09Z)
• Statistical Learning under Heterogeneous Distribution Shift [71.8393170225794]
  ground-truth predictor is additive $mathbbE[mathbfz mid mathbfx,mathbfy] = f_star(mathbfx) +g_star(mathbfy)$.
  論文  参考訳（メタデータ） (2023-02-27T16:34:21Z)
• Improved Dynamic Regret for Online Frank-Wolfe [54.690867216880356]
  オンライン凸最適化のための効率的なプロジェクションフリーアルゴリズムであるFrank-Wolfe (OFW) の動的後悔について検討する。 本稿では,FWの高速収束率をオフライン最適化からオンライン最適化に拡張することにより,OFWの動的後悔境界の改善を導出する。
  論文  参考訳（メタデータ） (2023-02-11T07:19:51Z)
• 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)
• 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)
• Runtime analysis of the (mu+1)-EA on the Dynamic BinVal function [0.0]
  進化的アルゴリズムを動的に研究し、各世代ごとに異なる適合関数が選択される。 特に、最適化の最も難しい領域は最適化の周辺ではない。
  論文  参考訳（メタデータ） (2020-10-26T08:55:53Z)
• Streaming Complexity of SVMs [110.63976030971106]
  本稿では,ストリーミングモデルにおけるバイアス正規化SVM問題を解く際の空間複雑性について検討する。 両方の問題に対して、$frac1lambdaepsilon$の次元に対して、$frac1lambdaepsilon$よりも空間的に小さいストリーミングアルゴリズムを得ることができることを示す。
  論文  参考訳（メタデータ） (2020-07-07T17:10:00Z)
• 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)
• A Simple Convergence Proof of Adam and Adagrad [74.24716715922759]
  我々はAdam Adagradと$O(d(N)/st)$アルゴリズムの収束の証明を示す。 Adamはデフォルトパラメータで使用する場合と同じ収束$O(d(N)/st)$で収束する。
  論文  参考訳（メタデータ） (2020-03-05T01:56:17Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。