論文の概要: The $(1+(\lambda,\lambda))$ Genetic Algorithm for Permutations

• arxiv url: http://arxiv.org/abs/2004.08664v2
• Date: Sun, 10 May 2020 13:13:44 GMT
• ステータス: 処理完了
• システム内更新日: 2022-12-12 05:19:43.870281
• Title: The $(1+(\lambda,\lambda))$ Genetic Algorithm for Permutations
• Title（参考訳）: 置換のための$(1+(\lambda,\lambda))$遺伝的アルゴリズム
• Authors: Anton Bassin and Maxim Buzdalov
• Abstract要約: 我々は、$(lambda,lambda)$の遺伝的アルゴリズムが、$O(n2)$のフィットネスクエリで最適であることを示す。 また,Hamと呼ばれる置換に基づく問題に対して,このアルゴリズムの最初の解析を行った。
• 参考スコア（独自算出の注目度）: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: The $(1+(\lambda,\lambda))$ genetic algorithm is a bright example of an evolutionary algorithm which was developed based on the insights from theoretical findings. This algorithm uses crossover, and it was shown to asymptotically outperform all mutation-based evolutionary algorithms even on simple problems like OneMax. Subsequently it was studied on a number of other problems, but all of these were pseudo-Boolean. We aim at improving this situation by proposing an adaptation of the $(1+(\lambda,\lambda))$ genetic algorithm to permutation-based problems. Such an adaptation is required, because permutations are noticeably different from bit strings in some key aspects, such as the number of possible mutations and their mutual dependence. We also present the first runtime analysis of this algorithm on a permutation-based problem called Ham whose properties resemble those of OneMax. On this problem, where the simple mutation-based algorithms have the running time of $\Theta(n^2 \log n)$ for problem size $n$, the $(1+(\lambda,\lambda))$ genetic algorithm finds the optimum in $O(n^2)$ fitness queries. We augment this analysis with experiments, which show that this algorithm is also fast in practice.
• Abstract（参考訳）: 1+(\lambda,\lambda)$の遺伝的アルゴリズムは、理論的な発見から得られた知見に基づいて開発された進化的アルゴリズムの明るい例である。 このアルゴリズムはクロスオーバーを使い、OneMaxのような単純な問題でさえ、すべての突然変異ベースの進化アルゴリズムを漸近的に上回ることを示した。 その後、他の多くの問題について研究されたが、これらは全て擬似ブールである。 我々は,1+(\lambda,\lambda)$の遺伝的アルゴリズムを置換問題に適応させることにより,この状況を改善することを目指している。 このような適応は、突然変異の数や相互依存など、ビット文字列といくつかの重要な側面において顕著に異なるため必要である。 また,このアルゴリズムを最初に実行時解析し,その特性がonemaxに類似しているham問題について述べる。 この問題では、単純な突然変異ベースのアルゴリズムが問題サイズが$n$に対して$\theta(n^2 \log n)$である場合、$(1+(\lambda,\lambda))$の遺伝的アルゴリズムは、最適な$o(n^2)$の適合クエリを見つける。 我々はこの解析を実験で補強し,このアルゴリズムが実際に高速であることを示す。

関連論文リスト

• A Scalable Algorithm for Individually Fair K-means Clustering [77.93955971520549]
  Jung et al. と Mahabadi et al が導入した個別フェア (p$, $k$) クラスタリング問題に対するスケーラブルなアルゴリズムを提案する。 クラスタリングは、各$xin P$に対して$delta(x)$ of $x$の範囲内で中心となる場合、個別にフェアと呼ばれる。 我々は,従来よりもアルゴリズムがはるかに高速であるだけでなく,低コストのソリューションを生み出すことを実証的に示す。
  論文  参考訳（メタデータ） (2024-02-09T19:01:48Z)
• Efficiently Learning One-Hidden-Layer ReLU Networks via Schur Polynomials [50.90125395570797]
  正方形損失に関して、標準的なガウス分布の下での$k$ReLU活性化の線形結合をPAC学習する問題をmathbbRd$で検討する。 本研究の主な成果は,この学習課題に対して,サンプルおよび計算複雑性が$(dk/epsilon)O(k)$で,epsilon>0$が目標精度である。
  論文  参考訳（メタデータ） (2023-07-24T14:37:22Z)
