歸偉夏,藍(lán) 婷,陸 倩

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

1 引 言

目前,在某些應(yīng)用場(chǎng)景中所需要的計(jì)算資源越來(lái)越多,為滿足計(jì)算需求,大規(guī)模的計(jì)算機(jī)集群應(yīng)用越來(lái)越廣泛.而隨著需求的不斷提高,計(jì)算機(jī)集群中的結(jié)點(diǎn)數(shù)量也在不斷地增加,進(jìn)而導(dǎo)致集群系統(tǒng)的安全性和可靠性下降.在諸如股票交易、網(wǎng)上銀行、導(dǎo)彈系統(tǒng)等關(guān)鍵領(lǐng)域,若系統(tǒng)中的某一節(jié)點(diǎn)發(fā)生故障而不能盡快排查,則很可能造成不可估計(jì)的后果.因此,如何能迅速、精確地找到故障機(jī)成為當(dāng)前的重大問(wèn)題.

自1967年P(guān)reparata,Metze和Chien[1]首次提出系統(tǒng)級(jí)故障診斷方法(PMC模型)以來(lái),故障診斷領(lǐng)域的相關(guān)研究一直備受關(guān)注.在此之后,學(xué)者們相繼提出另外三種經(jīng)典的故障診斷模型,如1976年Barsi等人提出的BGM模型[2];1980年Malek提出的Malek模型[3];1981年由Chwa和Hakimi兩位學(xué)者所提出的Chwa&Hakimi模型[4].

系統(tǒng)級(jí)故障診斷近幾年的研究成果頗豐,根據(jù)算法的性質(zhì),主要分為兩大類型.第一類故障診斷算法是以圖論理論為基礎(chǔ)而建立,第二類是利用各類人工智能算法判斷故障結(jié)點(diǎn)的故障診斷算法.張大方等[5]基于圖論原理及系統(tǒng)級(jí)故障診斷的特點(diǎn),首次提出了解決故障診斷問(wèn)題的集團(tuán)診斷算法,并且研究了“一步t可診斷系統(tǒng)”的特征.宣恒農(nóng)等人[6]首次提出了方程診斷算法,也是屬于第一類以圖論理論為基礎(chǔ)的診斷算法,該算法的特點(diǎn)是不以“t-可診斷性”作為假設(shè),且不以“相信大多數(shù)”作為前提條件.第二類主要包括各種人工智能算法和高效的群體智能算法,如:人工免疫診斷算法、智能BP神經(jīng)網(wǎng)絡(luò)診斷算法、PSO粒子群診斷算法、GA遺傳診斷算法等.這些智能診斷算法基本上都存在不同程度的易早熟收斂、收斂速度慢、易陷入局部最優(yōu)等缺點(diǎn).

2010年,Tan等在文獻(xiàn)[7]中首次提出了煙花算法(FWA,Fireworks Algorithm),FWA是通過(guò)模擬煙花爆炸時(shí)產(chǎn)生新火花的這一過(guò)程來(lái)搜索鄰域.FWA作為新型的群體智能算法,與其他群體智能算法不同的是,FWA采用的是爆炸搜索機(jī)制.在FWA中,適應(yīng)度值作為生成新火花的重要參考依據(jù),不同適應(yīng)度值的煙花,它的爆炸半徑和爆炸火花數(shù)不同;對(duì)于適應(yīng)度值好的煙花,為了使其具有更好的開(kāi)采能力,它的爆炸半徑相對(duì)較小;對(duì)于適應(yīng)度值差的煙花,為了使其具有更好的勘探能力,它的爆炸半徑相對(duì)較大.這兩個(gè)特點(diǎn)使得FWA具有良好的局部搜索能力和全局搜索能力自調(diào)節(jié)機(jī)制.FWA自提出以來(lái),因其強(qiáng)大的問(wèn)題求解能力被應(yīng)用到眾多領(lǐng)域,主要有0/1背包問(wèn)題[8]、方程求解[9]、圖像處理[10]、物流調(diào)度[11]、多目標(biāo)調(diào)度問(wèn)題[12]等.系統(tǒng)級(jí)故障診斷中處理器結(jié)點(diǎn)的狀態(tài)要么為0要么為1,所以可以用一個(gè)0/1串來(lái)表示一個(gè)系統(tǒng)的結(jié)點(diǎn)狀態(tài),而文獻(xiàn)[13]中設(shè)計(jì)了基于二進(jìn)制編碼的煙花算法(BFA),表明FWA具有解決0/1編碼問(wèn)題的能力,也間接證明了FWA具有解決系統(tǒng)級(jí)故障診斷問(wèn)題的潛能.

