一種PMC模型下的系統級故障診斷煙花算法

歸偉夏，陸 倩

(廣西大學 計算機與電子信息學院，南寧 530004)

1 引 言

隨著計算機技術的飛速發展，單個計算機的運算能力已經遠遠不能滿足人們的需求，取而代之的是更為復雜的多處理器系統.現如今，多處理器系統已經滲透到我們生活中的諸多領域，如天文計算、金融、交通管理、軍事等.但是，多處理器系統給我們帶來諸多便利的同時，也存在著一些潛在的風險和隱患.隨著并行計算機規模的不斷擴大，系統的復雜程度不斷提高，處理器結點出現故障的概率也隨之增大，從中找出故障結點的工作也隨之變得愈來愈繁重，其花費也愈來愈高，而一些關鍵性業務一般是不允許存在安全隱患的，或者在發生故障的時候，需要以很小的代價檢測出并排除故障，如網上銀行、電子貨幣、核武器研制等.為了使系統能夠安全可靠的運行，出現故障的處理器必須排除，因此，如何使系統安全運行已經成為一個非常迫切的問題，故障診斷則成為了解決這類問題的重要手段.

Preparata等人在文獻[1]中首次提出PMC模型并利用圖論的思想解決系統故障診斷問題，在隨后幾十年的研究中，人們先后提出了BGM[2]、Chwa & Hakimi[3]以及Malek[4]故障診斷模型.隨著系統級故障診斷研究的不斷深入，Mourad Elhadef和Bechir Ayeb等人在文獻[5]中首次運用遺傳算法(Genetic Algorithm)來解決PMC模型下的系統級故障診斷問題.此后文獻[6]通過對遺傳算法的不斷改進，取得更高效的診斷效果.在文獻[7]中，Mourad Elhadef和Amiya Nayak則首次將BP神經網絡算法應用于Chwa & Hakimi故障模型下的系統級故障診斷中.張大方等人在文獻[8]中提出集團的概念和求法，以t-可診斷系統為前提，從另一個角度較好地解決了系統級故障診斷問題.在此基礎上，宣恒農等人提出了一種基于矩陣運算的貪婪診斷算法[9].在文獻[10]中，考慮到大多數網絡中都存在星型結構，于是在故障診斷度已確定并且能夠構造出擴展星型結構的多處理機系統的基礎上，提出了一種擴展星型結構算法.隨著群體智能算法的廣泛應用，文獻[11]利用PMC模型的特點，優化了初始種群的質量，同時對親和度函數進行了修改，并考慮到了故障集合的所有癥候.文獻[12]則將蝙蝠算法應用于系統級故障診斷中，提出了新的初始化方法并改進了適應度函數和速度更新公式，進一步提高t-可診斷系統下的診斷效果.文獻[13]中提出了PMC模型下的貝殼漫步優化(MWOFD)算法以及Chwa & Hakimi模型下的布谷鳥-BP神經網絡(CS-BPFD)算法，都取得了較好的效果.文獻[14]則面向Malek比較模型，通過對遺傳算法改進，將其應用于系統故障診斷中.由系統級故障診斷研究的發展過程不難看出，基于現代群體智能算法的系統級故障診斷已逐漸成為一種研究趨勢.

與遺傳算法等常見現代群體智能算法不同，煙花算法采用的是爆炸搜索的機制.煙花個體之間通過競爭與協作進行相互作用，根據每個煙花個體的適應度值來計算得出每個煙花的爆炸半徑和爆炸生成的火花數量，使得適應度值較差的煙花的爆炸半徑越大，且爆炸生成的火花數量越少，而適應度值較好的煙花的爆炸半徑越小，且爆炸生成的火花數量越多.這種分布式信息共享機制不僅能使煙花算法具有很好的全局搜索能力和局部搜索能力的自調節機制，還使得煙花算法能很好地避免早熟，因此煙花算法在許多領域的應用日漸廣泛[15].

本文通過改進變異算子、選擇策略和適應度函數，首次將煙花算法應用于PMC模型下的系統級故障診斷，提出了一種新的智能診斷算法——故障診斷煙花算法FWAFD(Fireworks Algorithm for Fault Diagnosis).

2 預備知識

2.1 PMC模型

