hopfield网络求解tsp问题

《hopfield网络求解tsp问题》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、Hopfield神经网络求解TSP问题1.什么是TSP问题？旅行商问题，即TSP问题（TravelingSalesmanProblem），也是最优化问题。一个旅行商人要拜访n个城市，他必须选择所要走的路径，路径的限制是每个城市只能拜访一次，而且最后要回到原来出发的城市。路径的选择目标是要求得的路径路程为所有路径之中的最小值。用数学语言描述TSP如下:设有限个城市集合:C={C1,C2,…,Cn}，每两个城市间的距离为d（Ci，Cj）∈Z,其中Ci，Cj∈C（1<=i,j<=n),即求minL=∑d（Ci，Cj）的值的问题。有效路径的方案数目为Rn=（（n-1）！

2、/2）,例如:R4=3,R5=12,R6=120,R10=181440可见路径总数，随n增大而急剧增长,当城市数目增加到一定的程度,计算量增加到无法进行的地步，所以要选择一种合理快速的算法，而不能对所有情况使用人工列举的方法。2.Hopfield神经网络介绍人工神经网络（ArtificialNeuralNetworks，简写为ANNs）也简称为神经网络（NNs）或称作连接模型（ConnectionModel），它是一种模仿动物神经网络行为特征，进行分布式并行信息处理的算法数学模型。这种网络依靠系统的复杂程度，通过调整内部大量节点之间相互连接的关系，从而达到处理信

3、息的目的.最基础的为BP、Hopfield网络等。Hopfield网络是一种互连型网络的一种，它引入类似于Lyapunov函数的能量函数概念，把神经网络的拓扑结构(用连接权矩阵表示)与所求问题(用目标函数描述)相对应，并将其转换为神经网动力学系统的演化问题。1.神经元的数学模型人的大脑是由大量神经细胞或神经元组成的。每个神经元可以看作为一个小的处理单元，这些神经元按照某种方式相互连接起来，构成大脑内部的生理神经元网络系统，他们中各个神经元之间连接的强弱不是固定不变的，而是按照外部的信号激励程度做自适应的变化，而每个神经元又随着接收到的多个激励信号的综合大小呈现兴

4、奋或抑制状态。大脑的学习过程就是神经元之间连接强度随外部激励信号做自适应变化的过程。大脑处理信息的结果由神经元状态表现出来。由此见，神经元是信息处理的最小单位。神经元，也就是神经细胞，由细胞体、树突、轴突和突触组成。从细胞体上伸出许多树突和一条长的轴突，树突和轴突分别负责传入和传出兴奋或抑制信号到细胞体。神经元的树突短而且分支很多，是信号的输入端；轴突较长，是信号的输出端，其未端化为许多细小的分支，称为神经术梢。一个神经元通过轴突与其它细胞的树突相连。神经末梢与树突接触的界面称为突触，它是一个神经元与另一个神经元联系的特殊结构部位，突触包括突触前(成分)、突触间

5、隙和突触后(成分)三个部分。树突和轴突一一对接，从而靠突触把众多的神经元连接成一个神经元网络。神经元群或者神经网络系统对外界有兴奋或抑制两种反应，兴奋指的是由相对静止变为相对活动，而抑制则是指由相对活动变为相对静止。神经元之间的信息传递有正负两种连接。正连接相互激发，负连接相互抑制。图1.1神经元的结构型其中,,...为输入信息，为神经元内部状态，为阈值，为到连接的权值，表示外部输入信号，(在某些情况下，它可以控制神经元，使可以保持在某一状态)，为激发函数，为输出，上述模型的数学形式可以描述为：(式1.1)(式1.2)(式1.3)其中，(式1.4)4.Hopfi

6、eld神经网络结构图图2.2连续型Hopfield神经网络的电路形式若定义网络中第j个神经元的总输入为，输出状态为，那么网络的状态转移方程可写为：（式2.10）其中g为S型函数，一般常用的有这两个函数的共同特点是。和。时，函数值饱和到两极，限制了网络中状态及流动信息的增长范围。函数，中的参数以控制S型函数在零点附近的斜率变化。函数可看做符号函数。在网络的整个运行过程中，所有节点状态的演变有异步、同步和连续更新三种形式。与离散Hopfield网络比较，多了一种连续更新的形式，表示网络中所有节点都随连续时间并行更新。网络中状态在一定范围内连续变化。5.神经元网络的动

7、力学方程连续型hopfield神经网络在时间上是连续的。所以，网络中各神经元是处于同步方式工作的。考虑对于一个神经细胞，即神经元i，其内部膜电位状态用表示，生物神经元的动态(微分系统)由运算放大器来模拟，其中微分电路中细胞膜输入电容为Ci，细胞膜的传递电阻为Ri，输出电压为Vi，外部输入电流用表示。神经元的状态满足如下动力学方程：（式2.11）则连续型Hopfield神经网络模型可用图2.2所示的电路来模拟实现。5.Hopfield神经网络解决TSP问题Hopfield神经网络解决TSP问题的基本步骤1）将TSP问题的每一条可能路径用一个置换矩阵表示，并给出相应

8、的距离表示式。2）将TS