基于混合离散二进制粒子群-遗传算法的测试配置方法研究

，，

(海军航空大学 岸防兵学院，山东 烟台 264001)

0 引言

测试性建模是对系统中故障-测试信息与功能信息流向的一种图示或数学描述，选择一种好的测试性模型是进行测试性分析与设计的前提[1]。一个好的测试性模型应既能够体现系统的物理结构组成和功能信息流向,又可以描述系统故障与测试之间的逻辑关系和对测试资源的占用关系等。为了提高系统的测试性指标，建模人员在建立系统测试性模型时通常会设置大量的测试。目前系统的测试配置工作基本上都由建模人员凭借经验完成，由于大型复杂系统的故障模式数量极多，若为每个故障模式都设置测试，对此测试性模型进行分析必然会使系统的测试性指标如：故障检测率(fault detection rate，FDR)和故障隔离率(fault isolation rate，FIR)等达到最高[2]。但复杂的测试性模型增加了整个测试性分析工作的难度，过多的冗余测试大幅降低了整个系统的诊断效率，根据此模型对系统进行设计和开发也会产生一系列问题，如：增加系统的设计难度、增加全寿命周期费用、提高研发成本等。因此有必要解决测试性建模过程中测试的优化配置问题，简化测试性模型，以最简约有效的方案最大程度地检测并隔离系统中的故障。

基于以上问题，本文提出了一种混合离散二进制粒子群-遗传算法(binary particle swarm optimization-genetic algorithm，BPSO-GA)对复杂系统测试性建模过程中测试优化配置问题进行求解。

1 测试优化配置的数学描述与建模

1.1 故障可达性矩阵

测试性建模工作主要是面对系统的故障空间，然后为故障配置相应的测试。目的是建立系统内部各个功能单元之间的故障传播关系和故障与测试资源的逻辑关系[3]。根据系统的组成结构和故障模式、影响及危害性分析(failure mode, effects and criticality analysis，FMECA)可知，系统内部的故障模式存在着一定的传播关系，故障模式之间的这种传播关系可以用故障可达性矩阵表示。假设系统故障流图G=中包含n个故障模式节点:FM={fm1,fm2,…,fmn}；m条边:E={|fmi∈FM,fmj∈FM}。有序对表示故障模式节点fmi到fmj有一条有向边，则定义n阶方阵f(G)=[fij]为系统的故障邻接矩阵，其中：

(1)

定义故障可达性矩阵F(G)如下：若故障模式fmi可以引起故障模式fmj发生，即从fmi到fmj存在一条通路，则n阶方阵F(G)=[Fij]称为系统的故障可达性矩阵，其中：

(2)

下面给出由故障邻接矩阵求取故障可达性矩阵的一般方法[4]：

1)对故障邻接矩阵f(G)进行如下变换：

(3)

式中,R是表示任意两故障模式之间通路数目的矩阵。

2)将矩阵R中的全部非零元素置换为1，为零的元素保持不变，就得到故障可达性矩阵，其中：

(4)

1.2 测试配置方案

系统测试配置方案可用n维向量表示：

VT=[v1,v2,…vn]

(5)

其中:vi=1表示为故障模式fmi配置测试；vi=0表示不为故障模式fmi配置测试。将VT中vi=1的个数记为m，表示为系统配置测试的总数量。其中：系统最优测试配置方案应为最小完备测试集合，即去除该集合中任意一个测试就不再满足测试性参数指标要求。

1.3 故障-测试相关性矩阵

测试性模型具有图示形式和矩阵形式两种表示方法,故障-测试相关性矩阵以测试性图示模型为基础进行相关性分析得到, 故障-测试相关性矩阵便是对系统功能单元故障与测试资源相关性的数学描述。根据测试配置方案VT为系统配置测试，构建故障与测试资源的逻辑关系，故障-测试相关性矩阵Dn×m可由下式计算得到：

(6)

在建模过程中，通常为系统作下列假设：(1)被测对象仅有两种状态：正常状态和故障状态。被测对象在正常状态下无故障可以正常工作；反之被测对象不能正常工作。(2)当被测对象处于故障状态时，则假设仅有一个组成元件(或部件)发生了故障。(3)某一组成单元发生了故障，在信息流动方向可达的各个测试点上，测量的有效性是一样的。(4)每个测试的测试结果都是二值且可靠的，各测试之间相互独立。则故障-测试相关性矩阵内的元素：若故障模式fmi与测试tj相关，则dij=1，否则dij=0。

1.4 测试性参数指标

1.4.1 故障检测率

故障检测率描述了系统对故障模式的检测能力[5]，可根据故障-测试相关性矩阵计算得到：

(7)

式中,LD为矩阵Dn×m中非全零行向量个数。若考虑各故障模式的故障率λ，此时故障检测率的计算公式为：

