A GPU Accelerated Parallel Genetic Algorithm for the Traveling Salesman Problem

Abstract

This research delves into the correlation between computational runtime and problem-solving efficacy within the realm of the Traveling Salesman Problem (TSP). Despite its classification as NP-Hard, various Algorithms such as the Genetic Algorithm (GA) have been proposed. Nevertheless, with the increasing complexity of the problem, constraints on runtime become apparent. To address this issue, it is recommended to employ a parallelized genetic algorithm and investigate the effects of block size configuration to facilitate efficient execution on GPU for improved speedup while maintaining solution quality. The results of the experiments demonstrate significant improvements in processing times, with the parallel-enhanced GA achieving an average processing time of 0.7 using the gr120 dataset and a population size of 2048, as opposed to the average processing time of the sequential approach.