論文の概要: Improved Compact Genetic Algorithms with Efficient Caching

• arxiv url: http://arxiv.org/abs/2504.02972v1
• Date: Thu, 03 Apr 2025 18:47:26 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-04-07 14:50:00.226898
• Title: Improved Compact Genetic Algorithms with Efficient Caching
• Title（参考訳）: 効率的なキャッシングによる遺伝的アルゴリズムの改良
• Authors: Prasanta Dutta, Anirban Mukhopadhyay,
• Abstract要約: 我々は同じ染色体の冗長な評価を避ける手段として,cGAにおけるキャッシュの概念を紹介した。 提案手法は,cGAと等価に動作するが,関数評価の回数を減らすことにより,アルゴリズムの時間効率を向上させる。 提案手法は, エリート主義に基づくcGAの選択圧の高いキャッシング機構をさらに一般化する。
• 参考スコア（独自算出の注目度）: 1.3270838622986498
• License:
• Abstract: Compact Genetic Algorithms (cGAs) are condensed variants of classical Genetic Algorithms (GAs) that use a probability vector representation of the population instead of the complete population. cGAs have been shown to significantly reduce the number of function evaluations required while producing outcomes similar to those of classical GAs. However, cGAs have a tendency to repeatedly generate the same chromosomes as they approach convergence, resulting in unnecessary evaluations of identical chromosomes. This article introduces the concept of caching in cGAs as a means of avoiding redundant evaluations of the same chromosomes. Our proposed approach operates equivalently to cGAs, but enhances the algorithm's time efficiency by reducing the number of function evaluations. We also present a data structure for efficient cache maintenance to ensure low overhead. The proposed caching approach has an asymptotically constant time complexity on average. The proposed method further generalizes the caching mechanism with higher selection pressure for elitism-based cGAs. We conduct a rigorous analysis based on experiments on benchmark optimization problems using two well-known cache replacement strategies. The results demonstrate that caching significantly reduces the number of function evaluations required while maintaining the same level of performance accuracy.
• Abstract（参考訳）: コンパクト遺伝的アルゴリズム(英: Compact Genetic Algorithms、cGAs)は、遺伝的アルゴリズム(英語版) (GAs) の縮合した変種であり、完全な集団ではなく、集団の確率ベクトル表現を使用する。 cGAは,古典的GAと同様の結果が得られながら,必要な機能評価の回数を大幅に減らすことが示されている。 しかし、cGAは収束に近づくにつれて同じ染色体を何度も生成する傾向にあり、結果として同じ染色体を不必要に評価する。 本稿では、同じ染色体の冗長な評価を避ける手段として、cGAにおけるキャッシュの概念を紹介する。 提案手法は,cGAと等価に動作するが,関数評価の回数を減らすことにより,アルゴリズムの時間効率を向上させる。 また、オーバヘッドを低くする効率的なキャッシュメンテナンスのためのデータ構造も提案する。 提案するキャッシュ手法は, 平均的に漸近的に一定の時間的複雑性を有する。 提案手法は, エリート主義に基づくcGAの選択圧の高いキャッシング機構をさらに一般化する。 2つのよく知られたキャッシュ置換戦略を用いて、ベンチマーク最適化問題の実験に基づいて厳密な分析を行う。 その結果、キャッシングは、同じ性能の精度を維持しながら、必要な機能評価の回数を大幅に削減することを示した。

関連論文リスト

• A Greedy Strategy for Graph Cut [95.2841574410968]
  GGCと呼ばれるグラフカットの問題を解決するための欲求戦略を提案する。 これは、各データサンプルがクラスタと見なされる状態から始まり、2つのクラスタを動的にマージする。 GGCはサンプル数に関してほぼ線形な計算複雑性を持つ。
  論文  参考訳（メタデータ） (2024-12-28T05:49:42Z)
• Benchmarking of GPU-optimized Quantum-Inspired Evolutionary Optimization Algorithm using Functional Analysis [0.0]
  本稿では、進化最適化(QIEO)のGPU並列化実装の比較分析について述べる。 その結果,QIEOはGAよりも優れた性能を示した。
  論文  参考訳（メタデータ） (2024-12-12T06:47:23Z)
