論文の概要: Runtime Analysis of Quality Diversity Algorithms

• arxiv url: http://arxiv.org/abs/2305.18966v2
• Date: Tue, 4 Jul 2023 07:10:38 GMT
• ステータス: 処理完了
• システム内更新日: 2023-07-06 20:35:24.852367
• Title: Runtime Analysis of Quality Diversity Algorithms
• Title（参考訳）: 品質多様性アルゴリズムの実行時解析
• Authors: Jakob Bossek, Dirk Sudholt
• Abstract要約: 品質粒度(QD)は進化計算の一分野であり、近年関心が高まりつつある。 本稿では,擬似ブール最適化の文脈において,特徴空間の個数に関する簡単なQDアルゴリズムについて検討する。 この結果から,QD は予測された時間で最小の分布木となることがわかった。
• 参考スコア（独自算出の注目度）: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Quality diversity~(QD) is a branch of evolutionary computation that gained increasing interest in recent years. The Map-Elites QD approach defines a feature space, i.e., a partition of the search space, and stores the best solution for each cell of this space. We study a simple QD algorithm in the context of pseudo-Boolean optimisation on the ``number of ones'' feature space, where the $i$th cell stores the best solution amongst those with a number of ones in $[(i-1)k, ik-1]$. Here $k$ is a granularity parameter $1 \leq k \leq n+1$. We give a tight bound on the expected time until all cells are covered for arbitrary fitness functions and for all $k$ and analyse the expected optimisation time of QD on \textsc{OneMax} and other problems whose structure aligns favourably with the feature space. On combinatorial problems we show that QD finds a ${(1-1/e)}$-approximation when maximising any monotone sub-modular function with a single uniform cardinality constraint efficiently. Defining the feature space as the number of connected components of a connected graph, we show that QD finds a minimum spanning tree in expected polynomial time.
• Abstract（参考訳）: 品質の多様性~(QD)は進化的計算の分野であり、近年関心が高まりつつある。 map-elites qdアプローチは、探索空間の分割のような特徴空間を定義し、この空間の各セルに対して最適な解を格納する。 我々は,$i$th セルが $[(i-1)k, ik-1]$ で多数のセルを持つセルに対して最適な解を格納する ``number of ones'' 特徴空間上の疑似boolean 最適化の文脈において,単純な qd アルゴリズムについて検討する。 ここで$k$は粒度パラメータ $1 \leq k \leq n+1$ である。 我々は、全てのセルが任意のフィットネス関数に被覆されるまでの期待時間に厳密な拘束を与え、すべての$k$に対して \textsc{OneMax} 上の QD の期待最適化時間と、特徴空間に好適に整合する他の問題を分析する。 組合せ問題では、QD は単調部分モジュラ函数を 1 つの一様濃度制約で効率的に最大化するときに${(1-1/e)}$-近似を求める。 連結グラフの連結成分の個数として特徴空間を定義すると、QDが期待される多項式時間で最小のスパンニングツリーを見つけることを示す。

関連論文リスト

• Run Time Bounds for Integer-Valued OneMax Functions [0.9012198585960443]
  探索空間 $mathbbZn$ を多値決定変数 $0,ldots,r-1n$ の観点から考える。 ステップサイズ適応のRSSが$Theta(n cdot log(|a|_1))$の最適化時間を達成することを示す。 本稿では,これらのアルゴリズムを離散探索空間に対するCMA-ESの変種と比較し,実験的な解析を行った。
  論文  参考訳（メタデータ） (2023-07-21T18:49:06Z)
• Quadratic Memory is Necessary for Optimal Query Complexity in Convex Optimization: Center-of-Mass is Pareto-Optimal [23.94542304111204]
  本研究では,1次凸最適化に最適なオラクル複雑性を実現するためには,二次記憶が必要であることを示す。 単位球上の1ドルのLipschitz凸関数を1/d4$精度で最小化するためには、少なくともd2-delta$ビットのメモリを使用する決定論的一階述語アルゴリズムは$tildeOmega(d1+delta/3)$クエリを生成する必要がある。
  論文  参考訳（メタデータ） (2023-02-09T22:37:27Z)
