論文の概要: Hyper-Heuristics Can Profit From Global Variation Operators
- arxiv url: http://arxiv.org/abs/2407.14237v1
- Date: Fri, 19 Jul 2024 12:10:05 GMT
- ステータス: 処理完了
- システム内更新日: 2024-07-22 17:44:33.964677
- Title: Hyper-Heuristics Can Profit From Global Variation Operators
- Title（参考訳）: ハイパーヒューリスティックス、グローバルな変動オペレーターから利益を得る
- Authors: Benjamin Doerr, Johannes F. Lutzeyer,
- Abstract要約: モーブアクセプタンス・ハイパーヒューリスティック(MAHH)は,マルチモーダルCLIFFベンチマークの局所的最適化を極めて効率よく残していることを示す。
また、MAHHの局所的な1ビット突然変異演算子を、EAで一般的に使用されるグローバルビットワイズ演算子に置き換えると、JUMP関数上の$min1, O(fraceln(n)m)m, O(nm)$のランタイムが得られることを示す。
- 参考スコア（独自算出の注目度）: 12.774575491521926
- 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. The $O(n^3)$ runtime of the MAHH, for almost all cliff widths $d\ge 2,$ is significantly better than the $\Theta(n^d)$ runtime of simple elitist evolutionary algorithms (EAs) on CLIFF. In this work, we first show that this advantage is specific to the CLIFF problem and does not extend to the JUMP benchmark, the most prominent multi-modal benchmark in the theory of randomized search heuristics. 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 is significantly slower than the $O(n^m)$ runtime of simple elitist EAs. Encouragingly, we also show that replacing the local one-bit mutation operator in the MAHH with the global bit-wise mutation operator, commonly used in EAs, yields a runtime of $\min\{1, O(\frac{e\ln(n)}{m})^m\} \, O(n^m)$ on JUMP functions. This is at least as good as the runtime of simple elitist EAs. For larger values of $m$, this result proves an asymptotic performance gain over simple EAs. As our proofs reveal, the MAHH profits from its ability to walk through the valley of lower objective values in moderate-size steps, always accepting inferior solutions. This is the first time that such an optimization behavior is proven via mathematical means. Generally, our result shows that combining two ways of coping with local optima, global mutation and accepting inferior solutions, can lead to considerable performance gains.
- Abstract（参考訳）: 最近の研究で、Lissovoi, Oliveto, and Warwicker (Artificial Intelligence (2023)) は、Move Acceptance Hyper-Heuristic (MAHH) がマルチモーダルCLIFFベンチマークの局所的な最適化を著しく効率よく残していることを示した。
MAHHの$O(n^3)$ランタイムは、ほぼすべての崖幅に対して$d\ge 2,$は、CLIFF上の単純なエリート主義進化アルゴリズム(EA)の$\Theta(n^d)$ランタイムよりもはるかに優れている。
本稿では,この優位性はCLIFF問題に特有であり,ランダム化探索ヒューリスティックス理論において最も顕著なマルチモーダルベンチマークであるJUMPベンチマークに拡張されないことを示す。
我々は、MAHH選択パラメータ$p$の任意の選択に対して、ギャップサイズ$m = O(n^{1/2})$が少なくとも$\Omega(n^{2m-1} / (2m-1)!
)$。
これは単純なエリート主義EAの$O(n^m)$ランタイムよりもかなり遅い。
また、MAHHの局所的な1ビット突然変異演算子を、EAで一般的に使用されるグローバルビットワイズ演算子に置き換えると、JUMP関数上の$\min\{1, O(\frac{e\ln(n)}{m})^m\} \, O(n^m)$のランタイムが得られることを示す。
これは、少なくとも単純なエリート主義EAのランタイムと同じくらい良いです。
m$の大きい値の場合、この結果は単純なEAよりも漸近的なパフォーマンスの向上を示す。
我々の証明が示すように、MAHHは低目標値の谷を適度な規模で歩く能力から利益を得ており、常に劣る解を受け入れている。
このような最適化行動が数学的手法で証明されたのはこれが初めてである。
概して, 局所的最適性, グローバルな突然変異, 劣等な解を受け入れる2つの方法を組み合わせることで, 性能が著しく向上する可能性が示唆された。
関連論文リスト
- How the Move Acceptance Hyper-Heuristic Copes With Local Optima: Drastic
Differences Between Jumps and Cliffs [6.793248433673384]
我々は, マルチモーダル崖ベンチマークの局所的最適度を, 高い効率で保ち, モブアクセプタンスハイパーヒューリスティック (MAHH) が最適であることを示す。
また、局所的な1ビット演算子の代わりにグローバルビットワイズ演算子を持つMAHHがジャンプ関数を時間内に最適化することを示した。
これは、いくつかの方法で局所最適に対処する方法を組み合わせることは、実りあるアプローチであることを示している。
論文 参考訳（メタデータ） (2023-04-20T15:57:33Z) - TURF: A Two-factor, Universal, Robust, Fast Distribution Learning
Algorithm [64.13217062232874]
最も強力で成功したモダリティの1つは、全ての分布を$ell$距離に近似し、基本的に最も近い$t$-piece次数-$d_$の少なくとも1倍大きい。
本稿では,この数値をほぼ最適に推定する手法を提案する。
論文 参考訳（メタデータ） (2022-02-15T03:49:28Z) - 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) - 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) - Finding Global Minima via Kernel Approximations [90.42048080064849]
関数評価のみに基づく滑らかな関数のグローバル最小化を考える。
本稿では,近似関数を共同でモデル化し,大域的最小値を求める手法を検討する。
論文 参考訳（メタデータ） (2020-12-22T12:59:30Z) - Accelerated Zeroth-Order and First-Order Momentum Methods from Mini to
Minimax Optimization [133.53164856723782]
そこで我々は,関数値のみが得られるブラックボックス最小最適化のための新しいアクセラレーションゼロ階運動量 (AccZOM) 法を提案する。
一方,ブラックボックス最小値最適化のためのアクセラレーションゼロ階運動量降下法(Acc-MDA)を提案する。
特に、Acc-MDAは、$tildeO(kappa_y2.5epsilon-3)$の低い勾配の複雑さを、バッチサイズ$O(kappa_y4)$で得ることができる。
論文 参考訳（メタデータ） (2020-08-18T22:19:29Z) - 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) - Does Comma Selection Help To Cope With Local Optima [9.853329403413701]
我々は、$(mu,lambda)$EAが$(mu+lambda)$EAに対してランタイム上の優位性をもたらすことはないことを示した。
これは、低次項から遠ざかるマルチモーダル問題に対する非エリートアルゴリズムの最初の実行時結果である。
論文 参考訳（メタデータ） (2020-04-02T21:39:33Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。