人工智能系統(tǒng)的基本結(jié)構(gòu)

第二章

人工智能系統(tǒng)的基本結(jié)構(gòu)

?產(chǎn)生式系統(tǒng)（ProductionSystem），也稱作基于規(guī)則的系統(tǒng)，是人工智能系統(tǒng)中最典型、最普遍的結(jié)構(gòu)。

第二章

人工智能系統(tǒng)結(jié)構(gòu)

?2.1產(chǎn)生式系統(tǒng)概述

?2.2問題的表示

?2.3控制策略分類

?2.4產(chǎn)生式系統(tǒng)的類型

2.1產(chǎn)生式系統(tǒng)概述

?產(chǎn)生式，也稱作規(guī)則，或產(chǎn)生式規(guī)則，用于描述各種知識(shí)單元間廣泛存在的因果關(guān)系，即前提和結(jié)論之間的關(guān)系。

?在產(chǎn)生式系統(tǒng)中，待描述系統(tǒng)的知識(shí)被分為兩部分：

–事實(shí)：表示已知事實(shí)，如事物、事件及其之間關(guān)系，也可以看作是無前提條件的產(chǎn)生式。

–產(chǎn)生式規(guī)則：前提和結(jié)論之間的關(guān)系式，表示推理過程和行為。

2.1.1產(chǎn)生式系統(tǒng)的基本結(jié)構(gòu)

三個(gè)基本部分：綜合數(shù)據(jù)庫(kù)（事實(shí)庫(kù)）、規(guī)則庫(kù)（規(guī)則集）、控制器（規(guī)則解釋）。

1、綜合數(shù)據(jù)庫(kù)是產(chǎn)生式系統(tǒng)使用的主要數(shù)據(jù)結(jié)構(gòu)，存儲(chǔ)有關(guān)問題狀態(tài)、性質(zhì)等事實(shí)（敘述型知識(shí)），包括推理過程中形成的中間結(jié)論，對(duì)應(yīng)問題的表示信息。

2、規(guī)則庫(kù)是產(chǎn)生式規(guī)則的集合，存儲(chǔ)有關(guān)問題的狀態(tài)轉(zhuǎn)移、性質(zhì)變化等規(guī)則（過程型知識(shí)），規(guī)則形式:if條件then行動(dòng)

if前提t(yī)hen結(jié)論

如果某規(guī)則的前件能夠被事實(shí)庫(kù)中的事實(shí)滿足，則該規(guī)則被激活。3、控制器是規(guī)則的解釋程序或執(zhí)行程序，它規(guī)定選擇一條可用規(guī)則的原則和規(guī)則使用的方式(推理方向)，并根據(jù)綜合數(shù)據(jù)庫(kù)的信息，控制求解問題的過程（控制策略,推理引擎）。通常從選擇規(guī)則到執(zhí)行操作分三步：

?匹配。

–判斷規(guī)則的前件是否成立?–可能有多條規(guī)則的前件能夠與綜合數(shù)據(jù)庫(kù)中的事實(shí)匹配!?沖突解決，選擇可調(diào)用的規(guī)則。

–從匹配滿足的規(guī)則集中選擇一條規(guī)則。

?執(zhí)行規(guī)則，并在滿足結(jié)束條件時(shí)終止產(chǎn)生式系統(tǒng)的運(yùn)行。

–如果規(guī)則的后件是結(jié)論，把該結(jié)論加入綜合數(shù)據(jù)庫(kù)；

–如果規(guī)則的后件是動(dòng)作，執(zhí)行該動(dòng)作；

4、產(chǎn)生式系統(tǒng)的特點(diǎn)：

–數(shù)據(jù)、知識(shí)和控制相互獨(dú)立。

–知識(shí)具有相對(duì)固定的格式：均由左、右兩部分組成。

–知識(shí)無序性與模塊化：知識(shí)的補(bǔ)充和修改非常容易。

–控制系統(tǒng)與問題無關(guān)。

2.1.2產(chǎn)生式系統(tǒng)的基本過程

基本算法如下

：

過程PRODUCTION1．DATA?

初始數(shù)據(jù)庫(kù)

