用于测试序列优化的DPSO-WAO*算法研究

汪芊芊，林 臻，苏 晗，王海涛，蓝 鲲

(北京宇航系统工程研究所，北京 100076)

0 引言

由于测试项目对系统资源的占用，在对系统进行测试的过程中，所有的测试并不能同时进行，需对测试进行排序，而不同的测试执行顺序对于系统的测试效果和测试成本均会产生较大影响[1-3]。因此，在执行测试前，需要对测试序列进行优化设计，使其尽可能早并精确地隔离故障，同时降低测试代价(包括费用、故障隔离时间等综合评价因素)，这正是测试策序列优化设计问题。

针对该问题，国内外学者提出了优化算法。常用的方法有动态规划(DP)算法[4-6]和启发式算法[7-13]。动态规划是自底向上构造测试树，具有指数级的计算量，无法应用于复杂设备的测试序列优化；启发式算法是利用启发式评估函数对测试成本进行评估，以评估结果进行测试点筛选的一类贪婪搜索算法，目前应用最为广泛的是由Krishna R.Pattipati以及其团队提出的AO*(AND/OR*)算法[12]。但传统AO*算法由于需要通过测试成本回溯实现全局最优，导致节点扩展量巨大，当测试个数增加时，易导致计算量爆炸。为此，国内外学者提出了众多改进方法，主要从两方面考虑：(1)减少传统AO*算法的扩展节点[14]；(2)结合现代优化算法降低计算复杂度[15-20]。以上方法一定程度上降低了传统AO*算法的计算复杂度，但未从全局的角度考虑各个测试项目的代价和故障概率对于测试选择的影响，导致算法的优化性能下降，难以达到最佳优化效果。

针对传统AO*算法计算量大，而现有对于AO*算法的改进无法同时满足计算效率和优化性能的问题，本文从启发式评估函数的改进出发，设计了基于加权Huffman编码的启发式评估函数，对基于离散粒子群的AO*算法(DPSO-AO*)进行改进，提出了DPSO-WAO*(DPSO-Weight_AO*)算法。实例证明，基于加权Huffman编码的启发式评估函数较传统AO*算法使用的启发式评估函数更为准确地评估了全局测试成本，在取消了成本回溯的情况下，算法计算复杂度与DPSO-AO*算法相当，但算法寻优性能较DPSO-AO*算法得到了较大提升，很好地解决了传统AO*算法存在的计算效率和优化性能的矛盾，适用于大型复杂对象的测试序列设计。

1 测试序列优化问题分析与建模

对于被测系统来说，其系统状态和测试信息可以定义为五元组(S，p，T，c，D)，式中：

S={s1，s2，…，sm}是系统故障状态集合，si(1≤i≤m)表示系统不同的故障状态，也即故障模式；

p=[p(s1)，p(s2)，…，p(sm)]T是系统各故障状态S的故障率集合；

T={t1，t2，…，tn}是系统可选的测试集合；

c=[c1，c2，…，cn]T是各可行测试的测试成本集合，可以测试时长、人力成本或其它指标评价。

Dm×n是测试与系统状态的相关性矩阵。其基本形式为：

(1)

di，j表示故障fi与测试tj之间的相关性，若di，j=1，则表示测试tj可以检测到故障状态fi，若di，j=0，则表示测试tj无法检测到故障状态fi。

假定同一时刻只有一个故障状态si发生，且每次只施加一个测试项目，则测试序列优化就是设计一个方法，能够通过合理安排测试项目的实施顺序，来识别系统故障状态集中的故障模式，且使期望的测试成本最小，测试成本通过如下公式评估：

(2)

式(2)中A(m+1)×n=[aij]是一个二值矩阵，如果在识别系统状态si的过程中采用了测试tj，则aij=1；否则aij=0。如何能在满足系统故障隔离率和故障检测率要求的前提下，使式(2)中测试成本最小，是本文的研究目标。

2 现有AO*算法及DPSO-AO*算法

AO*算法通过构建与或图采用top-down的搜索方法进行故障隔离，如图1所示。或节点对应故障集节点X；与节点对应可用测试节点tj，其各子节点分别代表tj应用于故障状态集节点X后根据其测试结果和相关矩阵所得的通过故障子集Xjp和失败故障子集Xjf。

AO*算法是两个运算阶段的反复：

1)自上而下进行节点扩展。从初始模拟故障集开始，评估所有可选测试用于隔离模糊故障集的测试代价，并选取代价最小的测试进行与或树扩展，直至所有故障集节点均为单节点，则解树生成，实现故障隔离的目的。

