BROWSE
Detail
Journal Article
GPU-based Parallel Genetic Approach to Large-scale Travelling Salesman Problem
Cited 16 time in 
Share 
Share
- Authors
- Semin Kang, Sung-Soo Kim, Jongho Won, Young-Min Kang
- Issue Date
- 2016-11
- Citation
- Journal of Supercomputing, v.72, no.11, pp.4399-4414
- ISSN
- 0920-8542
- Publisher
- Springer
- Language
- English
- Type
- Journal Article
- Abstract
- 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.
- KSP Keywords
- Complex Computation, Computing power, GPU-based acceleration, Genetic Approach, NP-Hard problem, Parallel approach, Parallel computing, Search Space, Travelling salesman problem(TSP), genetic algorithms(NSGA II), graphics processing units(GPUs)