• Mind the gap: Achieving a super-Grover quantum speedup by jumping to the end [114.3957763744719]
  本稿では,数種類のバイナリ最適化問題に対して,厳密な実行保証を有する量子アルゴリズムを提案する。 このアルゴリズムは、$n$非依存定数$c$に対して、時間で$O*(2(0.5-c)n)$の最適解を求める。 また、$k$-spinモデルからのランダムなインスタンスの多数と、完全に満足あるいはわずかにフラストレーションされた$k$-CSP式に対して、文 (a) がそうであることを示す。
  論文  参考訳（メタデータ） (2022-12-03T02:45:23Z)
• Submodular + Concave [53.208470310734825]
  第一次最適化法が凹関数の最大目的値に収束できることはよく確立されている。 本研究では、滑らかな函数凸体(英語版)の行列式を$F(x) = G(x) +C(x)$で始める。 このクラスの函数は、保証がないような凹凸函数と連続DR-部分モジュラ函数の両方の拡張である。
  論文  参考訳（メタデータ） (2021-06-09T01:59:55Z)
• Finding Global Minima via Kernel Approximations [90.42048080064849]
  関数評価のみに基づく滑らかな関数のグローバル最小化を考える。 本稿では,近似関数を共同でモデル化し,大域的最小値を求める手法を検討する。
  論文  参考訳（メタデータ） (2020-12-22T12:59:30Z)
• Small Covers for Near-Zero Sets of Polynomials and Learning Latent Variable Models [56.98280399449707]
  我々は、s$ of cardinality $m = (k/epsilon)o_d(k1/d)$ に対して $epsilon$-cover が存在することを示す。 構造的結果に基づいて,いくつかの基本的高次元確率モデル隠れ変数の学習アルゴリズムを改良した。
  論文  参考訳（メタデータ） (2020-12-14T18:14:08Z)
• Towards Tight Communication Lower Bounds for Distributed Optimisation [30.134447658488057]
  N$マシンは$sum_i = 1N f_i (x)$という関数の和を最小化することを目的としている。 我々の主な成果は、$N$マシンによって送信され受信される必要がある全ビット数に関する最初の完全に条件のない境界を提供する。 我々は、$Omega(Nd log d / Nvarepsilon)$ total bits をマシン間で通信し、$sum_i = 1N の最小値に対する加算 $epsilon$-approximation を見つける必要があることを示した。
  論文  参考訳（メタデータ） (2020-10-16T08:10:02Z)
• Streaming Complexity of SVMs [110.63976030971106]
  本稿では,ストリーミングモデルにおけるバイアス正規化SVM問題を解く際の空間複雑性について検討する。 両方の問題に対して、$frac1lambdaepsilon$の次元に対して、$frac1lambdaepsilon$よりも空間的に小さいストリーミングアルゴリズムを得ることができることを示す。
  論文  参考訳（メタデータ） (2020-07-07T17:10:00Z)
• Maximizing Determinants under Matroid Constraints [69.25768526213689]
  我々は、$det(sum_i in Sv_i v_i v_itop)$が最大になるような基底を$S$$$$M$とする問題を研究する。 この問題は、実験的なデザイン、商品の公平な割り当て、ネットワーク設計、機械学習など、さまざまな分野に現れている。
  論文  参考訳（メタデータ） (2020-04-16T19:16:38Z)
• A Rigorous Runtime Analysis of the $(1 + (\lambda, \lambda))$ GA on Jump Functions [8.34061303235504]
  我々は,このアルゴリズムの最初の実行時解析を,ジャンプ関数ベンチマークであるマルチモーダル問題クラス上で実施する。 ジャンプ関数の局所最適性を残すという孤立した問題に対して、$(n/k)k/2 eTheta(k)$のランタイムにつながる証明可能な最適パラメータを決定する。
  論文  参考訳（メタデータ） (2020-04-14T17:54:12Z)

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

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