基于Chwa ＆Hakimi模型的GA－BPFD算法

宣恒農(nóng)，劉田田，張潤馳

（南京財(cái)經(jīng)大學(xué) 信息工程學(xué)院，江蘇 南京210046）

0 引 言

對系統(tǒng)級故障診斷的研究是建立在故障模型基礎(chǔ)之上的［1－5］，主要模型有測試模型和比較模型兩類。系統(tǒng)故障診斷算法發(fā)展至今，研究成果頗豐。張大方等提出了集團(tuán)診斷算法，結(jié)合圖論的相關(guān)知識確定系統(tǒng)中的故障節(jié)點(diǎn)；筆者等建立了基于方程的診斷理論，根據(jù)測試結(jié)果矩陣直接求取絕對故障基方程診斷算法的最大特點(diǎn)是對系統(tǒng)中的故障節(jié)點(diǎn)數(shù)目無任何要求，不需要滿足t－可診斷性［6］。近年來，由于群體智能算法具有自學(xué)習(xí)、自組織、自適應(yīng)的特征和實(shí)現(xiàn)簡單、魯棒性強(qiáng)等優(yōu)點(diǎn)，運(yùn)用群體智能方法解決系統(tǒng)級故障診斷問題漸漸成為主流［7，8］。

1 相關(guān)研究

Elhadef等運(yùn)用遺傳算法 （genetic algorithm，GA）解決了PMC模型下的系統(tǒng)級故障診斷問題，李炯城等改進(jìn)了遺傳算法并取得良好的效果［9］；Mourad Elhadef等首次將BP神經(jīng)網(wǎng)絡(luò)應(yīng)用到Chwa ＆ Hakimi模型下的系統(tǒng)級故障診斷問題，得到了BPFD 智能診斷算法［5］，仿真結(jié)果表明，BPFD 算法具有極高的診斷精度。然而由于BP神經(jīng)網(wǎng)絡(luò)本身的局限性，初始參數(shù)的選擇對迭代次數(shù)與結(jié)果誤差的影響很大。本文將探究基于Chwa ＆ Hakimi模型，用遺傳算法對BPFD 算法進(jìn)行了改進(jìn)，提出了GA－BPFD算法。仿真結(jié)果表明，算法在穩(wěn)定性與時間復(fù)雜度方面具有明顯的優(yōu)越性。

根據(jù)Chwa ＆ Hakimi模型的定義，對于由n 個節(jié)點(diǎn)組成的系統(tǒng)v＝｛v1，v2…，vn｝，讓任意一對相鄰節(jié)點(diǎn)vi、vj（i≠j）執(zhí)行相同的測試任務(wù)，接著對所得結(jié)果進(jìn)行比較。若兩個節(jié)點(diǎn)的運(yùn)行結(jié)果一致，則這兩個節(jié)點(diǎn)都認(rèn)為對方通過了測試，否則，都認(rèn)為對方未通過測試。根據(jù)雙方的故障狀態(tài)可分為3種情況：正常節(jié)點(diǎn)與正常節(jié)點(diǎn)比較，其結(jié)果必為正常；正常節(jié)點(diǎn)與故障節(jié)點(diǎn) （或故障節(jié)點(diǎn)與正常節(jié)點(diǎn)）比較，其結(jié)果必為故障；故障節(jié)點(diǎn)與故障節(jié)點(diǎn)比較，其結(jié)果可能為正常，亦可能為故障。令vi＝0表示vi為正常節(jié)點(diǎn)，vi＝1表示vi為故障節(jié)點(diǎn)，用wij＝0 （或wji＝0）表示vi與vj的運(yùn)行結(jié)果一致，wij＝1 （或wji＝0）表示vi與vj的運(yùn)行結(jié)果不一致。將全部這樣的wij以i 為行號、j為列號的規(guī)則存儲在一個n 階矩陣W 中，稱W 為系統(tǒng)X 的一個測試癥候矩陣。

