徳島大学 教育・研究者情報データベース(EDB)

1. (英) Terao Keiichiro / (日) 寺尾 圭一郎 / (読) てらお けいいちろう

   役割	任意
   貢献度	任意
   学籍番号	推奨	****

2. 小野 典彦

   役割	任意
   貢献度	任意
   学籍番号	推奨

3. 永田 裕一([徳島大学.大学院社会産業理工学研究部.理工学域.知能情報系.情報工学分野]/[徳島大学.理工学部.理工学科.知能情報コース.情報工学講座])

   役割	任意
   貢献度	任意
   学籍番号	推奨

(英) Parallelization of GA-EAX using Identical Population in all Processes

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

(英) 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.

1. (英) traveling salesman problem
2. (英) genetic algorithm
3. (英) EAX
4. (英) parallel computing

1. 永田 裕一([徳島大学.大学院社会産業理工学研究部.理工学域.知能情報系.情報工学分野]/[徳島大学.理工学部.理工学科.知能情報コース.情報工学講座])