Enhanced Genetic Algorithm for Traveling Salesman Problem
Yuzhou Liu, Huayi Yin, Zebin Huang, Yihong Wu · 2024
Aiming at the challenges faced by genetic algorithms in solving the traveler’s problem, including the low quality of initialized population, slow convergence speed, and the tendency to fall into local optimal solutions, this paper proposes an Enhanced Genetic Algorithm for Traveling Salesman Problem (EGAT). The algorithm has the following four key improvements: (1) Improved greedy heuristic to initialize the population: this study introduces an improved greedy heuristic to initialize the population, which not only improves the quality of the initial solution, but also accelerates the convergence speed of the global search. (2) Introducing tournament selection mechanism: we adopt a tournament selection mechanism, in which a number of individuals are randomly selected to compete in order to select the one with the highest fitness. Compared with the traditional roulette wheel selection, this method effectively maintains the diversity of the population and avoids the algorithm from converging to the local optimal solution too early. (3) Application of Partial Matching Crossover operator: when generating offspring, the use of Partial Matching Crossover operator can retain the order information of the original paths, which greatly improves the quality of offspring. This design not only ensures the generation of legitimate paths, but also enhances the diversity among the offspring, which helps to explore the solution space more comprehensively.(4) Combination of diversified mutation strategy and 2-opt local search: a diversified mutation strategy is designed, including swap mutation, insertion mutation and inversion mutation. These variants enhance the exploratory nature of the search process while maintaining appropriate variant probabilities. The combination of local search techniques further optimizes the path quality.