人工神经网络及其应用.ppt

《人工神经网络及其应用.ppt》由会员分享，可在线阅读，更多相关《人工神经网络及其应用.ppt（132页珍藏版）》请在三一办公上搜索。

1、第 8 章 人工神经网络及其应用,教材：王万良人工智能及其应用（第2版）高等教育出版社，2008.6,2,第8章 人工神经网络及其应用,神经网络（neural networks，NN）,生物神经网络(natural neural network,NNN):由中枢神经系统（脑和脊髓）及周围神经系统（感觉神经、运动神经等）所构成的错综复杂的神经网络，其中最重要的是脑神经系统。人工神经网络(artificial neural networks,ANN):模拟人脑神经系统的结构和功能，运用大量简单处理单元经广泛连接而组成的人工网络系统。,神经网络方法：隐式的知识表示方法,3,第8章 人工神经网络及其应

2、用,8.1 神经元与神经网络 8.2 BP神经网络及其学习算法 8.3 BP神经网络的应用 8.4 Hopfield神经网络及其改进 8.5 Hopfield神经网络的应用8.6 Hopfield神经网络优化方法求解JSP,4,第8章 人工神经网络及其应用,8.1 神经元与神经网络 8.2 BP神经网络及其学习算法 8.3 BP神经网络的应用8.4 Hopfield神经网络及其改进8.5 Hopfield神经网络的应用8.6 Hopfield神经网络优化方法求解JSP,5,8.1 神经元与神经网络,8.1.1 生物神经元的结构8.1.2 神经元数学模型8.1.3 神经网络结构与工作方式,6,8

3、.1.1 生物神经元的结构,人脑由一千多亿（1011亿 1014 亿）个神经细胞（神经元）交织在一起的网状结构组成，其中大脑皮层约140亿个神经元，小脑皮层约1000亿个神经元。,神经元约有1000种类型，每个神经元大约与103 104个其他神经元相连接，形成极为错综复杂而又灵活多变的神经网络。人的智能行为就是由如此高度复杂的组织产生的。浩瀚的宇宙中，也许只有包含数千忆颗星球的银河系的复杂性能够与大脑相比。,7,8.1.1 生物神经元的结构,（输入）,（输出）,神经冲动,生物神经元结构,8,8.1.1 生物神经元的结构,工作状态：兴奋状态：细胞膜电位 动作电位的阈值 神经冲动 抑制状态：细胞膜

4、电位 动作电位的阈值 学习与遗忘：由于神经元结构的可塑性，突触的传递作用可增强和减弱。,9,8.1 神经元与神经网络,8.1.1 生物神经元的结构8.1.2 神经元数学模型8.1.3 神经网络的结构与工作方式,10,8.1.2 神经元数学模型,1943年，麦克洛奇和皮兹提出MP模型。一般模型：,11,8.1.2 神经元数学模型,：第 个神经元的输出。：第 个神经元的阈值。：外部输入。：权值。,加权求和：其矩阵形式：,12,线性环节的传递函数：1；及其组合等。,8.1.2 神经元数学模型,13,8.1.2 神经元数学模型,非线性激励函数（传输函数、输出变换函数）,（硬极限函数或阶跃函数）,（对称

5、硬极限函数）,14,8.1.2 神经元数学模型,非线性激励函数（传输函数、输出变换函数）,（对数-S 形函数或S型函数）,（双曲正切S形函数）,15,8.1.2 神经元数学模型,非线性激励函数（传输函数、输出变换函数）,（饱和线性函数）,（对称饱和线性函数）,16,8.1.2 神经元数学模型,非线性激励函数（传输函数、输出变换函数）,（线性函数）,（高斯或径向基函数）,17,8.1.2 神经元数学模型,工作过程:从各输入端接收输入信号 uj(j=1,2,n)根据连接权值求出所有输入的加权和 用非线性激励函数进行转换，得到输出,18,8.1.2 神经元数学模型,19,8.1 神经元与神经网络,8

6、.1.1 生物神经元的结构8.1.2 神经元的数学模型8.1.3 神经网络的结构与工作方式,20,8.1.3 神经网络的结构与工作方式,决定人工神经网络性能的三大要素：,神经元的特性。神经元之间相互连接的形式拓扑结构。为适应环境而改善性能的学习规则。,21,1.神经网络的结构（1）前馈型（前向型）,8.1.3 神经网络的结构与工作方式,22,1.神经网络的结构（2）反馈型,（Hopfield神经网络）,8.1.3 神经网络的结构与工作方式,23,2.神经网络的工作方式,同步（并行）方式：任一时刻神经网络中所有神经元同时调整状态。异步（串行）方式：任一时刻只有一个神经元调整状态，而其它神经元的状

