鄧　露, 許愛強, 吳忠德

(海軍航空工程學(xué)院飛行器檢測與應(yīng)用研究所, 山東 煙臺 264001)

?

基于遺傳算法的故障樣本優(yōu)化選取方法

鄧露, 許愛強, 吳忠德

(海軍航空工程學(xué)院飛行器檢測與應(yīng)用研究所, 山東 煙臺 264001)

摘要：為降低測試性驗證試驗費用,提出基于遺傳算法的故障樣本優(yōu)化選取方法。方法通過故障—測試關(guān)聯(lián)分析和故障—故障等價分析,確定初始故障樣本集中各元素對應(yīng)的等價集,并對初始故障樣本集進(jìn)行擴展,在此基礎(chǔ)上,建立了故障樣本選取優(yōu)化求解模型。在不降低樣本注入數(shù)量和測試特性的條件下,以試驗費用最小為優(yōu)化目標(biāo),給出了基于改進(jìn)遺傳算法的樣本優(yōu)化選取方法。算例應(yīng)用結(jié)果表明,該方法設(shè)計的故障樣本選取方法能有效降低測試性驗證試驗費用。

關(guān)鍵詞：測試性驗證試驗; 試驗費用; 遺傳算法; 故障樣本選取; 等價集

0引言

測試性驗證試驗是指在研制的產(chǎn)品中注入一定數(shù)量的故障，用測試性設(shè)計規(guī)定的方法進(jìn)行故障檢測與隔離，按其結(jié)果來估計產(chǎn)品的測試性水平，并判斷是否達(dá)到了規(guī)定的要求，決定接收或絕收[1-3]。作為測試性驗證試驗的一項重要內(nèi)容,故障樣本選取主要任務(wù)是,根據(jù)制定的測試性驗證試驗方案選擇合理、經(jīng)濟、可行的故障注入樣本。

目前,針對測試性驗證試驗故障樣本選取問題還沒有專用的標(biāo)準(zhǔn)。MIL-STD-471A臨時通告2[4]以標(biāo)準(zhǔn)附件的形式給出了測試性驗證方法,即采用與維修性驗證相同的基于故障率比例的分層抽樣方法選取故障樣本。ADA報告[5]提出以二項分布和多項分布為基礎(chǔ)來確定試驗所需樣本量和合格判定數(shù)。文獻(xiàn)[6]在建立故障信息模型的基礎(chǔ)上,提出了樣本集的信息覆蓋充分性度量方法和準(zhǔn)則。文獻(xiàn)[7]通過構(gòu)建功能—重要度二元組故障特征模型,提出基于該故障特征模型的測試性測定試驗樣本選取方法和步驟。文獻(xiàn)[8]基于多信號流圖模型,建立了故障—故障相關(guān)矩陣,在滿足充分覆蓋約束條件下,提出了最小故障樣本集選取方法。文獻(xiàn)[9]針對故障模式之間的復(fù)雜性與不確定性關(guān)系,建立了模糊概率Petri網(wǎng)故障擴散模型,提出了基于故障率和故障擴散強度的故障樣本選擇方法。文獻(xiàn)[10]針對故障樣本不可注入或注入成本高的問題,在對故障樣本進(jìn)行功能等價劃分和測試等價劃分的基礎(chǔ)上,根據(jù)測試點上不同測試對應(yīng)的功能屬性設(shè)計了一種故障樣本等價算法。

上述方法針對測試性驗證試驗故障樣本選取問題,提出了不同的解決方法,取得了一定效果。本文在上述研究的基礎(chǔ)上,結(jié)合故障等價替換注入和故障順序注入兩個因素，對減少試驗費用的影響,提出了基于遺傳算法的故障樣本優(yōu)化選取方法。

1數(shù)學(xué)模型與問題描述

1.1數(shù)學(xué)模型

設(shè)系統(tǒng)的故障模式集F={f1,f2,…,fn},測試集T={t1,t2,…,tm},n為F的基數(shù),亦即該系統(tǒng)所有故障模式的數(shù)量(F可通過故障模式影響及危害性分析和故障樹分析獲得),m為T的基數(shù),亦即該系統(tǒng)所有測試的數(shù)量(T可通過測試性設(shè)計分析獲得)。

