Fugu-MT 論文翻訳(概要): A First Running Time Analysis of the Strength Pareto Evolutionary Algorithm 2 (SPEA2)

論文の概要: A First Running Time Analysis of the Strength Pareto Evolutionary Algorithm 2 (SPEA2)

arxiv url: http://arxiv.org/abs/2406.16116v2
Date: Sat, 14 Sep 2024 07:43:50 GMT
ステータス: 処理完了
システム内更新日: 2024-09-18 01:36:14.534939
Title: A First Running Time Analysis of the Strength Pareto Evolutionary Algorithm 2 (SPEA2)
Title（参考訳）: 強度パレート進化アルゴリズム(SPEA2)の初走行時間解析
Authors: Shengjie Ren, Chao Bian, Miqing Li, Chao Qian,
Abstract要約: 本研究では, 強度進化アルゴリズム2 (SPEA2) の動作時間解析を行った。具体的には、一般的に使用される3つの多目的問題、すなわち$m$OneMinMax、$m$LeadingOnesZeroes、$m$-OneZeroJumpを解決するためのSPEA2の実行時間が期待されていることを証明します。
参考スコア（独自算出の注目度）: 22.123838452178585
License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
Abstract: Evolutionary algorithms (EAs) have emerged as a predominant approach for addressing multi-objective optimization problems. However, the theoretical foundation of multi-objective EAs (MOEAs), particularly the fundamental aspects like running time analysis, remains largely underexplored. Existing theoretical studies mainly focus on basic MOEAs, with little attention given to practical MOEAs. In this paper, we present a running time analysis of strength Pareto evolutionary algorithm 2 (SPEA2) for the first time. Specifically, we prove that the expected running time of SPEA2 for solving three commonly used multi-objective problems, i.e., $m$OneMinMax, $m$LeadingOnesTrailingZeroes, and $m$-OneJumpZeroJump, is $O(\mu n\cdot \min\{m\log n, n\})$, $O(\mu n^2)$, and $O(\mu n^k \cdot \min\{mn, 3^{m/2}\})$, respectively. Here $m$ denotes the number of objectives, and the population size $\mu$ is required to be at least $(2n/m+1)^{m/2}$, $(2n/m+1)^{m-1}$ and $(2n/m-2k+3)^{m/2}$, respectively. The proofs are accomplished through general theorems which are also applicable for analyzing the expected running time of other MOEAs on these problems, and thus can be helpful for future theoretical analysis of MOEAs.
Abstract（参考訳）: 進化的アルゴリズム(EA)は、多目的最適化問題に対処する主要なアプローチとして登場した。しかし、多目的EA(MOEA)の理論的基盤、特に実行時間分析のような基本的な側面は、いまだほとんど探索されていない。既存の理論研究は主に基本的なMOEAに焦点を当てており、実際的なMOEAにはほとんど注目されていない。本稿では,Pareto進化アルゴリズム2(SPEA2)の動作時間解析を初めて行う。具体的には、一般的に使用される3つの多目的問題(例えば$m$OneMinMax, $m$LeadingOnesTrailingZeroes, $m$-OneJumpZeroJump)を解決するためのSPEA2の実行時間は、$O(\mu n\cdot \min\{m\log n, n\})$, $O(\mu n^2)$, $O(\mu n^k \cdot \min\{mn, 3^{m/2}\})$である。ここで$m$は目的数を表し、人口規模$\mu$は少なくとも$(2n/m+1)^{m/2}$、$(2n/m+1)^{m-1}$、$(2n/m-2k+3)^{m/2}$でなければならない。これらの証明は、これらの問題に関して他のMOEAの期待される実行時間を分析するのにも適用できる一般的な定理によって達成され、MOEAの将来の理論的解析に役立つ。

関連論文リスト

