Hopfield神经网络优化方法PPT课件

1,第10章Hopfield神经网络优化方法,.神经网络优化方法,2,Hopfield神经网络优化方法,10.1人工神经网络模型10.2Hopfield神经网络10.3Hopfield网络与最优化问题,.神经网络优化方法,3,人工神经网络,人工神经网络是指由大量简单人工神经元互联而成的一种计算结构。它可以在某种程度上模拟生物神经系统的工作过程，从而具备解决实际问题的能力。,人工神经网络由于其大规模并行处理、学习、联想和记忆等功能，以及它高度的自组织和自适应能力，已成为解决许多工程问题的有力工具，近年来得到了飞速的发展。,.神经网络优化方法,4,生物神经系统,生物神经系统是一个有高度组织和相互作用的数目庞大的细胞组织群体。这些细胞被称为神经细胞，也称作神经元。,.神经网络优化方法,5,人工神经元模型,人工神经元是构成人工神经网络的基本单元，是对生物神经元特性及功能的一种数学抽象，通常为一个多输入单输出器件。,.神经网络优化方法,6,人工神经元模型,输入与输出信号：s1、s2、.sn为输入，vi为输出。输出也称为单元的状态。,.神经网络优化方法,7,人工神经元模型,权值：给不同的输入的信号一定的权值，用wij表示。一般权值为+表示激活，为-表示抑制；,.神经网络优化方法,8,人工神经元模型,求和器：用表示，以计算各输入信号的加权和，其效果等同于一个线性组合；,.神经网络优化方法,9,人工神经元模型,激活函数：图中的f()，主要起非线性映射作用，另外还可以作为限幅器将神经元输出幅度限制在一定范围内；,.神经网络优化方法,10,人工神经元模型,阈值：控制激活函数输出的开关量，用i表示。,.神经网络优化方法,11,人工神经元模型,上述作用可用数学方式表示如下：,i=1,2,n,式中，sj为输入信号；wij为神经元i对输入信号sj的权值；ui为线性组合结果；i为阈值；f()为激活函数；vi为神经元i的输出。,.神经网络优化方法,12,激活函数的若干形式,（1）阈值函数，即阶跃函数,于是神经元i的相应输出为：,式中，,.神经网络优化方法,13,激活函数的若干形式,（2）分段线性函数,特点：类似于系数为1的非线性放大器，当工作于线性区时它是一个线性组合器，放大系数趋于无穷大时变成一个阈值单元,.神经网络优化方法,14,激活函数的若干形式,（3）sigmoid函数,式中，c为大于0的参数，可控制曲线斜率,.神经网络优化方法,15,10.1.3人工神经网络的互连模式,根据连接方式的不同，将现有的各类神经网络分为如下2种形式：前馈型网络，反馈型网络,（1）前馈型网络,各神经元接受前一层的输入，并输出给下一层，没有反馈。结点分为两类，即输入单元和计算单元，每一计算单元可有任意个输入，但只有一个输出（它可耦合到任意多个其他结点作为输入）。可分为不同的层，第i-1层输出是第i层的输入，输入和输出结点与外界相连，而其他中间层称为隐层。,主要起函数映射作用，常用于模式识别和函数逼近。,.神经网络优化方法,16,（2）反馈型网络,所有结点都是计算单元，同时也可接受输入，并向外界输出。若总的单元数为n，则每一个结点有n-1个输入、个输出，如图10-7的形式。,反馈网络按对能量函数极小点的利用分为两类：一类是能量函数的所有极小点都起作用，主要用作各种联想存储器；第二类只利用全局极小点，主要用于优化问题求解。Hopfield模型、波尔兹曼机（BM）模型等可以完成此类计算。,.神经网络优化方法,17,10.2Hopfield神经网络-HNN,网络中引入了反馈，所以它是一个非线性动力学系统.非线性动力学系统着重关心的是系统的稳定性问题。在Hopfield模型中，神经网络之间的联系总是设为对称的，这保证了系统最终会达到一个固定的有序状态，即稳定状态。,特点：,.神经网络优化方法,18,Hopfield网络基本结构:,其中，I1,I2,.,In是外部对网络的输入；v1,v2,.,vn是网络系统的输出；u1,u2,.,un是对相应神经元输入，wij是从第j个神经元对第i个神经元的输入的权值，wji=wij，wii=0。f()是特性函数，决定了网络是离散的还是连续的。,.神经网络优化方法,19,离散型Hopfield网络,定义：对图10-8中的特性函数f()取阈值函数（见图10-3）等硬限函数，使神经元的输出取离散值，就得到离散型Hopfield神经网络。工作原理：设有n个神经元，v为神经网络的状态矢量，为第i个神经元的输出，输出取值为0或者为l的二值状态。对任一神经元i，为第i个神经元的内部未加权输入，它们对该神经元的影响程度用连接权wij表示。为第i个神经元的阈值。,（10-6）,.神经网络优化方法,20,离散型Hopfield网络,2种状态更新方式：异步方式：在任一时刻t，只有某一个神经元按式（10-6）发生变化，而其余n-1个神经元的状态保持不变。同步方式：在任一时刻t，有部分神经元按式（10-6）变化（部分同步）或所有神经元按式（10-6）变化（全并行方式）。,一旦给出Hopfield网络的权值和神经元的阈值，则网络的状态转移序列就确定了。,.神经网络优化方法,21,离散型Hopfield网络,定义10.1若神经元i在更新过程中，输出变量v不再变化，则称神经元i已稳定。若Hopfield网络从t=0的任意一个初始输出状态开始，存在一个有限的时间，此时间点后系统中所有神经元都是稳定的，即网络状态不再发生变化，则称该系统是稳定的，即：，对所有。,.神经网络优化方法,22,离散型Hopfield网络,定理10.1若神经网络的连接权矩阵W是零主对角元素的对称矩阵，即满足wij=wji且wii0，il，2，n，网络状态按串行异步方式更新，则网络必收敛于状态空间中的某一稳定状态。能量函数与稳定性之间的关系：如果网络是稳定的，则在满足一定的参数条件下，某种能量函数在网络运行过程中是不断降低并最后趋于稳定平衡状态的网络中任意一个神经元节点状态发生变化时，能量E都将减小。,.神经网络优化方法,23,能量函数与稳定性,故节点i的能量可定义为：,对于离散型网络方程，Hopfield将网络整体能量函数定义为：,.神经网络优化方法,24,能量函数与稳定性,容易证明它满足Lyapunov函数的三个条件：函数连续可导；函数正定以及；函数的导数半负定。,严格来说，式（10-9）并不能满足Lyapunov函数的正定条件。但是，对于神经元有界的神经网络的稳定性来说，正定条件可以退化为只要求该函数有界。,即前面已讨论过的“E随状态变化而严格单调递减”,.神经网络优化方法,25,能量函数与稳定性,W和（由n个i构成的列向量）都是有确定值的矩阵和向量，且有界，因此E有下界：因为式（10-9）的E是有界函数，从而可知式（10-9）是正定的，即网络将最终达到稳定状态。,订正：P155,.神经网络优化方法,26,能量函数与稳定性,离散Hopfield模型的稳定状态与能量函数E在状态空间的局部极小点是一一对应的。需要指出：一般在Hopfield神经网络中，能量函数可能存在局部最小值，如图10-9所示。,.神经网络优化方法,27,能量函数与稳定性,例10-1试计算一个有8个神经元的离散Hopfield网络，其网络权值W和阈值向量如下：,试确定网络最后的平衡状态。,.神经网络优化方法,28,能量函数与稳定性,例10-1试计算一个有8个神经元的离散Hopfield网络，其网络权值W和阈值向量如下：,解：1计算步骤如下：（1）按式（10-9）确定如下能量函数：,（2）随机选取神经元i，按下式判断该神经元输出状态vi（即采用了阈值为0的双极硬限函数），按串行工作方式，直至状态不变，计算终止：,若神经元i的状态,0，则取vi=1,若记忆模式较少，同时模式之间的差异较大，则联想的结果就比较正确；而当需记忆的模式较多时，网络到达的稳定状态往往不是己记忆的模式，亦即容易引起混淆；再者，当模式间差异较小时，网络可能无法辨别出正确的模式，此时即便采用已记忆的模式作为联想模式（自联想），也仍可能出错，如本例所示。注意：本例m1和m2是该网络的两个稳定状态。可验证，对于该网络的其余6个网络状态中的任何一个，都可在一次运行后收敛于这两个状态中的一个。解毕。,.神经网络优化方法,36,10.2.3连续型Hopfield网络,将离散的Hopfield神经网络模型扩展到连续时间的动力学模型，其网络的连接方式不变，仍然是全互连对称结构，特性函数f()选用Sigmoid函数，使神经元的输出取连续值。连续的Hopfield网络可与一电子线路对应，如图10-10所示。,.神经网络优化方法,37,10.2.3连续型Hopfield网络,图10-11表示由运算放大器实现的一个节点的模型。,.神经网络优化方法,38,（10-13）,式中，,.神经网络优化方法,39,定义10.2对式（10-14）的连续Hopfield网络，其能量函数E(t)为,（10-15）,证明式（10-15）表示的能量函数满足李雅普诺夫函数的前两个条件是很容易的事。第三个条件的满足则可用式（10-15）推导得到。从式（10-15）不难看出：,连续Hopfield网络收敛性,（10-16）,于是，,为Sigmoid函数时，其逆函数,为非减函数，即,当,.神经网络优化方法,40,（10-18）,故,。,注意，式（10-15）的最后一项在Sigmoid函数值高增益下由于接近限幅器而可以忽略不计。,.神经网络优化方法,41,定理10.2对于连续Hopfield网络，如果f-1()为单调递增的连续函数，Ci0，wij=wji，则沿系统运动轨道有,（10-19）,当且仅当,时，,，(i=1,2,n),由定理10.2可知，连续Hopfield网络随时间推移其能量函数总是在不断地减少。网络的平衡点就是E(t)的极小值点。,.神经网络优化方法,42,连续Hopfield网络的工作方式有如下结论：,系统过程从任意非平衡状态出发，最终收敛于平衡状态，平衡点有限。如果平衡点是稳定的，那么一定是渐近稳定的。渐近稳定平衡点为其能量函数的极小点；通过适当的学习，该网络能将任意一级正交矢量存储起来作为渐近稳定平衡点；连续Hopfield网络的信息存储表现为神经元之间互连的分布动态存储；连续Hopfield网络以大规模非线性连续时间并行方式处理信息，其计算时间就是系统趋于平衡点的时间。,.神经网络优化方法,43,连续Hopfield网络神经网络迭代过程的框图,计算,.神经网络优化方法,44,10.3Hopfield网络与最优化问题,如果把一个动态系统的稳定点视为个能量函数的极小点，而把能量函数视为一个优化问题的目标函数，那么从初态朝这个稳定点的演变过程就是一个求解该优化问题的过程。反馈网络用于优化计算和作为联想存储这两个问题是对偶的：用于优化计算时权矩阵W已知，目的是寻找E以达到最小的稳定状态；而作联想存储时稳定状态则是给定的（对应于待存的模式向量），要通过学习来寻找合适的W。,.神经网络优化方法,45,旅行商问题（TSP）,给定N个城市和它们两两之间的直达距离，找出一个闭合旅程，使每个城市只经过一次，且总的旅行距离必须为最短。Hopfield与Tank将N城市TSP问题映射到连续Hopfield网络中，通过这N个城市的一个旅程次序表给出问题的一个可行解。在旅程次序表中，一个旅程的城市次序由一组神经元的输出状态表示。建立能量方程使最优旅程次序表对应网络的稳定终止状态。,.神经网络优化方法,46,旅行商问题（TSP）,对一个N城市的TSP问，因为有N个城市，并对应有N种次序，所以要有NN个神经元。在图10-13（a）给出了一个路径，其旅程总距离d为d=dBH+dHS+dSG+dGC+dCX+dXB，其中B是第一个被访问的，随后依次为H、S、G、C和X。这里，dIJ表示从I市到J市的直达距离。,.神经网络优化方法,47,旅行商问题（TSP）,用换位矩阵来表示TSP一条路径的方法：,在该矩阵中，每一列只有一个元素为l，其余为0，列的大小表示对某城市访问的次序。同样每一行也只有一个元素为1，其余为0。通过这样的矩阵，可惟一地确定一条旅行路线。,.神经网络优化方法,48,对于用Hopfield网络来求解TSP问题，就是要恰当地构造一个能量函数，使得Hopfield网络中的n个神经元能够求得问题的解，并使其能量处于最低状态。为此，构造能量函数需考虑以下两个问题：（1）能量函数要具有适合于换位矩阵的稳定状态（约束条件）。（2）能量函数要有利于表达在TSP所有合法旅行路线中最短路线的解（目标函数）。能量函数的合法形式可以通过考虑神经元的输出是0或1来实现。先考虑第（2）个问题。,定义优化目标函数为：,.神经网络优化方法,49,旅行商问题（TSP）,TSP可表示为如下优化问题：,（10-21）,（10-22）,（10-23）,(10-24),s.t.,纠正P162yj,.神经网络优化方法,50,旅行商问题（TSP）,写在一起，其目标函数为,（10-25）,此即描述TSP的Hopfield神经网络的能量函数。,纠正P162yj,.神经网络优化方法,51,旅行商问题（TSP）,比较式（10-25）与式（10-15）同一变量两端的系数，可得到网络连接权和阈值的表达式（这里需要注意的是，因为网络是二维的，每个变量有两个下标，而且求和符号也相应增加一倍）：,（10-26）,式中，,为Kronecker函数，,纠正P163xi,yj-Cn,.神经网络优化方法,52,旅行商问题（TSP）,相应的神经网络动力学方程为,（10-27）,选择合适的参数A，B，C，D和初始状态,，用式（10-27）引导网络状态的变化，就可得到用其稳定的网络状态所表示的TSP的最优解。,纠正P163,.神经网络优化方法,53,二分图最优化问题,定义：给定n（n为偶数）个节点，选择任意两节点进行相互连线，由此连成一个线图；对于此线图，用分割线将所有节点分为二等份，从而获得一个二分图，要求该分割线跨越这两组之间的连线最少。如图10-14的线图中，给出了两种不同的分割方式，分割1有10条跨越连线，分割2有2条跨越连线（此为最小值）。二分图问题的在超大规模集成电路（VLSI）的布线设计中有广泛应用。,图10-14二分图示例,.神经网络优化方法,54,二分图最优化问题,可用如下连接矩阵表示图10-14的连接方式：,（10-28）,式中，,纠正P164,.神经网络优化方法,55,二分图最优