智能决策支持系统和智能技术的决策支持

人 工 智 能 的 决 策 支 持 和 智 能 决 策 支 持 系 统 第 4章 目 录n 4.1 人 工 智 能 基 本 原 理 n 4.2 专 家 系 统 与 智 能 决 策 支 持 系 统n 4.3 神 经 网 络 的 决 策 支 持 n 4.4 遗 传 算 法 的 决 策 支 持n 4.5 机 器 学 习 的 决 策 支 持 4.1 人 工 智 能 基 本 原 理n 1、 人 工 智 能 的 决 策 支 持 技 术 4.1 人 工 智 能 基 本 原 理 4.1 人 工 智 能 基 本 原 理 问 题 综 合 与 交 互 系 统 数 据 库管 理 系 统模 型 库管 理 系 统模 型 库 数 据 库人 工 智 能 技 术专 家系 统 神 经网 络 遗 传算 法 机 器学 习 自 然 语言 理 解图 4.1 智 能 决 策 支 持 系 统 的 基 本 结 构 图 4.2 智 能 决 策 支 持 系 统 结 构问 题 综 合 与 交 互 系 统模 型 库 管 理 系 统 数 据 库 管 理 系 统知 识 库管 理 系 统 推 理 机 用 户模 型 库 知 识 库 数 据 库 4.2 人 工 智 能 基 本 原 理n 4.2.1 逻 辑 推 理n 4.2.2 知 识 表 示 与 知 识 推 理n 4.2.3 搜 索 技 术 4.2.1 逻 辑 推 理1.形 式 逻 辑 (人 的 思 维 形 式 、 规 律 )（ 1） 概 念 ： 反 映 事 物 的 特 有 属 性 和 属 性 的 取 值 。（ 2） 判 断 ： 对 概 念 的 肯 定 或 否 定 ； 判 断 本 身 有 对 有 错 ； 判 断 有 全 称 的 肯 定 （ 或 否 定 ） 判 断 和 存 在 的 肯定 （ 或 否 定 ） 判 断 。（ 3） 推 理 ： 从 一 个 或 多 个 判 断 推 出 一 个 新 判 断 的 过 程 。 4.2.1 逻 辑 推 理2.推 理 的 种 类 演 绎 推 理归 纳 推 理类 比 推 理 假 言 推 理三 段 论 推 理数 学 归 纳 法假 言 易 位 推 理枚 举 归 纳 推 理 1） 演 绎 推 理 专 家 系 统 的 研 究 基 本 上 属 于 演 绎 推 理 范 畴 。 演 绎 推 理 的核 心 是 假 言 推 理 。 假 言 推 理 ： 以 假 言 判 断 为 前 提 ， 对 该 假 言 判 断 的 前 件 或后 件 的 推 理 。 1） 假 言 推 理 ： pq， p q 2） 三 段 论 推 理 ： pq， qr pr 3） 假 言 易 位 推 理 （ 拒 取 式 ） ： pq， q p 符 号 “ ” 表 示 推 出4.2.1 逻 辑 推 理 2） 归 纳 推 理 (个 别 一 般 )（ 1） 数 学 归 纳 法 这 种 推 导 是 严 格 的 ， 结 论 是 确 实 可 靠 的 。（ 2） 枚 举 归 纳 推 理 S1是 P ， S2是 P ， Sn是 P S1Sn是 S类 事 物 中 的 部 分 分 子 ， 没 有 相 反 事 例 。 所 以 ， S类 事 物 都 是 P。 枚 举 归 纳 推 理 的 结 论 是 或 然 的 (并 非 必 然 地 )，它 的 可 靠 性 和 事 例 数 量 相 关 。4.2.1 逻 辑 推 理 枚 举 归 纳 推 理 实 例 如 观 察 到 铁 受 热 膨 胀 、 铜 受 热 膨 胀 等 事 实 而不 知 其 所 以 然 ， 由 此 推 出 “ 所 有 金 属 受 热 膨 胀 ”的 结 论 就 是 简 单 枚 举 归 纳 推 理 。 3） 类 比 推 理它 是 由 两 个 （ 或 两 类 ） 事 物 在 某 些 属 性 上 相 同 ，进 而 推 断 它 们 在 另 一 个 属 性 上 也 可 能 相 同 的 推 理 。A事 物 有 abcd属 性 ,B事 物 有 abc属 性 （ 或 a,b,c相 似 属性 ） 所 以 ， B事 物 也 可 能 有 d属 性 （ 或 d相 似 属 性 ） 类 比 推 理 的 结 论 带 有 或 然 性 ， 它 的 可 靠 性 和 相 类比 事 物 属 性 之 间 的 联 系 程 度 有 关 。4.2.1 逻 辑 推 理 类 比 推 理 实 例 一 1816年 的 一 天 ， 法 国 医 生 雷 奈 克 出 诊 为 一 位 年 轻的 女 性 看 病 ， 一 见 病 人 ， 雷 奈 克 犯 起 愁 来 ： 她 身 体非 常 肥 胖 ， 要 诊 断 她 的 心 脏 和 肺 部 是 否 正 常 ， 按 当时 医 生 惯 用 的 方 法 ， 把 耳 朵 贴 近 病 人 的 胸 部 来 听 ，肯 定 听 不 清 楚 ， 更 何 况 她 是 一 位 年 轻 的 女 性 。 雷 奈克 抬 头 看 了 看 院 子 里 正 在 玩 耍 的 小 孩 ， 脑 子 里 突 然浮 现 出 几 年 前 看 到 一 个 孩 子 们 玩 的 游 戏 ： 一 个 孩 子用 钉 子 敲 打 木 板 的 一 头 ， 另 外 的 孩 子 争 先 恐 后 地 抱着 把 耳 朵 贴 近 木 板 的 另 一 头 ， 兴 致 勃 勃 地 倾 听 着 。 为 什 么 木 头 能 够 把 声 音 清 晰 地 传 过 来 呢 ？ 雷 奈克 稍 微 想 了 想 ， 只 见 他 很 很 地 拍 了 一 下 手 说 ： “ 就是 这 样 ！ 就 是 这 样 ！ ” 雷 奈 克 要 来 一 叠 纸 ， 紧 紧 地卷 成 一 个 卷 ， 然 后 把 纸 卷 的 一 端 放 在 姑 娘 的 胸 部 ，另 一 端 放 在 自 己 的 耳 朵 上 ， 侧 着 脸 听 了 起 来 。 “ 真是 一 个 妙 法 ！ ” 雷 奈 克 高 兴 地 喊 了 一 句 。 回 到 家 里 ，雷 奈 克 找 到 一 根 木 棒 ， 造 成 了 历 史 上 第 一 个 “ 听 诊器 ” 。类 比 推 理 实 例 一 类 比 推 理 实 例 二 19世 纪 30年 代 ， 英 国 商 人 威 尔 斯 以 与 冯 灿 的 茂 隆 皮 箱 商 行订 购 的 皮 箱 中 有 不 是 皮 的 木 料 为 由 ， 向 香 港 法 院 起 诉 ， 蓄 意敲 诈 冯 灿 。 针 对 这 种 情 况 ， 冯 灿 的 律 师 罗 文 锦 取 出 口 袋 的 金怀 表 ， 高 声 问 法 官 ： “ 请 问 这 是 什 么 表 ？ ” 法 官 答 道 ： “ 这是 金 表 ， 可 是 这 与 本 案 有 什 么 关 系 ？ ” 罗 文 锦 高 举 金 表 ， 面对 法 庭 上 所 有 的 人 说 ： “ 有 关 系 。 这 是 金 表 ， 没 有 人 怀 疑 是吧 ？ 但 是 ， 请 问 ， 这 块 金 表 除 表 面 镀 金 之 外 ， 内 部 的 机 制 都是 金 制 吗 ？ ” 旁 听 者 同 声 议 论 ： “ 当 然 不 是 。 ” 罗 文 锦 继 续说 ： “ 那 么 人 们 为 什 么 又 叫 它 金 表 呢 ？ ” 稍 作 停 顿 又 高 声 说 ：“ 由 此 可 见 ， 茂 隆 行 的 皮 箱 案 不 过 是 原 告 无 理 取 闹 、 存 心 敲诈 而 已 ” 原 告 理 屈 词 穷 ， 法 庭 最 后 以 威 尔 斯 诬 告 ， 罚 款 5000元 结 案 皮 箱 诉 讼 案 的 法 庭 辩 论 中 ， 卖 方 律 师 在 反 驳中 所 使 用 的 就 是 类 比 推 理 ： 表 的 外 表 有 金 ， 内 部 含 有 不 是 金 的 材 料 ， 但却 是 金 表 ； 箱 的 外 表 有 皮 ， 但 也 含 有 不 是 皮 的 材 料 ；所 以 ， 箱 仍 是 皮 箱 。类 比 推 理 实 例 二 3. 总 结 1） 演 绎 推 理 的 结 论 没 有 超 出 已 知 的 知 识 范 围 。而 归 纳 推 理 和 类 比 推 理 的 结 论 超 出 已 知 的 知 识 范 围 。 演绎推理只能解释一般规律中的个别现象 而归纳推理和类比推理创造了新的知识，使科学得到新发展，是一种创造思维方式 2） 演 绎 推 理 中 由 于 前 提 和 结 论 有 必 然 联 系 ， 只要 前 提 为 真 ， 结 论 一 定 为 真 。 归纳推理和类比推理中前提和结论，不能保证有必然联系，具有或然性。这样推理的结论未必是可靠的。需要经过严格的验证和证明，使之形成新的理论。4.2.1 逻 辑 推 理 4.2.2 知 识 表 示 与 知 识 推 理n 4.2.2.1 数 理 逻 辑 表 示 法 (自 学 )n 4.2.2.1 产 生 式 规 则n 4.2.2.3 语 义 网 络n 4.2.2.4 框 架n 4.2.2.5 剧 本 (自 学 ) 4.2.2.2 产 生 式 规 则 （ if A then B）n 1. 正 向 推 理 1.A BG2.C DA3.ED B,C,E4.2.2.2 产 生 式 规 则事 实 库 的 最 后 状 态 为 ：B， C， E， D， A， G产 生 式 规 则 库 事 实 库产 生 式 规 则 库 和 事 实 库 的 初 始 状 态 为 ： 4.2.2.2 产 生 式 规 则n 逆 (反 )向 推 理 G A D EB C4.2.2.2 产 生 式 规 则逆 向 推 理 中 ， 目 标 改 变 过 程 ：1.A BG2.C DA3.ED B,C,E产 生 式 规 则 库 事 实 库 4.2.3 搜 索 技 术n 搜 索 技 术 是 人 工 智 能 的 一 个 重 要 研 究 内 容 。 智 能 技术 体 现 在 减 少 搜 索 树 中 的 盲 目 搜 索 。按 多 项 式 时 间 执 行 的 算 法 ， 计 算 机 是 可 以 实 现 的 。按 指 数 时 间 执 行 的 算 法 ， 计 算 机 是 不 可 能 实 现 的 。 4.2.3 搜 索 技 术n 人 工 智 能 中 发 展 了 一 种 称 为 启 发 式 搜 索 方 法 ， 基 本 思 想 可 用一 个 实 例 来 说 明 ：n 一 个 外 地 人 到 某 城 市 出 差 ， 他 想 到 书 店 看 看 ， 又 不 知 书 店在 何 处 ， 如 果 采 取 盲 目 搜 索 ， 从 住 地 出 发 沿 任 一 方 向 走 ，在 分 叉 路 口 又 任 选 一 分 支 走 ， 他 可 能 走 几 天 几 夜 也 找 不 到 n 如 果 采 用 启 发 式 方 法 ， 他 会 问 路 上 的 人 ， 到 书 店 怎 样 走 。城 市 中 的 大 部 分 人 对 书 店 不 知 道 ， 问 不 出 来 。 4.2.3 搜 索 技 术问 该 城 市 最 热 闹 的 地 方 在 哪 儿 ？n 但 书 店 在 哪 儿 ， 仍 然 不 知 道 。 如 果 盲 目 搜 索 ， 可 能 仍 然找 不 到 。 如 果 采 用 启 发 式 方 法 ， 他 会 问 路 上 的 人 ， 卖 画的 地 方 在 哪 儿 ， 他 可 以 通 过 画 店 再 问 书 店 在 哪 儿 ？ n 启 发 式 方 法 能 减 少 大 量 盲 目 无 效 的 搜 索 ， 能 有 效 克 服 按指 数 时 间 执 行 的 组 合 爆 炸 现 象 4.2.3 搜 索 技 术n 搜 索 方 法 分 类 ： （ 1） 极 小 极 大 搜 索 法 。 （ 2） 剪 枝 算 法 。 4.2.3.1 广 度 优 先 搜 索 （ 宽 度 优 先 搜 索 ）1、 广 度 优 先 搜 索 思 想 图 4.7 广 度 优 先 搜 索 示 意 图 （ 2） 算 法1) 把 初 始 节 点 S0故 入 OPEN表 。2) 如 果 OPEN表 为 空 ， 则 问 题 无 解 ， 退 出 。 3) 把 OPEN表 的 第 一 个 节 点 (记 为 节 点 n)取 出 放 入CLOSED表 。4)考 察 节 点 n是 否 为 目 标 节 点 。 若 是 ， 则 求 得 了问 题 的 解 ， 退 出 。 5)若 节 点 n不 可 扩 展 ， 则 转 第 2)步 。 6) 扩 展 节 点 n， 将 其 子 节 点 放 入 OPEN表 的 尾 部 ， 并为 每 一 个 子 节 点 都 配 置 指 向 父 节 点 的 指 针 ， 然 后转 第 2)步 。 广度优先搜索过程 开 始 把 n的 后 继 节 点 放 入 OPEN表 的 末端 ， 提 供 返 回 节 点 n的 指 针把 S放 入 OPEN表OPEN表 为 空 表 ？ 是 失 败否把 第 一 个 节 点 （ n） 从 OPEN移 至 CLOSED表n为 目 标 节 点 ？ 是 成 功否n能 否 扩 展 是 否 有 任 何 后 继节 点 为 目 标 节 点否 是是否 例 子 1(八 数 码 难 题 )重 排 九 宫 问 题 ， 在 3x3的 方 格 棋 盘 上 放 置 分 别 标 有 数字 1、 2、 3、 4、 5、 6、 7、 8共 8个 棋 子 ， 初 始 状 态为 S0， 目 标 状 态 为 Sg， 如 图 1所 示 。可 使 用 的 算 符 有 ： 空 格 左 移 ， 空 格 上 移 ， 空 格 右 移 ， 空 格 下 移 。 即只 允 许 把 位 于 空 格 左 、 上 、 右 、 下 的 邻 近 棋 子 移 入空 格 。 要 求 寻 找 从 初 始 状 态 到 目 标 状 态 的 路 径 。 该 路 径 使 用 的 算 符 序 列 ： 空 格 上 移 ， 空 格 左 移 ， 空 格 下 移 ，空 格 右 移 。 广 度 优 先 搜 索 的 盲 目 性 较 大 ， 当 目 标 节 点 距 离初 始 节 点 较 远 时 将 会 产 生 许 多 无 用 节 点 ， 因 此 搜 索效 率 低 ， 但 是 ， 只 要 问 题 有 解 ， 用 广 度 优 先 搜 索 总可 以 得 到 解 ， 而 且 得 到 的 是 路 径 最 短 的 路 径 。 由 图 2可 以 看 出 ， 解 的 路 径 是 ： S0381626广 度 优 先 法 适 合 于 搜 索 树 的 宽 度 较 小 的 问 题 。 1、 深 度 优 先 搜 索 法 思 想 4.2.3.2 深 度 优 先 搜 索 法 图 4.8 深 度 优 先 搜 索 示 意 图 （ 2） 算 法1) 把 初 始 节 点 S0故 入 OPEN表 。2)如 果 OPEN表 为 空 ， 则 问 题 无 解 ， 退 出 。 3)把 OPEN表 的 第 一 个 节 点 (记 为 节 点 n)取 出 放 入 CLOSED表 。 4)考 察 节 点 n是 否 为 目 标 节 点 。 若 是 ， 则 求 得 了 问题 的 解 ， 退 出 。 5)若 节 点 n不 可 扩 展 ， 则 转 第 2)步 。 6)扩 展 节 点 n， 将 其 全 部 子 节 点 放 入 到 OPEN表 的 首 部 ，并 为 其 配 置 指 向 父 节 点 的 指 针 ， 然 后 转 第 2)步 。 开 始把 S放 入 OPEN表OPEN表 为 空 表 ？ 是 失 败否把 第 一 个 节 点 （ n） 从 OPEN移 至 CLOSED表 是 否 有 任 何 后 继节 点 为 目 标 节 点 是 成 功否扩 展 n,把 n的 后 继 节 点 放 入 OPEN表 的前 头 ， 提 供 返 回 节 点 n的 指 针s为 目 标 节 点 ？否 是深度优先搜索 例 子 2： 对 图 1所 示 的 重 排 九 宫 问 题 进 行 深 度 优 先 搜 索 ， 可 得 到 图 3所 示 的 搜 索 树 这 只 是 搜 索 树 的 一 部 分 ， 尚 未 到 达 目 标 节 点 ， 仍需 继 续 往 下 搜 索 。 在 深 度 优 先 搜 索 中 ， 搜 索 一 旦 进 入 某 个 分 支 ， 就将 沿 着 该 分 支 一 直 向 下 搜 索 。 如 果 目 标 节 点 恰 好 在 此分 支 上 ， 则 可 较 快 地 得 到 解 。 但 是 ， 如 果 目 标 节 点 不在 此 分 支 上 ， 而 该 分 支 又 是 一 个 无 穷 分 支 ， 则 就 不 能得 到 解 。 所 以 深 度 优 先 搜 索 是 不 完 备 的 ， 即 使 问 题 有解 ， 它 也 不 一 定 能 求 得 解 。 显 然 ， 用 深 度 优 先 求 得 的解 ， 也 不 一 定 是 路 径 最 短 的 解 。 深 度 优 先 法 适 合 于 搜 索 树 的 深 度 较 小 的 问 题 4.2.3.3 生 成 测 试 法n 生 成 测 试 法 算 法 是 ： 4.2.3.3 生 成 测 试 法 4.2.3.4 爬 山 法 (生 成 测 试 法 的 变 种 ) n 爬 山 算 法 ： (测 试 函 数 )n 对该状态测试，检查是否为目标，是则停止。 n 计算该状态的好坏，或者比较各状态的好坏。 在 爬 山 法 中 可 能 出 现 以 下 几 种 情 况 ： 局 部 极 大 点 ： 它 比 周 围 邻 居 状 态 都 好 ， 但 不 是 目 标 。 图 4.9局 部 极 大 点 示 意 图 在 爬 山 法 中 可 能 出 现 以 下 几 种 情 况 ： 平 顶 ： 它 与 全 部 邻 居 状 态 都 有 同 一 个 值 ， 构 成 一 个 平 面 。 图 4.10 平 顶 示 意 图 在 爬 山 法 中 可 能 出 现 以 下 几 种 情 况 ： 山 脊 ： 它 与 线 状 邻 居 状 态 有 相 同 值 ， 比 其 它 邻 居 状态 要 好 。 图 4.11山 脊 示 意 图 4.2.3.4 爬 山 法n 为 了 解 决 以 上 问 题 ， 需 要 采 用 如 下 策 略 ： 4.2.3.5 启 发 式 搜 索 n 启 发 式 搜 索 是 对 每 个 在 搜 索 过 程 中 遇 到 的 新 状 态 ，用 一 个 估 计 函 数 （ 启 发 式 函 数 ） 并 计 算 其 值 的 大小 ， 确 定 下 一 步 将 从 哪 一 个 状 态 开 始 继 续 前 进 。 4.2.3.5 启 发 式 搜 索n 具 体 需 要 考 虑 以 下 问 题 ： 一 般 启 发 式 函 数 法 用 如 下 公 式 表 示 ： f（ x） =g（ x） +h（ x） 4.2.3.5 启 发 式 搜 索 启 发 式 函 数 分 析 ：n 1. 当 h（ x） =0， 即 f（ x） =g（ x） 取 f（ x） 为 最 小 ， 即 取 g（ x） 为 最 小 。 这 要 求 在 已扩 展 的 结 点 中 取 最 佳 路 径 。 g（ x） 能 保 证 找 到 最 好解 。 但 对 搜 索 速 度 没 有 太 多 的 帮 助 。n 2. 当 g（ x） =0， 即 f（ x） =h（ x） h（ x） 是 从 当 前 状 态 到 目 标 状 态 的 耗 费 。 取 它 最 小 ，将 会 加 快 搜 索 速 度 ， 但 它 并 不 保 证 得 到 最 优 解 。4.2.3.5 启 发 式 搜 索 g（ x） 选 取 的 几 种 特 例 ： f(x)一 般 表 示 估 计 值 ， 愈 接 近 精 确 值 ， 启 发 式 效 果愈 好 。 如 果 是 精 确 值 ,就 不 是 启 发 式 函 数 。4.2.3.5 启 发 式 搜 索 图 -4启 发 式 搜 索 2 8 31 6 47 52 8 31 47 6 5 1 38 2 47 6 5 2 8 31 47 6 5 2 31 8 47 6 5 2 8 31 47 6 58 32 1 47 6 5 2 8 37 1 46 5 2 31 8 47 6 5 2 31 8 47 6 58 3 2 1 47 6 5 1 38 2 4 7 6 5 1 2 38 47 6 58 1 3 2 6 47 5 8 1 32 47 6 5 1 2 37 8 46 58 32 1 47 6 5 8 1 32 47 6 58 1 32 47 6 5 1 2 38 47 6 5 1 38 2 47 6 51 2 38 47 6 5*8 1 37 2 46 5 * 4 4 5 54 5 3 54 2 305 45 5 45 3 20 4h（ x） 可 以定 义 为 节 点x中 数 码 位 置与 目 标 节 点相 比 不 同 的个 数 n 4.3 专 家 系 统 与 智 能 决 策 支 持 系 统 4.3.1专 家 系 统 原 理n 1. 专 家 系 统 概 念n 专 家 系 统 是 具 有 大 量 专 门 知 识 ， 并 能 运 用 这 些 知 识 解 决特 定 领 域 中 实 际 问 题 的 计 算 机 程 序 系 统 。 n 专 家 系 统 是 利 用 大 量 的 专 家 知 识 ， 运 用 知 识 推 理 的 方 法来 解 决 各 特 定 领 域 中 的 实 际 问 题 。 计 算 机 专 家 系 统 这 样的 软 件 能 够 达 到 人 类 专 家 解 决 问 题 的 水 平 。 4.3.1专 家 系 统 原 理n 2） 专 家 系 统 的 特 点 4.3.1专 家 系 统 原 理 例 如 ： 求 解 微 积 分 问 题 ， 是 利 用 30 40条 微 分 、 积 分 公式 来 求 解 千 变 万 化 的 微 分 、 积 分 问 题 ， 得 出 各 自 的结 果 。其 中 微 积 分 公 式 就 是 规 律 性 知 识 ， 求 解 微 积 分 问 题 就 是对 某 函 数 反 复 利 用 微 积 分 公 式 进 行 推 导 ， 最 后 得 出 该 问题 的 结 果 。这 个 推 理 过 程 是 一 个 不 固 定 形 式 的 推 理 ， 即 前 后 用 哪 个公 式 ， 调 用 多 少 次 这 些 公 式 都 随 问 题 变 化 而 变 化 。 n 1） 专 家 系 统 对 比 数 据 库 检 索n （ A） 知 识 只 含 事 实 性 知 识 ， 不 包 含 规 律 性 知 识 。 n （ B） 推 理 是 对 已 有 记 录 的 检 索 ， 记 录 不 存 在 ， 则 检 索不 到 。 不 能 适 应 变 化 的 事 实 ， 推 理 不 出 新 事 实 。4.3.1专 家 系 统 原 理 4.3.1专 家 系 统 原 理n 2） 专 家 系 统 对 比 数 值 计 算 知 识 处 理 的 特 点从 上 面 分 析 可 见 ， 数 值 计 算 、 数 据 处 理 是 知 识 处 理的 特 定 情 况 ， 知 识 处 理 则 是 它 们 的 发 展 ! （ A） 知 识 包 括 事 实 和 规 则 （ 状 态 转 变 过 程 ） 。（ B） 适 合 于 符 号 处 理 （ 如 微 积 分 求 解 ） 。（ C） 推 理 过 程 是 不 固 定 形 式 的 （ 推 导 过 程 中 每次 选 用 的 规 则 知 识 是 变 化 的 ） 。（ D） 能 得 出 未 知 的 事 实 （ 如 推 导 出 新 的 微 分 公式 ） 。 2.专 家 系 统 结 构 专 家 系 统 的 核 心 是 知 识 库 和 推 理 机 。 专 家 系 统 可 以 概 括 为 ： 专 家 系 统 知 识 库 +推 理 机4.3.1专 家 系 统 原 理 知 识 获 取 人 机 接 口知 识 库 推 理 机专 家 用 户咨 询 建 议 专 家 系 统 核 心 专 家 系 统 结 构 3.产 生 式 规 则 知 识 的 推 理 机产 生 式 规 则 的 推 理 机 搜 索 +匹 配 （ 假 言 推 理 ）n 在 推 理 过 程 中 ， 是 一 边 搜 索 一 边 匹 配 。 匹 配 需 要 找 事实 ,这 个 事 实 一 是 来 自 于 规 则 库 中 别 的 规 则 ， 一 是 来 自向 用 户 提 问 。n 在 匹 配 时 会 出 现 成 功 或 不 成 功 ， 对 于 不 成 功 的 将 引 起搜 索 中 的 回 溯 和 由 一 个 分 枝 向 另 一 个 分 枝 的 转 移 ， 可见 在 搜 索 过 程 中 包 含 了 回 溯 。4.3.1 专 家 系 统 原 理 4.3.1 专 家 系 统 原 理4. 产 生 式 规 则 推 理 的 解 释 4.3.2 产 生 式 规 则 专 家 系 统n 4.3.2.1 产 生 式 规 则n 4.3.2.2 推 理 树 (知 识 树 )n 4.3.2.3 逆 向 推 理 过 程n 4.3.2.4 事 实 数 据 和 解 释 机 制 4.3.2 产 生 式 规 则 专 家 系 统n 产 生 式 规 则 的 优 点 4.3.2.1 产 生 式 规 则 ESn 产 生 式 规 则 知 识 一 般 表 示 为 :if A then B，或 ：如 果 A成 立 则 B成 立 ，或 ： AB 4.3.2.1 产 生 式 规 则n 产 生 式 规 则 知 识 表 示 允 许 有 如 下 的 特 点 ： 4.3.2.1 产 生 式 规 则 ESn 由 于 以 上 特 点 ， 规 则 知 识 集 能 做 到 ： 4.3.2.2推 理 树 （ 知 识 树 ）n 规 则 库 中 的 各 条 规 则 之 间 一 般 来 说 都 是 有 联 系 的n 按 逆 向 推 理 思 想 把 知 识 库 所 含 的 总 目 标 （ 它 是 某些 规 则 的 结 论 ） 作 为 根 结 点 ， 按 规 则 的 前 提 和 结论 展 开 成 一 棵 树 的 形 式 。 这 棵 树 一 般 称 为 推 理 树或 知 识 树 ， 它 把 知 识 库 中 的 所 有 规 则 都 连 结 起 来 XF GLMEC4.3.2.2推 理 树 （ 知 识 树 ）A BI J KW Z P Q 用 规 则 的 前 提 和 结 论 形 式 画 出 逆 向 推 理 树 形 式 为 ： 4.3.2.2推 理 树 （ 知 识 树 ）前 提 I前 提 J前 提 L前 提 M前 提 E(结 论 )(结 论 )(结 论 )前 提 A前 提 B前 提 C（ 结 论 )（ 结 论 ） (结 论 )总 目 标 G（ 结 论 ) 前 提 X前 提 F前 提 W前 提 Z前 提 P前 提 Q? ? ? ? ? ? ? n 该 “ 与 或 ” 推 理 树 的 特 点 是 ：4.3.2.2推 理 树 （ 知 识 树 ） 4.3.2.3 逆 向 推 理 过 程 推 理 树 的 深 度优 先 搜 索 N1 7 982 GA B CJI K L M E4 5Y X F Z P Q1011 123 Y W Y Y YN6 4.3.2.3 逆 向 推 理 过 程在 计 算 机 中 实 现 时 ， 并 不 把 规 则 连 成 推 理 树 ， 而 是 利 用规 则 栈 来 完 成 。 当 调 用 此 规 则 时 ， 把 它 压 入 栈 内 （ 相 当 于对 树 的 搜 索 ） ， 当 此 规 则 的 结 论 已 求 出 （ yes或 no） 时 ， 需要 将 此 规 则 退 栈 （ 相 当 于 对 树 的 回 溯 ） 。 利 用 规 则 栈 的 压 入 和 退 出 的 过 程 ， 相 当 于 完 成 了 推 理树 的 深 度 优 先 搜 索 和 回 溯 过 程 。 4.3.2.3 逆 向 推 理 过 程 结 点 的 否 定 4.3.2.4 事 实 数 据 库 和 解 释 机 制 1. 事 实 数 据 库 (动 态 数 据 库 ) 事 实 Y,N值 规 则 号 可 信 度A11 N 0(提 问 ) 0A12 Y 0 0.9A 1 Y 4 0.8事 实 栏 放 入 命 题规 则 号 ： 事 实 取 Y或N的 理 由可 信 度 ： 事 实 的 可信 度 2. 解 释 机 制4.3.2.4 事 实 数 据 库 和 解 释 机 制 4.3.3 专 家 系 统 与 决 策 支 持 系 统 集 成 数 据 库DBDSS控 制系 统模 型 库MB 问 题 综 合与交 互 系 统 动 态DB推 理 机和解 释 器知 识 库KB 集 成 系 统DSS ES 图 4.16智 能 决 策 支 持 系 统 集 成 结 构 图综 合 系 统 DSS与 ES集 成 形 式 一 ： DSS和 ES并 重 的 IDSS结 构 集 成系 统DSS ES4.3.3 专 家 系 统 与 决 策 支 持 系 统 集 成 集 成 特 点1.具 有 综 合 系 统 ， 具 有 调 用 和 集 成 DSS和 ES的能 力 。2.扩 充 DSS的 问 题 与 人 机 交 互 系 统 功 能 ， 增 加对 ES的 调 用 组 合 能 力DSS与 ES的 关 系 ：DSS中 DB与 ES中 的 动 态 DB进 行 数 据 交 换解 决 问 题 的 特 点体 现 定 性 分 析 和 定 量 分 析 并 重 解 决 问 题 的 特 点 。 DSS控 制 系统MB DB ESDSS与 ES集 成 形 式 二 ： DSS为 主 体 的 IDSS结 构 4.3.3 专 家 系 统 与 决 策 支 持 系 统 集 成 集 成 特 点集 成 系 统 和 DSS控 制 系 统 合 为 一 体DSS与 ES的 关 系 ：ES被 DSS控 制 系 统 调 用解 决 问 题 的 特 点体 现 以 定 量 分 析 为 主 ， 结 果 定 性 分 析 解 决 问题 的 特 点 。 推 理 机（ 广 义 ） DSS 动 态DB KB 推 理 机 MB动 态DB KB图 4.19 DSS作 为 推 理 形 式 的 IDSS 图 4.20模 型 作 为 知 识 的 IDSSDSS与 ES集 成 形 式 三 ： ES为 主 体 的 IDSS结 构4.3.3 专 家 系 统 与 决 策 支 持 系 统 集 成 集 成 特 点人 机 交 互 系 统 和 ES合 为 一 体 DSS与 ES的 关 系 ：图 4.19 DSS作 为 推 理 机 ， 受 ES的 推 理 机 控 制 ；图 4.20数 据 模 型 作 为 知 识 出 现解 决 问 题 的 特 点 体 现 以 定 量 分 析 为 主 ， 结 果 定 性 分 析 解 决 问 题 的 特 点 。 4.3.4 建 模 专 家 系 统 专 家 系 统 实 现 模 型 选 择 的 实 例 进 行 说 明 。 R1： A B C M1R2： A1AR3： A11A1R4： A12A1R5： A B E F M2R6： C1CR7： E1ER8： A B E F GM3R9： A B C GM4R10： B1B R11： H1HR12： A2AR13： H B C M5R14： H B C GM6R15： H B E F M7R16： H B E F GM8R17： A B E I M9R18： A B I GM10R19： H B E I M11R20： H B E I GM124.3.4 建 模 专 家 系 统 A： 弹 簧 满 足 胡 克 定 律B： 弹 簧 质 量 可 以 忽 略C： 可 以 忽 略 摩 擦 力D： 没 有 冲 力A1： 弹 簧 有 线 性 恢 复 力A11： 弹 力 与 位 移 成 正 比A12： 位 移 量 很 小E： 要 考 虑 摩 擦 力F： 摩 擦 力 与 速 度 之 间 为 线性 关 系C1： 若 振 动 为 自 发 时 振 幅为 常 数 E1： 若 振 动 为 自 发 时 振 幅 是 递减 的G： 有 冲 力 F（ T）B1： 弹 簧 具 有 质 量 N并 且 N/M远远 小 于 1H1： 弹 簧 势 能 不 是 关 于 平 衡 位置 对 称H： 弹 簧 不 潢 足 胡 克 定 律A2： 弹 簧 势 能 与 函 数 X（ T） 成正 比I： 摩 擦 力 与 速 度 之 间 为 非 线 性关 系各 项 英 文 字 母 含 义 为 ： M1： X+（ C2/M） X 0M2： X+（ C1/M） X+（ C2/M） X 0M3： X+（ C1/M） X+（ C2/M） X F（ T） /MM4： X+（ C2/M） X F（ T） /MM5： X+F（ X） /M 0M6： X+F（ X） /M F（ T） /MM7： X+（ C1/M） X+F（ X） /M 0 M8： X+（ C1/M） X+F（ X）/M F（ T） /MM9： X+（ G/M） X+（ C2/M）X 0M10： X+（ G/M） X+（ C2/M）X F（ T） /MM11： X+（ G/M） X+F（ X）/M 0M12： X+（ G/M） X+F（ X）/M F（ T） /M其 中 X表 示 X对 的 二 阶 导 数 ，X表 示 一 阶 导 数 。 3. 规 则 库 的 推 理 树 4.3.4 建 模 专 家 系 统 A2A1B1C1？ E1？ ？ B1？A11A12？ ？ ？ ？DEFGHIA B C？ ？ M（ M1， M2， ， M12）图 4.21弹 簧 振 动 推 理 树 的 标 准 形 式 专 家 系 统 应 用现 有 一 个 弹 簧 ， 满 足 如 下 特 性 ： H1（ 弹 簧 势 能 不 是 关 于 平 衡 位 置 对 称 ） B1（ 弹 簧 具 有 质 量 N并 且 N/M远 远 小 于 1） C1（ 若 振 动 为 自 发 时 振 幅 为 常 数 ） G（ 有 冲 力 F（ T） ）通 过 专 家 系 统 推 理 将 得 出 ： 该 弹 簧 满 足 模 型 6（ M 6） 的 微 分 方 程 。 4.5 遗 传 算 法 的 决 策 支 持 4.5.1 遗 传 算 法 原 理n 遗 传 算 法 (Genetic Algorithm， GA) n 遗 传 算 法 的 发 展 过 程 大 体 上 可 分 为 以 下 三 个 阶 段 ： n 1975年 美 国 Michigan 大 学 J.Holland首 次 系 统 地 阐 述 了 遗 传 算法 的 基 本 理 论 和 方 法 。 n 在 这 一 时 期 的 大 部 分 研 究 都 处 于 理 论 研 究 和 建 立 实 验 模 型 阶 段n 1980年 Smith教 授 将 遗 传 算 法 应 用 于 机 器 学 习 领 域 ， 研 制 出 了 一个 著 名 的 分 类 器 (Classifier)系 统 。 n 这 期 间 许 多 学 者 对 遗 传 算 法 进 行 了 大 量 的 改 进 和 发 展 ， 提 出 了许 多 成 功 的 遗 传 算 法 模 型 ， 使 遗 传 算 法 应 用 于 更 广 泛 的 领 域 。n 进 入 90年 代 后 ， 遗 传 算 法 作 为 一 种 实 用 、 高 效 的 优 化 技 术 ， 得到 了 极 为 迅 速 的 发 展 。4.5.1 遗 传 算 法 原 理 4.5.1 遗 传 算 法 原 理4.5.1.1 遗 传 算 法 工 作 过 程4.5.1.2 遗 传 算 法 的 理 论 基 础4.5.1.3 遗 传 算 法 的 基 本 特 征 4.5.1.1 遗 传 算 法 的 工 作 过 程n 遗 传 算 法 是 一 种 群 体 型 操 作 ， 该 操 作 以 群 体 中 的 所 有 个 体为 对 象 。n 个 体 就 是 模 拟 生 物 个 体 而 对 问 题 中 的 对 象 （ 一 般 就 是 问 题 的 解 ） 的一 种 称 呼 ， 一 个 个 体 也 就 是 搜 索 空 间 中 的 一 个 点 。n 种 群 (population)就 是 模 拟 生 物 种 群 而 由 若 干 个 体 组 成 的 群 体 , 它 一般 是 整 个 搜 索 空 间 的 一 个 很 小 的 子 集 。 n 遗 传 算 法 的 三 个 主 要 操 作 算 子 ： 选 择 （ selecation） 、交 叉 （ crossover） 和 变 异 （ mutation） 构 成 了 遗 传操 作 （ G enetic operation） ， 使 遗 传 算 法 具 有 了 其 他 传统 方 法 所 没 有 的 特 性 。 产 生 新 一 代 群 体 编 码 和 初 始 群 体 形 成 输 出 种 群个 体 适 应 值 满 意 否 ？4.5.1.1 遗 传 算 法 的 工 作 过 程n 首 先 将 问 题 的 每 个 可 能 的 解 按 某种 形 式 编 码 ， 编 码 后 的 解 称 作 染 色体 （ 个 体 ） 。n 随 机 选 取 N个 染 色 体 构 成 初 始 种 群 ，再 根 据 预 定 的 评 价 函 数 对 每 个 染 色体 计 算 适 应 值 ， 使 得 性 能 较 好 的 染色 体 具 有 较 高 的 适 应 值 。n 选 择 适 应 值 高 的 染 色 体 进 行 复 制 ，通 过 遗 传 算 子 来 产 生 一 群 新 的 更 适应 环 境 的 染 色 体 ， 形 成 新 的 种 群 。n 这 样 一 代 一 代 不 断 繁 殖 ， 最 后 收敛 到 一 个 最 适 应 环 境 的 个 体 上 ， 求 得 问 题 的 最 优 解 。遗传算子选 择交 叉变 异 1. 群 体 中 个 体 的 编 码4.5.1.1 遗 传 算 法 的 工 作 过 程 2. 适 应 值 函 数 的 确 定 n 适 应 值 函 数 (即 评 价 函 数 )是 根 据 目 标 函 数 确 定 的 。 适 应 值 总 是 非 负 的 ，任 何 情 况 下 总 是 希 望 越 大 越 好 。 如 果 目 标 函 数 不 是 取 最 大 值 时 ， 需 要将 它 映 射 成 适 应 值 函 数 。n 一 般 是 一 个 实 值 函 数 。 该 函 数 就 是 遗 传 算 法 中 指 导 搜 索 的 评 价 函 数 。4.5.1.1 遗 传 算 法 的 工 作 过 程 3.遗 传 算 法 的 三 个 算 子4.5.1.1 遗 传 算 法 的 工 作 过 程 n 它 又 称 复 制 (reproduction) 、 繁 殖 算 子 。n 选 择 是 从 种 群 中 选 择 生 命 力 强 的 染 色 体 产 生 新 种 群 的过 程 。 依 据 每 个 染 色 体 的 适 应 值 大 小 ， 适 应 值 越 大 ，被 选 中 的 概 率 就 越 大 ， 其 子 孙 在 下 一 代 产 生 的 个 数 就越 多 。n 选 择 操 作 是 建 立 在 群 体 中 个 体 的 适 应 值 估 评 基 础 上 的 。4.5.1.1 遗 传 算 法 的 工 作 过 程 通 常 做 法 是 ： 对 于 一 个 规 模 为 N的 种 群 S,按 每 个 染 色 体 xi S的 选择 概 率 P(xi)所 决 定 的 选 中 机 会 , 分 N次 从 S中 随 机 选 定 N个 染 色 体 , 并 进 行 复 制 。4.5.1.1 遗 传 算 法 的 工 作 过 程 Nj jii xfxfxP 1 )( )()( 这 里 的 选 择 概 率 P(xi)的 计 算 公 式 为 n 它 又 称 重 组 (recombination) 、 配 对 (breeding)算 子 ， 在 遗 传算 法 中 起 着 核 心 作 用 。n 染 色 体 重 组 是 分 两 步 骤 进 行 的 :n首先在新复制的群体中随机选取两个个体n然后，沿着这两个个体(字符串)随机地取一个位置，二者互换从该位置起的末尾部分。 n 交 叉 率 (crossover rate)就 是 参 加 交 叉 运 算 的 染 色 体 个 数 占 全 体 染色 体 总 数 的 比 例 ， 记 为 Pc,取 值 范 围 一 般 为 0.4 0.99。4.5.1.1 遗 传 算 法 的 工 作 过 程 4.5.1.1 遗 传 算 法 的 工 作 过 程例 1:有 两 个 用 二 进 制 编 码 的 个 体 A和 B。 长 度 L=5， A=a1a2a3a4a5 ，B=b1b2b3b4b5随 机 选 择 一 整 数 k 1， L-1 ， 设 k=4， 经 交 叉 后 变为 ：A = a1a2a3|a4a5 B = b1b2b3|b4b5 A= a1a2a3 b4b5 B = b1b2b3 a4a5s 1=01000101, s2=10011011可 以 看 做 是 原 染 色 体 s1和 s2的 子 代 染 色 体 。 例 2,设 染 色 体 s1=01001011, s2=10010101,交 换 其 后 4位 基 因 ,即 n 变 异 就 是 以 很 小 的 概 率 ， 随 机 地 改 变 字 符 串 某 个 位 置 上 的 值 。变 异 操 作 是 按 位 （ bit） 进 行 的 ， 即 把 某 一 位 的 内 容 进 行 变 异 。在 二 进 制 编 码 中 ， 就 是 将 某 位 0变 成 1， 1变 成 0。n 选 择 和 交 叉 算 子 基 本 上 完 成 了 遗 传 算 法 的 大 部 分 搜 索 功 能 ， 而变 异 则 增 加 了 遗 传 算 法 找 到 接 近 最 优 解 的 能 力 。n 变 异 率 (mutation rate)是 指 发 生 变 异 的 基 因 位 数 所 占 全 体 染色 体 的 基 因 总 位 数 的 比 例 ， 记 为 Pm， 取 值 范 围 一 般 为0.0001 0.02。 它 保 证 了 遗 传 算 法 的 有 效 性 。4.5.1.1 遗 传 算 法 的 工 作 过 程 4.5.1.1 遗 传 算 法 的 工 作 过 程 4.控 制 参 数 设 定4.5.1.1 遗 传 算 法 的 工 作 过 程 n 1.模 式 定 理4.5.1.2 遗 传 算 法 的 理 论 基 础 n 1.模 式 定 理4.5.1.2 遗 传 算 法 的 理 论 基 础 n 2 基 因 块 假 设4.5.1.2 遗 传 算 法 的 理 论 基 础 n 1. 遗 传 算 法 的 处 理 对 象 是 问 题 参 数 的 编码 个 体 （ 位 串 ）4.5.1.3 遗 传 算 法 的 基 本 特 征 n 2. 遗 传 算 法 的 搜 索 是 从 问 题 解 位 串 集 开 始 搜索 ， 而 不 是 从 单 个 解 开 始4.5.1.3 遗 传 算 法 的 基 本 特 征 n 3. 遗 传 算 法 只 使 用 目 标 函 数 (即 适 应 值 )来 搜 索 ， 而 不 需 要 导数 等 其 他 辅 助 信 息n 4. 遗 传 算 法 使 用 的 三 种 遗 传 算 子 是 一 种 随 机 操 作 ， 而 不 是 确定 性 规 则 n 5.隐 含 的 并 行 性n 6.易 介 入 到 已 有 的 模 型 中 ， 并 具 有 扩 展 性 ； 易 于 同 别 的 技 术 结合 使 用4.5.1.3 遗 传 算 法 的 基 本 特 征 4.5.2 优 化 模 型 的 遗 传 算 法 求 解 优 化 模 型 的 计 算 是 遗 传 算 法 最 基 本 的 也 是 最重 要 的 研 究 和 应 用 领 域 之 一 。 一 般 说 来 ， 优 化 计 算 问 题 通 常 带 有 大 量 的 局部 极 值 点 ， 往 往 是 不 可 微 的 、 不 连 续 的 、 多 维的 、 有 约 束 条 件 的 、 高 度 非 线 性 的 NP完 全 问题 。 精 确 地 求 解 优 化 问 题 的 全 局 最 优 解 一 般 是 不可 能 的 。 4.5.2 优 化 模 型 的 遗 传 算 法 求 解4.5.2.1 优 化 模 型 的 遗 传 算 法 处 理4.5.2.2 实 例 1、 适 应 值 函 数 优 化4.5.2.1 优 化 模 型 的 遗 传 算 法 处 理 2、 约 束 条 件 的 处 理4.5.2.1 优 化 模 型 的 遗 传 算 法 处 理 4.5.2.1 优 化 模 型 的 遗 传 算 法 处 理 3、 遗 传 算 法 的 迭 代 终 止 条 件 步 1在 搜 索 空 间 U上 定 义 一 个 适 应 度 函 数 f(x)， 给 定 种 群 规 模 N， 交 叉 率 Pc和 变 异 率Pm， 代 数 T；步 2随 机 产 生 U中 的 N个 个 体 s1,s2,sN， 组 成 初 始 种 群 S=s1,s2,sN， 置 代 数 计数 器 t=1；步 3计 算 S中 每 个 个 体 的 适 应 度 f()；步 4若 终 止 条 件 满 足 ， 则 取 S中 适 应 度 最 大 的 个 体 作 为 所 求 结 果 ， 算 法 结 束 。步 5按 选 择 概 率 P(xi)所 决 定 的 选 中 机 会 ， 每 次 从 S中 随 机 选 定 1个 个 体 并 将 其 染 色体 复 制 ， 共 做 N次 ， 然 后 将 复 制 所 得 的 N个 染 色 体 组 成 群 体 S1；步 6按 交 叉 率 Pc所 决 定 的 参 加 交 叉 的 染 色 体 数 c， 从 S1中 随 机 确 定 c个 染 色 体 ， 配对 进 行 交 叉 操 作 ， 并 用 产 生 的 新 染 色 体 代 替 原 染 色 体 ， 得 群 体 S2； 步 7按 变 异 率 Pm所 决 定 的 变 异 次 数 m， 从 S2中 随 机 确 定 m个 染 色 体 ， 分 别 进 行 变异 操 作 ， 并 用 产 生 的 新 染 色 体 代 替 原 染 色 体 ， 得 群 体 S3；步 8将 群 体 S3作 为 新 一 代 种 群 ， 即 用 S3代 替 S， t=t+1， 转 步 3； 基 本 遗 传 算 法 步 聚 例 4.1利 用 遗 传 算 法 求 解 区 间 0,31 上 的二 次 函 数 y=x2的 最 大 值 。 y=x2 31 XY 分 析 原 问 题 可 转 化 为 在 区 间 0, 31 中 搜 索 能 使 y取 最大 值 的 点 a的 问 题 。 那 么 ， 0, 31 中 的 点 x就 是 个 体 , 函 数 值 f(x)恰 好 就 可 以 作 为 x的 适 应 度 ， 区 间 0, 31就 是 一 个 (解 )空 间 。 这 样 , 只 要 能 给 出 个 体 x的 适 当 染色 体 编 码 , 该 问 题 就 可 以 用 遗 传 算 法 来 解 决 。 解 (1) 设 定 种 群 规 模 ,编 码 染 色 体 ， 产 生 初 始 种 群 。 将 种 群 规 模 设 定 为 4； 用 5位 二 进 制 数 编 码 染 色 体 ； 取下 列 个 体 组 成 初 始 种 群 S1: s1= 13 (01101), s2= 24 (11000) s3= 8 (01000), s4= 19 (10011) (2) 定 义 适 应 度 函 数 , 取 适 应 度 函 数 ： f (x)=x2 (3) 计 算 各 代 种 群 中 的 各 个 体 的 适 应 度 , 并 对 其 染 色体 进 行 遗 传 操 作 ,直 到 适 应 度 最 高 的 个 体 (即 31（ 11111） )出 现 为 止 。 再 计 算 种 群 S1中 各 个 体 的 选 择 概 率 。 Nj jii xfxfxP 1 )()()(选 择 概 率 的 计 算 公 式 为 由 此 可 求 得 P(s1) = P(13) = 0.14 P(s2) = P(24) = 0.49 P(s 3) = P(8) = 0.06 P(s4) = P(19) = 0.31 赌 轮 选 择 示 意s40.31s20.49 s10.14s30.06 赌轮选择法 在 算 法 中 赌 轮 选 择 法 可 用 下 面的 子 过 程 来 模 拟 : 在 0,1 区 间 内 产 生 一 个均 匀 分 布 的 随 机 数 r。 若 rq1,则 染 色 体 x1被 选 中 。 若