Improved Genetic Algorithm for TSP
Wei Yan · Journal of Chongqing Institute of Technology · 2007
Traveling Salesman Problem(TSP) is a classical combinatorial optimization problem.Genetic algorithm(GA) is a method for solving this problem.But it is hard for GA to find global optimization quickly and prevent premature convergence.Considering the characteristic of TSP,this paper puts forward an improved genetic algorithm,that is,using greedy strategy to initialize species,using 2-opt operator to optimize it so that the initialized individuals contain optimized paths,which quickens the convergence of the algorithm to some degree and protects prematurity and close relative reproduction.After improving cross operator and mutation operator,the diversity of population and most of the good performance of last generation can be maintained.And the improved algorithm is used to solve TSP problem in 20 cities and the experimental result indicates that the algorithm is fast and has good solutions.