人工智能产生式系统.ppt

Artificial Intelligence 第二章 产生式系统 2.1 产生式系统概述 2.2 问题的表示 2.3 控制策略分类 2.4 产生式系统的类型 Artificial Intelligence 2.1 产生式系统概述 在自然界的各种知识单元之间存在着大量的因果关系。这 是前提和结论之间的关系，可用产生式（或称规则）来表 示。产生式也称作规则，或产生式规则。 产生式（规则）：前提和结论之间的关系式。 表示形式：前提结论 例：1. 如果获得学士学位就有资格考取硕士研究生 2. 如果获得学士学位成绩名列前茅德育优良就有 资格推免上硕士 研究生 事实：无需前提条件的产生式，可用于表示已知的事实。 表示形式：事实 Artificial Intelligence 2.1.1 产生式系统的基本结构 三个基本部分：综合数据库、产生式规则、控制系统。 1、综合数据库是产生式使用的主要数据结构，它用来表述 问题状态或有关事实，对应于表示问题的说明式知识。 2、一组产生式规则构成了规则库，每一条规则形如: if 条件 then 行动 或 if 前提 then 结论 例如 1： if 某动物有羽毛 then 该动物是鸟类 2： if 某动物是鸟 and 有长脖子 and 有长腿 and 不会 飞 then 该动物是鸵鸟 （前提结论） 3： if 老虎在铁笼中 and 鸡在同一铁笼中 and 老虎饿 了 then 老虎吃掉这只鸡 （条件行动） Artificial Intelligence 3、控制系统是规则的解释程序，它规定了选择一条可用 规则的原则和规则使用的方式 (推理方向)，并根据综合 数据库的信息，控制求解问题的过程。 4、产生式系统的特点： 相对固定的格式：均由左、右两部分组成 知识的模块化：知识元 、元知识 、高阶元知识；知 识的模块化使得知识库（规则）的补充和修改变得 非常容易 。 相互影响的间接性：“数据驱动”，是通过修改数 据库来间接实现 。 机器可读性 ：机器识别产生式、语法检查和某种程 度上的语义检查 Artificial Intelligence 2.1.2 产生式系统的基本过程 基本算法如下 ： 过程PRODUCTION 1DATA 初始数据库 2Until DATA 满足结束条件之前，do：（匹配） 3 Begin 4在规则集中，选一条可应用于DATA的规则R（选 择） 5 DATA R 应用到 DATA 得到的结果 （执行） 6 End 上述过程是 “匹配、选择、执行”的循环过程。 Artificial Intelligence 2.2 问题的表示 用产生式系统求解问题，就是把一个问题的描述转化 成产生式系统的三个部分。其中问题的表示（即综合 数据库和规则集的描述）对问题的求解有很大的影响 。 常用方法有两个：状态空间法和问题归约法。 状态空间法：找出所求问题的各种状态，通过对可能 的状态空间的搜索求得一个解。（PRODUCTION过程 ） 问题归约法：在解决一个较为复杂的问题时，我们可 把问题分解为一些较为简单的子问题，通过对各个子 问题解答的搜索求得原问题的解答。 （SPLIT过程） Artificial Intelligence 2.2.1 状态空间法 状态空间可用三元组（S，O，G）来描述， S状态集合 。状态是某种事实的符号或数据，任何类型的数据结构 都可以描述问题的状态。起始状态S0表示S的一个非空 子集，它是问题的现状或已知条件；目标状态G也是S 的一个非空子集，它可以是一个或多个要达到的目标， 也可是对某些状态性质的描述。O是操作算子（规则） 集，利用它将一个状态转化为另一个状态. 中间状态：求解过程中的状态；状态空间：所有可能的 状态集合；状态转换：靠规则实现 问题求解：从S0出发，经过一系列操作变换，达到G， 即状态空间搜索问题。状态空间的一个解是一个有限的 规则序列： ，其中， 即为状态空间的一个解，解不一定唯一。 Artificial Intelligence 2.2.2 问题归约法 问题归约法也可用一个三元组（S0，O，P）来描述，其 中： S0是初始问题，即要求解的问题；P是本原问题集， 其中的每一个问题是不证明的，自然成立的； O操作算 子集，通过一个操作算子把一个问题化成若干个子问题 。 该方法是由问题出发，运用操作算子产生一些子问题， 对子问题再运用操作算子产生子问题的子问题，这样一 直进行到产生的问题均为本原问题，则问题得解。 所有问题归约的最终目的是产生本原问题。问题归约法 是比状态空间法更一般的问题求解方法，如果在归约法 中，每运用一次操作算子，只产生一个子问题，则就是 状态空间法。 Artificial Intelligence 2.2.3 举例 图2-1、八数码游戏 问题描述：给定一种初始布局（初始状态）和一个目 标的布局（目标状态），问如何移动将牌，实现从初 始状态到目标状态的转变。问题的解就是给出一个合 理的走步序列。 1综合数据库：就是要选择一种数据结构来表示将牌 布局。本例中，选用二维数组来表示布局较直观，其 数组元素用 表示，其中， 且互不 相等，这样数组的每个具体取值矩阵就代表了一个棋 局状态。显然，该问题有 个状态。 Artificial Intelligence 2. 规则集：移动一块将牌（即走一步）就使状态发生 一次转变。有四种走法：空格左移、空格上移、空格 下移、空格右移。当然，每种走法都有条件，且可用 如下4条规则来模拟：（设 为数组第i行第j列的数码 元素， 为空格所在的行、列数值，即 ），则 规则1: （向左移一格） 规则2: （向上移一格） 规则3: （向右移一格） 规则4: （向下移一格） Artificial Intelligence 3.控制策略：是从规则集中选择规则并作用于状态的一 种广义选取函数。确定某一策略后，就可以用算法的形 式给出程序。它从初始状态出发，通过不断寻求满足一 定条件的问题状态，最后到达目标状态。 2.3 控制策略分类 对当前的状态，只要某一条规则作用之后能生成合法的新状态 ，那么，这条规则就是可用规则。所以，产生式系统的运行表现出 一种搜索过程，在每一个循环中选一条规则试用，直到找到某一个 序列能产生一个满足结束条件的状态为止。 不同的控制策略能够产生不同的解，高效率的控制策略 能够走较少的步骤达到目标，但需要问题求解的足够知 识。 控制策略可分为两类：不可撤回方式（Irrevocable）和试探方式（ Tentative）。 Artificial Intelligence 1）不可撤回方式： 思想: 利用问题给出的局部知识来决定如何选取 规则，不必考虑撤回已用过的规则，其优点是控制 简单。 例、爬山问题：人们在登山过程中，目标是爬上峰 顶，如何一步一步地向目标前进就是一个策略问题 。通常，人们利用高度随位置变化的函数H（P） 来引导爬山，这是一种不可撤回方式。 Artificial Intelligence 假设登山人当前所处的位置 为P0，如果只存在四种走法 向东（x）、向西（-x ）、向北（y）、向南（- y），这相当于4条规则， 那么这时可以用H（P）计算 一下不同方向迈出一步后高 度的变化情况。即相应地求 出z1=H（x）-H0、 z2=H（-x）-H0、z3=H （y）-H0、z4=H（-y ）-H0，然后选择z变化最 大的那一步攀登，到达新的 位置P，然后从P开始重复这 一过程直到到达山顶。 图2-2 爬山过程示意图 Artificial Intelligence 爬山算法： 1. 开始状态作为一个可能状态。 2. 从一个可能状态，应用可应用的规则集合生成所 有新的可能状态集。 3. 对该状态集中每一状态，进行： 状态测试，检查是否为目标，如果是，则停止 。 计算该状态的好坏，或者比较各状态的好坏。 4. 取状态集中最好状态，作为下一个可能状态。 5. 循环到第2步。 Artificial Intelligence 图2-3 爬山法的三种状态 爬山算法的缺点： 有时到达某一状态后，尽管它不是目标状态，但在测试 过程中又找不到比该状态更好的状态。三种情况: 局部极大点（多峰时处于非主峰）：它比周围邻居状态 都好，但不是目标。 平顶：它与全部邻居状态都有同一个值。 山脊：如果搜索方向与山脊的走向不一致，则会停留在 山脊处。 所以，用不可撤回方式来求解登山问题，需对测试函 数进行选择：这个函数应具有单极值，且这个极值对应 的状态就是目标。 Artificial Intelligence 例、以8数码为例：用“不在位”将牌个数（当 前状态与目标状态对应位置逐一比较后有差异的 将牌总个数）并取其负值作为状态描述的函数. -W（n）（n为任一状态） 因此有: 初始状态 -4，目标状态 0。 爬山法选取规则的原则：选取使用规则后生成的 新状态的函数值有最大增长的规则，如没有使函 数值增长的规则，则选取使函数值不减少的规则 ，若这种规则也没有，则过程停止。 对初始状态可应用的规则有3个，比较爬山函数 值后，所选取的规则为向上。爬山法搜索过程如 下：有圆圈的数字为爬山函数值，图2-4中列出了 求解过程所出现的状态序列。 Artificial Intelligence 2）试探方式 试探方式又分为两种：回溯方式和图搜索方式。 回溯方式：在选择一条规则时要建立一个回溯点，当计算 遇到困难，不能得到一个解时，使状态返回到原来的回溯 点上，从那里改选另外一条可应用的规则。 对八数码问题而言，在3种情况下应考虑回溯： （1）、新生成的状态在通向目标的路径上已经出现过； （2）、从初始状态开始，在搜索深度范围所规定的规则 数目达到后仍没有找到目标状态； （3）、对当前状态，再没有可应用的规则。 假如规定的搜索深度为6层，回溯策略应用于八数码游戏时 的一部分搜索图可如图2-5所示（思考作业 ) Artificial Intelligence 图搜索方式: 如果把问题求解过程用图或树的这种结 构来描述，即图中的每一个节点代表问题的状态， 节点间的弧代表应用的规则，那么问题的求解空间 就可由图来表示。图搜索方式就是用某种策略选择 应用规则，并把状态变化过程用图结构记录下来， 一直到得到解为止，即从图中搜索出含有解路径的 子图来。 图搜索策略求解八数码问题采用的是一种穷举方式 ，对每一个状态可应用的所有规则都要去试，并把 结果记录下来。(图2-6) 这样，求得一条解路径要搜索问题的求解空间。对 于状态空间较大的问题，需要利用与问题有关的知 识来引导规则的选择，以便在较窄的空间内找到问 题的解。 Artificial Intelligence 5个城市旅行商问题的地图如 图所示， 求从A出发经B、C 、D、E再回到A的最短路径 。 问题的表示：若每个城市用一 个字母表示，则综合数据库可 用一个字母组成的表或字符串 来表示，如（A）表示初始状 态，（A*A）表示目标状 态，（A*）表示访问两个城 市后的当前状态。 例如：旅行商问题：一个推销员要到几个城市去办理业务，城市间里 程数已知，问题的提法是：从某个城市出发，每个城市只允许访问一 次，最后又回到原来的城市，求一条最短距离的路径。 图2-7 旅行商问题的地图 Artificial Intelligence 规则集：1）下一步走向城市 A；2）下一步走向城市B； ， 5）下一步走向城市E； 对当前的状态，只要某一条 规则作用之后能生成合法的 新状态，那么这一条规则就 是可应用规则。 （不重复走到同一城市，在没有 转完所有城市时，不能走向 城市A）。 引导策略： 每次走向离的最近的城市。下图 表示求解该问题时，用启发式图 搜索控制方式生成的搜索树。 初态（A）B、C、D、E 710613 （AB） （AC） B、D、E （AD）（AE） 5 （ACD） B、E 6 10 7 （ACDE） B （ACDEB） A （ACDEBA） 目标 图2-8 用启发式图搜索生成的搜索树 Artificial Intelligence 三种控制方式有不同的特点： 不可撤回方式相当于沿着单独的一条路向下延伸 搜索下去； 回溯方式则不保留完整的搜索树结构，只记住当 前工作的一条路径，回溯就是对这条路径进行修 正； 穷举图搜索方式则记下完整的搜索树。 Artificial Intelligence 2.4 产生式系统的类型 1、正向、逆向、双向产生式系统 正向：是从初始状态出发朝着目标状态的方向来使用 规则，称其为F规则。 逆向：如果选取目标描述作为初始综合数据库逆向进 行求解，即逆向使用规则，产生子目标状态，反方向 一步一步朝着初始状态方向求解，称其为B规则。 若以双向搜索的方式（正向和逆向同时进行）去求解 问题，则称为双向产生式系统。此时，必须把状态描 述和目标描述合并成综合数据库，F规则只适用于状 态描述部分，B规则则用于目标描述部分。 这几种推理的效率视具体问题而定 . Artificial Intelligence 2、可交换的产生式系统 如果一个产生式系统对任一个状态数据库D都具有如下3 个性质，则称这个产生式系统是可交换的。 1）可应用于D的规则集合，对用了其中任意一条规则 之后所生成的任何数据库，这个规则集合仍然适用； 2）满足目标条件的某个数据库D，当应用任何一个可 应用于数据库D的规则之后所生成的任何数据库，仍 然满足目标条件。 3）若对D应用某一规则序列之后得到一个数据库D1（ 设有一对应于D D1的一条解路），则当改变D 的可 应用规则集合中的规则次序后，仍然可求得解，即求 得D1与使用满足D的可应用规则集合中的规则次序无 关。 Artificial Intelligence 例如：给定一个整数集合a，b，c，可通过把集合中任 意一对元素的乘积作为新元素添加到集合中的办法来扩大 该整数集，要求通过若干次操作后能够生成出所需的整数 集合来。 问题描述：综合数据库用集合表示，问题的初始状态为a，b，c ，目标状态为a，b，c，ab，bc，ca， 初始状态可用的规则集合为： R1：将集合中第一个元素与第二个元素相乘，将生 成的整数 添加到集合。 R2：将集合中第二个元素与第三个元素相乘，将生 成的整数添加到集合。 R3：将集合中第三个元素与第一个元素相乘，将生 成的整数添加到集合。 通过测验，这个产生式系统具有上述三个性质，具有可交 换性，其状态空间图如图。(适用不可撤回方式?) Artificial Intelligence 图2-9、整数集合生成问题的状态空间图 Artificial Intelligence 3、可分解的产生式系统 将初始数据库分解成几个可以独立加以处理的分量，分 别对它们进行求解。即分别对每个分量，测试产生式规 则可应用的条件，然后应用于每个分量生成出新的数据 库，如此分解、生成交替进行下去，直到各个分量满足 某种结束条件为止。相应地一般结束条件也应分解为对 应于分量数据库所使用的结束条件。能够分解产生式系 统的综合数据库和结束条件的产生式系统称为可分解的 产生式系统。 例如：一个重写问题的产生式系统，其初始数据库为（C，B，Z），产 生式规则的依据是如下的重写规则： R1：C （D，L） R2：C （B，M） R3：B （M，M） R4：Z （B，B，M） 结束状态是（M，M）。 用图搜索方式求解这个问题时，搜索得到的部分状态空间图如图2-10 所示。 Artificial