一種HAL匹配算法在專家系統中的應用研究

秦旭東

（沈陽工業大學，沈陽 110027）

推理機是專家系統中最重要的部分，它決定了整個專家系統性能的優劣。現在，絕大多數的專家系統采用了規則產生式系統。規則產生式系統由三個部分組成：第一部分是事實或斷言組成的工作內存，被用于問題求解；第二部分是規則集，其中所有規則都是由LHS和RHS組成，LHS由一個或多個條件元素構成，對工作內存中元素的操作存放在RHS；第三部分是控制規則推理引擎。規則產生式系統匹配規則約占90%的工作時間，因此，選擇合適的匹配算法極其重要。傳統上我們在產生式系統中運用RETE、TREAT和Matchbox幾種匹配方法，而本文提出HAL算法，HAL綜合了以上算法的優點，減少了匹配時間，通過建立相關規則和類的啟發式反饋通道，減少了冗余內容和匹配網絡。

1 專家系統結構

專家系統主要由知識庫、推理機、解釋系統、動態數據庫、人機界面等組成。專家系統結構見圖1。

圖1 專家系統結構Fig.1 Expert system structure

2 推理算法

在專家系統中使用的推理算法多種多樣，下面主要介紹被廣泛使用的RETE算法和TREAT算法。

2.1 RETE算法

在RETE中，將每條規則轉化為包含alpha和beta在內的內存匹配網絡，網絡的縱向和橫向成正比，alpha節點位于匹配網絡上方，alpha節點存儲事實集合和匹配條件的記號。其余節點都是beta節點，儲存條件變量綁定和連接的記號。RETE匹配原理見圖2。

圖2 RETE匹配原理Fig.2 RETE matching principle

2.2 TREAT算法

TREAT算法為每條規則建立一個alpha節點。其alpha節點分成三個部分，分別是舊節點、新添加節點、新刪除節點。例如，將新的刪除節點插入到alpha節點時，新的刪除節點會觸發搜索操作，沖突集可能會發生變化，匹配原理見圖3。

圖3 TREAT匹配原理Fig.3 TREAT matching principle

2.3 HAL匹配算法

HAL主要使用類的啟發式信息，而不是規則的啟發式信息，HAL基于類只需定義一個全局匹配網絡，網絡中包括規則節點、類節點和中間節點。

2.3.1 HAL算法的匹配過程

建立一個全局匹配網絡，規則和類轉化為規則節點和類節點。若規則節點有類的變量綁定則建立中間節點，規則節點和中間節點之間進行雙向通信。若規則不涉及類的變量綁定，則類節點與規則節點直接相連。

遍歷舊事實，選取一個事實，查看事實對應的類節點，若此類節點連接中間節點，當加入事實時，將新事實發送給中間節點；當有刪除信息時，中間節點和規則節點接收刪除信息，轉到步驟3。若無中間節點，若滿足檢查類節點的事實條件，則此類節點連接的規則節點被激發，轉到步驟4。若沒有新事實信息或刪除操作時，則算法終止。

對于所有的中間節點，若新的綁定值不屬于被監視的事實或者刪除操作，則中間節點激發所有相連的類節點，不添加新的事實或刪除操作；反之，添加新的事實或刪除操作，轉到步驟4。

遍歷新的綁定值或者刪除操作后，確定規則節點是否全部匹配條件元素。若部分匹配，則修改中間節點對應的條件元素；若全部匹配，則執行RHS部分操作。若沒有“結束”操作則轉入步驟3，否則結束算法。

2.3.2HAL匹配原理圖

圖4 HAL偽雙向網絡Fig.4 HAL pseudo two way network

例如，當添加事實時，匹配過程見圖5。

圖5 添加事實A1Fig.5 Add facts A1

向A類節點添加事實A1，中間節點被激發，中間節點激發B節點，B節點中B1*開始監聽A1匹配規則1。

圖6 添加事實A2Fig.6 Add facts A2

向A類節點添加事實A2，中間節點被激發，中間節點激發B節點中B2*監聽A2匹配規則1。

圖7 添加事實B14Fig.7 Add facts B14

向B類節點添加事實B14，中間節點被B類節點激發，然后中間節點激發C節點C4*監聽B14匹配規則1。

圖8 添加事實B46Fig.8 Add facts B46

向B類節點添加事實B46，中間節點被B類節點激發，然后中間節點激發C節點C4*，同時激發A節點A4監聽B46進行匹配規則1。

圖9 添加事實B47Fig.9 Add facts B47

向B類節點添加事實B47，中間節點被B類節點激發，中間節點激發C節點C7*監聽B47進行匹配。

3 結語

其他規則產生式系統的程序復雜度與HAL的大致相同，但HAL建立的偽雙向網絡是一個常數，而且在多數專家系統中，規則的數量要遠多于類的數量，因此，HAL匹配速度更快。

在實際應用中，還要考察大型的基于規則系統HAL運用的效果如何，防止發生沒有預料到的問題，最終將HAL有效的應用到實踐中。

［1］ 耿慶宦，呂良雙.產生式系統規則匹配算法研究［J］.計算機科學，2009，(11)：26-29.

［2］ P.-Y.LeeandA.M.K.Cheng,"HAL：A Faster Match Algorithm",IEEE Trans. Knowledge and Data Eng.,vol.14,no.5,Sept./Oct.2002..

［3］ 歷長云.鋼板矯直專家系統的設計［D］.沈陽：沈陽工業大學，2004.