論文の概要: Illustrating the Efficiency of Popular Evolutionary Multi-Objective Algorithms Using Runtime Analysis
- arxiv url: http://arxiv.org/abs/2405.13572v1
- Date: Wed, 22 May 2024 12:09:00 GMT
- ステータス: 処理完了
- システム内更新日: 2024-05-25 00:14:28.118734
- Title: Illustrating the Efficiency of Popular Evolutionary Multi-Objective Algorithms Using Runtime Analysis
- Title（参考訳）: 実行時解析を用いた一般的な進化的多目的アルゴリズムの効率性の図示
- Authors: Duc-Cuong Dang, Andre Opris, Dirk Sudholt,
- Abstract要約: 一般的な進化的多目的アルゴリズム(EMO)は、単純な(G)SEMOアルゴリズムと同じ性能を保証する。
我々は、GSEMOがOneTrapZeroTrapを最適化するために少なくとも$nn$のフィットネス評価を必要とするのに対し、一般的なEMOアルゴリズムNSGA-II、NSGA-III、SMS-EMOAは、ジェノタイプ重複を避けるための軽度な多様性メカニズムで拡張されているが、期待されるフィットネス評価は$O(n log n)$である。
- 参考スコア（独自算出の注目度）: 3.748255320979002
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Runtime analysis has recently been applied to popular evolutionary multi-objective (EMO) algorithms like NSGA-II in order to establish a rigorous theoretical foundation. However, most analyses showed that these algorithms have the same performance guarantee as the simple (G)SEMO algorithm. To our knowledge, there are no runtime analyses showing an advantage of a popular EMO algorithm over the simple algorithm for deterministic problems. We propose such a problem and use it to showcase the superiority of popular EMO algorithms over (G)SEMO: OneTrapZeroTrap is a straightforward generalization of the well-known Trap function to two objectives. We prove that, while GSEMO requires at least $n^n$ expected fitness evaluations to optimise OneTrapZeroTrap, popular EMO algorithms NSGA-II, NSGA-III and SMS-EMOA, all enhanced with a mild diversity mechanism of avoiding genotype duplication, only require $O(n \log n)$ expected fitness evaluations. Our analysis reveals the importance of the key components in each of these sophisticated algorithms and contributes to a better understanding of their capabilities.
- Abstract（参考訳）: 実行時解析は、厳密な理論基盤を確立するためにNSGA-IIのような一般的な進化的多目的アルゴリズム(EMO)に適用されている。
しかし、ほとんどの分析では、これらのアルゴリズムは単純な(G)SEMOアルゴリズムと同じ性能を保証する。
我々の知る限り、決定論的問題に対する単純なアルゴリズムよりも人気のあるEMOアルゴリズムの利点を示す実行時解析は存在しない。
そのような問題を提案し、(G)SEMOよりも人気のあるEMOアルゴリズムの優位性を示すために使用する: OneTrapZeroTrapは、よく知られたTrap関数を2つの目的に簡単に一般化したものである。
我々は、GSEMOがOneTrapZeroTrapを最適化するために少なくとも$n^n$のフィットネス評価を必要とするのに対し、一般的なEMOアルゴリズムNSGA-II、NSGA-III、SMS-EMOAは、ジェノタイプ重複を避けるための軽度な多様性メカニズムで拡張されているが、期待されるフィットネス評価は$O(n \log n)$である。
我々の分析は、これらの洗練されたアルゴリズムのそれぞれにおいて重要なコンポーネントの重要性を明らかにし、それらの能力のより深い理解に寄与する。
関連論文リスト
- 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) - Analysing the Robustness of NSGA-II under Noise [1.7205106391379026]
EMOアルゴリズムNSGA-IIの最初のランタイム解析が登場した。
NSGA-IIがGSEMOを上回った時期は明らかではない。
論文 参考訳（メタデータ） (2023-06-07T15:33:54Z) - Representation Learning with Multi-Step Inverse Kinematics: An Efficient
and Optimal Approach to Rich-Observation RL [106.82295532402335]
既存の強化学習アルゴリズムは、計算的難易度、強い統計的仮定、最適なサンプルの複雑さに悩まされている。
所望の精度レベルに対して、レート最適サンプル複雑性を実現するための、最初の計算効率の良いアルゴリズムを提供する。
我々のアルゴリズムMusIKは、多段階の逆運動学に基づく表現学習と体系的な探索を組み合わせる。
論文 参考訳（メタデータ） (2023-04-12T14:51:47Z) - A Mathematical Runtime Analysis of the Non-dominated Sorting Genetic
Algorithm III (NSGA-III) [9.853329403413701]
NSGA-II (Non-Maninated Sorting Genetic Algorithm II) は、実世界の応用において最も顕著な多目的進化アルゴリズムである。
NSGA-IIIは2つ以上の目的をうまく扱うことを目的としたNSGA-IIの改良である。
論文 参考訳（メタデータ） (2022-11-15T15:10:36Z) - Towards Better Out-of-Distribution Generalization of Neural Algorithmic
Reasoning Tasks [51.8723187709964]
ニューラルネットワーク推論タスクのOOD一般化について検討する。
目標は、ディープニューラルネットワークを使用して入出力ペアからアルゴリズムを学ぶことである。
論文 参考訳（メタデータ） (2022-11-01T18:33:20Z) - Regret Bounds for Expected Improvement Algorithms in Gaussian Process
Bandit Optimization [63.8557841188626]
期待されている改善(EI)アルゴリズムは、不確実性の下で最適化するための最も一般的な戦略の1つである。
本稿では,GP予測平均を通した標準既存値を持つEIの変種を提案する。
我々のアルゴリズムは収束し、$mathcal O(gamma_TsqrtT)$の累積後悔境界を達成することを示す。
論文 参考訳（メタデータ） (2022-03-15T13:17:53Z) - A Simple Evolutionary Algorithm for Multi-modal Multi-objective
Optimization [0.0]
マルチモーダル・多目的最適化問題(MMOP)を解くための定常進化アルゴリズムを提案する。
本報告では,1000関数評価の低計算予算を用いて,様々なテストスイートから得られた21個のMMOPの性能について報告する。
論文 参考訳（メタデータ） (2022-01-18T03:31:11Z) - Mathematical Runtime Analysis for the Non-Dominated Sorting Genetic
Algorithm II (NSGA-II) [16.904475483445452]
NSGA-IIにも実行時解析が可能であることを示す。
NSGA-IIは,パレートフロントの4倍の大きさの個体群を持つため,SEMOアルゴリズムやGSEMOアルゴリズムと同じランタイム保証を満たす。
論文 参考訳（メタデータ） (2021-12-16T03:00:20Z) - Result Diversification by Multi-objective Evolutionary Algorithms with
Theoretical Guarantees [94.72461292387146]
両目的探索問題として結果の多様化問題を再構成し,多目的進化アルゴリズム(EA)を用いて解くことを提案する。
GSEMOが最適時間近似比1/2$を達成できることを理論的に証明する。
目的関数が動的に変化すると、GSEMOはこの近似比をランニングタイムで維持することができ、Borodinらによって提案されたオープンな問題に対処する。
論文 参考訳（メタデータ） (2021-10-18T14:00:22Z) - ES-Based Jacobian Enables Faster Bilevel Optimization [53.675623215542515]
バイレベル最適化(BO)は多くの現代の機械学習問題を解決する強力なツールとして生まれてきた。
既存の勾配法では、ヤコビアンあるいはヘッセンベクトル計算による二階微分近似が必要となる。
本稿では,進化戦略(ES)に基づく新しいBOアルゴリズムを提案し,BOの過勾配における応答ヤコビ行列を近似する。
論文 参考訳（メタデータ） (2021-10-13T19:36:50Z) - GEO: Enhancing Combinatorial Optimization with Classical and Quantum
Generative Models [62.997667081978825]
我々は、生成モデルとして知られる機械学習モデルを活用する新しいフレームワークを導入し、最適化問題を解決する。
我々は、テンソルネットワークマシンに依存するGEOの量子インスパイアされたバージョンに注力する。
関数呼び出し数に対する固定予算が与えられた場合、その目標が最小限の最小値を求める場合、その優れた性能を示す。
論文 参考訳（メタデータ） (2021-01-15T18:18:38Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。