Mixing genetic algorithm for traveling salesman problem, The

2022 Spring.Includes bibliographical references.The Traveling Salesman Problem (TSP) is one of the most intensively studied NP-Hard problems. The TSP solvers are well-suited for multi-core CPU-based architectures. With the decline in Moore's law, there is an increasing need to port the codes to parallel architectures such as the GPU massively. This thesis focuses on the Genetic Algorithm (GA) based TSP solvers. The major drawback in porting the state-of-the-art GA based TSP solver (called the Edge Assembly Crossover (EAX)) are (a) the memory per crossover operation is large and limits the scalability of the solver (b) the communication per crossover operation is random and not favorable for the SIMD machines. We designed a new solver, the Mixing Genetic Algorithm (MGA), using the Generalized Partition Crossover (GPX) operator to overcome these aspects. The GPX consumes 4 x lesser memory and does not access the memory during crossover operation. The MGA is used in three different modes. (1) MGA can converge fast on problems smaller than 2,000 cities as a single solver. (2) As a hybrid solver, together with EAX, it speeds up the convergence rate for problems up to 85,900 cities. (3) In an ensemble setting, together with EAX and an iterated local search (called the Lin-Kernighan Helsgaun (LKH) heuristic), it increases the success rate of some of the hard TSP instances. The MGA is parallelized on shared memory (using OpenMP), distributed memory (using MPI), and GPU (using CUDA). A combination of OpenMP and MPI parallelization is examined on problems ranging between 5,000 to 85,900 cities. We show near-linear speedup (proportional to the number of parallel units) on these instances. Preliminary results on GPU parallelization of the GPX crossover operator partition phase show a 48x to 625x speedup over the naive sequential implementation. This is the first step towards the fine-grain parallelization of GA operators for TSP. The results are tested on problems ranging from 10,000 to 2M cities