Artificial Neural Networks

Presentation on theme: "Artificial Neural Networks"— Presentation transcript:

1 Artificial Neural Networks
第六章 人工神经网络 (III) Artificial Neural Networks ANN by 谢广明 ， ~2006学年度第一学期

2 内 容 Hopfield NN DHNN CHNN HNN求解TSP 算法改进 算法混合 其它神经网络
内 容 Hopfield NN DHNN CHNN HNN求解TSP 算法改进 算法混合 其它神经网络 by 谢广明 ， ~2006学年度第一学期

3 John Joseph Hopfield Prof. of Molecular Biology
Princeton University, USA 掀起人工神经网络研究第二次热潮！ by 谢广明 ， ~2006学年度第一学期

4 Hopfield 网络 Hopfield 网络
1982年，Hopfield开创性地在物理学、神经生物学和计算机科学等领域架起了桥梁，提出了Hopfield 反馈神经网络模型(HNN)，证明在高强度连接下的神经网络依靠集体协同作用能自发产生计算行为。 与前向神经网络相比，后者有学习能力；前者具有联想记忆功能和解决优化问题的能力 by 谢广明 ， ~2006学年度第一学期

5 与前向神经网络比较 BP神经网络 Hopfield神经网络 by 谢广明 ， ~2006学年度第一学期

6 Hopfield 网络 Hopfield 网络 Hopfield 网络是典型的全连接网络
网络的状态满足一个非线性动力学方程，可表现出丰富的动态特性，如收敛，发散，极限环，混沌等。 by 谢广明 ， ~2006学年度第一学期

7 Hopfield 网络 Hopfield 网络 在一定的条件下，赋予网络某个初值，系统将迅速演化到某个静止状态，即所谓稳态。
稳态由各个神经元的连接权值确定，并不唯一 从不同的初值出发会演化到不同的稳态 可以构造一个状态的能量函数，并证明稳态对应的能量函数取极小 by 谢广明 ， ~2006学年度第一学期

8 Hopfield 网络 HNN 优化问题 网络的状态 优化问题的解 能量函数 目标值 稳态 极小点
by 谢广明 ， ~2006学年度第一学期

9 Hopfield 网络 1985 年Hopfield 和Tank 两人用连续HNN尝试解决TSP ，获得了成功.
其基本思想是把TSP问题映射到CHNN 网络中去, 使用换位矩阵表示有效路径,并设法用网络能量代表路径总长作用于反馈回路调节输入变化, 从而使得网络能量为最小———得到最短路径. 由于Hopfield 网络状态更新规则只能使能量函数往减小的这一个方向变化, 能量函数很容易陷入局部最小值,使得网络解不能够达到路径最优. 所以并不理想！ by 谢广明 ， ~2006学年度第一学期

10 DHNN 离散型Hopfield 网络采用差分方程描述，输出为二值型，网络采用全连接结构。
令 为各神经元的输出， 为各神经元与第 个神经元的连接权值， 为第 神经元的阈值，则有 by 谢广明 ， ~2006学年度第一学期

11 DHNN 对称网络 无自反馈网络 异步更新方式 同步更新方式 两个神经元相互影响的权重相同 神经元对自己的反馈为零
任意时刻只有一个神经元更新输出，其他神经元不变 同步更新方式 任意时刻所有神经元更新输出（全并行） 任意时刻部分神经元更新输出（部分同步） by 谢广明 ， ~2006学年度第一学期

12 DHNN 稳定输出 从某个初始输出开始，若存在一个有限时刻, 从该时刻后网络输出不再发生变化，则称网络进入稳定输出。
by 谢广明 ， ~2006学年度第一学期

13 DHNN 随机异步更新方式 任意时刻随机选择一个神经元更新输出，其他神经元不变 优点；算法容易实现，不需要同步机制，避免不同稳态以等概率出现
by 谢广明 ， ~2006学年度第一学期

14 DHNN 异步更新方式下的能量函数 也是构造一个关于状态的函数，定义其能量为 能量变化量为 这样随着网络的演变，能量总是在下降
by 谢广明 ， ~2006学年度第一学期

15 DHNN DHNN主要用途是联想记忆 每一种稳定输出对应一种模式，给定一个输出，令网络从其开始演化，则必然收敛到稳定输出，即某个模式上。
稳定输出的个数以及具体值可由网络的连接权值和阈值完全决定，应用的时候就要具体设计它们 by 谢广明 ， ~2006学年度第一学期

16 CHNN 连续型Hopfield 网络采用微分方程描述，输出取值也为连续型，仍然采用全连接结构。
by 谢广明 ， ~2006学年度第一学期