Preparata、Metze和Chien于1967年提出了一種基于測試的系統級故障診斷模型，并用這三個人的名字的首字母將其命名為PMC模型[1]，它是系統級故障診斷模型中的一個經典模型.在PMC模型中，可以用一個有向圖G(U，E)來表示多處理器系統中的各處理機之間的測試關系.其中有向圖的頂點代表系統中的處理機，每一次測試都會有一個測試者和一個被測試者，有向邊(ui，uj)表示的是測試者ui對被測試者uj進行測試，測試結果用uij來表示.在該模型下，假設無故障機的測試結果是可信的，而故障機的測試結果是不可信的.

表1 PMC模型Table 1 PMC Model

如果測試者認為被測試者是正常的，則將邊(ui，uj)的權值uij記為0；否則將邊(ui，uj)的權值uij記為1.用1/0來分別表示結點機狀態為有/無故障，則PMC模型具體定義見表1.

2.2 相關定義

在系統級故障診斷算法中，可以將多處理器系統中的結點劃分為三大部分[16]：故障機集合F、無故障機集合FF和可疑結點機集合SF.若SF為空集，則稱該診斷算法是完全的.

用集合U={u0，…，un-1}來表示一個包含n個處理機的系統，每一個計算機結點ui∈U會被多個其他計算機結點uj∈U測試.對于每一個計算機結點ui，其測試者集合被定義為Γ-1(ui)={uj：(uj，ui)∈E}，其被測試者的集合被定義為Γ(ui)={uj：(ui，uj)∈E}，結點ui的入度表示為din(ui)=|Γ-1(ui)|，其出度表示為dout(ui)=|Γ(ui)|.S是故障集F產生的任一系統癥候，即S(ui，uj)=uij，S(ui)={S(ui，uj)：uj∈Γ(ui)}來表示癥候中的被測試者集，用S-1(ui)={S(uj，ui)：uj∈Γ-1(ui)}來表示癥候中的測試者集，F*表示系統的目標故障集，S*表示系統的目標癥候.

定理1. 在PMC模型下，如果得出的故障集合F和系統測試癥候S相容，那么①若權值uij=1，則結點ui和結點uj一定滿足ui+uj≥1；②若權值uij=0，則結點ui和結點uj一定滿足ui-uj≥0.

證明：當權值uij=1時，可從表1中查出結點ui和結點uj的狀態可能為第2、3、4種情況，而將這三種情況下結點ui和結點uj的狀態代入到ui+uj中進行計算，得出的計算結果均大于等于1，故①成立；

當權值uij=0時，可從表1中查出結點ui和結點uj的狀態可能為第1、3、4種情況，而將這三種情況下結點ui和結點uj的狀態代入到ui-uj中進行計算，得出的計算結果均大于等于0，故②成立；

綜上，可證明定理1成立.

2.3 煙花算法的基本原理

煙花算法[17]是一種用于解決復雜的無約束優化問題的新型群體智能算法，它來自于對煙花在空中爆炸從而產生火花的過程的模擬.煙花算法的工作過程與其他群體智能算法大同小異，其原理為：首先，隨機選擇N個煙花進行種群初始化，然后種群中的每個煙花都經過爆炸算子、變異算子、映射和選擇等操作，在保留當前種群中最優個體的前提下，在剩下的煙花和火花中選擇出N-1個個體組成下一次迭代的煙花種群.就這樣逐一迭代，不斷循環，直至滿足終止條件.其中適應度值較差的煙花的爆炸半徑越大，爆炸火花數量越少，使其具有全局搜索能力；反之，適應度值較好的煙花的爆炸半徑越小，爆炸火花數量越多，使其具有局部搜索能力.

3 算法步驟

3.1 字串表示

由系統級故障診斷的概念可知，系統級故障診斷過程就是在求解一個離散型問題，而在文獻[18]中展示了煙花算法是具有求解0/1規劃問題的能力的，這間接表明了煙花算法是具有解決系統級故障診斷問題的潛能的.

