論文の概要: 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)
• Runtime Analyses of NSGA-III on Many-Objective Problems [10.955844285189372]
  本稿では,一般的な多目的ベンチマーク問題mLOTZ,mOMM,mCOCZにおけるNSGA-IIIのランタイム解析について述べる。 これらのパラメータは,問題次元,目的数,適合範囲によってどのようにスケールするかを示す。 我々の知る限り、これらは3つ以上の目的に対してNSGA-IIIの最初のランタイム解析である。
  論文  参考訳（メタデータ） (2024-04-17T14:39:14Z)
• NICE: Improving Panoptic Narrative Detection and Segmentation with Cascading Collaborative Learning [77.95710025273218]
  我々は2つの単視的物語認識タスクを共同で学習できるNICEという統合フレームワークを提案する。 PNSとPNDを連接してセグメンテーションのバリ中心をアンカーとすることで、我々のアプローチは2つのタスクを自然に整列させる。 NICEは既存のすべての手法を大差で上回り、PNDは4.1%、PNSは2.9%となっている。
  論文  参考訳（メタデータ） (2023-10-17T03:42:12Z)
• 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)
• MGNNI: Multiscale Graph Neural Networks with Implicit Layers [53.75421430520501]
  暗黙グラフニューラルネットワーク(GNN)は、基礎となるグラフの長距離依存性をキャプチャするために提案されている。 暗黙的GNNの2つの弱点は、長距離依存を捉えるための限られた有効範囲による制約付き表現性と、複数の解像度でグラフ上のマルチスケール情報をキャプチャする能力の欠如である。 グラフ上のマルチスケール構造をモデル化できる暗黙の層(MGNNI)を持つマルチスケールグラフニューラルネットワークを提案する。
  論文  参考訳（メタデータ） (2022-10-15T18:18:55Z)
• 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)
• Lookback for Learning to Branch [77.32867454769936]
  Bipartite Graph Neural Networks (GNN) は、ディープラーニングに基づくMixed-Integer Linear Program (MILP) の重要コンポーネントであることが示されている。 近年の研究では、分岐とバウンド(B&B)の解法における分岐(可変選択)を置き換える上で、そのようなGNNの有効性が実証されている。
  論文  参考訳（メタデータ） (2022-06-30T02:33:32Z)
• 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)
• Efficient Person Search: An Anchor-Free Approach [86.45858994806471]
  パーソンサーチは、クエリーの人物を、リアルで切り刻まれていない画像から、同時にローカライズし、識別することを目的としている。 この目標を達成するために、最先端モデルは通常、Faster R-CNNのような2段階検出器にre-idブランチを追加する。 本研究では,この課題に対処するためのアンカーフリーな手法を提案する。
  論文  参考訳（メタデータ） (2021-09-01T07:01:33Z)
• GEO: Enhancing Combinatorial Optimization with Classical and Quantum Generative Models [62.997667081978825]
  我々は、生成モデルとして知られる機械学習モデルを活用する新しいフレームワークを導入し、最適化問題を解決する。 我々は、テンソルネットワークマシンに依存するGEOの量子インスパイアされたバージョンに注力する。 関数呼び出し数に対する固定予算が与えられた場合、その目標が最小限の最小値を求める場合、その優れた性能を示す。
  論文  参考訳（メタデータ） (2021-01-15T18:18:38Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。