第2章 人工智能系统的基本结构.ppt

第二章人工智能系统的基本结构 产生式系统 ProductionSystem 也称作基于规则的系统 是人工智能系统中最典型 最普遍的结构 第二章人工智能系统结构 2 1产生式系统概述2 2问题的表示2 3控制策略分类2 4产生式系统的类型 2 1产生式系统概述 产生式 也称作规则 或产生式规则 用于描述各种知识单元间广泛存在的因果关系 即前提和结论之间的关系 在产生式系统中 待描述系统的知识被分为两部分 事实 表示已知事实 如事物 事件及其之间关系 也可以看作是无前提条件的产生式 产生式规则 前提和结论之间的关系式 表示推理过程和行为 2 1 1产生式系统的基本结构 三个基本部分 综合数据库 事实库 规则库 规则集 控制器 规则解释 1 综合数据库是产生式系统使用的主要数据结构 存储有关问题状态 性质等事实 叙述型知识 包括推理过程中形成的中间结论 对应问题的表示信息 2 规则库是产生式规则的集合 存储有关问题的状态转移 性质变化等规则 过程型知识 规则形式 if条件then行动if前提then结论如果某规则的前件能够被事实库中的事实满足 则该规则被激活 3 控制器是规则的解释程序或执行程序 它规定选择一条可用规则的原则和规则使用的方式 推理方向 并根据综合数据库的信息 控制求解问题的过程 控制策略 推理引擎 通常从选择规则到执行操作分三步 匹配 判断规则的前件是否成立 可能有多条规则的前件能够与综合数据库中的事实匹配 冲突解决 选择可调用的规则 从匹配满足的规则集中选择一条规则 执行规则 并在满足结束条件时终止产生式系统的运行 如果规则的后件是结论 把该结论加入综合数据库 如果规则的后件是动作 执行该动作 4 产生式系统的特点 数据 知识和控制相互独立 知识具有相对固定的格式 均由左 右两部分组成 知识无序性与模块化 知识的补充和修改非常容易 控制系统与问题无关 2 1 2产生式系统的基本过程 基本算法如下 过程PRODUCTION1 DATA 初始数据库2 UntilDATA满足结束条件 匹配 之前 do 3 从规则集中选一条可应用于DATA的规则R 选择 4 综合数据库 R应用到DATA得到结果 执行 上述过程是 匹配 选择 执行 的循环过程 2 2问题的表示 用产生式系统求解问题 就是把一个问题的描述转化成产生式系统的三个部分 其中问题的表示 即综合数据库和规则集的描述 对问题的求解有很大的影响 状态空间法 所求问题的已知事实及中间结论 称为状态 状态的集合及状态间的转移规则构成问题的表示 基于这种表示的问题求解称为状态空间法 求解过程是 通过对可能的状态空间的搜索求得一个解 PRODUCTION过程 问题归约法 待求问题分解为一些较为简单的子问题 且子问题也可以分解 所以可得到若干子问题 包含问题 子问题的集合与问题分解的规则一起构成问题的表示 基于这种表示的问题求解称为问题归约法 求解过程是 通过对各个子问题解答的搜索求得原问题的解答 SPLIT过程 2 2 1状态空间法 状态空间可用三元组 S O G 来描述S是状态集合 状态是表示某种事实的符号或数据 问题的状态可以用任何类型的数据结构描述 起始状态S0是S的一个非空子集 描述问题的初始状态 G是目标状态 G是S的一个非空子集 它可以是一个或多个要达到的状态 也可以是对某些状态性质的描述 O是规则集合 集合中的每个元素称作操作算子 将一个状态转化为另一个状态 问题求解 从S0出发 经过一系列操作变换达到G 即状态空间搜索问题 状态空间的一个解是一个有限的规则序列 即为状态空间的一个解 解不一定唯一 2 2 2问题归约法 问题归约法也可用一个三元组 S0 O P 来描述S0是初始问题 即要求解的问题 P是本原问题集 其中的每一个问题是自然成立的 不需证明的 O是操作算子集 一个操作算子可把一个问题化成若干个子问题 该方法由问题出发 运用操作算子产生一些子问题 对子问题再运用操作算子产生子问题的子问题 一直进行到产生的问题均为本原问题 则问题得解 问题归约的最终目的是产生本原问题 问题归约法是比状态空间法更一般的问题求解方法 如果在归约法中 每运用一次操作算子 只产生一个子问题 则就是状态空间法 2 2 3产生式系统举例 图2 1八数码游戏问题描述 给定一种初始布局 初始状态 和一个目标的布局 目标状态 问如何移动将牌 实现从初始状态到目标状态的转变 一个合理的走步序列是问题的一个解 1 综合数据库 选择一种数据结构表示将牌布局 本例选用二维数组来表示布局较直观 其数组元素用表示 其中且互不相等 这样每个具体取值矩阵就代表了一个棋局状态 显然 该问题有个状态 2 规则集 移动一块将牌 即走一步 就使状态发生一次转变 有四种走法 空格左移 空格上移 空格右移 空格下移 记数组第i行第j列的元素为空格所在的行 列分别记为 则则空格左移一格 空格上移一格 空格右移一格 空格下移一格可用如下4条规则来描述 规则1 空格左移一格 规则2 空格上移一格 规则3 空格右移一格 规则4 空格下移一格 3 控制策略 从规则集中选择规则并作用于状态的一种广义选取函数 确定某一策略后 可以用算法的形式给出程序 使用该策略从初始状态出发 通过不断寻求满足一定条件的问题状态 最后到达目标状态 2 3控制策略分类对当前的状态 只要某一条规则作用之后能生成合法的新状态 那么 这条规则就是可用规则 产生式系统的运行表现出一种搜索过程 在每一个循环中选一条规则试用 直到找到某一个序列能产生满足结束条件的状态为止 不同的控制策略产生不同的解 高效率的控制策略能够走较少的步骤达到目标 但需要问题求解的足够知识 控制策略分为两类 不可撤回方式 Irrevocable 和试探方式 Tentative 1 不可撤回方式 思想 利用问题给出的局部知识决定如何选取规则 已用过的规则不能撤回 优点是控制简单 例 爬山问题 登山过程中 登山人的目标是爬上峰顶 如何一步一步地向目标前进就是一个策略问题 通常 人们利用高度随位置变化的函数H P 来引导爬山 这是一种不可撤回方式 利用H P 可以计算朝不同方向迈出一步后高度的变化情况 即向东 z1 H P0 x H P0 向西 z2 H P0 x H P0 向北 z3 H P0 y H P0 向南 z4 H P0 y H P0 选择 z变化最大的那一步攀登 到达新的位置P 从P开始重复这一过程 直到到达山顶 图2 2爬山过程示意图 假设登山人当前所处的位置为P0 如果只有四个方向可供选择 向东 x 向西 x 向北 y 向南 y 分别记为规则1 2 3 4 爬山算法1 开始状态作为一个可能状态 2 从一个可能状态 应用可用规则集生成所有新的可能状态集 3 对该状态集中每一状态 1 进行状态测试 检查其是否为目标 2 如果是目标则程序停止 3 如果不是目标 计算该状态的好坏或者比较各状态的好坏 4 取状态集中最好状态 作为下一个可能状态 5 回到第2步 爬山算法缺点 有时到达某一状态后 尽管它不是目标状态 但在测试过中又找不到比该状态更好的状态 如图2 3 局部极大点 多峰时处于非主峰 它比周围邻居状态都好 但不是目标 平顶 它与全部邻居状态都有同一个值 山脊 如果搜索方向与山脊的走向不一致 则有可能会停留在山脊处 所以 用不可撤回方式来求解登山问题 需要对状态测试函数进行选择 这个函数应具有单极值 且这个极值对应目标状态值 图2 3爬山法的三种可能状态 测试函数例 以8数码为例 统计 不在位 将牌个数 逐一比较当前状态与目标状态对应位置 有差异的将牌总个数 并取其负值作为状态描述的函数 W n n为测试状态 基于该定义 下图所示状态的函数值为 4 显然 目标状态的函数值为0 28316475 123 45 76 8 12384765 图2 4八数码问题各状态的爬山函数值 爬山法的策略执行使新状态的测试函数值有最大增长的规则 所有规则都不能使新状态的测试函数值增长时 执行使测试函数值不减少的规则 如果以上两种规则都不存在 则过程停止 2 试探方式 试探方式分为两种 回溯方式和图搜索方式 回溯方式 应用规则后遇到规定的情况时 返回到最近的回溯点 无特殊规定时 最近的上一状态即是回溯点 从那里改选另外一条可应用规则 2 试探方式 对八数码问题而言 在3种情况下应考虑回溯 新生成的状态在通向目标的路径上已经出现过 从初始状态开始 在应用了指定数目的规则后 仍没有找到目标状态 对当前状态 再没有可应用规则 假如规定的搜索深度为6层 表现为 应用了第6条规则之后得到的状态仍然不是目标状态 回溯策略应用于八数码游戏时的一部分搜索图如图2 5所示 同状态4 回溯到上一步 到状态5 同状态5 回溯到上一步 到状态6 用了6条规则 未找到解 回溯到上一步 到状态6 状态6的所有规则用完 回溯到上一步 到状态5 图2 5利用回溯策略的部分搜索图 图搜索方式 对任一状态 应用其所有可应用规则 并把状态变化过程用图结构记录下来 一直到得到解为止 图搜索策略求解问题是一种穷举方式 图搜索方式下 求得一条解路径需要搜索问题的整个求解空间 对于状态空间较大的问题 需要利用与问题有关的知识引导规则的选择 以便在较窄的空间内找到问题的解 搜索过程中利用应用问题相关知识对规则进行选择的搜索 称为启发式图搜索 图2 7是5个城市旅行商问题的地图 求从A出发经B C D E再回到A的最短路径 问题的表示 若每个城市用一个字母表示 则综合数据库可用字母组成的表或字符串来表示 如 A 表示初始状态 A A 表示目标状态 A 表示访问两个城市后的当前状态 启发式图搜索例 问题 旅行商问题 一个推销员要到几个城市办理业务 城市间里程数已知 求 从某个城市出发 每个城市只允许访问一次 最后回到出发城市的最短距离环路 图2 7旅行商问题的地图 规则集 1 下一步走向城市A 2 下一步走向城市B 5 下一步走向城市E 问题的约束 不可以重复经过同一城市 在没有转完所有城市时 不能走向起点城市A 引导策略 每次走向离得最近的城市 图2 8表示求解该问题时 用启发式图搜索控制方式生成的搜索树 初态 A B C D E 图2 8用启发式图搜索生成的搜索树 三种控制方式有不同的特点 不可撤回方式沿着单独的一条路径延伸搜索 回溯方式保留部分搜索树结构