論文の概要: Running Time Analysis of the Non-dominated Sorting Genetic Algorithm II
(NSGA-II) using Binary or Stochastic Tournament Selection
- arxiv url: http://arxiv.org/abs/2203.11550v1
- Date: Tue, 22 Mar 2022 09:10:50 GMT
- ステータス: 処理完了
- システム内更新日: 2023-02-21 02:58:23.147782
- Title: Running Time Analysis of the Non-dominated Sorting Genetic Algorithm II
(NSGA-II) using Binary or Stochastic Tournament Selection
- Title（参考訳）: 非支配的ソーティング遺伝的アルゴリズム(NSGA-II)の2次・確率的経路選択による実行時間解析
- Authors: Chao Bian and Chao Qian
- Abstract要約: 本稿では,LOTZ,OneMinMax,COCZを解くための標準NSGA-IIのランニング時間解析について述べる。
具体的には、LOTZが$O(n3)$、OneMinMaxとCOCZが$O(n2log n)$であることを示す。
また, ランニングタイム上界はLOTZに強く, OneMinMax と COCZ にほぼ密であることを示す実験も行われた。
- 参考スコア（独自算出の注目度）: 27.270523212333018
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Evolutionary algorithms (EAs) have been widely used to solve multi-objective
optimization problems, and have become the most popular tool. However, the
theoretical foundation of multi-objective EAs (MOEAs), especially the essential
theoretical aspect, i.e., running time analysis, has been still largely
underdeveloped. The few existing theoretical works mainly considered simple
MOEAs, while the non-dominated sorting genetic algorithm II (NSGA-II), probably
the most influential MOEA, has not been analyzed except for a very recent work
considering a simplified variant without crossover. In this paper, we present a
running time analysis of the standard NSGA-II for solving LOTZ, OneMinMax and
COCZ, the three commonly used bi-objective optimization problems. Specifically,
we prove that the expected running time (i.e., number of fitness evaluations)
is $O(n^3)$ for LOTZ, and $O(n^2\log n)$ for OneMinMax and COCZ, which is
surprisingly as same as that of the previously analyzed simple MOEAs, GSEMO and
SEMO. Next, we introduce a new parent selection strategy, stochastic tournament
selection (i.e., $k$ tournament selection where $k$ is uniformly sampled at
random), to replace the binary tournament selection strategy of NSGA-II,
decreasing the required expected running time to $O(n^2)$ for all the three
problems. Experiments are also conducted, suggesting that the derived running
time upper bounds are tight for LOTZ, and almost tight for OneMinMax and COCZ.
- Abstract（参考訳）: 進化的アルゴリズム(EA)は多目的最適化の問題を解決するために広く使われており、最も人気のあるツールとなっている。
しかしながら、多目的eas(moeas)の理論的基礎、特に本質的な理論的側面、すなわち実行時間分析は、いまだにほとんど未開発である。
最も影響力のあるMOEAである非支配的ソート遺伝的アルゴリズムII(NSGA-II)は、クロスオーバーのない単純化された変種を考える非常に最近の研究を除いては分析されていない。
本稿では,一般的な2目的最適化問題であるlotz,oneminmax,coczを解くための標準nsga-iiの動作時間解析を行う。
具体的には、予想走行時間(つまり、フィットネス評価数)がLOTZに対して$O(n^3)$、OneMinMaxおよびCOCZに対して$O(n^2\log n)$であり、従来解析された単純なMOEA、GSEMO、SEMOと驚くほど同じであることを示す。
次に,nsga-iiの2次トーナメント選択戦略に代えて,3つの問題すべてに対して要求される実行時間をo(n^2)$に短縮する,新たな親選択戦略である確率的トーナメント選択(すなわち,k$がランダムにサンプリングされた1次トーナメント選択)を導入する。
また, ランニングタイム上界はLOTZに強く, OneMinMax と COCZ にほぼ密であることを示す実験も行われた。
関連論文リスト
- Sum-of-Squares inspired Quantum Metaheuristic for Polynomial Optimization with the Hadamard Test and Approximate Amplitude Constraints [76.53316706600717]
最近提案された量子アルゴリズムarXiv:2206.14999は半定値プログラミング(SDP)に基づいている
SDPにインスパイアされた量子アルゴリズムを2乗和に一般化する。
この結果から,本アルゴリズムは大きな問題に適応し,最もよく知られた古典学に近似することが示唆された。
論文 参考訳（メタデータ） (2024-08-14T19:04:13Z) - 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) - Illustrating the Efficiency of Popular Evolutionary Multi-Objective Algorithms Using Runtime Analysis [3.748255320979002]
一般的な進化的多目的アルゴリズム(EMO)は、単純な(G)SEMOアルゴリズムと同じ性能を保証する。
我々は、GSEMOがOneTrapZeroTrapを最適化するために少なくとも$nn$のフィットネス評価を必要とするのに対し、一般的なEMOアルゴリズムNSGA-II、NSGA-III、SMS-EMOAは、ジェノタイプ重複を避けるための軽度な多様性メカニズムで拡張されているが、期待されるフィットネス評価は$O(n log n)$である。
論文 参考訳（メタデータ） (2024-05-22T12:09:00Z) - Combinatorial Stochastic-Greedy Bandit [79.1700188160944]
我々は,選択した$n$のアームセットのジョイント報酬以外の余分な情報が観測されない場合に,マルチアームのバンディット問題に対する新規グリーディ・バンディット(SGB)アルゴリズムを提案する。
SGBは最適化された拡張型コミットアプローチを採用しており、ベースアームの大きなセットを持つシナリオ用に特別に設計されている。
論文 参考訳（メタデータ） (2023-12-13T11:08:25Z) - 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) - 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) - Correcting Momentum with Second-order Information [50.992629498861724]
最適積に$O(epsilon)$epsilon点を求める非臨界最適化のための新しいアルゴリズムを開発した。
我々は、さまざまな大規模ディープラーニングベンチマークとアーキテクチャで結果を検証する。
論文 参考訳（メタデータ） (2021-03-04T19:01:20Z) - GEO: Enhancing Combinatorial Optimization with Classical and Quantum
Generative Models [62.997667081978825]
我々は、生成モデルとして知られる機械学習モデルを活用する新しいフレームワークを導入し、最適化問題を解決する。
我々は、テンソルネットワークマシンに依存するGEOの量子インスパイアされたバージョンに注力する。
関数呼び出し数に対する固定予算が与えられた場合、その目標が最小限の最小値を求める場合、その優れた性能を示す。
論文 参考訳（メタデータ） (2021-01-15T18:18:38Z) - 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) - 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) - A new regret analysis for Adam-type algorithms [78.825194932103]
理論的には、オンライン凸最適化に対する後悔の保証は、急速に崩壊する$beta_1to0$スケジュールを必要とする。
最適なデータ依存リセット境界を一定の$beta_1$で導出できる新しいフレームワークを提案する。
論文 参考訳（メタデータ） (2020-03-21T19:19:51Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。