基于遗传算法的故障样本优化选取方法

邓　露, 许爱强, 吴忠德

(海军航空工程学院飞行器检测与应用研究所, 山东 烟台 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。