人工智能产生式系统.ppt

第二章 产生式系统,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 1DATA 初始数据库 2Until DATA 满足结束条件之前，do：（匹配）3Begin 4在规则集中，选一条可应用于DATA的规则R（选 择）5DATA R 应用到 DATA 得到的结果（执行）6End上述过程是“匹配、选择、执行”的循环过程。,2.2 问题的表示,用产生式系统求解问题，就是把一个问题的描述转化成产生式系统的三个部分。其中问题的表示（即综合数据库和规则集的描述）对问题的求解有很大的影响。常用方法有两个：状态空间法和问题归约法。状态空间法：找出所求问题的各种状态，通过对可能的状态空间的搜索求得一个解。（PRODUCTION过程）问题归约法：在解决一个较为复杂的问题时，我们可把问题分解为一些较为简单的子问题，通过对各个子问题解答的搜索求得原问题的解答。（SPLIT过程）,2.2.1 状态空间法,状态空间可用三元组（S，O，G）来描述，S状态集合。状态是某种事实的符号或数据，任何类型的数据结构都可以描述问题的状态。起始状态S0表示S的一个非空子集，它是问题的现状或已知条件；目标状态G也是S的一个非空子集，它可以是一个或多个要达到的目标，也可是对某些状态性质的描述。O是操作算子（规则）集，利用它将一个状态转化为另一个状态.中间状态：求解过程中的状态；状态空间：所有可能的状态集合；状态转换：靠规则实现问题求解：从S0出发，经过一系列操作变换，达到G，即状态空间搜索问题。状态空间的一个解是一个有限的规则序列：，其中，即为状态空间的一个解，解不一定唯一。,2.2.2 问题归约法,问题归约法也可用一个三元组（S0，O，P）来描述，其中：S0是初始问题，即要求解的问题；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）计算一下不同方向迈出一步后高度的变化情况。即相应地求出z1=H（x）-H0、z2=H（-x）-H0、z3=H（y）-H0、z4=H（-y）-H0，然后选择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）。引导策略：每次走向离的最近的城市。下图表示求解该问题时，用启发式图搜索控制方式生成的搜索树。,图2-8 用启发式图搜索生成的搜索树,三种控制方式有不同的特点：,不可撤回方式相当于沿着单独的一条路向下延伸搜索下去；回溯方式则不保留完整的搜索树结构，只记住当前工作的一条路径，回溯就是对这条路径进行修正；穷举图搜索方式则记下完整的搜索树。,2.4 产生式系统的类型,1、正向、逆向、双向产生式系统 正向：是从初始状态出发朝着目标状态的方向来使用规则，称其为F规则。逆向：如果选取目标描述作为初始综合数据库逆向进行求解，即逆向使用规则，产生子目标状态，反方向一步一步朝着初始状态方向求解，称其为B规则。若以双向搜索的方式（正向和逆向同时进行）去求解问题，则称为双向产生式系统。此时，必须把状态描述和目标描述合并成综合数据库，F规则只适用于状态描述部分，B规则则用于目标描述部分。这几种推理的效率视具体问题而定.,2、可交换的产生式系统,如果一个产生式系统对任一个状态数据库D都具有如下3个性质，则称这个产生式系统是可交换的。1）可应用于D的规则集合，对用了其中任意一条规则之后所生成的任何数据库，这个规则集合仍然适用；2）满足目标条件的某个数据库D，当应用任何一个可应用于数据库D的规则之后所生成的任何数据库，仍然满足目标条件。3）若对D应用某一规则序列之后得到一个数据库D1（设有一对应于D D1的一条解路），则当改变D 的可应用规则集合中的规则次序后，仍然可求得解，即求得D1与使用满足D的可应用规则集合中的规则次序无关。,例如：给定一个整数集合a，b，c，可通过把集合中任意一对元素的乘积作为新元素添加到集合中的办法来扩大该整数集，要求通过若干次操作后能够生成出所需的整数集合来。问题描述：综合数据库用集合表示，问题的初始状态为a，b，c，目标状态为a，b，c，ab，bc，ca，初始状态可用的规则集合为：R1：将集合中第一个元素与第二个元素相乘，将生成的整数 添加到集合。R2：将集合中第二个元素与第三个元素相乘，将生成的整数添加到集合。R3：将集合中第三个元素与第一个元素相乘，将生成的整数添加到集合。通过测验，这个产生式系统具有上述三个性质，具有可交换性，其状态空间图如图。(适用不可撤回方式?),图2-9、整数集合生成问题的状态空间图,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所示。,图2-10、重写问题的部分搜索图,一个可分解产生式系统，其基本过程描述如下：,过程 SPLIT（1）DATA：=初始数据库（2）Di：=DATA 的分解式，Di 都可看成单独的数据库（3）Until Di的所有元素都满足结束条件之前，do：（4）Begin（5）从Di中选择一个不满足结束条件的D*（6）如果D*能够与任一条规则的前件匹配，则从Di中 删去D*（7）将该条规则R应用于D*（8）D：=R应用于D*的结果（并仍将其表示为分解式）（9）在Di中添加D（10）end,SPLIT系统的策略是在第5步选一个分量数据库D*，第6步检查是否有一个可利用的规则，如果没有，继续选取下一个分量；否则，在第7步应用该规则，并用结果替代原分量。重复该过程，直到得到一个解。上图中的两个解分别为R2、R3、R3、R4、R3、R3，R4、R2、R3、R3、R3、R3。如果用节点表示综合数据库，有向弧组（含小段圆弧）表示复合数据库和分解后的各分量数据库之间具有的与关系，其余有向弧表示某个分量数据库和应用规则之后产生的新数据库之间具有的或关系，则重写问题的与或图表示如图2-11所示。在与关系表示中，后继节点的集合中全部分量都处理完，本复合节点（数据库）才算处理完，而在或关系表示中，后继节点中只要有一个处理完毕，本节点就算处理完成，双线框代表满足结束条件的终节点。,图2-11 重写问题的与或图,