论文部分内容阅读
TSP问题一直是组合优化中极富活力的研究课题之一。七十年代中期，计算复杂性理论的出现和数学规划的发展大大推动了组合优化的前进。计算复杂性理论表明，被称作NP完全问题的旅行推销员问题以及其它类似的组合优化问题在计算上是等价的。也就是说，不能用任何已知的多项式算法求解这种问题。从这个新发现可以看出：最优化方法的能力是有限的，这使得研究人员不得不寻求更好的解决办法。 神经网络的发展为这一问题的解决提供了一种新的思路。Hopfield神经网络算法是解决这一问题的经典算法，这一算法最初具有的不足之处也得到了不断的改进。 本文所做的工作： ● 给出了TSP问题的描述及数学模型 ● 介绍了神经网络应用于TSP问题的相关理论知识 ● Hopfield算法在求解TSP问题中的应用分析 ● 在已有的改进算法基础上，对Hopfield算法进一步改进 ● 提出了大规模TSP问题的基于分层聚类思想的解决方案 本文的创新之处： ● 分析了Hopfield神经网络算法解决TSP问题的理论过程，在已有改进算法的基础上，提出了新的改进，使得构造神经网络的神经元数目由n~2个减少到(n-1)~2个，简化了网络结构，提高了算法效率，对于神经网络的硬件实现有重要的意义； ● 提出采用分层聚类的方法来解决大规模TSP问题的方案。基本思想是利用聚类神经网络先把地理位置上相互靠近的城市划分为一个集体单位(一个物理区域)，用改进的Hopfield神经网络算法求解各个区域间的最优(或近似最优)路径，然后再在每一个区域内部用同样的方法来求解其局部的最优(或近似最优)路径，这样可以最终得到全局的最优(或近似最优)解。描述如下： 设有城市集合S，按城市的地理位置把S划分为若干子 摘要－2－ 集，得S＝IjS，，其中＊厂S；＝d，i一 口 求得集合 I叫 S－｛s；］i习，2，…n｝的 TSP最优路径，再依次求得子集s；内部 的TSP 最 优 路 径，即 得 最 终 优 化 路 径 M 一）S 一）…一宁S；DI．I．K三＊。二…·．厂I．l一7一厂）。 ＼”I”“］””“k“3J3’”“＼“3“9 9‘“IS“”J”‘“j“ 这一思想的具体实现可以使得神经网络有效地用于大规 模TSP问题的求解，同时也为用神经网络解决其它大规模组 合优化问题提供了一种可参考的思路。