論文の概要: Theoretical Analyses of Multiobjective Evolutionary Algorithms on
Multimodal Objectives
- arxiv url: http://arxiv.org/abs/2012.07231v4
- Date: Mon, 27 Mar 2023 08:57:10 GMT
- ステータス: 処理完了
- システム内更新日: 2023-03-29 05:03:57.803094
- Title: Theoretical Analyses of Multiobjective Evolutionary Algorithms on
Multimodal Objectives
- Title（参考訳）: マルチモーダル目的に対する多目的進化アルゴリズムの理論解析
- Authors: Weijie Zheng, Benjamin Doerr
- Abstract要約: OJZJ問題(OJZJ problem)は、古典的なジャンプ関数のベンチマークに同型な2つの目的からなる双目的問題である。
確率1のSEMOは、実行時に関係なく、完全なParetoフロントを計算していないことを証明します。
また、より厳密な制限付き$frac 32 e nk+1 pm o(nk+1)$を示す。
- 参考スコア（独自算出の注目度）: 15.56430085052365
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: The theoretical understanding of MOEAs is lagging far behind their success in
practice. In particular, previous theory work considers mostly easy problems
that are composed of unimodal objectives.
As a first step towards a deeper understanding of how evolutionary algorithms
solve multimodal multiobjective problems, we propose the OJZJ problem, a
bi-objective problem composed of two objectives isomorphic to the classic jump
function benchmark. We prove that SEMO with probability one does not compute
the full Pareto front, regardless of the runtime. In contrast, for all problem
sizes $n$ and all jump sizes ${k \in [4..\frac n2 - 1]}$, the global SEMO
(GSEMO) covers the Pareto front in an expected number of $\Theta((n-2k)n^{k})$
iterations. For $k = o(n)$, we also show the tighter bound $\frac 32 e n^{k+1}
\pm o(n^{k+1})$, which might be the first runtime bound for an MOEA that is
tight apart from lower-order terms. We also combine the GSEMO with two
approaches that showed advantages in single-objective multimodal problems. When
using the GSEMO with a heavy-tailed mutation operator, the expected runtime
improves by a factor of at least $k^{\Omega(k)}$. When adapting the recent
stagnation-detection strategy of Rajabi and Witt (2022) to the GSEMO, the
expected runtime also improves by a factor of at least $k^{\Omega(k)}$ and
surpasses the heavy-tailed GSEMO by a small polynomial factor in $k$. Via an
experimental analysis, we show that these asymptotic differences are visible
already for small problem sizes: A factor-$5$ speed-up from heavy-tailed
mutation and a factor-$10$ speed-up from stagnation detection can be observed
already for jump size~$4$ and problem sizes between $10$ and $50$. Overall, our
results show that the ideas recently developed to aid single-objective
evolutionary algorithms to cope with local optima can be effectively employed
also in multiobjective optimization.
- Abstract（参考訳）: MOEAの理論的理解は、実際の成功よりもはるかに遅れている。
特に、以前の理論研究は、主に一助的目的からなる簡単な問題を考える。
マルチモーダル多目的問題に対する進化的アルゴリズムの解法を深く理解するための第一歩として,従来のジャンプ関数ベンチマークに同型な2つの目的からなる双目的問題であるojzj問題を提案する。
ランタイムに関係なく、semoは完全なparetoフロントを計算することができないことを証明します。
対照的に、すべての問題サイズは$n$、すべてのジャンプサイズは${k \in [4.]である。
\frac n2 - 1]}$, グローバルセモ (gsemo) はparetoの前面を想定される数である$\theta((n-2k)n^{k})$の反復でカバーする。
k = o(n)$ に対して、より厳密な境界を持つ $\frac 32 e n^{k+1} \pm o(n^{k+1})$ を示す。
また,gsemoを,単一目的のマルチモーダル問題の利点を示す2つのアプローチと組み合わせた。
重い尾の突然変異演算子でGSEMOを使用する場合、期待されるランタイムは少なくとも$k^{\Omega(k)}$で改善される。
Rajabi と Witt (2022) の最近の停滞検出戦略を GSEMO に適用すると、期待されるランタイムは少なくとも$k^{\Omega(k)}$ の係数で改善され、さらに$k$ の小さな多項式係数で重み付き GSEMO を超える。
実験結果から,これらの漸近的差異は,小さな問題に対してすでに確認されていることが明らかとなった。 重み付き突然変異による5$のスピードアップと,停滞検出による10$のスピードアップは,ジャンプサイズから4$のジャンプサイズですでに観測可能であり,問題サイズは10$から50$である。
以上の結果から,局所最適に対処する単一目的進化アルゴリズムを多目的最適化にも有効に活用できる可能性が示唆された。
関連論文リスト
- Theoretical Advantage of Multiobjective Evolutionary Algorithms for Problems with Different Degrees of Conflict [4.8951183832371]
OneMaxMin$_k$ベンチマーククラスは、COCZとOneMinMaxの一般化版である。
2つの典型的な非MOEAアプローチ、スカラー化(重み付きサム法)と$epsilon$-constraint法が検討されている。
我々は、(G)SEMO、MOEA/D、NSGA-II、SMS-EMOAがパレートフロント全体を$O(maxk,1nln n)$でカバーできることを証明する。
論文 参考訳（メタデータ） (2024-08-08T04:09:52Z) - A First Running Time Analysis of the Strength Pareto Evolutionary Algorithm 2 (SPEA2) [22.123838452178585]
本研究では, 強度進化アルゴリズム2 (SPEA2) の動作時間解析を行った。
具体的には、一般的に使用される3つの多目的問題、すなわち$m$OneMinMax、$m$LeadingOnesZeroes、$m$-OneZeroJumpを解決するためのSPEA2の実行時間が期待されていることを証明します。
論文 参考訳（メタデータ） (2024-06-23T14:12:22Z) - Matching the Statistical Query Lower Bound for k-sparse Parity Problems with Stochastic Gradient Descent [83.85536329832722]
勾配勾配降下(SGD)は,$d$次元ハイパーキューブ上の$k$パリティ問題を効率的に解くことができることを示す。
次に、SGDでトレーニングされたニューラルネットワークがどのようにして、小さな統計的エラーで$k$-parityの問題を解決するかを実証する。
論文 参考訳（メタデータ） (2024-04-18T17:57:53Z) - Runtime Analysis of Evolutionary Diversity Optimization on the Multi-objective (LeadingOnes, TrailingZeros) Problem [10.697103866816958]
進化的多様性最適化(EDO)を3つの対象関数 LOTZ$_k$ 上で証明する。
GSEMOが全てのパレート最適解の集合を$O(kn3)$期待反復で計算することを示す。
両多様性尺度に非常によく似た振る舞いを示す実証的な研究で、我々の理論分析を補完する。
論文 参考訳（メタデータ） (2024-04-17T15:51:15Z) - Adaptive, Doubly Optimal No-Regret Learning in Strongly Monotone and Exp-Concave Games with Gradient Feedback [75.29048190099523]
オンライン勾配降下(OGD)は、強い凸性や単調性仮定の下では二重最適であることが知られている。
本稿では,これらのパラメータの事前知識を必要としない完全適応型OGDアルゴリズム,textsfAdaOGDを設計する。
論文 参考訳（メタデータ） (2023-10-21T18:38:13Z) - Global Nash Equilibrium in Non-convex Multi-player Game: Theory and
Algorithms [66.8634598612777]
ナッシュ均衡(NE)はマルチプレイヤーゲームにおいて全てのプレイヤーに受け入れられることを示す。
また、一般理論から一歩ずつ一方的に利益を得ることはできないことも示している。
論文 参考訳（メタデータ） (2023-01-19T11:36:50Z) - The $(1+(\lambda,\lambda))$ Global SEMO Algorithm [8.34061303235504]
我々は、$(lambda,lambda)$の遺伝的計算を多目的進化計算に転送できることを示した。
我々は,従来のグローバルSEMOアルゴリズムの変種である$(lambda,lambda)$ global SEMOアルゴリズムを定義し,OneMinMaxアルゴリズムがグローバルSEMOよりもベンチマークで高速であることを証明した。
論文 参考訳（メタデータ） (2022-10-07T15:18:32Z) - A First Runtime Analysis of the NSGA-II on a Multimodal Problem [17.049516028133958]
この研究は、NSGA-IIが少なくともグローバルSEMOアルゴリズムと同様にOneJumpZeroJump問題の局所最適化に対処していることを示している。
この研究は、NSGA-IIが少なくともグローバルSEMOアルゴリズムと同様にOneJumpZeroJump問題の局所最適化に対処していることを示している。
論文 参考訳（メタデータ） (2022-04-28T19:44:47Z) - Result Diversification by Multi-objective Evolutionary Algorithms with
Theoretical Guarantees [94.72461292387146]
両目的探索問題として結果の多様化問題を再構成し,多目的進化アルゴリズム(EA)を用いて解くことを提案する。
GSEMOが最適時間近似比1/2$を達成できることを理論的に証明する。
目的関数が動的に変化すると、GSEMOはこの近似比をランニングタイムで維持することができ、Borodinらによって提案されたオープンな問題に対処する。
論文 参考訳（メタデータ） (2021-10-18T14:00:22Z) - Model-Based Multi-Agent RL in Zero-Sum Markov Games with Near-Optimal
Sample Complexity [67.02490430380415]
モデルに基づくMARLは、Nash平衡値(NE)を求めるために$tilde O(|S||B|(gamma)-3epsilon-2)$のサンプル複雑性を実現する。
また、アルゴリズムが報酬に依存しない場合、そのようなサンプル境界は最小値(対数因子まで)であり、アルゴリズムは報酬知識のない遷移サンプルを問合せする。
論文 参考訳（メタデータ） (2020-07-15T03:25:24Z) - FANOK: Knockoffs in Linear Time [73.5154025911318]
本稿では,ガウスモデル-Xノックオフを効率的に実装し,大規模特徴選択問題における誤発見率を制御するアルゴリズムについて述べる。
当社のメソッドは、最大50,000ドルという問題でテストしています。
論文 参考訳（メタデータ） (2020-06-15T21:55:34Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。