論文の概要: Runtime Analysis for Multi-Objective Evolutionary Algorithms in Unbounded Integer Spaces

• arxiv url: http://arxiv.org/abs/2412.11684v1
• Date: Mon, 16 Dec 2024 11:53:54 GMT
• ステータス: 翻訳完了
• システム内更新日: 2024-12-17 14:00:36.726346
• Title: Runtime Analysis for Multi-Objective Evolutionary Algorithms in Unbounded Integer Spaces
• Title（参考訳）: 非有界整数空間における多目的進化アルゴリズムの実行時解析
• Authors: Benjamin Doerr, Martin S. Krejca, Günter Rudolph,
• Abstract要約: 整数探索空間に対する多目的進化アルゴリズムを解析する。 パワーロー変異は指数的な尾を持つ突然変異よりも優れていることが判明した。 整数空間における未知問題に対して、パワーロー突然変異を推奨する。
• 参考スコア（独自算出の注目度）: 9.591164070876687
• License:
• Abstract: Randomized search heuristics have been applied successfully to a plethora of problems. This success is complemented by a large body of theoretical results. Unfortunately, the vast majority of these results regard problems with binary or continuous decision variables -- the theoretical analysis of randomized search heuristics for unbounded integer domains is almost nonexistent. To resolve this shortcoming, we start the runtime analysis of multi-objective evolutionary algorithms, which are among the most successful randomized search heuristics, for unbounded integer search spaces. We analyze single- and full-dimensional mutation operators with three different mutation strengths, namely changes by plus/minus one (unit strength), random changes following a law with exponential tails, and random changes following a power-law. The performance guarantees we prove on a recently proposed natural benchmark problem suggest that unit mutation strengths can be slow when the initial solutions are far from the Pareto front. When setting the expected change right (depending on the benchmark parameter and the distance of the initial solutions), the mutation strength with exponential tails yields the best runtime guarantees in our results -- however, with a wrong choice of this expectation, the performance guarantees quickly become highly uninteresting. With power-law mutation, which is an essentially parameter-less mutation operator, we obtain good results uniformly over all problem parameters and starting points. We complement our mathematical findings with experimental results that suggest that our bounds are not always tight. Most prominently, our experiments indicate that power-law mutation outperforms the one with exponential tails even when the latter uses a near-optimal parametrization. Hence, we suggest to favor power-law mutation for unknown problems in integer spaces.
• Abstract（参考訳）: ランダムな探索ヒューリスティックスは、多くの問題にうまく適用されている。 この成功は、多くの理論的な結果によって補完される。 残念なことに、これらの結果の大部分はバイナリまたは連続的な決定変数の問題に関するものであり、非有界な整数領域に対するランダム化探索ヒューリスティックの理論的解析はほとんど存在しない。 この欠点を解決するために,非有界整数探索空間において,最も成功したランダム化探索ヒューリスティックの一つである多目的進化アルゴリズムのランタイム解析を開始する。 単次元および全次元の突然変異演算子を3つの異なる突然変異強度、すなわちプラス/マイナス1(単位強度)による変化、指数尾を持つ法則によるランダムな変化、そしてパワー・ローに続くランダムな変化で解析する。 私たちが最近提案した自然ベンチマーク問題で証明した性能保証は、初期解がパレート正面から遠く離れている場合、単位突然変異強度が遅くなる可能性があることを示唆している。 期待される変更を正しく設定する(ベンチマークパラメータと初期ソリューションの距離に依存する)と、指数的な尾を持つ突然変異強度は、結果に最高のランタイム保証をもたらす。 本質的にパラメータレスな突然変異演算子であるパワー・ロー突然変異では、全ての問題パラメータと開始点に対して一様に良い結果が得られる。 数学的な結果と実験結果とを補完し、境界が常にきついとは限らないことを示唆する。 最も顕著なことは、我々の実験は、パワーロー変異が、後者が準最適パラメトリゼーションを用いた場合であっても、指数的な尾を持つものよりも優れていることを示している。 したがって、整数空間における未知問題に対して、パワーロー突然変異を推奨する。

関連論文リスト

• Error Feedback under $(L_0,L_1)$-Smoothness: Normalization and Momentum [56.37522020675243]
  機械学習の幅広い問題にまたがる正規化誤差フィードバックアルゴリズムに対する収束の最初の証明を提供する。 提案手法では,許容可能なステップサイズが大きくなったため,新しい正規化エラーフィードバックアルゴリズムは,各種タスクにおける非正規化エラーよりも優れていた。
  論文  参考訳（メタデータ） (2024-10-22T10:19:27Z)
