離散二進制粒子群算法在基于模型配電網(wǎng)故障診斷中的應(yīng)用

關(guān) 龍 ，劉志剛 ，何士玉 ，楊紅梅

（1.西南交通大學(xué) 電氣工程學(xué)院，四川 成都 610031；2.中國能源建設(shè)集團安徽省電力設(shè)計院，安徽 合肥 230601）

0 引言

基于模型診斷 MBD（Model-Based Diagnosis）是為了克服傳統(tǒng)專家系統(tǒng)診斷方法的不足而提出的一種推理方法，它對人工智能領(lǐng)域的研究具有重大意義［1-3］。MBD把診斷推理過程與系統(tǒng)模型分開，具有很好的移植性，已經(jīng)廣泛應(yīng)用于工程、航天、電路診斷等領(lǐng)域［4-6］。

MBD方法一般先根據(jù)系統(tǒng)的描述和觀測，得到極小沖突集，然后通過計算最小沖突集MCS（Minimal Conflict Set）的最小碰集，得到系統(tǒng)的極小診斷。許多學(xué)者對計算最小碰集算法進行了深入研究，文獻［7-9］中提出的 HS-Tree、HST-Tree、BHS-Tree 等樹形搜索算法，需要建立樹或者圖，而且可能因為剪枝問題而丟失正確解，算法實現(xiàn)比較繁瑣并且計算效率較低。文獻［10-11］中提出的布爾代數(shù)、邏輯數(shù)組方法則需先存儲所有碰集，通過化簡才能得到所有的最小碰集集合。文獻［12］中提出的遺傳算法（GA）只能快速計算出95%的最小碰集，并不能保證所有輸出結(jié)果都為最小碰集。

離散二進制粒子群優(yōu)化（BPSO）算法由Kennedy和Eberhart在1997年首次提出［13］。BPSO算法本質(zhì)上是屬于迭代的隨機搜索算法，具有并行處理特征，魯棒性好，易于實現(xiàn)，原理上可以以較大的概率找到優(yōu)化問題的全局最優(yōu)解，并且具有較快的收斂速度和較高的計算效率，在許多領(lǐng)域得到廣泛應(yīng)用?；诖?，本文在基于模型的配電網(wǎng)診斷實例中，將計算最小碰集問題轉(zhuǎn)化為0、1表示的二值空間問題，并且引入離散BPSO算法用于求解沖突集的最小碰集，取得了很好的效果。

1 MBD的基本概念

MBD的目的是辨識出故障部件，所以模型必須清楚地表示設(shè)備的部件和行為模式。1987年Reiter首次將MBD原理用一階邏輯表示出來［14-15］。在診斷的邏輯表示中，系統(tǒng)可以用一個三元組（SD，OBS，COMP）來表示，其中SD為系統(tǒng)的模型描述一階語句，OBS為系統(tǒng)的觀測值一階語句，COMP為組成系統(tǒng)的元件集合。MBD領(lǐng)域中的常用基本概念介紹如下。

沖突集：元件集 C 是系統(tǒng)（SD，OBS，COMP）的一個沖突集（CSC），C必須滿足2個條件：

a.C=｛c1，c2，…，cn｝?COMP；

如果C的任一真子集都不是沖突集，則稱C是最小沖突集。

在沖突集中至少有一個元件存在故障，這樣才能解釋系統(tǒng)模型預(yù)期和實際觀測差異存在的原因。

碰集：設(shè)CS是一個沖突集簇（即由集合組成的集合），H是CS的一個碰集，H必須滿足2個條件：如果H的任一真子集都不是碰集，則稱H是最小碰集。

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

由定理1可知，如果知道了系統(tǒng)所有的最小沖突集，可以通過計算最小沖突集的最小碰集，得到極小診斷結(jié)果。

2 基于BPSO算法的最小碰集搜索算法

2.1 標準BPSO算法

為解決離散或二進制變量的優(yōu)化問題，文獻［16］提出了BPSO算法。該算法用二進制編碼方式來表示空間中的某一維是否被選擇，粒子位置xid每一維被限制為1或者0，用速度vid表示位置狀態(tài)改變的可能性，速度代表粒子位置接近于1的概率，vid越大，xid為 1 的概率越大，它被限制在［0，1］之間，由 sig（）函數(shù)實現(xiàn)，其速度和位置更新公式如下：

2.2 基于BPSO算法的最小碰集算法原理