2．UntilDATA滿足結(jié)束條件(匹配）之前,do:{3．從規(guī)則集中選一條可應(yīng)用于DATA的規(guī)則R（選擇）

4．綜合數(shù)據(jù)庫(kù)

?R應(yīng)用到DATA得到結(jié)果

（執(zhí)行）

}上述過程是

“匹配、選擇、執(zhí)行”的循環(huán)過程。

2.2問題的表示

?用產(chǎn)生式系統(tǒng)求解問題，就是把一個(gè)問題的描述轉(zhuǎn)化成產(chǎn)生式系統(tǒng)的三個(gè)部分。其中問題的表示（即綜合數(shù)據(jù)庫(kù)和規(guī)則集的描述）對(duì)問題的求解有很大的影響。

–狀態(tài)空間法。所求問題的已知事實(shí)及中間結(jié)論，稱為狀態(tài)。狀態(tài)的集合及狀態(tài)間的轉(zhuǎn)移規(guī)則構(gòu)成問題的表示。基于這種表示的問題求解稱為狀態(tài)空間法。求解過程是，通過對(duì)可能的狀態(tài)空間的搜索求得一個(gè)解。（PRODUCTION過程）

–問題歸約法。待求問題分解為一些較為簡(jiǎn)單的子問題，且子問題也可以分解，所以可得到若干子問題。包含問題、子問題的集合與問題分解的規(guī)則一起構(gòu)成問題的表示。基于這種表示的問題求解稱為問題歸約法。求解過程是，通過對(duì)各個(gè)子問題解答的搜索求得原問題的解答。

（SPLIT過程）

2.2.1狀態(tài)空間法

?狀態(tài)空間可用三元組（S，O，G）來描述

–S是狀態(tài)集合。狀態(tài)是表示某種事實(shí)的符號(hào)或數(shù)據(jù)。問題的狀態(tài)可以用任何類型的數(shù)據(jù)結(jié)構(gòu)描述。起始狀態(tài)S0是S的一個(gè)非空子集，描述問題的初始狀態(tài)。

–G是目標(biāo)狀態(tài)。G是S的一個(gè)非空子集，它可以是一個(gè)或多個(gè)要達(dá)到的狀態(tài)，也可以是對(duì)某些狀態(tài)性質(zhì)的描述。

–O是規(guī)則集合。集合中的每個(gè)元素稱作操作算子，將一個(gè)狀態(tài)轉(zhuǎn)化為另一個(gè)狀態(tài)。

?問題求解：從S0出發(fā)，經(jīng)過一系列操作變換達(dá)到G，

即狀態(tài)空間搜索問題。狀態(tài)空間的一個(gè)解是一個(gè)有限的規(guī)則序列，

即為狀態(tài)空間的一個(gè)解，解不一定唯一。

GSSSkOOO??????????21021kOO,,1?2.2.2問題歸約法

?問題歸約法也可用一個(gè)三元組（S0，O，P）來描述

–S0是初始問題，即要求解的問題；

–P是本原問題集，其中的每一個(gè)問題是自然成立的，不需證明的；

–O是操作算子集，一個(gè)操作算子可把一個(gè)問題化成若干個(gè)子問題。

?該方法由問題出發(fā)，運(yùn)用操作算子產(chǎn)生一些子問題，對(duì)子問題再運(yùn)用操作算子產(chǎn)生子問題的子問題，一直進(jìn)行到產(chǎn)生的問題均為本原問題，則問題得解。問題歸約的最終目的是產(chǎn)生本原問題。

?問題歸約法是比狀態(tài)空間法更一般的問題求解方法，如果在歸約法中，每運(yùn)用一次操作算子，只產(chǎn)生一個(gè)子問題，則就是狀態(tài)空間法。

2.2.3產(chǎn)生式系統(tǒng)舉例

圖2-1八數(shù)碼游戲

?問題描述：給定一種初始布局（初始狀態(tài)）和一個(gè)目標(biāo)的布局（目標(biāo)狀態(tài)），問如何移動(dòng)將牌，實(shí)現(xiàn)從初始狀態(tài)到目標(biāo)狀態(tài)的轉(zhuǎn)變。

?一個(gè)合理的走步序列是問題的一個(gè)解。

2834571612345678?1．綜合數(shù)據(jù)庫(kù)：選擇一種數(shù)據(jù)結(jié)構(gòu)表示將牌布局。

?本例選用二維數(shù)組來表示布局較直觀，其數(shù)組元素用

表示，其中

且互不相等。

?這樣每個(gè)具體取值矩陣就代表了一個(gè)棋局狀態(tài)。顯然，該問題有

個(gè)狀態(tài)。

}{ijS}8,,1,0{,3,1????ijSji362880!9111213141516171819??????????CCCCCCCCC?2.規(guī)則集：移動(dòng)一塊將牌（即走一步）就使?fàn)顟B(tài)發(fā)生一次轉(zhuǎn)變。有四種走法：空格左移、空格上移、空格右移、空格下移。

記數(shù)組第i行第j列的元素為

