神经网络算法

神经网络算法 TSP 题目: 基于Hopfield网络算法的TSP问题的与实现 学 号: 2220150496 姓 名: 陈帅 一、预备知识 1、TSP问题 旅行商问题，简称TSP，即给定n个城市和两两城市之间的距离，确定一条经过各城市当且仅当一次的最短路线。其图论描述为:给定图G=(V，A)，其中V为顶点集，A为各顶点相互连接组成的边集，设D=(dij)是由顶点i和顶点j之间的距离所组成的距离矩阵，要求确定一条长度最短的Hamilton回路，即遍历所有顶点当且仅当一次的最短距离。 旅行商问题可分为如下两类: (1)对称旅行商问题(d=d，Π，j=1，2，3，?，n); ijjii (2)非对称旅行商问题(d?d，ϖ，j=1，2，3，?，n)。 ijjii 非对称旅行商问题较难求解，我们一般是探讨对称旅行商问题的求解。 }的一个访问顺序为T={t，t，t，?，t，若对于城市V={v，v，v，?，vn123i123 ?，t}，其中t?V(i=1，2，3，?，n)，且记t+1=t，则旅行商问题的数学模nin1 型为:minL=。 。 TSP是一个典型的组合优化问题，并且是一个NP完全难题，是诸多领域内出现的多种复杂问题的集中概括和简化形式，并且已成为各种启发式的搜索、优化算法的间接比较。因此，快速、有效地解决TSP有着重要的理论价值和极高的实际应用价值。 2、Hopfield网络 Hopfield网络是一种互连型网络的一种，它引入类似于Lyapunov函数的能量函数概念，把神经网络的拓扑结构(用连接权矩阵表示)与所求问题(用目标函数描述)相对应，并将其转换为神经网动力学系统的演化问题。其演变过程是一个非线性动力学系统，可以用一组非线性差分议程描述(离散型)或微分方程(连续型)来描述。系统的稳定性可用所谓的“能量函数”进行分析。在满足条件的情况下， 1 某种“能量函数”的能量在网络运行过程中不断地减少，最后趋于稳定的平衡状态。 因为人工神经网络的变换函数是一个有界函数，故系统的状态不会发生发散现象。目前，人工神经网络经常利用渐进稳定点来解决某些问题。如果把系统的稳定点视为一个记忆的话，那么从初态朝这个稳定点的演变过程就是一个寻找记忆的过程。如果把系统的稳定点视为一个能量函数的极小点，而把能量函数视为一个优化问题的目标函数，那么从初态朝这个稳定点的演变过程就是一个求解该优化问题的过程。因此，Hopfield神经网络的演变过程是一个计算联想记忆或求解优化问题的过程。实际上，它的解决并不需要真的去计算，而是通过构成反馈神经网络，适当地设计其连接权和输入就可以达到这个目的。 二、HopField神经网络分析 1、离散型HopField神经网络 Hopfield最早提出的网络是二值神经网络，神经元的输出只取1和0两个值，也称为离散Hopfield网络。在离散Hopfield网络中，采用的神经元是二值神经元，输出的离散值1和0分别表示神经元处于激活和抑制状态。 离散Hopfield神经网络是离散时间系统，它可以用一个加权无向图表示，图的每一边都有一个权值，图的每个节点都有一个阈值，网络的阶数相应于图中的节点数。 Hopfield网络的基本结构如图1所示，这种网络是一种单层网络，令网络 NNN由n个单元组成，，，...，表示n个神经元，这些神经元既是输入单元，12n fff,,也是输出单元，其转移特性函数为，，...，，门限值(阈值)为，，...，12n12,。 n 2 图1 Hopfield网络结构图 对于离散型Hopfield网络，各节点一般选取同样的转移函数，且为符号函数，即: (式1.1) fxfxfxx()()()sgn(),,,,…12n 为了分析方便，选取各节点的门限值(即阈值)全部为0，即: ,,,==…==0 (式1.2) 12n nn同时，为网络的输入;xxxxx,,,，(,,,){1,1}…，yyyyy,,,，(,,){1,1}…，1212nn n为网络的输出;为网络在t时刻的状态，vtvtvtvtvt()((),(),,())(){1,1},,,，…，12n wNN其中t(0,1,2…)为离散时间变量;为从到的连接权值，Hopfield神,ijji 经网络是对称的，即有 ww,， (式1.3) ij,(1,2,3,),…,nijji 整个网络所有n个节点之间的连接强度用矩阵W表示，显然W为n×n方阵。 由图1可见Hopfield网络为一层结构的反馈网络，能处理双极型离散数据(即输入x?{-l，+1})，及二进制数据(x?{0，1})。当网络经过训练后，可以认为网络处于等待工作状态，而对网络给定初始输入x时，网络就处于特定的初始 3 状态，由此初始状态开始运行，可以得到网络输出即网络的下一状态。然后，这个输出状态通过反馈回送到网络的输入端，作为网络下一阶段运行的输入信号，而这个信号可能与初始信号x不同，由这个新的输入又可得到下一步的输出，这个输出也可能与上一步输出不同。如此下去，网络的整个运行过程就是上述反馈过程的重复。如果网络是稳定的，那么，随着许多次反馈运行，网络状态的变化减少，直到后来不再变化，达到稳定状态，此时，在网络的输出端可得到稳定的输出，可用以下公式表示为: vx(0),jj n,,vtfwvt(1)()，,,, (式1.4) ,,,jjijjjj,, 其中f,是由(1.1)定义，为方便，一般值取0。从某个时刻t之后网络状态jj 不再变迁，既有，那么，输出有 vtvt(1)()，, (式1.5) yvt,() 网络神经元状态的演变有两种形式: 1)串行方式 ( 在某一时刻t，只有某一神经元N，的状态按照式(1.4)更新，而其余j-1个神经元状态保持不变，即 n,,vtwvt(1)sgn() (式1.6) ，,,iji,,,1i,, 对于某个特定的j单元来说，下式成立 vtvt(1)()，, iij,,(1,2,),…,n (式1.7) ii 若以某种确定性次序来选择N，，使其按照(1.6)变化，称顺序更新;若按照 N预先设定的概率来选择神经元，，则称其为随机更新。 j (2)并行方式 在任一时刻t，部分单元按(1.4)改变状态，其中有一种重要的特殊情况是在 4 某时刻，所有神经元同时按照(1.4)改变状态，即: n,, (式1.8) vtwvt(1)sgn()j,{1,2,}…,n，,,jijj,,,1i,, 这时，可把状态转移方程写成向量形式: (式1.9) vtvtw(1)sgn(())，, 2、连续型Hopfield神经网络 这种网络的每个神经元的输入与输出关系为连续可微的单调递增函数，它的每个神经元的输入是一个随时间变化的状态变量，它与外界输入和其他神经元来的信号有直接关系，同时也与其它神经元同它之间的连接权有关系，状态变量宜接影响输入变量，使系统变成一个随时间变化的动态系统。 连续型Hopfield神经网络在网络的结构上与离散型相同，其状态方程在形 Nuv式上也一样。若定义网络中第j个神经元的总输入为，输出状态为，那jjj么网络的状态转移方程可写为: ,, (式1.10) vgugwx,,,,，，,jjijij,,i,, 其中g为S型函数，一般常用的有 ,,x gxe()1/(1),，1 g(x),th(,x)2 这两个函数的共同特点是。和x,,,。时，函数值饱和到两极，限x,，, vugg制了网络中状态及流动信息的增长范围。函数，中的以控制S,jj12 g型函数在零点附近的斜率变化。函数可看做符号函数。 2 在网络的整个运行过程中，所有节点状态的演变有异步、同步和连续更新三种形式。与离散Hopfield网络比较，多了一种连续更新的形式，表示网络中所有节点都随连续时间并行更新。网络中状态在一定范围内连续变化。 连续型hopfield神经网络在时间上是连续的。所以，网络中各神经元是处 u于同步方式工作的。考虑对于一个神经细胞，即神经元i，其内部膜电位状态用j 5 表示，生物神经元的动态(微分系统)由运算放大器来模拟，其中微分电路中细胞膜输入电容为Ci，细胞膜的传递电阻为Ri，输出电压为Vi，外部输入电流用表Ii示。神经元的状态满足如下动力学方程: n,dU(t)U(t)ii,,，，CWV(t)I,ijiji,,i1,2,...,ndtR,j,1i,,V(t)g(U(t))iii, (式1.11) 则连续型Hopfield神经网络模型可用图2所示的电路来模拟实现。 图2 连续型Hopfield神经网络的电路形式 电路中微分系统的暂态过程的时间常数通过电容Ci,和电阻Ri并联实现， T跨导模拟神经元之间互连的突触特性。 ij n()Vu,,duujiiiCI,，,，,ii,dtRR j,1iij, ,Vfu,，，ii, (式1.12) nduI11,ii,,，，uV,ij',dtRCRCC,1jiiijii, ,Vfu,，，ii, (式1.13) 其中: N111,，,'RRR,1 (式1.14) jiiij 6 I1'i,,,,,, (式1.15)vVRCw,,,iiiiijiRCCijii 可得到: n iiduu,,，，,ijjiwv,j,1, (式1.16) dt ，，v,fui,1,2,3,4,,,,,,Niii (式1.17) 先设定初态()，运行至稳定，得到稳定状态。对应输出: ui ，，u1iv,，1tani,,02u (公式1.18) ，， 微分方程(式1.12)反映了网络状态的连续更新的意义，随着时间的增长变化，网络逐渐趋于定态，在输出端可以得到稳定的输出。 三、实际应用 Hopfield神经网络有很多成功的应用，这种网络的主要应用形式有联想记忆和优化计算两种形式。用Hopfield网络解决具体的优化问题，需要按以下进行: 1(对于待定的问题，选择一种合适的表示方法，使得神经网络的输出与 问题的解对应起来; 2(构造神经元网络的能量函数，使其最小值对应于问题的最佳解; 3(由能量函数倒过来推出神经网络的结构; 4(由网络结构建立起网络，令其运行，那么稳定状态就是在一定条件下 问题的解。 对于TSP问题若用传统的穷举搜索法，则需要找出全部路径之组合，再对其进行比较，找到最佳路径。这种方法随着城市数目的增加，计算工作量急剧增加。这是用传统的串行计算机难以在有限时间内得到圆满解决的问题。在实际应用中，这类问题往往不要求得到严格的最优解，只要是接近最优的解就可以了。 开始首先把问题转化成适合于 7 Hopfield网络来解决TSP问题时体现了人脑的一些特征。开始首先把问题转化成适合于神经元网络处理的形式。对于n个城市的TSP问题，用一个"n×n”的神经元矩阵，用神经元的状态来表示某一个城市在某一条有效路径中的位置。 神经元的状态用，表示，其中:第X个城市用表示，而i?xvc,,x,1，2，？,nixix{1,2,?,n}表示城市在路径中是第i个城市。状态表示在路径中第i个ccv,1xxxi 位置出现;表示在第i个位置不出现，说明此时第i个位置上是其它城cv,0xxi 市。由此可见，n×n矩阵v可以表示n个城市TSP问题一次有效的路径，即v矩阵可以唯一地确定对于所有城市的访问次序。为了保证每个城市只去一次(出发点除外)，那么关联矩阵v上每一行只能有一个为1，其它必须为0，对应于每次访问而且只访问一个城市，所以对于关联矩阵的次序上，也是每一列只有一个元素为1，其它为0，全部非0元素的总和为n。例如n=6，则一次有效路径可能构成v矩阵如下表1所示。 表1 城市TSP问题中一次可能的路径 城市 1 2 3 4 5 6 次数 C10 0 0 1 0 0 C2 1 0 0 0 0 0 C3 0 0 1 0 0 0 C4 C50 1 0 0 0 0 C6 0 0 0 0 0 1 0 0 0 0 1 0 ,,,,,由上表可见，访问次序为，(最终再回到)。由CCCCCCC2412365 l访问次序就可得到路径的总长度，对于这个例子来说，路径的总长度为: 8 l,l，l，l，l，l2443311556 为了解决TSP问题，必须构成这样的网络:在网络运行时，计算能量降低。网络稳定后其输出状态代表城市被访问的次序，即构成表1所示的换位阵。网络能量的极小点对应于最佳或者较好的路径的形成，此时由输出换位阵能得到较好路径。 解决问题的关键一步是构成合适的能量函数。针对路径有效性，为了保证输出换位阵，因此有约束条件: nnnA,Evv (式2.1) ,,,1xixj2,,,,111,xijji 其中A>0为常数。保证当矩阵V的每一行不多于一个1时，达到最小EE11 =0。 E1min 同理构成列约束条件为 nnnB,Evv (式2.2) ,,,2xiyi2,,,,111,ixyyx 其中B>0为常数。保证当矩阵V的每一列不多于一个l时，达到最小EE22 =0。 E2min 构成全局约束 2nnC,,Evn,, (式2.3) 3xi2,,xi11 E其中C>0为常数。保证当矩阵V中的1的个数恰好为n时，即整个矩阵有n3 EE个1时，达到最小=0。 33min 式(2.1)、(2.2)和(2.3)之和达到最小时，能保证网络输出状态矩阵V构成换位阵。 考虑路径的合理性，此项定义中应包含有效路径的长度信息，此项定义为 nnnD,，()Elvvv (式2.4) ,,,4,1,1，,xyxiyiyi2,,,,111,xiyyx 9 其中D>0为常数。下标运算定义为类似于以下的取模运算 k，rk，r,n 若 ()kr，,n，k，rk，r,0 若 mod ,n，k，rk，r,n 若 r为模式平移量。表示一维模式平移r位，往左移r为正，往右移r为负。原模式x中的元素，现在移动为，。 xxxxiki，rk，r 这样从路径最后一个城市到第一城市的距离也包括在式(2.4)中。实际数E4值就是一次有效路径总长度的倍数。若路径为最佳时，达到最小点。若路径E4 为较好时，达到极小点。所以，构成用Hopfield神经网络求解TSP问题的能量E4 函数为: EEEEE,，，，4123 C2,，，,dvvvvn()(),,,,,,1,1xyxiyiyixi，,2xyxixi, AB，，vvvv,,,,,,xixjxiyi22xijiixyx,, (式2.5) 将上式和Hopfield神经网络电路标准能量函数公式 nnnn()Vt11i,1E(t),-WV(t)V(t)-V(t)I，g(V)dV,,,,jijiii,02R,,11,1,1ijiii (式2.6) yx相比较可得到神经元与之间的导纳值(相当于权系数)为: ji TABCDl,,,,,,,，,,,,,,,,(1)(1)()(1)xiyjxyijijxyxyjijixy,,,,,,1,1，, (式2.7) ,,其中和定义为: ijxy 1,ij,,,,i,j0其它, 其中偏流(外加激励)为 I,CN (式2.8) xi 10 将式(2.7)和(2.8)代入网络状态方程中，得到: ,,,dUUxixi()CAvBvCNDlvv,,,,,,,，,,,,,,,,,1,1，,xixjxjxyyiyidtR,,,,jiyxxyyxxi,,,()vgu,xixi, 其中为神经元的时空综合输入，为其对应的神经元的输出，两者关系为: uvxixi 当网络节点输出为连续型时 1vfu,,() xixi,,,u2xi，1exp,,u0,,当网络节点输出为离散型时: 1,0,uxi,v,xi0,0uxi, 其运行结果写入到Debug文件夹下的result.txt文件中。部分截图如下: 11