1.1目的及意义

旅行销售员问题（简称TSP），亦称为邮递员路径问题，是组合优化领域中的一个经典问题，它可描述为：平面上有N个城市，一个旅行商欲遍历所有城市且每个城市仅能访问一次并最后回到起始点，则按照怎样的遍历顺序，回路长度才最短。虽然该问题模型简单，求解却很困难，并且已经被证明是NP完全问题。但它确实广泛存在，且是诸多领域内出现的多种复杂问题的集中概括和简化形式。因此提出一种有效地解决TSP问题的算法有着重要的理论意义和实际应用价值。在理论上，只要有足够的时间和计算能力,任何规模的TSP问题都可以得到解决。在城市数较少的情况下可以用枚举等方法, 但如果城市数量较大时,使用枚举法求解就要考虑的情况是数量级，计算量之大是不可想象的，且对于实际应用，往往只要求在时间允许的条件下给出尽可能好的解。因而需要有效的较优解而非最优解算法,神经网络就是一种有效的近似求解算法。

“人工神经网络”（ Artificial Neural Network ，即 ANN ）或“神经网络”是指用大量的简单计算单元（即神经元）构成的非线性系统，是 20世纪 80 年代以来人工智能领域兴起的研究热点。它在一定程度和层次上模仿了人脑神经系统的信息处理、存储及检索功能，所以其具有了学习、记忆和计算等一系列智能处理功能。神经网络具有一些十分显著的特点：具有非线性映射能力；不需要精确的数学模型；擅长从输入输出数据中学习有用知识；容易实现并行计算；由于神经网络由大量简单计算单元组成，因而易于用软硬件实现。最近十多年来，人工神经网络的研究工作不断深入，已经取得了很大的进展，其在模式识别、智能机器人、自动控制、预测估计、生物、医学、经济等领域已成功地解决了许多复杂的实际问题，表现出了良好的智能特性。人工神经网络作为对自然界生物进化、人脑的思维结构和思维方式进行模拟抽象的仿真过程，提出了各种不同的算法模型，典型的如 BP 网络、ART 网络、Hopfield 网络、自组织特征映射网络、BAM 网络等。其中, Hopfield 神经网络( 简称 HNN)是一种被广泛应用于解决组合优化问题的人工神经网络模型。将 Hopfield 网络应用于求解组合优化问题, 把目标函数转化为网络的能量函数, 把问题的变量对应到网络的状态。这样, 当网络的能量函数收敛于极小值时, 问题的最优解也随之求出。由于神经网络是并行计算的, 其计算量不随维数的增加而发生指数性“爆炸”, 因而对于优化问题的高速计算特别有效。

1.2国内外研究现状

TSP问题一直是组合优化问题中极富活力的研究课题之一。从最初的研究TSP的离散模型到现在，几代组合学数学家和运筹家对这个问题进行了广泛而且深入的研究，并取得了很大的成就。

目前来说世界上研究TSP主要遇到的瓶颈问题就是如何避免陷入局部最优以及计算效率的问题。为了解决这些问题，20世纪90年代起，一些更新的思想和算法逐渐形成。由群居性昆虫行为特性获得灵感的蚂蚁算法（又称蚁群算法）是目前研究的热点；又如由混沌现象受启发的一系列新尝试；将混沌机制和启发式搜索方法、人工神经网络、模拟退火等相交叉结合，建立更多优质高效的算法来提高算法的计算效率和对全局最优点的获取能力。

美国加州工学院物理学家Hopfield于1982年和1984年分别提出了两种神经元网络模型,简称为HNN,一种是离散的随机模型,一种是确定论模型。HNN模型是目前得到最充分研究和广泛应用的反馈式神经元网络模型。Hopfield把“能量函数”(也称李雅普诺夫函数)的概念引入分析一类人工神经元网络稳定过程,使网络运行的稳定性判断有了可靠和简便的判据。这一神经网络算法在1985年被Hopfield和Tank提出用于TSP问题求解，后来研究学者们也对Hopfield算法解决TSP问题进行了进一步的改进。

2. 研究的基本内容与方案

2.1研究内容

(1)界定TSP问题，阐述TSP问题研究现状