2)自下而上进行成本回溯。在与或树扩展过程中，单纯根据局部极值进行节点扩展，可能陷入局部最优，因此，需要在每一次节点扩展后自下而上进行成本回溯，计算初始模拟故障集的测试成本，并与该次扩展前的成本评估值比较，若相等，则继续扩展，否则，选取启发式函数值次小的测试进行该节点的扩展，直至回溯成本与扩展前成本相同(若各可用测试所达到的成本回溯值均大于扩展前的评估值，则选取回溯成本最小的测试进行与或树扩展)。

AO*算法利用Huffman编码构造启发式评估函数。假设测试费用满足：0≤c1≤…≤cn，构造评估隔离故障集X的最小平均测试代价启发式函数如式(3)所示：

(3)

若故障集X被测试tj区分为两个故障子集Xjp和Xjf(Xjp∪Xjf=X)，其中Xjp表示测试tj无法检测到的故障子集，Xjf表示测试tj可以检测到的故障子集。利用测试点tj隔离故障集X的最小测试代价近似估计为：

hx=cj+p(xjp)×h(xjp)+p(xjf)×h(xjf)

(4)

其中：h(xjp)和h(xjf)分别表示估计隔离故障集Xjp和Xjf的最小测试代价，利用HEF(X)估计；p(xjp)和p(xjf)分别表示测试tj通过和失败的相对概率。传统AO*算法利用式(4)中hx的值评价测试点tj，选取hx最小的tj向下扩展。并在每次向下扩展之后将测试成本向上回溯，以确保当前所扩展测试的全局最优性。

传统AO*算法通过不断回溯以寻得最优测试序列，对于运载火箭电气系统、电气设备这样规模庞大的优化对象，由于涉及的测试项目、故障模式均较多，因此所需运算时间急剧增加，很容易出现计算爆炸问题。为解决传统AO*算法回溯次数多，计算量大的问题，文献[18]将离散粒子群算法(DPSO)与AO*算法相结合，对AO*算法的可扩展节点进行筛选，并取消了成本回溯，大大减少了AO*算法的计算复杂度。

DPSO-AO*算法的基本思想是[18，20]：利用DPSO算法优选AO*算法中每个待扩展节点的测试集，进而减少待扩展测试的个数，并取消成本回溯，降低算法计算复杂度。DPSO-AO*算法采用式(5)所示的适应度函数对备选测试集T进行优化：

(5)

其中：Ts代表所选的最优测试集，N代表测试集Ts中测试项目的个数，ηFD、ηFI分别代表Ts的故障检测率和故障隔离率；ci、cj分别代表测试ti、tj的测试代价；h(ti)代表测试集T的单个测试ti的优劣程度，如式(6)所示：

(6)

式(6)中，P(ti)代表测试ti能检测到的故障可能发生的总概率；S(ti)代表ti所能检测到的故障的最小可测度，a为其系数，需根据实际优化结果进行调整。

3 基于改进评估函数的DPSO-WAO*算法

3.1 基于加权Huffman编码的启发式评估函数

传统AO*算法依据评估函数选择最优测试，实现故障树的向下扩展，并结合向上回溯来保证测试选择的正确性，其优化性能主要取决于以下两点。

1)启发式评估函数对于故障集的测试代价描述的准确性：

启发式评估函数越接近真实的最小测试代价，则对于测试的选择越准确，越接近全局最优。

2)回溯步数：

回溯的目的是检验当前所选测试的全局最优性，向上回溯步数越多，则越接近全局最优，若每一次测试选择都向顶端节点回溯，则所生成的测试序列一定为全局最优。

传统AO*算法利用向顶端节点回溯来确保算法的全局优化性能，但回溯步数过多会导致扩展节点数目增多，因此计算量巨大，不适用于大规模系统的测试序列优化。DPSO-AO*算法结合离散粒子群算法对传统AO*算法进行改进，通过DPSO算法对扩展测试集进行优选，并取消成本回溯来减少节点扩展数目，降低计算复杂度。DPSO-AO*算法所用的启发式函数(3)主要通过故障集中各个故障状态的平均Huffman编码来确定所需测试数量，并按照测试成本由低到高的原则选取测试项目用于计算总测试成本。

在理论编码中，Huffman树(最优二叉树)具有带权路径长度最小(即成本最小)的特点，因此，可用于近似估计测试集的最小测试成本。但该方法忽略了每个故障状态的Huffman编码信息，而是求取各故障状态的平均Huffman编码用于评估最小测试代价。事实上，Huffman编码越短的故障，对应故障率越高，越应该被提前隔离，而仅通过平均Huffman编码，无法体现该原则。因此，本文在DPSO-AO*算法的基础上，从启发式评估函数的改进这一角度出发，构建了基于加权Huffman编码的启发式函数，对DPSO-AO*算法进行改进。加权Huffman编码的启发式函数基本思想如下：

