CUDA-based Genetic Algorithm To Solve TSP Problem

Accompanied by the continuous development of computer technology oncomputer performance rising, prompting the computer’s processor on behalf of thegeneral-purpose processor developed in two directions toward the CPU on behalf ofthe dedicated processor and GPU, along with the rapid development of GPU, how touse the powerful GPU disease sexuality has become a new hot spot. This article is tostudy how to better play a role in large-scale parallel computing for CUDA goals, andtake this opportunity to continue based on how CUDA genetic algorithm to solve TSP(Traveling Salesman Problem Traveling Salesman Problem) study. Genetic Algorithm(Genetic Algorithm) is a replica of the biosphere Darwin’s "survival of the fittest,survival of the fittest" laws of nature, learn from and evolved out of a random searchmethod. Although genetic algorithm can handle close to reality in many areas, but thegenetic algorithm has its limitations, of which the most important restrictions ongenetic algorithm is a matter of time, especially in the face of some of the tasksexceptionally huge problem. This is a genetic algorithm needed to face solve, while inthe CUDA parallel the help, the most serious problems can be effectively alleviate.The main function and contribution of this article is as follows:First of all, analysis of the shortcomings of the genetic algorithm, and thus theadvantages of parallel genetic algorithm. CUDA parallel genetic algorithm, to design aCUDA-based coarse-grained parallel genetic algorithm, a definite improvement on thepenalty function.Second CPU-based environment using genetic algorithm to solve TSP program,followed by the NVIDIA CUDA platform developed with the problem of parallel. Themain steps: first, the TSP problem initialization and the population of the entire geneticalgorithm is divided into a number of small populations. Second, the small populationof each partition on the GPU stream processors and let these small populations in thescreening of the operation of the genetic algorithm operator to optimize thisgeneration from the various stream processing the best individual and returns theCPU, the CPU compared comparison, this generation than the best individual. Then the individual pass reflow processor to continue the algorithm to optimize offspringfitness to maintain the required algebra is not a big change or termination algebra isreached the end.Finally, by comparison test in the CPU and GPU+CPU environment, can befound along with the increase in the number of cities, the best solution for theexperimental and the optimal solution will have some differences, but a smaller range,with the GPU performance enhance accuracy minor upgrade. By comparing theexperimental GPU parallel after time performance has greatly improved, which has animportant significance to alleviate the TSP spend time.