論文の概要: A Proof that Using Crossover Can Guarantee Exponential Speed-Ups in
Evolutionary Multi-Objective Optimisation
- arxiv url: http://arxiv.org/abs/2301.13687v1
- Date: Tue, 31 Jan 2023 15:03:34 GMT
- ステータス: 処理完了
- システム内更新日: 2023-02-01 16:10:45.437876
- Title: A Proof that Using Crossover Can Guarantee Exponential Speed-Ups in
Evolutionary Multi-Objective Optimisation
- Title（参考訳）: クロスオーバーを用いた進化的多目的最適化における指数速度向上の保証
- Authors: Duc-Cuong Dang and Andre Opris and Bahare Salehi and Dirk Sudholt
- Abstract要約: 多目的進化最適化(EMO)の理論は、まだ初期段階にある。
クロスオーバー演算子の利点のような基本的な質問は、まだ完全には理解されていない。
これは、広く使われているNSGA-IIアルゴリズムのクロスオーバーによる指数関数的な性能ギャップの最初の例である。
- 参考スコア（独自算出の注目度）: 1.7205106391379026
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Evolutionary algorithms are popular algorithms for multiobjective
optimisation (also called Pareto optimisation) as they use a population to
store trade-offs between different objectives. Despite their popularity, the
theoretical foundation of multiobjective evolutionary optimisation (EMO) is
still in its early development. Fundamental questions such as the benefits of
the crossover operator are still not fully understood. We provide a theoretical
analysis of well-known EMO algorithms GSEMO and NSGA-II to showcase the
possible advantages of crossover. We propose a class of problems on which these
EMO algorithms using crossover find the Pareto set in expected polynomial time.
In sharp contrast, they and many other EMO algorithms without crossover require
exponential time to even find a single Pareto-optimal point. This is the first
example of an exponential performance gap through the use of crossover for the
widely used NSGA-II algorithm.
- Abstract（参考訳）: 進化的アルゴリズムは、多目的最適化(パレート最適化とも呼ばれる)のための一般的なアルゴリズムである。
その人気にもかかわらず、多目的進化最適化(EMO)の理論基盤は、まだ初期段階にある。
クロスオーバー演算子の利点のような基本的な質問は、まだ完全には理解されていない。
本稿では,よく知られたEMOアルゴリズムGSEMOとNSGA-IIの理論解析を行い,クロスオーバーの利点を示す。
クロスオーバーを用いたこれらのEMOアルゴリズムが期待多項式時間でパレート集合を探索する問題のクラスを提案する。
対照的に、クロスオーバーのない他の多くのEMOアルゴリズムは、1つのパレート最適点を見つけるのに指数時間を必要とする。
これは、広く使われているNSGA-IIアルゴリズムのクロスオーバーによる指数的な性能ギャップの最初の例である。
関連論文リスト
- 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) - Runtime Analysis of a Multi-Valued Compact Genetic Algorithm on Generalized OneMax [2.07180164747172]
一般化されたOneMax関数の最初のランタイム解析を提供する。
r-cGAはこのr値のOneMax問題を効率的に解くことを示す。
実験の最後には、多値OneMax関数の別の変種が期待されるランタイムに関する予想を述べる。
論文 参考訳（メタデータ） (2024-04-17T10:40:12Z) - Real-Time Image Segmentation via Hybrid Convolutional-Transformer Architecture Search [49.81353382211113]
マルチヘッド自己認識を高分解能表現CNNに効率的に組み込むという課題に対処する。
本稿では,高解像度機能の利点をフル活用したマルチターゲットマルチブランチ・スーパーネット手法を提案する。
本稿では,Hybrid Convolutional-Transformer Architecture Search (HyCTAS)法を用いて,軽量畳み込み層とメモリ効率のよい自己保持層を最適に組み合わせたモデルを提案する。
論文 参考訳（メタデータ） (2024-03-15T15:47:54Z) - DARLEI: Deep Accelerated Reinforcement Learning with Evolutionary
Intelligence [77.78795329701367]
本稿では,進化アルゴリズムと並列化強化学習を組み合わせたフレームワークであるDARLEIを提案する。
我々はDARLEIの性能を様々な条件で特徴付け、進化形態の多様性に影響を与える要因を明らかにした。
今後DARLEIを拡張して、よりリッチな環境における多様な形態素間の相互作用を取り入れていきたいと考えています。
論文 参考訳（メタデータ） (2023-12-08T16:51:10Z) - 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) - Generalized Schrödinger Bridge Matching [54.171931505066]
一般化Schr"odinger Bridge (GSB) 問題設定は、機械学習の内外を問わず、多くの科学領域で一般的である。
我々は最近の進歩に触発された新しいマッチングアルゴリズムである一般化シュリンガーブリッジマッチング(GSBM)を提案する。
このような一般化は条件最適制御の解法として、変分近似を用いることができることを示す。
論文 参考訳（メタデータ） (2023-10-03T17:42:11Z) - Bidirectional Looking with A Novel Double Exponential Moving Average to
Adaptive and Non-adaptive Momentum Optimizers [109.52244418498974]
我々は,新しいtextscAdmeta(textbfADouble指数textbfMov averagtextbfE textbfAdaptiveおよび非適応運動量)フレームワークを提案する。
我々は、textscAdmetaR と textscAdmetaS の2つの実装を提供し、前者は RAdam を、後者は SGDM をベースとしています。
論文 参考訳（メタデータ） (2023-07-02T18:16:06Z) - Massively Parallel Genetic Optimization through Asynchronous Propagation
of Populations [50.591267188664666]
Propulateは、グローバル最適化のための進化的最適化アルゴリズムとソフトウェアパッケージである。
提案アルゴリズムは, 選択, 突然変異, 交叉, 移動の変種を特徴とする。
Propulateは解の精度を犠牲にすることなく、最大で3桁高速であることがわかった。
論文 参考訳（メタデータ） (2023-01-20T18:17:34Z) - Influence of Binomial Crossover on Approximation Error of Evolutionary
Algorithms [10.984298685238445]
本稿では,二項交叉が進化的アルゴリズムの近似誤差を低減できるかどうかを問う。
二項交叉は遷移行列の優位性をもたらすことが証明された。
知覚上の二項交叉の優位性を高めるための適応的パラメータ戦略を提案する。
論文 参考訳（メタデータ） (2021-09-29T05:15:01Z) - Distributed stochastic optimization with large delays [59.95552973784946]
大規模最適化問題を解決する最も広く使われている手法の1つは、分散非同期勾配勾配(DASGD)である。
DASGDは同じ遅延仮定の下で大域的最適実装モデルに収束することを示す。
論文 参考訳（メタデータ） (2021-07-06T21:59:49Z) - Benchmarking a $(\mu+\lambda)$ Genetic Algorithm with Configurable
Crossover Probability [4.33419118449588]
我々は、突然変異またはランダムに選択された2人の親の再結合によって子孫を生成する、$(mu+lambda)$ Genetic Algorithms (GAs)の家系を調査する。
クロスオーバー確率を拡大することにより、完全突然変異のみのアルゴリズムから完全クロスオーバーベースGAへの補間が可能となる。
論文 参考訳（メタデータ） (2020-06-10T15:22:44Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。