7、态保持不变。,8.1.3 神经网络的结构与工作方式,24,探索时期（开始于20世纪40年代）：,1943年，麦克劳（W.S.McCullocn）和匹茨（W.A.Pitts）首次提出一个神经网络模型MP模型。1949年，赫布（D.O.Hebb）提出改变神经元连接强度的 Hebb学习规则。,8.1.4 神经网络的发展概况,25,1958年，罗森布拉特（F.Rosenblatt）提出感知器模型（perceptron）。1959年，威德罗(B.Widrow)等提出自适应线性元件（adaline）网络，通过训练后可用于抵消通信中的回波和噪声。1960年，他和 M.Hoff 提出LMS（Least Mea

8、n Square 最小方差）算法的学习规则。,8.1.4 神经网络的发展概况,第一次热潮时期：20世纪50年代末 20世纪60年代初,26,1969年，明斯基（M.Minsky）等在Perceptron中对感知器功能得出悲观结论。1972年，T.Kohonen 和 J.Anderson 分别提出能完成记忆的新型神经网络。1976年，S.Grossberg 在自组织神经网络方面的研究十分活跃。,8.1.4 神经网络的发展概况,低潮时期：20世纪60年代末 20世纪70年代,27,第二次热潮时期：20世纪80年代至今,1982年1986年，霍普菲尔德（J.J.Hopfield）陆续提出离散的和连续

9、的全互连神经网络模型，并成功求解旅行商问题（TSP）。1986年，鲁姆尔哈特（Rumelhart）和麦克劳（McCellan）等在Parallel Distributed Processing中提出反向传播学习算法（BP算法）。1987年6月，首届国际神经网络学术会议在美国圣地亚哥召开，成立了国际神经网络学会（INNS）。,8.1.4 神经网络的发展概况,28,神经网络控制的研究领域,基于神经网络的系统辨识 神经网络控制器 神经网络与其他算法（模糊逻辑、专家系统、遗传算法等）相结合 优化计算,8.1.4 神经网络的发展概况,29,第8章 人工神经网络及其应用,8.1 神经元与神经网络 8.2

10、BP神经网络及其学习算法 8.3 BP神经网络的应用 8.4 Hopfield神经网络及其改进 8.5 Hopfield神经网络的应用 8.6 Hopfield神经网络优化方法求解JSP,30,8.2 BP神经网络及其学习算法,8.2.1 BP神经网络（back-propagation neural network）的结构8.2.2 BP学习算法8.2.3 BP算法的实现,31,8.2 BP神经网络及其学习算法,8.2.1 BP神经网络（back-propagation neural network）的结构8.2.2 BP学习算法8.2.3 BP算法的实现,32,8.2.1 BP神经网络的结构

11、,1.BP 网络结构,33,8.2.1 BP神经网络的结构,2.输入输出变换关系,34,8.2.1 BP神经网络的结构,3.工作过程,第一阶段或网络训练阶段：N 组输入输出样本：xi=xi1,xi2,xip1T di=di1,di2,dipmT i=1,2,N 对网络的连接权进行学习和调整，以使该网络实现给定样本的输入输出映射关系。第二阶段或称工作阶段：把实验数据或实际数据输入到网络，网络在误差范围内预测计算出结果。,35,8.2 BP神经网络及其学习算法,8.2.1 BP神经网络的结构8.2.2 BP学习算法8.2.3 BP算法的实现,36,（1）是否存在一个BP神经网络能够逼近给定的样本或

12、者函数。,8.2.2 BP学习算法,两个问题：,（2）如何调整BP神经网络的连接权，使网络的输入与输出与给定的样本相同。1986年，鲁梅尔哈特（D.Rumelhart）等提出BP学习算法。,37,8.2.2 BP学习算法,目标函数：,约束条件：,连接权值的修正量：,1.基本思想,38,8.2.2 BP学习算法,正向传播：输入信息由输入层传至隐层，最终在输出层输出。反向传播：修改各层神经元的权值，使误差信号最小。,2.学习算法,39,8.2.2 BP学习算法,2.学习算法,40,8.2.2 BP学习算法,2.学习算法,41,8.2 BP神经网络及其学习算法,8.2.1 BP神经网络的结构8.2.

