Authors: Semin Kang SungSoo Kim Jongho Won YoungMin Kang
Publish Date: 2016/05/23
Volume: 72, Issue: 11, Pages: 4399-4414
Abstract
The travelling salesman problem TSP is a wellknown NPhard 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 GPUbased 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
Keywords: