基于遺傳算法的故障樣本優化選取方法

鄧　露, 許愛強, 吳忠德

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

?

基于遺傳算法的故障樣本優化選取方法

鄧露, 許愛強, 吳忠德

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

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

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

0引言

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

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

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

1數學模型與問題描述

1.1數學模型

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

定義 1故障—測試關聯矩陣[11]

(1)

式中,rij為故障fi與測試tj之間的相關性系數,且有

(2)

定義 2故障—測試關聯向量

任取故障—測試關聯矩陣R中的一行ri:,稱向量ri:為故障fi的測試關聯向量,記為FTfi,當故障fi發生時,測試向量中與FTfi對應的測試會發生異常變化。

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

(3)

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

(4)

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

定義 4故障等價集

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

定義 5故障順序注入費用

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

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

(5)

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

1.2問題描述

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

圖1　故障樣本選取模型

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

2構建樣本優化選取求解模型

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

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

(6)

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

(7)

(8)

式中

(9)

(10)

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

(11)

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

(12)

則

(13)

圖2優化求解模型

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

3改進遺傳算法的樣本選取方法

3.1目標函數

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

(14)

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

3.2求解樣本優化選取問題的改進遺傳算法

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

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

(15)

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

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

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

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

步驟 7記當前進化的代數為k，如果k小于最大進化代數K,則轉到步驟2;否則,輸出進化結果,終止。

圖3　算法流程圖

4算例應用

4.1算例說明

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

表1　系統結構單元名稱、故障率及分配樣本量

4.2結果分析

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

圖4　樣本隨機選取

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

圖5　樣本優化選取

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

圖6　擴展樣本分布

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

圖7　樣本等效優化選取

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

圖8　注入方法與試驗費用

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

圖9　不同樣本量試驗費用

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

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

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

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

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

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

5結論

本文針對故障樣本優化選取問題,提出基于遺傳算法的故障樣本優化選取方法。方法利用故障等價替換和樣本順序注入減少試驗費用,并通過算例進行了驗證。從分析結果來看,在相同樣本數量和測試條件下,相比于樣本隨機選取注入方法,采用本文提出的故障樣本優化選取方法進行試驗能夠有效節約試驗費用,具有較強的工程實用性。

參考文獻：

[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. (田仲, 石君友. 系統測試性設計分析與驗證[M]. 北京: 北京航空航天大學出版社, 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. (石君友, 康銳. 基于通用充分性準則的測試性試驗方案研究[J]. 航空學報, 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的測試性測定試驗及其相關方法[J].北京航空航天大學學報,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]. 系統工程與電子技術, 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. (辜健, 王紅霞. 基于擴展關聯矩陣的故障樣本等價方法[J]. 海軍工程大學學報, 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]. 航空學報, 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]. 航空學報, 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.(國防科學技術工業委員會.維修性試驗與評定[S].GJB2072-94.北京:中國標準出版社,1994.)

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

E-mail:starprain332990024@126.com

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

E-mail:xuaq6342@yahoo.com.cn

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

E-mail:wzd99117@163.com

網絡優先出版地址：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

文獻標志碼：A

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

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

收稿日期：2014-04-24；修回日期：2014-09-01；網絡優先出版日期：2014-10-30。