空格所在的行、列分別記為

，則

則空格左移一格、空格上移一格、空格右移一格、空格下移一格可用如下4條規(guī)則來描述：

ijS1ij3,,??00,ji000?jiS?規(guī)則1:（空格左移一格）

?規(guī)則2:（空格上移一格）

?規(guī)則3:（空格右移一格）

?規(guī)則4:（空格下移一格）

0000000ijij1ij1ifj2thenSSS0()(),;?????0000000iji1ji1jifi2thenSSS0()(),;?????0000000ijij1ij1ifj2thenSSS0()(),;?????0000000iji1ji1jifi2thenSSS0()(),;??????3.控制策略：從規(guī)則集中選擇規(guī)則并作用于狀態(tài)的一種廣義選取函數(shù)。

確定某一策略后，可以用算法的形式給出程序。使用該策略從初始狀態(tài)出發(fā)，通過不斷尋求滿足一定條件的問題狀態(tài)，最后到達(dá)目標(biāo)狀態(tài)。

?2.3控制策略分類

?對(duì)當(dāng)前的狀態(tài)，只要某一條規(guī)則作用之后能生成合法的新狀態(tài)，那么，這條規(guī)則就是可用規(guī)則。

?產(chǎn)生式系統(tǒng)的運(yùn)行表現(xiàn)出一種搜索過程，在每一個(gè)循環(huán)中選一條規(guī)則試用，直到找到某一個(gè)序列能產(chǎn)生滿足結(jié)束條件的狀態(tài)為止。

?不同的控制策略產(chǎn)生不同的解，高效率的控制策略能夠走較少的步驟達(dá)到目標(biāo)，但需要問題求解的足夠知識(shí)。

?控制策略分為兩類：不可撤回方式（Irrevocable）和試探方式（Tentative）。

1）不可撤回方式：

?思想:利用問題給出的局部知識(shí)決定如何選取規(guī)則，已用過的規(guī)則不能撤回。優(yōu)點(diǎn)是控制簡(jiǎn)單。

?例：爬山問題。登山過程中，登山人的目標(biāo)是爬上峰頂，如何一步一步地向目標(biāo)前進(jìn)就是一個(gè)策略問題。通常，人們利用高度隨位置變化的函數(shù)H(P)來引導(dǎo)爬山，這是一種不可撤回方式。

?利用H(P)可以計(jì)算朝不同方向邁出一步后高度的變化情況。即

–向東：△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變化最大的那一步攀登，到達(dá)新的位置P；從P開始重復(fù)這一過程，直到到達(dá)山頂。

ZYXP0(x0,y0,z0)y0x0z0圖2-2爬山過程示意圖

?假設(shè)登山人當(dāng)前所處的位置為P0，如果只有四個(gè)方向可供選擇

：[向東（△x）、向西（-△x）、向北（△y）、向南（-△y）]，分別記為規(guī)則1、2、3、4。

爬山算法

1.開始狀態(tài)作為一個(gè)可能狀態(tài)。

2.從一個(gè)可能狀態(tài)，應(yīng)用可用規(guī)則集生成所有新的可能狀態(tài)集。

3.對(duì)該狀態(tài)集中每一狀態(tài)：

（1）進(jìn)行狀態(tài)測(cè)試，檢查其是否為目標(biāo)：

（2）如果是目標(biāo)則程序停止。

（3）如果不是目標(biāo)，計(jì)算該狀態(tài)的好壞或者比較各狀態(tài)的好壞。4.取狀態(tài)集中最好狀態(tài)，作為下一個(gè)可能狀態(tài)。

5.回到第2步。

爬山算法缺點(diǎn)：有時(shí)到達(dá)某一狀態(tài)后，盡管它不是目標(biāo)狀態(tài)，但在測(cè)試過

中又找不到比該狀態(tài)更好的狀態(tài)，如圖2-3。

⑴

局部極大點(diǎn)（多峰時(shí)處于非主峰）：它比周圍鄰居狀態(tài)都好，但不是目標(biāo)。

⑵

平頂：它與全部鄰居狀態(tài)都有同一個(gè)值。

⑶

山脊：如果搜索方向與山脊的走向不一致，則有可能會(huì)停留在山脊處。

所以，用不可撤回方式來求解登山問題，需要對(duì)狀態(tài)測(cè)試函數(shù)進(jìn)行選擇：這個(gè)函數(shù)應(yīng)具有單極值，且這個(gè)極值對(duì)應(yīng)目標(biāo)狀態(tài)值。

圖2-3爬山法的三種可能狀態(tài)

