一種PMC模型下的系統(tǒng)級故障診斷煙花算法

歸偉夏，陸 倩

(廣西大學(xué) 計(jì)算機(jī)與電子信息學(xué)院，南寧 530004)

1 引 言

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

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

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

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

2 預(yù)備知識

2.1 PMC模型

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

表1 PMC模型Table 1 PMC Model

如果測試者認(rèn)為被測試者是正常的，則將邊(ui，uj)的權(quán)值uij記為0；否則將邊(ui，uj)的權(quán)值uij記為1.用1/0來分別表示結(jié)點(diǎn)機(jī)狀態(tài)為有/無故障，則PMC模型具體定義見表1.

2.2 相關(guān)定義

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

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

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

證明：當(dāng)權(quán)值uij=1時，可從表1中查出結(jié)點(diǎn)ui和結(jié)點(diǎn)uj的狀態(tài)可能為第2、3、4種情況，而將這三種情況下結(jié)點(diǎn)ui和結(jié)點(diǎn)uj的狀態(tài)代入到ui+uj中進(jìn)行計(jì)算，得出的計(jì)算結(jié)果均大于等于1，故①成立；

當(dāng)權(quán)值uij=0時，可從表1中查出結(jié)點(diǎn)ui和結(jié)點(diǎn)uj的狀態(tài)可能為第1、3、4種情況，而將這三種情況下結(jié)點(diǎn)ui和結(jié)點(diǎn)uj的狀態(tài)代入到ui-uj中進(jìn)行計(jì)算，得出的計(jì)算結(jié)果均大于等于0，故②成立；

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

2.3 煙花算法的基本原理

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

3 算法步驟

3.1 字串表示

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

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

3.2 初始種群

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

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

具體算法如下：

算法1.初始種群產(chǎn)生的具體過程

輸入：多處理器系統(tǒng)的結(jié)點(diǎn)個數(shù)和煙花數(shù)量

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

Begin

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

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

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

End

3.3 適應(yīng)度函數(shù)

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

(1)

其中，

(2)

(3)

(4)

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

(5)

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

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

(6)

(7)

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

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

具體算法如下：

算法2.計(jì)算適應(yīng)度

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

輸出：每個煙花個體的適應(yīng)度值

Begin

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

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

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

計(jì)算fin(v[i])；

計(jì)算fout(v[i])；

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

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

End

3.4 爆炸算子

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

3.4.1 爆炸強(qiáng)度

每個煙花爆炸產(chǎn)生的火花數(shù)目可表示為：

(8)

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

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

(9)

3.4.2 爆炸幅度

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

(10)

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

(11)

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

3.4.3 位移操作

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

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

(12)

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

具體算法如下：

算法3.煙花爆炸產(chǎn)生爆炸火花的具體過程

輸入：所有煙花的位置

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

Begin

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

2.計(jì)算每個煙花的適應(yīng)度值；

3.計(jì)算每個煙花爆炸產(chǎn)生的火花數(shù)Si和爆炸半徑Ai；

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

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

6.wherezk=1 do

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

8.xik=xik+ΔX；

9. ifxik超出解的邊界 then

10. 將xik映射到問題的可行域內(nèi)；

11. 將xik保存到當(dāng)前的煙花/火花種群中.

End

3.5 變異算子

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

xik=XBk

(13)

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

算法4.煙花爆炸產(chǎn)生最優(yōu)變異火花的具體過程

輸入：所有煙花的位置

輸出：最優(yōu)變異火花種群的位置

Begin

1.初始化最優(yōu)變異火花的位置xi=Xi；

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

3.wherezk=1 do

4.xik=XBk，其中XBk為當(dāng)前種群中適應(yīng)度值最優(yōu)的個體在第k維上的信息;

5. ifxik超出解的邊界 then

6. 將xik映射到問題的可行域內(nèi)；

7. 將xik保存到當(dāng)前的煙花/火花種群中.

End

3.6 映射規(guī)則

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

ui=fix(ui)