定義 1故障—測試關(guān)聯(lián)矩陣[11]

(1)

式中,rij為故障fi與測試tj之間的相關(guān)性系數(shù),且有

(2)

定義 2故障—測試關(guān)聯(lián)向量

任取故障—測試關(guān)聯(lián)矩陣R中的一行ri:,稱向量ri:為故障fi的測試關(guān)聯(lián)向量,記為FTfi,當(dāng)故障fi發(fā)生時,測試向量中與FTfi對應(yīng)的測試會發(fā)生異常變化。

定義 3故障—故障等價矩陣[12]

(3)

式中,eij為故障fi與故障fj之間的等價性系數(shù),且有

(4)

若故障fi與故障fj等價,即eij=1,則故障fi的測試關(guān)聯(lián)向量FTfi與故障fj的測試關(guān)聯(lián)向量FTfj完全相同;若故障fi與故障fj不等價,即eij=0,則故障fi的測試關(guān)聯(lián)向量FTfi與故障fj的測試關(guān)聯(lián)向量FTfj不完全相同。

定義 4故障等價集

在故障—故障等價矩陣EFF的第i行中,取值為1的所有元素對應(yīng)的故障模式組成的集合稱為故障等價集,記為EF。當(dāng)EF中的任意兩個故障i和j發(fā)生時,對應(yīng)產(chǎn)生的兩個故障—測試關(guān)聯(lián)向量FTfi與FTfj完全相同。

定義 5故障順序注入費用

故障順序注入費用是指在進(jìn)行測試性驗證試驗時某一故障完成注入后,進(jìn)行下一故障注入所需的費用,記為c。故障順序注入費用主要包括某一故障注入后系統(tǒng)恢復(fù),下一故障注入所需人員配置和場地重新布置,故障注入方式與注入設(shè)備重新選擇,實際故障注入以及故障注入準(zhǔn)備周期等因素造成的直接或間接費用總和。

定義 6故障順序注入費用矩陣

(5)

式中,cij為故障fi完成注入后,進(jìn)行故障fj注入所需的費用。

1.2問題描述

設(shè)根據(jù)制定的測試性驗證試驗和樣本選取方法,選取的初始注入故障樣本集為FI。擴展后的故障樣本集為FI′,擴展后的故障樣本集中的各元素對應(yīng)為初始樣本集各元素(包含自身)的等價集?；谶z傳算法的故障樣本優(yōu)化選取方法需要解決的問題是:從擴展的故障樣本集中求解試驗費用最小的故障樣本集及其注入順序,求解模型如圖1所示。

圖1　故障樣本選取模型

圖1中,圓點表示故障模式;實線圓弧內(nèi)的故障模式為一個故障等價集;虛線圓弧內(nèi)的故障模式為孤立故障,表示不存在與自身不同的等價故障。

2構(gòu)建樣本優(yōu)化選取求解模型

設(shè)系統(tǒng)的故障模式集為F={f1,f2,…,fn},根據(jù)試驗方案和樣本選取方法選取的初始注入故障樣本集為FI={ff1,ff2,…,ffi,…,ffu},u為集合FI的基數(shù),表示待注入故障樣本的數(shù)量。通過系統(tǒng)故障—測試關(guān)聯(lián)分析和故障—故障等價分析,對于FI中的任意一個故障模式ffi可以得到一個其對應(yīng)的故障等價集EFffi。若范數(shù)|EFffi|>1,即ffi存在至少一個不同于自身,且與自身等價的故障,則稱ffi為冗余故障;若范數(shù)|EFffi|=1,即EFffi={ffi},表明不存在其他與其自身等價的故障,則稱ffi為孤立故障。

根據(jù)得到的試驗初始注入故障樣本集中元素的等價集,對FI進(jìn)行擴展,設(shè)擴展后的待注入故障樣本集為

