《神经网络算法》由会员分享，可在线阅读，更多相关《神经网络算法（12页珍藏版）》请在金锄头文库上搜索。
1、神经网络解决TSP问题题目：基于HopHeld网络算法的TSP问题的分析与实现学 号：名：一、预备知识1、TSP问题旅行商问题，简称TSP,即给定n个城市和两两城市之间的距离，要求确定 一条经过各城市当且仅当一次的最短路线。其图论描述为：给定图G=（V，A）， 其中V为顶点集，A为各顶点相互连接组成的边集，设D=（dij）是由顶点i和顶 点j之间的距离所组成的距离矩阵，要求确定一条长度最短的Hamilton回路，即 遍历所有顶点当且仅当一次的最短距离。旅行商问题可分为如下两类：（1）对称旅行商问题（ddji，n，j=1，2, 3,，n）;（2）非对称旅行商问题（d|j气，甲j=1，2，3，n）
2、。非对称旅行商问题较难求解，我们一般是探讨对称旅行商问题的求解。若对于城市V=v，v，v，v 的一个访问顺序为T=t，t， t，t，123123t，其中t.EV （i=1，2, 3,，n），且记t+1=t，则旅行商问题的数学模型为：nin 1riminL=。/ .。仕|TSP是一个典型的组合优化问题，并且是一个NP完全难题，是诸多领域内 出现的多种复杂问题的集中概括和简化形式，并且已成为各种启发式的搜索、优 化算法的间接比较标准。因此，快速、有效地解决TSP有着重要的理论价值和极 高的实际应用价值。2、Hopfield 网络Hopfield网络是一种互连型网络的一种，它引入类似于Lyapuno
3、v函数的能量函 数概念，把神经网络的拓扑结构（用连接权矩阵表示）与所求问题（用目标函数描述） 相对应，并将其转换为神经网动力学系统的演化问题。其演变过程是一个非线性 动力学系统，可以用一组非线性差分议程描述（离散型）或微分方程（连续型）来描 述。系统的稳定性可用所谓的“能量函数”进行分析。在满足条件的情况下，某种“能量函数”的能量在网络运行过程中不断地减少，最后趋于稳定的平衡状态。因为人工神经网络的变换函数是一个有界函数，故系统的状态不会发生发散 现象。目前，人工神经网络经常利用渐进稳定点来解决某些问题。如果把系统的 稳定点视为一个记忆的话，那么从初态朝这个稳定点的演变过程就是一个寻找记 忆的
4、过程。如果把系统的稳定点视为一个能量函数的极小点，而把能量函数视为 一个优化问题的目标函数，那么从初态朝这个稳定点的演变过程就是一个求解该 优化问题的过程。因此，Hopeld神经网络的演变过程是一个计算联想记忆或求 解优化问题的过程。实际上，它的解决并不需要真的去计算，而是通过构成反馈 神经网络，适当地设计其连接权和输入就可以达到这个目的。二、HopField神经网络分析1、离散型HopField神经网络Hopfield最早提出的网络是二值神经网络，神经元的输出只取1和0两个值， 也称为离散Hopfield网络。在离散Hopfield网络中，采用的神经元是二值神经元， 输出的离散值1和0分别表
5、示神经元处于激活和抑制状态。离散Hopfield神经网络是离散时间系统，它可以用一个加权无向图表示，图 的每一边都有一个权值，图的每个节点都有一个阈值，网络的阶数相应于图中的 节点数。Hopfield网络的基本结构如图1所示，这种网络是一种单层网络，令网络由n 个单元组成，N1，N2，N表示n个神经元，这些神经元既是输入单元，也 是输出单元，其转移特性函数为f，f，.，f，门限值（阈值）为0，0，.，0。12n12n图1 Hopfield网络结构图对于离散型Hopfield网络，各节点一般选取同样的转移函数，且为符号函数， 即：f =匕=fn (x) = sgn( x)(式 1.1)为了分析方
6、便，选取各节点的门限值(即阈值)全部为0，即：0 = 0 =0 =0(式 1.2)同时，x = (x , x，,x ), x e -1,+1n 为网络的输入；y = (yy，,y ), y e -1,+112n1 2n为网络的输出；馅)=(v(), v2(t ), vn (t), v (t) = -1, + 1n为网络在t时刻的状态， 其中te(0,1,2)为离散时间变量；七为从七到气的连接权值，Hopfield神经 网络是对称的，即有w = w , i, j e (1,2,3,n)(式 1.3)整个网络所有n个节点之间的连接强度用矩阵W表示，显然W为nXn方阵。由图1可见Hopfield网络
7、为一层结构的反馈网络，能处理双极型离散数据(即 输入x-l，+1)，及二进制数据(x0，1)。当网络经过训练后，可以认为网络 处于等待工作状态，而对网络给定初始输入x时，网络就处于特定的初始状态， 由此初始状态开始运行，可以得到网络输出即网络的下一状态。然后，这个输出状态通过反馈回送到网络的输入端，作为网络下一阶段运行的输入信号，而这个 信号可能与初始信号X不同，由这个新的输入又可得到下一步的输出，这个输出 也可能与上一步输出不同。如此下去，网络的整个运行过程就是上述反馈过程的 重复。如果网络是稳定的，那么，随着许多次反馈运行，网络状态的变化减少， 直到后来不再变化，达到稳定状态，此时，在网络
8、的输出端可得到稳定的输出， 可用以下公式表示为：v (0) xv (t1)f w v (t)j ij j（式 1.）其中%是由（1.定义，为方便，一般j值取0。从某个时刻t之后网络状态不再变迁，既有v（t 1） v（t），那么，输出有y v(t)（式 1.）网络神经元状态的演变有两种形式：（1）串行方式在某一时刻t只有某一神经元N，的状态按照式（1.更新，而其余j-个神经元状态保持不变，即v(t 1) sgn w v (t)ij i（式 1.）对于某个特定的j单元来说，下式成立（式 1.）v (t 1) v (t) i (1,2，n),i若以某种确定性次序来选择N，使其按照（1.变化，称顺序更
9、新；若按照预 先设定的概率来选择神经元N，则称其为随机更新。（2）并行方式在任一时刻t部分单元按（1.政变状态，其中有一种重要的特殊情况是在某时刻，所有神经元同时按照（1.政变状态，即：匕(t +1) = sgn心(t)”j 引1,2,，n(式 1.8)这时，可把状态转移方程写成向量形式:(式 1.9)v(t +1) = sgn(v(t) w)2、连续型Hopfield神经网络这种网络的每个神经元的输入与输出关系为连续可微的单调递增函数，它的 每个神经元的输入是一个随时间变化的状态变量，它与外界输入和其他神经元来 的信号有直接关系，同时也与其它神经元同它之间的连接权有关系，状态变量宜 接影响输
10、入变量，使系统变成一个随时间变化的动态系统。连续型Hopfield神经网络在网络的结构上与离散型相同，其状态方程在形式 上也一样。若定义网络中第j个神经元气的总输入为七，输出状态为vj，那么 网络的状态转移方程可写为:(式 1.10)其中g为S型函数，一般常用的有gi( x) = 1/(1+ e$)g 2( x) = th (人 x)这两个函数的共同特点是X T+3。和X T-8。时，函数值饱和到两极，限制了网络中状态V及流动信息U的增长范围。函数g，g中的参数人以控制Sjj12型函数在零点附近的斜率变化。函数g2可看做符号函数。在网络的整个运行过程中，所有节点状态的演变有异步、同步和连续更新
11、三 种形式。与离散Hopfield网络比较，多了一种连续更新的形式，表示网络中所有 节点都随连续时间并行更新。网络中状态在一定范围内连续变化。连续型hopfield神经网络在时间上是连续的。所以，网络中各神经元是处于同步方式工作的。考虑对于一个神经细胞，即神经元i，其内部膜电位状态用u j表示，生物神经元的动态(微分系统)由运算放大器来模拟，其中微分电路中细胞膜输入电容为Ci，细胞膜的传递电阻为Ri，输出电压为Vi，外部输入电流用1表表示。神经元的状态满足如下动力学方程:C du = _ 誓 + wy （t） +1idtRji j i I = 1,2,.,n-i R Vt（t） = gW*）j
12、=1（式 1.11）则连续型HopGeld神经网络模型可用图2所示的电路来模拟实现。图2连续型Hopfield神经网络的电路形式电路中微分系统的暂态过程的时间常数通过电容Ci,和电阻Ri并联实现， 跨导勺模拟神经元之间互连的突触特性。du u f 奇F V = f （u ）L ii=Y 5 +1RijTij（式 1.12）du111u + L V + i-iRC j C5i dt R CV = f （u Viij=1 ij ii（式 1.13）其中：1 R + U Rij=1 Ri（式 1.14）（式 1.15）0 = L , i i i ij R C i Cij i可得到:duidt（式 1
13、.16）i =1234N（式 1.17）i先设定初态（u ），运行至稳定，得到稳定状态。对应输出:ITU（公式1.18）随着时间的增长变1 + tan u0微分方程（式1.12）反映了网络状态的连续更新的意义， 化，网络逐渐趋于定态，在输出端可以得到稳定的输出。三、实际应用Hopfield神经网络有很多成功的应用，这种网络的主要应用形式有联想记忆和优化计算两种形式。用Hopfield网络解决具体的优化问题，需要按以下步骤进行:1. 对于待定的问题，选择一种合适的表示方法，使得神经网络的输出与问题的解对应起来;2. 构造神经元网络的能量函数，使其最小值对应于问题的最佳解;3. 由能量函数倒过来推
14、出神经网络的结构；4. 由网络结构建立起网络，令其运行，那么稳定状态就是在一定条件下 问题的解。对于TSP问题若用传统的穷举搜索法，则需要找出全部路径之组合，再对其 进行比较，找到最佳路径。这种方法随着城市数目的增加，计算工作量急剧增加。 这是用传统的串行计算机难以在有限时间内得到圆满解决的问题。在实际应用 中，这类问题往往不要求得到严格的最优解，只要是接近最优的解就可以了。 开始首先把问题转化成适合于Hopfield网络来解决TSP问题时体现了人脑的一些特征。开始首先把问题转 化成适合于神经元网络处理的形式。对于n个城市的TSP问题，用一个nXn”的 神经元矩阵，用神经元的状态来表示某一个城
15、市在某一条有效路径中的位置。神经元x的状态用v，表示，其中x $,2,., n：第X个城市用c表示，而沱 ixix1,2, ,n表示城市c在路径中是第i个城市。状态V. =1表示c在路径中第i个位 置出现；vxi=0表示cx在第i个位置不出现，说明此时第i个位置上是其它城市。 由此可见，nXn矩阵v可以表示n个城市TSP问题一次有效的路径，即v矩阵可 以唯一地确定对于所有城市的访问次序。为了保证每个城市只去一次（出发点除 外），那么关联矩阵v上每一行只能有一个为1，其它必须为0，对应于每次访问 而且只访问一个城市，所以对于关联矩阵的次序上，也是每一列只有一个元素为 1，其它为0，全部非0元素的总和为n。例如n=6,则一次有
