人工智能产生式系统

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