論文の概要: Tensorized Ant Colony Optimization for GPU Acceleration

• arxiv url: http://arxiv.org/abs/2404.04895v2
• Date: Fri, 12 Apr 2024 08:33:10 GMT
• ステータス: 処理完了
• システム内更新日: 2024-04-15 17:03:53.288710
• Title: Tensorized Ant Colony Optimization for GPU Acceleration
• Title（参考訳）: GPU加速のためのテンソル化アントコロニー最適化
• Authors: Luming Yang, Tao Jiang, Ran Cheng,
• Abstract要約: アントコロニー最適化(Ant Colony Optimization, ACO)は、旅行セールスマン問題の解決に有効であることで有名である。 我々はGPUアクセラレーションの進歩を利用するために新しいAnt Colony Optimization(TensorACO)を導入する。
• 参考スコア（独自算出の注目度）: 14.550636773962317
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Ant Colony Optimization (ACO) is renowned for its effectiveness in solving Traveling Salesman Problems, yet it faces computational challenges in CPU-based environments, particularly with large-scale instances. In response, we introduce a Tensorized Ant Colony Optimization (TensorACO) to utilize the advancements of GPU acceleration. As the core, TensorACO fully transforms ant system and ant path into tensor forms, a process we refer to as tensorization. For the tensorization of ant system, we propose a preprocessing method to reduce the computational overhead by calculating the probability transition matrix. In the tensorization of ant path, we propose an index mapping method to accelerate the update of pheromone matrix by replacing the mechanism of sequential path update with parallel matrix operations. Additionally, we introduce an Adaptive Independent Roulette (AdaIR) method to overcome the challenges of parallelizing ACO's selection mechanism on GPUs. Comprehensive experiments demonstrate the superior performance of TensorACO achieving up to 1921$\times$ speedup over standard ACO. Moreover, the AdaIR method further improves TensorACO's convergence speed by 80% and solution quality by 2%. Source codes are available at https://github.com/EMI-Group/tensoraco.
• Abstract（参考訳）: Ant Colony Optimization (ACO)は、トラベルセールスマン問題の解決に有効であることで有名だが、CPUベースの環境、特に大規模インスタンスでは計算上の課題に直面している。 これに対し、GPUアクセラレーションの進歩を活用するために、Tensorized Ant Colony Optimization (TensorACO)を導入する。 中心となるものとして、TensorACO は ant 系と ant 経路を完全にテンソル形式に変換する。 アリシステムのテンソル化のために,確率遷移行列を計算して計算オーバーヘッドを削減する前処理法を提案する。 アントパスのテンソル化において,逐次経路更新の機構を並列行列演算に置き換えることで,フェロモン行列の更新を高速化するインデックスマッピング手法を提案する。 さらに,GPU上でのACOの選択機構の並列化という課題を克服するために,Adaptive Independent Roulette (AdaIR) 手法を導入する。 総合的な実験は、標準的なACOよりも1921$\times$スピードアップを達成するTensorACOの優れた性能を示す。 さらに、AdaIR法は、テンソルACOの収束速度を80%、溶液品質を2%改善する。 ソースコードはhttps://github.com/EMI-Group/tensoraco.comで入手できる。

関連論文リスト

• 3DGS-LM: Faster Gaussian-Splatting Optimization with Levenberg-Marquardt [65.25603275491544]
  3DGS-LM, 3D Gaussian Splatting(3DGS)の再構築を高速化する新しい手法を提案する。 提案手法は元の3DGSよりも30%高速で, 再現品質の最適化が可能である。
  論文  参考訳（メタデータ） (2024-09-19T16:31:44Z)
• GPU-accelerated Evolutionary Multiobjective Optimization Using Tensorized RVEA [13.319536515278191]
  本稿では,GPUアクセラレーションの進歩を活用するために,大規模な進化的参照ベクトルガイドアルゴリズム(TensorRVEA)を提案する。 大規模集団と問題次元を含む数値ベンチマークテストでは、RVEAは一貫して高い計算性能を示し、1000ドル以上のスピードアップを達成している。
  論文  参考訳（メタデータ） (2024-04-01T15:04:24Z)
