Hopfield神经网络优化方法.ppt

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