Fugu-MT 論文翻訳(概要): Proven Runtime Guarantees for How the MOEA/D Computes the Pareto Front From the Subproblem Solutions

論文の概要: Proven Runtime Guarantees for How the MOEA/D Computes the Pareto Front From the Subproblem Solutions

arxiv url: http://arxiv.org/abs/2405.01014v2
Date: Fri, 3 May 2024 05:55:45 GMT
ステータス: 処理完了
システム内更新日: 2024-05-06 11:57:06.840879
Title: Proven Runtime Guarantees for How the MOEA/D Computes the Pareto Front From the Subproblem Solutions
Title（参考訳）: MOEA/Dがサブプロブレム溶液からパレートフロントをどう計算するか
Authors: Benjamin Doerr, Martin S. Krejca, Noé Weeks,
Abstract要約: 分解に基づく多目的進化アルゴリズム(MOEA/D)は、与えられた多目的関数$f$を直接最適化するのではなく、共進化的に$f$の単目的サブプロブレム$N + 1$を最適化する。我々は、標準突然変異演算子のみを持つMOEA/Dが、OneMinMaxベンチマークのPareto全体を計算する方法について、初めて分析する。パワーローに対する我々の全体的な境界は、MOEA/D が$N = O(nbeta - 1)$ に対して最も良く、結果として$O(n) となることを示唆している。
参考スコア（独自算出の注目度）: 9.044970217182117
License: http://creativecommons.org/licenses/by/4.0/
Abstract: The decomposition-based multi-objective evolutionary algorithm (MOEA/D) does not directly optimize a given multi-objective function $f$, but instead optimizes $N + 1$ single-objective subproblems of $f$ in a co-evolutionary manner. It maintains an archive of all non-dominated solutions found and outputs it as approximation to the Pareto front. Once the MOEA/D found all optima of the subproblems (the $g$-optima), it may still miss Pareto optima of $f$. The algorithm is then tasked to find the remaining Pareto optima directly by mutating the $g$-optima. In this work, we analyze for the first time how the MOEA/D with only standard mutation operators computes the whole Pareto front of the OneMinMax benchmark when the $g$-optima are a strict subset of the Pareto front. For standard bit mutation, we prove an expected runtime of $O(n N \log n + n^{n/(2N)} N \log n)$ function evaluations. Especially for the second, more interesting phase when the algorithm start with all $g$-optima, we prove an $\Omega(n^{(1/2)(n/N + 1)} \sqrt{N} 2^{-n/N})$ expected runtime. This runtime is super-polynomial if $N = o(n)$, since this leaves large gaps between the $g$-optima, which require costly mutations to cover. For power-law mutation with exponent $\beta \in (1, 2)$, we prove an expected runtime of $O\left(n N \log n + n^{\beta} \log n\right)$ function evaluations. The $O\left(n^{\beta} \log n\right)$ term stems from the second phase of starting with all $g$-optima, and it is independent of the number of subproblems $N$. This leads to a huge speedup compared to the lower bound for standard bit mutation. In general, our overall bound for power-law suggests that the MOEA/D performs best for $N = O(n^{\beta - 1})$, resulting in an $O(n^\beta \log n)$ bound. In contrast to standard bit mutation, smaller values of $N$ are better for power-law mutation, as it is capable of easily creating missing solutions.
Abstract（参考訳）: 分解に基づく多目的進化アルゴリズム(MOEA/D)は、与えられた多目的関数$f$を直接最適化するのではなく、共進化的な方法で$N + 1$単目的サブプロブレム$f$を最適化する。支配的でないすべてのソリューションのアーカイブを保持し、パレートフロントへの近似として出力する。 MOEA/Dがサブプロブレムのすべてのオプティマ($g$-オプティマ)を見つければ、それでもパレートオプティマが$f$であるのを見逃すかもしれない。アルゴリズムは、$g$-optima を変更することによって、残りの Pareto optima を直接見つけるように命じられる。本研究では、標準的な突然変異演算子のみを持つMOEA/Dが、$g$-optimaがParetoフロントの厳密なサブセットである場合に、OneMinMaxベンチマークのParetoフロント全体をどのように計算するかを初めて分析する。標準的なビット突然変異に対しては、$O(n N \log n + n^{n/(2N)} N \log n)$関数評価の期待ランタイムを証明する。特に、アルゴリズムがすべての$g$-optimaから始まるとき、より興味深いフェーズでは、$\Omega(n^{(1/2)(n/N + 1)} \sqrt{N} 2^{-n/N})$期待ランタイムを証明する。このランタイムは、$N = o(n)$の場合、超ポリノミカルである。指数 $\beta \in (1, 2)$ の有理突然変異に対して、$O\left(n N \log n + n^{\beta} \log n\right)$関数評価の期待ランタイムを証明する。 O\left(n^{\beta} \log n\right)$ という項は、すべての$g$-optimaから始まる2番目のフェーズに由来する。これにより、標準ビット突然変異のバウンダリよりも大幅にスピードアップする。一般に、大まかに言えば、MOEA/D は$N = O(n^{\beta - 1})$ に対して最もよく作用し、結果として$O(n^\beta \log n)$bound となることを示唆している。標準的なビット突然変異とは対照的に、N$の小さな値は、欠落した解を容易に生成できるため、パワー・ローの突然変異に対してより優れている。