13、2 BP学习算法8.2.3 BP算法的实现,42,8.2.3 BP算法的实现,（1）隐层数及隐层神经元数的确定：目前尚无理论指导。（2）初始权值的设置：一般以一个均值为0的随机分布设置网络的初始权值。（3）训练数据预处理：线性的特征比例变换，将所有的特征变换到0，1或者-1，1区间内，使得在每个训练集上，每个特征的均值为0，并且具有相同的方差。（4）后处理过程：当应用神经网络进行分类操作时，通常将输出值编码成所谓的名义变量，具体的值对应类别标号。,1.BP算法的设计,43,8.2.3 BP算法的实现,（1）初始化：对所有连接权和阈值赋以随机任意小值；（2）从 N 组输入输出样本中取一组样本：x

14、=x1,x2,xp1T,d=d1,d2,dpmT,把输入信息x=x1,x2,xp1T输入到BP网络中（3）正向传播：计算各层节点的输出：（4）计算网络的实际输出与期望输出的误差：,2.BP算法的计算机实现流程,44,8.2.3 BP算法的实现,（5）反向传播：从输出层方向计算到第一个隐层，按连接权值修正公式向减小误差方向调整网络的各个连接权值。（6）让t+1t，取出另一组样本重复（2）（5），直到 N 组输入输出样本的误差达到要求时为止。,2.BP算法的计算机实现流程,45,8.2.3 BP算法的实现,BP学习算法的程序框图,46,1.特点,BP网络：多层前向网络（输入层、隐层、输出层）。连接

15、权值：通过Delta学习算法进行修正。神经元传输函数：S形函数。学习算法：正向传播、反向传播。层与层的连接是单向的，信息的传播是双向的。,8.2.4 BP算法的特点分析,47,2.BP网络的主要优缺点,很好的逼近特性。具有较强的泛化能力。具有较好的容错性。,优点,收敛速度慢。局部极值。难以确定隐层和隐层结点的数目。,缺点,8.2.4 BP算法的特点分析,48,8.3 BP神经网络的应用,8.3.1 BP神经网络在模式识别中的应用8.3.2 BP神经网络在软测量中的应用,49,8.3.1 BP神经网络在模式识别中的应用,模式识别研究用计算机模拟生物、人的感知，对模式信息，如图像、文字、语音等，进

16、行识别和分类。传统人工智能的研究部分地显示了人脑的归纳、推理等智能。但是，对于人类底层的智能，如视觉、听觉、触觉等方面，现代计算机系统的信息处理能力还不如一个幼儿园的孩子。神经网络模型模拟了人脑神经系统的特点：处理单元的广泛连接；并行分布式信息储存、处理；自适应学习能力等。神经网络模式识别方法具有较强的容错能力、自适应学习能力、并行信息处理能力。,50,例 输入输出样本：测试数据：,8.3.1 BP神经网络在模式识别中的应用,51,8.3.1 BP神经网络在模式识别中的应用,例 设计一个三层BP网络对数字0至9进行分类。,每个数字用97的网格表示，灰色像素代表0，黑色像素代表1。将每个网格表示

17、为0，1的长位串。位映射由左上角开始向下直到网格的整个一列，然后重复其他列。选择BP网络结构为63-6-9。97个输入结点，对应上述网格的映射。9个输出结点对应10种分类。使用的学习步长为0.3。训练600个周期，如果输出结点的值大于0.9，则取为ON，如果输出结点的值小于0.1，则取为OFF。,52,测试结果表明：除了8以外，所有被测的数字都能够被正确地识别。对于数字8，神经网络的第6个结点的输出值为0.53，第8个结点的输出值为0.41，表明第8个样本是模糊的，可能是数字6，也可能是数字8，但也不完全确信是两者之一。,8.3.1 BP神经网络在模式识别中的应用,当训练成功后，对如图所示测试

