神经网络及其在TSP问题中的应用摘要：TSP问题一直是组合优化中极富活力的研究课题之一。

神经网络的发展为这一问题的解决提供了一种新的思路。

1985年Hopfield和Tank两人用CHNN网络为解决TSP难题开辟了一条崭新的途径并获得了巨大成功。

本文介绍了神经网络的基本知识，给出了TSP 问题的描述及数学模型，介绍了神经网络应用于TSP问题的相关理论知识及Hopfield算法在求解TSP问题中的应用分析.关键词：TSP问题；人工神经元网络；最优路径；Hopfield神经网络；The Application Of Neural Network In The Travelling SalesmanProblemWang XinCollege of Aeronautical Engineering，Civil Aviation University of China 1401001Abstract:The travelling salesman Problem (TSP) is always one of the most vigorous research topics in combined optimization . The development of neural network provided a newway to solve the problem. In 1985 Hopfield and Tank open up a new way for solving the TSPproblem by using CHNN and gained great success. This paper will introduce the basic knowledge of neural networks, describe the travelling salesman Problem and its mathematical model. In this paper, the neural network application knowledge in TSP and the related theoretical knowledge is given . Moreover, the paper will talk about the application of Hopfield algorithm analysis insolving TSP problem.Keywords:TSP , artificial neural network ,optimal path ,Hopfield neural network;自20世纪40年代出现以来，人工神经网络的发展虽不是一帆风顺但始终被人们寄予厚望。

因为在智能的，模糊的，随机的信息处理方面，人工神经网络具有巨大优势。

神经网络的应用已经渗透到模式识别、图像处理、非线性优化、专家系统等各个领域，并取得了令人瞩目的成果。

旅行商的路径优化问题规则虽然简单，但在地点数目增多后求解却极为复杂。

随着旅行商所经地点数目的增多，如果要列举所有路径后再确定最佳行程，那么总路径数量之大，几乎难以计算出来。

多年来全球数学家绞尽脑汁，试图找到一个高效算法。

本文介绍了利用人工神经网络来解决这一传统难题的另一个方法。

1.生物神经网络基础1.1生物神经元的结构大脑中的神经元形态不尽相同，功能也有差异，但从组成结构来看个神经元细胞是有共性的。

神经元在结构上由细胞体、树突、轴突和突触四部分组成。

如图1图1 神经细胞的结构1.2生物神经元的信息处理机理神经细胞利用电-化学过程交换信号。

输入信号来自另一些神经细胞。

这些神经细胞的轴突末梢（也就是终端）和本神经细胞的树突相遇形成突触，信号就从树突上的突触进入本细胞。

信号在大脑中实际怎样传输是一个相当复杂的过程，但就我们而言，重要的是把它看成和现代的计算机一样，利用一系列的0和1来进行操作。

就是说，大脑的神经细胞也只有两种状态：兴奋（fire）和不兴奋（即抑制）。

发射信号的强度不变，变化的仅仅是频率。

神经细胞利用一种我们还不知道的方法,把所有从树突突触上进来的信号进行相加，如果全部信号的总和超过某个阀值，就会激发神经细胞进入兴奋状态，这时就会有一个电信号通过轴突发送出去给其他神经细胞。

如果信号总和没有达到阀值，神经细胞就不会兴奋起来。

1.3人脑的功能特点由于脑神经细胞间数量巨大的连接，使得大脑具备难以置信的能力。

尽管每一个神经细胞仅仅工作于大约100Hz的频率，但因各个神经细胞都以独立处理单元的形式并行工作着，使人类的大脑具有下面这些非常明显的特点：能实现无监督的学习。

有关我们的大脑的难以置信的事实之一，就是它们能够自己进行学习，而不需要导师的监督教导。

如果一个神经细胞在一段时间内受到高频率的刺激，则它和输入信号的神经细胞之间的连接强度就会按某种过程改变，使得该神经细胞下一次受到激励时更容易兴奋。

与此相反的是，如果一个神经细胞在一段时间内不受到激励，那么它的连接的有效性就会慢慢地衰减。

这一现象就称可塑性1）对损伤有冗余性。

大脑即使有很大一部分受到了损伤，它仍然能够执行复杂的工作。

例如在人类身上能见到这种现象：由于心血管病或其他原因引起大面积脑组织坏死的脑梗死病人经过一段时间的康复训练后也能恢复健康，特别是，记忆力并不受损。

2）处理信息的效率极高。

神经细胞之间电-化学信号的传递，与一台数字计算机中CPU的数据传输相比，速度是非常慢的，但因神经细胞采用了并行的工作方式，使得大脑能够同时处理大量的数据。

例如，大脑视觉皮层在处理通过我们的视网膜输入的一幅图象信号时，大约只要100ms的时间就能完成。

考虑到神经细胞的平均工作频率只有100Hz，100ms的时间就意味只能完成10个计算步骤！想一想通过我们眼睛的数据量有多大，你就可以看到这真是一个难以置信的伟大工程了。

