An improved genetic algorithm for solving TSP problem
Guangxi Chen · Journal of Guilin University of Electronic Technology · 2007
Traveling Salesman Problem(TSP) is a typical NP-Complete problem.Genetic Algorithm(GA)is a global optimal searching algorithm based on the biological evolutionism.GA is a method for solving this problem,it is hard for it to find global optimization quickly and prevent premature convergence.In response to this problem,a novel genetic algorithm is proposed in this paper,which is based on the feature of the optimum of TSP and comprises the minimal line of the city.Greedy two points insertion mutation operator is proposed and the heuristic crossover operator is improved.The mutation probability of the units is given by its suit-function value.Comparing with the mean of the group's suit-function value.In order to improve the convergence speed,local optimized search is used to enhance the ability of the initial group.The improved algorithm can avoid the local optimum by local adjustment.The experimental result based on the improved GA indicates that the improved GA has a better convergence property and can induce the optimal results.Its testing results are as good or even superior in comparison with TSPLIB.