상세정보
학술지
GPU-based Parallel Genetic Approach to Large-scale Travelling Salesman Problem
- 발행일
- 201611
- 출처
- Journal of Supercomputing, v.72 no.11, pp.4399-4414
- ISSN
- 0920-8542
- 출판사
- Springer
- 협약과제
- 16ZS1400, 듀얼모드 배치.쿼리 분석을 제공하는 빅데이터 플랫폼 핵심기술 개발, 원종호
- 초록
- The travelling salesman problem (TSP) is a well-known NP-hard problem. It is difficult to efficiently find the solution of TSP even with the large number of gene instances. Evolutionary approaches such as genetic algorithm have been widely applied to explore the huge search space of TSP. However, the feasibility constraints of TSP make it difficult to devise an effective crossover method. In this paper, we propose an improved constructive crossover for TSP. As the performance of graphics processing units (GPUs) rapidly improves, GPU-based acceleration is increasingly required for complex computation problems. Unfortunately, the constructive crossover methods cannot be easily implemented in a parallel fashion because each gene element of offspring is dependent on the previous element in the gene string. In this paper, we propose a more effective method with which large number of genes can evolve effectively by exploiting the parallel computing power of GPUs and an effective parallel approach to genetic TSP where crossover methods cannot be easily implemented in parallel fashion.