产生式系统课件

產生式系統

5.1產生式規則5.1.1產生式規則產生式(Production)一詞，首先是由美國數學家波斯特（E.Post）提出來的。波斯特根據替換規則提出了一種稱為波斯特機的計算模型，模型中的每一條規則當時被稱為一個產生式。後來，這一術語幾經修改擴充，被用到許多領域。例如，形式語言中的文法規則就稱為產生式。產生式也稱為產生式規則，或簡稱規則。

產生式的一般形式為前件→後件其中，前件就是前提，後件是結論或動作，前件和後件可以是由邏輯運算符AND、OR、NOT組成的運算式。產生式規則的語義是:如果前提滿足，則可得結論或者執行相應的動作,即後件由前件來觸發。所以，前件是規則的執行條件，後件是規則體。

例如，下麵就是幾個產生式規則：

(1)如果銀行存款利率下調，那麼股票價格上漲。

(2)如果爐溫超過上限，則立即關閉風門。

(3)如果鍵盤突然失靈，且螢幕上出現怪字元，則是病毒發作。

(4)如果膠捲感光度為200，光線條件為晴天，目標距離不超過5米，則快門速度取250，光圈大小取f16。5.1.2基於產生式的推理模式由產生式的涵義可知，利用產生式規則可以實現有前提條件的指令性操作，也可以實現邏輯推理。實現操作的方法是當測試到一條規則的前提條件滿足時，就執行其後部的動作。這稱為規則被觸發或點燃。利用產生式規則實現邏輯推理的方法是當有事實能與某規則的前提匹配（即規則的前提成立）時，就得到該規則後部的結論（即結論也成立）。

實際上，這種基於產生式規則的邏輯推理模式，就是邏輯上所說的假言推理（對常量規則而言）和三段論推理（對變數規則而言），即：

A→BAB

這裏的大前提就是一個產生式規則，小前提就是證據事實。

5.2產生式系統

5.2.1產生式系統的組成產生式系統由三部分組成：產生式規則庫、推理機和動態資料庫，其結構如圖5--1所示。圖5—1產生式系統結構產品式規則庫推理機動態資料庫

產生式規則庫亦稱產生式規則集，由領域規則組成，在機器中以某種動態數據結構進行組織。推理機亦稱控制執行機構，它是一個程式模組，負責產生式規則的前提條件測試或匹配，規則的調度與選取，規則體的解釋和執行。即推理機實施推理，並對推理進行控制，它也就是規則的解釋程式。5.2.2產生式系統的運行過程產生式系統運行時，除了需要規則庫以外，還需要有初始事實(或數據)和目標條件。

目標條件是系統正常結束的條件，也是系統的求解目標。產生式系統啟動後，推理機就開始推理，按所給的目標進行問題求解。推理機的一次推理過程，可如圖5—2所示。一個實際的產生式系統，其目標條件一般不會只經一步推理就可滿足，往往要經過多步推理才能滿足或者證明問題無解。圖5—2推理機的一次推理過程從規則庫中取一個條規則，將其前提同當前動態資料庫中的事實/數據進行模式匹配匹配成功否把該規則的結論放入當前動態資料庫：或執行規則所規定的動作NY5.2.3控制策略與常用演算法產生式系統的推理可分為正向推理和反向推理兩種基本方式。下麵我們給出產生式系統正向推理和反向推理的常用演算法：

1.正向推理正向推理演算法一：步1將初始事實/數據置入動態資料庫；步2用動態資料庫中的事實/數據，匹配/測試目標條件，若目標條件滿足，則推理成功，結束。

步3用規則庫中各規則的前提匹配動態資料庫中的事實/數據，將匹配成功的規則組成待用規則集；步4若待用規則集為空，則運行失敗，退出。步5將待用規則集中各規則的結論加入動態資料庫，或者執行其動作，轉步2；可以看出，隨著推理的進行，動態資料庫的內容或者狀態在不斷變化。圖5—3正向推理的動態資料庫動態資料庫推理

