論文の概要: Runtime Analyses of Multi-Objective Evolutionary Algorithms in the Presence of Noise

• arxiv url: http://arxiv.org/abs/2305.10259v1
• Date: Wed, 17 May 2023 14:48:06 GMT
• ステータス: 処理完了
• システム内更新日: 2023-05-18 15:20:20.680099
• Title: Runtime Analyses of Multi-Objective Evolutionary Algorithms in the Presence of Noise
• Title（参考訳）: 雑音下における多目的進化アルゴリズムの実行時解析
• Authors: Matthieu Dinot, Benjamin Doerr, Ulysse Hennebelle, Sebastian Will
• Abstract要約: 対象関数にノイズが存在する場合の古典的ベンチマークの最初の解析を行う。 ビット単位の先行ノイズが$p le alpha/n$, $alpha$ a suitable constant であることを示す。 すべての解が各イテレーションで再評価されると、ノイズレート$p = omega(log(n)/n2)$がスーパーポリノミカルランタイムにつながることが証明される。
• 参考スコア（独自算出の注目度）: 7.421135890148154
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: In single-objective optimization, it is well known that evolutionary algorithms also without further adjustments can tolerate a certain amount of noise in the evaluation of the objective function. In contrast, this question is not at all understood for multi-objective optimization. In this work, we conduct the first mathematical runtime analysis of a simple multi-objective evolutionary algorithm (MOEA) on a classic benchmark in the presence of noise in the objective functions. We prove that when bit-wise prior noise with rate $p \le \alpha/n$, $\alpha$ a suitable constant, is present, the \emph{simple evolutionary multi-objective optimizer} (SEMO) without any adjustments to cope with noise finds the Pareto front of the OneMinMax benchmark in time $O(n^2\log n)$, just as in the case without noise. Given that the problem here is to arrive at a population consisting of $n+1$ individuals witnessing the Pareto front, this is a surprisingly strong robustness to noise (comparably simple evolutionary algorithms cannot optimize the single-objective OneMax problem in polynomial time when $p = \omega(\log(n)/n)$). Our proofs suggest that the strong robustness of the MOEA stems from its implicit diversity mechanism designed to enable it to compute a population covering the whole Pareto front. Interestingly this result only holds when the objective value of a solution is determined only once and the algorithm from that point on works with this, possibly noisy, objective value. We prove that when all solutions are reevaluated in each iteration, then any noise rate $p = \omega(\log(n)/n^2)$ leads to a super-polynomial runtime. This is very different from single-objective optimization, where it is generally preferred to reevaluate solutions whenever their fitness is important and where examples are known such that not reevaluating solutions can lead to catastrophic performance losses.
• Abstract（参考訳）: 単一目的最適化では、さらなる調整を伴わない進化的アルゴリズムが、目的関数の評価において一定のノイズを許容できることがよく知られている。 対照的に、この問題は多目的最適化では理解されていない。 本研究では,目的関数に雑音が存在する場合の古典的ベンチマークにおいて,単純な多目的進化アルゴリズム(MOEA)の数学的実行時解析を行う。 適切な定数として$p \le \alpha/n$, $\alpha$ がある場合、ノイズに対処するための調整を伴わない \emph{simple Evolution Multi-objective Optimizationr} (SEMO) は、ノイズのない場合と同様に、時間で$O(n^2\log n)$ の OneMinMax ベンチマークの Pareto フロントを見つける。 ここでの問題は、パレートフロントを目撃する$n+1$の個人からなる集団に到達することであり、これは驚くほど強いノイズに対する強靭性である(例えば、単純な進化アルゴリズムは、$p = \omega(\log(n)/n)$の多項式時間で単目的のOneMax問題を最適化することはできない)。 我々の証明は、MOEAの強い堅牢性は、パレートフロント全体をカバーする人口を計算するために設計された暗黙の多様性メカニズムに由来することを示唆している。 興味深いことに、この結果は、解の客観的値が1回だけ決定される場合にのみ成立し、その時点からのアルゴリズムは、おそらくは騒がしい客観的値を扱う。 すべての解が各反復で再評価されると、任意のノイズレート$p = \omega(\log(n)/n^2)$が超多項式ランタイムにつながることが証明される。 これは、1つの目的の最適化とは大きく異なり、一般的に、適合性が重要であれば解を再評価することが望ましい。

関連論文リスト

