論文の概要: The First Proven Performance Guarantees for the Non-Dominated Sorting
Genetic Algorithm II (NSGA-II) on a Combinatorial Optimization Problem
- arxiv url: http://arxiv.org/abs/2305.13459v2
- Date: Fri, 9 Jun 2023 11:00:15 GMT
- ステータス: 処理完了
- システム内更新日: 2023-06-12 16:34:35.190564
- Title: The First Proven Performance Guarantees for the Non-Dominated Sorting
Genetic Algorithm II (NSGA-II) on a Combinatorial Optimization Problem
- Title（参考訳）: 組合せ最適化問題に対する非支配的ソーティング遺伝的アルゴリズム(NSGA-II)の最初の性能保証
- Authors: Sacha Cerf, Benjamin Doerr, Benjamin Hebras, Yakob Kahane, Simon
Wietheger
- Abstract要約: NSGA-II(Non-Maninated Sorting Genetic Algorithm-II)は、多目的最適化問題を解くアルゴリズムの1つである。
従来の最適化問題であるNP完全二目的最小スパンニングツリー問題に対して、初めて証明された性能保証を与える。
- 参考スコア（独自算出の注目度）: 6.793248433673384
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: The Non-dominated Sorting Genetic Algorithm-II (NSGA-II) is one of the most
prominent algorithms to solve multi-objective optimization problems. Recently,
the first mathematical runtime guarantees have been obtained for this
algorithm, however only for synthetic benchmark problems.
In this work, we give the first proven performance guarantees for a classic
optimization problem, the NP-complete bi-objective minimum spanning tree
problem. More specifically, we show that the NSGA-II with population size $N
\ge 4((n-1) w_{\max} + 1)$ computes all extremal points of the Pareto front in
an expected number of $O(m^2 n w_{\max} \log(n w_{\max}))$ iterations, where
$n$ is the number of vertices, $m$ the number of edges, and $w_{\max}$ is the
maximum edge weight in the problem instance. This result confirms, via
mathematical means, the good performance of the NSGA-II observed empirically.
It also shows that mathematical analyses of this algorithm are not only
possible for synthetic benchmark problems, but also for more complex
combinatorial optimization problems.
As a side result, we also obtain a new analysis of the performance of the
global SEMO algorithm on the bi-objective minimum spanning tree problem, which
improves the previous best result by a factor of $|F|$, the number of extremal
points of the Pareto front, a set that can be as large as $n w_{\max}$. The
main reason for this improvement is our observation that both multi-objective
evolutionary algorithms find the different extremal points in parallel rather
than sequentially, as assumed in the previous proofs.
- Abstract（参考訳）: NSGA-II(Non-Maninated Sorting Genetic Algorithm-II)は、多目的最適化問題を解くアルゴリズムの1つである。
近年,このアルゴリズムに対して初めて数学的ランタイム保証が得られたが,これは合成ベンチマーク問題に限られている。
本研究では,従来の最適化問題であるNP完全二目的最小スパンニングツリー問題に対して,初めて証明された性能保証を与える。
より具体的には、人口サイズ$n \ge 4((n-1) w_{\max} + 1) のnsga-ii は、pareto フロントのすべての極端点を、期待される数 $o(m^2 n w_{\max} \log(n w_{\max}))$ で計算し、ここで $n$ は頂点数、$m$ 辺数、$w_{\max}$ は問題インスタンスの最大端重である。
この結果は、数学的手法により、NSGA-IIの良好な性能を実証的に確認する。
また、このアルゴリズムの数学的解析は、合成ベンチマーク問題だけでなく、より複雑な組合せ最適化問題にも可能であることも示している。
また,二目的最小スパンディングツリー問題に対するグローバルセモアルゴリズムの性能に関する新たな解析結果を得るとともに,従来の最良値である ||f|$,パレートフロントの極端点数,最大 $n w_{\max}$ の値を求める。
この改善の主な理由は、複数の目的を持つ進化的アルゴリズムが、前述の証明で想定されたように、逐次ではなく、異なる極値点を並列に見つけるという観測である。
関連論文リスト
- On Linear Convergence in Smooth Convex-Concave Bilinearly-Coupled Saddle-Point Optimization: Lower Bounds and Optimal Algorithms [17.227158587717934]
滑らかな凸凹型双線型結合型サドル点問題である $min_xmax_y f(x) + langle y,mathbfB xrangle - g(y)$ を再検討する。
この問題クラスに対して、第一低次複雑性境界と最適線形収束アルゴリズムを設計する。
論文 参考訳（メタデータ） (2024-11-21T22:06:25Z) - Sum-of-Squares inspired Quantum Metaheuristic for Polynomial Optimization with the Hadamard Test and Approximate Amplitude Constraints [76.53316706600717]
最近提案された量子アルゴリズムarXiv:2206.14999は半定値プログラミング(SDP)に基づいている
SDPにインスパイアされた量子アルゴリズムを2乗和に一般化する。
この結果から,本アルゴリズムは大きな問題に適応し,最もよく知られた古典学に近似することが示唆された。
論文 参考訳（メタデータ） (2024-08-14T19:04:13Z) - Analyzing the Runtime of the Gene-pool Optimal Mixing Evolutionary Algorithm (GOMEA) on the Concatenated Trap Function [2.038038953957366]
GOMEAは、リンク学習を利用して問題構造を効率的に活用する進化的アルゴリズムである。
GOMEAは確率の高い$O(m32k)$で解くことができ、$m$はサブファンクションの数、$k$はサブファンクションの長さである。
これは (1+1) 進化的 EA と比較して大きなスピードアップであり、これは$O(ln(m)(mk)k)$期待される評価を必要とする。
論文 参考訳（メタデータ） (2024-07-11T09:37:21Z) - An Algorithm with Optimal Dimension-Dependence for Zero-Order Nonsmooth Nonconvex Stochastic Optimization [37.300102993926046]
リプシッツの目的の滑らかな点も凸点も生成しない点の複雑さについて検討する。
私たちの分析は単純だが強力だ。
Goldstein-subdifferential set, これは最近の進歩を可能にする。
非滑らかな非最適化
論文 参考訳（メタデータ） (2023-07-10T11:56:04Z) - A One-Sample Decentralized Proximal Algorithm for Non-Convex Stochastic
Composite Optimization [10.762749887051546]
本稿では,Proxcal$DASA-GTとProxcal$DASA-Aの2時間スケールアルゴリズムを提案する。
以前の作業とは異なり、我々のアルゴリズムは、大きなバッチサイズ、より複雑な単位演算、より強い仮定を必要とせずに、同等の複雑さを達成する。
論文 参考訳（メタデータ） (2023-02-20T05:16:18Z) - Best of Both Worlds: Practical and Theoretically Optimal Submodular Maximization in Parallel [17.462968952951883]
主アルゴリズムは、独立した関心を持つ可能性のある2つのコンポーネントから組み立てられる。
LINEARSEQの変種は、文献のどのアルゴリズムよりも小さい$O(log(n))$の適応複雑性を持つ。
論文 参考訳（メタデータ） (2021-11-15T17:10:40Z) - Provably Faster Algorithms for Bilevel Optimization [54.83583213812667]
バイレベル最適化は多くの重要な機械学習アプリケーションに広く適用されている。
両レベル最適化のための2つの新しいアルゴリズムを提案する。
両アルゴリズムが$mathcalO(epsilon-1.5)$の複雑さを達成し,既存のアルゴリズムを桁違いに上回っていることを示す。
論文 参考訳（メタデータ） (2021-06-08T21:05:30Z) - Bayesian Optimistic Optimisation with Exponentially Decaying Regret [58.02542541410322]
現在の実用的なBOアルゴリズムは、$mathcalO(fraclogNsqrtN)$から$mathcalO(e-sqrtN)$まで、$N$は評価の数である。
本稿では,boと木に基づく楽観的楽観化の概念を絡み合うことにより,無音環境における後悔を改善できる可能性について検討する。
次数$mathcal O(N-sqrt)で指数的再帰を達成できる最初の実践的手法であるBOOアルゴリズムを提案する。
論文 参考訳（メタデータ） (2021-05-10T13:07:44Z) - Recent Theoretical Advances in Non-Convex Optimization [56.88981258425256]
近年、深層ネットワークにおける非最適化アルゴリズムの解析やデータ問題への関心が高まっており、非最適化のための理論的最適化アルゴリズムの最近の結果の概要を概説する。
論文 参考訳（メタデータ） (2020-12-11T08:28:51Z) - A Two-Timescale Framework for Bilevel Optimization: Complexity Analysis
and Application to Actor-Critic [142.1492359556374]
双レベル最適化は、2レベル構造を示す問題のクラスである。
このような二段階問題に対処するための2段階近似(TTSA)アルゴリズムを提案する。
本稿では,TTSAフレームワークの特殊な事例として,2段階の自然なアクター・クリティカルポリシー最適化アルゴリズムが有用であることを示す。
論文 参考訳（メタデータ） (2020-07-10T05:20:02Z) - Ranking a set of objects: a graph based least-square approach [70.7866286425868]
同一労働者の群集によるノイズの多いペアワイズ比較から始まる$N$オブジェクトのランク付けの問題について考察する。
品質評価のために,最小二乗内在的最適化基準に依存する非適応的ランキングアルゴリズムのクラスを提案する。
論文 参考訳（メタデータ） (2020-02-26T16:19:09Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。