論文の概要: Crossover Can Guarantee Exponential Speed-Ups in Evolutionary
Multi-Objective Optimisation
- arxiv url: http://arxiv.org/abs/2301.13687v2
- Date: Mon, 4 Dec 2023 14:44:44 GMT
- ステータス: 処理完了
- システム内更新日: 2023-12-06 01:39:28.338328
- Title: Crossover Can Guarantee Exponential Speed-Ups in Evolutionary
Multi-Objective Optimisation
- Title（参考訳）: クロスオーバーは進化的多目的最適化における指数的スピードアップを保証できる
- Authors: Duc-Cuong Dang and Andre Opris and Dirk Sudholt
- Abstract要約: 本稿では,よく知られたEMOアルゴリズムGSEMOとNSGA-IIの理論的解析を行う。
免疫刺激による過変異は指数的最適化時間を回避することはできない。
- 参考スコア（独自算出の注目度）: 4.212663349859165
- 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 the well-known EMO algorithms GSEMO and NSGA-II to showcase the
possible advantages of crossover: we propose classes of "royal road" functions
on which these algorithms cover the whole Pareto front in expected polynomial
time if crossover is being used. But when disabling crossover, they require
exponential time in expectation to cover the Pareto front. The latter even
holds for a large class of black-box algorithms using any elitist selection and
any unbiased mutation operator. Moreover, even the expected time to create a
single Pareto-optimal search point is exponential. We provide two different
function classes, one tailored for one-point crossover and another one tailored
for uniform crossover, and we show that immune-inspired hypermutations cannot
avoid exponential optimisation times. Our work shows the first example of an
exponential performance gap through the use of crossover for the widely used
NSGA-II algorithm and contributes to a deeper understanding of its limitations
and capabilities.
- Abstract（参考訳）: 進化的アルゴリズムは、多目的最適化(パレート最適化とも呼ばれる)のための一般的なアルゴリズムである。
その人気にもかかわらず、多目的進化最適化(EMO)の理論基盤は、まだ初期段階にある。
クロスオーバー演算子の利点のような基本的な質問は、まだ完全には理解されていない。
我々は,よく知られたemoアルゴリズムであるgsemoとnsga-iiの理論的解析を行い,クロスオーバーの可能性を示す。
しかし、クロスオーバーを無効にする場合は、パレートフロントをカバーするために指数関数的な時間を要する。
後者は、エリート選択と偏りのない突然変異演算子を使用して、ブラックボックスアルゴリズムの大きなクラスも持つ。
さらに、単一のパレート最適探索点を作成するための期待時間さえ指数関数的である。
我々は,一点交叉に適した機能クラスと一点交叉に適した機能クラスを2種類提供し,免疫刺激による過変異は指数的最適化時間を回避できないことを示した。
本研究は,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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。