• Variance-Reducing Couplings for Random Features [57.73648780299374]
  ランダム機能(RF)は、機械学習においてカーネルメソッドをスケールアップする一般的なテクニックである。 ユークリッド空間と離散入力空間の両方で定義されるRFを改善するための結合を求める。 パラダイムとしての分散還元の利点と限界について、驚くほどの結論に達した。
  論文  参考訳（メタデータ） (2024-05-26T12:25:09Z)
• Rethinking and Accelerating Graph Condensation: A Training-Free Approach with Class Partition [49.41718583061147]
  グラフ凝縮(Graph condensation)は、大きなグラフを小さいが情報的な凝縮グラフに置き換えるための、データ中心のソリューションである。 既存のGCメソッドは、複雑な最適化プロセス、過剰なコンピューティングリソースとトレーニング時間を必要とする。 我々は、CGC(Class-partitioned Graph Condensation)と呼ばれるトレーニング不要なGCフレームワークを提案する。 CGCはOgbn-productsグラフを30秒以内に凝縮し、102$Xから104$Xまでのスピードアップを実現し、精度は4.2%まで向上した。
  論文  参考訳（メタデータ） (2024-05-22T14:57:09Z)
• Improving genetic algorithms performance via deterministic population shrinkage [9.334663477968027]
  本稿では,遺伝的アルゴリズム(GA)の性能に対する簡易変数集団サイズ法の適用可能性に関する実証的研究について述べる。 それは、所定のスケジュールに従ってGAランの人口を減少させ、速度と重大度パラメータによって構成する。 その結果,SVPS-GAは性能を向上しながら解の質を保ちつつ,性能向上に要する評価回数を削減し,速度重大性の組合せを示した。
  論文  参考訳（メタデータ） (2024-01-22T17:05:16Z)
• A Discrete Particle Swarm Optimizer for the Design of Cryptographic Boolean Functions [1.6574413179773761]
  このアルゴリズムはHu, Eberhart, Shiによる置換PSOの修正版である。 PSO速度方程式のパラメータは2つのメタ最適化手法を用いて調整される。
  論文  参考訳（メタデータ） (2024-01-09T14:08:42Z)
• Stochastic Optimization for Non-convex Problem with Inexact Hessian Matrix, Gradient, and Function [99.31457740916815]
  信頼領域(TR)と立方体を用いた適応正則化は、非常に魅力的な理論的性質を持つことが証明されている。 TR法とARC法はヘッセン関数,勾配関数,関数値の非コンパクトな計算を同時に行うことができることを示す。
  論文  参考訳（メタデータ） (2023-10-18T10:29:58Z)
• Stochastic Reweighted Gradient Descent [4.355567556995855]
  SRG(stochastic reweighted gradient)と呼ばれる重要サンプリングに基づくアルゴリズムを提案する。 我々は、提案手法の時間とメモリオーバーヘッドに特に注意を払っています。 我々はこの発見を裏付ける実験結果を示す。
  論文  参考訳（メタデータ） (2021-03-23T04:09:43Z)
• Gradient Coding with Dynamic Clustering for Straggler-Tolerant Distributed Learning [55.052517095437]
  勾配降下(GD)は、複数の労働者にデータセットを分散することで学習タスクの並列化に広く用いられている。 分散同期gdにおけるイテレーション完了時間ごとの重要なパフォーマンスボトルネックは$straggling$ workersである。 コード化された分散技術は、最近ストラグラーを緩和し、労働者に冗長な計算を割り当てることでgdイテレーションを高速化するために導入された。 本稿では,従来のトラグリング動作に依存する可能性のあるコードの中から,冗長なデータを労働者に割り当てて選択する動的GC方式を提案する。
  論文  参考訳（メタデータ） (2021-03-01T18:51:29Z)
• Gradient Coding with Dynamic Clustering for Straggler Mitigation [57.9123881133818]
  GC-DCは、前回のイテレーションにおけるストラグラーの振る舞いに基づいて、各クラスタ内のストラグラーワーカ数を規制する。 本稿では,GC-DCが従来のGC方式に比べて通信負荷を増大させることなく,各イテレーションの平均完了時間(各イテレーション)を大幅に改善できることを数値的に示す。
  論文  参考訳（メタデータ） (2020-11-03T18:52:15Z)

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

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