論文の概要: 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)}$のランタイム改善が示されている。
我々の実験は、中程度の問題サイズで既に実行時のゲインを検証する。
これらの結果から,最近開発された単目的進化アルゴリズムのアイデアは,多目的最適化においても有効に活用できることが示唆された。
関連論文リスト
- Runtime Analysis of the SMS-EMOA for Many-Objective Optimization [16.904475483445452]
本稿では,多目的最適化のためのSMS-EMOAの厳密な実行時解析を行う。
まず,二目的OJZJベンチマークの m-目的 mOJZJ 問題である多目的 mOJZJ 問題を提案する。
SMS-EMOAは、このベンチマークの全前面を、期待される数$O(M2 nk)$で計算する。
論文 参考訳(メタデータ) (2023-12-16T02:23:09Z) - Adaptive, Doubly Optimal No-Regret Learning in Strongly Monotone and
Exp-Concave Games with Gradient Feedback [84.61895643083226]
オンライン勾配降下(OGD)は、強い凸性や単調性仮定の下では二重最適であることが知られている。
本稿では,これらのパラメータの事前知識を必要としない完全適応型OGDアルゴリズム,textsfAdaOGDを設計する。
論文 参考訳(メタデータ) (2023-10-21T18:38:13Z) - An Oblivious Stochastic Composite Optimization Algorithm for Eigenvalue
Optimization Problems [76.2042837251496]
相補的な合成条件に基づく2つの難解なミラー降下アルゴリズムを導入する。
注目すべきは、どちらのアルゴリズムも、目的関数のリプシッツ定数や滑らかさに関する事前の知識なしで機能する。
本稿では,大規模半確定プログラム上での手法の効率性とロバスト性を示す。
論文 参考訳(メタデータ) (2023-06-30T08:34:29Z) - Runtime Analyses of Multi-Objective Evolutionary Algorithms in the
Presence of Noise [7.421135890148154]
対象関数にノイズが存在する場合の古典的ベンチマークの最初の解析を行う。
ビット単位の先行ノイズが$p le alpha/n$, $alpha$ a suitable constant であることを示す。
すべての解が各イテレーションで再評価されると、ノイズレート$p = omega(log(n)/n2)$がスーパーポリノミカルランタイムにつながることが証明される。
論文 参考訳(メタデータ) (2023-05-17T14:48:06Z) - 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) - Running Time Analysis of the Non-dominated Sorting Genetic Algorithm II
(NSGA-II) using Binary or Stochastic Tournament Selection [27.270523212333018]
本稿では,LOTZ,OneMinMax,COCZを解くための標準NSGA-IIのランニング時間解析について述べる。
具体的には、LOTZが$O(n3)$、OneMinMaxとCOCZが$O(n2log n)$であることを示す。
また, ランニングタイム上界はLOTZに強く, OneMinMax と COCZ にほぼ密であることを示す実験も行われた。
論文 参考訳(メタデータ) (2022-03-22T09:10:50Z) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。