Hopfield神经网络优化方法.ppt

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