一種HAL匹配算法在專家系統(tǒng)中的應(yīng)用研究

秦旭東

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

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

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

專家系統(tǒng)主要由知識(shí)庫(kù)、推理機(jī)、解釋系統(tǒng)、動(dòng)態(tài)數(shù)據(jù)庫(kù)、人機(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é)點(diǎn)位于匹配網(wǎng)絡(luò)上方，alpha節(jié)點(diǎn)存儲(chǔ)事實(shí)集合和匹配條件的記號(hào)。其余節(jié)點(diǎn)都是beta節(jié)點(diǎn)，儲(chǔ)存條件變量綁定和連接的記號(hào)。RETE匹配原理見圖2。

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

2.2 TREAT算法

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

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

2.3 HAL匹配算法

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

2.3.1 HAL算法的匹配過程

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

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

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

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

2.3.2HAL匹配原理圖

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

例如，當(dāng)添加事實(shí)時(shí)，匹配過程見圖5。

圖5 添加事實(shí)A1Fig.5 Add facts A1

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

圖6 添加事實(shí)A2Fig.6 Add facts A2

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

圖7 添加事實(shí)B14Fig.7 Add facts B14

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

圖8 添加事實(shí)B46Fig.8 Add facts B46

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

圖9 添加事實(shí)B47Fig.9 Add facts B47

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

3 結(jié)語(yǔ)

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

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

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