Hopfield神经网络优化方法

1、1第第10章章 Hopfield神经网络神经网络优化方法优化方法 Hopfield神经网络优化方法2Hopfield神经网络优化方法神经网络优化方法n10.1 人工神经网络模型人工神经网络模型n10.2 Hopfield神经网络神经网络n10.3 Hopfield网络与最优化问题网络与最优化问题 Hopfield神经网络优化方法3人工神经网络n人工神经网络是指由大量简单人工神经元互联而成的一种计算结构。它可以在某种程度上模拟生物神经系统的工作过程，从而具备解决实际问题的能力。n人工神经网络由于其大规模并行处理、学习、联想和记忆等功能，以及它高度的自组织和自适应能力，已成为解决许多工程问题的有力

2、工具，近年来得到了飞速的发展。 Hopfield神经网络优化方法4生物神经系统生物神经系统 n生物神经系统是一个有高度组织和相互作用的数目庞大的细胞组织群体。这些细胞被称为神经细胞，也称作神经元。 Hopfield神经网络优化方法5人工神经元模型人工神经元模型 n人工神经元是构成人工神经网络的基本单元，是对生物神经元特性及功能的一种数学抽象，通常为一个多输入单输出器件。 Hopfield神经网络优化方法6人工神经元模型人工神经元模型 n输入与输出信号输入与输出信号：s1、s2、.sn为输入，vi为输出。输出也称为单元的状态。 Hopfield神经网络优化方法7人工神经元模型人工神经元模型 n权

3、值：给不同的输入的信号一定的权值，用wij表示。一般权值为+表示激活，为-表示抑制； Hopfield神经网络优化方法8人工神经元模型人工神经元模型 n求和器：用表示，以计算各输入信号的加权和，其效果等同于一个线性组合； Hopfield神经网络优化方法9人工神经元模型人工神经元模型 n激活函数：图中的f()，主要起非线性映射作用，另外还可以作为限幅器将神经元输出幅度限制在一定范围内； Hopfield神经网络优化方法10人工神经元模型人工神经元模型 n阈值：控制激活函数输出的开关量，用i表示。 Hopfield神经网络优化方法11人工神经元模型人工神经元模型 n上述作用可用数学方式表示如下：

4、 1( )niijjjiiiiiuw sxuvf xi=1, 2, n 式中，sj为输入信号；wij为神经元i对输入信号sj的权值；ui为线性组合结果；i为阈值；f()为激活函数；vi为神经元i的输出。 Hopfield神经网络优化方法12激活函数的若干形式激活函数的若干形式 n（1）阈值函数，即阶跃函数 1 0( )sgn( )0 0 xf xxx于是神经元i的相应输出为： 01 00iiixvx式中， injjijiswx1 Hopfield神经网络优化方法13激活函数的若干形式激活函数的若干形式 n（2）分段线性函数 特点：类似于系数为1的非线性放大器，当工作于线性区时它是一个线性组合器

5、，放大系数趋于无穷大时变成一个阈值单元 111( )(1) 11210 xf xx xx Hopfield神经网络优化方法14激活函数的若干形式激活函数的若干形式 n（3）sigmoid函数 式中，c为大于0的参数，可控制曲线斜率 1( )1 exp()f xcx Hopfield神经网络优化方法1510.1.3 人工神经网络的互连模式人工神经网络的互连模式 n根据连接方式的不同，将现有的各类神经网络分为根据连接方式的不同，将现有的各类神经网络分为如下如下2种形式：种形式：前馈型网络前馈型网络 ，反馈型网络，反馈型网络（1）前馈型网络）前馈型网络 n各神经元接受前一层的输入，并输出给下各神经元

6、接受前一层的输入，并输出给下一层，没有反馈。一层，没有反馈。n结点分为两类，即输入单元和计算单元，结点分为两类，即输入单元和计算单元，每一计算单元可有任意个输入，但只有一每一计算单元可有任意个输入，但只有一个输出（它可耦合到任意多个其他结点作个输出（它可耦合到任意多个其他结点作为输入）。为输入）。n可分为不同的层，第可分为不同的层，第i-1层输出是第层输出是第i层的输层的输入，输入和输出结点与外界相连，而其他入，输入和输出结点与外界相连，而其他中间层称为隐层。中间层称为隐层。 主要起函数映射作用，常用于模式识别和函数逼近主要起函数映射作用，常用于模式识别和函数逼近 。 Hopfield神经网络