隔离系统各状态的测试总代价是通过将隔离各个状态的测试代价相叠加而得的，而各个状态的测试代价为隔离该状态所需的测试代价与该故障状态的故障率的乘积。因此，在对某个模糊状态集的测试代价进行评估时，分别考虑模糊集中的各个状态，利用故障率作为故障模式Huffman编码的权重，提出如下基于加权Huffman编码的启发式函数：

(7)

其中：测试费用满足0≤c1≤…≤cn，ω(si)表示故障模糊集X中si的Huffman编码长度。

1)优先隔离故障率高的故障；

2)优先选择测试成本低的测试。

由测试成本定义式(2)可知，该值即为测试成本的下限值。

基于加权Huffman编码的启发式函数与传统的启发式函数的差别在于：传统AO*算法利用模糊故障集的平均Huffman编码来表征隔离故障集的平均最少测试步骤，而丢失了故障集中的隔离各个故障所需的最少测试步骤这一信息，未体现优先隔离故障率高的故障的这一原则。而基于加权Huffman编码的启发式函数构建了满足最优测试序列优化原则的诊断树，并准确计算了该最优诊断树的测试代价。因此，利用基于加权Huffman编码的启发式函数评估测试代价更为准确。

3.2 DPSO-WAO*算法实施步骤

基于DPSO-WAO*算法的测试序列优化方法与传统AO*算法基本相同，但由于启发式函数的准确性更高，因此取消了向上回溯这一步骤，流程如图2所示。

图2 基于DPSO-WAO*算法的测试序列优化流程

具体流程如下：

1)建立一个仅由根节点(系统故障状态集)构成的有向图。

2)对于模糊故障集 (初始值为系统故障状态集)，利用DPSO算法对当前可用测试集进行优选；利用评估函数评估采用各优选出的测试隔离当前模糊故障集的测试代价，并选出测试代价最低的测试扩展有向图，直到中仅含有一个元素。具体步骤如下：

①利用DPSO算法对当前可用测试集进行筛选，获得优化的测试子集；

②在测试子集中，每个测试将模糊故障集(模糊故障集的初始值为)分为左右两个子集和，由式(7)估计两个子集的最优隔离代价，由式(4)计算利用测试隔离模糊故障集的最小代价；

③找出测试子集中隔离模糊故障集所用代价最小的测试，利用该测试扩展有向图，获得左右两个子集；

④分别以故障子集作为模糊故障集，重复2)进行有向图的扩展，直至为单元素集合，此时，系统故障状态集中各个状态均能被区分。

4 实例校验及算法对比

4.1 实例校验

为验证DPSO-WAO*算法的有效性，在matlab平台上实现了DPSO-WAO*算法，并利用该算法对文献[18]中的超外差接收器系统进行测试序列优化工作，与文献[18]提出的DPSO-AO*算法进行比对。

文献[18]所给出的超外差接收器系统包括22个不同的系统状态，各状态发生概率不等；包括36种测试，各测试的成本相同，均设为1。

然而，在实际测试条件下，各个测试的成本并不完全相同，由测试难易程度、测试时间、测试人力成本、资金成本等影响因素决定，对最终的系统测试总成本产生较大的影响。因此，本文对文献[18]中给出的超外差接收器系统的36个测试项目赋予测试成本属性，形成超外差接收器测试成本集合cjsq，如式(8)所示，测试成本从2到67不等，数值越高代表测试成本越高。

cjsq=[10，25，2，7，10，10，30，29，30，50，50，

20，4，5，67，34，30，50，50，20，4，20，4，5，67，

20，4，5，67，29，30，50，50，45，5，67]T

(8)

假设该系统同一时刻只有一个故障发生，且同一时刻只进行一种测试。对于测试成本相同及测试成本不同的情况，在matlab平台上分别利用传统AO*算法、DPSO-AO*算法、DPSO-WAO*算法对式(8)描述的系统进行测试序列优化。其中，DPSO的粒子数目取15，迭代次数取100时，优化性能较好。通过3种不同优化算法形成的优化结果如表1及图3、图4所示，表1中的数据为对应算法连续运行10次所得结果的平均值或标准差。

表1 各算法性能参数比较

图3 测试序列优化算法性能比对(测试成本相同)

图4 测试序列优化算法性能比对(测试成本不同)

分别比较了测试成本相同(均为1)和测试成本不同(各项目的测试成本设置参见式(8))两种工况下，3种算法寻得的最小平均测试代价、测试代价标准差、平均允许运行时间及平均扩展节点数目。其中：

1)平均最小测试代价。代表算法优化性能，该数值越小，则代表算法优化得出的测试代价越小，优化性能越好。

