1、第5章 產生式系統 5.1 產生式規則5.2 產生式系統5.3 產生式系統與圖搜索 5.4 產生式系統的應用5.5 產生式系統的程序實現第5章 產生式系統 5.1 產生式規則5.1 產生式規則 5.1.1 產生式規則 產生式(Production)一詞，首先是由美國數學家波斯特（E.Post）提出來的。波斯特根據替換規則提出了一種稱為波斯特機的計算模型，模型中的每一條規則當時被稱為一個產生式。后來，這一術語幾經修改擴充，被用到許多領域。例如，形式語言中的文法規則就稱為產生式。產生式也稱為產生式規則，或簡稱規則。5.1 產生式規則 5.1.1 產生式規則 產生式的一般形式為 前件后件 其中，前件

2、就是前提，后件是結論或動作，前件和后件可以是由邏輯運算符AND、OR、NOT組成的表達式。 產生式規則的語義是:如果前提滿足，則可得結論或者執行相應的動作,即后件由前件來觸發。所以，前件是規則的執行條件，后件是規則體。 產生式的一般形式為 例如，產生式規則： (1)如果銀行存款利率下調，那么股票價格上漲。 (2)如果爐溫超過上限，則立即關閉風門。 (3)如果鍵盤突然失靈，且屏幕上出現怪字符，則是病毒發作。 (4)如果膠卷感光度為200，光線條件為晴天，目標距離不超過5米，則快門速度取250，光圈大小取f16。 例如，產生式規則： 5.1.2 基于產生式的推理模式 由產生式的涵義可知，利用產生式

3、規則可以實現有前提條件的指令性操作，也可以實現邏輯推理。實現操作的方法是當測試到一條規則的前提條件滿足時，就執行其后部的動作。這稱為規則被觸發或點燃。利用產生式規則實現邏輯推理的方法是當有事實能與某規則的前提匹配（即規則的前提成立）時，就得到該規則后部的結論（即結論也成立）。 5.1.2 基于產生式的推理模式 實際上，這種基于產生式規則的邏輯推理模式，就是邏輯上所說的假言推理（對常量規則而言）和三段論推理（對變量規則而言），即： AB A B 這里的大前提就是一個產生式規則，小前提就是證據事實。 實際上，這種基于產生式規則的邏輯推理5.2 產生式系統 5.2.1 產生式系統的組成 產生式系統由

4、三部分組成：產生式規則庫、推理機和動態數據庫，其結構如圖所示。產生式規則庫亦稱產生式規則集，由領域規則組成，在機器中以某種動態數據結構進行組織。 推理機亦稱控制執行機構，它是一個程序模塊，負責產生式規則的前提條件測試或匹配，規則的調度與選取，規則體的解釋和執行。即推理機實施推理，并對推理進行控制，它也就是規則的解釋程序。 產品式規則庫推理機動態數據庫5.2 產生式系統 5.2.1 產生式系統的組 5.2.2 產生式系統的運行過程 產生式系統運行時，除了需要規則庫以外，還需要有初始事實(或數據)和目標條件。 目標條件是系統正常結束的條件，也是系統的求解目標。產生式系統啟動后，推理機就開始推理，按

5、所給的目標進行問題求解。 推理機的一次推理過程，可如圖所示。 一個實際的產生式系統，其目標條件一般不會只經一步推理就可滿足，往往要經過多步推理才能滿足或者證明問題無解。從規則庫中取一個條規則，將其前提同當前動態數據庫中的事實/數據進行模式匹配匹配成功否把該規則的結論放入當前動態數據庫：或執行規則所規定的動作NY 5.2.2 產生式系統的運行過程從規則庫中取一個條規 5.2.3 控制策略與常用算法 產生式系統的推理可分為正向推理和反向推理兩種基本方式。 1.正向推理 正向推理算法一： 步1 將初始事實/數據置入動態數據庫； 步2 用動態數據庫中的事實/數據，匹配/測試目標條件，若目標條件滿足，則