• Larger Offspring Populations Help the $(1 + (\lambda, \lambda))$ Genetic Algorithm to Overcome the Noise [76.24156145566425]
  進化的アルゴリズムは、適合性の評価においてノイズに対して堅牢であることが知られている。 我々は$(lambda,lambda)$の遺伝的アルゴリズムがどんなにノイズに強いかを解析する。
  論文  参考訳（メタデータ） (2023-05-08T08:49:01Z)
• Deterministic Nonsmooth Nonconvex Optimization [94.01526844386977]
  次元自由な次元自由アルゴリズムを得るにはランダム化が必要であることを示す。 我々のアルゴリズムは、ReLUネットワークを最適化する最初の決定論的次元自由アルゴリズムを得る。
  論文  参考訳（メタデータ） (2023-02-16T13:57:19Z)
• Runtime Analysis for Permutation-based Evolutionary Algorithms [9.044970217182117]
  ビットストリングの場合のように、スクランブル演算子の重み付きバージョンは、ジャンプサイズが$m$のジャンプ関数において、$mTheta(m)$の順序の高速化につながることを示す。 短い経験的分析によりこれらの知見が裏付けられるが、また、ヴォイド突然変異率のような小さな実装の詳細が重要な違いをもたらすことも明らかである。
  論文  参考訳（メタデータ） (2022-07-05T15:49:29Z)
• Towards a Stronger Theory for Permutation-based Evolutionary Algorithms [8.34061303235504]
  古典的な擬似ブールベンチマークを、置換の集合上で定義されたベンチマークに転送する。 我々は、Scharnow, Tinnefeld, Wegenerによって提案された置換に基づく$(+1)$ EAの厳密なランタイム解析を行う。 我々は、スクランブル作用素の重み付きバージョンが、ビットストリングの場合のように、ジャンプサイズを持つジャンプ関数の次数$mTheta(m)$の高速化につながることを観察する。
  論文  参考訳（メタデータ） (2022-04-15T20:36:35Z)
• Choosing the Right Algorithm With Hints From Complexity Theory [16.33500498939925]
  我々は,メトロポリスのアルゴリズムが,合理的な問題サイズを考慮に入れた全てのアルゴリズムの中で,明らかに最良のものであることを示す。 このタイプの人工アルゴリズムは、$O(n log n)$ランタイムを持つので、重要度に基づくコンパクト遺伝的アルゴリズム(sig-cGA)は、高い確率で、DLB問題を解くことができる。
  論文  参考訳（メタデータ） (2021-09-14T11:12:32Z)
• Streaming Complexity of SVMs [110.63976030971106]
  本稿では,ストリーミングモデルにおけるバイアス正規化SVM問題を解く際の空間複雑性について検討する。 両方の問題に対して、$frac1lambdaepsilon$の次元に対して、$frac1lambdaepsilon$よりも空間的に小さいストリーミングアルゴリズムを得ることができることを示す。
  論文  参考訳（メタデータ） (2020-07-07T17:10:00Z)
• 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)
• Fast Mutation in Crossover-based Algorithms [8.34061303235504]
  Doerr、Le、Makhmara、Nguyen(GECCO)で提案された重尾突然変異演算子 Doerr、Le、Makhmara、Nguyen(GECCO)で提案された重尾突然変異演算子 実験的な研究は、ランダムに満足できるMax-3SATインスタンスにも高速突然変異の有効性を示す。
  論文  参考訳（メタデータ） (2020-04-14T14:16:42Z)
• Model Selection in Contextual Stochastic Bandit Problems [51.94632035240787]
  基本アルゴリズムを選択できるメタアルゴリズムを開発した。 基本アルゴリズムの1つが$O(sqrtT)$後悔している場合でも、一般的には$Omega(sqrtT)$後悔よりも良いものを得ることはできません。
  論文  参考訳（メタデータ） (2020-03-03T18:46:34Z)

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

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