李 建，習(xí)文風(fēng)

西南石油大學(xué) 計(jì)算機(jī)科學(xué)學(xué)院，成都610500

1 引言

鉆井液設(shè)計(jì)專家系統(tǒng)結(jié)合來自于領(lǐng)域?qū)＜业慕?jīng)驗(yàn)規(guī)則庫(kù)，應(yīng)用基于規(guī)則的推理技術(shù)，通過鉆井地層的地質(zhì)結(jié)構(gòu)、地層特征和油氣井信息等數(shù)據(jù)來設(shè)計(jì)滿足條件的鉆井液體系和配方，以達(dá)到快速優(yōu)質(zhì)鉆井的目的，同時(shí)也能有效地保存經(jīng)驗(yàn)數(shù)據(jù)和避免重復(fù)性工作[1-2]。

但是，隨著規(guī)則的不斷增加，規(guī)則庫(kù)日益繁雜，對(duì)規(guī)則庫(kù)的維護(hù)已經(jīng)成為制約專家系統(tǒng)效率的重要因素。一般而言，對(duì)規(guī)則庫(kù)的維護(hù)主要包括從屬、冗余、環(huán)路和沖突四方面[3]。

針對(duì)規(guī)則庫(kù)的維護(hù)問題，文獻(xiàn)[4]研究了規(guī)則庫(kù)添加新的規(guī)則后對(duì)冗余的判別、處理以及校驗(yàn)的實(shí)現(xiàn)方法，但并未對(duì)環(huán)路和沖突等問題進(jìn)行研究；文獻(xiàn)[5]討論了規(guī)則庫(kù)的一致性檢測(cè)，并對(duì)沖突消解進(jìn)行了研究，但并未提及對(duì)冗余和環(huán)路等問題的檢測(cè)；文獻(xiàn)[6]結(jié)合有向超圖和生成樹，提出了一種能夠去除從屬和冗余的算法，但沒有研究環(huán)路和沖突等問題；文獻(xiàn)[7]研究了粗糙集理論，通過對(duì)決策表進(jìn)行屬性約簡(jiǎn)來去除冗余規(guī)則，并對(duì)剩余規(guī)則進(jìn)行排序，但同樣沒有提及對(duì)環(huán)路和沖突等問題的處理；文獻(xiàn)[8]提出了一種基于知識(shí)約簡(jiǎn)的Petri網(wǎng)模型簡(jiǎn)化方法，利用知識(shí)約簡(jiǎn)中的屬性約簡(jiǎn)方法，去除了Petri網(wǎng)對(duì)應(yīng)的產(chǎn)生式規(guī)則的冗余規(guī)則和冗余條件；文獻(xiàn)[9]提出了一種基于Petri網(wǎng)的冗余檢測(cè)算法；文獻(xiàn)[10]在有向超圖的基礎(chǔ)上提出了一種規(guī)則庫(kù)的合并算法，并且研究了如何檢測(cè)冗余、環(huán)路和沖突，但算法所構(gòu)建的鄰接矩陣規(guī)模太大，導(dǎo)致效率較低。

總的來說，目前應(yīng)用于規(guī)則庫(kù)維護(hù)的方法主要有表格法、基于Petri網(wǎng)的方法、基于圖的方法和基于代數(shù)插值的方法等[11-14]。其中，有向圖因其便于表示規(guī)則之間的關(guān)系而成為研究規(guī)則庫(kù)維護(hù)的重要工具。又因?yàn)殂@井液設(shè)計(jì)專家系統(tǒng)中的規(guī)則很多都是多對(duì)一的關(guān)系，所以本文引入有向超圖來表示規(guī)則[15-18]。

為了避免不能將規(guī)則庫(kù)中問題全部檢測(cè)而影響推理效率和推理準(zhǔn)確性的不利后果，本文提出了一種能夠檢測(cè)從屬、冗余、環(huán)路和沖突等全部問題的算法，同時(shí)降低了算法中矩陣的規(guī)模，保證了運(yùn)算效率。

本文首先介紹了如何用有向超圖來表示規(guī)則庫(kù)中的規(guī)則以及如何構(gòu)建對(duì)應(yīng)的鄰接矩陣，然后討論了可達(dá)矩陣的概念和計(jì)算，并在此基礎(chǔ)上給出了規(guī)則庫(kù)的檢測(cè)算法，最后通過實(shí)驗(yàn)對(duì)算法的可行性和有效性加以驗(yàn)證。

