論文の概要: Runtime Analysis of a Heavy-Tailed $(1+(\lambda,\lambda))$ Genetic
Algorithm on Jump Functions
- arxiv url: http://arxiv.org/abs/2006.03523v1
- Date: Fri, 5 Jun 2020 15:57:55 GMT
- ステータス: 処理完了
- システム内更新日: 2022-11-25 03:16:14.456293
- Title: Runtime Analysis of a Heavy-Tailed $(1+(\lambda,\lambda))$ Genetic
Algorithm on Jump Functions
- Title（参考訳）: ジャンプ関数を用いたヘビーテール$(1+(\lambda,\lambda))$遺伝的アルゴリズムのランタイム解析
- Authors: Denis Antipov, Benjamin Doerr
- Abstract要約: ジャンプ関数は、n(k + 1)/2k-k/2eO(k)$フィットネス評価のみの期待実行時に、ジャンプサイズ$k$で最適化できる。
ジャンプサイズが最大$n/4$のすべてのジャンプ関数上の分布パラメータを自然に選択したこのアルゴリズムは、前回の作業で得られる最良のインスタンス固有パラメータに近い性能を持つことを示す。
- 参考スコア（独自算出の注目度）: 9.853329403413701
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: It was recently observed that the $(1+(\lambda,\lambda))$ genetic algorithm
can comparably easily escape the local optimum of the jump functions benchmark.
Consequently, this algorithm can optimize the jump function with jump size $k$
in an expected runtime of only $n^{(k + 1)/2}k^{-k/2}e^{O(k)}$ fitness
evaluations (Antipov, Doerr, Karavaev (GECCO 2020)). To obtain this
performance, however, a non-standard parameter setting depending on the jump
size $k$ was used.
To overcome this difficulty, we propose to choose two parameters of the
$(1+(\lambda,\lambda))$ genetic algorithm randomly from a power-law
distribution. Via a mathematical runtime analysis, we show that this algorithm
with natural instance-independent choices of the distribution parameters on all
jump functions with jump size at most $n/4$ has a performance close to what the
best instance-specific parameters in the previous work obtained. This price for
instance-independence can be made as small as an $O(n\log(n))$ factor. Given
the difficulty of the jump problem and the runtime losses from using mildly
suboptimal fixed parameters (also discussed in this work), this appears to be a
fair price.
- Abstract（参考訳）: 最近、$(1+(\lambda,\lambda))$の遺伝的アルゴリズムはjump関数ベンチマークの局所最適値から容易に逃れることができることが観測された。
したがって、このアルゴリズムはジャンプサイズ$k$のジャンプ関数を、たった$n^{(k + 1)/2}k^{-k/2}e^{o(k)}$フィットネス評価(antipov, doerr, karavaev (gecco 2020))のランタイムで最適化することができる。
しかし、この性能を得るためには、ジャンプサイズ$k$に依存する非標準パラメータ設定が用いられた。
この課題を克服するために, 1+(\lambda,\lambda))$ 遺伝的アルゴリズムの2つのパラメータをパワーロー分布からランダムに選ぶことを提案する。
数学的な実行時解析により、ジャンプサイズが最大$n/4$のすべてのジャンプ関数上の分布パラメータの自然なインスタンス非依存の選択を持つこのアルゴリズムは、前回の作業で得られる最良のインスタンス固有パラメータに近い性能を持つことを示す。
このインスタンス独立性の価格は、$O(n\log(n))$ factor のように小さくすることができる。
ジャンプ問題の難しさと、軽度に最適でない固定パラメータの使用によるランタイム損失(この作業でも議論されている)を考えると、これは妥当な価格である。
関連論文リスト
- Kernelized Normalizing Constant Estimation: Bridging Bayesian Quadrature
and Bayesian Optimization [51.533164528799084]
小さい相対誤差内で正規化定数を推定するために、難易度は$lambda$の値に依存する。
関数評価がノイズである場合でも,このパターンは真であることがわかった。
論文 参考訳（メタデータ） (2024-01-11T07:45:09Z) - An Oblivious Stochastic Composite Optimization Algorithm for Eigenvalue
Optimization Problems [76.2042837251496]
相補的な合成条件に基づく2つの難解なミラー降下アルゴリズムを導入する。
注目すべきは、どちらのアルゴリズムも、目的関数のリプシッツ定数や滑らかさに関する事前の知識なしで機能する。
本稿では,大規模半確定プログラム上での手法の効率性とロバスト性を示す。
論文 参考訳（メタデータ） (2023-06-30T08:34:29Z) - Mind the gap: Achieving a super-Grover quantum speedup by jumping to the
end [114.3957763744719]
本稿では,数種類のバイナリ最適化問題に対して,厳密な実行保証を有する量子アルゴリズムを提案する。
このアルゴリズムは、$n$非依存定数$c$に対して、時間で$O*(2(0.5-c)n)$の最適解を求める。
また、$k$-spinモデルからのランダムなインスタンスの多数と、完全に満足あるいはわずかにフラストレーションされた$k$-CSP式に対して、文 (a) がそうであることを示す。
論文 参考訳（メタデータ） (2022-12-03T02:45:23Z) - Extra-Newton: A First Approach to Noise-Adaptive Accelerated
Second-Order Methods [57.050204432302195]
本研究では,2次スムーズな凸関数を最小化するための普遍的かつ適応的な2次法を提案する。
我々のアルゴリズムは、オラクルフィードバックが分散$sigma2$であるときに$O(sigma / sqrtT)$収束を達成し、決定論的オラクルで$O(1 / T3)$に収束を改善する。
論文 参考訳（メタデータ） (2022-11-03T14:12:51Z) - Near-Optimal Lower Bounds For Convex Optimization For All Orders of
Smoothness [26.71898403195793]
非常に滑らかな凸関数を最適化する複雑性について検討する。
正の整数 $p$ に対して、凸関数 $f$ の最小値 $epsilon$-approximate を求める。
我々は、この境界(ログファクタまで)にマッチする新しい下界を証明し、ランダム化アルゴリズムだけでなく、量子アルゴリズムにも適用する。
論文 参考訳（メタデータ） (2021-12-02T10:51:43Z) - Bayesian Optimistic Optimisation with Exponentially Decaying Regret [58.02542541410322]
現在の実用的なBOアルゴリズムは、$mathcalO(fraclogNsqrtN)$から$mathcalO(e-sqrtN)$まで、$N$は評価の数である。
本稿では,boと木に基づく楽観的楽観化の概念を絡み合うことにより,無音環境における後悔を改善できる可能性について検討する。
次数$mathcal O(N-sqrt)で指数的再帰を達成できる最初の実践的手法であるBOOアルゴリズムを提案する。
論文 参考訳（メタデータ） (2021-05-10T13:07:44Z) - An Extended Jump Function Benchmark for the Analysis of Randomized
Search Heuristics [4.38301148531795]
幅のフィットネスが低い谷を含むジャンプ関数の拡張クラス $textscJump_k,delta$ を提案します。
この新しいクラスは、特にグローバルな最適点から遠く離れている場合に、より広いフィットネスバレーでの実験を可能にすることを示す。
論文 参考訳（メタデータ） (2021-05-07T07:21:10Z) - Parameter-free Stochastic Optimization of Variationally Coherent
Functions [19.468067110814808]
我々は$mathbbRdilon上で関数のクラスを1次最適化するためのアルゴリズムを設計・解析する。
この2つを同時に実現したのは初めてである。
論文 参考訳（メタデータ） (2021-01-30T15:05:34Z) - 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 Rigorous Runtime Analysis of the $(1 + (\lambda, \lambda))$ GA on Jump
Functions [8.34061303235504]
我々は,このアルゴリズムの最初の実行時解析を,ジャンプ関数ベンチマークであるマルチモーダル問題クラス上で実施する。
ジャンプ関数の局所最適性を残すという孤立した問題に対して、$(n/k)k/2 eTheta(k)$のランタイムにつながる証明可能な最適パラメータを決定する。
論文 参考訳（メタデータ） (2020-04-14T17:54:12Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。