18、数据进行测试。测试数据都有一个或者多个位丢失。,53,8.3.2 BP神经网络在软测量中的应用,软测量技术,主导变量：被估计的变量。辅助变量：与被估计变量相关的一组可测变量。,54,软测量系统的设计：辅助变量的选择：变量类型、变量数量和检测点位置的选择。数据采集与处理。软测量模型的建立：通过辅助变量来获得对主导变量的最佳估计。,8.3.2 BP神经网络在软测量中的应用,55,序批式活性污泥法（SBR）,8.3.2 BP神经网络在软测量中的应用,56,BOD、COD、N和P：为软测量模型的主导变量。ORP、DO、PH和MLSS：辅助变量。三层BP网络：,8.3.2 BP神经网络在软测量中的应用,

19、57,第8章 人工神经网络及其应用,8.1 神经元与神经网络 8.2 BP神经网络及其学习算法 8.3 BP神经网络的应用 8.4 Hopfield神经网络及其改进 8.5 Hopfield神经网络的应用8.6 Hopfield神经网络优化方法求解JSP,58,8.4 Hopfield神经网络及其改进,8.4.1 离散型Hopfield神经网络8.4.2 连续型Hopfield神经网络及其VLSI实现8.4.3 随机神经网络8.4.4 混沌神经网络,59,8.4 Hopfield神经网络及其改进,8.4.1 离散型Hopfield神经网络8.4.2 连续型Hopfield神经网络及其VLSI实

