Application And Research Of Improved Genetic Algorithm In TSP Problem

Traveling salesman problem is a classic combinatorial optimization problems.With the rapid growth of city clusters size,the traveling salesman problem in search space becomes more and more difficult to find the optimal solution.At the same time,the improved algorithm is too redundant more negative impact to the program.Therefore,many scholars look for genetic algorithm,which is an efficient and convenient computing framework.Genetic algorithm has the advantage of global search to deal with traveling salesman problem,which is the complete problem.But its local search ability is insufficient and convergence speed is slow.In traditional precise algorithm,they are mostly local search algorithm,it usually get local optimal solution.For limited city,it can accurately calculate the approximate solution.Therefore,genetic algorithm is combined with traditional algorithm into a hybrid algorithm to achieve complementary advantages.In addition,it also has improvement with related strategies to improve the performance of genetic algorithm.In the improved algorithm,few scholars put forward the information preprocessing based on city to overcome those problems.Someone puts forward hybrid algorithm based on k-means clustering algorithm in data mining algorithm and genetic algorithm.Clustering algorithm at the expense of the time to improve the processing capacity of genetic algorithm.In this article,the traditional genetic algorithm is used to solve two key problems of the traveling salesman problem.It take a direct simple way to have the regional grid of the regional grid.It handles city information to improve path coding with dividing cities.Improved genetic algorithm make the original urban agglomeration coordinate data according the original urban agglomeration coordinate data according for data preprocessing.It can achieve the goal of map compression and extract useful information.The improved genetic algorithm based on the data preprocessing of domain rules puts forward a coding for traditional paths and improve the operators of genetic algorithm.The improved genetic algorithm of data preprocessing based on the characteristics of map regionalization to divide the cities.It uses local excellent gene block in advance,then combined with the overall to finish the initialization phase.At the same time,there must be adjacent area in the division,and then have the influence of the position and the probability of the operator.Then,The improved genetic algorithm based on the result information of the data preprocessing improves the initial population operator and selection,crossover and mutation operator.Because the similar clustering algorithm is compared with the hybrid algorithm of data mining algorithm,which becomes simple in early stage.The research results show that the realization of the urban data preprocessing and the strategy of the domain rules can improve the convergence speed and accuracy of genetic algorithm.