人工神经网络及其应用

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