在系統中，用1表示結點為故障機，用0表示結點為無故障機，那么，就可以用一個長度為n、每個字節都為0或者1的字串來表示一個有n個節點的系統，字串的第i位用1/0來代表對應結點ui有/無故障，例如，可以用字串(0010010001)來表示10個結點的多處理器系統，其中故障模式F={u2，u5，u9}.由于系統Dt(n)為t-可診斷系統，故系統中的故障結點數|F|∈[1，t]，所以字節位的值為1的數目大于t的或者沒有字節位的值等于1的字串都被視為無效個體.

3.2 初始種群

對于計算機結點數為n，煙花個數為N的問題，首先生成一個維度為[N×n]的矩陣，其中矩陣元素為1到2之間的離散均勻隨機整數，再生成一個維度為[N×n]的全1矩陣，對兩個矩陣執行減的操作，得到一個每個元素的值都為0或者1的矩陣，即得到一個隨機的0/1矩陣，其中矩陣中的每一行都代表一個初始煙花，即種群初始化.

在本文的煙花算法中，當前種群用population來表示，其大小用populationNum來表示,煙花的個數用N來表示.

具體算法如下：

算法1.初始種群產生的具體過程

輸入：多處理器系統的結點個數和煙花數量

輸出：煙花算法的初始種群

Begin

1.首先生成一個維度為[N×n]的矩陣，其元素為1到2之間的離散均勻隨機整數，其中N表示煙花數量，n表示計算機結點個數；

2.將步驟1中得到的矩陣減去與之維度相同的全1陣，得到一個每個元素的值都為0或者1的矩陣，即得到一個隨機的0/1矩陣；

3.步驟2矩陣中的每一行都代表一個初始煙花，即種群初始化.

End

3.3 適應度函數

對于種群中適應度的計算方法，文獻[19]中是通過比較系統的相容癥候S和目標癥候S*的相似程度而計算出來的，個體的適應度用FT(vi)來表示，而個體中的每一位(即每一個計算機結點)的適應度用f(v[i])來表示，fin(v[i])表示結點i作為被測試者時的適應度，fout(v[i])表示結點i作為測試者時的適應度.具體的適應度函數計算公式如下：

(1)

其中，

(2)

(3)

(4)

而由定理1可知，在PMC模型下，測試結點ui、uj與測試結果uij必然滿足如下的約束方程：

(5)

其次，根據約束方程F(ui，uj)可得出ddin(v[i])和ddout(v[i])，ddin(v[i])表示既是結點ui的測試結點并且又滿足約束方程式F(ui，uj)的結點個數，而ddout(v[i])表示既是結點ui的被測試結點并且又滿足約束方程式F(ui，uj)的結點個數，即ddin(v[i])=|{(uj，ui)：uj∈Γ-1(ui)且F(uj，ui)成立}|，ddout(v[i])=|{(ui，uj)：uj∈Γ(ui)且F(ui，uj)成立}|.

本文在文獻[19]的計算公式的基礎上，還要考慮到測試結點與測試結果是否滿足式(5).綜上所述，當初始化煙花種群后，可按照下列方法來計算和評估煙花個體的適應度值.

(6)

(7)

而對于f(v[i])和FT(v)的定義同式(1)和式(2).

對于適應度函數FT(v)而言，當且僅當一個煙花個體v表示的故障模式F(v)與目標故障模式F*相等時，適應度函數值FT(v)=1，即求得正確的系統故障模式.

具體算法如下：

算法2.計算適應度

輸入：煙花種群中的所有個體

輸出：每個煙花個體的適應度值

Begin

1.for(intk=1;k<=populationNum;k++)

2.for(inti=1;i<=n;i++)

3.for(intj=1;j<=n;j++)

計算fin(v[i])；

計算fout(v[i])；

根據公式(2)計算出f(v[i])；

再根據公式(1)計算出FT(v).

End

3.4 爆炸算子

在煙花算法中，爆炸算子是算法的核心，起著關鍵性的作用，其包括煙花個體的爆炸強度、爆炸幅度以及位移操作.

3.4.1 爆炸強度

每個煙花爆炸產生的火花數目可表示為：

(8)

其中，Si表示第i個煙花爆炸所產生的火花個數；m是個常數，用于限制爆炸產生的火花總數；Yworst是當前煙花種群中適應度值最差的個體的適應度值；f(xi)為煙花個體xi的適應度值；ε為一個極小的常數，用于避免出現除零操作.

