Hybrid Evolution Algorithm To Solve The Problem Of Super Large Scale Traveling Salesman Problem

The traveling salesman problem is a famous NP-hard problem.The earliest descriThe traveling salesman problem is a famous NP-hard problem.The earliest description was the Cavalier tour problem in Euler's study in 1759.Its problem was described as the 64 squares in chess,64 squares once and only once,and finally back to the starting point.In 1954,some scholars used linear programming to solve the traveling salesman problem,thus making a historic breakthrough-solving the problems of the tour of the 49 cities in the United States.Later,some scholars put forward a method called branch and bound method.But when solving the medium scale or super large scale TSP problem,the approximate algorithm can not obtain the high precision optimal solution(or the suboptimal solution)in solving the problem,but the intelligent algorithm can obtain the accuracy higher than the approximate algorithm,but the problem of local optimal value and the different optimization strategies are adopted.It is difficult to obtain different solutions in a reasonable time.The problem of traveling salesman on any scale will be of great significance to all fields,because the traveling salesman problem itself has important practical significance and engineering background.Based on the above problems,it is found that the global optimization idea of genetic algorithm is very efficient in solving the problem of large scale traveler,but it is difficult to overcome three problems when solving the problem.First of all,if the initial solution accuracy is not enough,we can not get a better solution in a reasonable time because of the convergence speed.And because of the large scale traveling salesman problem,the city point can only use the local search strategy,and the search radius has no uniform standard at present.Most of the random algorithms are adopted,and the same optimization position is also adopted at present,which will lead to the excessive dependence probability of the algorithm.Based on the above three problems,the improved convex hull algorithm is first adopted in this paper.By optimizing the convex hull interpolation method,the obtained solution is closer to the optimal solution.This method has strong robustness in solving small traveling salesman problem or in creating medium scale and super large scale initial population.The experiment proves that in the process of local optimization of genetic algorithm,the priority optimization area can get the optimal solution of higher probability and improve the efficiency and accuracy of the algorithm.This paper obtains the simulation experiment data by solving the data in the TSP case base.The experimental data show that the hybrid algorithm is better in efficiency and precision in solving the problem of super large scale traveling salesman problem.