2 GA－BPFD算法的主要過程

對BP神經(jīng)網(wǎng)絡(luò)訓(xùn)練的過程就是對其權(quán)值和偏置值不斷優(yōu)化改進(jìn)的過程，初始參數(shù)的選擇十分關(guān)鍵，不當(dāng)?shù)某跏紖?shù)會使算法的解空間搜索范圍陷入局部。考慮到遺傳算法全局搜索的特點(diǎn)能有效克服BP 神經(jīng)網(wǎng)絡(luò)解的局限性問題，我們首先用遺傳算法生成BP神經(jīng)網(wǎng)絡(luò)的初始參數(shù)。

用GA 算法改進(jìn)BPFD 算法，重點(diǎn)需要考慮以下幾個問題：GA 算法初始種群的選取；適應(yīng)度函數(shù)的構(gòu)造；選擇、交叉和變異算子的設(shè)計(jì)；與BPFD 算法的結(jié)合方式等。下面我們對改進(jìn)算法進(jìn)行逐一分析。

為敘述方便，對 vi∈V（1≤i≤n）；我們用γ（vi）表示V 中所有與vi相鄰的節(jié)點(diǎn)構(gòu)成的集合，即γ（vi）＝｛vj｜vj∈V，（vi，vj）∈E｝；用e（vi）表示V 中所有與vi相接的邊構(gòu)成的集合，即e（vi）＝｛eij｜vj∈V，eij∈E｝。于是不難得到如下結(jié)論。

定理1 在Chwa ＆ Hakimi模型下，設(shè)故障模式與其癥候相容，則：

（1）若eij＝0，則ui－uj＝0；

（2）若eij＝1，則（ui＋uj－1）（ui－uj）＝0。

證明：當(dāng)故障模式與癥候S 相容時，根據(jù)Chwa ＆Hakimi模型的定義，若eij＝0，則必有ui＝uj＝0或ui＝uj＝1，于是有ui－uj＝0；若eij＝1，則必有ui＝0，uj＝1，或ui＝1，uj＝0，或ui＝uj＝1。顯然，上述3種情況均滿足（ui＋uj－1）（ui－uj）＝0。

綜上，定理1得證。

2.1 選取初始種群

我們先隨機(jī)生成GA 算法的初始種群，即BP神經(jīng)網(wǎng)絡(luò)的權(quán)值和偏置值，種群中個體的編碼采用實(shí)數(shù)編碼方式。

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

GA 算法的核心是適應(yīng)度函數(shù)的設(shè)置，設(shè)置的好壞直接影響算法的收斂速度和最終解的獲得。在本文中，適應(yīng)度函數(shù)fit采用BP神經(jīng)網(wǎng)絡(luò)中誤差平方和的倒數(shù)，即

式中：sol表示種群中的每個個體，種群中的個體數(shù)為n。實(shí)際輸出與期望值之間的差值越小，適應(yīng)度函數(shù)的值就越大。

2.3 設(shè)計(jì)選擇算子

通用的選擇操作包括輪盤賭、（μ＋λ）選擇和期望值選擇等方法。這里采用輪盤賭選擇方法：每個個體被選擇的概率與其在整個種群中的相對適應(yīng)度成正比 （因此該法又被稱為適應(yīng)度比例選擇法）。具體步驟如下：

步驟1 計(jì)算每個個體在輪盤中的選擇概率。設(shè)種群數(shù)目為n；個體適應(yīng)度為fit（sol），則sol 被選擇的概率P（sol）為

顯然，個體的適應(yīng)度越大，被選中的概率也就越高。

步驟2 計(jì)算每個個體的累加概率，其中

步驟3 在輪盤中隨機(jī)選擇n 次，其具體的選擇方法如下：

（1）產(chǎn)生一個 ［0，1］之間的隨機(jī)數(shù)r；

（2）如果r＜q1，則選擇第1個個體，若qi－1＜r≤qi，則選擇第i個個體。