同時，為了避免煙花爆炸產生的火花數量過多或者過少的情況，對煙花xi的火花數做如公式(9)的控制：

(9)

3.4.2 爆炸幅度

每個煙花的爆炸半徑可表示為：

(10)

然而，若Xi為當前煙花種群中適應度值最優的煙花，則通過式(10)計算得出的爆炸幅度的值會非常小，幾乎接近于0.這就導致了當前煙花種群中最優的個體在實際的問題優化搜索過程中，由于其爆炸幅度太小而沒有發揮到局部挖掘的作用，或者更嚴重地說是沒有發揮到任何的搜索作用，這儼然與煙花算法的設計原則不相符.又因為系統故障診斷問題中計算機結點的狀態只能為0或者1，故該問題中煙花的爆炸幅度最大為1.為了避免和改善這兩個問題，本文的煙花算法借鑒了文獻[20]中對爆炸半徑的控制方法，在爆炸幅度計算公式(10)的基礎上引入了最小爆炸半徑檢測策略和最大爆炸半徑檢測策略，設Amin，k和Amax，k分別是第k維上的爆炸半徑最低/最高的檢測閾值，即

(11)

其中，Aik表示煙花個體i在維度k上的爆炸半徑.

3.4.3 位移操作

在計算出每個煙花個體的爆炸強度和爆炸幅度后，對每個煙花的一定數量的維度進行位移操作，這里所用到的位移操作方法是隨機位移.這樣一來，每個煙花個體都有自己特定的火花數目和爆炸幅度，對于某一個煙花來說，在爆炸幅度范圍內，隨機產生一個偏移量，爆炸生成新的火花，從而增強了種群的多樣性.在基本煙花算法中，當一個煙花個體爆炸產生爆炸火花時，在每一個維度上面發生的偏移量都是一樣的，這大大降低了爆炸火花種群的多樣性.針對這個缺陷，本文煙花算法在煙花個體爆炸產生爆炸火花的過程中，使用了在各個維度上面采取以不同大小的偏移量來進行位移操作的變異方式，即對煙花的每一個選擇到的維度上按下面的式(12)進行位置偏移，從而生成爆炸火花.

xik=xik+Ai×U(-1，1)

(12)

其中，xik表示的是第i個煙花個體xi在第k維上的位置；U(-1，1)表示在[-1，1]區間上的均勻分布的隨機數.

具體算法如下：

算法3.煙花爆炸產生爆炸火花的具體過程

輸入：所有煙花的位置

輸出：爆炸火花種群的位置

Begin

1.for(inti=1;i<=N;i++)

2.計算每個煙花的適應度值；

3.計算每個煙花爆炸產生的火花數Si和爆炸半徑Ai；

4.初始化爆炸火花的位置xi=Xi；

5.設置爆炸算子操作維度zk=round(U(0，1))，k=1，2，…，dim，其中dim為煙花個體xi的維數；

6.wherezk=1 do

7.計算火花的位置偏移量ΔX=Ai×U(-1，1)；

8.xik=xik+ΔX；

9. ifxik超出解的邊界 then

10. 將xik映射到問題的可行域內；

11. 將xik保存到當前的煙花/火花種群中.

End

3.5 變異算子

為了進一步提高種群的多樣性，基本煙花算法引入了高斯變異算子用來產生高斯變異火花，而由于多處理器系統中所有的計算機結點的故障狀態要么為0，要么為1，為更好地解決問題，本文的煙花算法中引入了最優變異.最優變異火花產生的過程如下：先在當前的煙花種群中隨機選擇若干個煙花個體，再分別對每個煙花個體隨機選擇一定數量的維度，然后將選擇到的每一個維度k上的信息，替換為當前煙花種群中適應度值最優的煙花在的第k維上的信息.即可按照下面的式(13)對每一個選擇得到的煙花的維度k執行最優變異操作.

xik=XBk

(13)

其中，xik表示的是第i個煙花個體xi在第k維上的位置，XBk為當前種群中適應度值最優的個體在第k維上的信息.具體算法如下：

算法4.煙花爆炸產生最優變異火花的具體過程

輸入：所有煙花的位置

輸出：最優變異火花種群的位置

Begin

1.初始化最優變異火花的位置xi=Xi；