7、优化方法16（2）反馈型网络）反馈型网络 n所有结点都是计算单元，同时也可接受输入，并向外界输出。所有结点都是计算单元，同时也可接受输入，并向外界输出。n若总的单元数为若总的单元数为n，则每一个结点有，则每一个结点有n-1个输入、个输入、个输出，如图个输出，如图10-7 的的形式。形式。 反馈网络反馈网络按对能量函数极按对能量函数极小点的利用分为两类：小点的利用分为两类：一类是能量函数的所有极一类是能量函数的所有极小点都起作用，主要用作小点都起作用，主要用作各种各种联想存储器联想存储器；第二类只利用全局极小点，第二类只利用全局极小点，主要用于主要用于优化问题求解优化问题求解。Hopfield模

8、型、波尔兹曼模型、波尔兹曼机（机（BM）模型等可以完成）模型等可以完成此类计算。此类计算。 Hopfield神经网络优化方法1710.2 Hopfield神经网络神经网络 - HNN n网络中引入了反馈，所以它是一个非线性动力学系统 .n非线性动力学系统着重关心的是系统的稳定性问题。 n在Hopfield模型中，神经网络之间的联系总是设为的，这保证了系统最终会达到一个固定的有序状态，即稳定状态。 特点：特点： Hopfield神经网络优化方法18Hopfield网络基本结构网络基本结构: 其中，I1, I2,., In是外部对网络的输入；v1, v2,., vn是网络系统的输出；u1, u2,

9、 ., un是对相应神经元输入，wij是从第j个神经元对第i个神经元的输入的权值，wji=wij，wii=0。f()是特性函数，决定了网络是离散离散的还是连续连续的。 Hopfield神经网络优化方法19离散型离散型Hopfield网络网络 n定义定义：对图10-8中的特性函数f()取阈值函数（见图10-3）等硬限函数，使神经元的输出取离散值，就得到离散型离散型Hopfield神经网络神经网络。 n工作原理工作原理：设有n个神经元，v为神经网络的状态矢量，为第i个神经元的输出，输出取值为0或者为l的二值状态。对任一神经元i， 为第i个神经元的内部未加权输入，它们对该神经元的影响程度用连接权wi

10、j表示。 为第i个神经元的阈值。 i01 00iiixvx（10-6） ivj ijv Hopfield神经网络优化方法20离散型离散型Hopfield网络网络 n2种状态更新方式种状态更新方式：q异步方式异步方式：在任一时刻t，只有某一个神经元按式（10-6）发生变化，而其余n-1个神经元的状态保持不变。q同步方式同步方式：在任一时刻t，有部分神经元按式（10-6）变化（部分同步）或所有神经元按式（10-6）变化（全并行方式）。 一旦给出一旦给出Hopfield网络的权值和神经元的阈值，网络的权值和神经元的阈值，则网络的状态转移序列就确定了。则网络的状态转移序列就确定了。 Hopfield神

11、经网络优化方法21离散型离散型Hopfield网络网络 n定义定义10.1 若神经元i在更新过程中，输出变量v不再变化，则称神经元i已稳定稳定。若Hopfield网络从t=0的任意一个初始输出状态开始，存在一个有限的时间，此时间点后系统中所有神经元都是稳定的，即网络状态不再发生变化，则称该的，即： ，对所有 。 ()( )tttvv0t Hopfield神经网络优化方法22离散型离散型Hopfield网络网络 若神经网络的连接权矩阵W是零主对角元素的对称矩阵，即满足wij=wji且wii0，il，2，n，网络状态按串行异步方式更新，则网络必收敛于状态空间中的某一稳定状态。 如果网络是稳定的，则

