An Improved Genetic Algorithm for Solving TSP by Optimizing Crossover and Worst Mutation

Abstract

To the traditional genetic algorithm in solving the TSP problem, there are three main problems: first, all genes participate in roulette mode, there will be cross gene random selection, discard the optimal solution, slow convergence; second, the worst gene is easy to be eliminated, easy to lead to the local optimal region, but the worst gene may jump out of the local optimal region, and find the optimal solution in a new region; finally Many related literature have not given the range of crossover rate and mutation rate of genetic algorithm in solving TSP problem, but the values of these two parameters have great influence on the convergence. Aiming at the above three problems, this paper proposes an improved genetic algorithm based on population optimization crossover and worst gene mutation. The main idea of the improved algorithm is: first, the genes of each generation are sorted according to their advantages and disadvantages, and the excellent genes are paired and crossed with each other; secondly, the worst genes produced by the last round of iteration are selected and mutated directly and enter the next generation; finally, since there is no clear theory as the basis for determining the value of crossover rate and mutation rate, several data samples are used for experiment, and the results are used as the basis of the values of two parameters. Finally, the improved genetic algorithm is implemented by coding and tested with eil51 general sample data to verify the superiority and effectiveness of the improved genetic algorithm.