胡 非 ，劉志剛 ，何士玉 ，楊紅梅

（1.西南交通大學(xué) 電氣工程學(xué)院，四川 成都 610031；2.湖北省黃石供電公司，湖北 黃石 435000）

0 引言

現(xiàn)代電力系統(tǒng)中，電力系統(tǒng)中的大部分故障來源于配電網(wǎng)，配電網(wǎng)故障診斷是從技術(shù)上提高配電網(wǎng)安全可靠運行的重要手段。近年來，許多學(xué)者將人工智能的理論和方法用于配電網(wǎng)故障診斷，如蟻群算法［1］、遺傳算法［2］、協(xié)同進(jìn)化算法［3］、粒子群算法［4］和專家系統(tǒng)［5-7］等，其中，專家系統(tǒng)在配電網(wǎng)故障診斷系統(tǒng)中應(yīng)用最為廣泛。

為了克服傳統(tǒng)專家系統(tǒng)的缺陷，從20世紀(jì)70年代起，Reiter等國外學(xué)者［8-11］提出用基于模型診斷（MBD）方法來開發(fā)故障診斷系統(tǒng)?，F(xiàn)在，MBD已經(jīng)成為人工智能領(lǐng)域的一個研究熱點，已應(yīng)用于醫(yī)療、經(jīng)濟(jì)、航天、電路診斷等諸多領(lǐng)域，但在電網(wǎng)系統(tǒng)故障診斷中的應(yīng)用研究還處于起步階段。

在MBD方法中，由最小沖突集求解最小碰集的過程是一個NP-Hard問題。目前，許多學(xué)者都對計算最小碰集的算法進(jìn)行了研究和改進(jìn)，主要有：HSTREE［12］，HS-DAG［13］，HST-TREE［14］，BHS-TREE［15］，布爾代數(shù)算法［16］，邏輯數(shù)組算法［17］，遺傳算法［18］，粒子群算法［19］等。在以上這些方法中，主要缺點集中表現(xiàn)在：

a.需要進(jìn)行剪枝，可能會丟失正確解［12］；

b.所建立的樹或者圖，數(shù)據(jù)結(jié)構(gòu)復(fù)雜而且計算量大［12-14］；

c.要求求出所有的碰集再化簡［15-17］；

d.所得到的結(jié)果不能保證全是最小碰集［18-19］。

這些缺點的存在使得程序難以編制，而且在處理復(fù)雜系統(tǒng)診斷問題時，例如配電網(wǎng)故障診斷，最小沖突集簇元件總數(shù)與最小沖突集中元件數(shù)對其算法效率影響比較大，導(dǎo)致算法效率不高。

本文針對上述算法產(chǎn)生的缺點，提出使用二進(jìn)制編碼邏輯運算的方法計算最小碰集，以滿足模型故障診斷中對配電網(wǎng)系統(tǒng)診斷解的計算，該方法的主要優(yōu)點是：

a.對每個元件進(jìn)行二進(jìn)制編碼，有2個好處，一是算法的整個運算過程，只有0/1組成的字符串進(jìn)行單一的邏輯“或”運算，易于程序的編制和實現(xiàn)，二是該算法的復(fù)雜度只與最小沖突集簇中所包含的元件數(shù)有關(guān)，與最小沖突集個數(shù)及最小沖突集中元件個數(shù)無關(guān)，促使該算法診斷元件數(shù)的能力大幅增強(qiáng)；

b.在搜索過程中，采用自底向上的寬度優(yōu)先類搜索算法，明顯地降低了算法的時域復(fù)雜度，效率更高。

1 相關(guān)定義與定理

下面介紹一些MBD的概念和定理［12］。

定義1 被診斷系統(tǒng)。一個被診斷系統(tǒng)用一個三元組｛系統(tǒng)的模型描述（SD，the system description）；系統(tǒng)的觀測值（OBS，observation）；組成系統(tǒng)的元件集合（COMPS，the system components）｝來表示。

定義2 沖突集。 系統(tǒng)（SD，OBS，COMPS）的一個沖突集是一個元件集｛c1，…，ck｝?COMPS，它使得SD∪OBS∪｛?AB（c1），…，?AB（ck）｝是不可滿足的。一個沖突集是最小沖突集當(dāng)且僅當(dāng)它的任何一個真子集都不是沖突集。其中，一元謂詞AB意味著“abnormal”，AB（c1）表示元件 c1異常，?AB（c1）表示元件c1正常。

定義3 碰集。設(shè)C是一個沖突集合簇，C的碰集是一個集合H，H滿足2個條件：一個碰集是最小碰集當(dāng)且僅當(dāng)它的任何一個真子集都不是碰集。

定義4 碰集環(huán)境。設(shè)元件集合COMPS=｛c1，c2，…，cn｝中有 n 個元件，非空集合 E?COMPS，則稱E為碰集環(huán)境，顯然，系統(tǒng)中的碰集環(huán)境的個數(shù)為2n-1（n表示系統(tǒng)中元件的個數(shù)）。