例5.1動物分類問題的產生式系統描述及其求解。設由下列動物識別規則組成一個規則庫，推理機採用上述正向推理演算法，建立一個產生式系統。該產生式系統就是一個小型動物分類知識庫系統。規則：

r1：若某動物有奶，則它是哺乳動物。

r2：若某動物有毛髮，則它是哺乳動物。

r3：若某動物有羽毛，則它是鳥。

r4：若某動物會飛且生蛋，則它是鳥。

r5：若某動物是哺乳動物且有爪且有犬齒且目盯前方，則它是食肉動物。

r6：若某動物是哺乳動物且吃肉，則它是食肉動物。

r7：若某動物是哺乳動物且有蹄，則它是有蹄動物。

r8：若某動物是有蹄動物且反芻食物，則它是偶蹄動物。

r9：若某動物是食肉動物且黃褐色且有黑色條紋，則它是老虎。

r10：若某動物是食肉動物且黃褐色且有黑色斑點，則它是金錢豹。

r11：若某動物是有蹄動物且長腿且長脖子且黃褐色且有暗斑點，則它是長頸鹿。r12：若某動物是有蹄動物且白色且有黑色條紋，則它是斑馬。

r13：若某動物是鳥且不會飛且長腿且長脖子且黑白色，則它是駝鳥。

r14：若某動物是鳥且不會飛且會游泳且黑白色，則它是企鵝。

r15：若某動物是鳥且善飛且不怕風浪，則它是海燕。再給出初始事實：f1：某動物有毛髮。f2：吃肉。f3：黃褐色。f4：有黑色條紋。目標條件為：該動物是什麼？易見，該系統的運行結果為：該動物是老虎。其推理樹如圖5—4所示。圖5—4動物分類正向推理樹老虎食肉動物哺乳動物有毛髮吃肉黃褐色有黑色條紋2.反向推理步1將初始事實/數據置入動態資料庫，將目標條件置入目標鏈；步2若目標鏈為空，則推理成功，結束。步3取出目標鏈中第一個目標，用動態資料庫中的事實/數據同其匹配，若匹配成功，轉步2；

步4用規則集中的各規則的結論同該目標匹配，若匹配成功，則將第一個匹配成功且未用過的規則的前提作為新的目標，並取代原來的父目標而加入目標鏈，轉步3；步5若該目標是初始目標，則推理失敗，退出。步6將該目標的父目標移回目標鏈，取代該目標及其兄弟目標，轉步3；可以看出，上述反向推理演算法的推理過程也是一個圖搜索過程，而且一般是一個與或樹搜索。

例5.2對於例5.1中的產生式系統，改為反向推理演算法，則得到圖5—5所示的推理樹。圖5—5動物分類反向推理樹

可以看出，與正向推理不同，這次的推理樹是從上而下擴展而成的，而且推理過程中還發生過回溯。反向推理也稱為後向推理、反向鏈、目標驅動的推理等。從上面的兩個演算法可以看出，正向推理是自底向上的綜合過程，而反向推理則是自頂向下的分析過程。除了正向推理和反向推理外，產生式系統還可進行雙向推理。雙向推理就是同時從初始數據和目標條件出發進行推理，如果在中間某處相遇，則推理搜索成功。3.衝突消解策略上述正向推理演算法中，對所有匹配成功的規則都同時觸發啟用。所以，它實現的搜索是窮舉式的樹式盲目搜索。下麵我們給出一個正向推理的啟發式線式搜索演算法。正向推理演算法二：步1將初始事實/數據置入動態資料庫；步2用動態資料庫中的事實/數據，匹配/測試目標條件，若目標條件滿足，則推理成功，結束。

步3用規則庫中各規則的前提匹配動態資料庫中的事實/數據，將匹配成功的規則組成待用規則集；步4若待用規則集為空，則運行失敗，退出。步5用某種策略，從待用規則集中選取一條規則，將其結論加入動態資料庫，或者執行其動作，撤銷待用規則集，轉步2；可以看出，該演算法與前面的演算法僅在步5有所差別。5.3產生式系統與圖搜索

分析前面給出的兩個正向推理演算法，可以看出，它們只能用於解決邏輯推理性問題。