(14)

(15)

3.7 選擇策略

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

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

(16)

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

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

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

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

輸入：系統(tǒng)結(jié)點(diǎn)的測試癥候S

輸出：系統(tǒng)故障結(jié)點(diǎn)集F以及無故障結(jié)點(diǎn)集FF

Begin

1.在解空間里隨機(jī)初始化N個煙花，進(jìn)行種群初始化；

2.計(jì)算和評估N個煙花的適應(yīng)度值FT；

3.根據(jù)爆炸算子計(jì)算每個煙花的爆炸幅度和爆炸火花數(shù)；

4.產(chǎn)生爆炸火花；

5.產(chǎn)生最優(yōu)變異火花；

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

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

8.輸出適應(yīng)度值FT為1的個體對應(yīng)的故障集和無故障集即為系統(tǒng)的故障集和無故障集；如果沒有輸出適應(yīng)度值為1的個體，則繼續(xù)執(zhí)行4-7過程.

End

4 算法實(shí)現(xiàn)與分析

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

4.1 參數(shù)設(shè)定

4.1.1 初始種群煙花個數(shù)N

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

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

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

4.1.2 爆炸半徑最低/最高的檢測閾值A(chǔ)min，k和Amax，k

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

4.1.3 最大火花數(shù)量m

為探究最大火花數(shù)量對算法性能的影響，本文同樣對其進(jìn)行了實(shí)驗(yàn)分析，實(shí)驗(yàn)結(jié)果如圖2所示，圖中的橫坐標(biāo)表示最大火花數(shù)量，縱坐標(biāo)表示算法運(yùn)行的CPU時間.

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

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

4.1.4 煙花最優(yōu)變異的個數(shù)mutationNum

最優(yōu)變異能增加算法種群的多樣性，故變異個體的個數(shù)對算法的性能也有很大的影響.本文對此也進(jìn)行了實(shí)驗(yàn)分析，實(shí)驗(yàn)結(jié)果如圖3所示，圖中的橫坐標(biāo)表示高斯變異個體的數(shù)量，縱坐標(biāo)表示算法運(yùn)行的CPU時間.

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

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

4.1.6 維數(shù)dim

由適應(yīng)度函數(shù)FT(v)可知，多處理器系統(tǒng)中有多少個計(jì)算機(jī)結(jié)點(diǎn)就有多少個維度，故維數(shù)dim=n.

4.1.7 算法最大迭代次數(shù)maxEva

參數(shù)maxEva的設(shè)置參考文獻(xiàn)[17]，即設(shè)置maxEva=400000次.

4.2 算法比較

根據(jù)本文4.1節(jié)和文獻(xiàn)[6，8，10，11]設(shè)置的參數(shù)，對本文算法和文獻(xiàn)[6，8，10，11]中各算法在解決PMC模型下的系統(tǒng)級故障診斷所需要的CPU運(yùn)行時間進(jìn)行比較，得出計(jì)算機(jī)結(jié)點(diǎn)數(shù)目n從10個遞增到300個時，五種算法的CPU運(yùn)行時間.如圖4所示，圖中的橫坐標(biāo)表示計(jì)算機(jī)結(jié)點(diǎn)數(shù)，縱坐標(biāo)表示算法運(yùn)行的CPU時間.

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

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

4.3 算法的正確性

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

證明：充分性.當(dāng)F(V)=F*時，所求得的故障模式F(v)與系統(tǒng)的目標(biāo)癥候S*相容，即在PMC模型下，系統(tǒng)癥候S*中的任意一條有向邊(ui，uj)的權(quán)值uij一定是由結(jié)點(diǎn)ui和uj的故障狀態(tài)產(chǎn)生的，由定理1可知，當(dāng)權(quán)值uij的值為1時，結(jié)點(diǎn)ui和uj的故障狀態(tài)滿足不等式ui+uj≥1，當(dāng)權(quán)值uij的值為0時，結(jié)點(diǎn)ui和uj的故障狀態(tài)滿足不等式ui-uj≥0，即滿足約束方程F(ui，uj).故在系統(tǒng)癥候S*中，任意兩個結(jié)點(diǎn)ui和uj之間如果存在測試邊(ui，uj)，則結(jié)點(diǎn)ui和uj的故障狀態(tài)一定是滿足約束方程F(ui，uj)的，也就是說結(jié)點(diǎn)ui的出度滿足等式dout(ui)=|{(ui，uj)：uj∈Γ(ui)且F(ui，uj)成立}|=ddout(v[i])，同理，結(jié)點(diǎn)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，F(xiàn)T(v)=1.

