人工智能系统的基本结构

第二章

人工智能系统的基本结构

?产生式系统（ProductionSystem），也称作基于规则的系统，是人工智能系统中最典型、最普遍的结构。

人工智能系统的基本结构全文共31页，当前为第1页。第二章

人工智能系统结构

?2.1产生式系统概述

?2.2问题的表示

?2.3控制策略分类

?2.4产生式系统的类型

人工智能系统的基本结构全文共31页，当前为第2页。2.1产生式系统概述

?产生式，也称作规则，或产生式规则，用于描述各种知识单元间广泛存在的因果关系，即前提和结论之间的关系。

?在产生式系统中，待描述系统的知识被分为两部分：

–事实：表示已知事实，如事物、事件及其之间关系，也可以看作是无前提条件的产生式。

–产生式规则：前提和结论之间的关系式，表示推理过程和行为。

人工智能系统的基本结构全文共31页，当前为第3页。2.1.1产生式系统的基本结构

三个基本部分：综合数据库（事实库）、规则库（规则集）、控制器（规则解释）。

1、综合数据库是产生式系统使用的主要数据结构，存储有关问题状态、性质等事实（叙述型知识），包括推理过程中形成的中间结论，对应问题的表示信息。

2、规则库是产生式规则的集合，存储有关问题的状态转移、性质变化等规则（过程型知识），规则形式:if条件then行动

if前提then结论

如果某规则的前件能够被事实库中的事实满足，则该规则被激活。人工智能系统的基本结构全文共31页，当前为第4页。3、控制器是规则的解释程序或执行程序，它规定选择一条可用规则的原则和规则使用的方式(推理方向)，并根据综合数据库的信息，控制求解问题的过程（控制策略,推理引擎）。通常从选择规则到执行操作分三步：

?匹配。

–判断规则的前件是否成立?–可能有多条规则的前件能够与综合数据库中的事实匹配!?冲突解决，选择可调用的规则。

–从匹配满足的规则集中选择一条规则。

?执行规则，并在满足结束条件时终止产生式系统的运行。

–如果规则的后件是结论，把该结论加入综合数据库；

–如果规则的后件是动作，执行该动作；

人工智能系统的基本结构全文共31页，当前为第5页。4、产生式系统的特点：

–数据、知识和控制相互独立。

–知识具有相对固定的格式：均由左、右两部分组成。

–知识无序性与模块化：知识的补充和修改非常容易。

–控制系统与问题无关。

人工智能系统的基本结构全文共31页，当前为第6页。2.1.2产生式系统的基本过程

基本算法如下

：

过程PRODUCTION1．DATA?

初始数据库