(6)

根據(jù)|EFffi|的不同取值,將FI′劃分成兩部分,即

(7)

(8)

式中

(9)

(10)

將擴展待注入故障樣本集中的冗余故障等價集和孤立故障等價集排列如下:

(11)

按上式順序,將擴展待注入故障樣本集中的冗余故障等價集和孤立故障等價集重新記為

(12)

則

(13)

圖2優(yōu)化求解模型

需要指出，對于第一個注入故障,由于在其之前沒有進(jìn)行故障注入,論文對其進(jìn)行處理時,將其作為最后一個注入故障的下一注入故障,其注入費用記為cu1。

3改進(jìn)遺傳算法的樣本選取方法

3.1目標(biāo)函數(shù)

故障樣本優(yōu)化選取問題的目的是求解滿足測試性驗證試驗方案要求的費用最小的故障樣本集。根據(jù)上述建立的故障樣本優(yōu)化選取求解模型,定義求解故障樣本選取問題的目標(biāo)函數(shù)為

(14)

式中,Tc為測試性驗證試驗故障注入需要的總費用;ωj為擴展注入故障樣本集中的第j個元素;c(fΠ(i),fΠ(i+1))為故障fΠ(i)注入后,進(jìn)行故障fΠ(i+1)注入的費用,根據(jù)定義5和定義6可將其記為cΠ(i),Π(i+1);Π(1),Π(2),…,Π(u)為1,2,…,u的全排列。

3.2求解樣本優(yōu)化選取問題的改進(jìn)遺傳算法

針對最小路徑求解問題和廣義旅行商求解問題,文獻(xiàn)[14-15]提出了遺傳算法及其改進(jìn)算法,在解決該類問題中取得了較好的效果。故障樣本優(yōu)化選取問題可以看作上述問題的擴展,其不同在于最小路徑求解問題和廣義旅行商求解問題中兩點之間的距離不變,而故障樣本優(yōu)化選取問題中兩個相同的故障模式,不同的注入順序?qū)?yīng)的費用可能不同,即故障順序注入費用矩陣C中cij與cji可能不相等。在此采用改進(jìn)遺傳算法進(jìn)行求解,算法的流程如圖3所示,主要步驟如下:

步驟 1初始化種群。利用初始化算子產(chǎn)生初始化的種群,初始種群為一個二元隨機算子,作用的變元為H和B,若種群大小為sp,則初始化的種群P可以表示為

(15)

步驟 2創(chuàng)建繁衍種群。按照“適者生存”的法則在父代群體中選取健壯的個體放入臨時種群—繁衍種群,直至繁衍種群得規(guī)模至sp。

步驟 3交叉過程。隨機在繁衍群體中選擇一對個體,并產(chǎn)生[0,1]之間的隨機數(shù)ρ,如果ρ小于交叉設(shè)置的概率pc,則對選取的一對父代個體施加交叉算子,以產(chǎn)生新的子代個體;否則直接把選取的一對父代個體作為子代個體,交叉算子是一個二元隨機算子,作用的變元為故障樣本選取費用優(yōu)化求解模型中的基因。

步驟 4變異過程。產(chǎn)生[0,1]之間的隨機數(shù)η。如果η小于變異概率ηm,則施加變異算子于子代個體;否則,不產(chǎn)生變異。變異算子是一個一元隨機算子,作用的變元為故障樣本選取費用優(yōu)化求解模型中的基因。

步驟 5逆轉(zhuǎn)過程。施加逆轉(zhuǎn)算子于子代個體,以增加子代個體的適應(yīng)度,逆轉(zhuǎn)算子是一個一元隨機算子,作用的變元為故障樣本選取費用優(yōu)化求解模型中的基因。

步驟 7記當(dāng)前進(jìn)化的代數(shù)為k，如果k小于最大進(jìn)化代數(shù)K,則轉(zhuǎn)到步驟2;否則,輸出進(jìn)化結(jié)果,終止。

圖3　算法流程圖

4算例應(yīng)用

4.1算例說明

