全プロセスによる同一集団を維持したGA-EAXの並列化
書誌事項
- タイトル別名
-
- 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.
収録刊行物
-
- 進化計算学会論文誌
-
進化計算学会論文誌 8 (3), 100-110, 2018
進化計算学会
- Tweet
詳細情報 詳細情報について
-
- CRID
- 1390001205364382848
-
- NII論文ID
- 130006668421
-
- ISSN
- 21857385
-
- 本文言語コード
- ja
-
- データソース種別
-
- JaLC
- CiNii Articles
- KAKEN
-
- 抄録ライセンスフラグ
- 使用不可