Parallel genetic algorithm for Travelling Salesman Problem
Chuyue Peng · 2022
Travelling Salesman Problem (TSP) returns the minimal length of traveling distance to travel through all the cities given by the data set and returning to the starting position, which allows the users to optimize their travel path to minimize total cost. Genetic algorithm (GA) is used to solve the problem due to its efficiency. However, as the sample size increases, the runtime of GA for TSP increases significantly. This paper introduces three new parallel GA (PGA) – Master-Slave model, Coarse-Grained model, and Combined PGA (MSCG)–to solve TSP to optimize performance and minimize runtime. The first two performs parallelization on a different level and Combined PGA is the combination of Master-Slave and Coarse- Grained models. The Master-slave model paralyzes the evolution process and divides the population into threads to enter the calculation. Coarse-grained separates the population even earlier, so before entering evolution, the populations are already divided into subsets. MSCG separates populations both before and after entering evolution to get the advantages of both approaches. To verify the effectiveness of the three proposed methods, we compare them with the non-parallelized GA. The results show that the master-slave method generally would produce on average 10% shorter route than the coarsegrained method but would have on average 40% higher time usage.