以某航空裝備的天線展開和旋轉(zhuǎn)系統(tǒng)為例,對其進(jìn)行測試性驗證故障樣本選取研究。該系統(tǒng)共包括10個獨立的結(jié)構(gòu)單元,各個單元的故障率如表1所示。根據(jù)可靠性分析得到該系統(tǒng)共有287個故障模式(限于論文篇幅要求,這里省略具體的結(jié)構(gòu)單元名稱和故障模式名稱)。設(shè)依據(jù)制定的測試性驗證試驗方案[16],確定試驗需要注入的故障樣本數(shù)量為34,并按故障率相對比例選取出初始待注入樣本集[17],各單元分配樣本量如表1所示。

表1　系統(tǒng)結(jié)構(gòu)單元名稱、故障率及分配樣本量

4.2結(jié)果分析

根據(jù)定義5,對選取的初始待注入樣本集中的34個故障模式進(jìn)行順序注入費用分析(順序注入費用由測試性專家預(yù)測確定),記得出的故障順序注入費用矩陣為C34×34。為了方便對比分析和圖形表示,論文在進(jìn)行算例應(yīng)用分析時假設(shè)C34×34為對稱矩陣(C34×34為不對稱矩陣時,問題求解方法相同,且分析假設(shè)不失結(jié)果的一般性)。利用Matlab仿真軟件,隨機產(chǎn)生一個1~34全排列,根據(jù)產(chǎn)生的全排列確定一條故障隨機選取注入序列,如圖4所示,圖中圓圈表示故障模式,其右上角的數(shù)字對應(yīng)為故障模式序號,兩圓圈之間的距離表示注入需要的費用。

圖4　樣本隨機選取

圖5給出了運行參數(shù)取值為:交叉概率0.9,變異概率0.05,編碼長度34,群體大小200。最大代數(shù)1 000的條件下,初始注入樣本集中的34個故障模式采用遺傳算法求解得到的費用最小的優(yōu)化選取注入序列。對比圖4和圖5可以看出,采用優(yōu)化選取方法進(jìn)行試驗所需的費用顯著低于采用隨機選取的方法。

圖5　樣本優(yōu)化選取

通過故障等價分析,得出初始注入故障樣本集中存在12個冗余故障和22個孤立故障。根據(jù)得到的12個冗余故障的等價集,對初始注入故障樣本集進(jìn)行擴展,擴展后的注入故障樣本集共包含59個故障模式。圖6給出了擴展注入故障樣本集中故障順序注入相對費用分布圖。圖中三角形表示冗余故障的等價故障,其右上角數(shù)字為等價故障對應(yīng)的冗余故障在初始注入樣本集中對應(yīng)的序號。

圖6　擴展樣本分布

圖7給出了擴展注入樣本集基于遺傳算法優(yōu)化選取得到的最小費用故障注入樣本及其注入序列。

圖7　樣本等效優(yōu)化選取

圖8給出了上述3種不同樣本選取方法對應(yīng)所需試驗費用的直方圖,圖中1、2、3分別表示采用樣本隨機選取、樣本優(yōu)化選取、樣本等效優(yōu)化選取方法試驗所需的費用。

圖8　注入方法與試驗費用

圖9給出了上述3種不同樣本選取方法在試驗樣本量不同的情況下對應(yīng)所需試驗費用。

圖9　不同樣本量試驗費用

表2給出了圖9中3種不同樣本選取方法在試驗樣本量不同的情況下對應(yīng)所需試驗費用的數(shù)值,從表2中可以看出:

(1) 當(dāng)初始注入樣本為34時,采用樣本優(yōu)化選取方法進(jìn)行試驗所需的費用約為采用隨機樣本選取方法所需費用的33.8%,采用樣本等價優(yōu)化選取方法進(jìn)行試驗,相比于不對樣本集擴展,試驗費用減少了約28.4%。

(2) 當(dāng)初始注入樣本為51時,相比于隨機樣本選取方法,采用樣本優(yōu)化選取方法進(jìn)行試驗所需的費用減少了約71.7%,采用樣本等價優(yōu)化選取方法進(jìn)行試驗,試驗費用可以進(jìn)一步減少約9.8%。

