A Look at the application and effectiveness of CUDA programming applied to precedence-constrained TSP using a genetic algorithm meta-heuristic.

摘要

In this thesis, we explore the potential promise of parallel computing on a graphic processing unit (GPU) using the CUDA parallel computing platform and programming model for parallel metaheuristics for combinatorial optimization problems. Our test problem and metaheuristic is the quintessential NP-Hard problem, the Traveling Salesman Problem (TSP), and commonly used genetic algorithm. The specific TSP variant explored is the precedence constrained TSP. Our problem and the heuristic employed are intended to provide a way to explore the potential of this parallel computing platform.