2．UntilDATA满足结束条件(匹配）之前,do:{3．从规则集中选一条可应用于DATA的规则R（选择）

4．综合数据库

?R应用到DATA得到结果

（执行）

}上述过程是

“匹配、选择、执行”的循环过程。

人工智能系统的基本结构全文共31页，当前为第7页。2.2问题的表示

?用产生式系统求解问题，就是把一个问题的描述转化成产生式系统的三个部分。其中问题的表示（即综合数据库和规则集的描述）对问题的求解有很大的影响。

–状态空间法。所求问题的已知事实及中间结论，称为状态。状态的集合及状态间的转移规则构成问题的表示。基于这种表示的问题求解称为状态空间法。求解过程是，通过对可能的状态空间的搜索求得一个解。（PRODUCTION过程）

–问题归约法。待求问题分解为一些较为简单的子问题，且子问题也可以分解，所以可得到若干子问题。包含问题、子问题的集合与问题分解的规则一起构成问题的表示。基于这种表示的问题求解称为问题归约法。求解过程是，通过对各个子问题解答的搜索求得原问题的解答。

（SPLIT过程）

人工智能系统的基本结构全文共31页，当前为第8页。2.2.1状态空间法

?状态空间可用三元组（S，O，G）来描述

–S是状态集合。状态是表示某种事实的符号或数据。问题的状态可以用任何类型的数据结构描述。起始状态S0是S的一个非空子集，描述问题的初始状态。

–G是目标状态。G是S的一个非空子集，它可以是一个或多个要达到的状态，也可以是对某些状态性质的描述。

–O是规则集合。集合中的每个元素称作操作算子，将一个状态转化为另一个状态。

?问题求解：从S0出发，经过一系列操作变换达到G，

即状态空间搜索问题。状态空间的一个解是一个有限的规则序列，

即为状态空间的一个解，解不一定唯一。

GSSSkOOO??????????21021kOO,,1?人工智能系统的基本结构全文共31页，当前为第9页。2.2.2问题归约法

?问题归约法也可用一个三元组（S0，O，P）来描述

–S0是初始问题，即要求解的问题；

–P是本原问题集，其中的每一个问题是自然成立的，不需证明的；

–O是操作算子集，一个操作算子可把一个问题化成若干个子问题。

?该方法由问题出发，运用操作算子产生一些子问题，对子问题再运用操作算子产生子问题的子问题，一直进行到产生的问题均为本原问题，则问题得解。问题归约的最终目的是产生本原问题。

?问题归约法是比状态空间法更一般的问题求解方法，如果在归约法中，每运用一次操作算子，只产生一个子问题，则就是状态空间法。

人工智能系统的基本结构全文共31页，当前为第10页。2.2.3产生式系统举例

图2-1八数码游戏

?问题描述：给定一种初始布局（初始状态）和一个目标的布局（目标状态），问如何移动将牌，实现从初始状态到目标状态的转变。

?一个合理的走步序列是问题的一个解。

2834571612345678人工智能系统的基本结构全文共31页，当前为第11页。?1．综合数据库：选择一种数据结构表示将牌布局。

?本例选用二维数组来表示布局较直观，其数组元素用

表示，其中

且互不相等。

?这样每个具体取值矩阵就代表了一个棋局状态。显然，该问题有

个状态。

}{ijS}8,,1,0{,3,1????ijSji362880!9111213141516171819??????????CCCCCCCCC人工智能系统的基本结构全文共31页，当前为第12页。?2.规则集：移动一块将牌（即走一步）就使状态发生一次转变。有四种走法：空格左移、空格上移、空格右移、空格下移。

记数组第i行第j列的元素为

空格所在的行、列分别记为

，则

则空格左移一格、空格上移一格、空格右移一格、空格下移一格可用如下4条规则来描述：

ijS1ij3,,??00,ji000?jiS人工智能系统的基本结构全文共31页，当前为第13页。?规则1:（空格左移一格）

?规则2:（空格上移一格）

?规则3:（空格右移一格）

?规则4:（空格下移一格）

0000000ijij1ij1ifj2thenSSS0()(),;?????0000000iji1ji1jifi2thenSSS0()(),;?????0000000ijij1ij1ifj2thenSSS0()(),;?????0000000iji1ji1jifi2thenSSS0()(),;?????人工智能系统的基本结构全文共31页，当前为第14页。?3.控制策略：从规则集中选择规则并作用于状态的一种广义选取函数。

确定某一策略后，可以用算法的形式给出程序。使用该策略从初始状态出发，通过不断寻求满足一定条件的问题状态，最后到达目标状态。

人工智能系统的基本结构全文共31页，当前为第15页。?2.3控制策略分类

?对当前的状态，只要某一条规则作用之后能生成合法的新状态，那么，这条规则就是可用规则。

?产生式系统的运行表现出一种搜索过程，在每一个循环中选一条规则试用，直到找到某一个序列能产生满足结束条件的状态为止。

?不同的控制策略产生不同的解，高效率的控制策略能够走较少的步骤达到目标，但需要问题求解的足够知识。

?控制策略分为两类：不可撤回方式（Irrevocable）和试探方式（Tentative）。

人工智能系统的基本结构全文共31页，当前为第16页。1）不可撤回方式：

?思想:利用问题给出的局部知识决定如何选取规则，已用过的规则不能撤回。优点是控制简单。

?例：爬山问题。登山过程中，登山人的目标是爬上峰顶，如何一步一步地向目标前进就是一个策略问题。通常，人们利用高度随位置变化的函数H(P)来引导爬山，这是一种不可撤回方式。

人工智能系统的基本结构全文共31页，当前为第17页。?利用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开始重复这一过程，直到到达山顶。

ZYXP0(x0,y0,z0)y0x0z0图2-2爬山过程示意图

?假设登山人当前所处的位置为P0，如果只有四个方向可供选择

：[向东（△x）、向西（-△x）、向北（△y）、向南（-△y）]，分别记为规则1、2、3、4。

人工智能系统的基本结构全文共31页，当前为第18页。

爬山算法

1.开始状态作为一个可能状态。

2.从一个可能状态，应用可用规则集生成所有新的可能状态集。

3.对该状态集中每一状态：

（1）进行状态测试，检查其是否为目标：

（2）如果是目标则程序停止。

（3）如果不是目标，计算该状态的好坏或者比较各状态的好坏。4.取状态集中最好状态，作为下一个可能状态。

5.回到第2步。

人工智能系统的基本结构全文共31页，当前为第19页。

爬山算法缺点：有时到达某一状态后，尽管它不是目标状态，但在测试过

中又找不到比该状态更好的状态，如图2-3。

⑴

局部极大点（多峰时处于非主峰）：它比周围邻居状态都好，但不是目标。

⑵

平顶：它与全部邻居状态都有同一个值。

⑶

山脊：如果搜索方向与山脊的走向不一致，则有可能会停留在山脊处。

所以，用不可撤回方式来求解登山问题，需要对状态测试函数进行选择：这个函数应具有单极值，且这个极值对应目标状态值。

图2-3爬山法的三种可能状态

人工智能系统的基本结构全文共31页，当前为第20页。?测试函数例：以8数码为例，统计“不在位”将牌个数（逐一比较当前状态与目标状态对应位置,有差异的将牌总个数），并取其负值作为状态描述的函数.-W(n)（n为测试状态）

基于该定义，下图所示状态的函数值为-4。显然，目标状态的函数值为0。

283164751234576

8人工智能系统的基本结构全文共31页，当前为第21页。12384765283164751W=-4283147652W=-3上

231847653W=-3上

231847654W=-2左

123847655W=-1下

123847656W=0右

283147653W=-3左

832147654W=-3上

832147655W=-3右

813247656W=-3下

813247657W=-3左

138247658W=-2上

138247659W=-1右

1238476510W=0下

图2-4八数码问题各状态的爬山函数值

人工智能系统的基本结构全文共31页，当前为第22页。

?爬山法的策略

–执行使新状态的测试函数值有最大增长的规则；

–所有规则都不能使新状态的测试函数值增长时，执行使测试函数值不减少的规则；

–如果以上两种规则都不存在，则过程停止。

人工智能系统的基本结构全文共31页，当前为第23页。2）试探方式

?试探方式分为两种：回溯方式和图搜索方式。

?回溯方式：应用规则后遇到规定的情况时，返回到最近的回溯点（无特殊规定时，最近的上一状态即是回溯点），从那里改选另外一条可应用规则。

人工智能系统的基本结构全文共31页，当前为第24页。2）试探方式

?对八数码问题而言，在3种情况下应考虑回溯：

–新生成的状态在通向目标的路径上已经出现过；

–从初始状态开始，在应用了指定数目的规则后，仍没有找到目标状态；

–对当前状态，再没有可应用规则。

?假如规定的搜索深度为6层（表现为：应用了第6条规则之后得到的状态仍然不是目标状态），回溯策略应用于八数码游戏时的一部分搜索图如图2-5所示

人工智能系统的基本结构全文共31页，当前为第25页。283164751左、上、右

同状态4，回溯到上一步，到状态5228316475上、右

左

283641753上、右、下

上

832641754右、下

上

832641755左、右、下

右

832641756左

同状态5，回溯到上一步，到状态6832641757左

834261757下

用了6条规则，未找

到解，回溯到上一步，到状态6状态6的所有规则

用完，回溯到上一步，到状态5832641756左、下

右

863241757左

（1）

（1）

（2）

（3）

863241756左、上、右、下下

（2）

图2-5利用回溯策略的部分搜索图

人工智能系统的基本结构全文共31页，当前为第26页。?图搜索方式:对任一状态，应用其所有可应用规则，并把状态变化过程用图结构记录下来，一直到得到解为止。图搜索策略求解问题是一种穷举方式。

?图搜索方式下，求得一条解路径需要搜索问题的整个求解空间。

–对于状态空间较大的问题，需要利用与问题有关的知识引导规则的选择，以便在较窄的空间内找到问题的解。搜索过程中利用应用问题相关知识对规则进行选择的搜索，称为启发式图搜索。

图2-6八数码游戏的部分搜索树

人工智能系统的基本结构全文共31页，当前为第27页。?图2-7是5个城市旅行商问题的地图，

求从A出发经B、C、D、E再回到A的最短路径。

?问题的表示：若每个城市用一个字母表示，则综合数据库可用字母组成的表或字符串来表示，如（A）表示初始状态，（A****A）表示目标状态，（A**）表示访问两个城市后的当前状态。

77101013965610BADEC启发式图搜索例：

问题：旅行商问题。一个推销员要到几个城市办理业务，城市间里程数已知。

求：从某个城市出发，每个城市只允许访问一次，最后回到出发城市的最短距离环路。

图2