本文采用改進(jìn)的FWA用于解決Malek模型下的故障診斷問(wèn)題.首先在本文的第二部分說(shuō)明故障診斷系統(tǒng)中的Malek模型及其相關(guān)定義、FWA的基本原理;然后描述本文算法的主要步驟,分別為:煙花種群初始化、計(jì)算種群適應(yīng)度、計(jì)算煙花爆炸半徑和火花數(shù)、分別產(chǎn)生爆炸火花和高斯變異火花、選擇下一代個(gè)體,最后輸出最優(yōu)個(gè)體所對(duì)應(yīng)的故障集和無(wú)故障集.

2 預(yù)備知識(shí)

2.1 Malek模型

1980年,Malek提出了基于比較的非對(duì)稱模型——Malek模型,故障模式、故障癥候以及拓?fù)浣Y(jié)構(gòu)是該模型的三個(gè)重要因素.故障模式是系統(tǒng)中所有結(jié)點(diǎn)的狀態(tài)集合,故障癥候是基于故障模式、故障診斷模型及拓?fù)浣Y(jié)構(gòu)而得的所有邊的狀態(tài)集合,這個(gè)集合就是與該故障模式相容的一個(gè)故障癥候.在同一個(gè)系統(tǒng)中,故障模式與故障癥候的對(duì)應(yīng)關(guān)系為:一個(gè)故障模式可對(duì)應(yīng)于多個(gè)故障癥候,而一個(gè)故障癥候也可對(duì)應(yīng)于多個(gè)故障模式.

在Malek模型下,系統(tǒng)內(nèi)的結(jié)點(diǎn)兩兩之間執(zhí)行相同的任務(wù)得到一個(gè)結(jié)果,然后比較這個(gè)結(jié)果是否相同來(lái)得到關(guān)于邊的信息,這些所有的邊構(gòu)成了一個(gè)無(wú)向圖.如表1所示為Malek模型定義,其中,結(jié)點(diǎn)狀態(tài)表示為:1是故障結(jié)點(diǎn),0是無(wú)故障結(jié)點(diǎn);比較結(jié)果的邊狀態(tài)表示為:1代表兩個(gè)結(jié)點(diǎn)得到不同的測(cè)試結(jié)果,0代表兩個(gè)結(jié)點(diǎn)得到相同的測(cè)試結(jié)果.

表1 Malek模型
Table 1 Malek Model

結(jié)點(diǎn)ui狀態(tài)結(jié)點(diǎn)uj狀態(tài)比較結(jié)果邊eij狀態(tài)000011101111

2.2 相關(guān)定義

在Malek模型中,用集合U={u1,u2,…,un}來(lái)表示一個(gè)包含有n個(gè)結(jié)點(diǎn)的多處理機(jī)系統(tǒng),結(jié)點(diǎn)之間邊的集合記為E={e1,e2,…,ek},分配相同的隨機(jī)任務(wù)給結(jié)點(diǎn)ui∈U和與它相鄰的結(jié)點(diǎn)uj∈U,比較它們的測(cè)試結(jié)果得到相關(guān)邊為eij={(ui,uj):(ui,uj)∈E}.用S表示故障癥候,則S(i,j)=eij.根據(jù)Malek模型的測(cè)試方法得到的一批測(cè)試結(jié)果決定了一個(gè)n階對(duì)稱矩陣A=(aij)n×n,aij∈{0,1}.用d表示結(jié)點(diǎn)的度,d(ui)=|{uj:(ui,uj)∈E}|.對(duì)于任意癥候S,必然存在與之相容的故障模式Fs.

定理1.Malek模型中的兩個(gè)關(guān)聯(lián)結(jié)點(diǎn)ui,uj的狀態(tài)值與它們的相關(guān)邊eij滿足如下方程組:

(1)

證明:當(dāng)兩個(gè)結(jié)點(diǎn)的測(cè)試結(jié)果一致,即eij=0時(shí),查表1可知:ui=0且uj=0,代入方程:左邊=ui+uj=0=右邊,滿足約束方程;

