Malek模型下的系統級故障診斷煙花算法

歸偉夏,藍 婷,陸 倩

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

1 引 言

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

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

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

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

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

2 預備知識

2.1 Malek模型

1980年,Malek提出了基于比較的非對稱模型——Malek模型,故障模式、故障癥候以及拓撲結構是該模型的三個重要因素.故障模式是系統中所有結點的狀態集合,故障癥候是基于故障模式、故障診斷模型及拓撲結構而得的所有邊的狀態集合,這個集合就是與該故障模式相容的一個故障癥候.在同一個系統中,故障模式與故障癥候的對應關系為:一個故障模式可對應于多個故障癥候,而一個故障癥候也可對應于多個故障模式.

在Malek模型下,系統內的結點兩兩之間執行相同的任務得到一個結果,然后比較這個結果是否相同來得到關于邊的信息,這些所有的邊構成了一個無向圖.如表1所示為Malek模型定義,其中,結點狀態表示為:1是故障結點,0是無故障結點;比較結果的邊狀態表示為:1代表兩個結點得到不同的測試結果,0代表兩個結點得到相同的測試結果.

表1 Malek模型
Table 1 Malek Model

結點ui狀態結點uj狀態比較結果邊eij狀態000011101111

2.2 相關定義

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

定理1.Malek模型中的兩個關聯結點ui,uj的狀態值與它們的相關邊eij滿足如下方程組:

(1)

證明:當兩個結點的測試結果一致,即eij=0時,查表1可知:ui=0且uj=0,代入方程:左邊=ui+uj=0=右邊,滿足約束方程;

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

綜上所述,定理1成立.

2.3 煙花算法

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

3 算法步驟

3.1 字串表示

在系統級故障診斷中,用1表示有故障結點,用0表示無故障結點,則可以用長度為n的二進制串來表示一個含有n個結點的系統,其中,字串的第i位表示對應結點ui有/無故障.例如,(0100010001)表示含有10個結點的多處理機系統,其故障模式為Fs={u2,u6,u10}.該系統以“t-可診斷性”為前提,所以故障結點數|Fs|∈[1,…,t].

3.2 初始種群

在文獻[14]中已經將文獻[15]提出的指定無故障結點生成初始種群的方法應用到Malek模型中,并取得了較好的效果,本文也采用這種方法來生成初始種群,算法1描述了其計算過程.

算法1.隨機指定無故障結點法生成初始種群

輸入:故障癥候S

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

Begin

1.在結點數為n的系統內,隨機選定一個結點ui,指定其狀態為0,即該結點無故障;

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

3.將步驟2中得到的所有無故障結點執行步驟2;

4.對不確定結點隨機指定狀態;

5.檢測個體是否滿足“t-可診斷性”,若故障結點數不滿足條件,則返回步驟1繼續執行;

End

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

3.3 適應度函數

本文通過計算個體中每個結點的度來得到個體的適應度,適應度函數定義如下:

(2)

(3)

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

(4)

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

算法2.煙花個體的適應度計算

輸入:煙花種群的全部個體

輸出:每個煙花的適應度值

Begin

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

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

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

計算結點j的度d(v[j]);

依據公式(3)計算出第i個個體中第j個結點的適應度:fv(i,j);

依據公式(2)計算出個體i的適應度:FT(v[i]);

End

3.4 爆炸火花數和爆炸半徑

由于每個煙花的適應度值不同,它們爆炸產生的火花數和爆炸半徑也不同.其中,適應度好的煙花爆炸半徑小且產生的火花數量較多;反之,適應度差的煙花則爆炸半徑較大且產生的火花數量少,這種爆炸機制利于算法跳出局部最優.

在本算法中,若煙花總數為N,且用Ni來表示第i個煙花,則第i個煙花爆炸產生的火花數如式(5).

(5)

其中,Si用來表示第i個煙花爆炸時產生的火花數,m是一個常數,代表每代產生的最大火花總數,Yworst為當前所有煙花適應度值的最差值,f(xi)是第i個煙花的適應度值,ξ是機器最小值,用來避免除零操作.

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

(6)

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

(7)

(8)

在算法執行過程中,每一代都會產生一個新的Amin,其計算方法如式(9):

(9)

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

3.5.1 爆炸火花

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

(10)

生成爆炸火花的具體過程見算法3.

算法3.生成爆炸火花

輸入:煙花種群所有個體的位置、爆炸火花數和爆炸半徑

輸出:爆炸火花的位置

Begin

2.設置爆炸維度個數:

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

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

if 超出邊界 then

按映射規則將煙花映射到可行域內;

End

3.5.2 高斯變異火花

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

(11)

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

(12)

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

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

Begin

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

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

if 超出邊界 then

End

3.6 映射規則

當火花第k維上的位置超出搜索范圍時,利用均勻分布數列,按公式(13)將新火花映射到搜索區域內的任意位置:

(13)

3.7 選擇策略

