A Variant of Parallel-Hybrid Genetic Algorithm for Large-Scale Traveling Salesman Problem

This research proposes a low-complexity parallel-hybrid genetic algorithm evolved in an island model to solve large instances of the traveling salesman problem. In order to increase the diversity of individuals among the islands, a variant of the 2-opt algorithm called Rnd2-opt is implemented in the first half of the islands and another variant called NN2-opt in the second half. Additionally, it incorporates a process known as the edge assembling crossover operator (EAX), along with the local search method 2-opt, to generate offspring. The resulting algorithm is implemented using an island model on a multicore processor, utilizing the POSIX thread standard. During each generation, a predefined quantity of offspring is generated from each individual. The best-quality offspring is then selected to replace the parent individual if it is superior. For individual migration, the best individual from one island is chosen to replace the worst individual from another island, employing a ring topology. The PhGA algorithm was applied in VLSI and Art TSP large instances. VLSI TSP instances have a smaller number of cities than Art TSP instances; however, their error rate is higher than Art TSP instances, both in generating the initial population and applying the EAX operator with local search. This is because VLSI instances contain cities that are arranged in a lattice pattern, and finding the best route is more difficult due to the existence of many alternative routes to the best solution.