2.設置變異算子操作維度個數zk=round(U(0，1))，k=1，2，…，dim，其中dim為xi的維數；

3.wherezk=1 do

4.xik=XBk，其中XBk為當前種群中適應度值最優的個體在第k維上的信息;

5. ifxik超出解的邊界 then

6. 將xik映射到問題的可行域內；

7. 將xik保存到當前的煙花/火花種群中.

End

3.6 映射規則

在執行爆炸算子和變異算子操作分別產生爆炸火花和變異火花的過程中，這些火花很有可能會超出問題可行域的邊界.如果煙花爆炸和變異后在可行域范圍外產生火花，則需要通過某種映射規則將其拉回到可行域范圍內.由于系統故障診斷問題的為0/1問題，故可先對火花進行向0取整，再對大于1的結點位取值為1，小于0的結點位取值為0，這樣能確保煙花個體中的每一個結點的狀態保持為0/1，滿足故障診斷問題中計算機結點的狀態.根據上述的映射規則，可按照下面的式(14)和式(15)對煙花爆炸產生的火花進行越界檢測，將越界的火花映射到可行域的范圍內.

ui=fix(ui)

(14)

(15)

3.7 選擇策略

為了保證當前煙花種群中優秀的信息能夠傳遞到下一次迭代的種群中，在執行爆炸算子和變異算子操作分別產生爆炸火花和變異火花后，算法會在當前的種群(其中包括初始煙花、爆炸火花以及最優變異火花)中選擇一定數量的個體作為下一次迭代的煙花種群.

在基本煙花算法中，一般都采用輪盤賭的選擇策略，即在當前的煙花、爆炸火花和高斯變異火花中，保留最優個體，并在余下個體中按照輪盤賭的規則選出N-1個個體進行下一次迭代.每個個體被選擇的概率用p(xi)來表示，其計算公式為：

(16)

本文中的選擇策略與基本煙花算法輪盤賭的選擇策略不同，本文采用的是最優適應度值選擇策略，即選擇煙花種群中適應度值較優的前N個煙花個體，使其組成下一代煙花群體.這種選擇策略很簡單，也很容易理解.

3.8 PMC模型下的煙花算法概述

綜合以上算法步驟，現給出PMC模型下的煙花算法.

算法5.本文煙花算法的具體過程

輸入：系統結點的測試癥候S

輸出：系統故障結點集F以及無故障結點集FF

Begin

1.在解空間里隨機初始化N個煙花，進行種群初始化；

2.計算和評估N個煙花的適應度值FT；

3.根據爆炸算子計算每個煙花的爆炸幅度和爆炸火花數；

4.產生爆炸火花；

5.產生最優變異火花；

6.對爆炸火花和變異火花進行越界檢測，將越界的火花映射到可行域的范圍內；

7.計算種群中個體的適應度值FT，采用最優適應度值選擇策略，選擇煙花種群中適應度值較優的前N個煙花個體，使其組成下一代煙花群體；

8.輸出適應度值FT為1的個體對應的故障集和無故障集即為系統的故障集和無故障集；如果沒有輸出適應度值為1的個體，則繼續執行4-7過程.

End

4 算法實現與分析

本文的算法設計平臺為MATLAB R2014a，并且在一臺內存為4.00GB，CPU為Intel(R) Core(TM) i5-3230M 2.60GHz的計算機上進行仿真實驗.

4.1 參數設定

4.1.1 初始種群煙花個數N

為了得出設置煙花個數的多少使得算法的性能較好，本文進行了如下實驗：在其他參數不變的情況下，對煙花算法的煙花個數分別取值為1，3，5，7，9時，實驗結果如圖1所示，圖中的橫坐標表示煙花數量，縱坐標表示算法運行的CPU時間.

圖1 煙花個數對算法CPU運行時間的影響Fig.1 Influence of the number of fireworks on the CPU time of the algorithm

由圖1可以看出，在其他參數保持不變的情況下，煙花個數為3個的時候算法的CPU運行時間最少，煙花算法可以得到相對較好的結果，故在此將煙花個數設置為3個.

4.1.2 爆炸半徑最低/最高的檢測閾值Amin，k和Amax，k