當(dāng)兩個(gè)結(jié)點(diǎn)的測(cè)試結(jié)果不一致,即eij=1時(shí),查表1可知,ui,uj中至少有一個(gè)故障結(jié)點(diǎn),若只有一個(gè)故障結(jié)點(diǎn),則ui=0,uj=1或ui=1,uj=0;若兩個(gè)均為故障結(jié)點(diǎn),則ui=1,uj=1.將以上兩種情況代入方程:左邊=ui×uj×(ui-uj)=0=右邊,滿足約束方程;

綜上所述,定理1成立.

2.3 煙花算法

FWA一種模擬煙花爆炸過(guò)程的群體智能算法.FWA采用的是一種新的搜索方式,通過(guò)局部空間內(nèi)的隨機(jī)爆炸過(guò)程來(lái)搜索潛在解決方案.FWA的工作原理如下:首先,隨機(jī)初始化N個(gè)煙花,評(píng)估其質(zhì)量(即適應(yīng)度),以確定每個(gè)煙花爆炸產(chǎn)生的火花數(shù)量和爆炸半徑.隨后,煙花爆炸并在其解空間內(nèi)產(chǎn)生不同的火花;爆炸后,根據(jù)隨機(jī)選擇的煙花產(chǎn)生高斯變異火花.最后,將當(dāng)前種群中的最優(yōu)個(gè)體保留進(jìn)入下一代,并且從剩下的所有煙花(包括新產(chǎn)生的火花、高斯變異火花以及N個(gè)原始煙花)中選出N-1個(gè)煙花進(jìn)入下一代.如此循環(huán),直到滿足終止條件.

3 算法步驟

3.1 字串表示

在系統(tǒng)級(jí)故障診斷中,用1表示有故障結(jié)點(diǎn),用0表示無(wú)故障結(jié)點(diǎn),則可以用長(zhǎng)度為n的二進(jìn)制串來(lái)表示一個(gè)含有n個(gè)結(jié)點(diǎn)的系統(tǒng),其中,字串的第i位表示對(duì)應(yīng)結(jié)點(diǎn)ui有/無(wú)故障.例如,(0100010001)表示含有10個(gè)結(jié)點(diǎn)的多處理機(jī)系統(tǒng),其故障模式為Fs={u2,u6,u10}.該系統(tǒng)以“t-可診斷性”為前提,所以故障結(jié)點(diǎn)數(shù)|Fs|∈[1,…,t].

3.2 初始種群

在文獻(xiàn)[14]中已經(jīng)將文獻(xiàn)[15]提出的指定無(wú)故障結(jié)點(diǎn)生成初始種群的方法應(yīng)用到Malek模型中,并取得了較好的效果,本文也采用這種方法來(lái)生成初始種群,算法1描述了其計(jì)算過(guò)程.

算法1.隨機(jī)指定無(wú)故障結(jié)點(diǎn)法生成初始種群

輸入:故障癥候S

輸出:與故障癥候相容的初始種群

Begin

1.在結(jié)點(diǎn)數(shù)為n的系統(tǒng)內(nèi),隨機(jī)選定一個(gè)結(jié)點(diǎn)ui,指定其狀態(tài)為0,即該結(jié)點(diǎn)無(wú)故障;

2.遍歷與ui相鄰的結(jié)點(diǎn)uj,若S(i,j)=0,即eij=0,根據(jù)表1可知,結(jié)點(diǎn)uj無(wú)故障,否則,結(jié)點(diǎn)uj有故障;

3.將步驟2中得到的所有無(wú)故障結(jié)點(diǎn)執(zhí)行步驟2;

4.對(duì)不確定結(jié)點(diǎn)隨機(jī)指定狀態(tài);

5.檢測(cè)個(gè)體是否滿足“t-可診斷性”,若故障結(jié)點(diǎn)數(shù)不滿足條件,則返回步驟1繼續(xù)執(zhí)行;

End

由算法1可得到一個(gè)符合“t-可診斷性”的個(gè)體,重復(fù)執(zhí)行N次,即可得到初始種群.

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

本文通過(guò)計(jì)算個(gè)體中每個(gè)結(jié)點(diǎn)的度來(lái)得到個(gè)體的適應(yīng)度,適應(yīng)度函數(shù)定義如下:

