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

• arxiv url: http://arxiv.org/abs/2311.07438v2
• Date: Tue, 01 Jul 2025 14:22:27 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-07-02 15:54:39.899734
• Title: Hardest Monotone Functions for Evolutionary Algorithms
• Title（参考訳）: 進化的アルゴリズムのための最も硬いモノトン関数
• Authors: Marc Kaufmann, Maxime Larcher, Johannes Lengler, Oliver Sieberling,
• Abstract要約: モノトーン擬ブール関数を最適化する$(1+1)$ Evolutionaryアルゴリズムでは、どの程度難しいのかという疑問を再考する。 提案手法は,ポエアモデルの悲観性を実現する最初の明示的な例であることを示す。
• 参考スコア（独自算出の注目度）: 0.0
• License: http://creativecommons.org/licenses/by-nc-nd/4.0/
• Abstract: In this paper we revisit the question how hard it can be for the $(1+1)$ Evolutionary Algorithm to optimize monotone pseudo-Boolean functions. By introducing a more pessimistic stochastic process, the partially-ordered evolutionary algorithm (PO-EA) model, Jansen first proved a runtime bound of $O(n^{3/2})$. More recently, Lengler, Martinsson and Steger improved this upper bound to $O(n \log^2 n)$ by an entropy compression argument. In this work, we analyze monotone functions that may adversarially vary at each step of the optimization, so-called dynamic monotone functions. We introduce the function Switching Dynamic BinVal (SDBV) and prove, using a combinatorial argument, that for the $(1+1)$-EA with any mutation rate $p \in [0,1]$, SDBV is drift minimizing within the class of dynamic monotone functions. We further show that the $(1+1)$-EA optimizes SDBV in $\Theta(n^{3/2})$ generations. Therefore, our construction provides the first explicit example which realizes the pessimism of the \poea model. Our simulations demonstrate matching runtimes for both the static and the self-adjusting $(1,\lambda)$-EA and $(1+\lambda)$-EA. Moreover, devising an example for fixed dimension, we illustrate that drift minimization does not equal maximal runtime beyond asymptotic analysis.
• Abstract（参考訳）: 本稿では,モノトーン擬ブール関数を最適化する$(1+1)$ Evolutionary Algorithmの難しさについて再検討する。 より悲観的な確率過程を導入することで、部分的に順序付けられた進化的アルゴリズム(PO-EA)モデルが最初に$O(n^{3/2})$のランタイム境界を証明した。 最近では、レングラー、マーティンソン、シュタイガーがこの上限をエントロピー圧縮引数により$O(n \log^2n)$に改善した。 本研究では,動的単調関数と呼ばれる最適化の各ステップで逆向きに変化する単調関数を解析する。 動的 BinVal (SDBV) を切り替える関数を導入し,1+1$-EAの突然変異率$p \in [0,1]$の場合,SDBV は動的単調関数のクラス内でのドリフト最小化を証明した。 さらに、$(1+1)$-EAは$\Theta(n^{3/2})$ジェネレーションでSDBVを最適化する。 したがって、我々の構成は、最初の明示的な例を提供し、それが \poea モデルの悲観性を実現する。 シミュレーションでは、静的と自己調整の両方のランタイムが、$(1,\lambda)$-EAと$(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)

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

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