全プロセスによる同一集団を維持したGA-EAXの並列化

DOI
  • 寺尾 圭一郎
    徳島大学大学院先端技術科学教育部システム創生工学専攻
  • 小野 典彦
    徳島大学大学院大学院社会産業理工学研究部
  • 永田 裕一
    徳島大学大学院大学院社会産業理工学研究部

書誌事項

タイトル別名
  • Parallelization of GA-EAX using Identical Population in all Processes

説明

One of the most powerful approximation solution methods for the traveling salesman problem (TSP) is a genetic algorithm using edge assembly crossover (GA-EAX), which has found best-known tours to several 100 thousand points scale TSP instances. However, due to the nature of multi-point search, in many cases GAs take more computation time than local search-based algorithms, and it is difficult to fully exercise the capability of GA-EAX for very large TSP instances having more than 1 million points within a reasonable computation time. In this research, we introduce a MPI parallel implementation of GA-EAX. However, in a naive master slave method, the communication costs between the processes are too high to obtain the effect of parallelization sufficiently. So, we introduce a method to reduce the amount of communication between processes to avoid this problem. We also introduce a MPI/thread hybrid parallel implementation of GA-EAX where each MPI process is executed using multiple threads. Experimental results show that the hybrid parallel model achieved up to 29.4 times speedup using 16 PCs, each with 4 cores.

収録刊行物

関連プロジェクト

もっと見る

詳細情報 詳細情報について

  • CRID
    1390001205364382848
  • NII論文ID
    130006668421
  • DOI
    10.11394/tjpnsec.8.100
  • ISSN
    21857385
  • 本文言語コード
    ja
  • データソース種別
    • JaLC
    • CiNii Articles
    • KAKEN
  • 抄録ライセンスフラグ
    使用不可

問題の指摘

ページトップへ