12、在满足一定的参数条件下，某种能量函数在网络运行过程中是不断降低并最后趋于稳定平衡状态的网络网络中任意一个神经元节点状态发生变化时，能量中任意一个神经元节点状态发生变化时，能量E都将减小都将减小。 Hopfield神经网络优化方法23能量函数与稳定性能量函数与稳定性iviviEiEiE假设第i个神经元节点状态的变化量记为，相应的能量变化量记为。能量随状态变化而减小意味着总是负值。考察两种情况：iviv由0变为1时，0，必有xi0。（1）当状态由1变为0时，0，必有xi0。 （2）当状态iviv可见iv与xi的积总是正正的。 iEiv)(nijijijvwiv=-xi=故节点i的能量可定义为： n

13、ijiijijivvwE)(对于离散型网络方程，Hopfield将网络整体能量函数定义为： iiininijjiijvvvwtE121)( Hopfield神经网络优化方法24能量函数与稳定性能量函数与稳定性n容易证明它满足Lyapunov函数的三个条件：函数函数连续可导；函数正定以及；函数的导数半连续可导；函数正定以及；函数的导数半负定。负定。 从iijjijivwvVE)(可以看出E对于所有V的分量是连续的。 严格来说，式（10-9）并不能满足Lyapunov函数的正定条件。但是，对于神经元有界的神经网络的稳定性来说，正定条件可以退化为只要求该函数有界。即前面已讨论过的即前面已讨论过的“E

14、随状态变化而严格随状态变化而严格单调递减单调递减” Hopfield神经网络优化方法25能量函数与稳定性能量函数与稳定性nW和 （由n个i构成的列向量）都是有确定值的矩阵和向量，且 有界，因此E有下界： n因为式（10-9）的E是有界函数，从而可知式（10-9）是正定的，即网络将最终达到稳定状态网络将最终达到稳定状态。niininjijwE111min21订正：P155 Hopfield神经网络优化方法26能量函数与稳定性能量函数与稳定性 离散Hopfield模型的稳定状态与能量函数E在状态空间的局部极小点是一一对应的。 需要指出：一般在Hopfield神经网络中，能量函数可能存在局部最小值，

15、如图10-9所示。 Hopfield神经网络优化方法27能量函数与稳定性能量函数与稳定性例例10-1 试计算一个有8个神经元的离散Hopfield网络， 其网络权值W和阈值向量如下： 023. 015. 0065. 005. 053. 022. 017. 023. 0081. 070. 014. 077. 030. 024. 015. 081. 0015. 032. 026. 061. 078. 0065. 070. 015. 0066. 019. 058. 063. 005. 014. 032. 066. 0010. 047. 033. 053. 077. 026. 019. 010. 00

16、91. 045. 022. 030. 061. 058. 047. 091. 0055. 017. 024. 078. 063. 033. 045. 055. 00W0.650.30.40.750.150.250.950.35 试确定网络最后的平衡状态。 Hopfield神经网络优化方法28能量函数与稳定性能量函数与稳定性例例10-1 试计算一个有8个神经元的离散Hopfield网络， 其网络权值W和阈值向量如下： 解：解：1计算步骤如下：（1）按式（10-9）确定如下能量函数： iiininijjiijvvvwE121（2）随机选取神经元i，按下式判断该神经元输出状态vi（即采用了阈值为0的

17、双极硬限函数），按串行工作方式，直至状态不变，计算终止： niijjij ixw vniijjij ixw v若神经元i的状态 0，则取vi=1若记忆模式较少，同时模式之间的差异较大，则联想的结果就比较正确；而当需记忆的模式较多时，网络到达的稳定状态往往不是己记忆的模式，亦即容易引起混淆； 再者，当模式间差异较小时，网络可能无法辨别出正确的模式，此时即便采用已记忆的模式作为联想模式（自联想），也仍可能出错，如本例所示。注意：本例m1和m2是该网络的两个稳定状态。可验证，对于该网络的其余6个网络状态中的任何一个，都可在一次运行后收敛于这两个状态中的一个。解毕。 Hopfield神经网络优化方法3

18、610.2.3 连续型连续型Hopfield网络网络n将离散的Hopfield神经网络模型扩展到连续时间的动力学模型，其网络的连接方式不变，仍然是全互连对称结构，特性函数f()选用Sigmoid函数，使神经元的输出取连续值。连续的Hopfield网络可与一电子线路对应，如图10-10所示。 Hopfield神经网络优化方法3710.2.3 连续型连续型Hopfield网络网络n图10-11表示由运算放大器实现的一个节点的模型。 对于该模型，其电路方程可写为： 1( )njiiiiijiijiivuduuCIdtRRvf u（10-12） Hopfield神经网络优化方法38式中，iI为系统的外

19、部激励。经过整理，得： 1( )njiiijiiijiiiivduuIdtR CR CCvf u （10-13） 式中， njijiiRRR1111令 1,iiiijiijiiIRC wR CC，有： )(11iiinjjijiiufvvwudtdu Hopfield神经网络优化方法39定义定义10.2 对式（10-14）的连续Hopfield网络，其能量函数E(t)为( )1011111( )( )2innnnv tijijiiij iiiE tw vvvfx dx （10-15） 证明式（10-15）表示的能量函数满足李雅普诺夫函数的前两个条件是很容易的事。第三个条件的满足则可用式（10-

20、15）推导得到。从式（10-15）不难看出： dtduvwudvdEinijijijii)(连续连续Hopfield网络收敛性网络收敛性（10-16） 于是， niiiiiniiiiniiiniiidtdvdvdudtdvdtdvdvdudtdvdtdudtdvdvdEdtdE12111)()(iiufv 为Sigmoid函数时，其逆函数 )(1iivfu为非减函数，即 当 Hopfield神经网络优化方法400)(1iiiivfdvddvdu（10-18） 0dtdE故 。 注意，式（10-15）的最后一项在Sigmoid函数值高增益下由于接近限幅器而可以忽略不计。 Hopfield神经网络

21、优化方法41对于连续Hopfield网络，如果f- -1()为单调递增的连续函数，Ci0，wij= wji，则沿系统运动轨道有 0dtdE（10-19） 0dtdui0dtdE当且仅当时，(i=1,2,n) 由定理10.2可知，连续Hopfield网络随时间推移其能量函数总是在不断地减少。网络的平衡点就是E(t)的极小值点。 Hopfield神经网络优化方法42连续连续Hopfield网络的工作方式有如下网络的工作方式有如下结论：结论： n系统过程从任意非平衡状态出发，最终收敛于平衡状态，平衡点有限。如果平衡点是稳定的，那么一定是渐近稳定的。渐近稳定平衡点为其能量函数的极小点；n通过适当的学习

22、，该网络能将任意一级正交矢量存储起来作为渐近稳定平衡点；n连续Hopfield网络的信息存储表现为神经元之间互连的分布动态存储；n连续Hopfield网络以大规模非线性连续时间并行方式处理信息，其计算时间就是系统趋于平衡点的时间。 Hopfield神经网络优化方法43连续连续Hopfield网络神经网络迭代过程网络神经网络迭代过程的框图的框图 初始化在每个周期（扫描）重复下列步骤：是否到达稳定状态随机抽取一个在此周期中尚未更新的神经元。 vi+=sgm( ui+)。停止否是injjijiiiivwtudvdEtuu1计算 Hopfield神经网络优化方法4410.3 Hopfield网络与最优

23、化问题网络与最优化问题 n如果把一个动态系统的稳定点视为个能量函数的极小点，而把能量函数视为一个优化问题的目标函数，那么从初态朝这个稳定点的演变过程就是一个求解该优化问题的过程。n反馈网络用于优化计算和作为联想存储这两个问题是对偶的：用于优化计算时权矩阵W已知，目的是寻找E以达到最小的稳定状态；而作联想存储时稳定状态则是给定的（对应于待存的模式向量），要通过学习来寻找合适的W。 Hopfield神经网络优化方法45旅行商问题（旅行商问题（TSP） n给定N个城市和它们两两之间的直达距离，找出一个闭合旅程，使每个城市只经过一次，且总的旅行距离必须为最短。nHopfield与Tank将N城市TSP

24、问题映射到连续Hopfield网络中，通过这N个城市的一个旅程旅程次序表次序表给出问题的一个可行解。n在旅程次序表中，一个旅程的城市次序由一组神经元的输出状态表示。建立能量方程使最优旅程次序表对应网络的稳定终止状态。 Hopfield神经网络优化方法46旅行商问题（旅行商问题（TSP）n对一个N城市的TSP问，因为有N个城市，并对应有N种次序，所以要有NN个神经元。n在图10-13（a）给出了一个路径，其旅程总距离d为d=dBH+dHS+dSG+dGC+dCX+dXB，其中B是第一个被访问的，随后依次为H、S、G、C和X。这里，dIJ表示从I市到J市的直达距离。 Hopfield神经网络优化方

25、法47旅行商问题（旅行商问题（TSP）n用换位矩阵来表示TSP一条路径的方法 ：在该矩阵中，每一列只有一个元素为l，其余为0，列的大小表示对某城市访问的次序。同样每一行也只有一个元素为1，其余为0。通过这样的矩阵，可惟一地确定一条旅行路线。 Hopfield神经网络优化方法48对于用Hopfield网络来求解TSP问题，就是要恰当地构造一个能量函数，使得Hopfield网络中的n个神经元能够求得问题的解，并使其能量处于最低状态。为此，构造能量函数需考虑以下两个问题：（1）能量函数要具有适合于换位矩阵的稳定状态（约束条件）。（2）能量函数要有利于表达在TSP所有合法旅行路线中最短路线的解（目标函

26、数）。能量函数的合法形式可以通过考虑神经元的输出是0或1来实现。先考虑第（2）个问题。 定义优化目标函数为： )(21min)(1,1,xxyiyiyixixyvvvdvJ Hopfield神经网络优化方法49旅行商问题（旅行商问题（TSP）xxyiyiyixixyvvvdvJ )(21)(min1,1,xjxjjixivvvJ0)(1ixyixyxivvvJ0)(2xixiNvvJ0)()(23TSP可表示为如下优化问题： （10-21）（10-22）（10-23）(10-24) s.t.纠正P162yj Hopfield神经网络优化方法50旅行商问题（旅行商问题（TSP）写在一起，其目标函

27、数为 xiiyiyxyxixyxixiixxyyixixiijxjxivvvdD nvCvvBvvAE)(22221,1,2（10-25） 此即描述TSP的Hopfield神经网络的能量函数。 纠正P162yj Hopfield神经网络优化方法51旅行商问题（旅行商问题（TSP）比较式（10-25）与式（10-15）同一变量两端的系数，可得到网络连接权和阈值的表达式（这里需要注意的是，因为网络是二维的，每个变量有两个下标，而且求和符号也相应增加一倍）： CnDdCBATxiijijxyxyijijxyyjxi)()1 ()1 (1,1,（10-26） ijjiji ij, 0, 1式中，为Kr

28、onecker函数，纠正P163xi,yj-Cn Hopfield神经网络优化方法52旅行商问题（旅行商问题（TSP）相应的神经网络动力学方程为 )2exp(11)()()(01,1,uuufvvvdDnvCvBvAudtduxixixiijxyxyiyiyxyyjyjyixjxixi（10-27） 选择合适的参数A，B，C，D和初始状态0u，用式（10-27）引导网络状态的变化，就可得到用其稳定的网络状态所表示的TSP的最优解。 纠正P163 Hopfield神经网络优化方法53二分图最优化问题二分图最优化问题 定义：给定n（n为偶数）个节点，选择任意两节点进行相互连线，由此连成一个线图；对

29、于此线图，用分割线将所有节点分为二等份，从而获得一个二分图，要求该分割线跨越这两组之间的连线最少。如图10-14的线图中，给出了两种不同的分割方式，分割1有10条跨越连线，分割2有2条跨越连线（此为最小值）。二分图问题的在超大规模集成电路（VLSI）的布线设计中有广泛应用。 图10-14 二分图示例 Hopfield神经网络优化方法54二分图最优化问题二分图最优化问题 可用如下连接矩阵表示图10-14的连接方式： 0110000000100100000010011000000110100001001101000100001010010000010101000000101100000001010

30、000111110 W（10-28） 1 , 0 , iji jwi j相连不连式中， 纠正P164 Hopfield神经网络优化方法55二分图最优化问题二分图最优化问题 记分割节点后形成的两个区为A和B，定义一个在节点i处的神经元为： 式中，n是节点数，是一个常数（拉格朗日参数），且wij=cij- 。 1 1 iiAviB（10-30） 这一问题的Hopfield网络能量函数为： （10-31） ijijjiniiijijjiwvvnvcvvE212)(22121纠正P164 Hopfield神经网络优化方法56二分图最优化问题二分图最优化问题可证明该函数是李雅普诺夫函数。1niijjjidEuw vdv （1