論文の概要: Analysis of Evolutionary Diversity Optimisation for the Maximum Matching Problem

• arxiv url: http://arxiv.org/abs/2404.11784v1
• Date: Wed, 17 Apr 2024 22:20:02 GMT
• ステータス: 処理完了
• システム内更新日: 2024-04-19 20:00:41.780283
• Title: Analysis of Evolutionary Diversity Optimisation for the Maximum Matching Problem
• Title（参考訳）: 最大マッチング問題に対する進化的多様性最適化の解析
• Authors: Jonathan Gadea Harder, Aneta Neumann, Frank Neumann,
• Abstract要約: 我々は、小さなギャップの場合、$(mu+1)$EAが$O(mu2 m4 log(m))$の期待ランタイムで最大多様性を達成することを示す。 2P-EA_D$はより強力なパフォーマンスを示し、小さなギャップケースは$O(mu2 n2 log(m))$、パスは$O(mu3 m3)$である。
• 参考スコア（独自算出の注目度）: 10.506038775815094
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: This paper explores the enhancement of solution diversity in evolutionary algorithms (EAs) for the maximum matching problem, concentrating on complete bipartite graphs and paths. We adopt binary string encoding for matchings and use Hamming distance to measure diversity, aiming for its maximization. Our study centers on the $(\mu+1)$-EA and $2P-EA_D$, which are applied to optimize diversity. We provide a rigorous theoretical and empirical analysis of these algorithms. For complete bipartite graphs, our runtime analysis shows that, with a reasonably small $\mu$, the $(\mu+1)$-EA achieves maximal diversity with an expected runtime of $O(\mu^2 m^4 \log(m))$ for the small gap case (where the population size $\mu$ is less than the difference in the sizes of the bipartite partitions) and $O(\mu^2 m^2 \log(m))$ otherwise. For paths, we establish an upper runtime bound of $O(\mu^3 m^3)$. The $2P-EA_D$ displays stronger performance, with bounds of $O(\mu^2 m^2 \log(m))$ for the small gap case, $O(\mu^2 n^2 \log(n))$ otherwise, and $O(\mu^3 m^2)$ for paths. Here, $n$ represents the total number of vertices and $m$ the number of edges. Our empirical studies, which examine the scaling behavior with respect to $m$ and $\mu$, complement these theoretical insights and suggest potential for further refinement of the runtime bounds.
• Abstract（参考訳）: 本稿では,進化的アルゴリズム (EA) における解の多様性の最大マッチング問題に対する拡張について検討し,完全な二部グラフと経路に着目した。 マッチングにバイナリ文字列符号化を採用し、ハミング距離を用いて多様性を測定し、最大化を目指す。 本研究は,多様性を最適化するための$(\mu+1)$-EAと$2P-EA_D$に焦点を当てる。 これらのアルゴリズムの厳密な理論的および実証的な分析を提供する。 完全な二部グラフの場合、我々の実行時解析では、$(\mu+1)$-EA は$O(\mu^2 m^4 \log のランタイムで最大値の多様性を達成する。 (m)$ for the small gap case(人口規模$\mu$は二部分裂の大きさの違いより小さい)と$O(\mu^2 m^2 \log (m)$でなければ。 パスについては、$O(\mu^3 m^3)$の上限を定めます。 2P-EA_D$は、O(\mu^2 m^2 \log)のバウンドを持つより強いパフォーマンスを示す。 (m)$ の場合、$O(\mu^2 n^2 \log (n)$、そうでなければ$O(\mu^3 m^2)$である。 ここで、$n$は頂点の総数を表し、$m$は辺の数を表す。 我々の経験的研究は、$m$と$\mu$に関するスケーリングの振る舞いを検証し、これらの理論的洞察を補完し、ランタイム境界のさらなる改善の可能性を提案する。

関連論文リスト

• Parameterized Approximation for Robust Clustering in Discrete Geometric Spaces [2.687607197645453]
  次元$Theta(log n)$ が $(sqrt3/2-o(1))$hard である場合でさえ、FPTアルゴリズムを近似する。 また、次元 $Theta(log n)$ が $(sqrt3/2-o(1))$hard であるような特別な場合でさえ、FPTアルゴリズムを近似することを示す。
  論文  参考訳（メタデータ） (2023-05-12T08:43:28Z)
• Lasting Diversity and Superior Runtime Guarantees for the $(\mu+1)$ Genetic Algorithm [7.421135890148154]
  集団サイズが$mu=O(n)$の遺伝的アルゴリズムは、ギャップサイズが$k ge 3$のジャンプ関数を最適化する。 この多様性は、(二次的ではなく)$mu$で指数関数的に高い確率で持続することを示す。 すべての$cln(n)lemu le n/log n$, with $c$ a suitable constant, the runtime of the $(mu+1)$ GA on $mathrmJump_k$, with $k
  論文  参考訳（メタデータ） (2023-02-24T10:50:24Z)
• Optimal Gradient Sliding and its Application to Distributed Optimization Under Similarity [121.83085611327654]
  積 $r:=p + q$, ここで$r$は$mu$-strong convex類似性である。 エージェントの通信やローカルコールにマスターされた問題を解決する方法を提案する。 提案手法は$mathcalO(sqrtL_q/mu)$法よりもはるかにシャープである。
  論文  参考訳（メタデータ） (2022-05-30T14:28:02Z)
• TURF: A Two-factor, Universal, Robust, Fast Distribution Learning Algorithm [64.13217062232874]
  最も強力で成功したモダリティの1つは、全ての分布を$ell$距離に近似し、基本的に最も近い$t$-piece次数-$d_$の少なくとも1倍大きい。 本稿では,この数値をほぼ最適に推定する手法を提案する。
  論文  参考訳（メタデータ） (2022-02-15T03:49:28Z)
• Quantum speedups for dynamic programming on $n$-dimensional lattice graphs [0.11470070927586015]
  複雑性を$widetilde O(T_Dn)$で表すと、$T_D D+1$となる。 最もよく知られている古典的アルゴリズムは $textpoly(m,n)log n T_Dn$ であるが、量子アルゴリズムの時間複雑性は $textpoly(m,n)log n T_Dn$ である。
  論文  参考訳（メタデータ） (2021-04-29T14:50:03Z)
• An Optimal Separation of Randomized and Quantum Query Complexity [67.19751155411075]
  すべての決定木に対して、与えられた順序 $ellsqrtbinomdell (1+log n)ell-1,$ sum to at least $cellsqrtbinomdell (1+log n)ell-1,$ where $n$ is the number of variables, $d$ is the tree depth, $c>0$ is a absolute constant。
  論文  参考訳（メタデータ） (2020-08-24T06:50:57Z)
• Streaming Complexity of SVMs [110.63976030971106]
  本稿では,ストリーミングモデルにおけるバイアス正規化SVM問題を解く際の空間複雑性について検討する。 両方の問題に対して、$frac1lambdaepsilon$の次元に対して、$frac1lambdaepsilon$よりも空間的に小さいストリーミングアルゴリズムを得ることができることを示す。
  論文  参考訳（メタデータ） (2020-07-07T17:10:00Z)
• Revisiting EXTRA for Smooth Distributed Optimization [70.65867695317633]
  改良された$Oleft(left(fracLmu+frac11-sigma_2(W)right)logfrac1epsilon (1-sigma_2(W))right)$。 高速化されたEXTRAの通信複雑性は、$left(logfracLmu (1-sigma_2(W))right)$と$left(logfrac1epsilon (1。
  論文  参考訳（メタデータ） (2020-02-24T08:07:08Z)
• Agnostic Q-learning with Function Approximation in Deterministic Systems: Tight Bounds on Approximation Error and Sample Complexity [94.37110094442136]
  本稿では,決定論的システムにおける関数近似を用いたQ$学習の問題について検討する。 もし$delta = Oleft(rho/sqrtdim_Eright)$なら、$Oleft(dim_Eright)$を使って最適なポリシーを見つけることができる。
  論文  参考訳（メタデータ） (2020-02-17T18:41:49Z)

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

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