(2)

(3)

dd(v[i])=|{eij∈E且滿足f(ui,uj)}|

(4)

其中,FT(v[i])表示種群中每個(gè)個(gè)體的適應(yīng)度,fv(i,j)表示第i個(gè)個(gè)體中第j個(gè)結(jié)點(diǎn)的適應(yīng)度,dd(v[i])指與結(jié)點(diǎn)i鄰接并且滿足約束方程f(ui,uj)的結(jié)點(diǎn)個(gè)數(shù),d(v[j])指結(jié)點(diǎn)j的度.算法2描述了具體計(jì)算方法.

算法2.煙花個(gè)體的適應(yīng)度計(jì)算

輸入:煙花種群的全部個(gè)體

輸出:每個(gè)煙花的適應(yīng)度值

Begin

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

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

依據(jù)公式(4)計(jì)算dd(v[i]);

計(jì)算結(jié)點(diǎn)j的度d(v[j]);

依據(jù)公式(3)計(jì)算出第i個(gè)個(gè)體中第j個(gè)結(jié)點(diǎn)的適應(yīng)度:fv(i,j);

依據(jù)公式(2)計(jì)算出個(gè)體i的適應(yīng)度:FT(v[i]);

End

3.4 爆炸火花數(shù)和爆炸半徑

由于每個(gè)煙花的適應(yīng)度值不同,它們爆炸產(chǎn)生的火花數(shù)和爆炸半徑也不同.其中,適應(yīng)度好的煙花爆炸半徑小且產(chǎn)生的火花數(shù)量較多;反之,適應(yīng)度差的煙花則爆炸半徑較大且產(chǎn)生的火花數(shù)量少,這種爆炸機(jī)制利于算法跳出局部最優(yōu).

在本算法中,若煙花總數(shù)為N,且用Ni來(lái)表示第i個(gè)煙花,則第i個(gè)煙花爆炸產(chǎn)生的火花數(shù)如式(5).

(5)

其中,Si用來(lái)表示第i個(gè)煙花爆炸時(shí)產(chǎn)生的火花數(shù),m是一個(gè)常數(shù),代表每代產(chǎn)生的最大火花總數(shù),Yworst為當(dāng)前所有煙花適應(yīng)度值的最差值,f(xi)是第i個(gè)煙花的適應(yīng)度值,ξ是機(jī)器最小值,用來(lái)避免除零操作.

在算法中,定義一個(gè)煙花可產(chǎn)生的最大火花數(shù)為MaxSN,最小火花數(shù)為MinSN,用來(lái)控制產(chǎn)生的火花數(shù)量,同時(shí)為了保證產(chǎn)生的煙花個(gè)數(shù)為整數(shù),對(duì)Si進(jìn)行四舍五入取整操作,約束如公式(6)所示:

(6)

每個(gè)煙花的爆炸半徑表示為:

(7)

(8)

在算法執(zhí)行過(guò)程中,每一代都會(huì)產(chǎn)生一個(gè)新的Amin,其計(jì)算方法如式(9):

(9)

3.5 爆炸火花和高斯變異火花

3.5.1 爆炸火花

計(jì)算出某一個(gè)煙花的爆炸火花數(shù)和爆炸半徑以后,在爆炸半徑范圍內(nèi),產(chǎn)生一個(gè)隨機(jī)偏移量,爆炸生成新的火花.在原始FWA中,一個(gè)煙花爆炸時(shí),僅計(jì)算一次偏移量,即在隨機(jī)選擇的k個(gè)維度上的偏移量都相同,這大大限制了算法的局部搜索能力.本文通過(guò)單獨(dú)計(jì)算不同維度上的偏移量(即被選擇的k個(gè)維度上的偏移量不相同),來(lái)避免和改善這種缺點(diǎn).按式(10)計(jì)算第i個(gè)煙花第k維上的偏移量,并生成新的火花:

(10)

生成爆炸火花的具體過(guò)程見(jiàn)算法3.

算法3.生成爆炸火花

輸入:煙花種群所有個(gè)體的位置、爆炸火花數(shù)和爆炸半徑

輸出:爆炸火花的位置

Begin

2.設(shè)置爆炸維度個(gè)數(shù):

zk=round(rand(0,1)),k=1,2,…,dim;