(3) 當(dāng)初始注入樣本為68時,采用樣本優(yōu)化選取方法進(jìn)行試驗所需的費用約為采用隨機樣本選取方法所需費用的25.6%,采用樣本等價優(yōu)化選取方法進(jìn)行試驗約為采用隨機樣本選取方法所需費用的16.1%。

(4) 由分析結(jié)果(1)、(2)、(3)可知,隨著試驗樣本量的增加,相比于隨機抽樣選取方法,采用樣本等效優(yōu)化選取方法進(jìn)行注入試驗所需的費用降低得越顯著。

表2　不同樣本下的試驗費用

5結(jié)論

本文針對故障樣本優(yōu)化選取問題,提出基于遺傳算法的故障樣本優(yōu)化選取方法。方法利用故障等價替換和樣本順序注入減少試驗費用,并通過算例進(jìn)行了驗證。從分析結(jié)果來看,在相同樣本數(shù)量和測試條件下,相比于樣本隨機選取注入方法,采用本文提出的故障樣本優(yōu)化選取方法進(jìn)行試驗?zāi)軌蛴行Ч?jié)約試驗費用,具有較強的工程實用性。

參考文獻(xiàn)：

[1] Jr Anderson J L, Figurerres Z E, Hovakemian A. Using ATE simulation to develop test procedures and verify testability for the standard missile[C]∥Proc.oftheIEEESystemsReadinessTechnologyConference, 1998: 28-34.

[2] Tian Z, Shi J Y.Systemtestabilitydesignanalysisanddemonstration[M]. Beijing: Beijing University of Aeronautics and Astronautics Press, 2003. (田仲, 石君友. 系統(tǒng)測試性設(shè)計分析與驗證[M]. 北京: 北京航空航天大學(xué)出版社, 2003.)

[3] Unger L Y. Testability design prevents harm[J].IEEEAerospaceandElectronicSystemsMagazine, 2010, 25(3): 35-43.

[4] Department of Defense. Main-tainability verification/ demonstration/ evaluation[S]. MIL-STD-471A.Columkia:U.S. Government Printing Office, 1978.

[5] Pliska T F, Angus J, Jew F L. BIT/external test figures of me-rit and demonstration techniques[R]. ADA 081128. U.S. Go-vernment Printing Office,1979.

[6] Shi J Y, Kang R. Study on the plan of testability demonstration based on the general adequacy criterion[J].ActaAeronauticaetAstronauticaSinica, 2005, 26(6): 691-695. (石君友, 康銳. 基于通用充分性準(zhǔn)則的測試性試驗方案研究[J]. 航空學(xué)報, 2005, 26(6): 691-695.)

[7] Xu P, Kang R. Concept of testability determine test and relative method for FDR[J].JournalofBeijingUniversityofAeronauticsandAstronautics,2007,33(3):357-360.(徐萍,康銳.考慮FDR的測試性測定試驗及其相關(guān)方法[J].北京航空航天大學(xué)學(xué)報,2007,33(3):357-360.)

[8] Li T M, Qiu J, Liu G J. Sample selection of testability verification experiment based on multi-signal modeling methodology[J].SystemsEngineeringandElectronics, 2008, 30(11): 2284-2287. (李天梅, 邱靜, 劉冠軍. 基于多信號流圖的測試性驗證試驗樣本選取方法[J]. 系統(tǒng)工程與電子技術(shù), 2008, 30(11): 2284-2287.)

[9] Li T M, Qiu J, Liu G J, et al. A failure sample selection method considering failure pervasion intensity in testability demonstration test[J].ActaArmamentarii, 2009, 5(3): 228-233.

[10] Gu J, Wang H X. Fault sample equivalence method based on extended dependency matrix[J].JournalofNavalUniversityofEngineering, 2012, 24(5): 70-74. (辜健, 王紅霞. 基于擴展關(guān)聯(lián)矩陣的故障樣本等價方法[J]. 海軍工程大學(xué)學(xué)報, 2012, 24(5): 70-74.)