• Evolutionary Algorithms Are Significantly More Robust to Noise When They Ignore It [10.165640083594573]
  再評価の必要性は過大評価される可能性があり、実際は有害である。 この進化的アルゴリズムの最初の分析は、再評価なしに単一目的雑音の問題を解くことで、そのようなアルゴリズムが以前考えられていたよりもずっと良いノイズに対処できることを示している。
  論文  参考訳（メタデータ） (2024-08-31T00:10:10Z)
• Already Moderate Population Sizes Provably Yield Strong Robustness to Noise [53.27802701790209]
  2つの進化的アルゴリズムは、OneMaxベンチマークのランタイムを増大させることなく、一定のノイズ確率を許容できることを示す。 この結果は、ノイズのない子孫は親と騒々しい子孫の間に偏りのある均一な交叉と見なすことができるという、新しい証明の議論に基づいている。
  論文  参考訳（メタデータ） (2024-04-02T16:35:52Z)
• Some Constructions of Private, Efficient, and Optimal $K$-Norm and Elliptic Gaussian Noise [54.34628844260993]
  微分プライベートな計算は、しばしば$d$次元統計学の感度に束縛されて始まる。 純粋な微分プライバシーのために、$K$-normメカニズムは統計学の感度空間に合わせた規範を用いてこのアプローチを改善することができる。 本稿では,総和,数,投票の単純な統計量について両問題を解く。
  論文  参考訳（メタデータ） (2023-09-27T17:09:36Z)
• The First Proven Performance Guarantees for the Non-Dominated Sorting Genetic Algorithm II (NSGA-II) on a Combinatorial Optimization Problem [6.793248433673384]
  NSGA-II(Non-Maninated Sorting Genetic Algorithm-II)は、多目的最適化問題を解くアルゴリズムの1つである。 従来の最適化問題であるNP完全二目的最小スパンニングツリー問題に対して、初めて証明された性能保証を与える。
  論文  参考訳（メタデータ） (2023-05-22T19:59:19Z)
• Larger Offspring Populations Help the $(1 + (\lambda, \lambda))$ Genetic Algorithm to Overcome the Noise [76.24156145566425]
  進化的アルゴリズムは、適合性の評価においてノイズに対して堅牢であることが知られている。 我々は$(lambda,lambda)$の遺伝的アルゴリズムがどんなにノイズに強いかを解析する。
  論文  参考訳（メタデータ） (2023-05-08T08:49:01Z)
• Stochastic Nonsmooth Convex Optimization with Heavy-Tailed Noises: High-Probability Bound, In-Expectation Rate and Initial Distance Adaptation [22.758674468435302]
  重尾雑音系では、勾配と真の速度の差は有限の$p-thモーメントを持つと仮定される。 本稿では,重み付き雑音を用いた非平滑凸最適化の包括的解析を行う。
  論文  参考訳（メタデータ） (2023-03-22T03:05:28Z)
• The $(1+(\lambda,\lambda))$ Global SEMO Algorithm [8.34061303235504]
  我々は、$(lambda,lambda)$の遺伝的計算を多目的進化計算に転送できることを示した。 我々は,従来のグローバルSEMOアルゴリズムの変種である$(lambda,lambda)$ global SEMOアルゴリズムを定義し,OneMinMaxアルゴリズムがグローバルSEMOよりもベンチマークで高速であることを証明した。
  論文  参考訳（メタデータ） (2022-10-07T15:18:32Z)
• Multi-block-Single-probe Variance Reduced Estimator for Coupled Compositional Optimization [49.58290066287418]
  構成問題の複雑さを軽減するために,MSVR (Multi-block-probe Variance Reduced) という新しい手法を提案する。 本研究の結果は, 試料の複雑さの順序や強靭性への依存など, 様々な面で先行して改善された。
  論文  参考訳（メタデータ） (2022-07-18T12:03:26Z)
• Minimax Optimization with Smooth Algorithmic Adversaries [59.47122537182611]
  対戦相手が展開するスムーズなアルゴリズムに対して,Min-playerの新しいアルゴリズムを提案する。 本アルゴリズムは,制限周期のない単調進行を保証し,適切な勾配上昇数を求める。
  論文  参考訳（メタデータ） (2021-06-02T22:03:36Z)
• A Two-Timescale Framework for Bilevel Optimization: Complexity Analysis and Application to Actor-Critic [142.1492359556374]
  双レベル最適化は、2レベル構造を示す問題のクラスである。 このような二段階問題に対処するための2段階近似(TTSA)アルゴリズムを提案する。 本稿では,TTSAフレームワークの特殊な事例として,2段階の自然なアクター・クリティカルポリシー最適化アルゴリズムが有用であることを示す。
  論文  参考訳（メタデータ） (2020-07-10T05:20:02Z)

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

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