摘要
NP hard problems have appeared in many areas. In this article, it is discussed how to solve this kind of problems using artificial neural network— Hopfield/Tank model, especially the Travelling Salesman Problem (TSP). At first, a stability analysis shows the conditions of the model to converge to the vertices of the hypercube and its relation with the parameters. And then, a HT model for solving TSP is formulated. Some theorems are given to analyze the influence of parameter D on the three subspaces of the connection matrix in which D is set to zero. Based on these analyses, a dynamic analysis of the model is given and a set of parameters′ rules are established. It is indicated that, if the parameters are selected according to these rules, the final solutions are optimal or near optimal. However, the initial noise would have some influences on the final solutions. According to these theories, a 'damping' optimal method is proposed which can not only guarantee the final solutions are high quality, but also weaken the influence of the initial noise. On the other hand, many kinds of modified HT models are summarized and a more simple and effective model is given. Compared with some traditional and modern methods for solving TSP, the performance of our method is very good. Linking with the practice, some applications are exploited. Our method has also been used for programming the posts route of some city in China. Finally, a theoretical analysis is given for com munication network routing problem using HT model. Liu Rong Born in October 1966. He received the Engineering Ph.D in Beijing University Posts and Telecommunications in April 1994.
NP hard problems have appeared in many areas. In this article, it is discussed how to solve this kind of problems using artificial neural network— Hopfield/Tank model, especially the Travelling Salesman Problem (TSP). At first, a stability analysis shows the conditions of the model to converge to the vertices of the hypercube and its relation with the parameters. And then, a HT model for solving TSP is formulated. Some theorems are given to analyze the influence of parameter D on the three subspaces of the connection matrix in which D is set to zero. Based on these analyses, a dynamic analysis of the model is given and a set of parameters′ rules are established. It is indicated that, if the parameters are selected according to these rules, the final solutions are optimal or near optimal. However, the initial noise would have some influences on the final solutions. According to these theories, a 'damping' optimal method is proposed which can not only guarantee the final solutions are high quality, but also weaken the influence of the initial noise. On the other hand, many kinds of modified HT models are summarized and a more simple and effective model is given. Compared with some traditional and modern methods for solving TSP, the performance of our method is very good. Linking with the practice, some applications are exploited. Our method has also been used for programming the posts route of some city in China. Finally, a theoretical analysis is given for com munication network routing problem using HT model. Liu Rong Born in October 1966. He received the Engineering Ph.D in Beijing University Posts and Telecommunications in April 1994.