(1)記錄動態資料庫狀態變化的歷史，這就需要增設一個CLOSED表。

(2)若要回溯，則還需保存與每個動態資料庫狀態對應的可用規則集。因為動態資料庫狀態與可用規則集實際是一一對應的。(3)要進行樹式搜索，還需設置一個OPEN表，以進行新生動態資料庫的狀態保存和當前動態資料庫狀態的切換。

(4)還要考慮一條規則是否只允許執行一次。若是，則要對已執行了的規則進行標記。表5.1產生式系統與圖搜索對比

可以看出，二者實際是一回事。要說差別的話，圖搜索技術描述了問題求解的方法，而產生式系統則給出了實施這種方法的一種電腦程式系統的結構模式。這樣，問題求解、圖搜索和產生式系統三者的關係是：問題求解是目的，圖搜索是方法，產生式系統是形式。5.4產生式系統的應用

由上述產生式系統與圖搜索的關係可見，產生式系統完全可以作為問題求解的表示模型和求解模型，而且可作為人工智慧問題求解系統的通用模型。用產生式系統也可實現基於謂詞邏輯的演繹推理和證明。

由於產生式系統既可用於操作性問題求解，也可用於推理性問題求解。因此，產生式系統也是專家系統的基本結構形式。用它既可實現規劃型專家系統，也可實現結論型專家系統。總之，產生式系統在人工智慧技術中佔有重要地位。5.5產生式系統的程式實現5.5.1產生式規則的程式語言實現上面我們對產生式的討論，只是用自然語言進行描述並僅在概念層次上進行闡述，而並未涉及它的具體結構和程式語言實現問題。現在討論產生式規則的程式語言實現問題。首先，討論產生式規則的結構問題。一般來講，產生式規則的前提和結論部分可以是一個複雜的邏輯運算式，但為了使表達簡單規範，且便於推理，在實踐中人們往往把規則的前提部分作成形如

條件1AND條件2AND…AND條件n

或條件1OR條件2OR…OR條件m

的形式（其中的條件可以帶否定詞）；把規則結論部分作成形如斷言1/動作1AND斷言2/動作2AND…AND斷言k/動作k

或斷言1/動作1OR斷言2/動作2OR…OR斷言k/動作k的形式，或者進一步簡化成斷言/動作即僅有一項的形式。由於含OR關係的規則也可以分解為幾個不含OR關係的規則，所以，產生式規則也可僅取下麵的一種形式：條件1AND條件2AND…AND條件n→斷言/動作即前件是若干與關係的條件，後件僅有一個斷言或動作。

例5.3把5.2節例5.1中給出的產生式規則用PROLOG的規則可表示如下：

animal-is("老虎"):-it-is("食肉動物"),fact("黃褐色"),

fact("有黑色條紋").it-is("食肉動物"):-it-is1("哺乳動物"),fact("有爪"),fact("有犬齒"),fact("目盯前方").it-is("食肉動物"):-it-is1("哺乳動物"),

fact("吃肉").It--is1("哺乳動物"):-fact("有奶").It--is1(“哺乳動物”):-fact(“有毛髮”).

對於這種規則表示形式，可以不用再編寫推理機程式，而可直接利用PROLOG自身的推理機，進行推理。例如，當再給出如下的事實：

fact("黃褐色").fact("有黑色條紋").fact("吃肉").fact("有奶").和目標：animal--is(Y).則程式運行後的結果就是:Y＝老虎但如果把上面的規則表示成如下的形式:rule(［"食肉動物","黃褐色","有黑色條紋"］,"老虎").rule(［"哺乳動物","有爪","有犬齒","目盯前方"］,"食肉動物").rule(［"哺乳動物","吃肉"］,"食肉動物").rule(［"有奶"］,"哺乳動物").rule(［"有毛髮"］,"哺乳動物").[

則就需要用PROLOG語言編寫一個推理機程式。否則，無法實施基於上述規則的推理。還需說明的是，並非凡是用PROLOG規則表示的產生式規則，都可直接使用PROLOG的推理機。例如，

rule(X,Y):-Y=X+1.

這是一個