計(jì)算偏移量Δxk=Ai×rand(-1,1);

if 超出邊界 then

按映射規(guī)則將煙花映射到可行域內(nèi);

End

3.5.2 高斯變異火花

為了增加種群多樣性,FWA中采用了變異算子來(lái)保持種群的鮮活度.在原始FWA中,高斯變異操作由式(11)計(jì)算完成:

(11)

為了避免以上缺點(diǎn),本文使用的高斯變異火花計(jì)算方法如式(12).

(12)

生成高斯變異火花的具體算法如下:

算法4.生成高斯變異火花

Begin

2.設(shè)置高斯變異的維度個(gè)數(shù):zk=round(rand(0,1)),k=1,2,…,dim;

3.計(jì)算高斯偏移系數(shù):e=Gaussain(0,1);

if 超出邊界 then

End

3.6 映射規(guī)則

當(dāng)火花第k維上的位置超出搜索范圍時(shí),利用均勻分布數(shù)列,按公式(13)將新火花映射到搜索區(qū)域內(nèi)的任意位置:

(13)

3.7 選擇策略

FWA經(jīng)過(guò)爆炸和高斯變異后,產(chǎn)生一批新的火花,將這些火花與種群中的煙花組成合集FTotal,然后根據(jù)選擇策略選擇N個(gè)個(gè)體成為下一代的煙花種群,繼續(xù)進(jìn)行迭代.在本文算法中,采用半保留最優(yōu)個(gè)體策略,首先將所有個(gè)體按適應(yīng)度值降序排列,選擇適應(yīng)度排在前面的N/2個(gè)個(gè)體,然后再?gòu)氖Ｏ碌乃袩熁ê突鸹ㄖ须S機(jī)選擇N/2個(gè)體,一起組成新種群,進(jìn)入下一代.

3.8 Malek模型下的FWA概述

根據(jù)以上各算法步驟,下面給出Malek模型下的FWA,見(jiàn)算法5.

算法5.Malek模型下的煙花算法

輸入:多處理機(jī)系統(tǒng)的故障癥候S

輸出:系統(tǒng)的故障結(jié)點(diǎn)集Fs和無(wú)故障結(jié)點(diǎn)集FF

Begin

1.指定無(wú)故障結(jié)點(diǎn)法初始化煙花種群IF;

2.計(jì)算種群中每個(gè)個(gè)體的適應(yīng)度值FT;

3.計(jì)算爆炸半徑最低檢測(cè)閾值A(chǔ)min;

4.計(jì)算每個(gè)煙花的爆炸火花數(shù)Si和爆炸半徑Ai;

5.產(chǎn)生爆炸火花EF;

6.產(chǎn)生高斯變異火花GF;

7.越界檢測(cè),將越界的火花映射到問(wèn)題可行域內(nèi);

8.計(jì)算種群中所有個(gè)體的適應(yīng)度值FT,按選擇策略選擇N個(gè)個(gè)體成為新種群;

9.輸出與種群中適應(yīng)度值為1的個(gè)體所對(duì)應(yīng)的故障集和無(wú)故障集,若沒(méi)有適應(yīng)度等于1的個(gè)體,則重復(fù)步驟2-9;

End

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

本文的算法實(shí)現(xiàn)采用Matlab語(yǔ)言編寫(xiě),程序運(yùn)行環(huán)境為,CPU:Intel(R)Core(TM)i5-3210M 2.50GHz,內(nèi)存:4.00GB.

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

考慮到煙花算法在不同參數(shù)設(shè)置下,運(yùn)行的結(jié)果差異較大,所以下面將對(duì)各參數(shù)分別進(jìn)行仿真實(shí)驗(yàn),選出較優(yōu)結(jié)果來(lái)進(jìn)行算法的性能測(cè)試.

本文算法中所有實(shí)驗(yàn)均是運(yùn)行100次,計(jì)算平均值的結(jié)果.

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

在其他參數(shù)不變的情況下,將煙花初始種群個(gè)數(shù)設(shè)為N=1:10,得到的實(shí)驗(yàn)結(jié)果如圖1所示,圖中橫坐標(biāo)代表種群煙花個(gè)數(shù),縱坐標(biāo)代表算法執(zhí)行100次的CPU平均運(yùn)行時(shí)間.由圖1中可知,當(dāng)種群煙花個(gè)數(shù)N=2時(shí),CPU運(yùn)行時(shí)間最短,所以將N設(shè)為2.