2 鉆井液設(shè)計(jì)專家系統(tǒng)規(guī)則庫(kù)

2.1 鉆井液的功用及體系

在鉆井中用作洗井的流體被稱為鉆井流體，因?yàn)殂@井流體多屬于液體，氣體型鉆井液很少被使用，所以簡(jiǎn)稱為“鉆井液”。

鉆井時(shí)，鉆井液除了需要保護(hù)所鉆油氣儲(chǔ)層外，還擔(dān)負(fù)著以下任務(wù)：潤(rùn)滑、冷卻鉆具、熱穩(wěn)定性、巖層穩(wěn)定性、平衡壓差、較強(qiáng)的清井及攜巖能力等。這些都是由于地下鉆井油氣層的差異性和復(fù)雜情況以及不同井型對(duì)鉆井液設(shè)計(jì)提出的要求。

鉆井液體系種類隨著具體要求和鉆井液技術(shù)的進(jìn)步而逐漸增多。目前，國(guó)內(nèi)外分類鉆井液的方法有很多種，根據(jù)體系組成特點(diǎn)和流體介質(zhì)的不同，可以把鉆井液分為油基、合成基、水基、氣體型四種類型，每種類型又包含多種鉆井液，如圖1所示。

2.2 規(guī)則庫(kù)

規(guī)則庫(kù)是鉆井液設(shè)計(jì)專家系統(tǒng)的核心部分，專家系統(tǒng)的所有操作都是圍繞規(guī)則庫(kù)進(jìn)行的。在對(duì)規(guī)則庫(kù)進(jìn)行增刪改等操作時(shí)，若沒有考慮到規(guī)則知識(shí)結(jié)構(gòu)的應(yīng)有變化，容易導(dǎo)致規(guī)則庫(kù)出現(xiàn)問題，從而不能推理出正確的結(jié)果。

一般情況下規(guī)則庫(kù)中的問題主要包括：

從屬：存在能產(chǎn)生相同規(guī)則，但條件卻是包含關(guān)系的兩條規(guī)則。

圖1 鉆井液體系分類

冗余：存在兩條等價(jià)的規(guī)則。

環(huán)路：一組規(guī)則互相推出，會(huì)使推理進(jìn)入死循環(huán)。

沖突：兩條規(guī)則在相同條件下產(chǎn)生相互矛盾的結(jié)果。

由上述可知，在對(duì)規(guī)則庫(kù)進(jìn)行增刪改等操作后有必要對(duì)其進(jìn)行檢測(cè)，以保證它能正確有效地發(fā)揮作用。

3 有向超圖及其鄰接矩陣

3.1 規(guī)則的表達(dá)形式

一個(gè)規(guī)則的一般形式可以表達(dá)為：

IF x1∧x2∧…∧xnTHEN xn+1

可簡(jiǎn)寫：

其中，規(guī)則的左部稱為規(guī)則的條件部分，或叫作規(guī)則前件；右部稱為規(guī)則的結(jié)論部分，或叫作規(guī)則后件。上述規(guī)則的含義為：如果條件部分x1,x2,…,xn都得到滿足，則執(zhí)行結(jié)論部分xn+1。

而如果規(guī)則的條件部分只包含一個(gè)選擇子，則該規(guī)則稱為簡(jiǎn)單規(guī)則，否則稱為復(fù)合規(guī)則。例如，規(guī)則R：

IF泥頁(yè)巖成分>50%∧含砂量>10%THEN鉆井液類型為鹽水鉆井液

則規(guī)則R為復(fù)合規(guī)則，將R的前提記為ante(R)，結(jié)論記為cons(R)，其中前者為由兩個(gè)選擇子組成的集合。

3.2 有向超圖與鄰接矩陣

有向超圖是有向圖的推廣，它是在無(wú)向超圖中每條超邊的基礎(chǔ)上添加方向所得。

定義1（有向超圖）有向超圖是由有限非空頂點(diǎn)集V和有向超邊集E組成的有序?qū)=(V,E)。有向超邊e∈E是有序?qū)?T(e),H(e))，其中T(e)為有向超邊e的尾點(diǎn)集，H(e)為有向超邊e的頭點(diǎn)集，T(e)與H(e)均為V的非空子集，且T(e)∩H(e)=?。

