人工神经网络及其应用

Artificial Intelligence Principles and Applications第 8 章 人 工 神 经 网 络 及 其 应 用教 材 ： 王万良人工智能及其应用（第2版） 高等教育出版社，2008. 6 2第 8章 人 工 神 经 网 络 及 其 应 用神 经 网 络 （ neural networks， NN） 生 物 神 经 网 络 ( natural neural network, NNN): 由 中 枢 神 经 系统 （ 脑 和 脊 髓 ） 及 周 围 神 经 系 统 （ 感 觉 神 经 、 运 动 神 经 等 ） 所构 成 的 错 综 复 杂 的 神 经 网 络 ， 其 中 最 重 要 的 是 脑 神 经 系 统 。人 工 神 经 网 络 (artificial neural networks, ANN): 模 拟 人 脑 神 经系 统 的 结 构 和 功 能 ， 运 用 大 量 简 单 处 理 单 元 经 广 泛 连 接 而 组 成的 人 工 网 络 系 统 。神 经 网 络 方 法 ： 隐 式 的知 识 表 示 方 法 3第 8章 人 工 神 经 网 络 及 其 应 用o 8.1 神 经 元 与 神 经 网 络 o 8.2 BP神 经 网 络 及 其 学 习 算 法 o 8.3 BP神 经 网 络 的 应 用 o 8.4 Hopfield神 经 网 络 及 其 改 进 o 8.5 Hopfield神 经 网 络 的 应 用o 8.6 Hopfield神 经 网 络 优 化 方 法 求 解 JSP 4第 8章 人 工 神 经 网 络 及 其 应 用8.1 神 经 元 与 神 经 网 络 o 8.2 BP神 经 网 络 及 其 学 习 算 法 o 8.3 BP神 经 网 络 的 应 用o 8.4 Hopfield神 经 网 络 及 其 改 进o 8.5 Hopfield神 经 网 络 的 应 用o 8.6 Hopfield神 经 网 络 优 化 方 法 求 解 JSP 58.1 神 经 元 与 神 经 网 络8.1.1 生 物 神 经 元 的 结 构8.1.2 神 经 元 数 学 模 型8.1.3 神 经 网 络 结 构 与 工 作 方 式 68.1.1 生 物 神 经 元 的 结 构n 人 脑 由 一 千 多 亿 （ 1011亿 1014 亿 ） 个 神 经 细 胞 （ 神 经 元 ） 交 织在 一 起 的 网 状 结 构 组 成 ， 其 中 大脑 皮 层 约 140亿 个 神 经 元 ， 小 脑 皮层 约 1000亿 个 神 经 元 。n 神 经 元 约 有 1000种 类 型 ， 每 个 神 经 元 大 约 与 103 104个 其 他神 经 元 相 连 接 ， 形 成 极 为 错 综 复 杂 而 又 灵 活 多 变 的 神 经 网 络 。n 人 的 智 能 行 为 就 是 由 如 此 高 度 复 杂 的 组 织 产 生 的 。 浩 瀚 的 宇宙 中 ， 也 许 只 有 包 含 数 千 忆 颗 星 球 的 银 河 系 的 复 杂 性 能 够 与 大脑 相 比 。 78.1.1 生 物 神 经 元 的 结 构（ 输 入 ） （ 输 出 ） 神 经 冲 动 生 物 神 经 元 结 构 88.1.1 生 物 神 经 元 的 结 构n 工 作 状 态 ：l 兴 奋 状 态 ： 细 胞 膜 电 位 动 作 电 位 的 阈 值 神 经 冲 动 l 抑 制 状 态 ： 细 胞 膜 电 位 0, wij = wji , 则 ； 当 且 仅 当 )(1 f ni vini iini nj jiij i dvvfRIvvvwE 1 0 111 1 )(121 0dtdE时 ， （ )10 nidtdvi 0dtdE 728.4.3 随 机 神 经 网 络o Hopfield神 经 网 络 中 ， 神 经 元 状 态 为 1是 根 据 其 输 入 是否 大 于 阈 值 确 定 的 ， 是 确 定 性 的 。o 随 机 神 经 网 络 中 ， 神 经 元 状 态 为 1是 随 机 的 ， 服 从 一 定的 概 率 分 布 。 例 如 ， 服 从 玻 尔 兹 曼 (Boltzmann)、 高 斯(Gaussian)、 柯 西 (Cauchy)分 布 等 ， 从 而 构 成 玻 尔 兹 曼机 、 高 斯 机 、 柯 西 机 等 随 机 机 。 738.4.3 随 机 神 经 网 络1. Boltzmann机o 1985年 ， 加 拿 大 多 伦 多 大 学 教 授 欣 顿 (Hinton)等 人 借 助 统计 物 理 学 的 概 念 和 方 法 ， 提 出 了 Boltzmann机 神 经 网 络 模 型 。o Boltzmann机 是 离 散 Hopfield神 经 网 络 的 一 种 变 型 ， 通 过对 离 散 Hopfield神 经 网 络 加 以 扰 动 ， 使 其 以 概 率 的 形 式 表 达 ，而 网 络 的 模 型 方 程 不 变 ， 只 是 输 出 值 类 似 于 Boltzmann分 布以 概 率 分 布 取 值 。o Boltzmann机 是 按 Boltzmann概 率 分 布 动 作 的 神 经 网 络 。 748.4.3 随 机 神 经 网 络1. Boltzmann机 （ 续 ）o 离 散 Hopfield神 经 网 络 的 输 出 ：o Boltzman机 的 内 部 状 态 ：o 神 经 元 输 出 值 为 0和 1时 的 概 率 ： )(sgn()1( 1 inijj jiji tvwtv inijj jiji tvwI 1 )(TIi ip /e1 1)1( i )1(1)0( ii pp 758.4.3 随 机 神 经 网 络1. Boltzmann机 （ 续 ）o Boltzmann的 能 量 函 数 ： i i iiij jiij vvvwE 21 神 经 元 状 态 转 换 时 网 络 能 量 的 变 化 ： ij jiji vwE i 神 经 元 改 变 为 状 态 “ 1” 的 概 率 ： i )exp(1 1 TEp ii 76 2. 高 斯 机 8.4.3 随 机 神 经 网 络 inj jiji Ivwdtdu 1 :均 值 为 0的 高 斯 随 机 变 量 （ 白 噪 声 ） ， 其 方 差 为 cT3. 柯 西 机 inj jiji Ivwdtdu 1 : 柯 西 随 机 变 量 （ 有 色 噪 声 ） 778.4.4 混 沌 神 经 网 络1. 混 沌o 混 沌 ： 自 然 界 中 一 种 较 为 普 遍 的 非 线 性 现 象 ， 其 行 为 看 似 混 乱 复 杂 且 类 似 随 机 ， 却 存 在 精 致 的 内 在 规 律 性 。o 混 沌 的 性 质 ：（ 1） 随 机 性 ： 类 似 随 机 变 量 的 杂 乱 表 现 。（ 2） 遍 历 性 ： 不 重 复 地 历 经 一 定 范 围 内 的 所 有 状 态 。（ 3） 规 律 性 ： 由 确 定 性 的 迭 代 式 产 生 。 781. 混 沌 （ 续 ）o 混 沌 学 的 研 究 热 潮 开 始 于 20世 纪 70年 代 初 期 。o 1963年 ， Lorenz在 分 析 气 候 数 据 时 发 现 ： 初 值 十 分接 近 的 两 条 曲 线 的 最 终 结 果 会 相 差 很 大 ， 从 而 获 得了 混 沌 的 第 一 个 例 子 。o 1975年 ， Li-Yorke的 论 文 周 期 3意 味 着 混 沌 使“ 混 沌 ” 一 词 首 先 出 现 在 科 技 文 献 中 。 混 沌 的 发 现 ，对 科 学 的 发 展 具 有 深 远 的 影 响 。 8.4.4 混 沌 神 经 网 络 798.4.4 混 沌 神 经 网 络2. 混 沌 神 经 元 o 混 沌 神 经 元 （ 1987年 ， Freeman） ： 构 造 混 沌 神 经网 络 的 基 本 单 位 。 )()()()1( tItxFtkyty )1()1( tyGtx 混 沌 神 经 元 模 型 ： 808.4.4 混 沌 神 经 网 络3. 混 沌 神 经 网 络 o 1990年 ， Aihara等 提 出 了 第 一 个 混 沌 神 经 网 络 模型 (chaotic neural network， CNN)。o 1991年 ， Inoue等 利 用 两 个 混 沌 振 荡 子 耦 合 成 一 个神 经 元 的 方 法 ， 构 造 出 一 个 混 沌 神 经 计 算 机 .o 1992年 ， Nozawa基 于 欧 拉 离 散 化 的 Hopfield神 经网 络 ， 通 过 增 加 一 个 大 的 自 反 馈 项 ， 得 到 了 一 个 与Aihara等 提 出 的 类 似 的 CNN模 型 。 818.4.4 混 沌 神 经 网 络 3. 混 沌 神 经 网 络（ 1） 基 于 模 拟 退 火 策 略 的 自 抑 制 混 沌 神 经 网 络 1995年 ， Chen等 提 出 的 暂 态 混 沌 神 经 网 络(transient chaotic neural network， TCNN) ：/)(e1 1)()( tuii ituftv )()()()()1( 0 nj iiijijii ItvtzItvwtkutu )()1()1( tztz ii 828.4.4 混 沌 神 经 网 络 3. 混 沌 神 经 网 络（ 1） 基 于 模 拟 退 火 策 略 的 自 抑 制 混 沌 神 经 网 络 具 有 暂 态 混 沌 特 性 。 能 演 化 到 一 个 稳 定 状 态 。 搜 索 区 域 为 一 分 形 结 构 。 具 有 混 沌 退 火 机 制 。 一 种 广 义 的 混 沌 神 经 网 络 。 可 求 解 0-1问 题 ， 也 可 求 解 连 续 非 线 性 优 化 问 题 。 838.4.4 混 沌 神 经 网 络o 非 线 性 函 数 ： 15.0)4.0()5.0(1.0)6.0()7.0(),( 2122222121 xxxxxxE 0150 1.0 0.015 0.01 0.5, (0) -0.082,0.082,k I z ， ， ， ， 848.4.4 混 沌 神 经 网 络 3. 混 沌 神 经 网 络（ 2） 基 于 加 大 时 间 步 长 的 混 沌 神 经 网 络 o CHNN的 欧 拉 离 散 化 ： nj ijijii Itvwttutttu )()()1()( )()1()1( tttt 10 1998年 ， Wang和 Smith采 用 加 大 时 间 步 长 产 生 混 沌 ： 858.4.4 混 沌 神 经 网 络 3. 混 沌 神 经 网 络（ 3） 引 入 噪 声 的 混 沌 神 经 网 络 o 1995年 ， Hayakawa等 的 混 沌 神 经 网 络 ： nj ijijii Itvwttutttu )()()1()( )()()( tAtuftv iii 868.5 Hopfield神 经 网 络 的 应 用8.5.1 Hopfield神 经 网 络 在 联 想 记 忆 中 的 应 用8.5.2 Hopfield神 经 网 络 优 化 方 法 87如 何 实 现 HNN的 联 想 记 忆 功 能 ?n 网 络 能 够 通 过 联 想 来 输 出 和 输 入 模 式最 为 相 似 的 样 本 模 式 。8.5.1 Hopfield神 经 网 络 在 联 想 记 忆 中 的 应 用 88传感器 神经网络 分类器苹果桔子o 例n 传 感 器 输 出 ： 外 形 ， 质 地 ， 重 量 T T)1( 101x标 准 桔 子 ： T)2( 010 x标 准 苹 果 ：8.5.1 Hopfield神 经 网 络 在 联 想 记 忆 中 的 应 用 89o 例n 样 本 : 桔 子 ）(1 0, ,1 T)1( x （ 苹 果 ）T)2( 0 1, 0,xl 步 骤 ： （ 1） 设 计 DHNN结 构（ 2） 设 计 连 接 权 矩 阵（ 3） 测 试具 体 怎 样 实 现 联 想记 忆 ？8.5.1 Hopfield神 经 网 络 在 联 想 记 忆 中 的 应 用 90n 样 本 : （ 1） 设 计 DHNN结 构3神 经 元 的 DHNN结 构 图12 31x2x 3x21w 12w 32w23w 31w13w 注 ： )3,2,1(0 ii 桔 子 ）(1 0, 1, T)1( x （ 苹 果 ）T)2( 0 1, ,0 x8.5.1 Hopfield神 经 网 络 在 联 想 记 忆 中 的 应 用 91n 样 本 : ，n 连 接 权 ：（ 2） 设 计 连 接 权 矩 阵 )12)(12()12)(12( )2(2)2(1)1(2)1(112 xxxxw 21221 ww ji jixxw l ljliij 0 )12)(12(21 )()( ),.,2,1;,.,2,1( njniww ijji 211 )112()102()102()112( 桔 子 ）(1 0, ,1 T)1( x （ 苹 果 ）T)2( 0 1, ,0 x8.5.1 Hopfield神 经 网 络 在 联 想 记 忆 中 的 应 用 92n 样 本 : ，n 连 接 权 ： T)1( 1 0, ,1x T01,0,)2( x ji jixxw l ljliij 0 )12)(12(21 )()( ),.,2,1;,.,2,1( njniww ijji )12)(12()12)(12( )2(3)2(2)1(3)1(223 xxxxw 22332 ww 2)1(1 )102()112()112()102( （ 2） 设 计 连 接 权 矩 阵8.5.1 Hopfield神 经 网 络 在 联 想 记 忆 中 的 应 用 9312 31x2x 3x-2-2 22-2 -2 022 202 220W （ 2） 设 计 连 接 权 矩 阵8.5.1 Hopfield神 经 网 络 在 联 想 记 忆 中 的 应 用 94传感器 神经网络 分类器苹果桔子 T)1( 1 ,0 ,1x标 准 桔 子 ： T)2( 0 1, ,0 x标 准 苹 果 ：n 输 入 ： 1， 1， 1T 输 出 ? （ 3） 测 试8.5.1 Hopfield神 经 网 络 在 联 想 记 忆 中 的 应 用 95 （ 3） 测 试 312 l 调 整 次 序 ： 1)0( 1)0( 1)0(321xxxl 初 始 状 态 ： T1 1, ,1l 测 试 用 例 ：l 样 本 ： 12 31x2x 3x-2-2 22-2 -2桔 子 ）(1 0, 1, T)1( x （ 苹 果 ）T)2( 0 1, ,0 x8.5.1 Hopfield神 经 网 络 在 联 想 记 忆 中 的 应 用 96l 调 整 次 序 ： 213 1)0( 1)0( 1)0(321xxxk = 02x 0)4()1)2(101)2()0()1( 31 2 ffxwf j jj 1)0()1(,1)0()1( 3311 xxxx 12 31x2x 3x-2-2 22-2 -28.5.1 Hopfield神 经 网 络 在 联 想 记 忆 中 的 应 用 97k = 1 1)1( 0)1( 1)1(321xxx 1)2()120)2(10()1()2( 31 1 ffxwf j jjx 1)1()2(,0)1()2( 3322 xxxx1 12 31x2x 3x-2-2 22-2 -2l 调 整 次 序 ： 2138.5.1 Hopfield神 经 网 络 在 联 想 记 忆 中 的 应 用 98 1)2( 0)2( 1)2(321xxxk = 2 1)2()100)2(12()1()3( 31 3 ffxwf j jj3x 0)2()3(,1)2()3( 2211 xxxx 12 31x2x 3x-2-2 22-2 -2l 调 整 次 序 ： 2138.5.1 Hopfield神 经 网 络 在 联 想 记 忆 中 的 应 用 99 1)2( 0)2( 1)2(321xxxk = 2 k = 3 1)3( 0)3( 1)3(321xxx 1)0( 1)0( 1)0(321xxx k = 0 k = 1 1)1( 0)1( 1)1(321xxxl 样 本 ：l 调 整 次 序 ： 12 31x2x 3x-2-2 22-2 -22 1 3桔 子 ）(1 0, ,1 T)1( x （ 苹 果 ）T)2( 0 1, ,0 x8.5.1 Hopfield神 经 网 络 在 联 想 记 忆 中 的 应 用 100传感器 神经网络 分类器苹果桔子o 例 T)1( 1 0, ,1x标 准 桔 子 ： T)2( 0 1, ,0 x标 准 苹 果 ：n 输 入 ： 1， 1 ， 1T n 输 出 ： 1， 0 ， 1T 8.5.1 Hopfield神 经 网 络 在 联 想 记 忆 中 的 应 用 101n 连 续 Hopfiled神 经 网 络 求 解 约 束 优 化 问 题 的 基 本 思 路 ： 最优化问题 连续Hopfield神经网络 目标函数 可 行 解 最 优 解 能量函数状 态 稳定状态8.5.2 Hopfield神 经 网 络 优 化 方 法n 1985年 ， 霍 普 菲 尔 德 和 塔 克 （ D. W. Tank） 应 用 连 续 Hopfield 神 经 网 络 求 解 旅 行 商 问 题 （ traveling salesman problem， TSP）获 得 成 功 。 1028.5.2 Hopfield神 经 网 络 优 化 方 法o 用 神 经 网 络 方 法 求 解 优 化 问 题 的 一 般 步 骤 ：（ 1） 将 优 化 问 题 的 每 一 个 可 行 解 用 换 位 矩 阵 表 示 。（ 2） 将 换 位 矩 阵 与 由 n 个 神 经 元 构 成 的 神 经 网 络 相 对 应 ：每 一 个 可 行 解 的 换 位 矩 阵 的 各 元 素 与 相 应 的 神 经 元 稳 态输 出 相 对 应 。（ 3） 构 造 能 量 函 数 ， 使 其 最 小 值 对 应 于 优 化 问 题 的 最 优解 ， 并 满 足 约 束 条 件 。（ 4） 用 罚 函 数 法 构 造 目 标 函 数 ， 与 Hopfield神 经 网 络 的计 算 能 量 函 数 表 达 式 相 等 ， 确 定 各 连 接 权 和 偏 置 参 数 。（ 5） 给 定 网 络 初 始 状 态 和 网 络 参 数 等 ， 使 网 络 按 动 态 方程 运 行 ， 直 到 稳 定 状 态 ， 并 将 它 解 释 为 优 化 问 题 的 解 。 103o 应 用 举 例 ： Hopfield神 经 网 络 优 化 方 法 求 解 TSP。n 1985年 ， 霍 普 菲 尔 德 和 塔 克 （ D. W. Tank） 应 用 连 续Hopfield 神 经 网 络 求 解 旅 行 商 问 题 获 得 成 功 。 旅 行 商 问 题 （ traveling salesman problem， TSP） ：有 n 个 城 市 ， 城 市 间 的 距 离 或 旅 行 成 本 已 知 ， 求 合 理的 路 线 使 每 个 城 市 都 访 问 一 次 ， 且 总 路 径 （ 或 者 总 成本 ） 为 最 短 。8.5.2 Hopfield神 经 网 络 优 化 方 法 104o 应 用 举 例 ： Hopfield神 经 网 络 优 化 方 法 求 解 TSP 旅 行 商 问 题 （ TSP） ： 典 型 的 组 合 优 化 问 题l n 个 城 市 存 在 的 路 径 数 ：l 用 穷 举 法 ， Cray 计 算 机 的 计 算 速 度 ： 108次 /秒 。2 )!1( nn 1985年 ， Hopfield 和 Tank 用 Hopfield网 络 求 解 n 30 的 TSP问 题 ， 0.2 s 就 得 到 次 优 解 。 8.5.2 Hopfield神 经 网 络 优 化 方 法 105 5个 城 市 的 TSP：C1 C2C3C4C5 100 501005075 100125125 12575 C1 C2C3C4C5 100 501005075 100125125 12575神 经 元 数 目 ： 258.5.2 Hopfield神 经 网 络 优 化 方 法 106 TSP的 描 述 ： x xy i iyiyxixy vvvdl )(21min 1,1, 次 ）（ 每 个 城 市 只 能 访 问 一 市 ）（ 每 次 只 能 访 问 一 个 城xv ivst i xix xi 11. x xy i iyiyxixy x i xii x xy yixjx i ij xjxi vvvdD nvCvvBvvAJ )(2 )(222 1,1, 2 用 罚 函 数 法 ， 写 出 优 化 问 题 的 目 标 函 数 ：8.5.2 Hopfield神 经 网 络 优 化 方 法 107 nx ni vxi nx ni vxinx ni xixinx ni ny nj yjxiyjxixi xivvfRE vvfRIvvvwE 1 1 0 11 1 1 0 11 11 1 1 1 , d)(1 d)(121 Hopfield神 经 网 络 能 量 函 数 ：8.5.2 Hopfield神 经 网 络 优 化 方 法 令 E1 与 目 标 函 数 J相 等 ， 确 定 神 经 网 络 的 连 接 权 值 和 偏 置 电 流 ：)()1()1( 1,1, ijijxyxyijijxyyjxi DCBAW CnIxi 108)tanh(121)( 0uuufv xixixi 神 经 网 络 的 动 态 方 程 ： y iyiyxyx i xixy yiij xjxixi xinx ni vxi xinx ni vxixixjxi vvdDnvCvBvARu v vvfRJ v vvfREvEdtduC xi xi )()( )d)(1( )d)(1( 1,1,1 1 0 1 1 1 0 118.5.2 Hopfield神 经 网 络 优 化 方 法 109 选 择 合 适 的 A、 B、 C、 D和 网 络 的 初 始 状 态 ， 按 网 络动 态 方 程 演 化 直 到 收 敛 。 C1 C2C3C4C5 100 501005075 100125125 125758.5.2 Hopfield神 经 网 络 优 化 方 法 110n 神 经 网 络 优 化 计 算 目 前 存 在 的 问 题 ：（ 1） 解 的 不 稳 定 性 。（ 2） 参 数 难 以 确 定 。（ 3） 能 量 函 数 存 在 大 量 局 部 极 小 值 ， 难 以 保 证 最 优 解 。8.5.2 Hopfield神 经 网 络 优 化 方 法 1118.6 Hopfield神 经 网 络 优 化 方 法 求 解 JSP8.6.1 作 业 车 间 调 度 问 题8.6.2 JSP的 Hopfield神 经 网 络 及 其 求 解8.6.3 作 业 车 间 生 产 调 度 举 例8.6.4 基 于 随 机 神 经 网 络 的 生 产 调 度 方 法 1128.6.1 作 业 车 间 调 度 问 题 作 业 车 间 调 度 问 题 （ job-shop scheduling Problem，JSP） : 一 类 满 足 任 务 配 置 和 顺 序 约 束 要 求 的 资 源 分 配问 题 。 问 题 描 述 ： 给 定 一 个 作 业 （ 工 件 ） 的 集 合 和 一 个 机器 的 集 合 ， 每 个 作 业 包 括 多 道 工 序 ， 每 道 工 序 需 要 在 一台 给 定 的 机 器 上 非 间 断 地 加 工 一 段 时 间 ； 每 台 机 器 一 次最 多 只 能 加 工 一 道 工 序 ， 调 度 就 是 把 工 序 分 配 给 机 器 上某 个 时 间 段 ， 使 加 工 完 成 时 间 最 短 。 113o Foo S. Y.和 Y. Takefuji在 1988年 最 早 提 出 用Hopfield神 经 网 络 求 解 JSP。8.6.1 作 业 车 间 调 度 问 题o 对 于 单 台 机 器 加 工 问 题 ， 如 果 有 个 作 业 而 每 个作 业 只 考 虑 加 工 时 间 以 及 与 操 作 序 列 有 关 的 安 装 时间 ， 则 这 个 问 题 就 和 个 城 市 的 TSP等 价 。 n no Conway 等 （ 1967） ， 生 产 调 度 理 论 ： “ 一般 作 业 车 间 调 度 问 题 是 一 个 迷 人 的 挑 战 性 问 题 。 尽管 问 题 本 身 描 述 非 常 容 易 ， 但 是 朝 着 问 题 求 解 的 方向 作 任 何 的 推 进 都 是 极 端 困 难 的 ” 。 1141. JSP的 换 位 矩 阵 表 示 0 1,1,1 1,2,2 2,2,1 2,1,21,1,1 1 0 0 0 01,2,2 0 0 0 0 12,2,1 0 0 1 0 02,1,2 1 0 0 0 02 作 业 2 机 器 JSP8.6.2 JSP的 Hopfield神 经 网 络 及 其 求 解“工 序 (2,2,1)依 赖 于 另 一工 序 (1,2,2)”的 命 题 成 立 。 (1,2,2)： 作 业 1 的 工 序 2 在 机 器 2 上 执 行 。“ 工 序 不依 赖 于 任 何 别 的工 序 ” 的 命 题 。 ),( kji 1158.6.2 JSP的 Hopfield神 经 网 络 及 其 求 解 作 业 机 器 JSP的 工 序 约 束 条 件 ：（ 1） 各 工 序 应 服 从 优 先 顺 序 关 系 。 任 一 工 序 可 以 依 赖 于 另 一 个工 序 ， 也 可 以 不 依 赖 于 任 何 工 序 （ 如 在 0时 刻 启 动 的 工 序 ） 。（ 2） 所 有 工 序 不 允 许 自 依 赖 和 互 依 赖 。（ 3） 允 许 在 0时 刻 启 动 的 工 序 数 不 超 过 。 即 在 时 ， 在 0时 刻 启 动 的 工 序 数 应 为 。（ 4） 在 同 一 时 刻 启 动 的 同 一 作 业 的 工 序 不 多 于 一 个 。（ 5 ） 在 同 一 时 刻 同 一 机 器 上 启 动 的 工 序 不 多 于 一 个 。 mn m mnm 1168.6.2 JSP的 Hopfield神 经 网 络 及 其 求 解 2. JSP计 算 能 量 函 数 : 与 矩 阵 中 位 置 相 对 应 的 神 经 元 的 输 出 状 态 。 2 1 3 131 2 3 21 233 21 1 1 12 1, 12 11 1 1 1 1 1 121 21 ( 1) , ( 1) ,11 1 13 ( 1) ,1 ( )2 2 2( )2 22mn mn mn mn mn mn mnxi xj xi xi i xi xx i j x ij i i x x imn n m mx k k m i k k m ikx k k k kn k k m ikk k kA B CE v v v mn v vD Dv m v vD v 1 31 2 ( 1) ,1 1m n k k m ik v xiv ),( ix 行 约 束 全 局 约 束 非 对 称约 束 列 约 束 1178.6.2 JSP的 Hopfield神 经 网 络 及 其 求 解3. Hopfield 神 经 网 络 的 参 数 连 续 型 Hopfield 神 经 网 络 的 计 算 能 量 函 数 : Ni viNi iiNi Nj jiij i vvfRIvvvwE 1 0 111 1 d)(121 神 经 元 与 神 经 元 之 间 的 连 接 权),( ix ),( jy yjxiw , 神 经 元 的 偏 置 电 流 : ),( ix xiI2 1 3 131 2 3 21 2 1 331 2 3 2, ( 1) ( 1) 11 1 1 2 ( 1) ( 1) 11 13 ( 1) ( 1) 11 1(1 ) (1 )(1 )(1 )xi yj xy ij y i j x i xy ijn m mi j x k k m y k k mkk k k km n n x k k m y k k mkk k k kw A B CD DD 11 ixi mDBmnI ji jiij ,0,1 1188.6.2 JSP的 Hopfield神 经 网 络 及 其 求 解4. Hopfield神 经 网 络 的 运 动 方 程 3 1 2 131 2 3 21 3 1 233 1 11 1 1( 1)( 1) 1 ( 1) ( 1)1 1 1 2 ( 1) ( 1) 11 1 13 ( 1) ( 1) 1dd (1 )(1 )(1 )mn mn mnxi xixi xj yjj y jxi j ii x i x i i xmn n m my i k k mi x k k mky k k k kk k i x k k mkku uc A v B vt rCvD v D vD v 1 2 21 1m n n xik k k I 1198.6.2 JSP的 Hopfield神 经 网 络 及 其 求 解 5. 成 本 树 step1 ： 根 据 换 位 矩 阵 ， 构 造 成 本 树 。 step2： 计 算 成 本 树 上 各 操 作 的 开 始 时 间 和 结 束 时 间 。 step3 ： 判 断 是 否 出 现 死 锁 调 度 。 step4 ： 调 整 死 锁 调 度 。 ),( kji ijkSijkE 1208.6.2 JSP的 Hopfield神 经 网 络 及 其 求 解6. 甘 特 图step1： 根 据 换 位 矩 阵 ， 计 算 成 本 树 上 各 操 作 的 开 始 时 间 和 结束 时 间 ， 并 给 出 相 应 的 甘 特 图 。step2： 判 断 甘 特 图 中 每 台 机 器 上 各 作 业 的 开 始 时 间 是 否 发 生重 叠 。step 3： 判 断 同 一 作 业 的 各 操 作 的 开 始 时 间 是 否 发 生 重 叠 。step4： 重 复 step2 和 step3， 直 至 甘 特 图 中 同 一 机 器 上 各 作 业的 开 始 时 间 和 同 一 作 业 的 各 操 作 的 开 始 时 间 都 不 发 生 重 叠 为止 。 1218.6.3 作 业 车 间 生 产 调 度 举 例o 2作 业 3机 器 的 JSP例 子 所 有 的 操 作 ：111， 122， 133，213， 221， 232。 1228.6.3 作 业 车 间 生 产 调 度 举 例o 换 位 矩 阵Hopfield 神 经 网 络 ： 6行 7列 的 神 经 元 阵 列 1238.6.3 作 业 车 间 生 产 调 度 举 例o 神 经 网 络 偏 置 电 流 矩 阵 300,300,500,200,100,500 321 DDDCBA 1248.6.3 作 业 车 间 生 产 调 度 举 例o 计 算 能 量 函 数 为 0的 换 位 矩 阵 1258.6.3 作 业 车 间 生 产 调 度 举 例o 成 本 树 返 回 1268.6.3 作 业 车 间 生 产 调 度 举 例o 甘 特 图 返 回 127o 基 本 思 想 ： 在 系 统 寻 优 过 程 中 ， 利 用 神 经 元 状 态 更 新 的 随 机性 ， 允 许 向 较 差 方 向 搜 索 ， 以 跳 出 局 部 极 小 。 经 多 次寻 查 后 ， 最 终 使 系 统 稳 定 于 能 量 最 低 状 态 ， 使 神 经 网络 收 敛 到 计 算 能 量 函 数 的 最 小 值 0， 从 而 使 神 经 网 络输 出 是 一 个 可 行 调 度 解 。8.6.4 基 于 随 机 神 经 网 络 的 生 产 调 度 方 法 128o 根 据 改 进 Metropolis方 法 ， 求 解 JSP的 基 于 模 拟 退 火 的 神 经网 络 算 法 ： （ 1） 初 始 化 ： 设 置 初 始 温 度 ， 合 适 的 输 入 偏 置 电 流 ， 凝 结 温 度 ，温 度 下 降 速 率 ， 在 每 个 温 度 点 的 循 环 处 理 次 数 。8.6.4 基 于 随 机 神 经 网 络 的 生 产 调 度 方 法max0 TT minTrk（ 2） 随 机 爬 山 ： 对 每 个 神 经 元 ， 由 求 解 网 络 方 程 计 算 输 出 电 压 。 由 网络 稳 定 状 态 集 组 成 成 本 树 ； 求 出 最 大 成 本 变 化 量 。 itcosi 1298.6.4 基 于 随 机 神 经 网 络 的 生 产 调 度 方 法 若 ， 则 转 去 （ 3） ； 否 则 计 算 能 量 变 化 量 若 ， 则 令 否 则 ， 令 计 算 概 率 0cos it ij jiji vwE 0 iE iii tEE cos iii tEE cos )exp(1 1 TEp ii 130 选 择 均 匀 分 布 随 机 数 RAND， 若 ， 则 令 神 经 元 的 状 态 为 “ 1” ， 否 则 ， 令 为 “ 0” 。 重 复 该 步 骤 次 。8.6.4 基 于 随 机 神 经 网 络 的 生 产 调 度 方 法RANDPi i（ 3） 退 火 /收 敛 检 验 令 ， 若 ， 则 转 去 （ 2） ； 否 则 停 止 。 max)( TrT nn minTTn k 1318.6.4 基 于 随 机 神 经 网 络 的 生 产 调 度 方 法o 模 拟 退 火 算 法 只 有 在 初 始 温 度 充 分 高 ， 温 度 下 降足 够 慢 ， 在 每 个 温 度 点 下 循 环 处 理 无 限 多 次 ， 并在 时 ， 才 能 收 敛 于 全 局 最 优 解 ， 但 导 致 计算 时 间 大 大 增 加 。0To 改 进 算 法 ： 快 速 模 拟 退 火 、 并 行 模 拟 退 火 等 。 132THE ENDArtificial Intelligence Principles and Applications