• Stochastic Optimal Control Matching [53.156277491861985]
  最適制御のための新しい反復拡散最適化(IDO)技術である最適制御マッチング(SOCM)を導入する。 この制御は、一致するベクトル場に適合しようとすることで、最小二乗問題を通じて学習される。 実験により,本アルゴリズムは最適制御のための既存のすべての IDO 手法よりも低い誤差を実現する。
  論文  参考訳（メタデータ） (2023-12-04T16:49:43Z)
• ELRA: Exponential learning rate adaption gradient descent optimization method [83.88591755871734]
  我々は, 高速(指数率), ab initio(超自由)勾配に基づく適応法を提案する。 本手法の主な考え方は,状況認識による$alphaの適応である。 これは任意の次元 n の問題に適用でき、線型にしかスケールできない。
  論文  参考訳（メタデータ） (2023-09-12T14:36:13Z)
• Reduce Computational Complexity for Convolutional Layers by Skipping Zeros [9.833821501774596]
  本稿では,畳み込みニューラルネットワークの効率的なアルゴリズムを提案する。 C-K-SアルゴリズムにはGPUの効率的な実装が伴っている。 実験により、C-K-Sは速度と収束の点で優れた性能を示すことが示された。
  論文  参考訳（メタデータ） (2023-06-28T06:21:22Z)
• Optimized Sparse Matrix Operations for Reverse Mode Automatic Differentiation [3.72826300260966]
  本稿では,PyTorch のための CSR ベースのスパース行列ラッパーの実装について述べる。 また,結果のスパースカーネルを最適化に応用し,実装や性能測定の容易さを高密度カーネルと比較した。
  論文  参考訳（メタデータ） (2022-12-10T00:46:51Z)
• Efficient Dataset Distillation Using Random Feature Approximation [109.07737733329019]
  本稿では,ニューラルネットワークガウス過程(NNGP)カーネルのランダム特徴近似(RFA)を用いた新しいアルゴリズムを提案する。 我々のアルゴリズムは、KIP上で少なくとも100倍のスピードアップを提供し、1つのGPUで実行できる。 RFA蒸留 (RFAD) と呼ばれる本手法は, 大規模データセットの精度において, KIP や他のデータセット凝縮アルゴリズムと競合して動作する。
  論文  参考訳（メタデータ） (2022-10-21T15:56:13Z)
• Fast Differentiable Matrix Square Root and Inverse Square Root [65.67315418971688]
  微分可能な行列平方根と逆平方根を計算するためのより効率的な2つの変種を提案する。 前方伝搬には, Matrix Taylor Polynomial (MTP) を用いる方法と, Matrix Pad'e Approximants (MPA) を使用する方法がある。 一連の数値実験により、両方の手法がSVDやNSの繰り返しと比較してかなりスピードアップすることが示された。
  論文  参考訳（メタデータ） (2022-01-29T10:00:35Z)
• Boosting Ant Colony Optimization via Solution Prediction and Machine Learning [10.687150889251031]
  本稿では,機械学習(ML)とアリコロニー最適化(ACO)を組み合わせたメタヒューリスティック(ML-ACO)を導入し,最適化問題を解く。
  論文  参考訳（メタデータ） (2020-07-29T13:03:37Z)
• Balancing Rates and Variance via Adaptive Batch-Size for Stochastic Optimization Problems [120.21685755278509]
  本研究は,ステップサイズの減衰が正確な収束に必要であるという事実と,一定のステップサイズがエラーまでの時間でより速く学習するという事実のバランスをとることを目的とする。 ステップサイズのミニバッチを最初から修正するのではなく,パラメータを適応的に進化させることを提案する。
  論文  参考訳（メタデータ） (2020-07-02T16:02:02Z)
• Accelerating supply chains with Ant Colony Optimization across range of hardware solutions [0.0]
  本稿では,Ant Colony Optimization (ACO) を用いた実時間アウトバウンドサプライチェーン問題とその2つの並列ACOアーキテクチャによるスケーリングダイナミクスについて検討する。 Paは、並列インスタンスの数が増えるにつれて、より少ないイテレーションでより高いソリューション品質に達することができた。 SS-RouletteのようなACOベクトル化技術はC++と16コアCPUを用いて実装された。
  論文  参考訳（メタデータ） (2020-01-22T16:09:06Z)

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

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