論文の概要: 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アルゴリズムのクロスオーバーによる指数的な性能ギャップの最初の例である。
関連論文リスト
- 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\"odinger Bridge Matching [57.40143569424158]
一般化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) - Quantum Genetic Algorithm with Individuals in Multiple Registers [0.0]
本稿では,サブルーチンに基づく量子遺伝的アルゴリズムを提案する。
この独特な体系化により、遺伝的アルゴリズムを特徴付ける基本的な要素をすべて記述できる。
量子可観測体の生物模倣的クローニングとブヴ・ゼク・ヒラーイ普遍量子クローニングマシンの2つのパラダイム例について検討する。
論文 参考訳(メタデータ) (2022-03-28T19:05:03Z) - 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) - 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) - A Simple yet Universal Strategy for Online Convex Optimization [97.64589722655612]
ユニバーサルオンライン凸最適化のための簡単な戦略を提案する。
鍵となるアイデアは、元のオンライン機能を処理する専門家のセットを構築し、emphlinearized lossの上にメタアゴリタムを配置することだ。
我々の戦略は、強い凸関数と指数関数のために設計された専門家の理論的保証を継承する。
論文 参考訳(メタデータ) (2021-05-08T11:43: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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。