2)测试代价标准差。代表算法寻优性能的稳定性，该数值越小，代表各次优化结果一致性好，算法运行稳定可靠。

3)平均运行时间。代表算法计算效率，该数值越小，代表算法运行时间越少，计算效率越高。

4)平均扩展节点数目。代表算法计算复杂度，该数值越小，代表算法遍历次数越少，算法复杂度越低。

从表1结果可以看出，DPSO-WAO*算法可有效寻得最小测试代价，算法性能稳定，运算效率较高。

注:算法各性能参数均以连续运行10次所得结果取平均值。

4.2 算法比对

上文通过超外差接收器系统对DPSO-WAO*算法有效性进行了实例验证，并与传统AO*算法、文献[18]提出的DPSO-AO*算法进行了性能比对，如表1及图3、图4所示，得到结论如下。

1)寻优性能：

DPSO-WAO*算法的优化性能稍差于传统AO*算法，但二者优化生成的测试序列的测试代价相差不超过3.9%，主要是由于传统AO*算法通过不断向上回溯找到全局最优解，而DPSO-WAO*算法无回溯，得到的是近似全局最优解，此结果与预期一致。

DPSO-WAO*算法与DPSO-AO*算法相比，生成的最小测试代价分别降低11.9%(测试代价相同)和10.1%(测试成本不同)，寻优性能得到较大提升。由此证明，DPSO-WAO*算法同DPSO-AO*算法一样，均取消了传统AO*算法的回溯，但由于基于加权Huffman编码的启发式函数能更好的评估模糊故障集的隔离代价，使当前测试节点的扩展路径更接近全局最优，因此，DPSO-WAO*算法优化性能较DPSO-AO*算法可提升10%以上。

2)计算效率和复杂度：

DPSO-WAO*算法的平均运行时间与DPSO-AO*算法的平均运行时间相当，且均远小于传统AO*算法，仅为传统算法所需时间的约15%，其扩展节点数目也约为传统AO*算法的15%。可以证明，DPSO-WAO*算法在进行测试节点扩展前利用DPSO对当前可用测试集进行优选，避免陷入局部最优，并大大减少了扩展节点的数目，提高了算法的计算效率，且越复杂的系统，采用DPSO-WAO*算法获得的计算效率提升效果也越明显。

5 测试序列优化方法在运载火箭电子设备中的应用模式思考

运载火箭电气系统组成复杂，故障模式在数量和种类上呈现多样性，需采取较多测试才能实现故障检测及隔离需求，如果不对测试进行统筹规划，将会耗费大量的时间和成本代价。现阶段运载火箭电子设备的测试包括单机测试、系统综合测试、全箭电气测试等多个环节，各测试环节主要关注测试覆盖性，及测试项目的设置需尽可能覆盖产品的功能、性能、冗余设计和对外接口等，测试项目的设置和排序主要依赖测试人员经验，未考虑测试对故障的隔离定位能力、测试成本等影响因素。

随着新型火箭的研制，传统火箭测试设计思路已很难适应新型火箭的测试需求，尤其是随着智慧火箭、可回收火箭等新概念的提出，传统依靠人工经验通过断插头、串转接盒等测试、排故模式已经无法适应火箭的测试排故需求，新型火箭的测试项目和测试序列的设计逐步向如下趋势发展：

1)从地面ATE测试、人工测试模式转向箭上BIT测试模式；

2)测试项目的选择和排序从依据人员经验和定性原则转向依据定量优化方法。

对于运载火箭来说，测试序列优化设计可实现在常规测试或排故时，对测试项目进行优选并形成最优测试序列，达到快速、自动地识别故障并将故障隔离定位到设定的故障隔离层次，如功能电路层、板卡层、单机层的目的。新研火箭电气系统设计可以在地面测试设备中嵌入测试序列优化设计功能，实现从测试序列自动生成、到故障诊断模型生成、到测试程序集生成、到测试设备测试操作、最后到故障诊断报告生成的自动测试排故流程，辅助测试人员开展自动故障排查，减少当前凭经验排故带来的故障定位困难及大量的人力、时间成本，提高排故效率和自动化程度，适应新型火箭的快速测试发射和排故需求。

6 结束语

通过对算法各性能参数的分析可以发现，基于加权Huffman编码的启发式评估函数能够更准确地评估隔离模糊故障集的测试代价，使当前测试节点的扩展路径更接近全局最优，对于测试成本不同时的测试序列优化具有更为明显的效果。因此，DPSO-WAO*算法虽然取消了传统AO*算法的回溯，但仍然取得了很好的优化效果，并且大大降低了计算复杂度，同时较DPAO-AO*算法实现了寻优性能的提升，可应用于运载火箭、武器装备等大型复杂系统的测试序列设计、故障诊断及定位中，具有重要意义。