論文の概要: Overcome the Difficulties of NSGA-II via Truthful Crowding Distance with Theoretical Guarantees
- arxiv url: http://arxiv.org/abs/2407.17687v1
- Date: Thu, 25 Jul 2024 01:09:58 GMT
- ステータス: 処理完了
- システム内更新日: 2024-07-26 15:37:23.598145
- Title: Overcome the Difficulties of NSGA-II via Truthful Crowding Distance with Theoretical Guarantees
- Title(参考訳): 理論的保証者による真剣な群集距離によるNSGA-IIの難しさの克服
- Authors: Weijie Zheng, Benjamin Doerr,
- Abstract要約: NSGA-IIは2つ以上の目的のために困難に遭遇することが証明されている。
本稿では,真偽群集距離という,そのような変種を提案する。
NSGA-IIは、理論的な保証のある多くの目的に対してよく機能する単純な構造を持つ最初のNSGA-II変種である。
- 参考スコア(独自算出の注目度): 14.309243378538014
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: The NSGA-II is proven to encounter difficulties for more than two objectives, and the deduced reason is the crowding distance computed by regarding the different objectives independently. The recent theoretical efficiency of the NSGA-III and the SMS-EMOA also supports the deduced reason as both algorithms consider the dependencies of objectives in the second criterion after the non-dominated sorting but with complicated structure or difficult computation. However, there is still a question of whether a simple modification of the original crowding distance can help. This paper proposes such a variant, called truthful crowding distance. This variant inherits the simple structure of summing the component for each objective. For each objective, it first sorts the set of solutions in order of descending objective values, and uses the smallest normalized L1 distance between the current solution and solutions in the earlier positions of the sorted list as the component. Summing up all components gives the value of truthful crowding distance. We call this NSGA-II variant by NSGA-II-T that replaces the original crowding distance with the truthful one, and that sequentially updates the crowding distance value after each removal. We prove that the NSGA-II-T can efficiently cover the full Pareto front for many-objective mOneMinMax and mOJZJ, in contrast to the exponential runtime of the original NSGA-II. Besides, we also prove that it theoretically achieves a slightly better approximation of the Pareto front for OneMinMax than the original NSGA-II with sequential survival selection. Besides, it is the first NSGA-II variant with a simple structure that performs well for many objectives with theoretical guarantees.
- Abstract(参考訳): NSGA-IIは2つ以上の目的のために困難に直面することが証明されており、推定された理由は、異なる目的に関して計算された群集距離である。
NSGA-IIIとSMS-EMOAの最近の理論的効率は、どちらのアルゴリズムも、非支配的なソート後の第2基準における目的の依存関係を複雑な構造や難解な計算で考慮しているため、推論された理由も支持している。
しかし、もともとの群集距離の単純な変更が役立つかどうかはまだ疑問が残る。
本稿では,真偽群集距離という,そのような変種を提案する。
この変種は、各目的のためにコンポーネントをまとめるという単純な構造を継承する。
各目的に対して、まず対象値の順に解の集合をソートし、ソートされたリストの以前の位置にある現在の解と解の間の最小の正規化L1距離を成分として使用する。
すべてのコンポーネントをまとめることで、真に群がる距離の価値が得られます。
我々は、NSGA-II-TによるこのNSGA-II変種を、本来の群集距離を真に置き換え、削除後の群集距離値を逐次更新するNSGA-II-Tと呼ぶ。
NSGA-II-T は、元の NSGA-II の指数ランタイムとは対照的に、多目的 mOneMinMax と mOJZJ のパレートフロント全体を効率的にカバーできることを示す。
また,理論上は,1MinMaxのパレートフロントの精度が,NSGA-IIの逐次生存選択よりも若干向上していることも証明した。
加えて、NSGA-II は理論的な保証のある多くの目的に対してよく機能する単純な構造を持つ最初の NSGA-II 変種である。
関連論文リスト
- Multiobjective Vehicle Routing Optimization with Time Windows: A Hybrid Approach Using Deep Reinforcement Learning and NSGA-II [52.083337333478674]
本稿では、時間窓を用いた多目的車両ルーティング問題(MOVRPTW)に対処するために、ウェイト・アウェア・ディープ・強化学習(WADRL)手法を提案する。
WADRLの結果を最適化するために非支配的ソート遺伝的アルゴリズム-II (NSGA-II) 法を用いる。
論文 参考訳(メタデータ) (2024-07-18T02:46:06Z) - Real-Time Image Segmentation via Hybrid Convolutional-Transformer Architecture Search [49.81353382211113]
マルチヘッド自己認識を高分解能表現CNNに効率的に組み込むという課題に対処する。
本稿では,高解像度機能の利点をフル活用したマルチターゲットマルチブランチ・スーパーネット手法を提案する。
本稿では,Hybrid Convolutional-Transformer Architecture Search (HyCTAS)法を用いて,軽量畳み込み層とメモリ効率のよい自己保持層を最適に組み合わせたモデルを提案する。
論文 参考訳(メタデータ) (2024-03-15T15:47:54Z) - Runtime Analysis of the SMS-EMOA for Many-Objective Optimization [14.309243378538014]
本稿ではSMSEMOAのための厳密なランタイム解析を行う。
SMS-EMOA は GSEMO と NSGA-II に匹敵する性能を示す。
論文 参考訳(メタデータ) (2023-12-16T02:23:09Z) - Runtime Analysis for the NSGA-II: Proving, Quantifying, and Explaining
the Inefficiency For Many Objectives [16.904475483445452]
NSGA-IIは多目的最適化問題を解く最も顕著なアルゴリズムの1つである。
NSGA-IIは多数の目的に対して効果が低いことを示す。
論文 参考訳(メタデータ) (2022-11-23T16:15:26Z) - 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) - From Understanding the Population Dynamics of the NSGA-II to the First
Proven Lower Bounds [10.107150356618588]
我々は, NSGA-IIが適切な個体数を持つためには$Omega(Nnlog n)$関数評価が必要であることを証明した。
2つの目的の群集距離の寄与を計算するために、先頭定数を含む厳密な実行時推定値を得る。
論文 参考訳(メタデータ) (2022-09-28T10:11:20Z) - Learning towards Synchronous Network Memorizability and Generalizability
for Continual Segmentation across Multiple Sites [52.84959869494459]
臨床実践では、複数のサイトから連続的なデータストリームを継続的に学習するために、セグメンテーションネットワークが必要であることが多い。
既存の方法は、通常、以前のサイトのネットワーク記憶可能性や、目に見えないサイトの一般化可能性に制限される。
本稿では,SMG学習フレームワークの提案により,同期記憶可能性と一般化可能性の問題に取り組むことを目的とする。
論文 参考訳(メタデータ) (2022-06-14T13:04:36Z) - Joint Spatial-Temporal and Appearance Modeling with Transformer for
Multiple Object Tracking [59.79252390626194]
本稿ではTransSTAMという新しい手法を提案する。Transformerを利用して各オブジェクトの外観特徴とオブジェクト間の空間的時間的関係の両方をモデル化する。
提案手法はMOT16, MOT17, MOT20を含む複数の公開ベンチマークで評価され, IDF1とHOTAの両方で明確な性能向上を実現している。
論文 参考訳(メタデータ) (2022-05-31T01:19:18Z) - Approximation Guarantees for the Non-Dominated Sorting Genetic Algorithm
II (NSGA-II) [16.904475483445452]
NSGA-IIは人口規模が小さい場合にパレートフロントをいかによく近似するかを考察する。
これはNSGA-IIの近似能力に関する最初の数学的研究であり、定常NSGA-IIに対する最初の実行時解析である。
論文 参考訳(メタデータ) (2022-03-05T09:53:30Z) - Improved Branch and Bound for Neural Network Verification via Lagrangian
Decomposition [161.09660864941603]
ニューラルネットワークの入出力特性を公式に証明するためのブランチとバウンド(BaB)アルゴリズムのスケーラビリティを改善します。
活性化に基づく新しい分岐戦略とBaBフレームワークであるブランチとデュアルネットワーク境界(BaDNB)を提案する。
BaDNBは、従来の完全検証システムを大きなマージンで上回り、対数特性で平均検証時間を最大50倍に削減した。
論文 参考訳(メタデータ) (2021-04-14T09:22:42Z) - 1st Place Solutions for OpenImage2019 -- Object Detection and Instance
Segmentation [116.25081559037872]
この記事では,2つのチャンピオンチーム,検出トラックのMMfruit'とセグメンテーショントラックのMMfruitSeg'のソリューションについて,OpenImage Challenge 2019で紹介する。
一般に、対象検出器の場合、バックボーンの端の共有特徴は分類と回帰の両方に適さないことが知られている。
自己学習型最適特徴抽出によりオブジェクトの分類と回帰を分離するデカップリングヘッド(DH)を提案する。
論文 参考訳(メタデータ) (2020-03-17T06:45:07Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。