論文の概要: GPU-Accelerated Parallel Gene-pool Optimal Mixing in a Gray-Box Optimization Setting

• arxiv url: http://arxiv.org/abs/2203.08680v1
• Date: Wed, 16 Mar 2022 15:08:48 GMT
• ステータス: 処理完了
• システム内更新日: 2023-02-21 23:08:01.335131
• Title: GPU-Accelerated Parallel Gene-pool Optimal Mixing in a Gray-Box Optimization Setting
• Title（参考訳）: グレーボックス最適化設定におけるgpuアクセラレーション並列遺伝子プール最適混合
• Authors: Anton Bouter and Peter A.N. Bosman
• Abstract要約: グラフカラー化は、依存に違反することなく、並列に変化を起こすことができる変数の集合をグループ化するのにどのように使用できるかを示す。 接続性に制限のある十分に大きなグラフでは、高品質なソリューションを見つけるのが最大100倍高速であることがわかった。
• 参考スコア（独自算出の注目度）: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: In a Gray-Box Optimization (GBO) setting that allows for partial evaluations, the fitness of an individual can be updated efficiently after a subset of its variables has been modified. This enables more efficient evolutionary optimization with the Gene-pool Optimal Mixing Evolutionary Algorithm (GOMEA) due to its key strength: Gene-pool Optimal Mixing (GOM). For each solution, GOM performs variation for many (small) sets of variables. To improve efficiency even further, parallel computing can be leveraged. For EAs, typically, this comprises population-wise parallelization. However, unless population sizes are large, this offers limited gains. For large GBO problems, parallelizing GOM-based variation holds greater speed-up potential, regardless of population size. However, this potential cannot be directly exploited because of dependencies between variables. We show how graph coloring can be used to group sets of variables that can undergo variation in parallel without violating dependencies. We test the performance of a CUDA implementation of parallel GOM on a Graphics Processing Unit (GPU) for the Max-Cut problem, a well-known problem for which the dependency structure can be controlled. We find that, for sufficiently large graphs with limited connectivity, finding high-quality solutions can be achieved up to 100 times faster, showcasing the great potential of our approach.
• Abstract（参考訳）: 部分的な評価を可能にするGray-Box Optimization (GBO)設定では、変数のサブセットを変更した後、個人の適合性を効率的に更新することができる。 これにより、Gene-pool Optimal Mixing Evolutionary Algorithm (GOMEA) によるより効率的な進化最適化が可能となる。 各解に対して、GOMは多くの(小さな)変数の集合に対して変分を実行する。 さらに効率を向上させるために、並列コンピューティングを活用できる。 EAの場合、これは人口的に並列化される。 しかし、人口が大きければ、これは限られた利益をもたらす。 大きなGBO問題に対して、GOMに基づく変動の並列化は、人口規模に関係なく、より高速なポテンシャルを持つ。 しかし、変数間の依存関係のため、このポテンシャルを直接利用することはできない。 グラフの彩色は、依存を損なうことなく、並列に変動することのできる変数の集合をグループ化するのにどのように使えるかを示す。 我々は,依存性構造を制御可能なよく知られた問題であるmax-cut問題のグラフィック処理ユニット(gpu)上で,並列gomのcuda実装の性能をテストする。 接続性に制限のある十分に大きなグラフでは、高品質なソリューションは最大100倍高速に実現でき、我々のアプローチの大きな可能性を示している。

関連論文リスト

• Improving genetic algorithms performance via deterministic population shrinkage [9.334663477968027]
  本稿では,遺伝的アルゴリズム(GA)の性能に対する簡易変数集団サイズ法の適用可能性に関する実証的研究について述べる。 それは、所定のスケジュールに従ってGAランの人口を減少させ、速度と重大度パラメータによって構成する。 その結果,SVPS-GAは性能を向上しながら解の質を保ちつつ,性能向上に要する評価回数を削減し,速度重大性の組合せを示した。
  論文  参考訳（メタデータ） (2024-01-22T17:05:16Z)
• All-to-all reconfigurability with sparse and higher-order Ising machines [0.0]
  オール・ツー・オールのネットワーク機能をエミュレートする多重アーキテクチャを導入する。 適応並列テンパリングアルゴリズムの実行は、競合するアルゴリズムと事前ファクターの利点を示す。 pビットIMのスケールされた磁気バージョンは、汎用最適化のための最先端技術よりも桁違いに改善される可能性がある。
  論文  参考訳（メタデータ） (2023-11-21T20:27:02Z)
