Parallelization of GA-EAX using Identical Population in all Processes

DOI
  • Terao Keiichiro
    Graduate School of Advanced Technology and Science, Tokushima University
  • Ono Norihiko
    Graduate School of Technology, Industrial and Social Sciences, Tokushima University
  • Nagata Yuichi
    Graduate School of Technology, Industrial and Social Sciences, Tokushima University

Bibliographic Information

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

Description

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.

Journal

Related Projects

See more

Keywords

Details 詳細情報について

  • CRID
    1390001205364382848
  • NII Article ID
    130006668421
  • DOI
    10.11394/tjpnsec.8.100
  • ISSN
    21857385
  • Text Lang
    ja
  • Data Source
    • JaLC
    • CiNii Articles
    • KAKEN
  • Abstract License Flag
    Disallowed

Report a problem

Back to top