人工神经网络及其应用

1、Artificial Intelligence Principles and Applications 第第 8 章章 人工神经网络及其应用人工神经网络及其应用 教材：教材： 王万良王万良人工智能及其应用人工智能及其应用（第（第2版）版） 高等教育出版社，高等教育出版社，2008. 6 2 第8章 人工神经网络及其应用 o神经网络（神经网络（neural networks，NN） 生物神经网络生物神经网络( natural neural network, NNN): 由中枢神经系由中枢神经系 统（脑和脊髓）及周围神经系统（感觉神经、运动神经等）所统（脑和脊髓）及周围神经系统（感觉神经、运动神经

2、等）所 构成的错综复杂的神经网络，其中最重要的是构成的错综复杂的神经网络，其中最重要的是脑神经系统脑神经系统。 人工神经网络人工神经网络(artificial neural networks, ANN): 模拟模拟人脑神经人脑神经 系统系统的结构和功能，运用大量简单处理单元经广泛连接而组成的结构和功能，运用大量简单处理单元经广泛连接而组成 的人工网络系统。的人工网络系统。 神经网络方法：神经网络方法： 隐式隐式的的 知识表示方法知识表示方法 3 第8章 人工神经网络及其应用 o8.1 神经元与神经网络神经元与神经网络 o8.2 BP神经网络及其学习算法神经网络及其学习算法 o8.3 BP神经网

3、络的应用神经网络的应用 o8.4 Hopfield神经网络及其改进神经网络及其改进 o8.5 Hopfield神经网络的应用神经网络的应用 o8.6 Hopfield神经网络优化方法求解神经网络优化方法求解JSP 4 第8章 人工神经网络及其应用 8.1 神经元与神经网络神经元与神经网络 o8.2 BP神经网络及其学习算法神经网络及其学习算法 o8.3 BP神经网络的应用神经网络的应用 o8.4 Hopfield神经网络及其改进神经网络及其改进 o8.5 Hopfield神经网络的应用神经网络的应用 o8.6 Hopfield神经网络优化方法求解神经网络优化方法求解JSP 5 8.1 神经元与

4、神经网络 o8.1.1 生物神经元的结构生物神经元的结构 o8.1.2 神经元数学模型神经元数学模型 o8.1.3 神经网络结构与工作方式神经网络结构与工作方式 6 8.1.1 生物神经元的结构 n人脑由一千多亿（人脑由一千多亿（1011亿亿 1014 亿）个神经细胞（神经元）交织亿）个神经细胞（神经元）交织 在一起的网状结构组成，其中大在一起的网状结构组成，其中大 脑皮层约脑皮层约140亿个神经元，小脑皮亿个神经元，小脑皮 层约层约1000亿个神经元。亿个神经元。 n 神经元约有神经元约有1000种类型，每个神经元大约与种类型，每个神经元大约与103 104个其他个其他 神经元相连接，形成极

5、为错综复杂而又灵活多变的神经网络。神经元相连接，形成极为错综复杂而又灵活多变的神经网络。 n 人的智能行为就是由如此高度复杂的组织产生的。浩瀚的宇人的智能行为就是由如此高度复杂的组织产生的。浩瀚的宇 宙中，也许只有包含数千忆颗星球的银河系的复杂性能够与大宙中，也许只有包含数千忆颗星球的银河系的复杂性能够与大 脑相比。脑相比。 7 8.1.1 生物神经元的结构 （输入输入） （输出输出） 神经冲动神经冲动 生物神经元结构生物神经元结构 8 8.1.1 生物神经元的结构 n 工作状态：工作状态： l 兴奋状态兴奋状态：细胞膜电位：细胞膜电位 动作电位的阈值动作电位的阈值 神经冲动神经冲动 l 抑制

6、状态抑制状态：细胞膜电位细胞膜电位 0, wij = wji , 则则 ；当且仅当；当且仅当 )( 1 f n i v i n i ii n i n j jiij i dvvf R IvvvwE 1 0 1 111 )( 1 2 1 0 dt dE 时，（)10ni dt dvi 0 dt dE 72 8.4.3 随机神经网络 oHopfield神经网络中，神经元状态为神经网络中，神经元状态为1是根据其输入是是根据其输入是 否大于阈值确定的，是确定性的。否大于阈值确定的，是确定性的。 o随机神经网络中，神经元状态为随机神经网络中，神经元状态为1是随机的，服从一定是随机的，服从一定 的概率分布。