Agnostically Learning Multi-index Models with Queries [54.290489524576756]
本稿では,ガウス分布下での非依存学習の課題に対するクエリアクセスのパワーについて検討する。クエリアクセスは、MIMを不可知的に学習するためのランダムな例よりも大幅に改善されていることを示す。
論文参考訳（メタデータ） (2023-12-27T15:50:47Z)
Towards Running Time Analysis of Interactive Multi-objective Evolutionary Algorithms [23.815981112784552]
本稿では,実際のiMOEAに対して,最初の実行時間解析(EAの本質的理論的側面)を提供する。我々は、OneMinMaxとOneJumpZeroJumpの問題を解くために、よく開発された対話型NSGA-IIのランニングタイムが、それぞれ$O(n log n)$と$O(nk)$であることを示す。
論文参考訳（メタデータ） (2023-10-12T14:57:47Z)
On the Stability and Generalization of Triplet Learning [55.75784102837832]
トリプルトラーニング(トリプルトラーニング)、すなわちトリプルトデータから学ぶことは、コンピュータビジョンタスクに大きな注目を集めている。本稿では,安定解析を利用した三重項学習の一般化保証について検討する。
論文参考訳（メタデータ） (2023-02-20T07:32:50Z)
Reward-Mixing MDPs with a Few Latent Contexts are Learnable [75.17357040707347]
報酬混合マルコフ決定過程(RMMDP)におけるエピソード強化学習の検討我々のゴールは、そのようなモデルにおける時間段階の累積報酬をほぼ最大化する、ほぼ最適に近いポリシーを学ぶことである。
論文参考訳（メタデータ） (2022-10-05T22:52:00Z)
A Multivariate Complexity Analysis of Qualitative Reasoning Problems [9.594432031144716]
我々は、それぞれ$f(k) cdot 2O(n)$, $f(k)n$, timeで解ける問題のクラス FPE と XE を紹介する。有効幅$k$の部分順序時間問題は16kn$時間で解決可能であり,XEに含まれることを示す。また、アレンの区間代数のネットワーク整合性問題は、$k$以上と重複しないが、$(2nk)2k cdot 2n$ timeで解決可能であり、その中に含まれることを示す。
論文参考訳（メタデータ） (2022-09-30T07:29:53Z)
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)
When Non-Elitism Meets Time-Linkage Problems [19.798298260257432]
Elitist (1+$lambda$)EAと非elitist (1,$lambda$)EAのパフォーマンスを比較することにより、非elitismの影響を分析します。確率1$(1,$lambda$)EAがグローバルな最適値に到達でき、期待されるランタイムは$O(n3+clog n)$ with $lambda=c log_fracee-1 n$ for the constant $cge 1$であることを示す。
論文参考訳（メタデータ） (2021-04-14T13:03:42Z)
Theoretical Analyses of Multiobjective Evolutionary Algorithms on Multimodal Objectives [15.56430085052365]
OJZJ問題(OJZJ problem)は、古典的なジャンプ関数のベンチマークに同型な2つの目的からなる双目的問題である。確率1のSEMOは、実行時に関係なく、完全なParetoフロントを計算していないことを証明します。また、より厳密な制限付き$frac 32 e nk+1 pm o(nk+1)$を示す。
論文参考訳（メタデータ） (2020-12-14T03:07:39Z)
Streaming Complexity of SVMs [110.63976030971106]
本稿では,ストリーミングモデルにおけるバイアス正規化SVM問題を解く際の空間複雑性について検討する。両方の問題に対して、$frac1lambdaepsilon$の次元に対して、$frac1lambdaepsilon$よりも空間的に小さいストリーミングアルゴリズムを得ることができることを示す。
論文参考訳（メタデータ） (2020-07-07T17:10:00Z)
Kernel-Based Reinforcement Learning: A Finite-Time Analysis [53.47210316424326]
モデルに基づく楽観的アルゴリズムであるKernel-UCBVIを導入する。スパース報酬を伴う連続MDPにおける我々のアプローチを実証的に検証する。
論文参考訳（メタデータ） (2020-04-12T12:23:46Z)
A new regret analysis for Adam-type algorithms [78.825194932103]
理論的には、オンライン凸最適化に対する後悔の保証は、急速に崩壊する$beta_1to0$スケジュールを必要とする。最適なデータ依存リセット境界を一定の$beta_1$で導出できる新しいフレームワークを提案する。
論文参考訳（メタデータ） (2020-03-21T19:19:51Z)

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

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