論文の概要: Provable Speedups From Dynamic Population Sizes in Evolutionary Algorithms for Multiobjective Optimization

• arxiv url: http://arxiv.org/abs/2607.23800v1
• Date: Sun, 26 Jul 2026 19:03:29 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-07-28 22:34:15.229355
• Title: Provable Speedups From Dynamic Population Sizes in Evolutionary Algorithms for Multiobjective Optimization
• Title（参考訳）: 多目的最適化のための進化的アルゴリズムにおける動的集団サイズからの確率的高速化
• Abstract要約: 両目的問題クラスCLIMBを導入し,GSEMOと広く使用されているNSGA-IIのランタイムを解析する。 この結果から,NSGA-IIの動的個体群サイズを許容すれば,次数$(sqrtn/log n)$の高速化が達成される可能性が示唆された。 これは、NSGA-II上でのGSEMOの超コンスタントな高速化を示す多目的最適化における最初の厳密な実行時解析である。
• 参考スコア（独自算出の注目度）: 5.482532589225553
• License: http://creativecommons.org/publicdomain/zero/1.0/
• Abstract: This paper investigates the role of dynamic population sizes in evolutionary multi-objective optimization. Although such approaches are widely used in practice, their benefits remain poorly understood, and rigorous runtime analyses explaining when and why they help are still scarce. To address this, we introduce the bi-objective problem class CLIMB and analyze the runtime of GSEMO and the widely used NSGA-II on this problem. Our results show that allowing a dynamic population size for NSGA-II can lead to a moderate improvement, yielding a speedup of order $Ω(\sqrt{n}/\log n)$. In particular, we prove that GSEMO and NSGA-II-DYN, a version of NSGA-II with dynamic population sizes we propose in this paper, can find the Pareto front of CLIMB in expected $O(n \log n)$ fitness evaluations, whereas NSGA-II with a fixed population size requires $Ω(n^{1.5})$ fitness evaluations in expectation. To the best of our knowledge, this is the first rigorous runtime analysis in multi-objective optimization demonstrating a super-constant speedup of GSEMO over NSGA-II. Our analysis builds on concepts from single-objective optimization, like the evolution of population diversity over time, and employs the well-known family-three method to prove the lower bound.
• Abstract（参考訳）: 本稿では,進化的多目的最適化における動的集団サイズの役割について検討する。 このようなアプローチは実際は広く使われているが、その利点は理解されていないままであり、厳密なランタイム分析で、いつ、なぜ助けられるかはいまだに乏しい。 この問題に対処するため,両目的問題クラスCLIMBを導入し,GSEMOのランタイムとNSGA-IIを解析した。 この結果から,NSGA-II の動的集団サイズを許容すれば,次数 $Ω(\sqrt{n}/\log n)$ の高速化が期待できることがわかった。 特に,GSEMO と NSGA-II-DYN の動的集団サイズを持つNSGA-II のバージョンでは,CLIMB の Pareto フロントが期待$O(n \log n)$ 適合度評価で得られるのに対し,NSGA-II の固定人口サイズでは $Ω(n^{1.5})$ 適合度評価が期待できることを示した。 我々の知る限り、これはNSGA-II上でのGSEMOの超定常高速化を示す多目的最適化における最初の厳密な実行時解析である。 我々の分析は、時間とともに個体数の多様性が進化するなど、単目的最適化の概念に基づいており、その下限を証明するためによく知られたファミリー3法を用いている。

関連論文リスト

• 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)
• Quantifying the Optimization and Generalization Advantages of Graph Neural Networks Over Multilayer Perceptrons [50.33260238739837]
  グラフネットワーク(GNN)は、グラフ構造化データから学習する際、顕著な能力を示した。 最適化と一般化の観点から、GNNと一般化を比較した分析の欠如がまだ残っている。
  論文  参考訳（メタデータ） (2023-06-24T10:21:11Z)
