二値または確率的トーナメント選択を用いた非支配ソーティング遺伝的アルゴリズムII(NSGA-II)の走行時間解析【JST・京大機械翻訳】

Bian Chao; Qian Chao

プレプリント

J-GLOBAL ID：202202213446562825 整理番号：22P0308200

二値または確率的トーナメント選択を用いた非支配ソーティング遺伝的アルゴリズムII(NSGA-II)の走行時間解析【JST・京大機械翻訳】

Running Time Analysis of the Non-dominated Sorting Genetic Algorithm II (NSGA-II) using Binary or Stochastic Tournament Selection

出版者サイト {{ this.onShowPLink() }} 複写サービスで全文入手
高度な検索・分析はJDreamⅢで

この文献はプレプリントです。プレプリントについてはこちらをご確認ください。

著者 (2件)： ,
資料名：
発行年： 2022年03月22日プレプリントサーバーでの情報更新日： 2022年03月22日
JST資料番号： O7000B 資料種別：プレプリント
記事区分：プレプリント発行国：アメリカ合衆国 (USA) 言語：英語 (EN)

進化アルゴリズム(EA)は多目的最適化問題を解くために広く使われており,最も一般的なツールとなっている。しかし,多目的EA(MOEA)の理論的基礎,特に重要な理論的側面,すなわち,実行時間分析が,まだほとんど開発されていない。少数の既存の理論的研究は,主に単純なMOEAsを考慮し,一方,非支配ソーティング遺伝的アルゴリズムII(NSGA-II)は,おそらく最も影響力のあるMOEAは,交差のない単純化変異体を考慮した非常に最近の研究を除いて,分析されていない。本論文では,LOTZ,1MinMaxおよびCOCZを解くための標準NSGA-IIの実行時間解析を示し,3つの通常用いられる2目的最適化問題である。特に,期待した実行時間(すなわち,適応度評価の数)はLOTZに対してO(n ̄3)であり,1MinMaxおよびCOCZに対してはO(n ̄2logn)であり,これは以前に分析した単純なMOEA,GSEMOおよびSEMOのそれと同じである。次に,著者らは,新しい親選択戦略,確率的トーナメント選択(すなわち,kがランダムで一様にサンプリングされるkトーナメント選択)を導入し,NSGA-IIのバイナリトーナメント選択戦略に置換し,すべての3つの問題に対するO(n ̄2)に対する必要な期待実行時間を減少させた。また,実験も行い,得られた実行時間上限がLOTZに対して緊密であり,1MinMaxとCOCZに対してほとんどタイトであることを示唆した。【JST・京大機械翻訳】

, , , , , , ,
, , , , , , 【Automatic Indexing@JST】

人工知能

, , , , , , , ,

前のページに戻る