6、推理成功，結束。 步3 用規則庫中各規則的前提匹配動態數據庫中的事實/數據，將匹配成功的規則組成待用規則集；步4 若待用規則集為空，則運行失敗，退出。步5 將待用規則集中各規則的結論加入動態數據庫，或者執行其動作，轉步2； 可以看出:隨著推理的進行，動態數據庫的內容或者狀態在不斷變化。動態數據庫推理 5.2.3 控制策略與常用算法動態數據庫推理 例5.1 動物分類問題的產生式系統描述及其求解。 設由動物識別規則組成規則庫，推理機采用上述正向推理算法。該產生式系統就是一個小型動物分類知識庫系統。規則： r1：若某動物有奶，則它是哺乳動物。 r2：若某動物有毛發，則它是哺乳動物。 r3：若某動物有

7、羽毛，則它是鳥。 r4：若某動物會飛且生蛋，則它是鳥。 r5：若某動物是哺乳動物且有爪且有犬齒且目盯前方，則它是食肉動物。r6：若某動物是哺乳動物且吃肉，則它是食肉動物。r7：若某動物是哺乳動物且有蹄，則它是有蹄動物。r8：若某動物是有蹄動物且反芻食物，則它是偶蹄動物。r9：若某動物是食肉動物且黃褐色且有黑色條紋，則它是老虎。r10：若某動物是食肉動物且黃褐色且有黑色斑點，則它是金錢豹。r11：若某動物是有蹄動物且長腿且長脖子且黃褐色且有暗斑點，則它是長頸鹿。r12：若某動物是有蹄動物且白色且有黑色條紋，則它是斑馬。r13：若某動物是鳥且不會飛且長腿且長脖子且黑白色，則它是駝鳥。r14：若某動

8、物是鳥且不會飛且會游泳且黑白色，則它是企鵝。r15：若某動物是鳥且善飛且不怕風浪，則它是海燕。 例5.1 動物分類問題的產生式系統描述及其求解。再給出初始事實：f1：某動物有毛發。f2：吃肉。f3：黃褐色。f4：有黑色條紋。目標條件：該動物是什么？易見，該系統的運行結果為：該動物是老虎。其推理樹如圖所示。動物分類正向推理樹 老虎食肉動物哺乳動物有毛發吃肉黃褐色有黑色條紋再給出初始事實：動物分類正向推理樹 老虎食肉動物哺乳動物有毛 2. 反向推理 步1 將初始事實/數據置入動態數據庫，將目標條件置入目標鏈； 步2 若目標鏈為空，則推理成功，結束。 步3 取出目標鏈中第一個目標，用動態數據庫中的事

9、實/數據同其匹配，若匹配成功，轉步2； 步4 用規則集中的各規則的結論同該目標匹配，若匹配成功，則將第一個匹配成功且未用過的規則的前提作為新的目標，并取代原來的父目標而加入目標鏈，轉步3； 步5 若該目標是初始目標，則推理失敗，退出。 步6 將該目標的父目標移回目標鏈，取代該目標及其兄弟目標，轉步3； 可以看出，上述反向推理算法的推理過程也是一個圖搜索過程，而且一般是一個與或樹搜索。 2. 反向推理 例5.2 對于上例的產生式系統，改為反向推理算法，則得到圖所示的推理樹。圖55 動物分類反向推理樹 例5.2 對于上例的產生式系統，改為 可以看出，與正向推理不同，這次的推理樹是從上而下擴展而成的

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

11、/數據，匹配/測試目標條件，若目標條件滿足，則推理成功，結束。 步3 用規則庫中各規則的前提匹配動態數據庫中的事實/數據，將匹配成功的規則組成待用規則集； 步4 若待用規則集為空，則運行失敗，退出。 步5 用某種策略，從待用規則集中選取一條規則，將其結論加入動態數據庫，或者執行其動作，撤消待用規則集，轉步2； 可以看出，該算法與前面的算法僅在步5有所差別。 3. 沖突消解策略5.3 產生式系統與圖搜索 分析前面給出的兩個正向推理算法，可以看出，它們只能用于解決邏輯推理問題: (1)記錄動態數據庫狀態變化的歷史，這就需要增設一個CLOSED表。 (2)若要回溯，則還需保存與每個動態數據庫狀態對應

