論文の概要: Improving Time and Memory Efficiency of Genetic Algorithms by Storing Populations as Minimum Spanning Trees of Patches

• arxiv url: http://arxiv.org/abs/2306.16686v1
• Date: Thu, 29 Jun 2023 05:12:14 GMT
• ステータス: 処理完了
• システム内更新日: 2023-06-30 14:48:08.881610
• Title: Improving Time and Memory Efficiency of Genetic Algorithms by Storing Populations as Minimum Spanning Trees of Patches
• Title（参考訳）: パッチの最小スパンツリーとして集団を記憶することで遺伝的アルゴリズムの時間と記憶効率を改善する
• Authors: Maxim Buzdalov
• Abstract要約: 進化的アルゴリズムでは、演算子を適用し、人口を保存する計算コストは、適合性評価のコストに匹敵する。 個体群を最小のスパンニングツリーとして保存することは、頂点が個体に対応するが、それらのメタ情報しか含まない場合において、簡単な実装の代替として実現可能であることを示す。 我々の実験は、メモリ使用量と計算コストの両方の観点から、大幅な改善(クロスオーバー演算子の実行を含む)が達成可能であることを示唆している。
• 参考スコア（独自算出の注目度）: 0.0
• License: http://creativecommons.org/licenses/by-nc-nd/4.0/
• Abstract: In many applications of evolutionary algorithms the computational cost of applying operators and storing populations is comparable to the cost of fitness evaluation. Furthermore, by knowing what exactly has changed in an individual by an operator, it is possible to recompute fitness value much more efficiently than from scratch. The associated time and memory improvements have been available for simple evolutionary algorithms, few specific genetic algorithms and in the context of gray-box optimization, but not for all algorithms, and the main reason is that it is difficult to achieve in algorithms using large arbitrarily structured populations. This paper makes a first step towards improving this situation. We show that storing the population as a minimum spanning tree, where vertices correspond to individuals but only contain meta-information about them, and edges store structural differences, or patches, between the individuals, is a viable alternative to the straightforward implementation. Our experiments suggest that significant, even asymptotic, improvements -- including execution of crossover operators! -- can be achieved in terms of both memory usage and computational costs.
• Abstract（参考訳）: 進化的アルゴリズムの多くの応用において、演算子を適用して集団を保存する計算コストは適合度評価のコストに匹敵する。 さらに、操作者が正確に何を変えたかを知ることで、スクラッチからよりもはるかに効率よくフィットネス値を再計算することができる。 関連する時間とメモリの改善は、単純な進化アルゴリズム、特定の遺伝的アルゴリズムが少ないこと、グレーボックス最適化の文脈で利用可能であるが、すべてのアルゴリズムではそうではない。 本稿は、この状況を改善するための第一歩となる。 個体群を最小限のスパンニングツリーとして保存し, 頂点は個体に対応するが, メタ情報のみを格納し, エッジは個体間の構造的差異やパッチを格納し, 簡単な実装の代替となることを示す。 私たちの実験では、メモリ使用量と計算コストの両面で、重要な、あるいは漸近的な改善 -- クロスオーバー演算子の実行を含む!

関連論文リスト

• Improving genetic algorithms performance via deterministic population shrinkage [9.334663477968027]
  本稿では,遺伝的アルゴリズム(GA)の性能に対する簡易変数集団サイズ法の適用可能性に関する実証的研究について述べる。 それは、所定のスケジュールに従ってGAランの人口を減少させ、速度と重大度パラメータによって構成する。 その結果,SVPS-GAは性能を向上しながら解の質を保ちつつ,性能向上に要する評価回数を削減し,速度重大性の組合せを示した。
  論文  参考訳（メタデータ） (2024-01-22T17:05:16Z)
• Efficient Non-Parametric Optimizer Search for Diverse Tasks [93.64739408827604]
  興味のあるタスクを直接検索できる,スケーラブルで汎用的なフレームワークを初めて提示する。 基礎となる数学表現の自然木構造に着想を得て、空間を超木に再配置する。 我々は,モンテカルロ法を木探索に適用し,レジェクションサンプリングと等価形状検出を備える。
  論文  参考訳（メタデータ） (2022-09-27T17:51:31Z)