沖突集是由若干系統(tǒng)元件組成，在這些元件中至少有一個元件是故障元件，這樣才能解釋系統(tǒng)模型預(yù)期和實際觀測差異存在的原因。將每個沖突集CSC映射成0、1表示的N維二值集合，其中N代表全部沖突集中系統(tǒng)元件的規(guī)模（問題規(guī)模）。每一系統(tǒng)元件存在0、1這2種狀態(tài)，0表示正常狀態(tài)，1表示故障狀態(tài)。初始化粒子X為P×N維的隨機二值矩陣，P表示粒子群的種群規(guī)模。每次迭代過程中，通過適應(yīng)度函數(shù)評價各粒子位置優(yōu)劣，更新粒子的當(dāng)前最優(yōu)位置和全體粒子的最優(yōu)位置，進而更新粒子的速度和位置，直到滿足迭代次數(shù)為止。最終得出的粒子群的全局最優(yōu)位置就是所求所有沖突集的最小碰集。

2.3 構(gòu)造適應(yīng)度函數(shù)

適應(yīng)度是評價粒子優(yōu)劣的唯一指標，因此構(gòu)造合適的適應(yīng)度函數(shù)就尤為重要。適應(yīng)度函數(shù)不僅要能夠準確評價一個粒子是否為最小碰集，而且還要盡可能提高粒子群算法的搜索效率。為此，本文定義的粒子適應(yīng)度函數(shù)如下：

其中，P為粒子群的種群規(guī)模，hnum為粒子X和沖突集簇CS中每個沖突集都有交集的二值集合個數(shù)，h為粒子X中包含的不同二值集合的數(shù)目。

由于本文的算法是為了找出所有的最小碰集，所以粒子的適應(yīng)度值越大越好。又因為hnum和h最大值只可能為P，所以適應(yīng)度函數(shù)最大值為1。在得到最優(yōu)適應(yīng)度函數(shù)對應(yīng)的二值矩陣后，矩陣中每一行對應(yīng)的二值集合即為一個最小碰集集合。

2.4 提高算法性能的改進措施

a.線性遞減慣性權(quán)重策略。

Y.Shi和R.C.Eberhart建議在粒子群算法中采用線性遞減權(quán)重策略［17-18］，如式（4）所示，該策略使得粒子群算法在開始時探索較大的區(qū)域，快速定位最優(yōu)解的大致位置，隨著wt逐漸減小，粒子速度減慢，著重局部搜索。本文采用的辦法是將wt初始化為0.9，并隨迭代次數(shù)的增加遞減至0.4，以達到較好的全局和局部搜索能力，并在診斷實例中與wt取常值時的算法性能進行比較。

其中，wint、wend、Tmax分別為初始權(quán)重系數(shù)、最終權(quán)重系數(shù)、最大迭代次數(shù)。

b.最小碰集保證策略。

為了加速離散BPSO算法的搜索效率并且保證最終輸出結(jié)果全為最小碰集，提出最小碰集保證策略，其主要過程如下。

步驟1迭代過程中，以二值矩陣每一行對應(yīng)的二值集合為操作對象，通過適應(yīng)度函數(shù)判斷其是否為碰集，若是則轉(zhuǎn)步驟2，否則，轉(zhuǎn)步驟3。二值矩陣中全部二值矩陣遍歷結(jié)束，算法結(jié)束，保存遍歷結(jié)果，繼續(xù)進行下一次迭代。

步驟2掃描當(dāng)前二值集合，當(dāng)對應(yīng)維數(shù)為1時，將其置為0，再利用適應(yīng)度函數(shù)對其進行適應(yīng)度評估，若還是碰集則保留變化，否則恢復(fù)原先數(shù)值，若當(dāng)前二值集合掃描完成，操作結(jié)束，轉(zhuǎn)步驟1。

步驟3掃描當(dāng)前二值集合，當(dāng)對應(yīng)維數(shù)為0時，將其置為1，對其進行適應(yīng)度評估，若適應(yīng)度函數(shù)值增加則保留變化，否則恢復(fù)原先數(shù)值，若當(dāng)前二值集合掃描完成或者當(dāng)前二值集合已為碰集集合，則操作結(jié)束，轉(zhuǎn)步驟1。

通過最小碰集保證策略，二值矩陣每一行對應(yīng)的二值集合全為最小碰集，它滿足最小碰集基本條件，本身為碰集集合，并且它的所有子集都不是碰集集合。通過診斷實例驗證表明改進算法在收斂速度和全局搜索性能等方面均有很大優(yōu)勢，并且保證最終輸出結(jié)果全為最小碰集。

2.5 算法流程

a.初始化粒子群：初始化粒子X為P×N維的隨機二值矩陣。對粒子群規(guī)模P、慣性權(quán)重w、學(xué)習(xí)因子c1和c2、迭代次數(shù)等參數(shù)進行初始化設(shè)置。定義全局變量xhit來存儲所有最小碰集。

