人工神经网络及其应用

null第 8 章 人工神经网络及其应用第 8 章 人工神经网络及其应用教材： 王万良《人工智能及其应用》（第2版） 高等教育出版社，2008. 6第8章 人工神经网络及其应用第8章 人工神经网络及其应用神经网络（neural networks，NN） 生物神经网络( natural neural network, NNN): 由中枢神经系统（脑和脊髓）及周围神经系统（感觉神经、运动神经等）所构成的错综复杂的神经网络，其中最重要的是脑神经系统。 人工神经网络(artificial neural networks, ANN): 模拟人脑神经系统的结构和功能，运用大量简单处理单元经广泛连接而组成的人工网络系统。 神经网络方法： 隐式的知识 表 关于同志近三年现实表现材料材料类招标技术评分表图表与交易pdf视力表打印pdf用图表说话 pdf 示方法第8章 人工神经网络及其应用第8章 人工神经网络及其应用8.1 神经元与神经网络 8.2 BP神经网络及其学习算法 8.3 BP神经网络的应用 8.4 Hopfield神经网络及其改进 8.5 Hopfield神经网络的应用 8.6 Hopfield神经网络优化方法求解JSP 第8章 人工神经网络及其应用第8章 人工神经网络及其应用8.1 神经元与神经网络 8.2 BP神经网络及其学习算法 8.3 BP神经网络的应用 8.4 Hopfield神经网络及其改进 8.5 Hopfield神经网络的应用 8.6 Hopfield神经网络优化方法求解JSP8.1 神经元与神经网络8.1 神经元与神经网络8.1.1 生物神经元的结构 8.1.2 神经元 数学 数学高考答题卡模板高考数学答题卡模板三年级数学混合运算测试卷数学作业设计案例新人教版八年级上数学教学计划 模型 8.1.3 神经网络结构与工作方式8.1.1 生物神经元的结构8.1.1 生物神经元的结构人脑由一千多亿（1011亿－ 1014 亿）个神经细胞（神经元）交织在一起的网状结构组成，其中大脑皮层约140亿个神经元，小脑皮层约1000亿个神经元。 神经元约有1000种类型，每个神经元大约与103－ 104个其他神经元相连接，形成极为错综复杂而又灵活多变的神经网络。 人的智能行为就是由如此高度复杂的组织产生的。浩瀚的宇宙中，也许只有包含数千忆颗星球的银河系的复杂性能够与大脑相比。8.1.1 生物神经元的结构8.1.1 生物神经元的结构（输入）（输出） 神经冲动生物神经元结构8.1.1 生物神经元的结构8.1.1 生物神经元的结构 工作状态： 兴奋状态：细胞膜电位 > 动作电位的阈值 → 神经冲动 抑制状态：细胞膜电位 < 动作电位的阈值 学习与遗忘：由于神经元结构的可塑性，突触的传递作用可增强和减弱 。8.1 神经元与神经网络8.1 神经元与神经网络8.1.1 生物神经元的结构 8.1.2 神经元数学模型 8.1.3 神经网络的结构与工作方式8.1.2 神经元数学模型8.1.2 神经元数学模型 1943年，麦克洛奇和皮兹提出M－P模型。一般模型： 8.1.2 神经元数学模型8.1.2 神经元数学模型 ：第 个神经元的输出。 ：第 个神经元的阈值。 ：外部输入。 ：权值。 8.1.2 神经元数学模型 线性环节的传递函数： ：1； ； ； 及其组合等。 8.1.2 神经元数学模型8.1.2 神经元数学模型8.1.2 神经元数学模型 非线性激励函数（传输函数、输出变换函数） （硬极限函数或阶跃函数）（对称硬极限函数）8.1.2 神经元数学模型8.1.2 神经元数学模型 非线性激励函数（传输函数、输出变换函数） （对数- S 形函数或S型函数）（双曲正切S形函数）8.1.2 神经元数学模型8.1.2 神经元数学模型 非线性激励函数（传输函数、输出变换函数） （饱和线性函数）（对称饱和线性函数）8.1.2 神经元数学模型8.1.2 神经元数学模型 非线性激励函数（传输函数、输出变换函数） （线性函数）（高斯或径向基函数）8.1.2 神经元数学模型8.1.2 神经元数学模型8.1.2 神经元数学模型8.1.2 神经元数学模型8.1 神经元与神经网络8.1 神经元与神经网络8.1.1 生物神经元的结构 8.1.2 神经元的数学模型 8.1.3 神经网络的结构与工作方式8.1.3 神经网络的结构与工作方式8.1.3 神经网络的结构与工作方式决定人工神经网络性能的三大要素：神经元的特性。 神经元之间相互连接的形式——拓扑结构。 为适应环境而改善性能的学习规则。8.1.3 神经网络的结构与工作方式8.1.3 神经网络的结构与工作方式 1. 神经网络的结构 （1）前馈型（ 前向型） 8.1.3 神经网络的结构与工作方式8.1.3 神经网络的结构与工作方式 1. 神经网络的结构 （2）反馈型（ Hopfield神经网络）8.1.3 神经网络的结构与工作方式8.1.3 神经网络的结构与工作方式 2. 神经网络的工作方式 同步（并行）方式：任一时刻神经网络中所有神经元同时调整状态。 异步（串行）方式：任一时刻只有一个神经元调整状态，而其它神经元的状态保持不变。8.1.4 神经网络的发展概况8.1.4 神经网络的发展概况 探索时期（开始于20世纪40年代）： 1943年，麦克劳（W. S. McCullocn）和匹茨（W. A. Pitts）首次提出一个神经网络模型——M－P模型。 1949年，赫布（D. O. Hebb）提出改变神经元连接强度的 Hebb学习规则。8.1.4 神经网络的发展概况8.1.4 神经网络的发展概况 1958年，罗森布拉特（F. Rosenblatt）提出感知器模型（perceptron）。 1959年，威德罗(B. Widrow)等提出自适应线性元件（adaline）网络，通过训练后可用于抵消通信中的回波和噪声。 1960年， 他和 M. Hoff 提出LMS （Least Mean Square 最小方差）算法的学习规则。 第一次热潮时期：20世纪50年代末－ 20世纪60年代初 8.1.4 神经网络的发展概况8.1.4 神经网络的发展概况 1969年，明斯基（M. Minsky）等在《Perceptron》中对感知器功能得出悲观结论。 1972年，T. Kohonen 和 J. Anderson 分别提出能完成记忆的新型神经网络。 1976年，S. Grossberg 在自组织神经网络方面的研究十分活跃。 低潮时期：20世纪60年代末－ 20世纪70年代 8.1.4 神经网络的发展概况8.1.4 神经网络的发展概况 第二次热潮时期： 20世纪80年代至今 1982年－1986年，霍普菲尔德（J. J. Hopfield）陆续提出离散的和连续的全互连神经网络模型，并成功求解旅行商问题（TSP）。 1986年，鲁姆尔哈特（Rumelhart）和麦克劳（McCellan）等在《Parallel Distributed Processing》中提出反向传播学习算法（B－P算法） 。 1987年6月，首届国际神经网络学术会议在美国圣地亚哥召开，成立了国际神经网络学会（INNS）。8.1.4 神经网络的发展概况8.1.4 神经网络的发展概况 神经网络控制的研究领域 基于神经网络的系统辨识 神经网络控制器 神经网络与其他算法（模糊逻辑、专家系统、遗传算法等）相结合 优化计算 第8章 人工神经网络及其应用第8章 人工神经网络及其应用8.1 神经元与神经网络 8.2 BP神经网络及其学习算法 8.3 BP神经网络的应用 8.4 Hopfield神经网络及其改进 8.5 Hopfield神经网络的应用 8.6 Hopfield神经网络优化方法求解JSP8.2 BP神经网络及其学习算法8.2 BP神经网络及其学习算法8.2.1 BP神经网络 （back-propagation neural network）的结构 8.2.2 BP学习算法 8.2.3 BP算法的实现 8.2 BP神经网络及其学习算法8.2 BP神经网络及其学习算法8.2.1 BP神经网络（back-propagation neural network）的结构 8.2.2 BP学习算法 8.2.3 BP算法的实现 8.2.1 BP神经网络的结构8.2.1 BP神经网络的结构 1. BP 网络结构 8.2.1 BP神经网络的结构8.2.1 BP神经网络的结构 2. 输入输出变换关系 8.2.1 BP神经网络的结构8.2.1 BP神经网络的结构3. 工作过程 第一阶段或网络训练阶段： N 组输入输出样本：xi=[xi1, xi2,…, xip1]T di=[di1, di2,…,dipm]T i=1, 2,…, N 对网络的连接权进行学习和调整，以使该网络实现给定样本的输入输出映射关系。 第二阶段或称工作阶段：把实验数据或实际数据输入到网络，网络在误差范围内预测计算出结果。 8.2 BP神经网络及其学习算法8.2 BP神经网络及其学习算法8.2.1 BP神经网络的结构 8.2.2 BP学习算法 8.2.3 BP算法的实现 8.2.2 BP学习算法8.2.2 BP学习算法两个问题：（1）是否存在一个BP神经网络能够逼近给定的样本或者函数。 （ 2）如何调整BP神经网络的连接权，使网络的输入与输出与给定的样本相同。 1986年，鲁梅尔哈特（D. Rumelhart）等提出BP学习算法。8.2.2 BP学习算法8.2.2 BP学习算法 目标函数： 约束条件： 连接权值的修正量： 1. 基本思想 8.2.2 BP学习算法8.2.2 BP学习算法 正向传播：输入信息由输入层传至隐层，最终在输出层输出。 反向传播：修改各层神经元的权值，使误差信号最小。 2. 学习算法 null8.2.2 BP学习算法 2. 学习算法null8.2.2 BP学习算法 2. 学习算法8.2 BP神经网络及其学习算法8.2 BP神经网络及其学习算法8.2.1 BP神经网络的结构 8.2.2 BP学习算法 8.2.3 BP算法的实现 null8.2.3 BP算法的实现（1） 隐层数及隐层神经元数的确定：目前尚无理论指导。 （2）初始权值的设置：一般以一个均值为0的随机分布设置网络的初始权值。 （3）训练数据预处理：线性的特征比例变换，将所有的特征变换到[0，1]或者[-1，1]区间内，使得在每个训练集上，每个特征的均值为0，并且具有相同的方差。 （4）后处理过程：当应用神经网络进行分类操作时，通常将输出值编码成所谓的名义变量，具体的值对应类别标号。 1. BP算法的 设计 领导形象设计圆作业设计ao工艺污水处理厂设计附属工程施工组织设计清扫机器人结构设计 8.2.3 BP算法的实现8.2.3 BP算法的实现（1）初始化：对所有连接权和阈值赋以随机任意小值； （2） 从 N 组输入输出样本中取一组样本：x=[x1, x2,…, xp1]T, d=[d1, d2,…,dpm]T, 把输入信息x=[x1, x2,…, xp1]T输入到BP网络中 （3）正向传播：计算各层节点的输出： （4）计算网络的实际输出与期望输出的误差： 2. BP算法的计算机实现流程 8.2.3 BP算法的实现8.2.3 BP算法的实现（5）反向传播：从输出层方向计算到第一个隐层，按连接权值修正公式向减小误差方向调整网络的各个连接权值。 （6）让t+1→t，取出另一组样本重复（2）－（5），直到 N 组输入输出样本的误差达到要求时为止。 2. BP算法的计算机实现流程 8.2.3 BP算法的实现8.2.3 BP算法的实现BP学习算法的程序框图8.2.4 BP算法的特点 分析 定性数据统计分析pdf销售业绩分析模板建筑结构震害分析销售进度分析表京东商城竞争战略分析 8.2.4 BP算法的特点分析 1. 特点 BP网络：多层前向网络（输入层、隐层、输出层）。 连接权值：通过Delta学习算法进行修正。 神经元传输函数：S形函数。 学习算法：正向传播、反向传播。 层与层的连接是单向的，信息的传播是双向的。8.2.4 BP算法的特点分析8.2.4 BP算法的特点分析 2. BP网络的主要优缺点 很好的逼近特性。 具有较强的泛化能力。 具有较好的容错性。 优点 收敛速度慢。 局部极值。 难以确定隐层和隐层结点的数目。 缺点null8.3 BP神经网络的应用8.3.1 BP神经网络在模式识别中的应用 8.3.2 BP神经网络在软测量中的应用 8.3.1 BP神经网络在模式识别中的应用8.3.1 BP神经网络在模式识别中的应用 模式识别研究用计算机模拟生物、人的感知，对模式信息，如图像、文字、语音等，进行识别和分类。 传统人工智能的研究部分地显示了人脑的归纳、推理等智能。但是，对于人类底层的智能，如视觉、听觉、触觉等方面，现代计算机系统的信息处理能力还不如一个幼儿园的孩子。 神经网络模型模拟了人脑神经系统的特点：处理单元的广泛连接；并行分布式信息储存、处理；自适应学习能力等。 神经网络模式识别方法具有较强的容错能力、自适应学习能力、并行信息处理能力。8.3.1 BP神经网络在模式识别中的应用 例 输入输出样本： 测试数据： 8.3.1 BP神经网络在模式识别中的应用8.3.1 BP神经网络在模式识别中的应用8.3.1 BP神经网络在模式识别中的应用例 设计一个三层BP网络对数字0至9进行分类。 每个数字用97的网格表示，灰色像素代表0，黑色像素代表1。将每个网格表示为0，1的长位串。位映射由左上角开始向下直到网格的整个一列，然后重复其他列。 选择BP网络结构为63-6-9。97个输入结点，对应上述网格的映射。9个输出结点对应10种分类。 使用的学习步长为0.3。训练600个周期，如果输出结点的值大于0.9，则取为ON，如果输出结点的值小于0.1，则取为OFF。 8.3.1 BP神经网络在模式识别中的应用 测试结果表明：除了8以外，所有被测的数字都能够被正确地识别。 对于数字8，神经网络的第6个结点的输出值为0.53，第8个结点的输出值为0.41，表明第8个样本是模糊的，可能是数字6，也可能是数字8，但也不完全确信是两者之一。 8.3.1 BP神经网络在模式识别中的应用当训练成功后，对如图所示测试数据进行测试。测试数据都有一个或者多个位丢失。null8.3.2 BP神经网络在软测量中的应用软测量技术 主导变量：被估计的变量。 辅助变量：与被估计变量相关的一组可测变量。null软测量系统的设计： 辅助变量的选择：变量类型、变量数量和检测点位置的选择。 数据采集与处理。 软测量模型的建立：通过辅助变量来获得对主导变量的最佳估计。 8.3.2 BP神经网络在软测量中的应用null序批式活性污泥法（SBR）8.3.2 BP神经网络在软测量中的应用nullBOD、COD、N和P：为软测量模型的主导变量。 ORP、DO、PH和MLSS：辅助变量。 三层BP网络： 8.3.2 BP神经网络在软测量中的应用第8章 人工神经网络及其应用第8章 人工神经网络及其应用8.1 神经元与神经网络 8.2 BP神经网络及其学习算法 8.3 BP神经网络的应用 8.4 Hopfield神经网络及其改进 8.5 Hopfield神经网络的应用 8.6 Hopfield神经网络优化方法求解JSP8.4 Hopfield神经网络及其改进8.4 Hopfield神经网络及其改进8.4.1 离散型Hopfield神经网络 8.4.2 连续型Hopfield神经网络及其VLSI实现 8.4.3 随机神经网络 8.4.4 混沌神经网络 8.4 Hopfield神经网络及其改进8.4 Hopfield神经网络及其改进8.4.1 离散型Hopfield神经网络 8.4.2 连续型Hopfield神经网络及其VLSI实现 8.4.3 随机神经网络 8.4.4 混沌神经网络 null1. 离散Hopfield神经网络模型 网络结构：离散Hopfield神经网络结构图……12(状态）(阈值）（连接权值）8.4.1 离散Hopfield 神经网络8.4.1 离散Hopfield 神经网络8.4.1 离散Hopfield 神经网络1. 离散Hopfield神经网络模型 输入输出关系：……或-18.4.1 离散Hopfield 神经网络8.4.1 离散Hopfield 神经网络1. 离散Hopfield神经网络模型 工作方式： 异步（串行）方式:同步（并行）方式:8.4.1 离散Hopfield 神经网络8.4.1 离散Hopfield 神经网络（异步或同步方式）初态：稳态：1. 离散Hopfield神经网络模型 工作过程：8.4.1 离散Hopfield 神经网络8.4.1 离散Hopfield 神经网络（异步或同步方式） 联想 记忆1. 离散Hopfield神经网络模型 工作过程：8.4.1 离散Hopfield 神经网络8.4.1 离散Hopfield 神经网络 稳定性定义： 若从某一时刻开始，网络中所有神经元的状态不再改变，即 ， 则称该网络是稳定的， 为网络的稳定点或吸引子 。 Hopfield神经网络是高维非线性系统，可能有许多稳定优态。从任何初始状态开始运动，总可以到某个稳定状态。这些稳定状态可以通过改变网络参数得到。 2. 网络的稳定性8.4.1 离散Hopfield 神经网络8.4.1 离散Hopfield 神经网络 稳定性定理证明：1983年，科恩（Cohen）、葛劳斯伯格（S. Grossberg）。 稳定性定理（Hopfield） 2. 网络的稳定性 并行稳定性 —— W：非负定对称阵 串行稳定性 —— W：对称阵8.4 Hopfield神经网络及其改进8.4 Hopfield神经网络及其改进8.4.1 离散型Hopfield神经网络 8.4.2 连续型Hopfield神经网络及其VLSI实现 8.4.2 连续型Hopfield神经网络及其VLSI实现8.4.2 连续型Hopfield神经网络及其VLSI实现连续Hopfield神经网络模型 网络的稳定性 应用举例 8.4.2 连续型Hopfield神经网络及其VLSI实现8.4.2 连续型Hopfield神经网络及其VLSI实现 1. 连续Hopfield神经网络模型 8.4.2 连续型Hopfield神经网络及其VLSI实现8.4.2 连续型Hopfield神经网络及其VLSI实现1. 连续Hopfield神经网络模型 8.4.2 连续型Hopfield神经网络及其VLSI实现8.4.2 连续型Hopfield神经网络及其VLSI实现 2. 网络的稳定性 计算能量函数 ： 定理：对于连续型 Hopfield 神经网络，若 为单调递增的连续函数， Ci > 0, wij = wji , 则 ；当且仅当 8.4.3 随机神经网络8.4.3 随机神经网络Hopfield神经网络中，神经元状态为1是根据其输入是否大于阈值确定的，是确定性的。 随机神经网络中，神经元状态为1是随机的，服从一定的概率分布。例如，服从玻尔兹曼(Boltzmann)、高斯(Gaussian)、柯西(Cauchy)分布等，从而构成玻尔兹曼机、高斯机、柯西机等随机机。8.4.3 随机神经网络8.4.3 随机神经网络1. Boltzmann机 1985年，加拿大多伦多大学教授欣顿(Hinton)等人借助统计物理学的概念和方法，提出了Boltzmann机神经网络模型。 Boltzmann机是离散Hopfield神经网络的一种变型，通过对离散Hopfield神经网络加以扰动，使其以概率的形式表达，而网络的模型方程不变，只是输出值类似于Boltzmann分布以概率分布取值。 Boltzmann机是按Boltzmann概率分布动作的神经网络。8.4.3 随机神经网络8.4.3 随机神经网络1. Boltzmann机 （续） 离散Hopfield神经网络的输出： Boltzman机的内部状态： 神经元 输出值为0和1时的概率：8.4.3 随机神经网络8.4.3 随机神经网络1. Boltzmann机 （续） Boltzmann的能量函数： 神经元 状态转换时网络能量的变化： 神经元 改变为状态“1”的概率： )exp(11TEpiiD-+=8.4.3 随机神经网络8.4.3 随机神经网络 2. 高斯机 3. 柯西机 : 柯西随机变量（有色噪声） 8.4.4 混沌神经网络8.4.4 混沌神经网络1. 混沌 混沌：自然界中一种较为普遍的非线性现象，其行 为看似混乱复杂且类似随机，却存在精致的内在规 律性。 混沌的性质 ： （1）随机性：类似随机变量的杂乱表现。 （2）遍历性：不重复地历经一定范围内的所有状态。 （3）规律性：由确定性的迭代式产生。 8.4.4 混沌神经网络8.4.4 混沌神经网络1. 混沌 （续） 混沌学的研究热潮开始于20世纪70年代初期。 1963年，Lorenz在分析气候数据时发现：初值十分接近的两条曲线的最终结果会相差很大，从而获得了混沌的第一个例子。 1975年，Li-Yorke的论文《周期3意味着混沌》使“混沌”一词首先出现在科技文献中。混沌的发现，对科学的发展具有深远的影响。 8.4.4 混沌神经网络8.4.4 混沌神经网络2. 混沌神经元 混沌神经元（1987年，Freeman）：构造混沌神经网络的基本单位。 8.4.4 混沌神经网络8.4.4 混沌神经网络3. 混沌神经网络 1990年，Aihara等提出了第一个混沌神经网络模型(chaotic neural network，CNN)。 1991年，Inoue等利用两个混沌振荡子耦合成一个神经元的方法，构造出一个混沌神经计算机. 1992年，Nozawa基于欧拉离散化的Hopfield神经网络，通过增加一个大的自反馈项，得到了一个与Aihara等提出的类似的CNN模型。 8.4.4 混沌神经网络8.4.4 混沌神经网络 3. 混沌神经网络 （1）基于模拟退火策略的自抑制混沌神经网络 1995年，Chen等提出的暂态混沌神经网络(transient chaotic neural network，TCNN) ： 8.4.4 混沌神经网络8.4.4 混沌神经网络 3. 混沌神经网络 （1）基于模拟退火策略的自抑制混沌神经网络 ① 具有暂态混沌特性。 ② 能演化到一个稳定状态。 ③ 搜索区域为一分形结构。 ④ 具有混沌退火机制。 ⑤ 一种广义的混沌神经网络。 ⑥ 可求解0-1问题，也可求解连续非线性优化问题。8.4.4 混沌神经网络8.4.4 混沌神经网络非线性函数： 8.4.4 混沌神经网络8.4.4 混沌神经网络 3. 混沌神经网络 （2）基于加大时间步长的混沌神经网络 CHNN的欧拉离散化： 1998年，Wang和Smith采用加大时间步长产生混沌：8.4.4 混沌神经网络8.4.4 混沌神经网络 3. 混沌神经网络 （3）引入噪声的混沌神经网络 1995年，Hayakawa等的混沌神经网络： 8.5 Hopfield神经网络的应用8.5 Hopfield神经网络的应用8.5.1 Hopfield神经网络在联想记忆中的应用 8.5.2 Hopfield神经网络优化方法 8.5.1 Hopfield神经网络在联想记忆中的应用8.5.1 Hopfield神经网络在联想记忆中的应用8.5.1 Hopfield神经网络在联想记忆中的应用例 传感器输出：[外形，质地，重量]T 8.5.1 Hopfield神经网络在联想记忆中的应用8.5.1 Hopfield神经网络在联想记忆中的应用 样本:例8.5.1 Hopfield神经网络在联想记忆中的应用8.5.1 Hopfield神经网络在联想记忆中的应用 样本: （1）设计DHNN结构8.5.1 Hopfield神经网络在联想记忆中的应用8.5.1 Hopfield神经网络在联想记忆中的应用（ 2）设计连接权矩阵 样本: ， 连接权：8.5.1 Hopfield神经网络在联想记忆中的应用8.5.1 Hopfield神经网络在联想记忆中的应用 （2）设计连接权矩阵 样本: ， 连接权：T]01,0,[)2(=x8.5.1 Hopfield神经网络在联想记忆中的应用8.5.1 Hopfield神经网络在联想记忆中的应用 （2）设计连接权矩阵8.5.1 Hopfield神经网络在联想记忆中的应用8.5.1 Hopfield神经网络在联想记忆中的应用 输入：[1，1，1]T 输出 ? （3）测试8.5.1 Hopfield神经网络在联想记忆中的应用8.5.1 Hopfield神经网络在联想记忆中的应用 （3）测试 初始状态： 测试用例： 样本：8.5.1 Hopfield神经网络在联想记忆中的应用8.5.1 Hopfield神经网络在联想记忆中的应用 调整次序： 2→1→3 8.5.1 Hopfield神经网络在联想记忆中的应用8.5.1 Hopfield神经网络在联想记忆中的应用 调整次序： 2→1→38.5.1 Hopfield神经网络在联想记忆中的应用8.5.1 Hopfield神经网络在联想记忆中的应用 调整次序： 2→1→38.5.1 Hopfield神经网络在联想记忆中的应用8.5.1 Hopfield神经网络在联想记忆中的应用 样本： 调整次序：2 1 32 1 32 1 32 1 38.5.1 Hopfield神经网络在联想记忆中的应用8.5.1 Hopfield神经网络在联想记忆中的应用 例 输入：[1，1 ，1]T 输出：[1，0 ，1]T 8.5.1 Hopfield神经网络在联想记忆中的应用8.5.2 Hopfield神经网络优化方法8.5.2 Hopfield神经网络优化方法 连续Hopfiled神经网络求解约束优化问题的基本思路： 1985年，霍普菲尔德和塔克（D. W. Tank）应用连续Hopfield 神经网络求解旅行商问题（traveling salesman problem，TSP）获得成功。8.5.2 Hopfield神经网络优化方法8.5.2 Hopfield神经网络优化方法 用神经网络方法求解优化问题的一般步骤： （1）将优化问题的每一个可行解用换位矩阵表示。 （2）将换位矩阵与由 n 个神经元构成的神经网络相对应：每一个可行解的换位矩阵的各元素与相应的神经元稳态输出相对应。 （3）构造能量函数，使其最小值对应于优化问题的最优解，并满足约束条件。 （4）用罚函数法构造目标函数，与Hopfield神经网络的计算能量函数表达式相等，确定各连接权和偏置参数。 （5）给定网络初始状态和网络参数等，使网络按动态方程运行，直到稳定状态，并将它解释为优化问题的解。8.5.2 Hopfield神经网络优化方法 应用举例： Hopfield神经网络优化方法求解TSP。 1985年，霍普菲尔德和塔克（D. W. Tank）应用连续Hopfield 神经网络求解旅行商问题获得成功。 旅行商问题（traveling salesman problem，TSP） ：有 n 个城市，城市间的距离或旅行成本已知，求合理的路线使每个城市都访问一次，且总路径（或者总成本）为最短。8.5.2 Hopfield神经网络优化方法8.5.2 Hopfield神经网络优化方法 应用举例：Hopfield神经网络优化方法求解TSP 旅行商问题（TSP）：典型的组合优化问题 n 个城市存在的路径数： 用穷举法，Cray 计算机的计算速度：108次/秒。 1985年，Hopfield 和Tank 用Hopfield网络求解 n＝30 的TSP问题，0.2 s 就得到次优解。 8.5.2 Hopfield神经网络优化方法8.5.2 Hopfield神经网络优化方法 5个城市的TSP：神经元数目：258.5.2 Hopfield神经网络优化方法8.5.2 Hopfield神经网络优化方法 TSP的描述： 用罚函数法，写出优化问题的目标函数：8.5.2 Hopfield神经网络优化方法8.5.2 Hopfield神经网络优化方法 Hopfield神经网络能量函数：8.5.2 Hopfield神经网络优化方法 令E1 与目标函数J相等，确定神经网络的连接权值和偏置电流：8.5.2 Hopfield神经网络优化方法神经网络的动态方程：8.5.2 Hopfield神经网络优化方法8.5.2 Hopfield神经网络优化方法 选择合适的A、B、C、D和网络的初始状态，按网络动态方程演化直到收敛。8.5.2 Hopfield神经网络优化方法8.5.2 Hopfield神经网络优化方法8.5.2 Hopfield神经网络优化方法 神经网络优化计算目前存在的问题： （1）解的不稳定性。 （2）参数难以确定。 （3）能量函数存在大量局部极小值，难以保证最优 解。null8.6 Hopfield神经网络优化方法求解JSP8.6.1 作业车间调度问题 8.6.2 JSP的Hopfield神经网络及其求解 8.6.3 作业车间生产调度举例 8.6.4 基于随机神经网络的生产调度方法 null8.6.1 作业车间调度问题 作业车间调度问题（job-shop scheduling Problem， JSP）: 一类满足任务配置和顺序约束要求的资源分配问题。 问题描述：给定一个作业（工件）的集合和一个机器的集合，每个作业包括多道工序，每道工序需要在一台给定的机器上非间断地加工一段时间；每台机器一次最多只能加工一道工序，调度就是把工序分配给机器上某个时间段，使加工完成时间最短。null Foo S. Y.和Y. Takefuji在1988年最早提出用Hopfield神经网络求解JSP。8.6.1 作业车间调度问题 对于单台机器加工问题，如果有 个作业而每个作业只考虑加工时间以及与操作序列有关的安装时间，则这个问题就和 个城市的TSP等价。 Conway 等（1967），《生产调度理论》：“一般作业车间调度问题是一个迷人的挑战性问题。尽管问题本身描述非常容易，但是朝着问题求解的方向作任何的推进都是极端困难的”。 null1. JSP的换位矩阵表示 8.6.2 JSP的Hopfield神经网络及其求解“工序(2,2,1)依赖于另一工序(1,2,2)”的命题成立 。(1,2,2)：作业 1 的工序 2 在机器 2 上执行 。“工序 不依赖于任何别的工序”的命题。 null8.6.2 JSP的Hopfield神经网络及其求解 作业 机器JSP的工序约束条件： （1）各工序应服从优先顺序关系。任一工序可以依赖于另一个工序，也可以不依赖于任何工序（如在0时刻启动的工序）。 （2） 所有工序不允许自依赖和互依赖。 （3）允许在0时刻启动的工序数不超过 。即在 时，在0时刻启动的工序数应为 。 （4）在同一时刻启动的同一作业的工序不多于一个。 （5 ）在同一时刻同一机器上启动的工序不多于一个。 null8.6.2 JSP的Hopfield神经网络及其求解 2. JSP计算能量函数 : 与矩阵中 位置相对应的神经元的输出状态。 行约束 全局约束 非对称约束 null8.6.2 JSP的Hopfield神经网络及其求解3. Hopfield 神经网络的参数 连续型 Hopfield 神经网络的计算能量函数: null8.6.2 JSP的Hopfield神经网络及其求解4. Hopfield神经网络的运动方程null8.6.2 JSP的Hopfield神经网络及其求解 5. 成本树 step1 ：根据换位矩阵，构造成本树。 step2： 计算成本树上各操作 的开始时间 和结束 时间 。 step3 ：判断是否出现死锁调度。 step4 ：调整死锁调度。null8.6.2 JSP的Hopfield神经网络及其求解6. 甘特图 step1：根据换位矩阵，计算成本树上各操作的开始时间和结束时间，并给出相应的甘特图。 step2：判断甘特图中每台机器上各作业的开始时间是否发生重叠。 step 3：判断同一作业的各操作的开始时间是否发生重叠。 step4：重复step2 和step3，直至甘特图中同一机器上各作业的开始时间和同一作业的各操作的开始时间都不发生重叠为止。null8.6.3 作业车间生产调度举例2作业3机器的JSP例子 所有的操作： 111，122，133，213，221，232。 null8.6.3 作业车间生产调度举例换位矩阵Hopfield 神经网络：6行7列的神经元阵列 null8.6.3 作业车间生产调度举例神经网络偏置电流矩阵 null8.6.3 作业车间生产调度举例计算能量函数为0的换位矩阵 null8.6.3 作业车间生产调度举例成本树 null8.6.3 作业车间生产调度举例甘特图 null 基本思想： 在系统寻优过程中，利用神经元状态更新的随机性，允许向较差方向搜索，以跳出局部极小。经多次寻查后，最终使系统稳定于能量最低状态，使神经网络收敛到计算能量函数的最小值0，从而使神经网络输出是一个可行调度解。 8.6.4 基于随机神经网络的生产调度方法null 根据改进Metropolis方法，求解JSP的基于模拟退火的神经网络算法： （1）初始化： 设置初始温度 ，合适的输入偏置电流，凝结温度 ，温度下降速率 ，在每个温度点的循环处理次数 。8.6.4 基于随机神经网络的生产调度方法（2）随机爬山： 对每个神经元 ，由求解网络方程计算输出电压。由网络稳定状态集组成成本树；求出最大成本变化量 。 null8.6.4 基于随机神经网络的生产调度方法 若 ，则转去（3）；否则计算能量变化量 若 ，则令 否则，令 计算概率null 选择均匀分布随机数RAND，若 ， 则令神经元 的状态 为 “1” ， 否则，令为 “0” 。 重复该步骤 次。 8.6.4 基于随机神经网络的生产调度方法（3）退火/收敛检验 令 ， 若 ，则转去（2）；否则停止。 null8.6.4 基于随机神经网络的生产调度方法模拟退火算法只有在初始温度充分高，温度下降足够慢，在每个温度点下循环处理无限多次，并在 时，才能收敛于全局最优解，但导致计算时间大大增加。 改进算法：快速模拟退火、并行模拟退火等。 null THE ENDArtificial Intelligence Principles and Applications