通過上述方法，適應(yīng)度高的個體會被盡可能地保存至下一代。

2.4 設(shè)計(jì)交叉算子

由于采用實(shí)數(shù)編碼的方式，因此采用簡單交叉的方法。根據(jù)交叉概率pc，從種群P1中選擇pc＊t個個體與種群P1中的個體進(jìn)行單點(diǎn)交叉。具體步驟如下：

步驟1 比較兩個個體的基因不同的位；

步驟2 列出基因不同位基因的所有組合，選出其中滿足t－可診斷性的個體，并按適應(yīng)度值由高到低的順序排列；

步驟3 選出適應(yīng)度最高的兩個個體作為雜交后的最終個體。

2.5 設(shè)計(jì)變異算子

變異的操作很大程度上依賴于變異概率pm，根據(jù)變異率pm選擇變異個體，當(dāng)適應(yīng)度函數(shù)值小于變異概率時，進(jìn)行基因翻轉(zhuǎn)操作。

2.6 GA算法與BPFD算法的結(jié)合

步驟1 通過以上步驟將得到誤差最小的一組神經(jīng)網(wǎng)絡(luò)權(quán)值和偏置值，并以此作為神經(jīng)網(wǎng)絡(luò)的初始權(quán)值；

步驟2 通過前向計(jì)算、誤差的計(jì)算、反向傳播和權(quán)值更新等操作進(jìn)行神經(jīng)網(wǎng)絡(luò)的訓(xùn)練；

步驟3 判斷是否滿足精度要求，若達(dá)到要求即輸出結(jié)果，否則再次進(jìn)行訓(xùn)練。

由于經(jīng)過了遺傳算法的全局搜索，所以再次陷入局部極小值的可能性不大。

3 GA－BPFD算法的步驟與效率分析

在上述步驟的基礎(chǔ)上，我們將GA－BPFD 算法的完整過程總結(jié)如下：

輸入：測試報(bào)告

輸出：故障集F，無故障集FF

算法流程如圖1所示，上述的6 個步驟順序執(zhí)行，我們逐步分析算法的時間復(fù)雜度。第一步，初始化隨機(jī)生成初始種群P0，種群大小為n，時間復(fù)雜度為Ο（n）；第二步，計(jì)算每個個體的適應(yīng)度，遍歷整個種群，種群大小為n，時間復(fù)雜度為Ο（n）；第三步，采用輪盤賭法進(jìn)行選擇，計(jì)算個體的適應(yīng)度總和時復(fù)雜度為Ο（n），選擇過程中共進(jìn)行了n次，所以時間復(fù)雜度為Ο（n）；第四步，交叉過程中采用的是單點(diǎn)交叉，最壞的情況是所有的個體均參與了交叉，時間復(fù)雜度為O（n2），最好的情況是無種群個體參與交叉，時間復(fù)雜度為O（1）；第五步，最壞情況下，所有種群個體均發(fā)生了變異，時間復(fù)雜度為O（n2），最好情況下，沒有個體發(fā)生變異，時間復(fù)雜度為O（1）；第六步，神經(jīng)網(wǎng)絡(luò)訓(xùn)練，時間復(fù)雜度為O（n2）。

圖1 GA－BPFD算法流程

因此，算法總的時間復(fù)雜度為Ο（n）＋Ο（n）＋Ο（n）＋Ο（n）＋Ο（n2）＋Ο（n2）＋Ο（n2）＝O（n2），即在最壞情況下，時間復(fù)雜度均為O（n2）。BPFD 算法為了避免得到的是局部最優(yōu)解，增加了相應(yīng)的額外步驟，算法的時間復(fù)雜度為Ο（n3）。相較之下，GA－BPFD 算法有效地降低了診斷的時間復(fù)雜度。

4 實(shí)驗(yàn)仿真

