論文の概要: Stochastic Population Update Provably Needs An Archive in Evolutionary Multi-objective Optimization

• arxiv url: http://arxiv.org/abs/2501.16735v1
• Date: Tue, 28 Jan 2025 06:21:38 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-01-29 16:42:35.439885
• Title: Stochastic Population Update Provably Needs An Archive in Evolutionary Multi-objective Optimization
• Title（参考訳）: 確率的人口更新は進化的多目的最適化のアーカイブを必要とする
• Authors: Shengjie Ren, Zimin Liang, Miqing Li, Chao Qian,
• Abstract要約: アーカイブを利用することで,少人数で SPU ベースのMOEA 検索が大幅に高速化できることを示す。 具体的には、よく研究されている二目的問題OneJumpZeroを解決するために、SMS-EMOAとNSGA-IIの2つの確立されたMOEAのランニング時間を分析する。
• 参考スコア（独自算出の注目度）: 20.883780207120783
• License:
• Abstract: Evolutionary algorithms (EAs) have been widely applied to multi-objective optimization, due to their nature of population-based search. Population update, a key component in multi-objective EAs (MOEAs), is usually performed in a greedy, deterministic manner. However, recent studies have questioned this practice and shown that stochastic population update (SPU), which allows inferior solutions have a chance to be preserved, can help MOEAs jump out of local optima more easily. While introducing randomness in the population update process boosts the exploration of MOEAs, there is a drawback that the population may not always preserve the very best solutions found, thus entailing a large population. Intuitively, a possible solution to this issue is to introduce an archive that stores the best solutions ever found. In this paper, we theoretically show that using an archive can allow a small population and accelerate the search of SPU-based MOEAs substantially. Specifically, we analyze the expected running time of two well-established MOEAs, SMS-EMOA and NSGA-II, with SPU for solving a commonly studied bi-objective problem OneJumpZeroJump, and prove that using an archive can bring (even exponential) speedups. The comparison between SMS-EMOA and NSGA-II also suggests that the $(\mu+\mu)$ update mode may be more suitable for SPU than the $(\mu+1)$ update mode. Furthermore, our derived running time bounds for using SPU alone are significantly tighter than previously known ones. Our theoretical findings are also empirically validated on a well-known practical problem, the multi-objective traveling salesperson problem. We hope this work may provide theoretical support to explore different ideas of designing algorithms in evolutionary multi-objective optimization.
• Abstract（参考訳）: 進化的アルゴリズム(EA)は、人口ベース探索の性質から、多目的最適化に広く応用されている。 多目的EA(MOEA)の重要なコンポーネントである集団更新は、通常、欲求的で決定論的に行われる。 しかし、近年の研究では、劣る解を保存できる確率的集団更新(SPU)が、MOEAがより容易に地域最適化から抜け出すのに役立つことが示されている。 人口更新プロセスにおけるランダム性の導入は、MOEAの探索を促進するが、人口が常に最も優れた解決策を保存しているとは限らないという欠点がある。 直感的には、この問題に対する解決策は、これまで見つかった最高のソリューションを格納するアーカイブを導入することである。 本稿では,SPU ベースのMOEA の探索を著しく高速化する上で,アーカイブの利用によって少数の人口の探索が可能であることを理論的に示す。 具体的には、よく研究されている2つのMOEA(SMS-EMOAとNSGA-II)のランニング時間を分析し、一般に研究されている双目的問題のOneJumpZeroJumpを解決するためのSPUを用いて、アーカイブの使用によって(指数関数的な)スピードアップがもたらされることを実証する。 SMS-EMOAとNSGA-IIを比較すると、$(\mu+\mu)$ update modeは$(\mu+1)$ update modeよりもSPUに適している可能性がある。 さらに,SPUのみを用いたランニング時間境界は,従来よりもかなり厳密である。 また,本研究は,多目的旅行セールスパーソン問題(多目的旅行セールスパーソン問題)を実証的に検証した。 この研究が、進化的多目的最適化においてアルゴリズムを設計する様々なアイデアを探求するための理論的支援を提供することを期待している。

関連論文リスト

• Do NOT Think That Much for 2+3=? On the Overthinking of o1-Like LLMs [76.43407125275202]
  o1のようなモデルは、推論中に人間のような長時間の思考をエミュレートすることができる。 本論文は,これらのモデルにおける過度な考察の課題に関する,最初の包括的研究である。 精度を損なうことなく、過剰思考を緩和し、推論プロセスを合理化するための戦略を提案する。
  論文  参考訳（メタデータ） (2024-12-30T18:55:12Z)