b.計算每個粒子的適應(yīng)值，選取粒子個體極值Pbestid和粒子群的全局極值Gbestid。

c.按照速度-位置模型式（1）、（2）更新粒子群的速度和位置，并根據(jù)適應(yīng)度值更新粒子個體極值和粒子群的全局極值Gbestid，采用最小碰集保證策略遍歷當(dāng)前二值矩陣，將粒子中是沖突集CSC最小碰集的粒子添加到xhit。

d.若達到最大迭代次數(shù)，算法終止。輸出集合xhit，即為沖突集簇CS的最小碰集。

3 診斷實例分析

3.1 基于模型的配電網(wǎng)診斷方案

MBD方法的診斷過程主要包括系統(tǒng)建模、沖突識別、候選產(chǎn)生、診斷鑒別4個階段。借鑒文獻［19-20］中的方法，給出了一個將MBD理論應(yīng)用于實際配電網(wǎng)的診斷方案，如圖1所示。

圖1 基于模型的配電網(wǎng)故障診斷步驟Fig.1 Flowchart of model-based fault diagnosis for distribution network

a.建立配電網(wǎng)設(shè)計原理模型。通過描述系統(tǒng)中元件內(nèi)部的約束方程、元件與元件之間的連接關(guān)系，建立整個配電網(wǎng)系統(tǒng)的結(jié)構(gòu)、功能和行為模型。建模時采用分層的結(jié)構(gòu)抽象模型方案［21-22］，不僅可以依據(jù)此模型診斷出全部系統(tǒng)故障，而且模型簡單實用。

b.沖突識別。針對設(shè)計原理模型及觀測信息的分布固定不變的特點，將最小沖突集的搜索問題分為離線搜索最小沖突集候選［23］與在線識別最小沖突集2個步驟。這種策略能夠明顯減小在線搜索最小沖突集的空間，使得實際診斷時具有較好的實時性。根據(jù)配電網(wǎng)設(shè)計原理模型和觀測數(shù)據(jù)，得到所有最小沖突集。

c.候選產(chǎn)生。通過計算診斷識別過程中得到的最小沖突集的最小碰集，得到系統(tǒng)的極小診斷候選。本文引入改進的離散BPSO算法用于求解沖突集的最小碰集。

d.診斷識別。通過診斷識別對得到的多個診斷候選作進一步區(qū)分，以獲得最佳的診斷結(jié)論。依據(jù)系統(tǒng)元件的先驗故障概率定性值，采用貝葉斯定理計算所得的侯選診斷的后驗故障概率，并進行故障概率排序，優(yōu)先選擇故障概率值較大的候選診斷作為故障點。

3.2 基于模型的配電網(wǎng)診斷實例

圖2為某10 kV配電網(wǎng)子網(wǎng)，節(jié)點1—7都布置了相應(yīng)的采集信息裝置（即電壓和電流互感器），故障發(fā)生時，可準確測量配電網(wǎng)的故障狀態(tài)信息。母線節(jié)點和輸電線路的先驗故障概率假設(shè)如下：母線節(jié)點的故障概率均為0.1；輸電線路故障概率都為0.4。

圖2 某10 kV配電網(wǎng)Fig.2 A 10 kV distribution network

假設(shè)在該配電網(wǎng)中，線路L23_A和線路L67_B發(fā)生短路接地故障，通過PSCAD軟件仿真獲得在此故障情況下配電網(wǎng)內(nèi)的各互感器的測量值，將電流、電壓互感器測得的配電網(wǎng)的故障狀態(tài)信息，代入到離線搜索時得到最小沖突集候選MCSC（Minimal Conflict Set Candidate）所對應(yīng)的解析冗余關(guān)系中，得到各解析冗余關(guān)系的殘差如表1所示。其中殘差定義為：一條解析冗余關(guān)系是從牽引變電站系統(tǒng)模型中得出的只含有系統(tǒng)可觀測變量的約束方程，該方程在給定任意一組觀測值后能夠被求值，模型值與實際值之間的差值稱為殘差。

從表1中選擇相對殘差r′＞0.4的最小沖突集候選，得到最小沖突集為：MCS：=｛MCSC1，MCSC8｝，即MCS：=｛｛B3_A，L23_A｝，｛B7_B，L67_B｝｝，B3_A 表示節(jié)點3出現(xiàn)A相故障，L23_A表示節(jié)點2與節(jié)點3之間導(dǎo)線出現(xiàn)A相故障，其他類似。

表1 解析冗余關(guān)系的殘差Tab.1 Residue of analytic redundancy relations