參數Amin，k和Amax，k的設置可以很好的控制煙花的爆炸幅度不會過大或者過小，本文將Amin，k設置為(XUB，k-XLB，k)×0.05，Amax，k設置為(XUB，k-XLB，k)×1，其中解空間在維度k上的上邊界XUB，k=1，下邊界XLB，k=0.

4.1.3 最大火花數量m

為探究最大火花數量對算法性能的影響，本文同樣對其進行了實驗分析，實驗結果如圖2所示，圖中的橫坐標表示最大火花數量，縱坐標表示算法運行的CPU時間.

由圖2可以看出，在其他參數保持不變的情況下，煙花算法的最大火花數m的取值等于40時，算法效果較好，因此，本文設定m=40.

圖2 最大火花數量m對算法的CPU運行時間的影響Fig.2 Influence of the maximum spark number m on the CPU time of the algorithm

4.1.4 煙花最優變異的個數mutationNum

最優變異能增加算法種群的多樣性，故變異個體的個數對算法的性能也有很大的影響.本文對此也進行了實驗分析，實驗結果如圖3所示，圖中的橫坐標表示高斯變異個體的數量，縱坐標表示算法運行的CPU時間.

圖3 最優變異個體數量對算法CPU運行時間的影響Fig.3 Influence of the number of optimal mutation individuals on the CPU time of the algorithm

由圖3可以看出，在其他參數保持不變的情況下，煙花算法中執行變異操作的煙花個數為22時可以得到相對較好的結果，因此，本文設定mutationNum=22.

4.1.6 維數dim

由適應度函數FT(v)可知，多處理器系統中有多少個計算機結點就有多少個維度，故維數dim=n.

4.1.7 算法最大迭代次數maxEva

參數maxEva的設置參考文獻[17]，即設置maxEva=400000次.

4.2 算法比較

根據本文4.1節和文獻[6，8，10，11]設置的參數，對本文算法和文獻[6，8，10，11]中各算法在解決PMC模型下的系統級故障診斷所需要的CPU運行時間進行比較，得出計算機結點數目n從10個遞增到300個時，五種算法的CPU運行時間.如圖4所示，圖中的橫坐標表示計算機結點數，縱坐標表示算法運行的CPU時間.

由圖4可看出，在計算機結點數目在10-300個時，本文算法的平均CPU運行時間為0.5989秒，而文獻[6，8，10，11]算法的平均CPU運行時間分別為4.3308秒、14.84秒、6.22秒以及13.173秒，由此可知，在PMC模型下的系統級故障診斷中，本文算法的運行效率明顯要高于文獻[6，8，10，11]中的各算法.

圖4 五種算法的CPU運行時間的比較Fig.4 Comparison of the CPU time of the five algorithms

4.3 算法的正確性

定理2. 當且僅當一個煙花個體v表示的故障模式F(V)=F*時，其適應度函數FT(v)=1.

證明：充分性.當F(V)=F*時，所求得的故障模式F(v)與系統的目標癥候S*相容，即在PMC模型下，系統癥候S*中的任意一條有向邊(ui，uj)的權值uij一定是由結點ui和uj的故障狀態產生的，由定理1可知，當權值uij的值為1時，結點ui和uj的故障狀態滿足不等式ui+uj≥1，當權值uij的值為0時，結點ui和uj的故障狀態滿足不等式ui-uj≥0，即滿足約束方程F(ui，uj).故在系統癥候S*中，任意兩個結點ui和uj之間如果存在測試邊(ui，uj)，則結點ui和uj的故障狀態一定是滿足約束方程F(ui，uj)的，也就是說結點ui的出度滿足等式dout(ui)=|{(ui，uj)：uj∈Γ(ui)且F(ui，uj)成立}|=ddout(v[i])，同理，結點ui的入度滿足等式din(ui)=|{(uj，ui)：uj∈Γ-1(ui)且F(uj，ui)成立}|=ddin(v[i]).那么由式(6)和式(7)中對fin(v[i])和fout(v[i])的定義易得出fin(v[i])=fout(v[i])=1，再由式(2)和式(1)得到f(v[i])=1，FT(v)=1.

