論文の概要: 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アルゴリズムのクロスオーバーによる指数関数的性能ギャップの最初の例を示し,その限界と能力のより深い理解に寄与する。
関連論文リスト
- 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。