采用改進的離散BPSO算法求解沖突集的最小碰集，從而得到配電網(wǎng)系統(tǒng)的所有最小候選診斷MHS（Minimal Hitting Set）。參數(shù)設(shè)置如下：搜索空間維數(shù)為20，粒子群規(guī)模為80，最大迭代次數(shù)為100，學(xué)習(xí)因子c1=2.5，c2=1.5。得到最小候選診斷為MHS：=｛［B3_A，B7_B］，［B3_A，L67_B］，［B7_B，L23_A］，［L23_A，L67_B］｝。

最小候選診斷的后驗故障概率排序結(jié)果見表2。

表2 最小候選診斷的后驗故障概率排序Tab.2 Sorting of minimal candidate diagnosis according to fault probability

由表2可知候選診斷［L23_A，L67_B］后驗故障概率最大，因此，可判斷線路L23_A和線路L67_B存在故障，與假設(shè)結(jié)果相符。

3.3 算法性能分析

配電網(wǎng)故障診斷實例中，引入改進BPSO算法求取沖突集的最小碰集，并對比不同最小碰集搜索算法性能及不同慣性權(quán)重策略對算法收斂性的影響。試驗機器配置為：CPU P4200 GHz，內(nèi)存512 MB，操作系統(tǒng)Windows XP，程序使用Visual C++6.0編譯。

a.慣性權(quán)重對算法性能的影響。

慣性權(quán)重w分別取1、0.8以及采用線性遞減慣性權(quán)重策略，計算診斷實例中得到?jīng)_突集的最小碰集，搜索結(jié)果如表3所示。采用不同的慣性權(quán)重策略，離散BPSO算法均可以搜索到所有的最小碰集，但是采用線性遞減慣性策略明顯可以提高算法的收斂性和全局搜索能力，提高計算效率，算法性能優(yōu)于慣性權(quán)重取常數(shù)的情況。

表3 不同慣性權(quán)重下算法性能的比較Tab.3 Comparison of algorithm performance among different inertia weights

b.改進策略有效性驗證。

為進一步驗證離散BPSO算法求取沖突集的最小碰集的可行性，將離散BPSO算法與HS-Tree算法［7］、Boolean Algebra 方 法［10］、遺傳算法［12］等算法搜索性能進行比較，引用文獻［10］中算例：假設(shè)沖突集簇中均有10個最小沖突集，各最小沖突集分別為｛1，2，…，l｝、｛2，3，…，l+1｝、…、｛n，n+1，…，n+l-1｝，問題規(guī)模（即 n+l-1）分別取 5、15、25、…、85，實驗結(jié)果如圖3所示。

圖3 幾種最小碰集算法搜索效率比較Fig.3 Comparison of search efficiency among several minimum hitting set algorithms

離散BPSO算法對沖突集規(guī)模不太敏感，適用于求解問題規(guī)模較大時的情況，問題規(guī)模越大，BPSO算法相對其他最小碰集算法的搜索效率越高。由實驗結(jié)果可知，BPSO算法有較高的計算效率和較快的收斂速度，求解時間節(jié)省了約1/3～1/2，尤其HSTree算法和Boolean Algebra方法在問題規(guī)模達到50時出現(xiàn)了由于內(nèi)存溢出而終止的情況，說明算法實現(xiàn)比較繁瑣，而BPSO算法對問題規(guī)模并不敏感，有效避免此種情況的發(fā)生。

4 結(jié)論

采用基于模型的配電網(wǎng)故障診斷方法，可以直接利用量測量來判斷故障元件，而不必在故障后根據(jù)保護和斷路器動作信息來進行故障定位，具有較好的實時性。以某10 kV配電網(wǎng)為診斷實例，通過實際建模、編程和實驗表明MBD配電網(wǎng)故障診斷方法可以快速準確地診斷出故障元件，取得較好效果。

本文引入離散BPSO算法應(yīng)用于基于模型的配電網(wǎng)故障診斷中極小診斷的求解，并提出算法的改進策略，進一步提高了BPSO算法的搜索效率和收斂速度。BPSO算法有較快的收斂速度，相對于HS-Tree算法、Boolean Algebra方法、遺傳算法等常用最小碰集算法搜索效率更高，并且當(dāng)問題規(guī)模較大時不會出現(xiàn)內(nèi)存溢出的問題。但是BPSO算法并不能保證得到全部的最小碰集，當(dāng)問題規(guī)模過大時，只能快速地搜索出98%～100%的最小碰集，在后續(xù)的研究中，如何進一步提高BPSO的最小碰集算法的正確率和搜索效率仍是本課題研究的重點。