FWA經過爆炸和高斯變異后,產生一批新的火花,將這些火花與種群中的煙花組成合集FTotal,然后根據選擇策略選擇N個個體成為下一代的煙花種群,繼續進行迭代.在本文算法中,采用半保留最優個體策略,首先將所有個體按適應度值降序排列,選擇適應度排在前面的N/2個個體,然后再從剩下的所有煙花和火花中隨機選擇N/2個體,一起組成新種群,進入下一代.

3.8 Malek模型下的FWA概述

根據以上各算法步驟,下面給出Malek模型下的FWA,見算法5.

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

輸入:多處理機系統的故障癥候S

輸出:系統的故障結點集Fs和無故障結點集FF

Begin

1.指定無故障結點法初始化煙花種群IF;

2.計算種群中每個個體的適應度值FT;

3.計算爆炸半徑最低檢測閾值Amin;

4.計算每個煙花的爆炸火花數Si和爆炸半徑Ai;

5.產生爆炸火花EF;

6.產生高斯變異火花GF;

7.越界檢測,將越界的火花映射到問題可行域內;

8.計算種群中所有個體的適應度值FT,按選擇策略選擇N個個體成為新種群;

9.輸出與種群中適應度值為1的個體所對應的故障集和無故障集,若沒有適應度等于1的個體,則重復步驟2-9;

End

4 算法的實現與分析

本文的算法實現采用Matlab語言編寫,程序運行環境為,CPU:Intel(R)Core(TM)i5-3210M 2.50GHz,內存:4.00GB.

4.1 參數設置

考慮到煙花算法在不同參數設置下,運行的結果差異較大,所以下面將對各參數分別進行仿真實驗,選出較優結果來進行算法的性能測試.

本文算法中所有實驗均是運行100次,計算平均值的結果.

4.1.1 初始種群煙花個數N

在其他參數不變的情況下,將煙花初始種群個數設為N=1:10,得到的實驗結果如圖1所示,圖中橫坐標代表種群煙花個數,縱坐標代表算法執行100次的CPU平均運行時間.由圖1中可知,當種群煙花個數N=2時,CPU運行時間最短,所以將N設為2.

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

4.1.2 爆炸火花數m

為了測試每代爆炸產生的火花數m對CPU運行時間的影響,將m設為m=5:5:50,實驗結果如圖2所示,圖中,橫坐標代表最大火花數m,縱坐標代表算法執行100次的CPU平均運行時間.由圖2可知,當爆炸火花個數等于35個時,CPU平均運行時間最短,故取參數m=35.

圖2 爆炸火花數對CPU運行時間的影響Fig.2 Influence of explosion sparks number on the CPU time

4.1.3 高斯變異個體的數量GN

高斯變異個體的數量GN分析實驗如圖3所示,圖中,橫坐標代表高斯變異個體數GN,縱坐標代表算法執行100次的CPU平均運行時間.由圖3可知,當高斯變異個體數等于2時,CPU平均運行時間最短,故將GN設置為2.

4.1.4 爆炸半徑系數

圖3 高斯變異個體數對算法CPU平均時間的影響Fig.3 Influence of gaussian mutation individuals number on the CPU time

4.1.5 煙花的維數dim

本文算法應用于故障診斷系統,從適應度函數可知,系統多處理機結點個數與算法中煙花的維數相對應,即dim=n.

4.1.6 算法最大迭代次數

若最大迭代次數過小時,會出現算法還未找到最優值就提前結束的情況;若最大迭代次數設置過大,則可能會在算法無法跳出局部最優時陷入長時間的無用計算.依據實驗結果以及參照文獻[16],將最大迭代次數設置為maxEva=300000次可取得較好的效果.

4.2 算法比較

圖4 四種算法的CPU運行時間比較Fig.4 Comparison on the CPU time of four algorithm

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

4.3 算法的時間復雜度

假設多機系統的結點個數為n,算法迭代次數為RT,種群煙花個數為N,每代煙花爆炸產生的火花個數為S,高斯變異火花數為m.下面按算法5逐步討論本文算法的時間復雜度,具體分析過程如下:

1)按隨機指定無故障結點法生成初始種群:種群煙花數為N,即循環N次,每次根據指定結點的度來判斷其它結點的狀態,每個結點的度最多為(n-1),按寬度原則,最壞情況下,產生一個新的煙花個體需執行k(n-1)步,因此在Malek模型下生成煙花初始種群的時間復雜度為O(N·n).

2)計算煙花種群的適應度值:通過遍歷整個煙花種群的所有結點來計算個體的適應度,因此,時間復雜度為O(N·n).

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

4)產生爆炸火花:對種群中所有個體進行爆炸操作,總共生成S個火花,每個火花有n維,所以時間復雜度為O(S·n).

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

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

綜上所述,在最壞情況下,算法重復迭代RT次的時間復雜度為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)).由此可見,本文算法的時間復雜度與算法迭代次數、處理機結點數、煙花種群個體數、爆炸火花數及高斯變異個體數有關,當后面三個參數確定時,算法的時間復雜度僅與算法迭代次數和處理機結點數相關.

5 結束語

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