基于DPSO-AO*算法系统测试序列优化问题研究

王丽丽, 林 海2, 包 亮3, 万 贺

(1.北京交通大学 机械与电子控制工程学院，北京 100044；2.北京宇航系统工程研究所，北京 100076； 3.北京航天自动控制研究所，北京 100854)

科技发展所带来的电子系统的结构和功能越来越复杂，特别是在航空航天和军事等重要领域，对电子系统的测试效率和正确率要求非常严格。但是，普遍存在的测试手段是通过测试人员(受过专业培训)在经验的基础上分析、诊断；因测试人员的不同造成测试结果的不稳定性很高，并且受人本身能力的限制，测试效率也不高。为解决以上问题，系统首先需要解决测试序列优化的问题，目前国内外已经提出了一系列相关技术，主要分为三类，分别为：基于图论的方法、基于搜索的方法和其他方法[1]。针对实现测试策略生成的问题，目前已经有很多种方法,包括遗传算法、差分进化、量子遗传算法、BP神经网络、模拟退火算法，以及对于这些算法的融合算法[2-4]。

由于AO*算法在研究测试序列问题上应用的比较多,但是AO*算法在搜索最优路径的过程中需要对每个测试进行扩展，这对于复杂的信息系统而言，计算量太大[5-6]。为了改进该算法，采用离散粒子群算法，对每次需要扩展的测试集进行优化选择，然后AO*算法只对优化的结果进行扩展，这样的处理使得整个过程的计算量大大减少，搜寻最优路径的时间也大大缩短。

1 测试序列优化问题的数学模型

1.1 系统的多信号流图模型和相关矩阵

建立了复杂装备信息处理系统，在此基础之上，计算了该系统的故障测试相关矩阵，然后基于系统的相关矩阵进行测试优化选择问题研究[7]。建立的复杂装备信息处理系统的多信号流图模型如图1所示。

图1 复杂装备信息处理系统多信号流图模型

如图2给出了计算系统相关矩阵的方法，得到系统的故障-测试相关矩阵如表1所示。

图2 系统相关矩阵的计算流程图

CTt1t2t3t4t5t6t7t8t9t10t11C1(F)10000000000C2(F)01000000000C3(F)00100000000C4(F)00010000000C5(G)00001000000C6(G)00000100000C7(F)00000010000C8(F)00000001000C9(F)00000000100C10(F)00000000110C11(F)00000001001C12(G)01011111000

表1中行向量表示信息处流系统中可能发生的故障，C(F)表示功能故障模式，C(G)表示完全故障模式；列向量分别表示针对系统的故障源设计的测试。本文的目的就是对这些测试项进行优化选择，期望在系统发生故障时，以最少的测试项对系统故障进行检测和隔离，使产生的测试代价最小。

1.2 数学描述

p=[999640,28,7,31,27,8,9,127,31,26,29,27,10]T×10-6

四元组参数中T={t1,t2,…，tn}是n个可用测试组成的集合，已知n=11。c=[c1,c2,…,cn]T表示测试费用的向量[8]。

1.3 与或树搜索算法及解树的代价

与或树能将搜索路径清晰地展示出来，构造与或树的过程就相当于将问题一步一步分解，直到分解成不能再分解的子问题。这种方式会搜索所有的路径然后去判断每个路径的好坏，所以对于复杂的信息处理系统而言，这种方法代价会很高，不适合采取[9]。

本文将利用AO*算法，由于该系统相关的系统参数引导，使进行的每一步搜索均为最佳路径，避免了一次性搜索所有路径从而求得最佳路径,搜索效率明显高出很多。

① 如果xi是“或节点”，它的子节点有(xj1,xj2,…,xjx)，则xi的代价计算公式如下：

h(xi)=min{c(xi,xj)+h(xjx)}

(1)

在这里取子集的最小代价值，当搜索最优路径的时候，只需要代价值最小的节点。

② 如果xi是“与节点”，则xi的代价分为和代价法与最大代价法,如式(2)、式(3)所示。

(2)

h(xi)=max{c(xi,xjx)+h(xjx)}

(3)

由于本文中总代价等于每个故障源测试代价的总和，故采用式(2)带入计算。

③ 如果xi是决策树最低端的节点(已被隔离)，那么h(xi)=0。

④ 如果xi不可扩展，而且不是终端节点，则h(xi)=∞。

2 选择系统扩展节点

此处介绍系统初始节点的扩展原理，由前述数学模型中的S与p，得到系统在初始状态时的霍夫曼编码，系统初始状态的霍夫曼树如图3所示。

图3中，圆为系统的状态，圆下面标出的数字表示该状态的p值。由图3可计算出系统各状态的霍夫曼编码长度为w*=[5,7,5,5,7,7,2,5,5,5,5,7]，再由表1中相关矩阵，对系统初始节点S={s1,s2,…,s12}进行扩展，根据11个测试得11个解,树扩展结果图如图4所示。

图3 信息处理系统初始状态对应的霍夫曼树

图4 初始节点扩展图

图4中，G为通过测试的信息处理系统状态的集合；NG为没有通过测试的信息处理系统状态的集合[10]。

在初始故障状态集S={s1,s2,…,s12}中进行测试tj(1≤j≤11)后，容易知道d0j=0(j=1,2,…,11)[1]。

由式(1)可知其解树的代价估计值如下：

h*(xi)=min{cj+h*(x,tj)}

(4)

式中，cj为测试tj的代价;h*(x,tj)为应用子节点tj对x进行隔离的代价，由于x是tj的子节点，所以“与节点”(x,tj)的代价值是h*(x,tj)。因此根据式(2)可得：

h*(xi.tj)=p(xjp)h*(xjp)+p(xjf)h*(xjf)

(5)