• Distributed Extra-gradient with Optimal Complexity and Communication Guarantees [60.571030754252824]
  複数のプロセッサ/ワーカー/クライアントがローカルなデュアルベクトルにアクセス可能なマルチGPU設定において、モノトン変分不等式(VI)問題を考察する。 モノトーンVI問題に対するデファクトアルゴリズムであるExtra-gradientは、通信効率が良くないように設計されている。 そこで本稿では,VI の解法に適した非バイアスで適応的な圧縮手法である量子化一般化外部勾配 (Q-GenX) を提案する。
  論文  参考訳（メタデータ） (2023-08-17T21:15:04Z)
• A Joint Python/C++ Library for Efficient yet Accessible Black-Box and Gray-Box Optimization with GOMEA [0.0]
  GOMEAライブラリを導入し、Python経由でC++で既存のGOMEAコードをアクセスできるようにする。 グレーボックス最適化(GBO)とブラックボックス最適化(BBO)の両方でその性能を示す。
  論文  参考訳（メタデータ） (2023-05-10T15:28:31Z)
• Massively Parallel Genetic Optimization through Asynchronous Propagation of Populations [50.591267188664666]
  Propulateは、グローバル最適化のための進化的最適化アルゴリズムとソフトウェアパッケージである。 提案アルゴリズムは, 選択, 突然変異, 交叉, 移動の変種を特徴とする。 Propulateは解の精度を犠牲にすることなく、最大で3桁高速であることがわかった。
  論文  参考訳（メタデータ） (2023-01-20T18:17:34Z)
• Twisted hybrid algorithms for combinatorial optimization [68.8204255655161]
  提案されたハイブリッドアルゴリズムは、コスト関数をハミルトニアン問題にエンコードし、回路の複雑さの低い一連の状態によってエネルギーを最適化する。 レベル$p=2,ldots, 6$の場合、予想される近似比をほぼ維持しながら、レベル$p$を1に減らすことができる。
  論文  参考訳（メタデータ） (2022-03-01T19:47:16Z)
• Adaptive Elastic Training for Sparse Deep Learning on Heterogeneous Multi-GPU Servers [65.60007071024629]
  本稿では,Adaptive SGDが4つの最先端ソリューションよりも精度が高いことを示す。 本稿では,Adaptive SGDが時間と精度で4つの最先端ソリューションより優れていることを示す。
  論文  参考訳（メタデータ） (2021-10-13T20:58:15Z)
• Implementation of Parallel Simplified Swarm Optimization in CUDA [2.322689362836168]
  最適化コンピューティングでは、インテリジェントなSwarmアルゴリズム(SIAs)が並列化に適している。 本稿では,計算能力と汎用性を考慮したGPUに基づくSimplified Swarm Algorithm Optimization (PSSO)を提案する。 結果から,Nの次数による時間複雑性の低減が達成され,資源プリエンプションの問題は完全に回避された。
  論文  参考訳（メタデータ） (2021-10-01T00:15:45Z)
• Distributed stochastic optimization with large delays [59.95552973784946]
  大規模最適化問題を解決する最も広く使われている手法の1つは、分散非同期勾配勾配(DASGD)である。 DASGDは同じ遅延仮定の下で大域的最適実装モデルに収束することを示す。
  論文  参考訳（メタデータ） (2021-07-06T21:59:49Z)
• Boosting Data Reduction for the Maximum Weight Independent Set Problem Using Increasing Transformations [59.84561168501493]
  最大重み独立集合問題に対する新しい一般化データ削減および変換規則を導入する。 驚くべきことに、これらのいわゆる増進変換は問題を単純化し、還元空間を開き、アルゴリズムの後にさらに小さな既約グラフが得られる。 提案アルゴリズムは, 1つのインスタンスを除くすべての既約グラフを計算し, 従来よりも多くのインスタンスを最適に解き, 最高の最先端解法よりも最大2桁高速に解き, 解法DynWVCやHILSよりも高品質な解を求める。
  論文  参考訳（メタデータ） (2020-08-12T08:52:50Z)
• More Effective Randomized Search Heuristics for Graph Coloring Through Dynamic Optimization [15.45783225341009]
  進化的アルゴリズムは、動的最適化を用いて、二部グラフのグラフ彩色問題をより効率的に解くことができることを示す。 3つの島を用いた島式は、すべての$m$-edge二部グラフ上で$Theta(m)$の最適時間で成功し、子孫より優れている。
  論文  参考訳（メタデータ） (2020-05-28T07:55:12Z)

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

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