人工智能产生式系统.ppt

《人工智能产生式系统.ppt》由会员分享，可在线阅读，更多相关《人工智能产生式系统.ppt（30页珍藏版）》请在优知文库上搜索。

1、第二章第二章 产生式系统产生式系统 2.1 产生式系统概述 2.2 问题的表示 2.3 控制策略分类 2.4 产生式系统的类型 2.1 产生式系统概述 在自然界的各种知识单元之间存在着大量的因果关系。这是前提和结论之间的关系，可用产生式（或称规则）来表示。产生式也称作规则，或产生式规则。 产生式（规则）：前提和结论之间的关系式。 表示形式：前提结论 例：1. 如果获得学士学位就有资格考取硕士研究生 2. 如果获得学士学位成绩名列前茅德育优良就有 资格推免上硕士 研究生 事实：无需前提条件的产生式，可用于表示已知的事实。 表示形式：事实2.1.1 产生式系统的基本结构 三个基本部分：综合数据库、

2、产生式规则、控制系统。1、综合数据库是产生式使用的主要数据结构，它用来表述问题状态或有关事实，对应于表示问题的说明式知识。2、一组产生式规则构成了规则库，每一条规则形如: if 条件 then 行动 或 if 前提 then 结论 例如 1： if 某动物有羽毛 then 该动物是鸟类 2： if 某动物是鸟 and 有长脖子 and 有长腿 and 不会 飞 then 该动物是鸵鸟 （前提结论） 3： if 老虎在铁笼中 and 鸡在同一铁笼中 and 老虎饿 了 then 老虎吃掉这只鸡 （条件行动） 3、控制系统是规则的解释程序，它规定了选择一条可用规则的原则和规则使用的方式 (推理方向

3、)，并根据综合数据库的信息，控制求解问题的过程。 4、产生式系统的特点： 相对固定的格式：均由左、右两部分组成 知识的模块化：知识元 、元知识 、高阶元知识；知识的模块化使得知识库（规则）的补充和修改变得非常容易 。 相互影响的间接性：“数据驱动”，是通过修改数据库来间接实现 。 机器可读性 ：机器识别产生式、语法检查和某种程度上的语义检查 2.1.2 产生式系统的基本过程 基本算法如下 ： 过程PRODUCTION 1DATA 初始数据库 2Until DATA 满足结束条件之前，do：（匹配） 3 Begin 4在规则集中，选一条可应用于DATA的规则R（选 择） 5 DATA R 应用到

4、 DATA 得到的结果 （执行） 6 End上述过程是 “匹配、选择、执行”的循环过程。 2.2 问题的表示 用产生式系统求解问题，就是把一个问题的描述转化成产生式系统的三个部分。其中问题的表示（即综合数据库和规则集的描述）对问题的求解有很大的影响。 常用方法有两个：状态空间法和问题归约法。 状态空间法：找出所求问题的各种状态，通过对可能的状态空间的搜索求得一个解。（PRODUCTION过程） 问题归约法：在解决一个较为复杂的问题时，我们可把问题分解为一些较为简单的子问题，通过对各个子问题解答的搜索求得原问题的解答。 （SPLIT过程） 2.2.1 状态空间法 状态空间可用三元组（S，O，G）

5、来描述， S状态集合。状态是某种事实的符号或数据，任何类型的数据结构都可以描述问题的状态。起始状态S0表示S的一个非空子集，它是问题的现状或已知条件；目标状态G也是S的一个非空子集，它可以是一个或多个要达到的目标，也可是对某些状态性质的描述。O是操作算子（规则）集，利用它将一个状态转化为另一个状态. 中间状态：求解过程中的状态；状态空间：所有可能的状态集合；状态转换：靠规则实现 问题求解：从S0出发，经过一系列操作变换，达到G，即状态空间搜索问题。状态空间的一个解是一个有限的规则序列： ，其中， 即为状态空间的一个解，解不一定唯一。GSSSkOOO21021kOO,12.2.2 问题归约法 问