我們對GA－BPFD算法與BPFD 算法進(jìn)行了仿真比較。仿真均在一臺配置為Core（TM）2 2.33GHz CPU，2.00 G 內(nèi) 存 的 計(jì) 算 機(jī) 上 用Matlab 語 言 編 程 實(shí) 現(xiàn)［10－12］。根 據(jù)Chwa ＆ Hakimi模型，我們首先隨機(jī)生成不同規(guī)模的網(wǎng)絡(luò)拓?fù)溥B接圖與符合t－可診斷性的故障模式，通過模擬測試，得出測試報(bào)告，以此作為算法的輸入。

當(dāng)種群大小設(shè)置為50，迭代次數(shù)設(shè)置為100、200時，由本文提出的方法進(jìn)行遺傳迭代得到誤差平方和變化曲線圖，如圖2 （a）、（b）、（c）所示，從圖2中我們可以看到，由100－200代，誤差平方和下降基本趨于一個穩(wěn)定最小值，在訓(xùn)練過程中誤差趨于最小，這說明了改進(jìn)算法分析實(shí)現(xiàn)的合理性。而適應(yīng)值在50－60代內(nèi)趨于穩(wěn)定并得到最優(yōu)的初始權(quán)值，這將作為BPFD 算法訓(xùn)練的初始權(quán)值。

圖3展示了當(dāng)系統(tǒng)節(jié)點(diǎn)數(shù)為200 時，兩個算法的均方根誤差、診斷時間和故障單元數(shù)的綜合比較。根據(jù)系統(tǒng)的t－可診斷性，故障節(jié)點(diǎn)的數(shù)目從1 遞增到99。圖4 展示了隨著系統(tǒng)規(guī)模的增加，兩種算法在CPU 運(yùn)行時間方面的比較，更加凸顯了改進(jìn)后的算法的優(yōu)越性。

結(jié)合大量實(shí)驗(yàn)的結(jié)果，我們得出以下結(jié)論：

對于診斷誤差，如圖3所示，GA－BPFD 算法的診斷誤差較小，在準(zhǔn)確性上要優(yōu)于BPFD 算法；在診斷的穩(wěn)定性方面，BPFD 算法的穩(wěn)定性較差，而GA－BPFD 算法診斷結(jié)果則趨于穩(wěn)定；在算法的泛化性能上，由于BP網(wǎng)絡(luò)的性能評價函數(shù)值與誤差呈負(fù)相關(guān)，改進(jìn)后的GA－BPFD 算法的輸出誤差較改進(jìn)前有了極大降低。而隨著故障節(jié)點(diǎn)數(shù)的增加，算法診斷的誤差并沒有隨之增大，在保證算法訓(xùn)練精度的同時，網(wǎng)絡(luò)的泛化精度也能得到滿意值；在診斷時間方面，如圖4 所示，隨著系統(tǒng)規(guī)模節(jié)點(diǎn)數(shù)的不斷增大，BPFD 與GA－BPFD 算法所用時間也相應(yīng)增加。但GABPFD 算法所用時間明顯少于BPFD 算法所用時間，隨著系統(tǒng)規(guī)模的增大，尤其實(shí)在節(jié)點(diǎn)數(shù)目大于100 以后，GABPFD 算法的時間效率要明顯高于BPFD 算法。

5 結(jié)束語

圖2 GA 的預(yù)處理

本文提出了GA－BPFD算法。與BPFD 算法相比，GABPFD 算法由于預(yù)先以GA 算法進(jìn)行參數(shù)預(yù)處理，得到了一個較為優(yōu)越的初始權(quán)值與偏置值，大幅降低了算法在BP神經(jīng)網(wǎng)絡(luò)迭代學(xué)習(xí)過程中非必要的迭代運(yùn)算，使得算法在進(jìn)行故障診斷時收斂速度加快，總體的時間復(fù)雜度降低；同時對BP神經(jīng)網(wǎng)絡(luò)泛化能力的分析可知，在訓(xùn)練過程中算法對不同樣本值也能給出準(zhǔn)確的診斷。