圖1 種群煙花個(gè)數(shù)對(duì)CPU運(yùn)行時(shí)間的影響Fig.1 Influence of the number of fireworks on the CPU time

4.1.2 爆炸火花數(shù)m

為了測(cè)試每代爆炸產(chǎn)生的火花數(shù)m對(duì)CPU運(yùn)行時(shí)間的影響,將m設(shè)為m=5:5:50,實(shí)驗(yàn)結(jié)果如圖2所示,圖中,橫坐標(biāo)代表最大火花數(shù)m,縱坐標(biāo)代表算法執(zhí)行100次的CPU平均運(yùn)行時(shí)間.由圖2可知,當(dāng)爆炸火花個(gè)數(shù)等于35個(gè)時(shí),CPU平均運(yùn)行時(shí)間最短,故取參數(shù)m=35.

圖2 爆炸火花數(shù)對(duì)CPU運(yùn)行時(shí)間的影響Fig.2 Influence of explosion sparks number on the CPU time

4.1.3 高斯變異個(gè)體的數(shù)量GN

高斯變異個(gè)體的數(shù)量GN分析實(shí)驗(yàn)如圖3所示,圖中,橫坐標(biāo)代表高斯變異個(gè)體數(shù)GN,縱坐標(biāo)代表算法執(zhí)行100次的CPU平均運(yùn)行時(shí)間.由圖3可知,當(dāng)高斯變異個(gè)體數(shù)等于2時(shí),CPU平均運(yùn)行時(shí)間最短,故將GN設(shè)置為2.

4.1.4 爆炸半徑系數(shù)

圖3 高斯變異個(gè)體數(shù)對(duì)算法CPU平均時(shí)間的影響Fig.3 Influence of gaussian mutation individuals number on the CPU time

4.1.5 煙花的維數(shù)dim

本文算法應(yīng)用于故障診斷系統(tǒng),從適應(yīng)度函數(shù)可知,系統(tǒng)多處理機(jī)結(jié)點(diǎn)個(gè)數(shù)與算法中煙花的維數(shù)相對(duì)應(yīng),即dim=n.

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

若最大迭代次數(shù)過(guò)小時(shí),會(huì)出現(xiàn)算法還未找到最優(yōu)值就提前結(jié)束的情況;若最大迭代次數(shù)設(shè)置過(guò)大,則可能會(huì)在算法無(wú)法跳出局部最優(yōu)時(shí)陷入長(zhǎng)時(shí)間的無(wú)用計(jì)算.依據(jù)實(shí)驗(yàn)結(jié)果以及參照文獻(xiàn)[16],將最大迭代次數(shù)設(shè)置為maxEva=300000次可取得較好的效果.

4.2 算法比較

圖4 四種算法的CPU運(yùn)行時(shí)間比較Fig.4 Comparison on the CPU time of four algorithm

文獻(xiàn)[14]中的遺傳算法根據(jù)Malek模型設(shè)計(jì)約束方程,提出新的適應(yīng)度函數(shù),優(yōu)化變異算子,其改進(jìn)的遺傳算法判斷故障集的CPU平均運(yùn)行時(shí)間為0.6540s.而文獻(xiàn)[17]是采用無(wú)故障結(jié)點(diǎn)法生成初始種群,提出了滿足PMC模型中結(jié)點(diǎn)的狀態(tài)值與可相容故障癥候結(jié)點(diǎn)狀態(tài)的方程,并且基于該方程設(shè)計(jì)適應(yīng)度函數(shù),其改進(jìn)的遺傳算法的CPU平均時(shí)間為4.3308s.文獻(xiàn)[18]中采用克隆選擇原理設(shè)計(jì)親和度函數(shù),提出基于人工免疫系統(tǒng)的故障診斷算法AIS_DIAG,該算法的CPU平均時(shí)間為13.173s.而本文算法的CPU平均時(shí)間為0.1989s,可見(jiàn)本文算法能高效解決系統(tǒng)級(jí)故障診斷問(wèn)題,并且其運(yùn)行效率明顯高于文獻(xiàn)[17]、文獻(xiàn)[18]的算法在解決PMC模型下故障診斷問(wèn)題的效率;同時(shí),本文算法的運(yùn)行效率也略高于文獻(xiàn)[14]中的高效遺傳算法.