與有向圖不同，在有向超圖中，超邊e所連接的可以是由多個(gè)頂點(diǎn)組成的點(diǎn)集，這一性質(zhì)適用于表示含有復(fù)合規(guī)則的規(guī)則庫(kù)。

利用有向超圖可以將規(guī)則庫(kù)（下述規(guī)則為示例所用，其選擇子x無(wú)實(shí)際意義）表示為如圖2所示形式。

圖2 規(guī)則庫(kù)的有向超圖表示

規(guī)則1 x1→x2；

規(guī)則2 x2→x4；

規(guī)則3 x3∧x4→x5，記為R1；

規(guī)則4 x3∧x6→?x2，記為R2。

假設(shè)規(guī)則庫(kù)中有n個(gè)選擇子（其中?x選擇子有d個(gè)），分別記為x1,x2,?x2,…,xn-d，并假設(shè)規(guī)則庫(kù)中有m條復(fù)合規(guī)則，分別記為R1,R2,…,Rm。

定義2（鄰接矩陣An×n）如果規(guī)則庫(kù)中不存在前提包含xi結(jié)論為xj的規(guī)則，記Ai,j=0；如果規(guī)則庫(kù)中包含簡(jiǎn)單規(guī)則xi→xj，記Ai,j=1，而若包含簡(jiǎn)單規(guī)則xi→?xj,則Ai,j+1=-1,若對(duì)應(yīng)的?xi→xj,則Ai+1,j=-1,而?xi→?xj，則將規(guī)則轉(zhuǎn)換為其逆否命題xj→xi；如果規(guī)則庫(kù)中存在復(fù)合規(guī)則Rm，其前提包含xi，結(jié)論為xj，則Ai,j表示為二元組(xi,Rm)，而若結(jié)論為?xj，則Ai,j表示為二元組-(xi,Rm)。

根據(jù)鄰接矩陣的定義可得圖2有向超圖的鄰接矩陣為：

鄰接矩陣可以通過掃描規(guī)則庫(kù)得到。顯然，在掃描過程中，如果元素|Ai,j|=1，則所有前提包含xi且結(jié)論為xj的復(fù)合規(guī)則均為從屬規(guī)則，從規(guī)則庫(kù)中刪除；如果元素Ai,j=±(xi,Rm)，則所有從屬于Rm的復(fù)合規(guī)則均從規(guī)則庫(kù)中刪除。

3.3 有向超圖的路徑長(zhǎng)度

定義3（路徑長(zhǎng)度）路徑長(zhǎng)度指該路徑從起點(diǎn)到終點(diǎn)所經(jīng)過的最長(zhǎng)路徑。即從xi到xj的某條路徑長(zhǎng)度為k的條件是：對(duì)該路徑的最后一條規(guī)則R（顯然其結(jié)論為xj），從xi到ante(R)中至少一個(gè)元素的路徑長(zhǎng)度為k-1。

如圖3所示，從x1到x5存在兩條路徑：（1）x1→x2,x2→x4,x3∧x4→x5；（2）x1→x3,x3∧x4→x5。在路徑（1）中，由規(guī)則的傳導(dǎo)性可知x1到x4的路徑長(zhǎng)度為2，而規(guī)則x3∧x4→x5的ante(R)中蘊(yùn)含了規(guī)則x2→x4的cons(R)，因此路徑（1）中從x1到x5的路徑長(zhǎng)度為3，同理可得路徑（2）中從x1到x5的路徑長(zhǎng)度為2，取最長(zhǎng)路徑得圖3中從x1到x5的路徑長(zhǎng)度為3。

圖3 有向超圖的路徑長(zhǎng)度

4 有向超圖的可達(dá)矩陣

4.1 可達(dá)矩陣的定義

有向超圖的可達(dá)矩陣有兩種：

若計(jì)算完Ek仍未檢測(cè)到冗余、環(huán)路、沖突，則Ek內(nèi)元素絕對(duì)值均為0或1。為了便于后續(xù)的計(jì)算，將當(dāng)前總可達(dá)矩陣Ek中非零元素的路徑長(zhǎng)度存入矩陣Fn×n。