定義5 候選碰集。如果E是某系統(tǒng)的碰集環(huán)境，則稱E為一個候選碰集。例如，某系統(tǒng)有元件集合｛A，B｝，則該系統(tǒng)的候選碰集有｛A｝、｛B｝、｛A，B｝。

定理1 Δ 是（SD，OBS，COMPS）的一個極小診斷，當(dāng)且僅當(dāng)Δ是（SD，OBS，COMPS）的最小沖突集的最小碰集。

2 算法描述

設(shè)有沖突集合簇 CS=｛C1，C2，…，Ck，…，Cm｝，k=1，…，m。

步驟1求出CS中的全部元件，記∪CS=｛C1∪C2∪C3∪…∪Cm｝=｛c1，c2，…，cn｝，系統(tǒng)中有 n 個元件。如果沖突集簇中含有超集，先要進(jìn)行超集刪除處理。

步驟2對系統(tǒng)的每個元件進(jìn)行二進(jìn)制編碼并得到一個碰集評判代碼。

a.沖突集合簇 CS=｛C1，C2，…，Ck，…，Cm｝，用一維數(shù)組B［m］存儲集合簇CS中各沖突集元素，即有B［m］=｛C1，C2，…，Ck，…，Cm｝，其中，B［1］=C1，B［2］=C2，…，B［m］=Cm。 對于元件 ci（1≤i≤m），如果 ci∈Ci（1≤i≤m），則用 1 表示；如果則用 0 表示；將二進(jìn)制碼0或1存入Ci在數(shù)組B［m］中所在的位置，此時的每個元件都會用一個由m個二進(jìn)制代碼組成的字符串表示。

b.沖突集合簇 CS=｛C1，C2，…，Ck，…，Cm｝，其碰集評判代碼為11…1（m個1）。

步驟3求出所有的碰集環(huán)境，即候選碰集，對于有n個元件的系統(tǒng)，則有2n-1個候選碰集，并對每個候選碰集進(jìn)行封裝，便于第5步的搜索。

步驟4對每個候選碰集，確認(rèn)彼此之間的父子關(guān)系。如果集合A?B，則稱A是B的子候選碰集，B是A的父候選碰集，顯然，對于一個集合而言，可能有3種情況：

a.可能有多個父候選碰集或多個子候選碰集；

b.可能同時存在父候選碰集和子候選碰集；

c.可能只存在父候選碰集或子候選碰集。

步驟5采用自底向上的寬度優(yōu)先類搜索算法進(jìn)行搜索，采用“邊搜索，邊計算，邊判斷，邊確認(rèn)”的策略，先對子候選碰集進(jìn)行判斷，將子候選碰集中的每個元件的二進(jìn)制代碼進(jìn)行“或”運算，如果運算結(jié)果和評判代碼一致，就可判斷該子候選碰集為碰集，則此時就不需要對其父候選碰集進(jìn)行判斷，否則，需要對其父候選碰集進(jìn)行判斷。此步驟結(jié)束以后，就得到所有的最小碰集，而且不會產(chǎn)生最小碰集超集，也不會漏掉最小碰集。

算法主要流程如圖1所示。

圖1 程序流程圖Fig.1 Flowchart of program

3 算法的實時性

求最小碰集時，影響其算法效率的有2個因素，分別為最小沖突集數(shù)和最小沖突集簇中所含的總元件數(shù)。因此，本文將二進(jìn)制編碼算法分別從這兩方面與 HS-TREE［12］、BHS-TREE［15］、邏輯數(shù)組算法［17］進(jìn)行比較，在 PC 機(jī)上（Celeron 2 GHz，1 GB，Windows XP）用MAPLE12仿真，得出下列2種情況的時間效率圖。

a.整個最小沖突集簇含M=30個元件，最小沖突集數(shù)不變，n=9，?。?，2，…，m），（2，3，…，m+1），…，（n，n+1，…，n+m+1）；m=5～9，得到最小沖突集元件數(shù)時間效率圖，如圖2所示。

b.當(dāng)n=9時，整個最小沖突集族中所含元件數(shù)M=26～30；得到最小沖突集簇元件數(shù)時間效率圖，如圖3所示。

圖2 每個最小沖突集元件數(shù)個數(shù)不同時間效率圖Fig.2 Curves of time needed vs.element number of each minimal conflict set for different algorithms

圖3 最小沖突集元件總數(shù)不同時間效率圖Fig.3 Curves of time needed vs.elements number of minimal conflict sets

可見，比較文獻(xiàn)［12］、［15］、［17］中的算法，本文提出的算法特點很明顯：算法時間效率與沖突集簇所含元件數(shù)及最小沖突集中所含的元件個數(shù)有關(guān)，這2種因素對二進(jìn)制編碼算法的時間效率影響較小。 若綜合上述 2 種因素，比較文獻(xiàn)［12］、［15］、［17］中的算法，二進(jìn)制編碼算法在時間效率上優(yōu)勢非常明顯。