(8)

1.4.2 故障隔离率

故障隔离率描述了系统对故障模式的隔离和诊断能力，可根据故障-测试相关性矩阵计算得到：

(9)

式中,LI为矩阵Dn×m中非全零且唯一的行向量的个数。若考虑各故障模式的故障率λ，此时故障隔离率的计算公式为：

(10)

1.5 优化模型

1.5.1 优化对象和目标

优化对象即对系统配置测试的方案，因此，优化对象模型可以用式(5)形式表示。测试最优配置方案需满足以下目标：在使系统达到规定的测试性指标参数的情况下，模型中测试数量最少。因此，优化目标函数可表示为：

minm

(11)

1.5.2 优化约束条件

在本文中，优化目标规定系统需要达到规定的测试性指标这一前提。因此，优化约束条件可表示为：

(12)

式中,系统要求达到的测试性指标分别记作FDR、FIR，在建模时若有充足的先验信息，在计算γFD、γFI时可以考虑故障率等因素，使模型更接近实际。

2 基于混合离散二进制粒子群-遗传算法的测试优化配置方法

2.1 遗传算法基本理论

20世纪60年代，Holland受生物进化机制启发，提出了一种模拟自然界生物遗传进化的自适应概率搜索算法，称为遗传算法(Genetic Algorithm，GA)[6-8]。遗传算法将进化理论中“适者生存”这一基本思想引入串结构当中，并且在串之间进行有规则的随机信息交换。随着算法的不断运行，好的品质被保留下来并加以结合，以此来繁衍出更佳的个体。新一代个体中不但包含着上一代个体的大量信息，而且由于好的特征被不断地继承下来，在总体特征上也不断胜过旧的一代，从而使整个种群向前进化发展。遗传算法的基本概念包括：

种群(Population)：是指遗传算法求解过程中，在解空间中的一个子集，即初始情况下多个解的集合。遗传算法从该初始种群开始计算求解。

个体(Individual)：是指某个解集合中的单个解，一个个体由某种数据结构描述其基本特征信息。本文中的个体即用二进制编码来表示一个测试配置方案。

适应度函数(Fitness)：是遗传算法实现优胜劣汰的主要依据，其作用是计算种群中每个个体的环境适应度并进行评估，它决定了染色体的优劣程度。

染色体(Chromosome)：是将个体进行编码后得到的编码串，也可称为基因型个体，编码串中的单个元素称为一个基因。

遗传操作(Genetic Operator)：遗传操作包括选择、交叉、变异3种基本形式，是一种从原始种群产生新种群的操作。

GA包含以下要素：

GA=(P(0),N,l,s,Qr,Qc,Qm,Pr,Pc,Pm,f)

(13)

式中,P(0)为初始种群；N为种群规模；l为染色体长度；s为对个体的选择策略；Qr为选择算子；Qc为交叉算子；Qm为变异算子；Pr为选择概率；Pc为交叉概率；Pm为变异概率；f为适应度函数。

2.2 离散二进制粒子群算法基本理论

Eberhart博士和Kennedy博士于1995年提出了粒子群优化算法(Particle Swarm Optimization，PSO)[9-11]。为解决实际问题，二人于1997年又提出了离散二进制粒子群优化算法(Binary Particle SwarmOptimization，BPSO)[12-13]。粒子群算法仅根据粒子的速度进行搜索，没有遗传算法复杂的选择、交叉和变异操作，结构简单，运行速度较快并且拥有记忆功能，但粒子仅仅将当前搜索到的最优位置作为共享信息，容易陷入局部最小，从而出现所谓的“早熟收敛”现象。

粒子群中任意一个粒子的信息都可以用如下信息来描述：①粒子的当前位置Xi=(xi1,xi2,…,xin)；②粒子搜索到的当前最优解Pi=(pi1,pi2,…,pin)，记作Pbest，称为个体极值；③粒子在搜索空间中的飞行速度Vi=(vi1,vi2,…vin)，这里i=1,2,…n。若粒子i的当前位置优于其历史最优位置，则将粒子i的当前位置更新作为历史最优位置。vij和xij的更新公式为：

vij=w·vij+c1·rand1()·(pij-xij)+

c2·rand1()·(pgj-xgj)

(14)

xij=xij+vij

(15)

式中,w为惯性权重；c1，c2为粒子群学习因子；rand1，rand2是两个随机分布在(0，1)之间的正实数。整个粒子群也存在一个历史最优位置Pg=(Pg1,Pg2,…,Pgn)，记作Gbest，即粒子群搜索到的最优解，称为全局极值。

对于BPSO中的任一粒子，其每一维的xij和Pbestij都用0或者1表示，而vij则变为粒子位置取1的概率，速度越快则粒子位置取1的概率越高。由于神经网络中的Sigmoid函数具有相似的特点，所以一般用该函数将粒子速度映射到区间[0,1]内：