12、的可用規則集。因為動態數據庫狀態與可用規則集實際是一一對應的。 (3)要進行樹式搜索，還需設置一個OPEN表，以進行新生動態數據庫的狀態保存和當前動態數據庫狀態的切換。 (4)還要考慮一條規則是否只允許執行一次。若是，則要對已執行了的規則進行標記。5.3 產生式系統與圖搜索 分析前面表5.1 產生式系統與圖搜索對比 可以看出，二者實際是一回事。要說差別的話，圖搜索技術描述了問題求解的方法，而產生式系統則給出了實施這種方法的一種計算機程序系統的結構模式。這樣，問題求解、圖搜索和產生式系統三者的關系是：問題求解是目的，圖搜索是方法，產生式系統是形式。表5.1 產生式系統與圖搜索對比 5.4 產生式

13、系統的應用 由上述產生式系統與圖搜索的關系可見，產生式系統完全可以作為問題求解的表示模型和求解模型，而且可作為人工智能問題求解系統的通用模型。用產生式系統也可實現基于謂詞邏輯的演繹推理和證明。 由于產生式系統既可用于操作性問題求解，也可用于推理性問題求解。因此，產生式系統也是專家系統的基本結構形式。用它既可實現規劃型專家系統，也可實現結論型專家系統。 產生式系統在人工智能技術中占有重要地位。5.4 產生式系統的應用 由上述產生式系統與5.5 產生式系統的程序實現 5.5.1 產生式規則的程序語言實現 討論產生式規則的形式結構: 產生式規則的前提和結論部分可以是一個復雜的邏輯表達式，為使表達簡單

14、規范，便于推理，往往把規則的前提部分作成形如: 條件1AND條件2ANDAND條件n 或者 條件1OR條件2OROR條件m 把規則結論部分作成形如 斷言1/動作1AND斷言2/動作2ANDAND斷言k/動作k 或者 斷言1/動作1OR斷言2/動作2OROR斷言k/動作k 或者進一步簡化成: 斷言/動作 ( 即僅有一項) 由于含OR關系的規則也可以分解為若干不含OR關系的規則，所以，產生式規則也可僅取下面的一種形式： 條件1AND條件2ANDAND條件n斷言/動作5.5 產生式系統的程序實現 5.5.1 產生式前例：DOMAINS name=string.PREDICATES animal_is

15、(name). it_is(name). it_is1(name). fact(name).GOAL animal_is(Y),write(“Y=”,Y).CLAUSES fact(“有爪”). fact(“吃肉”). fact(“有奶”).fact(“黃褐色”).fact(“有黑色斑點”). it_is(“哺乳動物”):-fact(“有奶”). it_is(“哺乳動物”):-fact(“有毛發”).it_is1(“食肉動物”):-it_is(“哺乳動物”),fact(“有爪”), fact(“有犬齒”).it_is1(“食肉動物”):-it_is(“哺乳動物”),fact(“吃肉”).it_

16、is1(“有蹄動物”):-it_is(“哺乳動物”),fact(“有蹄”).animal_is(“老虎”):- it_is1(“食肉動物”), fact(“黃褐色”),fact(“有黑色條紋”).animal_is(“金錢豹”):- it_is1(“食肉動物”), fact(“黃褐色”),fact(“有黑色斑點”).animal_is(“長頸鹿”):- it_is1(“有蹄動物”), fact(“長腿”),fact(“長脖”), fact(“有暗斑點”).animal_is(“斑馬”):- it_is1(“有蹄動物”), fact(“有黑色條紋”).前例： it_is(“哺乳動物”):-fact(“有奶”) 5.5.2 規則庫的程序實現 規則庫的程序實現分為內存和外存兩個方面。在內存中規則庫可用鏈表實現，在外存則就是以規則為基本單位的數據文件。 若用PROLOG程序，規則庫就是程序的一部分；對于事實表示的規則，則規則庫在內存就是動態數據庫，在外存就是數據庫文件。 還需說明的是，對于規則庫實際上還需配一個管理程序，即知識庫管理系統，專門負責規則及規則庫