一种基于聚类技术的Hopfield网络求解TSP方法

An Approach for Solving TSP by Hopfield Network Based on Clustering Technology

Hopfiled神经网络方法已被广泛用于求解旅行商问题(TSP),但对于解中规模和大规模的TSP,存在效果不理想甚至难以求解的问题。为了较好地解决这个问题,该文提出一种K-M eans聚类算法与Hopfie ld网络方法相结合求解TSP的新方法,先应用聚类算法对所给城市进行聚类以获得几组规模较小的城市,然后对每一组城市应用Hopfie ld网络方法进行求解,最后把求解后的每组城市连接起来。计算机仿真结果表明,该方法可以获得最优有效解,并且解的质量明显提高,对求解中大规模的TSP比较有效。

Hopfield network has been widely used for solving TSP, but it is difficult to solve medium or large scale TSP. An approach for solving medium or large scale TSP by Hopfield network based on clustering technology is presented. A K - Means algorithm has been applied to raw data, and the cities are classified into predefined classes, Hopfield networks can be applied to each of these groups. At last, we connect these groups being solved by Hopfield networks. Computer simulations show that optimal solution can be obtained using this method and the tour quality is enhanced. This method is valid for solving medium or large scale TSP.