由定義3有向超圖的路徑長(zhǎng)度可得Fn×n的定義為：

由定義可知，如果當(dāng)前Dk中至少有一個(gè)元素絕對(duì)值為1，則Fn×n中對(duì)應(yīng)位置的元素為k。因此，將Fn×n初值賦為，當(dāng)計(jì)算完Dk(k=2,3,…)時(shí)，F(xiàn)n×n更新為：

4.2 計(jì)算總可達(dá)矩陣E k+1

由鄰接矩陣的定義可知，將A中絕對(duì)值不為1的元素賦值為0，即可得到一步可達(dá)矩陣D1n×n和一步總可達(dá)矩陣E1n×n。

假設(shè)Dk和Ek都已求得，欲求Ek+1，需要先計(jì)算Dk+1。那么：

可得：

規(guī)定（矩陣中所有元素在計(jì)算過程中取絕對(duì)值參與計(jì)算，得出結(jié)果后再保持與同號(hào)）：若=0或Al,j=0,l=1,2,…,n，則若=1?(xp,R′)，且記R′為xp∧xq→xj，則：

5 規(guī)則庫(kù)檢測(cè)算法

本文提出了一種針對(duì)規(guī)則庫(kù)中從屬、冗余、環(huán)路和沖突的檢測(cè)算法，算法的具體步驟如下：

（1）整理規(guī)則庫(kù)，根據(jù)定義1所定義的有向超圖來表示規(guī)則庫(kù)中的規(guī)則。

（2）根據(jù)定義2構(gòu)建出該有向超圖的鄰接矩陣An×n。

（3）預(yù)處理鄰接矩陣，判定并刪除An×n中的從屬規(guī)則：如果元素1，則所有前提包含xi且結(jié)論為xj的復(fù)合規(guī)則均為從屬規(guī)則，從規(guī)則庫(kù)中刪除；如果元素Ai,j=±(xi,Rm)，則所有從屬于Rm的復(fù)合規(guī)則均從規(guī)則庫(kù)中刪除。

（4）將An×n中絕對(duì)值不為1的元素賦值為0得到一步可達(dá)矩陣和一步總可達(dá)矩陣，再將An×n中所有元素取絕對(duì)值得到路徑長(zhǎng)度矩陣Fn×n，同時(shí)判斷：若||≥1，則規(guī)則庫(kù)中存在環(huán)路；若||=1且=-1或者|=1且||=-1，則規(guī)則庫(kù)中存在沖突。

算法流程圖如圖4所示。

圖4 算法流程圖

該算法的復(fù)雜度與規(guī)則庫(kù)的規(guī)模、選擇子的數(shù)量以及路徑長(zhǎng)度有關(guān)。假設(shè)規(guī)則庫(kù)中規(guī)則的數(shù)量為m，選擇子的數(shù)量為n，路徑長(zhǎng)度最長(zhǎng)為r。

計(jì)算鄰接矩陣An×n需要掃描規(guī)則庫(kù)，該步驟的復(fù)雜度為O(m)。由計(jì)算Dk+1=Dk?A，復(fù)雜度為O(n3)；計(jì)算復(fù)雜度為O(n2)；計(jì)算Fn×n+→Fn×n,復(fù)雜度為O(n2)；掃描，檢測(cè)冗余、環(huán)路和沖突的復(fù)雜度為O(n2)。

最大循環(huán)次數(shù)為r，因此總的復(fù)雜度為O(m)+r(O(n3)+O(n2)+O(n2)+O(n2)),約等于O(m+rn3+3rn2)。

因?yàn)樗惴ㄖ械木仃嚧蠖嗍窍∈杈仃?，所以還可以利用零元素節(jié)省大量存儲(chǔ)、運(yùn)算和程序運(yùn)行時(shí)間，從而進(jìn)一步確保效率。

6 實(shí)驗(yàn)

6.1 實(shí)例驗(yàn)證

以下為鉆井液設(shè)計(jì)專家系統(tǒng)規(guī)則庫(kù)中的部分規(guī)則：

x1→x2；（若鉆井液類型為水基，則對(duì)漏失類型為滲漏的地層有效）

x1→x3；（若鉆井液類型為水基，則對(duì)漏失類型為完全漏失的地層有效）

x1→x6；（若鉆井液類型為水基，則對(duì)漏失類型為嚴(yán)重完全漏失的地層有效）

