論文の概要: Rigorous Runtime Analysis of Diversity Optimization with GSEMO on OneMinMax

• arxiv url: http://arxiv.org/abs/2307.07248v1
• Date: Fri, 14 Jul 2023 09:43:29 GMT
• ステータス: 処理完了
• システム内更新日: 2023-07-17 14:20:37.720843
• Title: Rigorous Runtime Analysis of Diversity Optimization with GSEMO on OneMinMax
• Title（参考訳）: gsemoによるoneminmax上のダイバーシティ最適化の厳密な実行時解析
• Authors: Denis Antipov, Aneta Neumann, Frank Neumann
• Abstract要約: 両目的のベンチマーク問題であるOneMinにおいて,GSEMOアルゴリズムの多様性向上による人口の多様性の最適化について検討した。 問題サイズ$n$が奇数である場合、期待時間$O(n2)$で最適な多様性を持つ集団が見つかることを証明している。 目標を達成するために、人口のランダムウォークを分析し、人口の変化頻度とその成果を反映する。
• 参考スコア（独自算出の注目度）: 13.026567958569965
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: The evolutionary diversity optimization aims at finding a diverse set of solutions which satisfy some constraint on their fitness. In the context of multi-objective optimization this constraint can require solutions to be Pareto-optimal. In this paper we study how the GSEMO algorithm with additional diversity-enhancing heuristic optimizes a diversity of its population on a bi-objective benchmark problem OneMinMax, for which all solutions are Pareto-optimal. We provide a rigorous runtime analysis of the last step of the optimization, when the algorithm starts with a population with a second-best diversity, and prove that it finds a population with optimal diversity in expected time $O(n^2)$, when the problem size $n$ is odd. For reaching our goal, we analyse the random walk of the population, which reflects the frequency of changes in the population and their outcomes.
• Abstract（参考訳）: 進化的多様性の最適化は、適合性に一定の制約を満たす多様なソリューションを見つけることを目的としている。 多目的最適化の文脈では、この制約はパレート最適解を必要とする。 本稿では,2目的ベンチマーク問題であるOneMinMaxにおいて,GSEMOアルゴリズムが多様性を持つヒューリスティックアルゴリズムをどのように最適化するかを検討する。 最適化の最後のステップの厳密な実行時間解析を行い、アルゴリズムが2番目に高い多様性を持つ集団から始めると、問題のサイズがn$が奇数である場合に、最適な多様性を持つ集団が期待時間であるo(n^2)$で見つかることを証明します。 目的を達成するために,人口の変化頻度とその結果を反映したランダムウォークの分析を行った。

関連論文リスト

• Runtime Analysis of Evolutionary Diversity Optimization on the Multi-objective (LeadingOnes, TrailingZeros) Problem [10.697103866816958]
  進化的多様性最適化(EDO)を3つの対象関数 LOTZ$_k$ 上で証明する。 GSEMOが全てのパレート最適解の集合を$O(kn3)$期待反復で計算することを示す。 両多様性尺度に非常によく似た振る舞いを示す実証的な研究で、我々の理論分析を補完する。
  論文  参考訳（メタデータ） (2024-04-17T15:51:15Z)
• Evolutionary Solution Adaption for Multi-Objective Metal Cutting Process Optimization [59.45414406974091]
  我々は,従来の最適化タスクから解を転送するアルゴリズムの能力を研究することのできる,システムの柔軟性のためのフレームワークを提案する。 NSGA-IIの柔軟性を2つの変種で検討し,1)2つのタスクの解を同時に最適化し,より適応性が高いと期待されるソース間の解を得る,2)活性化あるいは非活性化の異なる可能性に対応する能動的非アクティブなジェノタイプについて検討した。 その結果,標準NSGA-IIによる適応は目標目標への最適化に必要な評価回数を大幅に削減し,提案した変種は適応コストをさらに向上することがわかった。
  論文  参考訳（メタデータ） (2023-05-31T12:07:50Z)
• Multi-Objective GFlowNets [59.16787189214784]
  本稿では,多目的最適化の文脈において,多様な候補を生成する問題について検討する。 薬物発見やマテリアルデザインといった機械学習の多くの応用において、目標は、競合する可能性のある目標のセットを同時に最適化する候補を生成することである。 GFlowNetsをベースとした多目的GFlowNets(MOGFNs)を提案する。
  論文  参考訳（メタデータ） (2022-10-23T16:15:36Z)
• Coevolutionary Pareto Diversity Optimization [13.026567958569965]
  共進化的Pareto Diversity Optimizationアプローチを導入する。 特に,集団間クロスオーバーの利用により,解の集合の多様性がさらに向上することを示す。
  論文  参考訳（メタデータ） (2022-04-12T00:52:13Z)
• Learning Proximal Operators to Discover Multiple Optima [66.98045013486794]
  非家族問題における近位演算子を学習するためのエンドツーエンド手法を提案する。 本手法は,弱い目的と穏やかな条件下では,世界規模で収束することを示す。
  論文  参考訳（メタデータ） (2022-01-28T05:53:28Z)
• 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)
• Entropy-Based Evolutionary Diversity Optimisation for the Traveling Salesperson Problem [11.590506672325668]
  我々は,高次エントロピー尺度(High-order entropy measure)と呼ばれる集団多様性尺度を進化的アルゴリズムに応用し,トラベリングセールスパーソン問題に対する多様な高品質な解を求める。 最近提案されたエッジベースの多様性最適化アプローチと比較して,多数のソリューションや長いセグメントを扱う場合に比べて,大幅な改善が見られた。
  論文  参考訳（メタデータ） (2021-04-28T02:36:14Z)
• Evolutionary Diversity Optimization and the Minimum Spanning Tree Problem [13.264683014487376]
  多様性最適化の文脈において、よく知られた最小スパンニングツリー問題(MST)について検討する。 単純な$(mu+1)$-EAは、高品質の木々の多様化した個体群を効果的に計算できることを示す。
  論文  参考訳（メタデータ） (2020-10-21T11:50:49Z)
• Convergence of adaptive algorithms for weakly convex constrained optimization [59.36386973876765]
  モローエンベロープの勾配のノルムに対して$mathcaltilde O(t-1/4)$収束率を証明する。 我々の分析では、最小バッチサイズが1ドル、定数が1位と2位のモーメントパラメータが1ドル、そしておそらくスムーズな最適化ドメインで機能する。
  論文  参考訳（メタデータ） (2020-06-11T17:43:19Z)

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

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