Fugu-MT 論文翻訳(概要): Theoretical Analyses of Multi-Objective Evolutionary Algorithms on Multi-Modal Objectives

論文の概要: Theoretical Analyses of Multi-Objective Evolutionary Algorithms on Multi-Modal Objectives

arxiv url: http://arxiv.org/abs/2012.07231v3
Date: Mon, 19 Apr 2021 12:34:00 GMT
ステータス: 処理完了
システム内更新日: 2021-05-08 14:22:17.063811
Title: Theoretical Analyses of Multi-Objective Evolutionary Algorithms on Multi-Modal Objectives
Title（参考訳）: マルチモーダル目的に対する多目的進化アルゴリズムの理論的解析
Authors: Benjamin Doerr, Weijie Zheng
Abstract要約: 本稿では,進化的アルゴリズムがマルチモーダル多目的問題をどのように解決するかを理解するための第一歩を踏み出す。古典的なジャンプ関数ベンチマークに従属する単一目的を持つ2つの対象問題であるOneJumpJump問題を提案する。
参考スコア（独自算出の注目度）: 5.177947445379688
License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
Abstract: Previous theory work on multi-objective evolutionary algorithms considers mostly easy problems that are composed of unimodal objectives. This paper takes a first step towards a deeper understanding of how evolutionary algorithms solve multi-modal multi-objective problems. We propose the OneJumpZeroJump problem, a bi-objective problem whose single objectives are isomorphic to the classic jump functions benchmark. We prove that the simple evolutionary multi-objective optimizer (SEMO) cannot compute the full Pareto front. 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 $\Theta((n-2k)n^{k})$ iterations in expectation. To improve the performance, we combine the GSEMO with two approaches, a heavy-tailed mutation operator and a stagnation detection strategy, that showed advantages in single-objective multi-modal problems. Runtime improvements of asymptotic order at least $k^{\Omega(k)}$ are shown for both strategies. Our experiments verify the {substantial} runtime gains already for moderate problem sizes. Overall, these results show that the ideas recently developed for single-objective evolutionary algorithms can be effectively employed also in multi-objective optimization.
Abstract（参考訳）: 先述した多目的進化アルゴリズムに関する理論は、主に一助的目的からなる簡単な問題を考える。本稿では,進化的アルゴリズムがマルチモーダル多目的問題をどのように解決するかを理解するための第一歩を踏み出す。本論文では,古典ジャンプ関数のベンチマークに単一目的が同型である単目的問題であるOneJumpZeroJump問題を提案する。単純な進化的多目的最適化器 (SEMO) は完全なパレートフロントを計算できないことを示す。対照的に、すべての問題サイズ~$n$とすべてのジャンプサイズに対して$k \in [4..\frac n21]$は、大域SEMO (GSEMO) がパレートフロントを$\Theta((n-2k)n^{k})$イテレーションでカバーする。性能向上のため,gsemoと重畳型突然変異演算子とスタギネーション検出戦略の2つのアプローチを組み合わせることで,単一目的のマルチモーダル問題に有利性を示した。どちらの戦略にも、漸近的順序の少なくとも$k^{\Omega(k)}$のランタイム改善が示されている。我々の実験は、中程度の問題サイズで既に実行時のゲインを検証する。これらの結果から,最近開発された単目的進化アルゴリズムのアイデアは,多目的最適化においても有効に活用できることが示唆された。

関連論文リスト

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)

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

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