(16)

则粒子位置更新公式可表示为：

(17)

2.3 混合离散二进制粒子群-遗传算法

由于GA存在搜索速度慢，没有种群的移动，不能参考历史信息等缺点[14]。为解决系统的测试优化配置问题，本文将二进制粒子群算法与遗传算法相结合，提出一种BPSO-GA算法。该算法将遗传算法和离散二进制粒子群算法相结合，通过综合两种算法的优点，使新算法既能保证较快的搜索速度和成功率，又可以拥有良好的信息共享机制，避免陷入局部最优。

BPSO-GA的流程如图1所示。

图1 BPSO-GA流程图

BPSO-GA的总体思路是:首先对每一代种群分别计算其中个体对应的适应度函数，并进行遗传操作。在经过规定代数的迭代后再进行粒子群操作产生新种群，将种群中达到指标要求的个体在数据库中进行存储。最后对数据库中个体进行比较，将数据库中测试数量最少的个体输出为最优个体。下面介绍基于BPSO-GA的测试配置问题求解的几个关键步骤：

1)粒子编码：将第k个粒子的二进制编码设置为VTk=[v1k,v2k,…vnk]，此时种群中每一个粒子都对应一种测试的配置方案；

2)为防止Sigmoid函数饱和使算法早熟，本文将粒子最大速度设置为2，此时的Sigmoid函数为：

(18)

3)构造适应度函数：首先计算种群中个体的测试性指标γFD和γFI。由于个体的适应度主要由3个参数决定：测试配置数量m、系统故障检测率γFD、系统故障检测率γFI。由于测试数量m越少，测试性指标γFD、γFI越大，个体的适应度越大。因此，本文将适应度函数设置为：

(19)

φ为权值系数。

3 实例验证

对某装备涡扇发动机的传动供电系统建立测试性模型，系统功能框图如图2所示。该系统有25个故障模式，根据系统功能框图和先验故障传播关系，建立系统的故障邻接矩阵f(G)，如表1所示。

表1 传动供电系统故障邻接矩阵

根据公式(3)，(4)可计算得到系统故障可达性矩阵F(G)，限于文章篇幅，此处不再赘述。得到故障可达性矩阵后为混合算法设置初始参数：Nmax=100，Popsize=20，Pc=0.8，Pm=0.1，c1=c2=2，w=0.9，vmax=1，φ=1。

仿真算例(一)：考虑为所有故障模式都设置测试的情况，仿真结果如表2所示。

表2 测试配置仿真结果(一)

由表2可知，在所有故障模式均可测的情况下系统的故障检测率γFD和故障隔离率γFI都为100%。但在实际中由于接口设计、物理结构、成本等问题无法为所有的故障模式都设置测试点，此时的测试性模型的测试性指标虽然都为100%，却无法落实到系统研发设计当中。

图2 传动供电系统功能框图

仿真算例(二)：计算FDR=0.8，FIR=0.6时的优化仿真结果，如表3所示。

表3 测试优化配置仿真结果(二)

上述结果表明，当系统对故障检测率和隔离率的要求为FDR≥0.8，FIR≥0.6时。表3中列出了BPSO-GA得出的最优解，以及它们不能够检测到的故障模式和不能够隔离的故障模式。由该测试配置方案可得最少要设置m=13个测试才能满足该指标。

仿真算例(三)：计算FDR=0.95，FIR=0.9时的优化仿真结果，如表4所示。

表4 测试优化配置仿真结果(三)

无仿真算例(三)中所提测试性指标基本可以达到武器装备的测试性指标要求。由表4可知至少需要为模型设置m=20个测试才能满足所提测试性指标要求；至少需要m=21个测试才可以完全检测和隔离所有故障模式，这比仿真算例(一)中满测试配置方案减少使用了4个测试，效率提高了16%，若考虑测试接口设计和测试费用，该测试配置方案可以大大降低实际系统的设计难度和全寿命周期费用。

4 结论

本文针对目前测试性建模工作中尚无具体方法指导测试配置这一问题，以系统故障空间为基础，建立了系统的故障传播模型。然后以测试性分析的指标为约束，以测试数量为优化目标，提出了一种基于混合离散二进制粒子群-遗传算法的测试优化配置方法，并应用在某型装备涡扇发动机的传动供电系统中。通过考虑不同的测试性指标要求，得到了不同情况下的最优测试配置方案及对应的测试性指标和无法检测、隔离的故障模式。由测试配置仿真结果可知，该算法可以在满足系统测试性指标要求下给出系统的最优测试配置方案，有效地解决了系统测试性分析与设计方面的问题，能够提高测试性分析与设计效率，降低系统的设计难度，对于指导复杂系统的测试性建模工作具有实际应用价值。