6、题归约法也可用一个三元组（S0，O，P）来描述，其中： S0是初始问题，即要求解的问题；P是本原问题集，其中的每一个问题是不证明的，自然成立的； O操作算子集，通过一个操作算子把一个问题化成若干个子问题。 该方法是由问题出发，运用操作算子产生一些子问题，对子问题再运用操作算子产生子问题的子问题，这样一直进行到产生的问题均为本原问题，则问题得解。 所有问题归约的最终目的是产生本原问题。问题归约法是比状态空间法更一般的问题求解方法，如果在归约法中，每运用一次操作算子，只产生一个子问题，则就是状态空间法。 2.2.3 举例 图2-1、八数码游戏 问题描述：给定一种初始布局（初始状态）和一个目标的布局

7、（目标状态），问如何移动将牌，实现从初始状态到目标状态的转变。问题的解就是给出一个合理的走步序列。 1综合数据库：就是要选择一种数据结构来表示将牌布局。本例中，选用二维数组来表示布局较直观，其数组元素用 表示，其中， 且互不相等，这样数组的每个具体取值矩阵就代表了一个棋局状态。显然，该问题有 个状态。 2834 571612345678ijS8 , 1 , 0, 3,1ijSji362880! 9111213141516171819CCCCCCCCC 2. 规则集：移动一块将牌（即走一步）就使状态发生一次转变。有四种走法：空格左移、空格上移、空格下移、空格右移。当然，每种走法都有条件，且可用如

8、下4条规则来模拟：（设 为数组第i行第j列的数码元素， 为空格所在的行、列数值，即 ），则 规则1: （向左移一格） 规则2: （向上移一格） 规则3: （向右移一格） 规则4: （向下移一格） ijS00, ji000jiS; 0,2)1()1(0000000jijijiSSSthenjif; 0,2000000)1()1(0jijijiSSStheniif; 0,2)1()1(0000000jijijiSSSthenjif; 0,2000000)1()1(0jijijiSSStheniif 3.控制策略：是从规则集中选择规则并作用于状态的一种广义选取函数。确定某一策略后，就可以用算法的形式

9、给出程序。它从初始状态出发，通过不断寻求满足一定条件的问题状态，最后到达目标状态。 2.3 控制策略分类 对当前的状态，只要某一条规则作用之后能生成合法的新状态，那么，这条规则就是可用规则。所以，产生式系统的运行表现出一种搜索过程，在每一个循环中选一条规则试用，直到找到某一个序列能产生一个满足结束条件的状态为止。 不同的控制策略能够产生不同的解，高效率的控制策略能够走较少的步骤达到目标，但需要问题求解的足够知识。控制策略可分为两类：不可撤回方式（Irrevocable）和试探方式（Tentative）。1）不可撤回方式： 思想: 利用问题给出的局部知识来决定如何选取规则，不必考虑撤回已用过的规

10、则，其优点是控制简单。 例、爬山问题：人们在登山过程中，目标是爬上峰顶，如何一步一步地向目标前进就是一个策略问题。通常，人们利用高度随位置变化的函数H（P）来引导爬山，这是一种不可撤回方式。 假设登山人当前所处的位置为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开始重复这一过程直到到达山顶。 ZYXP0(x0,y0,z0

11、)y0 x0z0图2-2 爬山过程示意图 爬山算法：1. 开始状态作为一个可能状态。2. 从一个可能状态，应用可应用的规则集合生成所有新的可能状态集。3. 对该状态集中每一状态，进行： 状态测试，检查是否为目标，如果是，则停止。 计算该状态的好坏，或者比较各状态的好坏。4. 取状态集中最好状态，作为下一个可能状态。5. 循环到第2步。 图2-3 爬山法的三种状态 爬山算法的缺点： 有时到达某一状态后，尽管它不是目标状态，但在测试过程中又找不到比该状态更好的状态。三种情况: 局部极大点（多峰时处于非主峰）：它比周围邻居状态都好，但不是目标。 平顶：它与全部邻居状态都有同一个值。 山脊：如果搜索方

12、向与山脊的走向不一致，则会停留在山脊处。 所以，用不可撤回方式来求解登山问题，需对测试函数进行选择：这个函数应具有单极值，且这个极值对应的状态就是目标。 例、以8数码为例：用“不在位”将牌个数（当前状态与目标状态对应位置逐一比较后有差异的将牌总个数）并取其负值作为状态描述的函数. -W（n）（n为任一状态） 因此有: 初始状态 -4，目标状态 0。 爬山法选取规则的原则：选取使用规则后生成的新状态的函数值有最大增长的规则，如没有使函数值增长的规则，则选取使函数值不减少的规则，若这种规则也没有，则过程停止。 对初始状态可应用的规则有3个，比较爬山函数值后，所选取的规则为向上。爬山法搜索过程如下：

13、有圆圈的数字为爬山函数值，图2-4中列出了求解过程所出现的状态序列。 2）试探方式 试探方式又分为两种：回溯方式和图搜索方式。 回溯方式：在选择一条规则时要建立一个回溯点，当计算遇到困难，不能得到一个解时，使状态返回到原来的回溯点上，从那里改选另外一条可应用的规则。 对八数码问题而言，在3种情况下应考虑回溯： （1）、新生成的状态在通向目标的路径上已经出现过； （2）、从初始状态开始，在搜索深度范围所规定的规则数目达到后仍没有找到目标状态； （3）、对当前状态，再没有可应用的规则。 假如规定的搜索深度为6层，回溯策略应用于八数码游戏时的一部分搜索图可如图2-5所示（思考作业 ) 图搜索方式:

