《人工智能系统的基本结构.ppt》由会员分享，可在线阅读，更多相关《人工智能系统的基本结构.ppt（31页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、第二章第二章 人工智能系统的基本结构人工智能系统的基本结构 产生式系统（产生式系统（Production SystemProduction System），），也称作基于规则的系统，是人工智能也称作基于规则的系统，是人工智能系统中最典型、最普遍的结构。系统中最典型、最普遍的结构。第二章第二章 人工智能系统结构人工智能系统结构 2.1 2.1 产生式系统概述产生式系统概述 2.2 2.2 问题的表示问题的表示 2.3 2.3 控制策略分类控制策略分类 2.4 2.4 产生式系统的类型产生式系统的类型 2.1 2.1 产生式系统概述产生式系统概述 产生式，也称作规则，或产生式规则，用于描述各种产生
2、式，也称作规则，或产生式规则，用于描述各种知识单元间广泛存在的因果关系，即前提和结论之间知识单元间广泛存在的因果关系，即前提和结论之间的关系。的关系。在产生式系统中，待描述系统的知识被分为两部分：在产生式系统中，待描述系统的知识被分为两部分：事实：事实：表示已知事实，如事物、事件及其之间关系，也可表示已知事实，如事物、事件及其之间关系，也可以看作是无前提条件的产生式。以看作是无前提条件的产生式。产生式规则：产生式规则：前提和结论之间的关系式，表示推理过程和前提和结论之间的关系式，表示推理过程和行为。行为。2.1.1 2.1.1 产生式系统的基本结构产生式系统的基本结构 三三个个基基本本部部分分
3、：综综合合数数据据库库（事事实实库库）、规规则则库库（规规则则集集）、控控制制器（规则解释）。器（规则解释）。1 1、综综合合数数据据库库是是产产生生式式系系统统使使用用的的主主要要数数据据结结构构，存存储储有有关关问问题题状状态态、性性质质等等事事实实（叙叙述述型型知知识识），包包括括推推理理过过程程中中形形成成的的中中间间结结论，对应问题的表示信息。论，对应问题的表示信息。2 2、规规则则库库是是产产生生式式规规则则的的集集合合，存存储储有有关关问问题题的的状状态态转转移移、性性质质变化等规则（过程型知识），规则形式变化等规则（过程型知识），规则形式:if if 条件条件 then the
4、n 行动行动 if if 前提前提 then then 结论结论 如果某规则的前件能够被事实库中的事实满足，则该规则被激活。如果某规则的前件能够被事实库中的事实满足，则该规则被激活。3 3、控制器是规则的解释程序或执行程序，它规定选择一条可用规、控制器是规则的解释程序或执行程序，它规定选择一条可用规则的原则和规则使用的方式则的原则和规则使用的方式 (推理方向推理方向)，并根据综合数据库的，并根据综合数据库的信息，控制求解问题的过程（控制策略信息，控制求解问题的过程（控制策略,推理引擎）。通常从选推理引擎）。通常从选择规则到执行操作分择规则到执行操作分三步：三步：匹配。匹配。判断规则的前件是否成
5、立判断规则的前件是否成立?可能有多条规则的前件能够与综合数据库中的事实匹配可能有多条规则的前件能够与综合数据库中的事实匹配!冲突解决，选择可调用的规则。冲突解决，选择可调用的规则。从匹配满足的规则集中选择一条规则。从匹配满足的规则集中选择一条规则。执行规则，并在满足结束条件时终止产生式系统的运行。执行规则，并在满足结束条件时终止产生式系统的运行。如果规则的后件是结论，把该结论加入综合数据库；如果规则的后件是结论，把该结论加入综合数据库；如果规则的后件是动作，执行该动作；如果规则的后件是动作，执行该动作；4 4、产生式系统的特点：、产生式系统的特点：数据、知识和控制相互独立。数据、知识和控制相互
6、独立。知识具有相对固定的格式：均由左、右两部分组成。知识具有相对固定的格式：均由左、右两部分组成。知识无序性与模块化：知识的补充和修改非常容易。知识无序性与模块化：知识的补充和修改非常容易。控制系统与问题无关。控制系统与问题无关。2.1.2 2.1.2 产生式系统的基本过程产生式系统的基本过程 基本算法如下基本算法如下 ：过程过程PRODUCTIONPRODUCTION 1 1DATA DATA 初始数据库初始数据库 2 2Until DATA Until DATA 满足结束条件满足结束条件(匹配）之前匹配）之前,do:,do:3 3从规则集中选一条可应用于从规则集中选一条可应用于DATADA
7、TA的规则的规则R R（选择）（选择）4 4综合数据库综合数据库 R R 应用到应用到 DATA DATA 得到结果得到结果 （执行）（执行）上述过程是上述过程是 “匹配、选择、执行匹配、选择、执行”的循环过程的循环过程。2.2 2.2 问题的表示问题的表示 用产生式系统求解问题，就是把一个问题的描述转化成产生式系统的三个部用产生式系统求解问题，就是把一个问题的描述转化成产生式系统的三个部分。其中问题的表示（即综合数据库和规则集的描述）对问题的求解有很大分。其中问题的表示（即综合数据库和规则集的描述）对问题的求解有很大的影响。的影响。状态空间法状态空间法。所求问题的已知事实及中间结论，称为状态
8、。状态的集合及。所求问题的已知事实及中间结论，称为状态。状态的集合及状态间的转移规则构成问题的表示。基于这种表示的问题求解称为状态间的转移规则构成问题的表示。基于这种表示的问题求解称为状态空状态空间法间法。求解过程是，通过对可能的状态空间的搜索求得一个解。求解过程是，通过对可能的状态空间的搜索求得一个解。（PRODUCTIONPRODUCTION过程）过程）问题归约法问题归约法。待求问题分解为一些较为简单的子问题，且子问题也可以分。待求问题分解为一些较为简单的子问题，且子问题也可以分解，所以可得到若干子问题。包含问题、子问题的集合与问题分解的规则解，所以可得到若干子问题。包含问题、子问题的集合
9、与问题分解的规则一起构成问题的表示。基于这种表示的问题求解称为一起构成问题的表示。基于这种表示的问题求解称为问题归约法问题归约法。求解过。求解过程是，通过对各个子问题解答的搜索求得原问题的解答。程是，通过对各个子问题解答的搜索求得原问题的解答。（SPLITSPLIT过程）过程）2.2.1 2.2.1 状态空间法状态空间法状态空间可用三元组（状态空间可用三元组（S，O，G）来描述）来描述S是状态集合。状态是表示某种事实的符号或数据。问题的状态可以用任何类型的是状态集合。状态是表示某种事实的符号或数据。问题的状态可以用任何类型的数据结构描述。起始状态数据结构描述。起始状态S0是是S的一个非空子集，
10、描述问题的初始状态。的一个非空子集，描述问题的初始状态。G是目标状态。是目标状态。G是是S的一个非空子集，它可以是一个或多个要达到的状态，也可的一个非空子集，它可以是一个或多个要达到的状态，也可以是对某些状态性质的描述。以是对某些状态性质的描述。O是规则集合。集合中的每个元素称作操作算子，将一个状态转化为另一个状态。是规则集合。集合中的每个元素称作操作算子，将一个状态转化为另一个状态。问题求解：从问题求解：从S S0 0出发，经过一系列操作变换达到出发，经过一系列操作变换达到G G，即状态空间搜索问题。状态空间的一个解是一个有限的规则序列，即状态空间搜索问题。状态空间的一个解是一个有限的规则序
11、列，即为状态空间的一个解，解不一定唯一。即为状态空间的一个解，解不一定唯一。2.2.2 2.2.2 问题归约法问题归约法 问题归约法也可用一个三元组（问题归约法也可用一个三元组（S0，O，P）来描述）来描述S0是初始问题，即要求解的问题；是初始问题，即要求解的问题；P是本原问题集，其中的每一个问题是自然成立的，不需证明的；是本原问题集，其中的每一个问题是自然成立的，不需证明的；O是操作算子集，一个操作算子可把一个问题化成若干个子问题。是操作算子集，一个操作算子可把一个问题化成若干个子问题。该方法由问题出发，运用操作算子产生一些子问题，对子问题再运用操作该方法由问题出发，运用操作算子产生一些子问
12、题，对子问题再运用操作算子产生子问题的子问题，一直进行到产生的问题均为本原问题，则问题算子产生子问题的子问题，一直进行到产生的问题均为本原问题，则问题得解。问题归约的最终目的是产生本原问题。得解。问题归约的最终目的是产生本原问题。问题归约法是比状态空间法更一般的问题求解方法，如果在归约法中，每问题归约法是比状态空间法更一般的问题求解方法，如果在归约法中，每运用一次操作算子，只产生一个子问题，则就是状态空间法。运用一次操作算子，只产生一个子问题，则就是状态空间法。2.2.3 2.2.3 产生式系统举例产生式系统举例 图图2-1 2-1 八数码游戏八数码游戏问问题题描描述述：给给定定一一种种初初始
13、始布布局局（初初始始状状态态）和和一一个个目目标标的的布布局局（目目标标状状态态），问问如如何何移移动动将将牌牌，实实现现从从初初始始状状态态到到目目标标状态的转变。状态的转变。一个合理的走步序列是问题的一个解。一个合理的走步序列是问题的一个解。1 1综合数据库：选择一种数据结构表示将牌布局。综合数据库：选择一种数据结构表示将牌布局。本例选用二维数组来表示布局较直观，其数组元素用本例选用二维数组来表示布局较直观，其数组元素用 表示，其中表示，其中 且互不相等。且互不相等。这样每个具体取值矩阵就代表了一个棋局状态。显然，这样每个具体取值矩阵就代表了一个棋局状态。显然，该问题有该问题有 个状态。个
14、状态。2.2.规规则则集集：移移动动一一块块将将牌牌（即即走走一一步步）就就使使状状态态发发生生一一次次转转变变。有有四四种种走走法法：空空格格左左移移、空空格格上移、空格右移、空格下移。上移、空格右移、空格下移。记数组第记数组第 i i 行第行第 j j 列的元素为列的元素为 空格所在的行、列分别记为空格所在的行、列分别记为 ，则，则 则则空空格格左左移移一一格格、空空格格上上移移一一格格、空空格格右右移移一一格、空格下移一格可用如下格、空格下移一格可用如下4 4条规则来描述：条规则来描述：规则规则1:1:（空格左移一格）（空格左移一格）规则规则2:2:（空格上移一格）（空格上移一格）规则规
15、则3:3:（空格右移一格）（空格右移一格）规则规则4:4:（空格下移一格）（空格下移一格）3.3.控制策略：从规则集中选择规则并作用于状控制策略：从规则集中选择规则并作用于状态的一种广义选取函数。态的一种广义选取函数。确定某一策略后，可以用算法的形式给出确定某一策略后，可以用算法的形式给出程序。使用该策略从初始状态出发，通过不断程序。使用该策略从初始状态出发，通过不断寻求满足一定条件的问题状态，最后到达目标寻求满足一定条件的问题状态，最后到达目标状态。状态。2.3 2.3 控制策略分类控制策略分类对当前的状态，只要某一条规则作用之后能生成合法的新状态，对当前的状态，只要某一条规则作用之后能生成
16、合法的新状态，那么，这条规则就是可用规则。那么，这条规则就是可用规则。产生式系统的运行表现出一种搜索过程，在每一个循环中选一产生式系统的运行表现出一种搜索过程，在每一个循环中选一条规则试用，直到找到某一个序列能产生满足结束条件的状态条规则试用，直到找到某一个序列能产生满足结束条件的状态为止。为止。不同的控制策略产生不同的解，高效率的控制策略能够走较少不同的控制策略产生不同的解，高效率的控制策略能够走较少的步骤达到目标，但需要问题求解的足够知识。的步骤达到目标，但需要问题求解的足够知识。控控制制策策略略分分为为两两类类：不不可可撤撤回回方方式式（IrrevocableIrrevocable）和和
17、试试探探方方式（式（TentativeTentative）。1 1）不可撤回方式：）不可撤回方式：思想思想:利用问题给出的局部知识决定如何选取规则，利用问题给出的局部知识决定如何选取规则，已用过的规则不能撤回。优点是控制简单。已用过的规则不能撤回。优点是控制简单。例：爬山问题。登山过程中，登山人的目标是爬上例：爬山问题。登山过程中，登山人的目标是爬上峰顶，如何一步一步地向目标前进就是一个策略问峰顶，如何一步一步地向目标前进就是一个策略问题。通常，人们利用高度随位置变化的函数题。通常，人们利用高度随位置变化的函数H(P)来来引导爬山，这是一种不可撤回方式。引导爬山，这是一种不可撤回方式。利用利用
18、 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 2-2 爬山过程示意图爬山过程示意图假设登山人当前所处的位置为假设登山人当前所处的位置为P0，如果只有四个方向可供选，如果只有四个方向可供选择择：向东（向东
19、（x）、向西（）、向西（-x）、向北（）、向北（y）、向南（）、向南（-y），分别记为规则，分别记为规则1、2、3、4。爬山算法爬山算法1.1.开始状态作为一个可能状态。开始状态作为一个可能状态。2.2.从一个可能状态，从一个可能状态，应用可用规则集生成所有新的可能状态集应用可用规则集生成所有新的可能状态集。3.3.对该状态集中每一状态：对该状态集中每一状态：（1 1）进行状态测试，检查其是否为目标：）进行状态测试，检查其是否为目标：（2 2）如果是目标则程序停止。）如果是目标则程序停止。（3 3）如果不是目标，计算该状态的好坏或者比较各状态的好坏。）如果不是目标，计算该状态的好坏或者比较各状
20、态的好坏。4.4.取状态集中最好状态，作为下一个可能状态取状态集中最好状态，作为下一个可能状态。5.5.回到第回到第2 2步。步。爬山算法缺点：有时到达某一状态后，尽管它不是目标状态，但在测试过爬山算法缺点：有时到达某一状态后，尽管它不是目标状态，但在测试过中又找不到比该状态更好的状态，如图中又找不到比该状态更好的状态，如图2-32-3。局部极大点（多峰时处于非主峰）：它比周围邻居状态都好，但不是目标。局部极大点（多峰时处于非主峰）：它比周围邻居状态都好，但不是目标。平顶：它与全部邻居状态都有同一个值。平顶：它与全部邻居状态都有同一个值。山脊：如果搜索方向与山脊的走向不一致，则有可能会停留在山
21、脊处。山脊：如果搜索方向与山脊的走向不一致，则有可能会停留在山脊处。所以，用不可撤回方式来求解登山问题，需要对状态测试函数进行选择：所以，用不可撤回方式来求解登山问题，需要对状态测试函数进行选择：这个函数应具有单极值，且这个极值对应目标状态值。这个函数应具有单极值，且这个极值对应目标状态值。图图2-3 2-3 爬山法的三种可能状态爬山法的三种可能状态 测测试试函函数数例例：以以8 8数数码码为为例例，统统计计“不不在在位位”将将牌牌个个数数（逐逐一一比比较较当当前前状状态态与与目目标标状状态态对对应应位位置置,有有差差异异的的将将牌牌总总个个数数），并并取取其负值作为状态描述的函数其负值作为状
22、态描述的函数.-W(n)-W(n)（n n为测试状态）为测试状态）基基于于该该定定义义，下下图图所所示示状状态态的的函函数数值值为为-4-4。显显然然，目目标标状状态态的的函数值为函数值为0 0。2 8 31 6 47 51 2 3457 6 81 2 38 47 6 52 8 31 6 47 51W=-42 8 31 47 6 52W=-3上上2 31 8 47 6 53W=-3上上 2 31 8 47 6 54W=-2左左1 2 3 8 47 6 55W=-1下下1 2 38 47 6 56W=0右右2 8 3 1 47 6 53W=-3左左 8 3 2 1 47 6 54W=-3上上8
23、3 2 1 47 6 55W=-3右右8 1 3 2 47 6 56W=-3下下8 1 3 2 47 6 57W=-3左左 1 3 8 2 47 6 58W=-2上上1 3 8 2 47 6 59W=-1右右1 2 38 47 6 510W=0下下图图2-4 2-4 八数码问题各状态的爬山函数值八数码问题各状态的爬山函数值 爬山法的策略爬山法的策略执行使新状态的测试函数值有最大增长的规则；执行使新状态的测试函数值有最大增长的规则；所有规则都不能使新状态的测试函数值增长时，所有规则都不能使新状态的测试函数值增长时，执行使测试函数值不减少的规则；执行使测试函数值不减少的规则；如果以上两种规则都不存
24、在，则过程停止。如果以上两种规则都不存在，则过程停止。2 2）试探方式）试探方式 试探方式分为两种：试探方式分为两种：回溯方式和图搜索方式回溯方式和图搜索方式。回溯方式：应用规则后遇到规定的情况时，返回到最回溯方式：应用规则后遇到规定的情况时，返回到最近的近的回溯点回溯点（无特殊规定时，最近的上一状态即是回（无特殊规定时，最近的上一状态即是回溯点），从那里改选另外一条可应用规则。溯点），从那里改选另外一条可应用规则。2 2）试探方式）试探方式 对八数码问题而言，在对八数码问题而言，在3 3种情况下应考虑回溯：种情况下应考虑回溯：新生成的状态在通向目标的路径上已经出现过；新生成的状态在通向目标的
25、路径上已经出现过；从初始状态开始，在应用了指定数目的规则后，仍没有找到从初始状态开始，在应用了指定数目的规则后，仍没有找到目标状态；目标状态；对当前状态，再没有可应用规则。对当前状态，再没有可应用规则。假如规定的搜索深度为假如规定的搜索深度为6 6层（表现为：应用了第层（表现为：应用了第6 6条规则之后得到条规则之后得到的状态仍然不是目标状态），回溯策略应用于八数码游戏时的一的状态仍然不是目标状态），回溯策略应用于八数码游戏时的一部分搜索图如图部分搜索图如图2-52-5所示所示2 8 31 6 47 51 1左、上、右左、上、右同状态同状态4 4，回溯到上，回溯到上一步，到状态一步，到状态5
26、52 22 8 31 6 4 7 5上、右上、右左左2 8 3 6 41 7 53 3上、右、下上、右、下上上 8 32 6 41 7 54 4右、下右、下上上8 32 6 41 7 55 5左、右、下左、右、下右右 8 32 6 41 7 56 6左左同状态同状态5 5，回溯到，回溯到上一步，到状态上一步，到状态6 68 32 6 41 7 57 7左左8 3 42 6 1 7 57 7下用了用了6 6条规则，未找条规则，未找到解，回溯到上一到解，回溯到上一步，到状态步，到状态 6 6状态状态6 6的所有规则的所有规则用完，回溯到上一用完，回溯到上一步，到状态步，到状态 5 58 3 2 6
27、 41 7 56 6左、下左、下右右8 6 3 2 41 7 57 7左左（1 1）（1 1）（2 2）（3 3）8 6 32 41 7 56 6左、上、右、下左、上、右、下下下（2 2）图图2-5 2-5 利用回溯策略的部分搜索图利用回溯策略的部分搜索图图图搜搜索索方方式式:对对任任一一状状态态，应应用用其其所所有有可可应应用用规规则则，并并把把状状态态变变化化过过程程用用图图结结构构记记录录下下来来，一一直直到到得得到到解解为为止止。图图搜搜索索策策略略求求解解问题是一种穷举方式。问题是一种穷举方式。图搜索方式下，求得一条解路径需要搜索问题的整个求解空间。图搜索方式下，求得一条解路径需要搜
28、索问题的整个求解空间。对于状态空间较大的问题，需要对于状态空间较大的问题，需要利用与问题有关的知识引导规则的选择利用与问题有关的知识引导规则的选择，以便在较窄的空间内找到问题的解。搜索过程中利用应用问题相关知识对以便在较窄的空间内找到问题的解。搜索过程中利用应用问题相关知识对规则进行选择的搜索，称为启发式图搜索。规则进行选择的搜索，称为启发式图搜索。图图2-6 2-6 八数码游戏的部分搜索树八数码游戏的部分搜索树 图图2-72-7是是5 5个个城城市市旅旅行行商商问问题题的的地地图图，求求从从A A出出发发经经B B、C C、D D、E E再再回回到到A A的的最最短短路路径。径。问问题题的的
29、表表示示：若若每每个个城城市市用用一一个个字字母母表表示示，则则综综合合数数据据库库可可用用字字母母组组成成的的表表或或字字符符串串来来表表示示，如如（A A）表表示示初初始始状状态态，（A*AA*A）表表示示目目标标状状态态，（A*A*）表表示示访问两个城市后的当前状态。访问两个城市后的当前状态。启发式图搜索例：启发式图搜索例：问题：旅行商问题。一个推销员要到几个城市办理业务，城市间里程数已知。问题：旅行商问题。一个推销员要到几个城市办理业务，城市间里程数已知。求：从某个城市出发，每个城市只允许访问一次，最后回到出发城市的最短求：从某个城市出发，每个城市只允许访问一次，最后回到出发城市的最短
30、距离环路。距离环路。图图2-7 2-7 旅行商问题的地图旅行商问题的地图 规规则则集集：1 1）下下一一步步走走向向城城市市A A；2 2）下下一一步步走走向向城城市市B B；，5 5）下下一一步步走走向城市向城市E E；问题的约束：问题的约束：不可以重复经过同一城市；不可以重复经过同一城市；在在没没有有转转完完所所有有城城市市时时，不不能能走走向向起起点城市点城市A A。引导策略：每次走向离得最近的城市引导策略：每次走向离得最近的城市。图图2-82-8表表示示求求解解该该问问题题时时，用用启启发发式式图图搜索控制方式生成的搜索树。搜索控制方式生成的搜索树。初态初态（A）B、C、D、E7106
31、13（AB）（AC）B、D、E（AD）（AE）10（ACDEB）A7（ACDEBA）目标目标图图2 2-8 8 用用启启发发式式图图搜搜索索生生成成的的搜搜索索树树5（ACD）B、E（ACB）（ACE）796（ACDE）BACDB10三种控制方式有不同的特点：三种控制方式有不同的特点：不可撤回方式沿着单独的一条路径延伸搜索；不可撤回方式沿着单独的一条路径延伸搜索；回溯方式保留部分搜索树结构，只记录当前工作的一条回溯方式保留部分搜索树结构，只记录当前工作的一条路径，回溯操作对当前工作路径进行修正；路径，回溯操作对当前工作路径进行修正；图搜索方式记录完整的搜索树。图搜索方式记录完整的搜索树。2.4
32、2.4 正向、逆向、双向产生式系统正向、逆向、双向产生式系统 正向产生式系统：应用正向产生式系统：应用F F规则求解问题。规则求解问题。F F规则：对规则的可应用性，基于事实描述进行判断。规则：对规则的可应用性，基于事实描述进行判断。逆向产生式系统：应用逆向产生式系统：应用B B规则求解问题。规则求解问题。B B规则：对规则的可应用性，基于目标描述进行判断。规则：对规则的可应用性，基于目标描述进行判断。双向产生式系统：以双向搜索的方式（正向和逆向同时双向产生式系统：以双向搜索的方式（正向和逆向同时进行）求解问题。此时，必须把事实描述和目标描述合进行）求解问题。此时，必须把事实描述和目标描述合并成综合数据库，并成综合数据库，F F规则只适用于事实描述部分，规则只适用于事实描述部分，B B规则规则适用于目标描述部分。适用于目标描述部分。