4.3 算法的時(shí)間復(fù)雜度

假設(shè)多機(jī)系統(tǒng)的結(jié)點(diǎn)個(gè)數(shù)為n,算法迭代次數(shù)為RT,種群煙花個(gè)數(shù)為N,每代煙花爆炸產(chǎn)生的火花個(gè)數(shù)為S,高斯變異火花數(shù)為m.下面按算法5逐步討論本文算法的時(shí)間復(fù)雜度,具體分析過(guò)程如下:

1)按隨機(jī)指定無(wú)故障結(jié)點(diǎn)法生成初始種群:種群煙花數(shù)為N,即循環(huán)N次,每次根據(jù)指定結(jié)點(diǎn)的度來(lái)判斷其它結(jié)點(diǎn)的狀態(tài),每個(gè)結(jié)點(diǎn)的度最多為(n-1),按寬度原則,最壞情況下,產(chǎn)生一個(gè)新的煙花個(gè)體需執(zhí)行k(n-1)步,因此在Malek模型下生成煙花初始種群的時(shí)間復(fù)雜度為O(N·n).

2)計(jì)算煙花種群的適應(yīng)度值:通過(guò)遍歷整個(gè)煙花種群的所有結(jié)點(diǎn)來(lái)計(jì)算個(gè)體的適應(yīng)度,因此,時(shí)間復(fù)雜度為O(N·n).

3)計(jì)算爆炸火花數(shù)和爆炸半徑:計(jì)算爆炸火花數(shù)和爆炸半徑需遍歷種群的所有個(gè)體,所以這一步的時(shí)間復(fù)雜度為O(N).

4)產(chǎn)生爆炸火花:對(duì)種群中所有個(gè)體進(jìn)行爆炸操作,總共生成S個(gè)火花,每個(gè)火花有n維,所以時(shí)間復(fù)雜度為O(S·n).

5)產(chǎn)生高斯變異火花:選擇m個(gè)煙花進(jìn)行高斯變異操作,其中每個(gè)個(gè)體的維數(shù)為n,所以時(shí)間復(fù)雜度為O(m·n).

6)選擇操作:用冒泡排序法將適應(yīng)度降序排列,最壞情況下的時(shí)間復(fù)雜度為O(N2),選擇適應(yīng)度值高的前N/2個(gè)個(gè)體,再隨機(jī)選擇N/2個(gè)個(gè)體,最壞時(shí)間復(fù)雜度為O(N2+N/2).

綜上所述,在最壞情況下,算法重復(fù)迭代RT次的時(shí)間復(fù)雜度為C(RT×(O(N·n)+O(N·n)+O(N)+O(S·n)+O(m·n)+O(N2+N/2))),即O(RT·(n·(N+S+m)+N2)).由此可見(jiàn),本文算法的時(shí)間復(fù)雜度與算法迭代次數(shù)、處理機(jī)結(jié)點(diǎn)數(shù)、煙花種群個(gè)體數(shù)、爆炸火花數(shù)及高斯變異個(gè)體數(shù)有關(guān),當(dāng)后面三個(gè)參數(shù)確定時(shí),算法的時(shí)間復(fù)雜度僅與算法迭代次數(shù)和處理機(jī)結(jié)點(diǎn)數(shù)相關(guān).

5 結(jié)束語(yǔ)

FWA具有良好的局部搜索和全局搜索能力,本文將改進(jìn)的FWA應(yīng)用于解決Malek模型下的系統(tǒng)級(jí)故障診斷問(wèn)題.文中首先介紹了Malek模型的定義和FWA的概述,通過(guò)實(shí)驗(yàn)分析了各參數(shù)的設(shè)置,并給出本文算法的偽代碼,接著進(jìn)行仿真實(shí)驗(yàn)將本文算法與三種算法進(jìn)行比較,最后根據(jù)算法步驟分析本文算法的時(shí)間復(fù)雜度.目前,FWA在系統(tǒng)級(jí)故障診斷中的研究還較少見(jiàn),且本文FWA的各參數(shù)較簡(jiǎn)單,所以接下來(lái)將會(huì)進(jìn)一步研究各參數(shù)的改進(jìn),或者加入其它算法的特點(diǎn)元素.