對于BP神經(jīng)網(wǎng)絡(luò)泛化性能的研究，目前還處在初級階段。通過對神經(jīng)網(wǎng)絡(luò)本身性質(zhì)的研究來改進(jìn)算法性能，將會是進(jìn)一步的研究方向。同時，其它智能算法，如模擬退火等對BPFD 算法改進(jìn)的研究還有待進(jìn)一步探討。

實(shí)際上，GA－BPFD算法不僅僅適用于Chwa ＆Hakimi模型，對于PMC 模型、BGM 模型和Malek模型，只要根據(jù)各模型的特征，將算法進(jìn)行相應(yīng)調(diào)整，亦可適用。因篇幅所限，我們將另文專述。

圖3 系統(tǒng)規(guī)模為200時誤差和時間比較

圖4 CPU 時間隨節(jié)點(diǎn)增加的變化

［1］Wu X，Zhu X，Wu GQ，et al.Data mining with big data［J］.IEEE Transactions on Knowledge and Data Engineering，2014，26 （1）：97－107.

［2］Ui－Min Choi，Kyo－Beum Lee，Blaabjerg F.Diagnosis and tolerant strategy of an open－switch fault for t－type three－level inverter systems［J］.IEEE Transactions on Industry Applications，2014，50 （1）：495－508.

［3］Mourad Elhadef.Solving the PMC－based system－level fault diagnosis problem using hopfield neural networks ［J］.IEEE International Conference on Advanced Information Networking and Applications，2011：216－223.

［4］Mourad Elhadef.A modified hopfield neural network for diagnosing comparison－based multiprocessor systems using partial syndromes［J］.IEEE 17th International Conference on Parallel and Distributed Systems，2011：646－653.

［5］Mourad Elhadef，Amiya Nayak.Comparison－based systemlevel fault diagnosis：A neural network approach ［J］.IEEE Transactions on Parallel and Distributed Systems，2012，23（6）：1047－1059.

［6］XUAN Hengnong，HE Tao，XU Hong，et al.Two points diagnostic algorithm based on Chwa ＆Hakimi fault model［J］.Computer Engineering and Applications，2010，46 （5）：66－68（in Chinese）. ［宣恒農(nóng)，何濤，許宏，等.基于Chwa ＆Hakimi故障模型的二分診斷算法 ［J］.計(jì)算機(jī)工程與應(yīng)用，2010，46 （5）：66－68.］

［7］Arora S，Singh S.The firefly optimization algorithm：Convergence analysis and parameter selection ［J］.International Journal of Computer Applications，2013，69 （3）：48－52.

［8］Yang XS，He X.Firefly algorithm：recent advances and applications ［J］.International Journal of Swarm Intelligence，2013，1 （1）：36－50.

［9］LI Jiongcheng，WANG Yangyang，LI Guiyu，et al.Rapid convergence of hybrid genetic algorithm ［J］.Computer Engineering and Design，2014，35 （2）：686－689 （in Chinese）.［李炯城，王陽洋，李桂愉，等.快速收斂的混合遺傳算法［J］.計(jì)算機(jī)工程與設(shè)計(jì)，2014，35 （2）：686－689.］

［10］Wan Weishui，Shingo Mabu，Kaoru Shimada，et al.Enhancing the generalization ability of neural networks through controlling the hidden layers ［J］.Applied Soft Computing，2009，9 （1）：404－414.

［11］ZHU Kai.Proficient in MATLAB neural network ［M］.Beijing：Electronic Industry Press，2010 （in Chinese）. ［朱凱.精通 MATLAB 神 經(jīng) 網(wǎng) 絡(luò) ［M］.北 京：電 子 工 業(yè) 出 版社，2010.］

［12］Nakama T.Theoretical analysis of batch and on－line training for gradient descent learning in neural networks ［J］.Neural Computing，2009，73 （1－3）：151－159.