文献

J-GLOBAL ID：202002218247069605   整理番号：20A0648231

GPUベースの並列max-min Antシステムの実装【JST・京大機械翻訳】

Implementing a GPU-based parallel MAX-MIN Ant System

著者 (1件)： Skinderowicz Rafal (University of Silesia in Katowice, Faculty of Science and Technology, Bedzinska 39, 41-205 Sosnowiec, Poland)
資料名： Future Generation Computer Systems  (Future Generation Computer Systems)
巻： 106  ページ： 277-295  発行年： 2020年 
JST資料番号： A0620C  ISSN： 0167-739X  資料種別： 逐次刊行物 (A)
記事区分： 原著論文  発行国： オランダ (NLD)  言語： 英語 (EN)

抄録/ポイント： MAX-MIN Ant System(MMAS)は,多くの困難な組合せ最適化問題に対する満足な解を見出すのに効率的であることが証明されている最も良く知られたアントコロニー最適化(ACO)アルゴリズムの一つである。Mooreの法則におけるスローダウンと高速で汎用計算を行うことができるグラフィックス処理ユニット(GPU)の利用可能性は,GPUベースのACO実装の開発にかなりの研究努力を払った。本論文では,GPUに基づく並列MMAS実装を改善するための新しいアイデアの範囲を検討し,2つのその後のNvidia GPUアーキテクチャにより提供される計算電力をより良く利用することを可能にした。具体的には,重み付き貯留層サンプリングアルゴリズムに基づいて,MMASと他のACOアルゴリズムの心臓にあるノード選択手順の新しい並列実装を提案した。また,ACOのソリューション構築段階で使用される別のキーコンポーネント,タブーリスト構造のメモリ効率的実装も示した。提案された実装は,既存のアプローチと組み合わせて,合計6つのMMAS変種をもたらし,それは198から3795の都市にわたる巡回セールスマン問題(TSP)事例の集合に関して評価される。結果は,著者らのMMAS実装が最先端のGPUベースとマルチコアCPUベースの並列ACO実装と競合することを示した。実際に,Nvidia V100 Volta GPUのために得られた時間は,それぞれ7.18xと21.79xより小さかった。提案したMMAS変種の最速は,1002都市の事例を解くとき,第2に100万以上の候補解を生成することができる。さらに,2-opt局所探索発見と組み合わせて,提案した並列MMASが,18512ノードまでのTSPインスタンスに対する高品質解を見出すことを示した。Copyright 2020 Elsevier B.V., Amsterdam. All rights reserved. Translated from English into Japanese by JST.【JST・京大機械翻訳】

シソーラス用語： 心臓 ,  電力 ,  計算機アーキテクチャ ,  都市 ,  近傍探索法 ,  組合せ最適化問題 ,  巡回セールスマン問題 ,  *アルゴリズム
準シソーラス用語： マルチコアプロセッサ ,  並列実装 ,  貯留層 ,  GPU【プロセッサ】 ,  Mooreの法則 ,  アリコロニー最適化 , 【Automatic Indexing@JST】

著者キーワード (5件)： 並列max-min Antシステム ,  加重貯留層サンプリング ,  アリコロニー最適化 ,  GPU ,  CUDA

分類 (3件)： 専用演算制御装置  (JC04030Y) ,  人工知能  (JE08000Z) ,  オペレーティングシステム  (JD03020J)

タイトルに関連する用語 (3件)： GPU ,  Max ,  実装