4 配電網(wǎng)故障診斷

圖4為某10 kV配電網(wǎng)子網(wǎng)，它是具有7個節(jié)點的輻射型配電網(wǎng)絡(luò)，其中系統(tǒng)等效是指除了這7個節(jié)點外的完整配電網(wǎng)，它的作用相當(dāng)于電源，給這7個節(jié)點供電，從節(jié)點1到節(jié)點7都布置了相應(yīng)的信息采集裝置。記B3_A為節(jié)點3的A相母線，L57_B為節(jié)點5和節(jié)點7之間的B相輸電線，其他母線和線路的編號類似。

假設(shè)在該配電網(wǎng)中，線路L23_A發(fā)生短路接地和線路L57_B發(fā)生短路接地故障。采用文獻(xiàn)［20］中的方法對該配網(wǎng)進(jìn)行建模仿真，可得到最小沖突集MinCs：=｛｛B3_A，L23_A｝，｛B7_B，L57_B｝｝。

對于沖突集簇MinCs，采用二進(jìn)制編碼法計算最小碰集，具體過程如下。

步驟1求出沖突集簇MinCs中的全部元件為∪MCS=｛C1∪C2｝=｛B3_A，L23_A，B7_B，L57_B｝。

步驟 2 候選碰集有｛B3_A｝、｛L23_A｝、…、｛B3_A，L23_A，B7_B，L57_B｝等 15 個。

步驟3確認(rèn)候選碰集彼此間的父子關(guān)系，比如，｛B3_A｝?｛B3_A，L23_A｝，則｛B3_A｝是｛B3_A，L23_A｝的子候選碰集，｛B3_A，L23_A｝是｛B3_A｝的父候選碰集。

步驟4元件的二進(jìn)制代碼B3_A為10，L23_A為10，B7_B 為 01，L57_B 為 01；碰集評判代碼為 11。

步驟5自底向上進(jìn)行搜索確認(rèn)。先從元件最少的候選碰集進(jìn)行判斷，即從含有單個元件的候選碰集開始判斷，顯然，在此例中單元件的二進(jìn)制代碼均不與碰集評判標(biāo)準(zhǔn)一致，故單元件候選碰集都不可能成為最小碰集。再從雙元件的候選碰集進(jìn)行判斷，例如候選碰集｛L23_A，L57_B｝，元件L23_A的代碼10，元件L57_B的代碼01，將這2個元件的代碼進(jìn)行“或”運算，得11，正好與評判代碼一致，說明集合｛L23_A，L57_B｝為碰集，即為該配電網(wǎng)的一個候選診斷，不需要對其父候選碰集｛B3_A，L23_A，L57_B｝、｛B7_B，L23_A，L57_B｝、｛B3_A，B7_B，L23_A，L57_B｝等進(jìn)行判斷。如此進(jìn)行下去，直至找出所有最小碰集。最后，得到4個最小碰集，即4個候選診斷，為：MinHs：=｛［B3_A，B7_B］，［B3_A，L57_B］，［B7_B，L23_A］，［L23_A，L57_B］｝。

將本例所得的最小沖突集簇，用其他的最小碰集算法計算，花費時間如表1所示。

由此表進(jìn)一步可以看出，二進(jìn)制編碼法較文獻(xiàn)［12］、［15］、［17］中的最小碰集算法效率更高，有較好的實時性。

表1 各種最小碰集算法所需時間Tab.1 Time needed by different algorithms

5 結(jié)論

本文將求解最小碰集問題映射到二進(jìn)制數(shù)0/1邏輯“或”關(guān)系求解問題上，使得數(shù)據(jù)結(jié)構(gòu)更為簡單，實現(xiàn)算法與程序的一致。先求出系統(tǒng)的所有候選碰集，對系統(tǒng)中每個元件進(jìn)行二進(jìn)制編碼，然后采用自底向上的搜索方法，進(jìn)行搜索確認(rèn)，在確認(rèn)的過程中，使用二進(jìn)制代碼的邏輯“或”運算。算法易于編程實現(xiàn)，而且該算法在時間與空間復(fù)雜性上都表現(xiàn)出了較優(yōu)的性能。通過實驗仿真，與其他算法進(jìn)行比較，說明該算法具有良好的實時性，最后，以一個實際配電網(wǎng)診斷為例，更加充分地證明了二進(jìn)制編碼算法在處理復(fù)雜系統(tǒng)問題上的優(yōu)越性，實現(xiàn)了在很短的時間內(nèi)找到全部的最小碰集的目的。本文提出的算法可以為基于模型故障診斷中最小碰集的計算，尤其是復(fù)雜系統(tǒng)故障診斷（如配電網(wǎng)）提供有價值的參考。