CUDA GPUを用いた並列GAによる巡回セールスマン問題の解法

カテゴリ: 部門大会

論文No: TC13-8

グループ名: 【C】平成22年電気学会電子・情報・システム部門大会講演論文集

発行日: 2010/09/02

タイトル(英語): A Parallel GA to solve TSP on the CUDA Architecture

著者名: 藤本 典幸(大阪府立大学),筒井 茂義(阪南大学)

著者名(英語): Noriyuki Fujimoto(Osaka Prefecture University),Shigeyoshi Tsutsui(Hannan University)

キーワード: 遺伝的アルゴリズム|並列処理|GPU|CUDA|genetic algorithm|parallel processing|GPU|CUDA

要約(日本語): 本論文はCUDA対応GPUを用いて巡回セールスマン問題を解く手法を提案する.提案手法は交叉としてOX,局所探索として2-optを用いる遺伝的アルゴリズムを特にCUDA向けに高並列化したものである.TSPLIBベンチマーク問題に対してNVIDIA GeForce GTX285を用いて評価実験をしたところ,3.0 GHz Intel Core2 Duo E6850 CPUに対して最大24.2倍の速度向上が見られた.

PDFファイルサイズ: 3,163 Kバイト