20、现8.4.3 随机神经网络8.4.4 混沌神经网络,60,离散Hopfield神经网络结构图,1,2,(状态）,(阈值）,（连接权值）,8.4.1 离散Hopfield 神经网络,1.离散Hopfield神经网络模型网络结构：,61,注：,或,8.4.1 离散Hopfield 神经网络,-1,1.离散Hopfield神经网络模型输入输出关系：,62,工作方式：,异步（串行）方式:,同步（并行）方式:,8.4.1 离散Hopfield 神经网络,1.离散Hopfield神经网络模型,63,（异步或同步方式）,初态：,稳态：,8.4.1 离散Hopfield 神经网络,1.离散Hopfield神经

21、网络模型工作过程：,64,（异步或同步方式）,联想 记忆,8.4.1 离散Hopfield 神经网络,1.离散Hopfield神经网络模型工作过程：,65,稳定性定义：若从某一时刻开始，网络中所有神经元的状态不再改变，即，则称该网络是稳定的，为网络的稳定点或吸引子。Hopfield神经网络是高维非线性系统，可能有许多稳定优态。从任何初始状态开始运动，总可以到某个稳定状态。这些稳定状态可以通过改变网络参数得到。,8.4.1 离散Hopfield 神经网络,2.网络的稳定性,66,稳定性定理证明：1983年，科恩（Cohen）、葛劳斯伯格（S.Grossberg）。稳定性定理（Hopfield）,

22、8.4.1 离散Hopfield 神经网络,2.网络的稳定性,并行稳定性 W：非负定对称阵,串行稳定性 W：对称阵,67,8.4 Hopfield神经网络及其改进,8.4.1 离散型Hopfield神经网络8.4.2 连续型Hopfield神经网络及其VLSI实现,68,8.4.2 连续型Hopfield神经网络及其VLSI实现,连续Hopfield神经网络模型网络的稳定性应用举例,69,8.4.2 连续型Hopfield神经网络及其VLSI实现,1.连续Hopfield神经网络模型,70,8.4.2 连续型Hopfield神经网络及其VLSI实现,1.连续Hopfield神经网络模型,71,

23、8.4.2 连续型Hopfield神经网络及其VLSI实现,2.网络的稳定性,计算能量函数：,定理：对于连续型 Hopfield 神经网络，若 为单调递增的连续函数，Ci 0,wij=wji,则；当且仅当,72,8.4.3 随机神经网络,Hopfield神经网络中，神经元状态为1是根据其输入是否大于阈值确定的，是确定性的。随机神经网络中，神经元状态为1是随机的，服从一定的概率分布。例如，服从玻尔兹曼(Boltzmann)、高斯(Gaussian)、柯西(Cauchy)分布等，从而构成玻尔兹曼机、高斯机、柯西机等随机机。,73,8.4.3 随机神经网络,1.Boltzmann机 1985年，加拿

24、大多伦多大学教授欣顿(Hinton)等人借助统计物理学的概念和方法，提出了Boltzmann机神经网络模型。Boltzmann机是离散Hopfield神经网络的一种变型，通过对离散Hopfield神经网络加以扰动，使其以概率的形式表达，而网络的模型方程不变，只是输出值类似于Boltzmann分布以概率分布取值。Boltzmann机是按Boltzmann概率分布动作的神经网络。,74,8.4.3 随机神经网络,1.Boltzmann机（续）离散Hopfield神经网络的输出：Boltzman机的内部状态：神经元 输出值为0和1时的概率：,75,8.4.3 随机神经网络,1.Boltzmann机（

25、续）Boltzmann的能量函数：,神经元 状态转换时网络能量的变化：,神经元 改变为状态“1”的概率：,),exp(,1,1,T,E,p,i,i,D,-,+,=,76,2.高斯机,8.4.3 随机神经网络,:均值为0的高斯随机变量（白噪声），其方差为,3.柯西机,:柯西随机变量（有色噪声）,77,8.4.4 混沌神经网络,1.混沌 混沌：自然界中一种较为普遍的非线性现象，其行 为看似混乱复杂且类似随机，却存在精致的内在规 律性。混沌的性质：（1）随机性：类似随机变量的杂乱表现。（2）遍历性：不重复地历经一定范围内的所有状态。（3）规律性：由确定性的迭代式产生。,78,1.混沌（续）混沌学的研

26、究热潮开始于20世纪70年代初期。1963年，Lorenz在分析气候数据时发现：初值十分接近的两条曲线的最终结果会相差很大，从而获得了混沌的第一个例子。1975年，Li-Yorke的论文周期3意味着混沌使“混沌”一词首先出现在科技文献中。混沌的发现，对科学的发展具有深远的影响。,8.4.4 混沌神经网络,79,8.4.4 混沌神经网络,2.混沌神经元 混沌神经元（1987年，Freeman）：构造混沌神经网络的基本单位。,80,8.4.4 混沌神经网络,3.混沌神经网络 1990年，Aihara等提出了第一个混沌神经网络模型(chaotic neural network，CNN)。1991年，

27、Inoue等利用两个混沌振荡子耦合成一个神经元的方法，构造出一个混沌神经计算机.1992年，Nozawa基于欧拉离散化的Hopfield神经网络，通过增加一个大的自反馈项，得到了一个与Aihara等提出的类似的CNN模型。,81,8.4.4 混沌神经网络,3.混沌神经网络（1）基于模拟退火策略的自抑制混沌神经网络 1995年，Chen等提出的暂态混沌神经网络(transient chaotic neural network，TCNN)：,82,8.4.4 混沌神经网络,3.混沌神经网络（1）基于模拟退火策略的自抑制混沌神经网络 具有暂态混沌特性。能演化到一个稳定状态。搜索区域为一分形结构。具有

28、混沌退火机制。一种广义的混沌神经网络。可求解0-1问题，也可求解连续非线性优化问题。,83,8.4.4 混沌神经网络,非线性函数：,84,8.4.4 混沌神经网络,3.混沌神经网络（2）基于加大时间步长的混沌神经网络 CHNN的欧拉离散化：,1998年，Wang和Smith采用加大时间步长产生混沌：,85,8.4.4 混沌神经网络,3.混沌神经网络（3）引入噪声的混沌神经网络 1995年，Hayakawa等的混沌神经网络：,86,8.5 Hopfield神经网络的应用,8.5.1 Hopfield神经网络在联想记忆中的应用8.5.2 Hopfield神经网络优化方法,87,8.5.1 Hopf

29、ield神经网络在联想记忆中的应用,88,例,传感器输出：外形，质地，重量T,8.5.1 Hopfield神经网络在联想记忆中的应用,89,例,样本:,具体怎样实现联想记忆？,8.5.1 Hopfield神经网络在联想记忆中的应用,90,样本:,（1）设计DHNN结构,3神经元的DHNN结构图,注：,8.5.1 Hopfield神经网络在联想记忆中的应用,91,样本:，,连接权：,（2）设计连接权矩阵,8.5.1 Hopfield神经网络在联想记忆中的应用,92,样本:，,连接权：,T,0,1,0,),2,(,=,x,（2）设计连接权矩阵,8.5.1 Hopfield神经网络在联想记忆中的应用

30、,93,（2）设计连接权矩阵,8.5.1 Hopfield神经网络在联想记忆中的应用,94,输入：1，1，1T,输出?,（3）测试,8.5.1 Hopfield神经网络在联想记忆中的应用,95,（3）测试,调整次序：,初始状态：,测试用例：,样本：,8.5.1 Hopfield神经网络在联想记忆中的应用,96,调整次序：213,k=0,8.5.1 Hopfield神经网络在联想记忆中的应用,97,k=1,调整次序：213,8.5.1 Hopfield神经网络在联想记忆中的应用,98,k=2,调整次序：213,8.5.1 Hopfield神经网络在联想记忆中的应用,99,k=2,k=3,k=0,

31、k=1,样本：,调整次序：,2 1 3,2 1 3,2 1 3,2 1 3,8.5.1 Hopfield神经网络在联想记忆中的应用,100,例,输入：1，1，1T,输出：1，0，1T,8.5.1 Hopfield神经网络在联想记忆中的应用,101,连续Hopfiled神经网络求解约束优化问题的基本思路：,8.5.2 Hopfield神经网络优化方法,1985年，霍普菲尔德和塔克（D.W.Tank）应用连续Hopfield 神经网络求解旅行商问题（traveling salesman problem，TSP）获得成功。,102,8.5.2 Hopfield神经网络优化方法,用神经网络方法求解优化

32、问题的一般步骤：（1）将优化问题的每一个可行解用换位矩阵表示。（2）将换位矩阵与由 n 个神经元构成的神经网络相对应：每一个可行解的换位矩阵的各元素与相应的神经元稳态输出相对应。（3）构造能量函数，使其最小值对应于优化问题的最优解，并满足约束条件。（4）用罚函数法构造目标函数，与Hopfield神经网络的计算能量函数表达式相等，确定各连接权和偏置参数。（5）给定网络初始状态和网络参数等，使网络按动态方程运行，直到稳定状态，并将它解释为优化问题的解。,103,应用举例：Hopfield神经网络优化方法求解TSP。,1985年，霍普菲尔德和塔克（D.W.Tank）应用连续Hopfield 神经网络

33、求解旅行商问题获得成功。,旅行商问题（traveling salesman problem，TSP）：有 n 个城市，城市间的距离或旅行成本已知，求合理的路线使每个城市都访问一次，且总路径（或者总成本）为最短。,8.5.2 Hopfield神经网络优化方法,104,应用举例：Hopfield神经网络优化方法求解TSP,旅行商问题（TSP）：典型的组合优化问题 n 个城市存在的路径数：用穷举法，Cray 计算机的计算速度：108次/秒。,1985年，Hopfield 和Tank 用Hopfield网络求解 n30 的TSP问题，0.2 s 就得到次优解。,8.5.2 Hopfield神经网络优化

34、方法,105,5个城市的TSP：,神经元数目：25,8.5.2 Hopfield神经网络优化方法,106,TSP的描述：,用罚函数法，写出优化问题的目标函数：,8.5.2 Hopfield神经网络优化方法,107,Hopfield神经网络能量函数：,8.5.2 Hopfield神经网络优化方法,令E1 与目标函数J相等，确定神经网络的连接权值和偏置电流：,108,神经网络的动态方程：,8.5.2 Hopfield神经网络优化方法,109,选择合适的A、B、C、D和网络的初始状态，按网络动态方程演化直到收敛。,8.5.2 Hopfield神经网络优化方法,110,神经网络优化计算目前存在的问题：

35、（1）解的不稳定性。（2）参数难以确定。（3）能量函数存在大量局部极小值，难以保证最优 解。,8.5.2 Hopfield神经网络优化方法,111,8.6 Hopfield神经网络优化方法求解JSP,8.6.1 作业车间调度问题8.6.2 JSP的Hopfield神经网络及其求解8.6.3 作业车间生产调度举例8.6.4 基于随机神经网络的生产调度方法,112,8.6.1 作业车间调度问题,作业车间调度问题（job-shop scheduling Problem，JSP）:一类满足任务配置和顺序约束要求的资源分配问题。问题描述：给定一个作业（工件）的集合和一个机器的集合，每个作业包括多道工序，

36、每道工序需要在一台给定的机器上非间断地加工一段时间；每台机器一次最多只能加工一道工序，调度就是把工序分配给机器上某个时间段，使加工完成时间最短。,113,Foo S.Y.和Y.Takefuji在1988年最早提出用Hopfield神经网络求解JSP。,8.6.1 作业车间调度问题,对于单台机器加工问题，如果有 个作业而每个作业只考虑加工时间以及与操作序列有关的安装时间，则这个问题就和 个城市的TSP等价。,Conway 等（1967），生产调度理论：“一般作业车间调度问题是一个迷人的挑战性问题。尽管问题本身描述非常容易，但是朝着问题求解的方向作任何的推进都是极端困难的”。,114,1.JSP的

37、换位矩阵表示,8.6.2 JSP的Hopfield神经网络及其求解,“工序(2,2,1)依赖于另一工序(1,2,2)”的命题成立。,(1,2,2)：作业 1 的工序 2 在机器 2 上执行。,“工序 不依赖于任何别的工序”的命题。,115,8.6.2 JSP的Hopfield神经网络及其求解,作业 机器JSP的工序约束条件：（1）各工序应服从优先顺序关系。任一工序可以依赖于另一个工序，也可以不依赖于任何工序（如在0时刻启动的工序）。（2）所有工序不允许自依赖和互依赖。（3）允许在0时刻启动的工序数不超过。即在 时，在0时刻启动的工序数应为。（4）在同一时刻启动的同一作业的工序不多于一个。（5）

38、在同一时刻同一机器上启动的工序不多于一个。,116,8.6.2 JSP的Hopfield神经网络及其求解,2.JSP计算能量函数:与矩阵中 位置相对应的神经元的输出状态。,行约束,全局约束,非对称约束,117,8.6.2 JSP的Hopfield神经网络及其求解,3.Hopfield 神经网络的参数连续型 Hopfield 神经网络的计算能量函数:,神经元 与神经元 之间的连接权,神经元 的偏置电流:,118,8.6.2 JSP的Hopfield神经网络及其求解,4.Hopfield神经网络的运动方程,119,8.6.2 JSP的Hopfield神经网络及其求解,5.成本树 step1：根据换

39、位矩阵，构造成本树。step2：计算成本树上各操作 的开始时间 和结束 时间。step3：判断是否出现死锁调度。step4：调整死锁调度。,120,8.6.2 JSP的Hopfield神经网络及其求解,6.甘特图step1：根据换位矩阵，计算成本树上各操作的开始时间和结束时间，并给出相应的甘特图。step2：判断甘特图中每台机器上各作业的开始时间是否发生重叠。step 3：判断同一作业的各操作的开始时间是否发生重叠。step4：重复step2 和step3，直至甘特图中同一机器上各作业的开始时间和同一作业的各操作的开始时间都不发生重叠为止。,121,8.6.3 作业车间生产调度举例,2作业3机

40、器的JSP例子,所有的操作：111，122，133，213，221，232。,122,8.6.3 作业车间生产调度举例,换位矩阵,Hopfield 神经网络：6行7列的神经元阵列,123,8.6.3 作业车间生产调度举例,神经网络偏置电流矩阵,124,8.6.3 作业车间生产调度举例,计算能量函数为0的换位矩阵,125,8.6.3 作业车间生产调度举例,成本树,126,8.6.3 作业车间生产调度举例,甘特图,127,基本思想：在系统寻优过程中，利用神经元状态更新的随机性，允许向较差方向搜索，以跳出局部极小。经多次寻查后，最终使系统稳定于能量最低状态，使神经网络收敛到计算能量函数的最小值0，从

41、而使神经网络输出是一个可行调度解。,8.6.4 基于随机神经网络的生产调度方法,128,根据改进Metropolis方法，求解JSP的基于模拟退火的神经网络算法：（1）初始化：设置初始温度，合适的输入偏置电流，凝结温度，温度下降速率，在每个温度点的循环处理次数。,8.6.4 基于随机神经网络的生产调度方法,（2）随机爬山：对每个神经元，由求解网络方程计算输出电压。由网络稳定状态集组成成本树；求出最大成本变化量。,129,8.6.4 基于随机神经网络的生产调度方法,若，则转去（3）；否则计算能量变化量 若，则令 否则，令 计算概率,130,选择均匀分布随机数RAND，若，则令神经元 的状态 为“1”，否则，令为“0”。重复该步骤 次。,8.6.4 基于随机神经网络的生产调度方法,（3）退火/收敛检验 令，若，则转去（2）；否则停止。,131,8.6.4 基于随机神经网络的生产调度方法,模拟退火算法只有在初始温度充分高，温度下降足够慢，在每个温度点下循环处理无限多次，并在 时，才能收敛于全局最优解，但导致计算时间大大增加。,改进算法：快速模拟退火、并行模拟退火等。,132,THE END,Artificial Intelligence Principles and Applications,