x4→x6；（若采用剪切稠化堵漏劑，則對(duì)漏失類型為嚴(yán)重完全漏失的地層有效）

x4→?x3；（若采用剪切稠化堵漏劑，則對(duì)漏失類型為完全漏失的地層無(wú)效）

x2∧x3→x4，記為R1；（若地層漏失類型為滲漏或者完全漏失，則應(yīng)采用剪切稠化堵漏劑）

x4∧x5→x1，記為R2。（若采用剪切稠化堵漏劑，并且加入細(xì)粒橋堵劑，則其適用于水基類型鉆井液）

將上述規(guī)則表示為圖5所示的有向超圖。

圖5 案例所述規(guī)則的有向超圖表示

將圖5表示為鄰接矩陣得：

將A中絕對(duì)值不為1的元素賦值為0可得D1和E1，再將所有元素取絕對(duì)值得到F：

判斷E1，未檢測(cè)到冗余、環(huán)路或沖突，計(jì)算D2：

D2=D1?A

由式（2）：存在規(guī)則R1:x2∧x3→x4，由于F1,2=F1,3=1，可得D21,5=1。

判斷E2，未檢測(cè)到冗余、環(huán)路或沖突，計(jì)算D3：

由式（1）：存在規(guī)則R2:x4∧x5→x1,由于F1,5=2≤2,可得D31,1=1。

根據(jù)第5章的檢測(cè)算法判斷E3：|=1≥1，檢測(cè)到環(huán)路，即x1可達(dá)x1；E13,3=1且E13,4=-1，檢測(cè)到?jīng)_突，即x1可達(dá)x3同時(shí)可達(dá)?x3；E31,7=2≥1，檢測(cè)到冗余，即x1通過兩條路徑可達(dá)x6。

可以看出，本算法能夠有效地檢測(cè)出規(guī)則庫(kù)中存在的從屬、冗余、環(huán)路和沖突等全部問題，且整個(gè)算法的計(jì)算過程較為簡(jiǎn)單快速。

6.2 對(duì)比分析

本算法能夠有效地檢測(cè)出規(guī)則庫(kù)中的從屬、冗余、環(huán)路和沖突等全部問題，相較于文獻(xiàn)[4-9]中提出的算法，針對(duì)于其中的一種或幾種，本算法能夠?qū)⒁?guī)則庫(kù)中的問題更加全面地檢測(cè)出來。

根據(jù)文獻(xiàn)[10]中算法得到圖5的鄰接矩陣為：

將A中絕對(duì)值不為1的元素賦值為0得到D1、E1和F：

對(duì)比本節(jié)實(shí)例驗(yàn)證部分可以看出，本算法構(gòu)建的鄰接矩陣規(guī)模大約減小了3/4，同時(shí)后續(xù)所有參與運(yùn)算的矩陣規(guī)模都隨之大大減小，使得運(yùn)算效率獲得了較大提升。

7 結(jié)論及展望

本算法結(jié)合有向超圖和鄰接矩陣來表示規(guī)則，通過計(jì)算可達(dá)矩陣和總可達(dá)矩陣來檢測(cè)規(guī)則庫(kù)中存在的問題。實(shí)驗(yàn)表明，本文提出的算法能夠準(zhǔn)確地檢測(cè)出規(guī)則庫(kù)中存在的從屬、冗余、環(huán)路和沖突等全部問題，而且算法構(gòu)建的鄰接矩陣規(guī)模較小，參與運(yùn)算的矩陣又大多是稀疏矩陣，因此計(jì)算過程較為簡(jiǎn)單快速，從而確保了效率。而當(dāng)規(guī)則結(jié)論部分為由若干選擇子組成的集合時(shí)，對(duì)規(guī)則庫(kù)從屬、冗余、環(huán)路和沖突的檢測(cè)有待進(jìn)一步研究。

另外，當(dāng)規(guī)則的數(shù)量很大時(shí)，參與計(jì)算的矩陣規(guī)模也會(huì)變得很大，算法的效率可能會(huì)隨之下降，這時(shí)可以先對(duì)規(guī)則進(jìn)行分類處理，為其設(shè)計(jì)一個(gè)分類算法，本文的下一步工作將圍繞著這個(gè)問題展開。