hopfield网络求解TSP问题

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）,例如:R4=3,R5=12,R6=120,R10=181440可见路径总数，随n增大而急剧增长,当城市数目增加到一定的程度,计算量增加到无法进行的地步，所以要选择一种合理快速的算法，而不能对所有情况使用人工列举的方法。2.Hopfield神经网络介绍人工神经网络（ArtificialNeuralNetworks，简写为ANNs）也简称为神经网络（NNs）或称作连接模型（ConnectionModel），它是一种模仿动物神经网络行为特征，进行分布式并行信息处理的算法数学模型。这种网络依靠系统的复杂程度，通过调整内部大量节点之间相互连接的关系，从而达到处理信息的目的.最基础的为BP、Hopfield网络等。Hopfield网络是一种互连型网络的一种，它引入类似于Lyapunov函数的能量函数概念，把神经网络的拓扑结构(用连接权矩阵表示)与所求问题(用目标函数描述)相对应，并将其转换为神经网动力学系统的演化问题。3.神经元的数学模型人的大脑是由大量神经细胞或神经元组成的。每个神经元可以看作为一个小的处理单元，这些神经元按照某种方式相互连接起来，构成大脑内部的生理神经元网络系统，他们中各个神经元之间连接的强弱不是固定不变的，而是按照外部的信号激励程度做自适应的变化，而每个神经元又随着接收到的多个激励信号的综合大小呈现兴奋或抑制状态。大脑的学习过程就是神经元之间连接强度随外部激励信号做自适应变化的过程。大脑处理信息的结果由神经元状态表现出来。由此见，神经元是信息处理的最小单位。神经元，也就是神经细胞，由细胞体、树突、轴突和突触组成。从细胞体上伸出许多树突和一条长的轴突，树突和轴突分别负责传入和传出兴奋或抑制信号到细胞体。神经元的树突短而且分支很多，是信号的输入端；轴突较长，是信号的输出端，其未端化为许多细小的分支，称为神经术梢。一个神经元通过轴突与其它细胞的树突相连。神经末梢与树突接触的界面称为突触，它是一个神经元与另一个神经元联系的特殊结构部位，突触包括突触前(成分)、突触间隙和突触后(成分)三个部分。树突和轴突一一对接，从而靠突触把众多的神经元连接成一个神经元网络。神经元群或者神经网络系统对外界有兴奋或抑制两种反应，兴奋指的是由相对静止变为相对活动，而抑制则是指由相对活动变为相对静止。神经元之间的信息传递有正负两种连接。正连接相互激发，负连接相互抑制。图1.1神经元的结构型其中1x,2x,...nx为输入信息，iu为神经元内部状态，i为阈值，ijw为iu到ju连接的权值，is表示外部输入信号，(在某些情况下，它可以控制神经元iu，使可以保持在某一状态)，()f为激发函数，iy为输出，上述模型的数学形式可以描述为：iijiijws(式1.1)()iiug(式1.2)()()iiiijjiijyhuffwxs(式1.3)其中，fhg(式1.4)4.Hopfield神经网络结构图图2.2连续型Hopfield神经网络的电路形式若定义网络中第j个神经元jN的总输入为ju，输出状态为jv，那么网络的状态转移方程可写为：jjijijivgugwx（式2.10）其中g为S型函数，一般常用的有1()1/(1)xgxe)()(2xthxg这两个函数的共同特点是x。和x。时，函数值饱和到两极，限制了网络中状态jv及流动信息ju的增长范围。函数1g，2g中的参数以控制S型函数在零点附近的斜率变化。函数2g可看做符号函数。在网络的整个运行过程中，所有节点状态的演变有异步、同步和连续更新三种形式。与离散Hopfield网络比较，多了一种连续更新的形式，表示网络中所有节点都随连续时间并行更新。网络中状态在一定范围内连续变化。5.神经元网络的动力学方程连续型hopfield神经网络在时间上是连续的。所以，网络中各神经元是处于同步方式工作的。考虑对于一个神经细胞，即神经元i，其内部膜电位状态用ju表示，生物神经元的动态(微分系统)由运算放大器来模拟，其中微分电路中细胞膜输入电容为Ci，细胞膜的传递电阻为Ri，输出电压为Vi，外部输入电流用iI表示。神经元的状态满足如下动力学方程：nitUgtVItVWRtUttUCiiiinjjjiiiii,...,2,1))(()()()(d)(d1（式2.11）则连续型Hopfield神经网络模型可用图2.2所示的电路来模拟实现。）（0/tanh121UUV6.Hopfield神经网络解决TSP问题Hopfield神经网络解决TSP问题的基本步骤1）将TSP问题的每一条可能路径用一个置换矩阵表示，并给出相应的距离表示式。2）将TSP问题的置换矩阵集合与由N个神经元构成的神经元阵列相应，每条路径对应的置换矩阵的各元素与相应的神经元稳态输出相应。3）找出一个反映TSP的约束优化问题的能量函数E。4）求出使E取最小值的神经网络连接权值矩阵和偏置参数。7.神经元矩阵和关联矩阵Hopfield网络来解决TSP问题时体现了人脑的一些特征。开始首先把问题转化成适合于神经元网络处理的形式。对于n个城市的TSP问题，用一个n×n”的神经元矩阵，用神经元的状态来表示某一个城市在某一条有效路径中的位置。神经元ix的状态用xiv，表示，其中nx,21，，：第X个城市用xc表示，而i∈{1,2,⋯,n}表示城市xc在路径中是第i个城市。状态1xiv表示xc在路径中第i个位置出现；0xiv表示xc在第i个位置不出现，说明此时第i个位置上是其它城市。由此可见，n×n矩阵v可以表示n个城市TSP问题一次有效的路径，即v矩阵可以唯一地确定对于所有城市的访问次序。为了保证每个城市只去一次(出发点除外)，那么关联矩阵v上每一行只能有一个为1，其它必须为0，对应于每次访问而且只访问一个城市，所以对于关联矩阵的次序上，也是每一列只有一个元素为1，其它为0，全部非0元素的总和为n。8.优化约束条件能量函数为了解决TSP问题，必须构成这样的网络：在网络运行时，计算能量降低。网络稳定后其输出状态代表城市被访问的次序。网络能量的极小点对应于最佳或者较好的路径的形成，此时由输出换位阵能得到较好路径。问题的关键一步是构成合适的能量函数。能量函数约束条件的含义：，其中A0为常数。保证当矩阵V的每一行不多于一个1时，达到最小=0。，其中B0为常数。保证当矩阵V的每一列不多于一个l时，达到最小=0。，其中C0为常数。保证当矩阵V中的1的个数恰好为n时，即整个矩阵有n个1时，达到最小=0。，实际数值就是一次有效路径总长度的倍数。若路径为最佳时，达到最小点。41232,1,1()()222xyxiyiyixixyxixixixjxiyixijiixyxEEEEECdvvvvnABvvvv1111,2nnnxixjxijjiAEvv2111,2nnnxiyiixyyxBEvv4,1,1111,()2nnnxyxiyiyixiyyxDElvvv9.Hopfield神经网络状态方程将约束条件能量函数E和神经网络电路标准能量函数公式nitViniiininjijjiiVVgRItVtVtVWtE1)(01111d)(1)(-)()(21-)(对比，并化简后得：,1,1()()xixixixjxjxyyiyijiyxxyyxxixixidUUCAvBvCNDlvvdtRvgu其中为神经元的时空综合输入,为其对应的神经元的输出01()21expxixixivfuuu10.Matlab实现与仿真结果实验一：10个城市的归一化坐标：（0.77880.5181）（0.42350.9436）（0.09080.6377）（0.26650.9577）（0.15370.2407）（0.28100.6761）（0.44010.2891）（0.52710.6718）（0.45740.6951）（0.87540.0680）k=1:1:5000（迭代次数）;A=B=D=500,C=200;u0=0.02（初始条件）;step=0.01;N=10(10个城市)TSP_hopfield迭代次数k=5000寻优路径矩阵：V1=0001000000000000000100000001000000000010000000100010000000000000010000001000000001000000000000100000优化路径L=C6-C9-C8-C1-C10-C7-C5-C3-C4-C2-C6最优能量函数：Final_E=1.5063初始路程：Initial_Length=4.1888最短路程：Final_Length=3.0126迭代次数对能量函数的影响能量函数随着迭代次数的增加而减小，最后达到极小稳定值，而在迭代开始的时候优化约束条件能量函数迅速下降，说明神经网络对于解决TSP的有效性。实验二改变u0=0.03，其他的都变TSP_hopfield迭代次数k=5000寻优路径矩阵：V1=0000001000000000000100100000001000000000000100000001000000000000100000000000010000000000100000010000优化路径L=C4-C6-C3-C5-C7-C10-C1-C8-C9-C-C4最优能量函数：Final_E=1.4469初始路程：Initial_Length=4.1888最短路程：Final_Length=2.8938实验一和实验二对比：初始条件的微小变化，也会对结果产生严重的影响，致使寻优路径，换位矩阵，能量函数都发生变化，产生了更优的结果。实验三20个城市归一化坐标：（0.89540.0946）（0.58250.3232）（0.58270.7696）（0.85490.2341）（0.03490.7404）（0.88540.6928）（0.40770.8241）（0.03640.8280）（0.74610.2934）（0.15480.3094）（0.14390.5230）（0.60600.3253）（0.25450.8318）（0.32420.8103）（0.40180.5570）（0.40640.2630）（0.38620.6806）（0.60980.2337）（0.16690.4564）（0.18810.3846）k=1:1:5000（迭代次数）;A=B=D=500,C=200;u0=0.02（初始条件）;step=0.01;N=20(10个城市)寻优路径矩阵：V1=10000000000000000000000010000000000000000000000000000000001001000000000000000000000000000000100000000000000000000000000100000000000000000100000000000001000000000010000000000000000000000000000000100000000000000000000