14、如果把问题求解过程用图或树的这种结构来描述，即图中的每一个节点代表问题的状态，节点间的弧代表应用的规则，那么问题的求解空间就可由图来表示。图搜索方式就是用某种策略选择应用规则，并把状态变化过程用图结构记录下来，一直到得到解为止，即从图中搜索出含有解路径的子图来。 图搜索策略求解八数码问题采用的是一种穷举方式，对每一个状态可应用的所有规则都要去试，并把结果记录下来。(图2-6) 这样，求得一条解路径要搜索问题的求解空间。对于状态空间较大的问题，需要利用与问题有关的知识来引导规则的选择，以便在较窄的空间内找到问题的解。 5个城市旅行商问题的地图如图所示， 求从A出发经B、C、D、E再回到A的最短路

15、径。 问题的表示：若每个城市用一个字母表示，则综合数据库可用一个字母组成的表或字符串来表示，如（A）表示初始状态，（A*A）表示目标状态，（A*）表示访问两个城市后的当前状态。77101013965610BADEC例如：旅行商问题：一个推销员要到几个城市去办理业务，城市间里程数已知，问题的提法是：从某个城市出发，每个城市只允许访问一次，最后又回到原来的城市，求一条最短距离的路径。图图2-7 2-7 旅行商问题的地图旅行商问题的地图 规则集：1）下一步走向城市A ； 2 ） 下 一 步 走 向 城 市B；， 5）下一步走向城市E；对当前的状态，只要某一条规则作用之后能生成合法的新状态，那么这一条

16、规则就是可应用规则。（不重复走到同一城市，在没有转完所有城市时，不能走向城市A）。 引导策略：每次走向离的最近的城市。下图表示求解该问题时，用启发式图搜索控制方式生成的搜索树。初态（初态（A）B、C、D、E710613（AB）（AC） B、D、E（AD）（AE）5（ACD） B、E6107（ACDE） B（ACDEB） A（ACDEBA） 目标目标图2-8 用启发式图搜索生成的搜索树三种控制方式有不同的特点： 不可撤回方式相当于沿着单独的一条路向下延伸搜索下去； 回溯方式则不保留完整的搜索树结构，只记住当前工作的一条路径，回溯就是对这条路径进行修正； 穷举图搜索方式则记下完整的搜索树。2.4 产生式系统的类型 1、正向、逆向、双向产生式系统 正向：是从初始状态出发朝着目标状态的方向来使用规则，称其为F规则。 逆向：如果选取目标描述作为初始综合数据库逆向进行求解，即逆向使用规则，产生子目标状态，反方向一步一步朝着初始状态方向求解，称其为B规则。 若以双向搜索的方式（正向和逆向同时进行）去求解问题，则称为双向产生式系统。此时，必须把状态描述和目标描述合并成综合数据库，F规则只适用于状态描述