関連論文リスト

A Formal Perspective on Byte-Pair Encoding [100.75374173565548]
Byte-Pairimation (BPE) は、当初圧縮法として考案されたものの、NLPでデータをトークン化するために使われる一般的なアルゴリズムである。我々は、ランタイムの複雑さを$mathcalOleft(N log Mright)$から$mathcalOleft(N log Mright)$に改善するBPEのより高速な実装を提供しています。
論文参考訳（メタデータ） (2023-06-29T10:29:23Z)
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)
Near-Optimal Non-Convex Stochastic Optimization under Generalized Smoothness [21.865728815935665]
2つの最近の研究は、$O(epsilon-3)$サンプル複雑性を確立し、$O(epsilon)$-定常点を得る。しかし、どちらも$mathrmploy(epsilon-1)$という大きなバッチサイズを必要とする。本研究では,STORMアルゴリズムの単純な変種を再検討することにより,従来の2つの問題を同時に解決する。
論文参考訳（メタデータ） (2023-02-13T00:22:28Z)
Optimal Query Complexities for Dynamic Trace Estimation [59.032228008383484]
我々は,行列がゆっくりと変化している動的環境において,正確なトレース推定に必要な行列ベクトルクエリ数を最小化する問題を考える。我々は、$delta$失敗確率で$epsilon$エラーまで、すべての$m$トレースを同時に推定する新しいバイナリツリー要約手順を提供する。我々の下界(1)は、静的な設定においてもフロベニウスノルム誤差を持つ行列ベクトル積モデルにおけるハッチンソン推定子の第一の厳密な境界を与え、(2)動的トレース推定のための最初の無条件下界を与える。
論文参考訳（メタデータ） (2022-09-30T04:15:44Z)
Self-adjusting Population Sizes for the $(1, \lambda)$-EA on Monotone Functions [7.111443975103329]
突然変異率$c/n$ for $cle 1$で、1:s+1)$-successルールで集団サイズを適応的に制御する。この$c=1$のセットアップは1maxで$s1$で効率的であるが、$s ge 18$で非効率的であることを示す。
論文参考訳（メタデータ） (2022-04-01T15:46:12Z)
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)
Private Stochastic Convex Optimization: Optimal Rates in $\ell_1$ Geometry [69.24618367447101]
対数要因まで $(varepsilon,delta)$-differently private の最適過剰人口損失は $sqrtlog(d)/n + sqrtd/varepsilon n.$ です。損失関数がさらなる滑らかさの仮定を満たすとき、余剰損失は$sqrtlog(d)/n + (log(d)/varepsilon n)2/3で上界(対数因子まで)であることが示される。
論文参考訳（メタデータ） (2021-03-02T06:53:44Z)
An Optimal Separation of Randomized and Quantum Query Complexity [67.19751155411075]
すべての決定木に対して、与えられた順序 $ellsqrtbinomdell (1+log n)ell-1,$ sum to at least $cellsqrtbinomdell (1+log n)ell-1,$ where $n$ is the number of variables, $d$ is the tree depth, $c>0$ is a absolute constant。
論文参考訳（メタデータ） (2020-08-24T06:50:57Z)
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)

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

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