[11] Shakei M. Advance in system fault modeling and diagnosis[D]. Connecticut: University of Connecticut, 1996: 216-218.

[12] Li T M, Hu C H, Zhou X. Fault injection method resulting from inaccessible location fault based on fault propagation characteristics[J].ActaAeronauticaetAstronauticaSinica， 2011, 32(12): 2277-2286. (李天梅, 胡昌華, 周鑫. 基于故障傳遞特性的位置不可訪問故障注入方法[J]. 航空學(xué)報, 2011, 32(12): 2277-2286.)

[13] Wu C G, Yang J H, Lee H P, et al. Generalized chromosome genetic algorithm for generalized traveling salesman problems and its applications for machining[J].PhysicalReviewE, 2004, 70(2): 1-13.

[14] Dorigo M, Gambardella L M. Ant colony optimization for the travelling salesman problem[J].Biosystems,1997,43(2):73-81.

[15] Yang J H, Wu C G, Lee H P, et al. Solving traveling salesman problems using generalized chromosome genetic algorithm[J].ProgressinNaturalScience, 2008, 18(7): 887-892.

[16] Chang C H, Yang J P, Cao P J. Study on the scheme of testability demonstration test based on development information[J].ActaAeronauticaetAstronauticaSinica, 2012, 33(11): 2057-2064. (常春賀, 楊江平, 曹鵬舉. 基于研制信息的測試性驗證試驗方案研究[J]. 航空學(xué)報, 2012, 33(11): 2057-2064.)

[17] National Science and Technology Industrial Committee. Maintainability test and evaluation[S].GJB 2072-94.Beijing: Standards Press of China,1994.(國防科學(xué)技術(shù)工業(yè)委員會.維修性試驗與評定[S].GJB2072-94.北京:中國標(biāo)準(zhǔn)出版社,1994.)

鄧露(1986-),男,博士研究生,主要研究方向為測試性驗證試驗與評估。

E-mail:starprain332990024@126.com

許愛強(1963-),男,教授,博士,主要研究方向為測試性設(shè)計分析與驗證、自動測試技術(shù)、故障診斷技術(shù)。

E-mail:xuaq6342@yahoo.com.cn

吳忠德(1982-),男,講師,碩士,主要研究方向為自動測試技術(shù)、故障診斷技術(shù)。

E-mail:wzd99117@163.com

網(wǎng)絡(luò)優(yōu)先出版地址：http://www.cnki.net/kcms/detail/11.2422.TN.20141030.1135.012.html

Method of failure sample optimization selection

based on genetic algorithm

DENG Lu, XU Ai-qiang, WU Zhong-de

(ResearchInstituteofAircraftDetectionandApplication,NavalAeronauticaland

AstronauticalUniversity,Yantai264001,China)

Abstract:Aiming to the cost of testability verification experiment, a method of failure sample optimization selection based on the genetic algorithm is proposed. Through the analyses of fault-test correlation and fault-fault equivalent, the alternative failure sample concentration equivalent set of each element is determined and the extension alternative failure sample set is established. On this basis the solving model of failure sample optimization selection is set up. Without reducing the sample injection quantity and the characteristics of the test conditions, the coding model of sample optimization selection is built by using the generalized chromosome. A method of failure sample selection and sequence injection is put forward based on the genetic algorithm, which takes the minimum cost as the optimization goal. Finally, an example results show that this method can effectively reduce the test cost.

Keywords:testability verification experiment; test cost; genetic algorithm; failure sample selection; equivalent set

作者簡介：

中圖分類號：TP806+.1

文獻(xiàn)標(biāo)志碼：A

DOI:10.3969/j.issn.1001-506X.2015.07.36

基金項目：總裝武器裝備預(yù)研基金(9140A27020212JB14311)資助課題

收稿日期：2014-04-24；修回日期：2014-09-01；網(wǎng)絡(luò)優(yōu)先出版日期：2014-10-30。