Fugu-MT 論文翻訳(概要): A Crowding Distance That Provably Solves the Difficulties of the NSGA-II in Many-Objective Optimization

論文の概要: A Crowding Distance That Provably Solves the Difficulties of the NSGA-II in Many-Objective Optimization

arxiv url: http://arxiv.org/abs/2407.17687v2
Date: Sun, 18 Aug 2024 09:35:27 GMT
ステータス: 処理完了
システム内更新日: 2024-08-21 01:59:09.518375
Title: A Crowding Distance That Provably Solves the Difficulties of the NSGA-II in Many-Objective Optimization
Title（参考訳）: 多目的最適化におけるNSGA-IIの困難を解消する群集距離
Authors: Weijie Zheng, Yao Gao, Benjamin Doerr,
Abstract要約: 最近の理論的研究により、NSGA-IIは2つ以上の目的を持つ問題を解くのに非常に困難であることが示されている。我々は、これらの過去の研究の洞察を用いて、真に群集距離と呼ばれる群集距離の変種を定義する。本アルゴリズムは,OneMinMax,COCZ,LOTZ,OJZJ$_k$問題の多目的バージョンを解くことができることを示す。
参考スコア（独自算出の注目度）: 13.277972583315051
License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
Abstract: Recent theoretical works have shown that the NSGA-II can have enormous difficulties to solve problems with more than two objectives. In contrast, algorithms like the NSGA-III or SMS-EMOA, differing from the NSGA-II only in the secondary selection criterion, provably perform well in these situations. To remedy this shortcoming of the NSGA-II, but at the same time keep the advantages of the widely accepted crowding distance, we use the insights of these previous work to define a variant of the crowding distance, called truthful crowding distance. Different from the classic crowding distance, it has for any number of objectives the desirable property that a small crowding distance value indicates that some other solution has a similar objective vector. Building on this property, we conduct mathematical runtime analyses for the NSGA-II with truthful crowding distance. We show that this algorithm can solve the many-objective versions of the OneMinMax, COCZ, LOTZ, and OJZJ$_k$ problems in the same (polynomial) asymptotic runtimes as the NSGA-III and the SMS-EMOA. This contrasts the exponential lower bounds previously shown for the classic NSGA-II. For the bi-objective versions of these problems, our NSGA-II has a similar performance as the classic NSGA-II, gaining however from smaller admissible population sizes. For the bi-objective OneMinMax problem, we also observe a (minimally) better performance in approximating the Pareto front. These results suggest that our truthful version of the NSGA-II has the same good performance as the classic NSGA-II in two objectives, but can resolve the drastic problems in more than two objectives.
Abstract（参考訳）: 最近の理論的研究により、NSGA-IIは2つ以上の目的を持つ問題を解くのに非常に困難であることが示されている。対照的に、NSGA-IIIやSMS-EMOAのようなアルゴリズムは、NSGA-IIとは二次選択基準のみが異なるため、これらの状況下では良好に機能する。 NSGA-IIのこの欠点を解決するため、同時に広く受け入れられている群集距離の利点を保ちながら、これらの過去の研究の洞察を用いて、真に群集距離と呼ばれる群集距離の変種を定義する。古典的な群集距離と異なり、任意の目的に対して、小さな群集距離値が、他の解が同様の目的ベクトルを持つことを示す望ましい性質を持つ。この特性に基づいて,真に群集距離を持つNSGA-IIの数学的実行時解析を行う。このアルゴリズムは、NSGA-IIIやSMS-EMOAと同じ(多項式)漸近型ランタイムにおいて、OneMinMax、COCZ、LOTZ、OJZJ$_k$の多目的バージョンを解くことができることを示す。これは、古典的なNSGA-IIに対して示されている指数的な下界とは対照的である。これらの問題に対して、NSGA-IIは古典的なNSGA-IIと類似した性能を有しており、より小さい許容個体数から得られる。双目的のOneMinMax問題に対しては、Paretoフロントを近似する際の(最小限の)パフォーマンスも観察する。これらの結果から,NSGA-IIの真正版は従来のNSGA-IIと2つの目的において同等に優れた性能を示すが,2つ以上の目的において劇的な問題を解決できることが示唆された。

関連論文リスト

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)

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

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