一種基于模型的配電網故障診斷搜索算法

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

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

0 引言

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

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

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

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

b.所建立的樹或者圖，數據結構復雜而且計算量大［12-14］；

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

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

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

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

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

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

1 相關定義與定理

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

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

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

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

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

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

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

2 算法描述

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

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

步驟2對系統的每個元件進行二進制編碼并得到一個碰集評判代碼。

a.沖突集合簇 CS=｛C1，C2，…，Ck，…，Cm｝，用一維數組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 表示；將二進制碼0或1存入Ci在數組B［m］中所在的位置，此時的每個元件都會用一個由m個二進制代碼組成的字符串表示。

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

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

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

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

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

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

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

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

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

3 算法的實時性

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

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

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

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

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

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

4 配電網故障診斷

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

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

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

步驟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確認候選碰集彼此間的父子關系，比如，｛B3_A｝?｛B3_A，L23_A｝，則｛B3_A｝是｛B3_A，L23_A｝的子候選碰集，｛B3_A，L23_A｝是｛B3_A｝的父候選碰集。

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

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

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

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

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

5 結論

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