論文の概要: How the Move Acceptance Hyper-Heuristic Copes With Local Optima: Drastic
Differences Between Jumps and Cliffs
- arxiv url: http://arxiv.org/abs/2304.10414v1
- Date: Thu, 20 Apr 2023 15:57:33 GMT
- ステータス: 処理完了
- システム内更新日: 2023-04-21 12:36:32.574006
- Title: How the Move Acceptance Hyper-Heuristic Copes With Local Optima: Drastic
Differences Between Jumps and Cliffs
- Title（参考訳）: 局所オプティマスを用いた移動受容型ハイパーヒューリスティック・コーパス:ジャンプとクリフの劇的差異
- Authors: Benjamin Doerr, Arthur Dremaux, Johannes Lutzeyer, and Aur\'elien
Stumpf
- Abstract要約: 我々は, マルチモーダル崖ベンチマークの局所的最適度を, 高い効率で保ち, モブアクセプタンスハイパーヒューリスティック (MAHH) が最適であることを示す。
また、局所的な1ビット演算子の代わりにグローバルビットワイズ演算子を持つMAHHがジャンプ関数を時間内に最適化することを示した。
これは、いくつかの方法で局所最適に対処する方法を組み合わせることは、実りあるアプローチであることを示している。
- 参考スコア（独自算出の注目度）: 6.793248433673384
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: In recent work, Lissovoi, Oliveto, and Warwicker (Artificial Intelligence
(2023)) proved that the Move Acceptance Hyper-Heuristic (MAHH) leaves the local
optimum of the multimodal cliff benchmark with remarkable efficiency. With its
$O(n^3)$ runtime, for almost all cliff widths $d,$ the MAHH massively
outperforms the $\Theta(n^d)$ runtime of simple elitist evolutionary algorithms
(EAs). For the most prominent multimodal benchmark, the jump functions, the
given runtime estimates of $O(n^{2m} m^{-\Theta(m)})$ and
$\Omega(2^{\Omega(m)})$, for gap size $m \ge 2$, are far apart and the real
performance of MAHH is still an open question.
In this work, we resolve this question. We prove that for any choice of the
MAHH selection parameter~$p$, the expected runtime of the MAHH on a jump
function with gap size $m = o(n^{1/2})$ is at least $\Omega(n^{2m-1} /
(2m-1)!)$. This renders the MAHH much slower than simple elitist evolutionary
algorithms with their typical $O(n^m)$ runtime.
We also show that the MAHH with the global bit-wise mutation operator instead
of the local one-bit operator optimizes jump functions in time $O(\min\{m
n^m,\frac{n^{2m-1}}{m!\Omega(m)^{m-2}}\})$, essentially the minimum of the
optimization times of the $(1+1)$ EA and the MAHH. This suggests that combining
several ways to cope with local optima can be a fruitful approach.
- Abstract（参考訳）: 最近の研究で、Lissovoi, Oliveto, and Warwicker (Artificial Intelligence (2023)) は、Move Acceptance Hyper-Heuristic (MAHH) がマルチモーダル崖ベンチマークの局所的な最適化を著しく効率よく残していることを示した。
ほぼすべての崖幅に対して$O(n^3)$ランタイムを使用すると、MAHHは単純なエリート主義進化アルゴリズム(EA)の$\Theta(n^d)$ランタイムよりも大幅にパフォーマンスが向上する。
もっとも顕著なマルチモーダルベンチマークでは、ジャンプ関数は与えられたランタイム推定値である$O(n^{2m} m^{-\Theta(m)})$と$\Omega(2^{\Omega(m)})$、ギャップサイズが$m \ge 2$の場合にはかなり離れており、MAHHの実際の性能は依然としてオープンな問題である。
この作業では、この問題を解決します。
MAHH選択パラメータ~$p$の任意の選択に対して、ギャップサイズ$m = o(n^{1/2})$が少なくとも$\Omega(n^{2m-1} / (2m-1)!
)$.
これにより、典型的な$o(n^m)$ランタイムを持つ単純な楕円型進化アルゴリズムよりもはるかに遅いmahとなる。
また、局所的な1ビット演算子の代わりにグローバルビットワイズ演算子を持つMAHHは、時間$O(\min\{m n^m,\frac{n^{2m-1}}{m!
Omega(m)^{m-2}}\})$、基本的には$(1+1)$ EA と MAHH の最適化時間の最小値である。
これは、局所最適化にいくつかの方法を組み合わせることは実りあるアプローチであることを示している。
関連論文リスト
- Hyper-Heuristics Can Profit From Global Variation Operators [12.774575491521926]
モーブアクセプタンス・ハイパーヒューリスティック(MAHH)は,マルチモーダルCLIFFベンチマークの局所的最適化を極めて効率よく残していることを示す。
また、MAHHの局所的な1ビット突然変異演算子を、EAで一般的に使用されるグローバルビットワイズ演算子に置き換えると、JUMP関数上の$min1, O(fraceln(n)m)m, O(nm)$のランタイムが得られることを示す。
論文 参考訳（メタデータ） (2024-07-19T12:10:05Z) - 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) - An Oblivious Stochastic Composite Optimization Algorithm for Eigenvalue
Optimization Problems [76.2042837251496]
相補的な合成条件に基づく2つの難解なミラー降下アルゴリズムを導入する。
注目すべきは、どちらのアルゴリズムも、目的関数のリプシッツ定数や滑らかさに関する事前の知識なしで機能する。
本稿では,大規模半確定プログラム上での手法の効率性とロバスト性を示す。
論文 参考訳（メタデータ） (2023-06-30T08:34:29Z) - Reward-Mixing MDPs with a Few Latent Contexts are Learnable [75.17357040707347]
報酬混合マルコフ決定過程(RMMDP)におけるエピソード強化学習の検討
我々のゴールは、そのようなモデルにおける時間段階の累積報酬をほぼ最大化する、ほぼ最適に近いポリシーを学ぶことである。
論文 参考訳（メタデータ） (2022-10-05T22:52:00Z) - TURF: A Two-factor, Universal, Robust, Fast Distribution Learning
Algorithm [64.13217062232874]
最も強力で成功したモダリティの1つは、全ての分布を$ell$距離に近似し、基本的に最も近い$t$-piece次数-$d_$の少なくとも1倍大きい。
本稿では,この数値をほぼ最適に推定する手法を提案する。
論文 参考訳（メタデータ） (2022-02-15T03:49:28Z) - When Non-Elitism Meets Time-Linkage Problems [19.798298260257432]
Elitist (1+$lambda$)EAと非elitist (1,$lambda$)EAのパフォーマンスを比較することにより、非elitismの影響を分析します。
確率1$(1,$lambda$)EAがグローバルな最適値に到達でき、期待されるランタイムは$O(n3+clog n)$ with $lambda=c log_fracee-1 n$ for the constant $cge 1$であることを示す。
論文 参考訳（メタデータ） (2021-04-14T13:03:42Z) - Provably Breaking the Quadratic Error Compounding Barrier in Imitation
Learning, Optimally [58.463668865380946]
状態空間 $mathcalS$ を用いたエピソードマルコフ決定過程 (MDPs) における模擬学習の統計的限界について検討する。
rajaraman et al (2020) におけるmdアルゴリズムを用いた準最適性に対する上限 $o(|mathcals|h3/2/n)$ を定式化する。
Omega(H3/2/N)$ $mathcalS|geq 3$ であるのに対して、未知の遷移条件はよりシャープレートに悩まされる。
論文 参考訳（メタデータ） (2021-02-25T15:50:19Z) - Nearly Minimax Optimal Reinforcement Learning for Linear Mixture Markov
Decision Processes [91.38793800392108]
本稿では,マルコフ決定過程(MDP)の遷移確率核が線形混合モデルである線形関数近似による強化学習について検討する。
上記の線形混合 MDP に対して$textUCRL-VTR+$ という線形関数近似を用いた計算効率の良い新しいアルゴリズムを提案する。
我々の知る限り、これらは線形関数近似を持つRLのための計算効率が良く、ほぼ最小のアルゴリズムである。
論文 参考訳（メタデータ） (2020-12-15T18:56:46Z) - Streaming Complexity of SVMs [110.63976030971106]
本稿では,ストリーミングモデルにおけるバイアス正規化SVM問題を解く際の空間複雑性について検討する。
両方の問題に対して、$frac1lambdaepsilon$の次元に対して、$frac1lambdaepsilon$よりも空間的に小さいストリーミングアルゴリズムを得ることができることを示す。
論文 参考訳（メタデータ） (2020-07-07T17:10:00Z) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。