17 CHNN Hopfield用模拟电路设计CHNN by 谢广明 ， ~2006学年度第一学期

18 CHNN 根据电路方程，CHNN的动态方程可简化描述如下： 其中g为Sigmoid函数 by 谢广明 ， ~2006学年度第一学期

19 CHNN 对称网络 同步更新方式 两个神经元相互影响的权重相同 任意时刻所有神经元更新输出（全并行）
by 谢广明 ， ~2006学年度第一学期

20 CHNN 构造能量函数 容易验证 注：这里实际上给出了如果先有能量函数，如何构造神经元的动态方程的方法
by 谢广明 ， ~2006学年度第一学期

21 CHNN 能量函数的导数为 by 谢广明 ， ~2006学年度第一学期

22 CHNN 随时间的增长，神经网络在状态空间中的轨迹总是向能量函数减小的方向变化，且网络的稳定点就是能量函数的极小点。
by 谢广明 ， ~2006学年度第一学期

23 CHNN求解TSP 利用CHNN求解TSP, 主要包含有两个问题 首先要把TSP的解表达成NN的状态
by 谢广明 ， ~2006学年度第一学期

24 TSP 问题回顾 给定n个城市以及两两城市之间的距离，求解一条从某个城市出发、不重复地遍历所有其它城市并最终又回到起始城市的最短路径。 数学描述 给定图G=(V,E), V为顶点集, E为边集，确定一条长度最短的Hamilton回路 by 谢广明 ， ~2006学年度第一学期

25 编码方案 置换矩阵表示 将一个旅程定义为一个置换矩阵M ,若城市 i 在第j 步访问，则矩阵元素mij = 1. 这种方法用n ×n 矩阵M 代表一条旅程, M有如下三个性质: 1) 矩阵中每一行有且仅有一个1 2) 矩阵中每一列有且仅有一个1 3) 所有元素之和为n by 谢广明 ， ~2006学年度第一学期

26 编码方案 例如：如下矩阵表示的解为 C->A -> E -> B -> D 1 2 3 4 5 A B C D E
B C D E by 谢广明 ， ~2006学年度第一学期

27 构造CHNN表示TSP的解 用一个包含n2个神经元的CHNN, 输出分别为v11,v12,…,vnn, 其中第一个下标表示城市的编号，第二个下标表示城市在解中的位置。 网络的输出取0或1，就可以表示TSP的解。 by 谢广明 ， ~2006学年度第一学期

28 目标函数的表示 TSP的目标函数用CHNN的状态可以为 但是直接作为能量函数不可以，否则必然所有节点输出为零即可，这显然不能的到TSP的解
by 谢广明 ， ~2006学年度第一学期

29 约束条件 行和为1 列和为1 所有元素和为n 注：以上三条为Hopfield最初提出的，有很大缺陷
by 谢广明 ， ~2006学年度第一学期

30 构造能量函数 采用Lagrange乘子法，有约束问题转化为无约束问题，得到能量函数为 其中 A,B,C,D为事先给定的正常数
by 谢广明 ， ~2006学年度第一学期

31 构造连接权重和阈值 根据公式 计算得到 其中 by 谢广明 ， ~2006学年度第一学期

32 下面干什么？ 若是硬件实现，那就随意设置初值开始算啦！ 若是软件仿真，那就编写程序算啦！ 最好多算几次！
by 谢广明 ， ~2006学年度第一学期

33 优点 速度快！ 其它好处似乎没有啦！ by 谢广明 ， ~2006学年度第一学期

34 缺点 理论上证明只能收敛到局部极小点，不能保证算法只有一个局部极小点 甚至收敛到不可行解 对参数非常敏感，稍微改变算法就不灵了！
改进余地非常大！ by 谢广明 ， ~2006学年度第一学期

35 算法设计 参数选择 D值大比较好 初始值选择 随机选择 S函数简化 离散化 by 谢广明 ， ~2006学年度第一学期

36 算法改进 大量的工作集中于修改Hopfield提出的能量函数 by 谢广明 ， ~2006学年度第一学期

37 算法改进 by 谢广明 ， ~2006学年度第一学期

38 算法混合 HNN+GA by 谢广明 ， ~2006学年度第一学期

39 算法混合 HNN+GA by 谢广明 ， ~2006学年度第一学期

40 其它神经网络 随机神经网络(RNN) 动态随机神经网络(DRNN) 脉冲耦合神经网络(PCNN) 混沌神经网络(CNN)
by 谢广明 ， ~2006学年度第一学期