The Study Of Neural Network Applied In The Travelling Salesman Problem

The travelling salesman problem (TSP) is always one of the most interesting topic in combinatorial majorizationo In the middle seventies, the appearance of the complexity theory of calculation and the development of mathematical programming have greatly improved the advancement of combinatorial majorization. The complexity theory of calculation has proved that the so-called problem of NP and other similar problems are equal in calculating. That is to say, we can not use any polynomial algorithm to solve this kind of problems. From this new discovery we find that the ability of optimization method is limited and this makes it necessary for the researches to find out better solutions.The development of neural network offers a new solution to this problem. Hopfield neural network (HNN) algorithm is a typical one in solving this problem, and the early shortcomings of this solution have been greatly improved.A general introduction to the thesis:A description of TSP and it's mathematical modelAn introduction of the theories of neural network applied to the TSPAn applicative analysis of HNN in solving the TSPThe improvement of HNNThe presentation of the solutions of large scale TSP based on the idea of sortingThe innovations of this thesis:The analysis of the theoretical process of HNN in solving the TSP problem, the new improvment of HNN on the basis of early improvement,which makes the number of neural reduce fromn2 to (n-1)2 ,and Amplifies the architecture of neuralnetwork ,also improves the efficiency. This has great significance in realizing hardware of the neural network.The presentation of the idea of sorting based on delamination in solving large scale TSP. The basic thought is to divide the cities which are close to each other into a group (physical area) by applying sorting neural network, find out the optimal path by the improved HNN, and then calculate the local optimal path by using the same method, and finally get the whole optimal path, which are described as following:A assembly S of cities is grouped into some subsetsaccording to their physical location and we can get,And then get the optimal, path of TSP ofS = {s, i = 1,2, n} through the given method,as well as the st.So we can get the ultimate optimal path:The realization of this idea may make neural network be widely applied in the solving of large scale tsp problem,and provide a referable way of resolving other large scale combination optimal problem by neural network.