?測(cè)試函數(shù)例：以8數(shù)碼為例，統(tǒng)計(jì)“不在位”將牌個(gè)數(shù)（逐一比較當(dāng)前狀態(tài)與目標(biāo)狀態(tài)對(duì)應(yīng)位置,有差異的將牌總個(gè)數(shù)），并取其負(fù)值作為狀態(tài)描述的函數(shù).-W(n)（n為測(cè)試狀態(tài)）

基于該定義，下圖所示狀態(tài)的函數(shù)值為-4。顯然，目標(biāo)狀態(tài)的函數(shù)值為0。

283164751234576

812384765283164751W=-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八數(shù)碼問題各狀態(tài)的爬山函數(shù)值

?爬山法的策略

–執(zhí)行使新狀態(tài)的測(cè)試函數(shù)值有最大增長(zhǎng)的規(guī)則；

–所有規(guī)則都不能使新狀態(tài)的測(cè)試函數(shù)值增長(zhǎng)時(shí)，執(zhí)行使測(cè)試函數(shù)值不減少的規(guī)則；

–如果以上兩種規(guī)則都不存在，則過程停止。

2）試探方式

?試探方式分為兩種：回溯方式和圖搜索方式。

?回溯方式：應(yīng)用規(guī)則后遇到規(guī)定的情況時(shí)，返回到最近的回溯點(diǎn)（無特殊規(guī)定時(shí)，最近的上一狀態(tài)即是回溯點(diǎn)），從那里改選另外一條可應(yīng)用規(guī)則。

2）試探方式

?對(duì)八數(shù)碼問題而言，在3種情況下應(yīng)考慮回溯：

–新生成的狀態(tài)在通向目標(biāo)的路徑上已經(jīng)出現(xiàn)過；

–從初始狀態(tài)開始，在應(yīng)用了指定數(shù)目的規(guī)則后，仍沒有找到目標(biāo)狀態(tài)；

–對(duì)當(dāng)前狀態(tài)，再?zèng)]有可應(yīng)用規(guī)則。

?假如規(guī)定的搜索深度為6層（表現(xiàn)為：應(yīng)用了第6條規(guī)則之后得到的狀態(tài)仍然不是目標(biāo)狀態(tài)），回溯策略應(yīng)用于八數(shù)碼游戲時(shí)的一部分搜索圖如圖2-5所示

283164751左、上、右

同狀態(tài)4，回溯到上一步，到狀態(tài)5228316475上、右

左

283641753上、右、下

上

832641754右、下

上

832641755左、右、下

右

832641756左

同狀態(tài)5，回溯到上一步，到狀態(tài)6832641757左

834261757下

用了6條規(guī)則，未找

到解，回溯到上一步，到狀態(tài)6狀態(tài)6的所有規(guī)則

用完，回溯到上一步，到狀態(tài)5832641756左、下

右

863241757左

（1）

（1）

（2）

（3）

863241756左、上、右、下下

（2）

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

?圖搜索方式:對(duì)任一狀態(tài)，應(yīng)用其所有可應(yīng)用規(guī)則，并把狀態(tài)變化過程用圖結(jié)構(gòu)記錄下來，一直到得到解為止。圖搜索策略求解問題是一種窮舉方式。

?圖搜索方式下，求得一條解路徑需要搜索問題的整個(gè)求解空間。

–對(duì)于狀態(tài)空間較大的問題，需要利用與問題有關(guān)的知識(shí)引導(dǎo)規(guī)則的選擇，以便在較窄的空間內(nèi)找到問題的解。搜索過程中利用應(yīng)用問題相關(guān)知識(shí)對(duì)規(guī)則進(jìn)行選擇的搜索，稱為啟發(fā)式圖搜索。

圖2-6八數(shù)碼游戲的部分搜索樹

?圖2-7是5個(gè)城市旅行商問題的地圖，

求從A出發(fā)經(jīng)B、C、D、E再回到A的最短路徑。

?問題的表示：若每個(gè)城市用一個(gè)字母表示，則綜合數(shù)據(jù)庫(kù)可用字母組成的表或字符串來表示，如（A）表示初始狀態(tài)，（A****A）表示目標(biāo)狀態(tài)，（A**）表示訪問兩個(gè)城市后的當(dāng)前狀態(tài)。

77101013965610BADEC啟發(fā)式圖搜索例：

問題：旅行商問題。一個(gè)推銷員要到幾個(gè)城市辦理業(yè)務(wù)，城市間里程數(shù)已知。

求：從某個(gè)城市出發(fā)，每個(gè)城市只允許