論文の概要: Runtime Analysis of Evolutionary Diversity Optimization on the Multi-objective (LeadingOnes, TrailingZeros) Problem
- arxiv url: http://arxiv.org/abs/2404.11496v1
- Date: Wed, 17 Apr 2024 15:51:15 GMT
- ステータス: 処理完了
- システム内更新日: 2024-04-18 13:25:44.180300
- Title: Runtime Analysis of Evolutionary Diversity Optimization on the Multi-objective (LeadingOnes, TrailingZeros) Problem
- Title（参考訳）: 多目的 (LeadingOnes, TrailingZeros) 問題における進化的多様性最適化の実行時解析
- Authors: Denis Antipov, Aneta Neumann, Frank Neumann. Andrew M. Sutton,
- Abstract要約: 進化的多様性最適化(EDO)を3つの対象関数 LOTZ$_k$ 上で証明する。
GSEMOが全てのパレート最適解の集合を$O(kn3)$期待反復で計算することを示す。
両多様性尺度に非常によく似た振る舞いを示す実証的な研究で、我々の理論分析を補完する。
- 参考スコア（独自算出の注目度）: 2.285821277711785
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: The diversity optimization is the class of optimization problems, in which we aim at finding a diverse set of good solutions. One of the frequently used approaches to solve such problems is to use evolutionary algorithms which evolve a desired diverse population. This approach is called evolutionary diversity optimization (EDO). In this paper, we analyse EDO on a 3-objective function LOTZ$_k$, which is a modification of the 2-objective benchmark function (LeadingOnes, TrailingZeros). We prove that the GSEMO computes a set of all Pareto-optimal solutions in $O(kn^3)$ expected iterations. We also analyze the runtime of the GSEMO$_D$ (a modification of the GSEMO for diversity optimization) until it finds a population with the best possible diversity for two different diversity measures, the total imbalance and the sorted imbalances vector. For the first measure we show that the GSEMO$_D$ optimizes it asymptotically faster than it finds a Pareto-optimal population, in $O(kn^2\log(n))$ expected iterations, and for the second measure we show an upper bound of $O(k^2n^3\log(n))$ expected iterations. We complement our theoretical analysis with an empirical study, which shows a very similar behavior for both diversity measures that is close to the theory predictions.
- Abstract（参考訳）: 多様性最適化は最適化問題のクラスであり、優れたソリューションの多様なセットを見つけることを目的としています。
このような問題を解決するためによく使われるアプローチの1つは、望ましい多様な個体群を進化させる進化的アルゴリズムを使用することである。
このアプローチは進化的多様性最適化(EDO)と呼ばれる。
本稿では,2オブジェクトのベンチマーク関数 (LeadingOnes, TrailingZeros) を改良した3オブジェクト関数 LOTZ$_k$ を用いてEDOを解析する。
我々は、GSEMOが全てのパレート最適解の集合を$O(kn^3)$期待反復で計算することを証明した。
また、GSEMO$_D$(多様性最適化のためのGSEMOの変更)のランタイムを解析し、2つの異なる多様性尺度、総不均衡とソート不均衡ベクトルに対して、最も可能な多様性を持つ個体群を見つける。
第1の測度に対して、GSEMO$_D$はパレート最適集団よりも漸近的に最適化され、$O(kn^2\log(n))$期待反復、第2の測度では$O(k^2n^3\log(n))$期待反復を示す。
我々は、理論解析を実証的な研究で補完し、理論予測に近く、両方の多様性尺度に非常によく似た振る舞いを示す。
関連論文リスト
- $f$-PO: Generalizing Preference Optimization with $f$-divergence Minimization [91.43730624072226]
$f$-POは、既存のアプローチを一般化し拡張する新しいフレームワークである。
ベンチマークデータセットを用いて最先端言語モデルの実験を行う。
論文 参考訳（メタデータ） (2024-10-29T02:11:45Z) - Rigorous Runtime Analysis of Diversity Optimization with GSEMO on
OneMinMax [13.026567958569965]
両目的のベンチマーク問題であるOneMinにおいて,GSEMOアルゴリズムの多様性向上による人口の多様性の最適化について検討した。
問題サイズ$n$が奇数である場合、期待時間$O(n2)$で最適な多様性を持つ集団が見つかることを証明している。
目標を達成するために、人口のランダムウォークを分析し、人口の変化頻度とその成果を反映する。
論文 参考訳（メタデータ） (2023-07-14T09:43:29Z) - Enhanced Opposition Differential Evolution Algorithm for Multimodal
Optimization [0.2538209532048866]
現実の問題は、本質的には複数の最適値からなるマルチモーダルである。
古典的な勾配に基づく手法は、目的関数が不連続あるいは微分不可能な最適化問題に対して失敗する。
我々は,MMOPを解くために,拡張オポポジション微分進化(EODE)アルゴリズムを提案する。
論文 参考訳（メタデータ） (2022-08-23T16:18:27Z) - Optimizer Amalgamation [124.33523126363728]
私たちは、Amalgamationという新しい問題の研究を動機付けています。"Teacher"アマルガメーションのプールを、より強力な問題固有のパフォーマンスを持つ単一の"学生"にどのように組み合わせるべきなのでしょうか?
まず、勾配降下による解析のプールをアマルガメートする3つの異なるメカニズムを定義する。
また, プロセスの分散を低減するため, 目標を摂動させることでプロセスの安定化を図る。
論文 参考訳（メタデータ） (2022-03-12T16:07:57Z) - Result Diversification by Multi-objective Evolutionary Algorithms with
Theoretical Guarantees [94.72461292387146]
両目的探索問題として結果の多様化問題を再構成し,多目的進化アルゴリズム(EA)を用いて解くことを提案する。
GSEMOが最適時間近似比1/2$を達成できることを理論的に証明する。
目的関数が動的に変化すると、GSEMOはこの近似比をランニングタイムで維持することができ、Borodinらによって提案されたオープンな問題に対処する。
論文 参考訳（メタデータ） (2021-10-18T14:00:22Z) - An Analysis of Phenotypic Diversity in Multi-Solution Optimization [118.97353274202749]
マルチモーダル最適化は高い適合性ソリューションを生み出し、品質の多様性は遺伝的中立性に敏感ではない。
オートエンコーダは表現型特徴を自動的に発見するために使用され、品質の多様性を備えたさらに多様なソリューションセットを生成する。
論文 参考訳（メタデータ） (2021-05-10T10:39:03Z) - Unified Convergence Analysis for Adaptive Optimization with Moving Average Estimator [75.05106948314956]
1次モーメントに対する大きな運動量パラメータの増大は適応的スケーリングに十分であることを示す。
また,段階的に減少するステップサイズに応じて,段階的に運動量を増加させるための洞察を与える。
論文 参考訳（メタデータ） (2021-04-30T08:50:24Z) - Theoretical Analyses of Multiobjective Evolutionary Algorithms on
Multimodal Objectives [15.56430085052365]
OJZJ問題(OJZJ problem)は、古典的なジャンプ関数のベンチマークに同型な2つの目的からなる双目的問題である。
確率1のSEMOは、実行時に関係なく、完全なParetoフロントを計算していないことを証明します。
また、より厳密な制限付き$frac 32 e nk+1 pm o(nk+1)$を示す。
論文 参考訳（メタデータ） (2020-12-14T03:07:39Z) - A Framework to Handle Multi-modal Multi-objective Optimization in
Decomposition-based Evolutionary Algorithms [7.81768535871051]
分解に基づく進化的アルゴリズムは多目的最適化に優れた性能を持つ。
解空間の多様性を維持するメカニズムが欠如しているため、マルチモーダルな多目的最適化にはあまり役に立たない可能性が高い。
本稿では,マルチモーダル多目的最適化のための分解に基づく進化的アルゴリズムの性能向上のためのフレームワークを提案する。
論文 参考訳（メタデータ） (2020-09-30T14:32:57Z) - Robust, Accurate Stochastic Optimization for Variational Inference [68.83746081733464]
また, 共通最適化手法は, 問題が適度に大きい場合, 変分近似の精度が低下することを示した。
これらの結果から,基礎となるアルゴリズムをマルコフ連鎖の生成とみなして,より堅牢で正確な最適化フレームワークを開発する。
論文 参考訳（メタデータ） (2020-09-01T19:12:11Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。