• A Pairwise Comparison Relation-assisted Multi-objective Evolutionary Neural Architecture Search Method with Multi-population Mechanism [58.855741970337675]
  ニューラルアーキテクチャサーチ(NAS)により、リサーチ者は広大なサーチスペースを自動的に探索し、効率的なニューラルネットワークを見つけることができる。 NASは重要なボトルネックに悩まされており、探索プロセス中に多くのアーキテクチャを評価する必要がある。 SMEM-NASは,多集団構造に基づく多目的進化アルゴリズムである。
  論文  参考訳（メタデータ） (2024-07-22T12:46:22Z)
• An Archive Can Bring Provable Speed-ups in Multi-Objective Evolutionary Algorithms [22.123838452178585]
  アーカイブを使うことでMOEAのスピードアップを保証できることを示す。 2つの確立されたMOEAに対して、アーカイブを使用することで、期待される実行時間に加速がもたらされることを示す。
  論文  参考訳（メタデータ） (2024-06-04T08:59:16Z)
• Quality-Diversity Algorithms Can Provably Be Helpful for Optimization [24.694984679399315]
  QD(Quality-Diversity)アルゴリズムは、ハイパフォーマンスだが多様なソリューションのセットを見つけることを目的としている。 本稿では,厳密な実行時間解析によってQDアルゴリズムの最適化能力に光を当てようとしている。
  論文  参考訳（メタデータ） (2024-01-19T07:40:24Z)
• Towards Running Time Analysis of Interactive Multi-objective Evolutionary Algorithms [23.815981112784552]
  本稿では,実際のiMOEAに対して,最初の実行時間解析(EAの本質的理論的側面)を提供する。 我々は、OneMinMaxとOneJumpZeroJumpの問題を解くために、よく開発された対話型NSGA-IIのランニングタイムが、それぞれ$O(n log n)$と$O(nk)$であることを示す。
  論文  参考訳（メタデータ） (2023-10-12T14:57:47Z)
• 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)
• Stochastic Population Update Can Provably Be Helpful in Multi-Objective Evolutionary Algorithms [23.248796792928204]
  多目的進化アルゴリズム(MOEA)における集団更新は重要な要素である 本稿では,MOEAの探索において,人口更新が有用であることを示す。 具体的には,二目的問題であるOneJumpZeroとBi-RoyalRoadの2つのMOEA(SMS-EMOAとNSGA-II)の予測実行時間を,決定論的集団更新機構をランダムに置き換えれば指数関数的に減少できることを示す。
  論文  参考訳（メタデータ） (2023-06-05T05:54:56Z)
• Enhancing MAP-Elites with Multiple Parallel Evolution Strategies [8.585387103144825]
  進化戦略(ES)に基づく新しい品質多様性(QD)アルゴリズムを提案する。 MEMESは複数の(最大100までの)同時ESプロセスを維持しており、それぞれが独立してQD最適化用に設計されている。 ブラックボックス最適化とQD強化学習において,MEMESは勾配に基づくQDアルゴリズムと突然変異に基づくQDアルゴリズムの両方より優れていることを示す。
  論文  参考訳（メタデータ） (2023-03-10T18:55:02Z)
• Result Diversification by Multi-objective Evolutionary Algorithms with Theoretical Guarantees [94.72461292387146]
  両目的探索問題として結果の多様化問題を再構成し,多目的進化アルゴリズム(EA)を用いて解くことを提案する。 GSEMOが最適時間近似比1/2$を達成できることを理論的に証明する。 目的関数が動的に変化すると、GSEMOはこの近似比をランニングタイムで維持することができ、Borodinらによって提案されたオープンな問題に対処する。
  論文  参考訳（メタデータ） (2021-10-18T14:00:22Z)
• Harnessing Heterogeneity: Learning from Decomposed Feedback in Bayesian Modeling [68.69431580852535]
  サブグループフィードバックを取り入れた新しいGPレグレッションを導入する。 我々の修正された回帰は、以前のアプローチと比べて、明らかにばらつきを減らし、したがってより正確な後続を減らした。 我々は2つの異なる社会問題に対してアルゴリズムを実行する。
  論文  参考訳（メタデータ） (2021-07-07T03:57:22Z)
• Iterative Feature Matching: Toward Provable Domain Generalization with Logarithmic Environments [55.24895403089543]
  ドメインの一般化は、限られた数のトレーニング環境からのデータで、目に見えないテスト環境でうまく機能することを目的としています。 我々は,O(logd_s)$環境のみを見た後に一般化する予測器を高確率で生成することを保証する反復的特徴マッチングに基づく新しいアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2021-06-18T04:39:19Z)

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

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