必要性.反證法：令目標(biāo)故障集F*對應(yīng)煙花個體表示的故障集為F(v)，則FT(v)=1，假設(shè)存在一個不同于v的煙花個體v′，使得其表示的故障集FT(v′)=1，因?yàn)関和v′是不同的煙花個體，所以F(v)和F(v′)中至少存在一個結(jié)點(diǎn)位的狀態(tài)不同，不失一般性，假設(shè)該結(jié)點(diǎn)位為v[i]，即v[i]≠v′[i](表示在F(v)和F(v′)中某一結(jié)點(diǎn)ui的狀態(tài)所取的值不同).由于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])的定義可知，對任意結(jié)點(diǎn)uj∈Γ-1(ui)且滿足約束條件F(ui，uj)，而v[i]≠v′[i]，即ui的測試結(jié)點(diǎn)對ui進(jìn)行測試時得到了兩種不一樣的結(jié)果，如果測試者是無故障結(jié)點(diǎn)，那么在PMC模型下，無故障結(jié)點(diǎn)是能夠正確識別其他結(jié)點(diǎn)的，那么測試者對ui進(jìn)行測試時，能識別出ui要么為1，要么為0，不可能在不同的煙花個體里出現(xiàn)兩種不同的狀態(tài)，故可以推出ui的所有測試者Γ-1(ui)都是故障結(jié)點(diǎn).根據(jù)t-可診斷系統(tǒng)的特點(diǎn)可知，系統(tǒng)中的故障結(jié)點(diǎn)總數(shù)最多為t個，每一個結(jié)點(diǎn)的測試者的個數(shù)|Γ-1(ui)|=t，而ui的所有的測試者都是故障結(jié)點(diǎn)，即當(dāng)前系統(tǒng)的故障結(jié)點(diǎn)數(shù)為t個，如果ui也為故障結(jié)點(diǎn)，那么系統(tǒng)的故障結(jié)點(diǎn)總數(shù)就會變?yōu)閠+1個，這就不滿足系統(tǒng)的t-可診斷性，所以ui只能是無故障結(jié)點(diǎn)，而這與v[i]≠v′[i]的假設(shè)相矛盾，故必要性得證.

證畢.

4.4 算法時間復(fù)雜度

設(shè)多處理器系統(tǒng)的結(jié)點(diǎn)數(shù)為n，算法迭代次數(shù)為I，煙花個數(shù)為N，在每次迭代過程中爆炸產(chǎn)生的火花數(shù)量為s，最優(yōu)變異火花數(shù)量為m.根據(jù)本文3.8節(jié)給出的算法，我們逐步對算法的時間復(fù)雜度進(jìn)行分析，具體的分析過程如下：

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

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

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

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

第5，對當(dāng)前煙花種群中的m個煙花個體進(jìn)行最優(yōu)變異操作，時間復(fù)雜度為Ο(n×m)；

第6，采用最優(yōu)適應(yīng)度值選擇策略進(jìn)行選擇，計(jì)算當(dāng)前種群中的每個煙花個體的適應(yīng)度函數(shù)值的時間復(fù)雜度為Ο(N+s+m)，對適應(yīng)度值進(jìn)行降序排序并選取前N個適應(yīng)度值對應(yīng)的煙花，時間復(fù)雜度為Ο(N+s+m).

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

5 結(jié)束語

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