必要性.反證法：令目標故障集F*對應煙花個體表示的故障集為F(v)，則FT(v)=1，假設存在一個不同于v的煙花個體v′，使得其表示的故障集FT(v′)=1，因為v和v′是不同的煙花個體，所以F(v)和F(v′)中至少存在一個結點位的狀態不同，不失一般性，假設該結點位為v[i]，即v[i]≠v′[i](表示在F(v)和F(v′)中某一結點ui的狀態所取的值不同).由于FT(v)=FT(v′)=1，則由式(1)易得出f(v[i])=f(v′[i])=1，再由式(6)求出ddin(v[i])=ddin(v′[i])=din(ui)，由ddin(v[i])的定義可知，對任意結點uj∈Γ-1(ui)且滿足約束條件F(ui，uj)，而v[i]≠v′[i]，即ui的測試結點對ui進行測試時得到了兩種不一樣的結果，如果測試者是無故障結點，那么在PMC模型下，無故障結點是能夠正確識別其他結點的，那么測試者對ui進行測試時，能識別出ui要么為1，要么為0，不可能在不同的煙花個體里出現兩種不同的狀態，故可以推出ui的所有測試者Γ-1(ui)都是故障結點.根據t-可診斷系統的特點可知，系統中的故障結點總數最多為t個，每一個結點的測試者的個數|Γ-1(ui)|=t，而ui的所有的測試者都是故障結點，即當前系統的故障結點數為t個，如果ui也為故障結點，那么系統的故障結點總數就會變為t+1個，這就不滿足系統的t-可診斷性，所以ui只能是無故障結點，而這與v[i]≠v′[i]的假設相矛盾，故必要性得證.

證畢.

4.4 算法時間復雜度

設多處理器系統的結點數為n，算法迭代次數為I，煙花個數為N，在每次迭代過程中爆炸產生的火花數量為s，最優變異火花數量為m.根據本文3.8節給出的算法，我們逐步對算法的時間復雜度進行分析，具體的分析過程如下：

第1，隨機初始化生成初始煙花種群時，由于初始種群大小為N，故時間復雜度為Ο(N)；

第2，依次計算初始種群中每個煙花個體的適應度值，這需要遍歷整個初始煙花種群，故時間復雜度為Ο(N×n)；

第3，計算初始種群中的每個煙花爆炸幅度和爆炸半徑，煙花個數為N，故時間復雜度為Ο(N)；

第4，對當前煙花種群中的每個煙花進行爆炸操作產生火花并進行位移變異，時間復雜度為Ο(s×n)；

第5，對當前煙花種群中的m個煙花個體進行最優變異操作，時間復雜度為Ο(n×m)；

第6，采用最優適應度值選擇策略進行選擇，計算當前種群中的每個煙花個體的適應度函數值的時間復雜度為Ο(N+s+m)，對適應度值進行降序排序并選取前N個適應度值對應的煙花，時間復雜度為Ο(N+s+m).

綜上，迭代I次時本文算法的時間復雜度為Ο(I×n×(N+s+m)).由此可以看出，整個煙花算法的時間復雜度取決于迭代次數、煙花種群的大小、多處理器系統的結點數、爆炸火花數以及進行變異的煙花數，因此，當煙花種群的大小、爆炸火花數以及進行變異的煙花數確定時，算法運行時間的長短僅與算法迭代次數、系統的計算機結點數有關.

5 結束語

煙花算法作為新型的群體智能算法，具有很強的局部搜索和全局搜索的自適應性，適合求解復雜問題的全局最優解.本文依據PMC診斷模型的特征，將煙花算法和PMC模型進行很好的結合，提出了一種基于PMC模型的煙花診斷算法.首先給出算法的基本思想和偽代碼，其次分析了算法中各控制參數的選擇和設定，然后用仿真實驗分別對基于遺傳算法、集團算法、擴展星型算法、人工免疫算法和本文算法的系統故障診斷效率進行比較，最后分析本文算法的正確性和時間復雜度.實驗結果表明，本文算法能夠更高效地判斷出多處理器系統的目標故障集.但對于煙花算法在系統級故障診斷領域的研究，目前仍處于初級的階段，煙花算法中的各個參數或許還不夠完善，對其進行改進，使得故障診斷更加快捷準確，并將其應用于BGM模型、Malek模型等其他系統級故障模型中，這將會是更進一步的研究方向.