内容发布更新时间 : 2024/12/22 19:13:07星期一 下面是文章的全部内容请认真阅读。

Hopfield神经网络求解TSP问题

1.什么是TSP问题？

旅行商问题，即TSP问题（Traveling Salesman Problem），也是最优

化问题。一个旅行商人要拜访n个城市，他必须选择所要走的路径，路径的限制是每个城市只能拜访一次，而且最后要 回到原来出发的城市。路径的选择目标是要求得的路径路程为所有路径之中的最小值。 用数学语言描述TSP如下 :设有限个城市集合 : C = { C1 , C 2 , … , Cn }，每两个城市间的距离为 d（Ci，Cj）∈Z, 其中 Ci，Cj∈C（ 1<=i , j <=n), 即求 minL=∑d（Ci，Cj）的值的问题。 有效路径的方案数目为Rn=（（n-1）！/2）,例如:R4=3,R5=12,R6=120,R10=181440可见路径总数，随n增大而急剧增长,当城市数目增加到一定的程度,计算量增加到无法进行的地步，所以要选择一种合理快速的算法，而不能对所有情况使用人工列举的方法。

2.Hopfield神经网络介绍

人工神经网络（Artificial Neural Networks，简写为ANNs）也简称

为神经网络（NNs）或称作连接模型（Connection Model），它是一种模仿动物神经网络行为特征，进行分布式并行信息处理的算法数学模型。这种网络依靠系统的复杂程度，通过调整内部大量节点之间相互连接的关系，从而达到处理信息的目的.最基础的为BP、Hopfield网络等。 Hopfield网络是一种互连型网络的一种，它引入类似于Lyapunov函数的能量函数概念，把神经网络的拓扑结构(用连接权矩阵表示)与所求问题(用目标函数描述)相对应，并将其转换为神经网动力学系统的演化问题。

3.神经元的数学模型

人的大脑是由大量神经细胞或神经元组成的。每个神经元可以看作为一个小的处理单元，这些神经元按照某种方式相互连接起来，构成大脑内部的生理神经元网络系统，他们中各个神经元之间连接的强弱不是固定不变的，而是按照外部的信号激励程度做自适应的变化，而每个神经元又随着接收到的多个激励信号的综合大小呈现兴奋或抑制状态。大脑的学习过程就是神经元之间连接强度随外部激励信号做自适应变化的过程。大脑处理信息的结果由神经元状态表现出来。由此见，神经元是信息处理的最小单位。神经元，也就是神经细胞，由细胞体、树突、轴突和突触组成。从细胞体上伸出许多树突和一条长的轴突，树突和轴突分别负责传入和传出兴奋或抑制信号到细胞体。神经元的树突短而且分支很多，是信号的输入端；轴突较长，是信号的输出端，其未端化为许多细小的分支，称为神经术梢。一个神经元通过轴突与其它细胞的树突相连。神经末梢与树突接触的界面称为突触，它是一个神经元与另一个神经元联系的特殊结构部位，突触包括突触前(成分)、突触间隙和突触后(成分)三个部分。树突和轴突一一对接，从而靠突触把众多的神经元连接成一个神经元网络。

神经元群或者神经网络系统对外界有兴奋或抑制两种反应，兴奋指的是由相对静止变为相对活动，而抑制则是指由相对活动变为相对静止。神经元之间的信息传递有正负两种连接。正连接相互激发，负连接相互抑制。

图1.1 神经元的结构型

?i为阈值，wij为ui其中x1,x2,...xn为输入信息，ui为神经元内部状态，

到uj连接的权值，si表示外部输入信号，(在某些情况下，它可以控制神经元ui，使可以保持在某一状态)，f()为激发函数，yi为输出，上述模型的数学形式可以描述为：

?i??wij?si??i (式1.1)

jui?g(?i) (式1.2)

??yi?h(ui)?f(?i)?f??wijxj?si??i? (式1.3)

?j?其中， f?h?g (式1.4)

4.Hopfield神经网络结构图

图2.2 连续型Hopfield神经网络的电路形式

若定义网络中第j个神经元Nj的总输入为uj，输出状态为vj，那么网络的状态转移方程可写为：

vj?g?uj??g??wijxi??j? （式2.10）

?i???