• Analysing the Robustness of NSGA-II under Noise [1.7205106391379026]
  EMOアルゴリズムNSGA-IIの最初のランタイム解析が登場した。 NSGA-IIがGSEMOを上回った時期は明らかではない。
  論文  参考訳（メタデータ） (2023-06-07T15:33:54Z)
• 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)
• NAG-GS: Semi-Implicit, Accelerated and Robust Stochastic Optimizer [45.47667026025716]
  2つの重要な要素に依存した、新しく、堅牢で、加速された反復を提案する。 NAG-GSと呼ばれる手法の収束と安定性は、まず広範に研究されている。 我々は、NAG-arityが、重量減衰を伴う運動量SGDや機械学習モデルのトレーニングのためのAdamWといった最先端の手法と競合していることを示す。
  論文  参考訳（メタデータ） (2022-09-29T16:54:53Z)
• 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)
• Stability and Generalization Analysis of Gradient Methods for Shallow Neural Networks [59.142826407441106]
  本稿では,アルゴリズム安定性の概念を活用して,浅層ニューラルネットワーク(SNN)の一般化挙動について検討する。 我々は、SNNを訓練するために勾配降下(GD)と勾配降下(SGD)を考慮する。
  論文  参考訳（メタデータ） (2022-09-19T18:48:00Z)
• A First Runtime Analysis of the NSGA-II on a Multimodal Problem [17.049516028133958]
  この研究は、NSGA-IIが少なくともグローバルSEMOアルゴリズムと同様にOneJumpZeroJump問題の局所最適化に対処していることを示している。 この研究は、NSGA-IIが少なくともグローバルSEMOアルゴリズムと同様にOneJumpZeroJump問題の局所最適化に対処していることを示している。
  論文  参考訳（メタデータ） (2022-04-28T19:44:47Z)
• Improved Convergence Rate of Stochastic Gradient Langevin Dynamics with Variance Reduction and its Application to Optimization [50.83356836818667]
  勾配ランゲヴィン・ダイナミクスは非エプス最適化問題を解くための最も基本的なアルゴリズムの1つである。 本稿では、このタイプの2つの変種、すなわち、分散還元ランジュバンダイナミクスと再帰勾配ランジュバンダイナミクスを示す。
  論文  参考訳（メタデータ） (2022-03-30T11:39:00Z)
• 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)
• Result Diversification by Multi-objective Evolutionary Algorithms with Theoretical Guarantees [94.72461292387146]
  両目的探索問題として結果の多様化問題を再構成し,多目的進化アルゴリズム(EA)を用いて解くことを提案する。 GSEMOが最適時間近似比1/2$を達成できることを理論的に証明する。 目的関数が動的に変化すると、GSEMOはこの近似比をランニングタイムで維持することができ、Borodinらによって提案されたオープンな問題に対処する。
  論文  参考訳（メタデータ） (2021-10-18T14:00:22Z)
• Interpreting and Unifying Graph Neural Networks with An Optimization Framework [47.44773358082203]
  グラフニューラルネットワーク(GNN)は、グラフ構造化データ学習に大きな注目を集めている。 本稿では,異なる伝搬機構と統一最適化問題との驚くほどの関連性を確立する。 提案する統一最適化フレームワークは,いくつかの代表的GNN間の共通性を要約し,柔軟に新しいGNNを設計する新たな機会を開く。
  論文  参考訳（メタデータ） (2021-01-28T08:06:02Z)
• Binarized Graph Neural Network [65.20589262811677]
  我々は二項化グラフニューラルネットワークを開発し、二項化ネットワークパラメータを用いてノードのバイナリ表現を学習する。 提案手法は既存のGNNベースの埋め込み手法にシームレスに統合できる。 実験により、提案された二項化グラフニューラルネットワーク、すなわちBGNは、時間と空間の両方の観点から、桁違いに効率的であることが示されている。
  論文  参考訳（メタデータ） (2020-04-19T09:43:14Z)

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

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