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

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

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

0 引 言

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

1 相關研究

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

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

2 GA－BPFD算法的主要過程

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

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

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

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

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

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

證明：當故障模式與癥候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 選取初始種群

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

2.2 構造適應度函數(shù)

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

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

2.3 設計選擇算子

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

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

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

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

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

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

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

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

2.4 設計交叉算子

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

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

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

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

2.5 設計變異算子

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

2.6 GA算法與BPFD算法的結合

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

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

步驟3 判斷是否滿足精度要求，若達到要求即輸出結果，否則再次進行訓練。

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

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

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

輸入：測試報告

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

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

圖1 GA－BPFD算法流程

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

4 實驗仿真

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

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

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

結合大量實驗的結果，我們得出以下結論：

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

5 結束語

圖2 GA 的預處理

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

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

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

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

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

［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］.計算機工程與應用，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］.計算機工程與設計，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) 絡 ［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.