秦旭東

（沈陽工業(yè)大學(xué)，沈陽 110027）

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

1 專家系統(tǒng)結(jié)構(gòu)

專家系統(tǒng)主要由知識庫、推理機、解釋系統(tǒng)、動態(tài)數(shù)據(jù)庫、人機界面等組成。專家系統(tǒng)結(jié)構(gòu)見圖1。

圖1 專家系統(tǒng)結(jié)構(gòu)Fig.1 Expert system structure

2 推理算法

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

2.1 RETE算法

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

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

2.2 TREAT算法

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

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

2.3 HAL匹配算法

HAL主要使用類的啟發(fā)式信息，而不是規(guī)則的啟發(fā)式信息，HAL基于類只需定義一個全局匹配網(wǎng)絡(luò)，網(wǎng)絡(luò)中包括規(guī)則節(jié)點、類節(jié)點和中間節(jié)點。

2.3.1 HAL算法的匹配過程

建立一個全局匹配網(wǎng)絡(luò)，規(guī)則和類轉(zhuǎn)化為規(guī)則節(jié)點和類節(jié)點。若規(guī)則節(jié)點有類的變量綁定則建立中間節(jié)點，規(guī)則節(jié)點和中間節(jié)點之間進行雙向通信。若規(guī)則不涉及類的變量綁定，則類節(jié)點與規(guī)則節(jié)點直接相連。

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

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

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

2.3.2HAL匹配原理圖

圖4 HAL偽雙向網(wǎng)絡(luò)Fig.4 HAL pseudo two way network

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

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

向A類節(jié)點添加事實A1，中間節(jié)點被激發(fā)，中間節(jié)點激發(fā)B節(jié)點，B節(jié)點中B1*開始監(jiān)聽A1匹配規(guī)則1。

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

向A類節(jié)點添加事實A2，中間節(jié)點被激發(fā)，中間節(jié)點激發(fā)B節(jié)點中B2*監(jiān)聽A2匹配規(guī)則1。

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

向B類節(jié)點添加事實B14，中間節(jié)點被B類節(jié)點激發(fā)，然后中間節(jié)點激發(fā)C節(jié)點C4*監(jiān)聽B14匹配規(guī)則1。

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

向B類節(jié)點添加事實B46，中間節(jié)點被B類節(jié)點激發(fā)，然后中間節(jié)點激發(fā)C節(jié)點C4*，同時激發(fā)A節(jié)點A4監(jiān)聽B46進行匹配規(guī)則1。

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

向B類節(jié)點添加事實B47，中間節(jié)點被B類節(jié)點激發(fā)，中間節(jié)點激發(fā)C節(jié)點C7*監(jiān)聽B47進行匹配。

3 結(jié)語

其他規(guī)則產(chǎn)生式系統(tǒng)的程序復(fù)雜度與HAL的大致相同，但HAL建立的偽雙向網(wǎng)絡(luò)是一個常數(shù)，而且在多數(shù)專家系統(tǒng)中，規(guī)則的數(shù)量要遠多于類的數(shù)量，因此，HAL匹配速度更快。

在實際應(yīng)用中，還要考察大型的基于規(guī)則系統(tǒng)HAL運用的效果如何，防止發(fā)生沒有預(yù)料到的問題，最終將HAL有效的應(yīng)用到實踐中。

［1］ 耿慶宦，呂良雙.產(chǎn)生式系統(tǒng)規(guī)則匹配算法研究［J］.計算機科學(xué)，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］ 歷長云.鋼板矯直專家系統(tǒng)的設(shè)計［D］.沈陽：沈陽工業(yè)大學(xué)，2004.