式中，xjp为通过检测的故障子集；xjf为没有通过检测的故障子集，而且xjp∪xjf=x(j=1,2,…,n)。结合式(4)和式(5)可得任意状态集节点x的估价值如下[1]：

h*(x)=min{cj+p(xjp)h*(xjp)+p(xjf)h*(xjf)}

(6)

式中,h*(xjp)和h*(xjf)分别是节点xjp和xjf估价值的启发函数[11]。由式(6)可以看出，在全部的扩展子节点中，状态集节点的估价值是最小的。式(6)中，p(xjp)和p(xjf)分别由式(7)和式(8)计算：

(7)

(8)

基于霍夫曼编码理论的启发函数在与或图中的搜索效率效果良好[12]，由式(9)表示：

(9)

(10)

同理可计算出各节点xjp的启发函数值，如表2第3列所示。

由式(6)计算各测试项的估价函数值，例如测试项t1的h(s)为：h(s)=c1+h(x1p)p(x1p)+h(x1f)p(x1f)=1+4.06×0.000332+5×0.000028=1.001487，经过计算，各个测试的估价函数值见表2第4列，由于整数位都是1，所以该列仅列出了h(s)的小数点后6位。

表2 各节点计算结果一览表

根据表2中第4列的真实值，将个测试的估价函数值绘制成曲线图，如图5所示。

图5 各个测试的估价函数值曲线

由图5可知，最小估价函数值属于t6，所以搜索最佳路径时，t6就是搜索首节点。然后再分别扩展t6的两个子集，继续对最佳路径的节点进行搜索。

3 扩展测试集的优选

首先确定优化完成后测试集中测试项的数目。然后再确定N个群落中的粒子数。第i个粒子的速度值和位置为：vi=(vi1,vi2,…,viD)和xi=(xi1,xi2,…,xiD)，i=1,2,…,N。群落中粒子的速度更新[1]和位置更新如下。

(11)

(12)

式中，w为惯性权重；c1为粒子的自我认知程度；c2为粒子对整体的认知程度；ξ、η为区间[0,1]内的随机数；r为速度的约束参数[1]。

w值的大小决定粒子群算法的局部搜索能力；本文考虑到粒子的位置和速度优势与整个群体的优势，取w=1,c1=2,c2=2[1]。

以上是传统的做法，本文未使用式(12)，使用了离散粒子群算法算法，在该算法中，粒子的速度值介于[0,1]之间，在代码中借助式(13)实现[0,1]的值域值：

s(v)=(1+ev)-1

(13)

式(13)是每个粒子的速度更新公式，粒子的位置更新见式(14)。

(14)

式中，rand为[0,1]区间的随机数。

基于以上所述，本文设计了测试项评价函数见式(15)，可根据式(15)对测试项相对于各测试发生概率的重要性做出评估[1]。

(15)

式中，p(ti)为系统所有可能发生故障的平均概率；N(ti)为ti能够检测到的故障数；S(ti)为系统所有故障中故障的最小可测度；a为调节值，本文中取a=1。通过表1得到测试项的评价函数值如表2第5列、第6列、第7列、第8列所示。

由表2第5～8列数据，可以看到任意一个测试项的重要性。为评估测试集的优劣，给出式(16)：

(16)

式中，Ts为随机选择的测试集；T为信息处理系统所有的测试项；N为Ts的数目；ηFD为系统的故障检测率；ηFI为系统的故障隔离率；ci为测试ti的费用；h(ti)为测试ti的评价函数值[13]。

结合本文研究的测试序列优化问题将离散粒子群算法的粒子定义为一个二进制向量xi=(xi1,xi2,…,xiN)[1]，计算粒子在位置的速度值，位置更新按式(14)计算。

4 实验验证

本文通过编写C++代码，多次运行算法程序，识别状态集s6p的测试集，多次运行算法的结果如图6所示。

图6 离散粒子群算法运行结果

算法运行结果中，位置若为1，则表示选中对应的测试，若为0，则表示未选中对应的测试。由图6得，{t1,t3,t5,t7}为算法最后优选出的测试集。

接下来对t1,t3,t5,t7扩展即可，不需要对其他10个测试操作，从计算量来说，明显缩减。

表2第9列、第10列中，h(s6p,tj)为测试tj对s6p的估价值，δ为新的估价值与原来估价值的差值。图7绘制了优选测试的估价函数值曲线。

图7 优选测试的估价函数值曲线

由表2第9列和图7得：最小的评估函数值是t1，所以t1就可以被当做隔离出来最好的子集。类似地，扩展s6f={t6,t12}，并用DPSO算法优选出将要扩展的系统测试项集合{t2,t4,t5,t7}(备选测试集不包括t1)，其中t1为测试代价最优。接着扩展t1的一个子集s1p={s2,s3,s4,s5,s7,s8,s9,s10,s11}，结果如图8所示。

图8 离散粒子群算法运行结果

由图8得：{t5,t7,t8}为优选出的测试集，估价函数值最小的是t5。然后对s1f进行扩展，用DPSO算法选择s1f将要扩展的系统测试项集合，得到信息处理系统最优测试策略决策树如图9所示。

图9 信息处理系统最优测试策略决策树

基于以上整个过程，本文显著减少了计算量，同时基于DPSO算法本身具有独有的优势，系统每一次进行的优化选择都是全局最优。

5 结论

由图9可得：该复杂信息处理系统所有的故障都能被独立隔离。按照图9对故障进行定位，可使故障源迅速确定，同时保证理论上总的测试代价最小。

当系统同一时间只发生了一个故障，可由图9中的测试顺序，利用一次测试即可将故障源定位。若多个故障同时发生，或存在隐藏故障时，也可利用图9进行故障定位，只需进行多次测试，将故障一一定位。