• Careful seeding for the k-medoids algorithm with incremental k++ cluster construction [4.981260380070016]
  k-medoidsアルゴリズム(INCKM)が最近提案され、この欠点を克服した。 本稿では,クラスタ数を動的に増加させる新しいk-medoidsアルゴリズム(INCKPP)を提案する。 提案アルゴリズムは,改良されたk-メロイドアルゴリズムのパラメータ選択問題を克服し,クラスタリング性能を向上し,不均衡なデータセットをうまく処理することができる。
  論文  参考訳（メタデータ） (2022-07-06T02:25:35Z)
• Efficient algorithms for implementing incremental proximal-point methods [0.3263412255491401]
  機械学習において、モデルトレーニングアルゴリズムは、各計算ステップにおけるトレーニングセットのごく一部を観察する。 いくつかの研究ストリームは、よく知られた近位作用素による勾配よりもコスト関数に関するより多くの情報を活用する試みである。 近似演算子のアルゴリズム効率とソフトウェアモジュール性の両方を達成するために凸双対性理論を利用する新しいアルゴリズムフレームワークを考案する。
  論文  参考訳（メタデータ） (2022-05-03T12:43:26Z)
• Breaking the Linear Iteration Cost Barrier for Some Well-known Conditional Gradient Methods Using MaxIP Data-structures [49.73889315176884]
  条件勾配法(CGM)は現代の機械学習で広く使われている。 ほとんどの取り組みは、全体の実行時間を短縮する手段として、イテレーションの数を減らすことに重点を置いています。 本稿では,多くの基本最適化アルゴリズムに対して,イテレーション毎のコストがパラメータ数にサブ線形である最初のアルゴリズムを示す。
  論文  参考訳（メタデータ） (2021-11-30T05:40:14Z)
• Simple Stochastic and Online Gradient DescentAlgorithms for Pairwise Learning [65.54757265434465]
  ペアワイズ学習(Pairwise learning)とは、損失関数がペアインスタンスに依存するタスクをいう。 オンライン降下(OGD)は、ペアワイズ学習でストリーミングデータを処理する一般的なアプローチである。 本稿では,ペアワイズ学習のための手法について,シンプルでオンラインな下降を提案する。
  論文  参考訳（メタデータ） (2021-11-23T18:10:48Z)
• Provably Faster Algorithms for Bilevel Optimization [54.83583213812667]
  バイレベル最適化は多くの重要な機械学習アプリケーションに広く適用されている。 両レベル最適化のための2つの新しいアルゴリズムを提案する。 両アルゴリズムが$mathcalO(epsilon-1.5)$の複雑さを達成し,既存のアルゴリズムを桁違いに上回っていることを示す。
  論文  参考訳（メタデータ） (2021-06-08T21:05:30Z)
• Towards Optimally Efficient Tree Search with Deep Learning [76.64632985696237]
  本稿では,線形モデルから信号整数を推定する古典整数最小二乗問題について検討する。 問題はNPハードであり、信号処理、バイオインフォマティクス、通信、機械学習といった様々な応用でしばしば発生する。 本稿では, 深いニューラルネットワークを用いて, 単純化されたメモリバウンドA*アルゴリズムの最適推定を推定し, HATSアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2021-01-07T08:00:02Z)
• Genetic Programming is Naturally Suited to Evolve Bagging Ensembles [0.0]
  適合度評価と選択の微妙な変化は、単純で従来のGPアルゴリズムを効率的に進化させるのに十分であることを示す。 我々のアルゴリズムは、最先端のアンサンブルと非アンサンブルGPアルゴリズムと非常によく比較できる。
  論文  参考訳（メタデータ） (2020-09-13T16:28:11Z)
• Variance Reduction with Sparse Gradients [82.41780420431205]
  SVRGやSpiderBoostのような分散還元法では、大きなバッチ勾配と小さなバッチ勾配が混在している。 我々は、新しい空間演算子:ランダムトップk演算子を導入する。 我々のアルゴリズムは、画像分類、自然言語処理、スパース行列分解など様々なタスクにおいて、一貫してSpiderBoostより優れています。
  論文  参考訳（メタデータ） (2020-01-27T08:23:58Z)

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

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