Hopfield神经网络在TSP问题中的应用

Hopfield神经网络在TSP问题中的应用摘要：首先介绍了人工神经网络，并给出了一种神经元数学模型。对其中的Hopfield神经网络模型进行了描述，分别对离散型和连续型的工作原理作了详细介绍。结合Hopfield算法在求解TSP问题中的应用，总结出Hopfield神经网络应用于TSP优化问题的步骤。最后通过编程对TSP问题求解，得出了准确结果。关键词：人工神经网络；Hopfield神经网络；能量函数；TSP中图分类号：TP301.6HopfieldneuralnetworkintheapplicationofTSPProblemAbstract：Firstthispaperintroducedtheartificialneuralnetwork,andpresentsamathematicalmodelofneurons.ThendescribetheHopfieldneuralnetworkmodel,andintroducethediscreteandcontinuousWorkingprincipleindetailrespectively.FromAnalysisoftheHopfieldalgorithmforTSPApplications,wesummeduptheHopfieldneuralnetworkappliedtoTSPoptimizationsteps.Finally,throughtheprogramtosolvetheTSPproblem,wedrawtheaccurateresult.Keywords：ArtificialNeuralNetworks；Hopfieldneuralnetwork；Energyfunction；TSP1人工神经网络“神经网络”或“人工神经网络”是指用大量的简单计算单元(即神经元)构成的非线性系统，它在一定程度和层次上模仿了人脑神经系统的信息处理、存储及检索功能，因而具有学习、记忆和计算等智能处理功能。神经网络具有一些显著的特点：具有非线性映射能力；不需要精确的数学模型；擅长从输入输出数据中学习有用知识；容易实现并行计算；由于神经网络由大量简单计算单元组成，因而易于用软硬件实现；等等。正因为神经网络是一种模仿生物神经系统构成的新的信息处理模型，并具有独特的结构，所以人们期望它能解决一些用传统方法难以解决的问题。人的大脑是由大量神经细胞或神经元组成的。每个神经元可以看作为一个小的处理单元，这些神经元按照某种方式相互连接起来，构成大脑内部的生理神经元网络系统，他们中各个神经元之间连接的强弱不是固定不变的，而是按照外部的信号激励程度做自适应的变化，而每个神经元又随着接收到的多个激励信号的综合大小呈现兴奋或抑制状态。大脑的学习过程就是神经元之间连接强度随外部激励信号做自适应变化的过程。大脑处理信息的结果由神经元状态表现出来。由此见，神经元是信息处理的最小单位。神经元虽然类型很多，但其基本结构是相似的。神经元，也就是神经细胞，由细胞体、树突、轴突和突触组成。从细胞体上伸出许多树突和一条长的轴突，树突和轴突分别负责传入和传出兴奋或抑制信号到细胞体。神经元的树突短而且分支很多，是信号的输入端；轴突较长，是信号的输出端，其未端化为许多细小的分支，称为神经术梢。一个神经元通过轴突与其它细胞的树突相连。神经术梢与树突接触的界面称为突触，它是一个神经元与另一个神经元联系的特殊结构部位，突触包括突触前(成分)、突触间隙和突触后(成分)三个部分。突触前(成分)是第一个神经元的轴突术梢部分，而突出后(成分)是第二个神经元的受体表面。突触前(成分)通过化学接触或电接触，将信号传往突触后(成分)的受体表面，实现神经元之间的信息传输。树突和轴突一一对接，从而靠突触把众多的神经元连接成一个神经元网络。神经元群或者神经网络系统对外界有兴奋或抑制两种反应，兴奋指的是由相对静止变为相对活动，而抑制则是指由相对活动变为相对静止。神经元之间的信息传递有正负两种连接。正连接相互激发，负连接相互抑制。各个神经元之间的连接强度和极性可以有所不同，并且都可以进行调整，因此人脑才可以有存储信息的功能。神经元的数学模型有很多，下面给出了一个简化的神经元数学模型，如图1.1所示。图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)当神经元没有内部状态时，可令iy=iu，()()fg。通常的情况是有is的。此时，每一个神经元的输入接受前一级神经元的输出，因此，神经元i的总作用i为所有输入的加权和减去闭值(若无阈值则不减)，此作用引起神经元i的状态变化，而神经元i的输出iy为其当前状态i的函数。如果考虑到反映时间，那么必须用微分方程来表示神经元的状变化，在最简单的情况下(无阈值的情况下)，以下的式子成立：1iw2iwinw()iiijjijdwxtdt(式1.5)()(())iiytft(式1.6)此时神经元的状态与输入成比例，而且向某一个初态衰减。2HopField神经网络Hopfield网络是一种互连型网络的一种，它引入类似于Lyapunov函数的能量函数概念，把神经网络的拓扑结构(用连接权矩阵表示)与所求问题(用目标函数描述)相对应，并将其转换为神经网动力学系统的演化问题。其演变过程是一个非线性动力学系统，可以用一组非线性差分议程描述(离散型)或微分方程(连续型)来描述。系统的稳定性可用所谓的“能量函数”进行分析。在满足条件的情况下，某种“能量函数”的能量在网络运行过程中不断地减少，最后趋于稳定的平衡状态。因为人工神经网络的变换函数是一个有界函数，故系统的状态不会发生发散现象。目前，人工神经网络经常利用渐进稳定点来解决某些问题。如果把系统的稳定点视为一个记忆的话，那么从初态朝这个稳定点的演变过程就是一个寻找记忆的过程。如果把系统的稳定点视为一个能量函数的极小点，而把能量函数视为一个优化问题的目标函数，那么从初态朝这个稳定点的演变过程就是一个求解该优化问题的过程。因此，Hopfield神经网络的演变过程是一个计算联想记忆或求解优化问题的过程。实际上，它的解决并不需要真的去计算，而是通过构成反馈神经网络，适当地设计其连接权和输入就可以达到这个目的。2.1离散型HopField神经网络Hopfield最早提出的网络是二值神经网络，神经元的输出只取1和0两个值，也称为离散Hopfield网络。在离散Hopfield网络中，采用的神经元是二值神经元，输出的离散值1和0分别表示神经元处于激活和抑制状态。离散Hopfield神经网络是离散时间系统，它可以用一个加权无向图表示，图的每一边都有一个权值，图的每个节点都有一个阈值，网络的阶数相应于图中的节点数。Hopfield网络的基本结构如图2.1所示，这种网络是一种单层网络，令网络由n个单元组成，1N，2N，...，nN表示n个神经元，这些神经元既是输入单元，也是输出单元，其转移特性函数为1f，2f，...，nf，门限值(阈值)为1，2，...，n。图2.1Hopfield网络结构图对于离散型Hopfield网络，各节点一般选取同样的转移函数，且为符号函数，即：12()()()sgn()nfxfxfxx…(式2.1)为了分析方便，选取各节点的门限值(即阈值)全部为0，即：1=2=…=n=0(式2.2)同时，12(,,,){1,1}nnxxxxx…，为网络的输入；12(,,){1,1}nnyyyyy…，为网络的输出；12()((),(),,())(){1,1}nnvtvtvtvtvt…，为网络在t时刻的状态，其中t（0,1,2…）为离散时间变量；ijw为从iN到jN的连接权值，Hopfield神经网络是对称的，即有ijjiww，,(1,2,3,)ij…,n(式2.3)整个网络所有n个节点之间的连接强度用矩阵W表示，显然W为n×n方阵。由图2.1可见Hopfield网络为一层结构的反馈网络，能处理双极型离散数据（即输入x∈{-l，+1})，及二进制数据(x∈{0，1})。当网络经过训练后，可以认为网络处于等待工作状态，而对网络给定初始输入x时，网络就处于特定的初始状态，由此初始状态开始运行，可以得到网络输出即网络的下一状态。然后，这个输出状态通过反馈回送到网络的输入端，作为网络下一阶段运行的输入信号，而这个信号可能与初始信号x不同，由这个新的输入又可得到下一步的输出，这个输出也可能与上一步输出不同。如此下去，网络的整个运行过程就是上述反馈过程的重复。如果网络是稳定的，那么，随着许多次反馈运行，网络状态的变化减少，直到后来不再变化，达到稳定状态，此时，在网络的输出端可得到稳定的输出，可用以下公式表示为：(0)jjvx(1)()njjijjjjvtfwvt（式2.4）其中jf是由(2.1)定义，为方便，一般j值取0。从某个时刻t之后网络状态不再变迁，既有(1)()vtvt，那么，输出有()yvt（式2.5）网络神经元状态的演变有两种形式：·串行方式在某一时刻t，只有某一神经元N，的状态按照式(2.4)更新，而其余j-1个神经元状态保持不变，即1(1)sgn()nijiivtwvt（式2.6）对于某个特定的j单元来说，下式成立(1)()iivtvt(1,2,),iij…,n（式2.7）若以某种确定性次序来选择N，，使其按照(2.6)变化，称顺序更新；若按照预先设定的概率来选择神经元jN，，则称其为随机更新。·并行方式在任一时刻t，部分单元按(2.4)改变状态，其中有一种重要的特殊情况是在某时刻，所有神经元同时按照(2.4)改变状态，即：1(1)sgn()njijjivtwvt{1,2,}j…,n（式2.8）这时，可把状态转移方程写成向量形式：(1)sgn(())vtvtw（式2.9）2.2连续型Hopfield神经网络这种网络的每个神经元的输入与输出关系为连续可微的单调递增函数，它的每个神经元的输入是一个随时间变化的状态变量，它与外界输入和其他神经元来的信号有直接关系，同时也与其它神经元同它之间的连接权有关系，状态变量宜接影响输入变量，使系统变成一个随时间变化的动态系统。连续型Hopfield神经网络在网络的结构上与离散型相同，其状态方程在形式上也一样。若定义网络中第j个神经元jN的总输入为ju，输出状态为jv，那么网络的状态转移方程可写为：jjijijivgugwx（式2.10）其中g为S型函数，一般常用的有1()1/(1)xgxe)()(2xthxg这两个函数的共同特点是x。和x。时，函数值饱和到两极，限制了网络中状态jv及流动信息ju的增长范围。函数1g，2g中的参数以控制S型函数在零点附近的斜率变化。函数2g可看做符号函数。在网络的整个运行过程中，所有节点状态的演变有异步、同步和连续更新三种形式。与离散Hopfield网络比较，多了一种连续更新的形式，表示网络中所有节点都随连续时间并行更新。网络中状态在一定范围内连续变化。连续型hopfield神经网络在时间上是连续的。所以，网络中各神经元是处于同步方式工作的。考虑对于一个神经细胞，即神经元i，其内部膜电位状态用ju表示，生物神经元的动态(微分系统)由运算放大器来模拟，其中微分电路中细胞膜输入电容为Ci，细胞膜的传递电阻为Ri，输出电压为Vi，外部输入电流用iI表示。神经元的状态满足如下动力学方程：nit