7、例如，服从玻尔兹曼的概率分布。例如，服从玻尔兹曼(Boltzmann)、高斯、高斯 (Gaussian)、柯西、柯西(Cauchy)分布等，从而构成玻尔兹曼分布等，从而构成玻尔兹曼 机、高斯机、柯西机等随机机。机、高斯机、柯西机等随机机。 73 8.4.3 随机神经网络 1. Boltzmann机机 o 1985年，加拿大多伦多大学教授欣顿年，加拿大多伦多大学教授欣顿(Hinton)等人借助统等人借助统 计物理学的概念和方法，提出了计物理学的概念和方法，提出了Boltzmann机神经网络模型。机神经网络模型。 o Boltzmann机是离散机是离散Hopfield神经网络的一种变型，通过神经网

8、络的一种变型，通过 对离散对离散Hopfield神经网络加以扰动，使其以概率的形式表达，神经网络加以扰动，使其以概率的形式表达， 而网络的模型方程不变，只是输出值类似于而网络的模型方程不变，只是输出值类似于Boltzmann分布分布 以概率分布取值。以概率分布取值。 o Boltzmann机是按机是按Boltzmann概率分布动作的神经网络。概率分布动作的神经网络。 74 8.4.3 随机神经网络 1. Boltzmann机机 （续）（续） o 离散Hopfield神经网络的输出： o Boltzman机的内部状态： o 神经元 输出值为0和1时的概率： )(sgn() 1( 1 i n ij

9、 j jiji tvwtv i n ij j jiji tvwI 1 )( TI i i p / e1 1 ) 1 ( i )1 (1)0( ii pp 75 8.4.3 随机神经网络 1. Boltzmann机机 （续）（续） o Boltzmann的能量函数： ii ii ij jiij vvvwE 2 1 神经元 状态转换时网络能量的变化： i j jiji vwE i 神经元 改变为状态“1”的概率： i )exp(1 1 T E p i i 76 2. 高斯机高斯机 8.4.3 随机神经网络 i n j jij i Ivw dt du 1 : :均值为均值为0的高斯随机变量（白噪声）

10、的高斯随机变量（白噪声） ，其方差为，其方差为 cT 3. 柯西机柯西机 i n j jij i Ivw dt du 1 : : 柯西随机变量（有色噪声）柯西随机变量（有色噪声） 77 8.4.4 混沌神经网络 1. 混沌混沌 o 混沌：自然界中一种较为普遍的非线性现象，其行 为看似混乱复杂且类似随机，却存在精致的内在规 律性。 o 混沌的性质 ： （1）随机性：类似随机变量的杂乱表现。 （2）遍历性：不重复地历经一定范围内的所有状态。 （3）规律性：由确定性的迭代式产生。 78 1. 混沌混沌 （续）（续） o混沌学的研究热潮开始于20世纪70年代初期。 o1963年，Lorenz在分析气候

11、数据时发现：初值十分 接近的两条曲线的最终结果会相差很大，从而获得 了混沌的第一个例子。 o1975年，Li-Yorke的论文周期3意味着混沌使 “混沌”一词首先出现在科技文献中。混沌的发现， 对科学的发展具有深远的影响。 8.4.4 混沌神经网络 79 8.4.4 混沌神经网络 2. 混沌神经元混沌神经元 o 混沌神经元（混沌神经元（1987年，年，Freeman）：构造混沌神经）：构造混沌神经 网络的基本单位。网络的基本单位。 )()()() 1(tItxFtkyty )1() 1(tyGtx 混沌神经元模型：混沌神经元模型： 80 8.4.4 混沌神经网络 3. 混沌神经网络混沌神经网络

12、 o 1990年，年，Aihara等提出了第一个混沌神经网络模等提出了第一个混沌神经网络模 型型(chaotic neural network，CNN)。 o 1991年，年，Inoue等利用两个混沌振荡子耦合成一个等利用两个混沌振荡子耦合成一个 神经元的方法，构造出一个混沌神经计算机神经元的方法，构造出一个混沌神经计算机. o 1992年，年，Nozawa基于欧拉离散化的基于欧拉离散化的Hopfield神经神经 网络，通过增加一个大的自反馈项，得到了一个与网络，通过增加一个大的自反馈项，得到了一个与 Aihara等提出的类似的等提出的类似的CNN模型。模型。 81 8.4.4 混沌神经网络

13、3. 混沌神经网络混沌神经网络 （1）基于模拟退火策略的自抑制混沌神经网络）基于模拟退火策略的自抑制混沌神经网络 1995年，年，Chen等提出的暂态混沌神经网络等提出的暂态混沌神经网络 (transient chaotic neural network，TCNN) ： / )( e1 1 )()( tu ii i tuftv )()()()() 1( 0 n j iiijijii ItvtzItvwtkutu )()1 () 1(tztz ii 82 8.4.4 混沌神经网络 3. 混沌神经网络混沌神经网络 （1）基于模拟退火策略的自抑制混沌神经网络）基于模拟退火策略的自抑制混沌神经网络 具

14、有具有暂态混沌特性暂态混沌特性。 能演化到一个稳定状态。能演化到一个稳定状态。 搜索区域为一分形结构。搜索区域为一分形结构。 具有混沌退火机制。具有混沌退火机制。 一种广义的混沌神经网络。一种广义的混沌神经网络。 可求解可求解0-1问题，也可求解连续非线性优化问题。问题，也可求解连续非线性优化问题。 83 8.4.4 混沌神经网络 o非线性函数：非线性函数： 15. 0)4 . 0()5 . 0( 1 . 0)6 . 0()7 . 0(),( 2 1 2 2 2 2 2 121 xxxxxxE 0 1501.00.0150.010.5, (0)-0.082,0.082,kIz， 84 8.4.

15、4 混沌神经网络 3. 混沌神经网络混沌神经网络 （2）基于加大时间步长的混沌神经网络）基于加大时间步长的混沌神经网络 oCHNN的欧拉离散化：的欧拉离散化： n j ijijii Itvwttu t ttu)()()1 ()( )()1 () 1(tttt 10 1998年，年，Wang和和Smith采用加大时间步长产生混沌：采用加大时间步长产生混沌： 85 8.4.4 混沌神经网络 3. 混沌神经网络混沌神经网络 （3）引入噪声的混沌神经网络）引入噪声的混沌神经网络 o1995年，年，Hayakawa等的混沌神经网络：等的混沌神经网络： n j ijijii Itvwttu t ttu)(

16、)()1 ()( )()()(tAtuftv iii 86 8.5 Hopfield神经网络的应用 o8.5.1 Hopfield神经网络在联想记忆中的应用神经网络在联想记忆中的应用 o8.5.2 Hopfield神经网络优化方法神经网络优化方法 87 如何实现如何实现HNN的联想记忆的联想记忆功能功能? n 网络能够通过联想来输出和输入模式网络能够通过联想来输出和输入模式 最为相似的样本模式。最为相似的样本模式。 8.5.1 Hopfield神经网络在联想记忆中的应用 88 传 感 器 神 经 网 络 分类器 苹 果 桔 子 o例例 n 传感器输出：传感器输出：外形，质地，重量外形，质地，重

17、量T T)1( 101 x标准桔子： T)2( 010 x标准苹果： 8.5.1 Hopfield神经网络在联想记忆中的应用 89 o例例 n 样本样本: 桔子）( 1 0, , 1 T)1( x（苹果） T)2( 0 1, 0,x l 步骤：步骤： （1）设计）设计DHNN结构结构 （2）设计连接权矩阵）设计连接权矩阵 （3）测试）测试 具体怎样实现联想具体怎样实现联想 记忆？记忆？ 8.5.1 Hopfield神经网络在联想记忆中的应用 90 n 样本样本: p （1）设计）设计DHNN结构结构 3神经元的神经元的DHNN结构图结构图 1 23 1 x 2 x 3 x 21 w 12 w

18、32 w 23 w 31 w 13 w 注：注：) 3 , 2 , 1(0 i i 桔子）( 1 0, 1, T)1( x （苹果） T)2( 0 1, , 0 x 8.5.1 Hopfield神经网络在联想记忆中的应用 91 n 样本样本: ， n 连接权：连接权： p（ 2）设计连接权矩阵）设计连接权矩阵 ) 12)(12() 12)(12( )2( 2 )2( 1 )1( 2 )1( 112 xxxxw 2 1221 ww ji jixx w l l j l i ij 0 )12)(12( 2 1 )()( ),.,2, 1;,.,2, 1(njniww ijji 211 ) 112()

19、 102() 102() 112( 桔子）( 1 0, , 1 T)1( x（苹果） T)2( 0 1, , 0 x 8.5.1 Hopfield神经网络在联想记忆中的应用 92 n 样本样本: ， n 连接权：连接权： T)1( 1 0, , 1 x T 01,0, )2( x ji jixx w l l j l i ij 0 )12)(12( 2 1 )()( ),.,2, 1;,.,2, 1(njniww ijji ) 12)(12() 12)(12( )2( 3 )2( 2 )1 ( 3 )1 ( 223 xxxxw 2 2332 ww 2) 1(1 ) 102() 112() 112

20、() 102( p （2）设计连接权矩阵）设计连接权矩阵 8.5.1 Hopfield神经网络在联想记忆中的应用 93 1 23 1 x 2 x 3 x -2 -2 2 2 -2 -2 022 202 220 W p （2）设计连接权矩阵）设计连接权矩阵 8.5.1 Hopfield神经网络在联想记忆中的应用 94 传 感 器 神 经 网 络 分类器 苹 果 桔 子 T)1( 1 , 0 , 1 x标准桔子： T)2( 0 1, , 0 x标准苹果： n 输入：输入：1，1，1T 输出输出 ? o （3）测试）测试 8.5.1 Hopfield神经网络在联想记忆中的应用 95 o （3）测试）

21、测试 312 l 调整次序调整次序： 1)0( 1)0( 1)0( 3 2 1 x x x l 初始状态初始状态： T 1 1, , 1 l 测试用例测试用例： l 样本样本： 1 23 1 x 2 x 3 x -2 -2 2 2 -2 -2 桔子）( 1 0, 1, T)1( x（苹果） T)2( 0 1, , 0 x 8.5.1 Hopfield神经网络在联想记忆中的应用 96 l 调整次序：调整次序： 213 1)0( 1)0( 1)0( 3 2 1 x x x k = 0 2 x 0) 4() 1) 2(101) 2() ) 0 () 1 ( 3 1 2 ffxwf j jj 1)0(

22、) 1 (, 1)0() 1 ( 3311 xxxx 1 23 1 x 2 x 3 x -2 -2 2 2 -2 -2 8.5.1 Hopfield神经网络在联想记忆中的应用 97 k = 1 1)1 ( 0)1 ( 1)1 ( 3 2 1 x x x 1)2() 120)2(10() ) 1 ()2( 3 1 1 ffxwf j jj x 1)1 ()2(, 0)1 ()2( 3322 xxxx 1 1 23 1 x 2 x 3 x -2 -2 2 2 -2 -2 l 调整次序调整次序： 213 8.5.1 Hopfield神经网络在联想记忆中的应用 98 1)2( 0)2( 1)2( 3

23、2 1 x x x k = 2 1)2() 100)2(12() ) 1 ()3( 3 1 3 ffxwf j jj 3 x 0)2()3(, 1)2()3( 2211 xxxx 1 2 3 1 x 2 x 3 x -2 -2 2 2 -2 -2 l 调整次序调整次序： 213 8.5.1 Hopfield神经网络在联想记忆中的应用 99 1)2( 0)2( 1)2( 3 2 1 x x x k = 2k = 3 1)3( 0)3( 1)3( 3 2 1 x x x 1)0( 1)0( 1)0( 3 2 1 x x x k = 0k = 1 1)1 ( 0)1 ( 1)1 ( 3 2 1 x

24、x x l 样本样本： l 调整次序调整次序： 1 23 1 x 2 x 3 x -2 -2 2 2 -2 -2 1 23 1 x 2 x 3 x -2 -2 2 2 -2 -2 1 23 1 x 2 x 3 x -2 -2 2 2 -2 -2 1 2 3 1 x 2 x 3 x -2 -2 2 2 -2 -2 2 1 32 1 32 1 32 1 3 桔子）( 1 0, , 1 T)1( x （苹果） T)2( 0 1, , 0 x 8.5.1 Hopfield神经网络在联想记忆中的应用 100 传感器 神经网络 分类器 苹果 桔子 o 例例 T)1( 1 0, , 1 x标准桔子： T)2

25、( 0 1, , 0 x标准苹果： n 输入：输入：1，1 ，1T n 输出：输出：1，0 ，1T 8.5.1 Hopfield神经网络在联想记忆中的应用 101 n 连续连续Hopfiled神经网络求解约束优化问题的基本思路：神经网络求解约束优化问题的基本思路： 最 优 化 问 题连 续 Hopfield神 经 网 络 目 标 函 数 可 行 解 最 优 解 能 量 函 数 状 态 稳 定 状 态 8.5.2 Hopfield神经网络优化方法 n 1985年，霍普菲尔德和塔克（年，霍普菲尔德和塔克（D. W. Tank）应用连续应用连续Hopfield 神经网络求解旅行商问题（神经网络求解旅

26、行商问题（traveling salesman problem，TSP） 获得成功。获得成功。 102 8.5.2 Hopfield神经网络优化方法 o 用神经网络方法求解优化问题的一般步骤：用神经网络方法求解优化问题的一般步骤： （1）将优化问题的每一个可行解用换位矩阵表示。）将优化问题的每一个可行解用换位矩阵表示。 （2）将换位矩阵与由）将换位矩阵与由 n 个神经元构成的神经网络相对应：个神经元构成的神经网络相对应： 每一个可行解的换位矩阵的各元素与相应的神经元稳态每一个可行解的换位矩阵的各元素与相应的神经元稳态 输出相对应。输出相对应。 （3）构造能量函数，使其最小值对应于优化问题的最优

27、）构造能量函数，使其最小值对应于优化问题的最优 解，并满足约束条件。解，并满足约束条件。 （4）用罚函数法构造目标函数，与）用罚函数法构造目标函数，与Hopfield神经网络的神经网络的 计算能量函数表达式相等，确定各连接权和偏置参数。计算能量函数表达式相等，确定各连接权和偏置参数。 （5）给定网络初始状态和网络参数等，使网络按动态方）给定网络初始状态和网络参数等，使网络按动态方 程运行，直到稳定状态，并将它解释为优化问题的解。程运行，直到稳定状态，并将它解释为优化问题的解。 103 o 应用举例：应用举例： Hopfield神经网络优化方法求解神经网络优化方法求解TSP。 n 1985年，霍

28、普菲尔德和塔克（年，霍普菲尔德和塔克（D. W. Tank）应用连续应用连续 Hopfield 神经网络求解旅行商问题获得成功。神经网络求解旅行商问题获得成功。 旅行商问题（旅行商问题（traveling salesman problem，TSP） ： 有有 n 个城市，城市间的距离或旅行成本已知，求合理个城市，城市间的距离或旅行成本已知，求合理 的路线使每个城市都访问一次，且总路径（或者总成的路线使每个城市都访问一次，且总路径（或者总成 本）为最短。本）为最短。 8.5.2 Hopfield神经网络优化方法 104 o 应用举例：应用举例：Hopfield神经网络优化方法求解神经网络优化方法

29、求解TSP 旅行商问题（旅行商问题（TSP）：）：典型的组合优化问题典型的组合优化问题 l n 个城市存在的路径数：个城市存在的路径数： l 用穷举法，用穷举法，Cray 计算机的计算速度：计算机的计算速度：108次次/秒。秒。 2 )!1(n n 1985年，年，Hopfield 和和Tank 用用Hopfield网络求解网络求解 n30 的的TSP 问题，问题，0.2 s 就得到次优解。就得到次优解。 8.5.2 Hopfield神经网络优化方法 105 5个城市的个城市的TSP： C1 C2 C3 C4 C5 100 50 100 50 75 100 125 125 125 75 C1

30、C2 C3 C4 C5 100 50 100 50 75 100 125 125 125 75 神经元数目：神经元数目：25 8.5.2 Hopfield神经网络优化方法 106 TSP的描述：的描述： xxyi iyiyxixy vvvdl)( 2 1 min 1,1, 次）（每个城市只能访问一 市）（每次只能访问一个城 xv ivst i xi x xi 1 1. xxyi iyiyxixy xi xi ixxy yixj xiij xjxi vvvd D nv C vv B vv A J )( 2 )( 222 1,1, 2 用罚函数法，写出优化问题的目标函数：用罚函数法，写出优化问题的

31、目标函数： 8.5.2 Hopfield神经网络优化方法 107 n x n i v xi n x n i v xi n x n i xixi n x n i n y n j yjxiyjxi xi xi vvf R E vvf R IvvvwE 11 0 1 1 11 0 1 111111 , d)( 1 d)( 1 2 1 Hopfield神经网络能量函数：神经网络能量函数： 8.5.2 Hopfield神经网络优化方法 令令E1 与目标函数与目标函数J相等，确定神经网络相等，确定神经网络的连接权值和偏置电流的连接权值和偏置电流： )()1 ()1 ( 1,1, ijijxyxyijijx

32、yyjxi DCBAW CnI xi 108 )tanh(1 2 1 )( 0 u u ufv xi xixi 神经网络的动态方程神经网络的动态方程： y iyiyxy xi xi xy yi ij xj xi xi xi n x n i v xi xi n x n i v xi xi xj xi vvdDnvCvBvA R u v vvf R J v vvf R E v E dt du C xi xi )()( )d)( 1 ( )d)( 1 ( 1,1, 11 0 1 11 0 1 1 8.5.2 Hopfield神经网络优化方法 109 选择合适的选择合适的A、B、C、D 和网络的初始状

33、态，按网络和网络的初始状态，按网络 动态方程演化直到收敛。动态方程演化直到收敛。 C1 C2 C3 C4 C5 100 50 100 50 75 100 125 125 125 75 8.5.2 Hopfield神经网络优化方法 110 n 神经网络优化计算目前存在的问题：神经网络优化计算目前存在的问题： （1）解的不稳定性。）解的不稳定性。 （2）参数难以确定。）参数难以确定。 （3）能量函数存在大量局部极小值，难以保证最优）能量函数存在大量局部极小值，难以保证最优 解。解。 8.5.2 Hopfield神经网络优化方法 111 8.6 Hopfield神经网络优化方法求解JSP o8.6.

34、1 作业车间调度问题作业车间调度问题 o8.6.2 JSP的的Hopfield神经网络及其求解神经网络及其求解 o8.6.3 作业车间生产调度举例作业车间生产调度举例 o8.6.4 基于随机神经网络的生产调度方法基于随机神经网络的生产调度方法 112 8.6.1 作业车间调度问题 o 作业车间调度问题（作业车间调度问题（job-shop scheduling Problem， oJSP）: 一类满足任务配置和顺序约束要求的资源分一类满足任务配置和顺序约束要求的资源分 配问题。配问题。 o 问题描述：给定一个作业（工件）的集合和一个机问题描述：给定一个作业（工件）的集合和一个机 器的集合，每个作

35、业包括多道工序，每道工序需要在一器的集合，每个作业包括多道工序，每道工序需要在一 台给定的机器上非间断地加工一段时间；每台机器一次台给定的机器上非间断地加工一段时间；每台机器一次 最多只能加工一道工序，调度就是把工序分配给机器上最多只能加工一道工序，调度就是把工序分配给机器上 某个时间段，使加工完成时间最短。某个时间段，使加工完成时间最短。 113 o Foo S. Y.和和Y. Takefuji在在1988年最早提出用年最早提出用Hopfield 神经网络求解神经网络求解JSP。 8.6.1 作业车间调度问题 o 对于对于单台机器加工问题单台机器加工问题，如果有，如果有 个作业而每个个作业而

36、每个 作业只考虑加工时间以及与操作序列有关的安装时作业只考虑加工时间以及与操作序列有关的安装时 间，则这个问题就和间，则这个问题就和 个城市的个城市的TSP等价。等价。 n n o Conway 等（等（1967），生产调度理论生产调度理论：“一般一般 作业车间调度问题是一个迷人的挑战性问题。尽管作业车间调度问题是一个迷人的挑战性问题。尽管 问题本身描述非常容易，但是朝着问题求解的方向问题本身描述非常容易，但是朝着问题求解的方向 作任何的推进都是极端困难的作任何的推进都是极端困难的”。 114 1. JSP的换位矩阵表示的换位矩阵表示 01,1,11,2,22,2,12,1,2 1,1,110

37、000 1,2,200001 2,2,100100 2,1,210000 2作业 2机器 JSP 8.6.2 JSP的Hopfield神经网络及其求解 “工序(2,2,1)依赖于另一 工序(1,2,2)”的命题成立 。 (1,2,2)：作业 1 的工序 2 在机器 2 上执行 。 “工序 不 依赖于任何别的 工序”的命题。 ),(kji 115 8.6.2 JSP的Hopfield神经网络及其求解 作业作业 机器机器JSP的工序约束条件：的工序约束条件： （1）各工序应服从）各工序应服从优先顺序优先顺序关系。任一工序可以依赖于另一个关系。任一工序可以依赖于另一个 工序，也可以不依赖于任何工序（

38、如在工序，也可以不依赖于任何工序（如在0时刻启动的工序）。时刻启动的工序）。 （2） 所有工序不允许所有工序不允许自依赖自依赖和和互依赖互依赖。 （3）允许在）允许在0时刻启动的工序数不超过时刻启动的工序数不超过 。即在。即在 时，在时，在0 时刻启动的工序数应为时刻启动的工序数应为 。 （4）在同一时刻启动的同一作业的工序不多于一个。）在同一时刻启动的同一作业的工序不多于一个。 （5 ）在同一时刻同一机器上启动的工序不多于一个。）在同一时刻同一机器上启动的工序不多于一个。 mn m mn m 116 8.6.2 JSP的Hopfield神经网络及其求解 2. JSP计算能量函数计算能量函数

39、: 与矩阵中与矩阵中 位置相对应的神经元的输出状态。位置相对应的神经元的输出状态。 2131 3 12 32 12 3 32 1111 2 1,1 21 11111 11 2 12 1(1),(1), 1 111 3 (1), 1 () 222 () 22 2 mn mnmnmn mnmnmn xixjxixi ix ix xijxi j i i xx i mnnmm xkkmikkmi k xkk kk n kkmi k k kk ABC Ev vvmnv v DD vmvv D v 13 12 (1), 11 mn kkmi k v xi v ),(ix 行约束 全局约束 非对称 约束 列

40、约束 117 8.6.2 JSP的Hopfield神经网络及其求解 3. Hopfield 神经网络的参数神经网络的参数 连续型连续型 Hopfield 神经网络的计算能量函数神经网络的计算能量函数: N i v i N i ii N i N j jiij i vvf R IvvvwE 1 0 1 111 d)( 1 2 1 神经元神经元 与神经元与神经元 之间的连接权之间的连接权 ),(ix),(jy yjxi w , 神经元神经元 的偏置电流的偏置电流 : ),(ix xi I 2131 3 12 32 1213 3 12 32 ,(1)(1)1 1112(1)(1) 1 11 3(1)(

41、1) 1 11 (1)(1)(1)(1) xi yjxyijy ij xixyij nmm ijx kkmy kkm k kk kk mnn x kkmy kkm k kk kk wABC DD D 11ixi mDBmnI ji ji ij ,0 ,1 118 8.6.2 JSP的Hopfield神经网络及其求解 4. Hopfield神经网络的运动方程神经网络的运动方程 3121 3 12 32 1312 3 3 11 111 ( 1)(1)1( 1)(1) 1112(1) (1) 1 111 3(1)(1) 1 d d (1)(1)(1) mnmn mn xixi xixjyj jyj

42、xi j i ixix ii x mnnmm yikkm ix kkm k ykk kk kkix kkm k k uu cAvBv tr Cv DvDv Dv 12 2 11 mnn xi kk k I 119 8.6.2 JSP的Hopfield神经网络及其求解 5. 成本树成本树 step1 ：根据换位矩阵，构造成本树。：根据换位矩阵，构造成本树。 step2： 计算成本树上各操作计算成本树上各操作 的开始时间的开始时间 和结束和结束 时间时间 。 step3 ：判断是否出现死锁调度。：判断是否出现死锁调度。 step4 ：调整死锁调度。：调整死锁调度。 ),(kji ijk S ijk

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