• A Flexible Evolutionary Algorithm With Dynamic Mutation Rate Archive [2.07180164747172]
  我々は、$k$-bitのフリップ突然変異を用いた進化的アルゴリズムの突然変異率を動的に維持する新しいフレキシブルなアプローチを提案する。 試行錯誤の回数がしきい値を超えた場合のレートは終了し、現在アーカイブに存在しないレートは2つの方法で入力できる。 最小選択確率について、重み付き分布を含む様々な選択肢を提案する。
  論文  参考訳（メタデータ） (2024-04-05T10:51:40Z)
• Already Moderate Population Sizes Provably Yield Strong Robustness to Noise [53.27802701790209]
  2つの進化的アルゴリズムは、OneMaxベンチマークのランタイムを増大させることなく、一定のノイズ確率を許容できることを示す。 この結果は、ノイズのない子孫は親と騒々しい子孫の間に偏りのある均一な交叉と見なすことができるという、新しい証明の議論に基づいている。
  論文  参考訳（メタデータ） (2024-04-02T16:35:52Z)
• Clipped Stochastic Methods for Variational Inequalities with Heavy-Tailed Noise [64.85879194013407]
  単調なVIPと非単調なVIPの解法における信頼度に対数的依存を持つ最初の高確率結果が証明された。 この結果は光尾の場合で最もよく知られたものと一致し,非単調な構造問題に新鮮である。 さらに,多くの実用的な定式化の勾配雑音が重く,クリッピングによりSEG/SGDAの性能が向上することを示す。
  論文  参考訳（メタデータ） (2022-06-02T15:21:55Z)
• Improved Convergence Rate of Stochastic Gradient Langevin Dynamics with Variance Reduction and its Application to Optimization [50.83356836818667]
  勾配ランゲヴィン・ダイナミクスは非エプス最適化問題を解くための最も基本的なアルゴリズムの1つである。 本稿では、このタイプの2つの変種、すなわち、分散還元ランジュバンダイナミクスと再帰勾配ランジュバンダイナミクスを示す。
  論文  参考訳（メタデータ） (2022-03-30T11:39:00Z)
• E-detectors: a nonparametric framework for sequential change detection [86.15115654324488]
  逐次的変化検出のための基本的かつ汎用的なフレームワークを開発する。 私たちの手順は、平均走行距離のクリーンで無症状な境界が伴います。 統計的および計算効率の両方を達成するために,これらの混合物を設計する方法を示す。
  論文  参考訳（メタデータ） (2022-03-07T17:25:02Z)
• Analysis of Evolutionary Diversity Optimisation for Permutation Problems [17.268191781480745]
  最もよく研究された置換問題の3つに対する進化的多様性最適化に関する研究 その結果、これらの問題に対する多くの突然変異演算子により、最大多様な個体群への収束が保証された。 QAPLIBおよび合成インスタンス上で、制約のない、制約のない環境で実験を行う。
  論文  参考訳（メタデータ） (2021-02-23T03:13:26Z)
• Optimal Static Mutation Strength Distributions for the $(1+\lambda)$ Evolutionary Algorithm on OneMax [1.0965065178451106]
  人口が十分に大きくなると、このような最適な分布は驚くほど複雑で直感に反する可能性がある。 人口が十分に大きくなると、このような最適な分布は驚くほど複雑で直感に反する可能性がある。
  論文  参考訳（メタデータ） (2021-02-09T16:56:25Z)
• Total Deep Variation: A Stable Regularizer for Inverse Problems [71.90933869570914]
  本稿では,データ駆動型汎用全深度変動正規化器について紹介する。 コアでは、畳み込みニューラルネットワークが複数のスケールや連続したブロックで局所的な特徴を抽出する。 我々は多数の画像処理タスクに対して最先端の結果を得る。
  論文  参考訳（メタデータ） (2020-06-15T21:54:15Z)
• Runtime Analysis of Evolutionary Algorithms with Biased Mutation for the Multi-Objective Minimum Spanning Tree Problem [12.098400820502635]
  我々は,Spanning Tree (MST) 問題を単目的および多目的バージョンで検討する。 我々は、低い支配数の観点から低いランクのエッジの選択に重点を置くバイアス付き突然変異を導入する。 我々は、非偏見または偏見のあるエッジ選択を決定する突然変異演算子の組み合わせが、最悪の場合、上界(unbiased mutation)を示すことを示した。
  論文  参考訳（メタデータ） (2020-04-22T07:47:00Z)
• Fast Mutation in Crossover-based Algorithms [8.34061303235504]
  Doerr、Le、Makhmara、Nguyen(GECCO)で提案された重尾突然変異演算子 Doerr、Le、Makhmara、Nguyen(GECCO)で提案された重尾突然変異演算子 実験的な研究は、ランダムに満足できるMax-3SATインスタンスにも高速突然変異の有効性を示す。
  論文  参考訳（メタデータ） (2020-04-14T14:16:42Z)

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

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