人工神经网络及其应用教学提纲.ppt
人工神经网络及其应用第8章 人工神经网络及其应用神经网络（神经网络（neural networks，NN）生生物物神神经经网网络络(natural neural network,NNN):由由中中枢枢神神经经系系统统（脑脑和和脊脊髓髓）及及周周围围神神经经系系统统（感感觉觉神神经经、运运动动神神经经等等）所所构成的错综复杂的神经网络，其中最重要的是构成的错综复杂的神经网络，其中最重要的是脑神经系统脑神经系统。人人工工神神经经网网络络(artificial neural networks,ANN):模模拟拟人人脑脑神神经经系系统统的的结结构构和和功功能能，运运用用大大量量简简单单处处理理单单元元经经广广泛泛连连接接而而组组成成的人工网络系统。的人工网络系统。神经网络方法：神经网络方法：隐式隐式的的知识表示方法知识表示方法28.1.1 生物神经元的结构n人脑由一千多亿（人脑由一千多亿（1011亿亿 1014 亿）个神经细胞（神经元）交织亿）个神经细胞（神经元）交织在一起的网状结构组成，其中大在一起的网状结构组成，其中大脑皮层约脑皮层约140亿个神经元，小脑皮亿个神经元，小脑皮层约层约1000亿个神经元。亿个神经元。n 神经元约有神经元约有1000种类型，每个神经元大约与种类型，每个神经元大约与103 104个其他个其他神经元相连接，形成极为错综复杂而又灵活多变的神经网络。神经元相连接，形成极为错综复杂而又灵活多变的神经网络。n 人的智能行为就是由如此高度复杂的组织产生的。浩瀚的宇人的智能行为就是由如此高度复杂的组织产生的。浩瀚的宇宙中，也许只有包含数千忆颗星球的银河系的复杂性能够与大宙中，也许只有包含数千忆颗星球的银河系的复杂性能够与大脑相比。脑相比。68.1.1 生物神经元的结构（输入输入）（输出输出）神经冲动神经冲动生物神经元结构生物神经元结构78.1.1 生物神经元的结构n 工作状态：工作状态：l兴奋状态兴奋状态：细胞膜电位：细胞膜电位动作电位的阈值动作电位的阈值神经冲动神经冲动 l 抑制状态抑制状态：细胞膜电位细胞膜电位 0,wij=wji,则则 ；当且仅当；当且仅当 718.4.3 随机神经网络oHopfield神神经经网网络络中中，神神经经元元状状态态为为1是是根根据据其其输输入入是是否大于阈值确定的，是确定性的。否大于阈值确定的，是确定性的。o随随机机神神经经网网络络中中，神神经经元元状状态态为为1是是随随机机的的，服服从从一一定定的的概概率率分分布布。例例如如，服服从从玻玻尔尔兹兹曼曼(Boltzmann)、高高斯斯(Gaussian)、柯柯西西(Cauchy)分分布布等等，从从而而构构成成玻玻尔尔兹兹曼曼机、高斯机、柯西机等随机机。机、高斯机、柯西机等随机机。728.4.3 随机神经网络1.Boltzmann机机o 1985年年，加加拿拿大大多多伦伦多多大大学学教教授授欣欣顿顿(Hinton)等等人人借借助助统统计物理学的概念和方法，提出了计物理学的概念和方法，提出了Boltzmann机神经网络模型。机神经网络模型。o Boltzmann机机是是离离散散Hopfield神神经经网网络络的的一一种种变变型型，通通过过对对离离散散Hopfield神神经经网网络络加加以以扰扰动动，使使其其以以概概率率的的形形式式表表达达，而而网网络络的的模模型型方方程程不不变变，只只是是输输出出值值类类似似于于Boltzmann分分布布以概率分布取值。以概率分布取值。o Boltzmann机是按机是按Boltzmann概率分布动作的神经网络。概率分布动作的神经网络。738.4.3 随机神经网络1.Boltzmann机机（续）（续）o 离散Hopfield神经网络的输出：o Boltzman机的内部状态：o 神经元 输出值为0和1时的概率：748.4.3 随机神经网络1.Boltzmann机机（续）（续）o Boltzmann的能量函数：神经元 状态转换时网络能量的变化：神经元 改变为状态“1”的概率：)exp(11TEpiiD-+=75 2.高斯机高斯机 8.4.3 随机神经网络 :均值为均值为0的高斯随机变量（白噪声）的高斯随机变量（白噪声），其方差为，其方差为3.柯西机柯西机 :柯西随机变量（有色噪声）柯西随机变量（有色噪声）768.4.4 混沌神经网络1.混沌混沌o 混沌：自然界中一种较为普遍的非线性现象，其行 为看似混乱复杂且类似随机，却存在精致的内在规 律性。o 混沌的性质：（1）随机性：类似随机变量的杂乱表现。（2）遍历性：不重复地历经一定范围内的所有状态。（3）规律性：由确定性的迭代式产生。771.混沌混沌（续）（续）o混沌学的研究热潮开始于20世纪70年代初期。o1963年，Lorenz在分析气候数据时发现：初值十分接近的两条曲线的最终结果会相差很大，从而获得了混沌的第一个例子。o1975年，Li-Yorke的论文周期3意味着混沌使“混沌”一词首先出现在科技文献中。混沌的发现，对科学的发展具有深远的影响。8.4.4 混沌神经网络788.4.4 混沌神经网络2.混沌神经元混沌神经元 o 混沌神经元（混沌神经元（1987年，年，Freeman）：构造混沌神经）：构造混沌神经网络的基本单位。网络的基本单位。混沌神经元模型：混沌神经元模型：798.4.4 混沌神经网络3.混沌神经网络混沌神经网络 o 1990年，年，Aihara等提出了第一个混沌神经网络模等提出了第一个混沌神经网络模型型(chaotic neural network，CNN)。o 1991年，年，Inoue等利用两个混沌振荡子耦合成一个等利用两个混沌振荡子耦合成一个神经元的方法，构造出一个混沌神经计算机神经元的方法，构造出一个混沌神经计算机.o 1992年，年，Nozawa基于欧拉离散化的基于欧拉离散化的Hopfield神经神经网络，通过增加一个大的自反馈项，得到了一个与网络，通过增加一个大的自反馈项，得到了一个与Aihara等提出的类似的等提出的类似的CNN模型。模型。808.4.4 混沌神经网络 3.混沌神经网络混沌神经网络（1）基于模拟退火策略的自抑制混沌神经网络）基于模拟退火策略的自抑制混沌神经网络 1995年，年，Chen等提出的暂态混沌神经网络等提出的暂态混沌神经网络(transient chaotic neural network，TCNN)：818.4.4 混沌神经网络 3.混沌神经网络混沌神经网络（1）基于模拟退火策略的自抑制混沌神经网络）基于模拟退火策略的自抑制混沌神经网络 具有具有暂态混沌特性暂态混沌特性。能演化到一个稳定状态。能演化到一个稳定状态。搜索区域为一分形结构。搜索区域为一分形结构。具有混沌退火机制。具有混沌退火机制。一种广义的混沌神经网络。一种广义的混沌神经网络。可求解可求解0-1问题，也可求解连续非线性优化问题。问题，也可求解连续非线性优化问题。828.4.4 混沌神经网络o非线性函数：非线性函数：838.4.4 混沌神经网络 3.混沌神经网络混沌神经网络（2）基于加大时间步长的混沌神经网络）基于加大时间步长的混沌神经网络 oCHNN的欧拉离散化：的欧拉离散化：1998年，年，Wang和和Smith采用加大时间步长产生混沌：采用加大时间步长产生混沌：848.4.4 混沌神经网络 3.混沌神经网络混沌神经网络（3）引入噪声的混沌神经网络）引入噪声的混沌神经网络 o1995年，年，Hayakawa等的混沌神经网络：等的混沌神经网络：858.5 Hopfield神经网络的应用8.5.1 Hopfield神经网络在联想记忆中的应用神经网络在联想记忆中的应用8.5.2 Hopfield神经网络优化方法神经网络优化方法86如何实现如何实现HNN的联想记忆的联想记忆功能功能?n 网络能够通过联想来输出和输入模式网络能够通过联想来输出和输入模式最为相似的样本模式。最为相似的样本模式。8.5.1 Hopfield神经网络在联想记忆中的应用87o例例n 传感器输出：传感器输出：外形，质地，重量外形，质地，重量T 8.5.1 Hopfield神经网络在联想记忆中的应用88o例例n样本样本:l 步骤：步骤：（1）设计）设计DHNN结构结构（2）设计连接权矩阵）设计连接权矩阵（3）测试）测试具体怎样实现联想具体怎样实现联想记忆？记忆？8.5.1 Hopfield神经网络在联想记忆中的应用89n样本样本:（1）设计）设计DHNN结构结构3神经元的神经元的DHNN结构图结构图注：注：8.5.1 Hopfield神经网络在联想记忆中的应用90n 样本样本:，n 连接权：连接权：（2）设计连接权矩阵）设计连接权矩阵8.5.1 Hopfield神经网络在联想记忆中的应用91n 样本样本:，n 连接权：连接权：T01,0,)2(=x（2）设计连接权矩阵）设计连接权矩阵8.5.1 Hopfield神经网络在联想记忆中的应用92（2）设计连接权矩阵）设计连接权矩阵8.5.1 Hopfield神经网络在联想记忆中的应用93n 输入：输入：1，1，1T 输出输出?（3）测试）测试8.5.1 Hopfield神经网络在联想记忆中的应用94（3）测试）测试l 调整次序调整次序：l 初始状态初始状态：l 测试用例测试用例：l 样本样本：8.5.1 Hopfield神经网络在联想记忆中的应用95l 调整次序：调整次序：213k=08.5.1 Hopfield神经网络在联想记忆中的应用96k=1l 调整次序调整次序：2138.5.1 Hopfield神经网络在联想记忆中的应用97k=2l 调整次序调整次序：2138.5.1 Hopfield神经网络在联想记忆中的应用98k=2k=3k=0k=1l 样本样本：l 调整次序调整次序：2 1 32 1 32 1 32 1 38.5.1 Hopfield神经网络在联想记忆中的应用99o例例n 输入：输入：1，1，1T n 输出：输出：1，0，1T 8.5.1 Hopfield神经网络在联想记忆中的应用100n 连续连续Hopfiled神神经经网网络络求解求解约约束束优优化化问题问题的基本思路：的基本思路：8.5.2 Hopfield神经网络优化方法n 1985年年，霍霍普普菲菲尔尔德德和和塔塔克克（D.W.Tank）应应用用连连续续Hopfield 神神经经网网络络求求解解旅旅行行商商问问题题（traveling salesman problem，TSP）获得成功。获得成功。1018.5.2 Hopfield神经网络优化方法o 用神经网络方法求解优化问题的一般步骤：用神经网络方法求解优化问题的一般步骤：（1）将优化问题的每一个可行解用换位矩阵表示。）将优化问题的每一个可行解用换位矩阵表示。（2）将将换换位位矩矩阵阵与与由由 n 个个神神经经元元构构成成的的神神经经网网络络相相对对应应：每每一一个个可可行行解解的的换换位位矩矩阵阵的的各各元元素素与与相相应应的的神神经经元元稳稳态态输出相对应。输出相对应。（3）构构造造能能量量函函数数，使使其其最最小小值值对对应应于于优优化化问问题题的的最最优优解，并满足约束条件。解，并满足约束条件。（4）用用罚罚函函数数法法构构造造目目标标函函数数，与与Hopfield神神经经网网络络的的计算能量函数表达式相等，确定各连接权和偏置参数。计算能量函数表达式相等，确定各连接权和偏置参数。（5）给给定定网网络络初初始始状状态态和和网网络络参参数数等等，使使网网络络按按动动态态方方程运行，直到稳定状态，并将它解释为优化问题的解。程运行，直到稳定状态，并将它解释为优化问题的解。102o 应用举例：应用举例：Hopfield神经网络优化方法求解神经网络优化方法求解TSP。n 1985年年，霍霍普普菲菲尔尔德德和和塔塔克克（D.W.Tank）应应用用连连续续Hopfield 神经网络求解旅行商问题获得成功。神经网络求解旅行商问题获得成功。旅旅行行商商问问题题（traveling salesman problem，TSP）：有有 n 个个城城市市，城城市市间间的的距距离离或或旅旅行行成成本本已已知知，求求合合理理的的路路线线使使每每个个城城市市都都访访问问一一次次，且且总总路路径径（或或者者总总成本）为最短。成本）为最短。8.5.2 Hopfield神经网络优化方法103o 应用举例：应用举例：Hopfield神经网络优化方法求解神经网络优化方法求解TSP 旅行商问题（旅行商问题（TSP）：）：典型的组合优化问题典型的组合优化问题l n 个城市存在的路径数：个城市存在的路径数：l 用穷举法，用穷举法，Cray 计算机的计算速度：计算机的计算速度：108次次/秒。秒。n 1985年，年，Hopfield 和和Tank 用用Hopfield网络求解网络求解 n30 的的TSP问题，问题，0.2 s 就得到次优解。就得到次优解。8.5.2 Hopfield神经网络优化方法104 5个城市的个城市的TSP：神经元数目：神经元数目：258.5.2 Hopfield神经网络优化方法105 TSP的描述：的描述：用罚函数法，写出优化问题的目标函数：用罚函数法，写出优化问题的目标函数：8.5.2 Hopfield神经网络优化方法106 Hopfield神经网络能量函数：神经网络能量函数：8.5.2 Hopfield神经网络优化方法 令令E1 与目标函数与目标函数J相等，确定神经网络相等，确定神经网络的连接权值和偏置电流的连接权值和偏置电流：107神经网络的动态方程神经网络的动态方程：8.5.2 Hopfield神经网络优化方法108 选选择择合合适适的的A、B、C、D和和网网络络的的初初始始状状态态，按按网网络络动态方程演化直到收敛。动态方程演化直到收敛。8.5.2 Hopfield神经网络优化方法109n 神经网络优化计算目前存在的问题：神经网络优化计算目前存在的问题：（1）解的不稳定性。）解的不稳定性。（2）参数难以确定。）参数难以确定。（3）能量函数存在大量局部极小值，难以保证最优）能量函数存在大量局部极小值，难以保证最优 解。解。8.5.2 Hopfield神经网络优化方法1108.6 Hopfield神经网络优化方法求解JSP8.6.1 作业车间调度问题作业车间调度问题8.6.2 JSP的的Hopfield神经网络及其求解神经网络及其求解8.6.3 作业车间生产调度举例作业车间生产调度举例8.6.4 基于随机神经网络的生产调度方法基于随机神经网络的生产调度方法1118.6.1 作业车间调度问题 作业车间调度问题（作业车间调度问题（job-shop scheduling Problem，JSP）:一类满足任务配置和顺序约束要求的资源分一类满足任务配置和顺序约束要求的资源分配问题。配问题。问题描述：给定一个作业（工件）的集合和一个机问题描述：给定一个作业（工件）的集合和一个机器的集合，每个作业包括多道工序，每道工序需要在一器的集合，每个作业包括多道工序，每道工序需要在一台给定的机器上非间断地加工一段时间；每台机器一次台给定的机器上非间断地加工一段时间；每台机器一次最多只能加工一道工序，调度就是把工序分配给机器上最多只能加工一道工序，调度就是把工序分配给机器上某个时间段，使加工完成时间最短。某个时间段，使加工完成时间最短。112o Foo S.Y.和和 Y.Takefuji在在 1988年年 最最 早早 提提 出出 用用Hopfield神经网络神经网络求解求解JSP。8.6.1 作业车间调度问题o 对对于于单单台台机机器器加加工工问问题题，如如果果有有 个个作作业业而而每每个个作作业业只只考考虑虑加加工工时时间间以以及及与与操操作作序序列列有有关关的的安安装装时时间间，则这个问题就和则这个问题就和 个城市的个城市的TSP等价。等价。o Conway 等等（1967），生生产产调调度度理理论论：“一一般般作作业业车车间间调调度度问问题题是是一一个个迷迷人人的的挑挑战战性性问问题题。尽尽管管问问题题本本身身描描述述非非常常容容易易，但但是是朝朝着着问问题题求求解解的的方方向向作作任何的推进都是极端困难的任何的推进都是极端困难的”。1131.JSP的换位矩阵表示的换位矩阵表示 01,1,11,2,22,2,12,1,21,1,1100001,2,2000012,2,1001002,1,2100002作业 2机器 JSP8.6.2 JSP的Hopfield神经网络及其求解“工序(2,2,1)依赖于另一工序(1,2,2)”的命题成立。(1,2,2)：作业 1 的工序 2 在机器 2 上执行。“工序 不依赖于任何别的工序”的命题。1148.6.2 JSP的Hopfield神经网络及其求解作业作业机器机器JSP的工序约束条件：的工序约束条件：（1）各各工工序序应应服服从从优优先先顺顺序序关关系系。任任一一工工序序可可以以依依赖赖于于另另一一个个工序，也可以不依赖于任何工序（如在工序，也可以不依赖于任何工序（如在0时刻启动的工序）。时刻启动的工序）。（2）所有工序不允许所有工序不允许自依赖自依赖和和互依赖互依赖。（3）允允许许在在0时时刻刻启启动动的的工工序序数数不不超超过过 。即即在在 时时，在在0时刻启动的工序数应为时刻启动的工序数应为 。（4）在同一时刻启动的同一作业的工序不多于一个。）在同一时刻启动的同一作业的工序不多于一个。（5）在同一时刻同一机器上启动的工序不多于一个。）在同一时刻同一机器上启动的工序不多于一个。1158.6.2 JSP的Hopfield神经网络及其求解 2.JSP计算能量函数计算能量函数 :与矩阵中与矩阵中 位置相对应的神经元的输出状态。位置相对应的神经元的输出状态。行约束 全局约束 非对称约束 列约束 1168.6.2 JSP的Hopfield神经网络及其求解3.Hopfield 神经网络的参数神经网络的参数连续连续型型 Hopfield 神经网络的计算能量函数神经网络的计算能量函数:神经元神经元 与神经元与神经元 之间的连接权之间的连接权 神经元神经元 的偏置电流的偏置电流 :1178.6.2 JSP的Hopfield神经网络及其求解4.Hopfield神经网络的运动方程神经网络的运动方程1188.6.2 JSP的Hopfield神经网络及其求解 5.成本树成本树 step1：根据换位矩阵，构造成本树。：根据换位矩阵，构造成本树。step2：计算成本树上各操作计算成本树上各操作 的开始时间的开始时间 和结束和结束 时间时间 。step3：判断是否出现死锁调度。：判断是否出现死锁调度。step4：调整死锁调度。：调整死锁调度。1198.6.2 JSP的Hopfield神经网络及其求解6.甘特图甘特图step1：根根据据换换位位矩矩阵阵，计计算算成成本本树树上上各各操操作作的的开开始始时时间间和和结结束时间，并给出相应的甘特图。束时间，并给出相应的甘特图。step2：判判断断甘甘特特图图中中每每台台机机器器上上各各作作业业的的开开始始时时间间是是否否发发生生重叠。重叠。step 3：判断同一作业的各操作的开始时间是否发生重叠。：判断同一作业的各操作的开始时间是否发生重叠。step4：重重复复step2 和和step3，直直至至甘甘特特图图中中同同一一机机器器上上各各作作业业的的开开始始时时间间和和同同一一作作业业的的各各操操作作的的开开始始时时间间都都不不发发生生重重叠叠为为止。止。1208.6.3 作业车间生产调度举例o2作业3机器的JSP例子 所有的操作：111，122，133，213，221，232。1218.6.3 作业车间生产调度举例o换位矩阵换位矩阵Hopfield 神经网络：神经网络：6行行7列的神经元阵列列的神经元阵列 1228.6.3 作业车间生产调度举例o神经网络偏置电流矩阵神经网络偏置电流矩阵 1238.6.3 作业车间生产调度举例o计算能量函数计算能量函数为为0的换位矩阵的换位矩阵 1248.6.3 作业车间生产调度举例o成本树成本树 返回1258.6.3 作业车间生产调度举例o甘特图甘特图 返回126o 基本思想：基本思想：在在系系统统寻寻优优过过程程中中，利利用用神神经经元元状状态态更更新新的的随随机机性性，允允许许向向较较差差方方向向搜搜索索，以以跳跳出出局局部部极极小小。经经多多次次寻寻查查后后，最最终终使使系系统统稳稳定定于于能能量量最最低低状状态态，使使神神经经网网络络收收敛敛到到计计算算能能量量函函数数的的最最小小值值0，从从而而使使神神经经网网络络输出是一个可行调度解。输出是一个可行调度解。8.6.4 基于随机神经网络的生产调度方法127o 根根据据改改进进Metropolis方方法法，求求解解JSP的的基基于于模模拟拟退退火火的的神神经经网络算法：网络算法：（1）初始化初始化：设设置置初初始始温温度度 ，合合适适的的输输入入偏偏置置电电流流，凝凝结结温温度度 ，温度下降速率温度下降速率 ，在每个温度点的循环处理次数，在每个温度点的循环处理次数 。8.6.4 基于随机神经网络的生产调度方法（2）随机爬山随机爬山：对每个神经元对每个神经元 ，由求解网络方程计算输出电压。由网，由求解网络方程计算输出电压。由网络稳定状态集组成成本树；求出最大成本变化量络稳定状态集组成成本树；求出最大成本变化量 。1288.6.4 基于随机神经网络的生产调度方法 若若 ，则转去，则转去（3）；否则计算能量变化量）；否则计算能量变化量 若若 ，则令，则令 否则，令否则，令 计算概率计算概率129 选选择择均均匀匀分分布布随随机机数数RAND，若若 ，则则令令神神经经元元 的状态的状态 为为“1”，否则，令为否则，令为“0”。重复该步骤重复该步骤 次。次。8.6.4 基于随机神经网络的生产调度方法（3）退火退火/收敛检验收敛检验 令令 ，若若 ，则转去（，则转去（2）；否则停止。）；否则停止。1308.6.4 基于随机神经网络的生产调度方法o模拟退火算法只有在初始温度充分高，温度下降足够慢，在每个温度点下循环处理无限多次，并在 时，才能收敛于全局最优解，但导致计算时间大大增加。o 改进算法：快速模拟退火、并行模拟退火等。改进算法：快速模拟退火、并行模拟退火等。131THE ENDArtificial Intelligence Principles and Applications132结束语结束语谢谢大家聆听！谢谢大家聆听！133