3）善于归纳推广。

大脑和数字计算机不同，它极擅长的事情之一就是模式识别，并能根据已熟悉信息进行归纳推广。

例如，我们能够阅读他人所写的手稿上的文字，即使我们以前从来没见过他所写的东西。

2.人工神经网络鉴于大脑具有以上的优点科学家们创造出了人工神经网络。

人工神经网络是基于生理学上真实的人脑神经网络的结构和原理以及基本特性进行理论抽象、简化和模拟而成的一种信息处理系统。

2.1人工神经元网络的神经元模型与大脑类似，神经元是人工神经网络的基本单元。

目前人们提出的神经元模型有多种，其中影响最大的是1943年心理学家McCulloch和数学家W . Pitts在分析总结神经元基本特性的基础上首先提出的M-P模型。

如图2图2 M-P模型示意图其中x1，x2，…xn。

为输入信息号，为神经元内部状态，θj为阈值，W i j为两个神经元的连接权值，f (.) 为激发函数，y j为输出，上述模型的数学形式为：y j=ƒ(∑ W ij X j - θ i)这样，每一个神经元的输入接受前一级神经元的输出，因此，对神经元j的总作用为所有输入的加权和减去阈值(若无阈值则不减)，此作用引起神经元j的状态变化，而神经元j的输出y，为其当前状态( ∑ W ij X j - θ I )的函数。

2.2人工神经元网络模型大量神经元相互连接组成庞大的神经网络才能实现对复杂信息的处理与存储。

因此必须按一定的规则将神经元连接成神经网络，这里根据神经网络内部信息的传递方向，可分为两类：前馈型网络和反馈型网络。

如图3、4图3：前馈网络图4：反馈网络2.3人工神经网络与冯诺依曼计算机相比的特点1）大规模并行处理人工神经网络的基本结构模仿人脑，具有并行处理的特征，可以大大提高工作速度。

2）分布式存储人工神经网络的信息存储在神经元之间的连接强度分布上，存储区与运算区合为一体。

3）自适应学习过程人工神经网络可以通过学习和训练过程改变突触权重值以适应周围环境要求2.4人工神经网络可以实现的功能1）联想记忆功能人工神经网络可以通过预先存储信息和学习机制进行自适应训练，从不完整的信息和噪声干扰中恢复原始的完整信息，如图像恢复，语音处理。

2）分类与识别功能神经网络对外界输入样本有很强的识别与分类能力，对输入样本的分类实际是在样本空间中找出符合分类要求的分割区域。

3）优化计算功能在约束条件下寻找参数组合，建立目标函数，使函数值达到最小。

人工神经网络的优化计算在TSP及生产调度问题上有重要的应用。

3. Hopfield神经网络的算法分析美国加州理工学院物理学家J.J. Hopfield教授于1983年提出一种单层反馈神经网络，后来人们将这种反馈网络称作Hopfield网络。

Hopfield网络分为离散型和连续型两种网络模型分别记作DHNN 和CHNN。

3.1离散型Hopfield网络3.1.1离散型Hopfield网络的结构图5离散型Hopfield网络为单层结构，网络由n个单元组成，Ni表示第i个神经元，这些神经元既是输入单元，也是输出单元，各个单元一般取同样的功能函数f，为分析方便各单元的阈值全部为0，其中x=（x1，x2，… xn)为网络输入，y=（y1，y2，… yn)为网络输出。

3.1.2Hopfield神经网络运行的几个基本概念1）网络的稳定性与能量函数网络从初态v(0)开始变化，经过有限次递归后其状态不再变化，即v(t+Δt)=v(t)则称网络是稳定的。

此时网络的能量函数为极小值。

网络的能量函数与网络的稳定性密切相关，网络的能量函数在网络状态按一定规则变化时能自动趋向能量的极小点。

2）网络的吸引子在网络经过时间t后，若状态ν(t)是稳定的，则称ν(t)是网络的稳定吸引子。

3）吸引子的吸引域网络按照运行规则会最终稳定在同一吸引子ν(t)上的特定的初始状态ν(0)的集合称为网络的吸引域。

3.2连续型Hopfield神经网络连续型Hopfield神经网络的结构与离散型Hopfield神经网络结构相同，所有神经元都随时间t 并行更新，网络随时间连续变化。

图6给出了基于电子线路的CHNN的拓扑结构。

CHNN模型与该电子线路直接对应，每一个神经元可以可以用一个运算放大器来模拟。

神经元的输入、输出分别对应运放的输入电压ui，和输出电压νi。

用输入端电导表示连接权值Wij，外界偏置电流Ij相当于阈值。

图6：CHNN的电子线路图分析图中第j个神经元电路，根据基尔霍夫定律可写出以下方程：令Rj=1/gj得：（1）令得：（2）定义CHNN的能量函数为（3）如果图6中的运算放大器接近理想运放，上式的积分项可以忽略不计，即能量函数可以写为：（4）可以证明CHNN的能量函数总是单调递减的，即网络最终能够达到稳定状态。