人工智能系統(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ī)則，用于描述各種知識單元間廣泛存在的因果關(guān)系，即前提和結(jié)論之間的關(guān)系。

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

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

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

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

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

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

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

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

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

?匹配。

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

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

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

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

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

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

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

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

–知識無序性與模塊化：知識的補充和修改非常容易。

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

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

基本算法如下

：

過程PRODUCTION1．DATA?

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

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

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

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

（執(zhí)行）

}上述過程是

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

2.2問題的表示

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

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

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

（SPLIT過程）

2.2.1狀態(tài)空間法

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

?一個合理的走步序列是問題的一個解。

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

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

表示，其中

且互不相等。

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

個狀態(tài)。

}{ijS}8,,1,0{,3,1????ijSji362880!9111213141516171819??????????CCCCCCCCC?2.規(guī)則集：移動一塊將牌（即走一步）就使狀態(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)，最后到達目標狀態(tài)。

?2.3控制策略分類

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

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

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

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

1）不可撤回方式：

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

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

?利用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開始重復(fù)這一過程，直到到達山頂。

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

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

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

爬山算法

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

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

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

（1）進行狀態(tài)測試，檢查其是否為目標：

（2）如果是目標則程序停止。

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

5.回到第2步。

爬山算法缺點：有時到達某一狀態(tài)后，盡管它不是目標狀態(tài)，但在測試過

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

⑴

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

⑵

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

⑶

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

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

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

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

基于該定義，下圖所示狀態(tài)的函數(shù)值為-4。顯然，目標狀態(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)的測試函數(shù)值有最大增長的規(guī)則；

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

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

2）試探方式

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

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

2）試探方式

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

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

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

–對當前狀態(tài)，再沒有可應(yīng)用規(guī)則。

?假如規(guī)定的搜索深度為6層（表現(xiàn)為：應(yīng)用了第6條規(guī)則之后得到的狀態(tài)仍然不是目標狀態(tài)），回溯策略應(yīng)用于八數(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利用回溯策略的部分搜索圖

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

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

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

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

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

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

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

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

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

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