基于准深度算法的多值测试诊断策略优化方法

马 羚，吕晓峰，曲晓燕，叶 文

（海军航空大学，山东 烟台 264001）

0 引言

诊断策略优化设计作为测试性工作中的重要组成部分，其主要目的是在满足系统测试性指标约束条件下，设计一组期望测试成本尽可能低的测试序列［1］。现有的诊断策略优化算法，如信息熵算法、贪婪算法、AO*算法、Rollout算法等以故障-测试相关性矩阵为基础优化设计诊断策略，相关性矩阵中的测试输出假设为布尔值，只能表示通过和不通过两种状态［2-5］。然而这种输出为布尔值的二值测试，描述的系统状态信息非常有限。实际上，在工程实践中，系统的状态信息有多种，测试输出存在多值。相比二值测试，多值测试能够获取系统更多的状态信息，可有效提高系统的诊断效率和精度，降低诊断时间和成本。文献［6-7］根据信息熵理论和多值逻辑推理，设计了基于信息熵算法的多值测试诊断策略优化方法。但是此算法容易陷入局部搜索，求得局部最优解。文献［8］提出了基于人工智能的搜索剪枝技术的多值测试诊断策略优化方法，但该方法只能适用于小系统的诊断策略优化设计。文献［9-10］将Rollout算法与信息熵算法相结合，设计了基于Rollout算法的多值测试诊断策略优化方法。该方法不能确保获取全局最优解，但是该方法搜索的结果优于信息熵算法搜索的结果。

信息熵算法是一种常用的启发式搜索算法。准深度算法是一种用于组合优化问题的计算方法。杨鹏首次将准深度算法应用于二值测试诊断策略优化问题［1］。本文根据准深度算法可改善信息熵算法的特点，用准深度算法对基于信息熵的多值测试诊断策略进行优化，提出一种新的多值测试诊断策略优化方法。首先对基于多值测试的故障-测试相关性矩阵和多值测试诊断策略优化问题进行了描述；然后针对该问题，设计了准深度算法；最后通过案例对准深度算法进行了仿真验证。

1 问题的描述

假设系统存在m个故障状态并设置了n个测试，则多值测试诊断策略优化问题描述如下［11-13］：

表1 故障-测试相关性矩阵

多值测试诊断策略是通过特定算法，基于相关性矩阵选取一组测试，使矩阵中每个故障状态都能被检测和隔离，而且尽可能降低期望测试代价，期望测试代价的计算公式如下［11］：

其中：pi为用于隔离故障fi的测试序列，为pi中测试的数量。

2 多值测试诊断策略

2.1 基于信息熵算法的多值测试诊断策略

测试提供的信息量越大，故障就越容易被检测和隔离。根据信息增量启发策略，测试选择的依据如下［4］：

基于信息熵的多值测试诊断策略是不断从备选测试集中选择信息量和测试代价比值最大的测试tq，使系统中所有故障状态都被检测和隔离，被选择的测试组成测试序列，生成故障诊断树。

具体的计算步骤如下：

1）设系统初始的故障状态集为x=F，初始的测试集为t=T。

2）计算测试集t中的每个测试tj将故障状态集x划分为k个子集的概率分别为：

3）根据式（2）计算每个测试tj提供的信息量。

4）根据式（3）从测试集t中选择一个信息量和测试代价比值最大的测试tq。

5）故障状态集x被测试tq划分为k个子集，用式（5）更新各个子集中的故障概率：

6）重新取t为原测试集删除测试tq后的测试集，x为各故障子集，重复执行步骤 2）～5），使测试子集中测试数量小于等于1时停止。

2.2 基于准深度算法的多值测试系统诊断策略

准深度算法是建立在信息熵算法基础上的一种一步前向回溯算法［1］。该方法的基本思路如下：采用两步确定一个测试，即先用信息熵算法构造出以各候选测试为顶点的临时诊断树，再用启发式函数k*计算和比较这些临时诊断树，得到最佳诊断树，将该诊断树的第一个测试作为当前最佳测试。本节将对二值准深度算法进行改进，使其能用于多值测试系统，建立基于准深度算法的多值测试系统诊断策略。该算法的搜索流程如下页图1所示。

准深度算法的计算步骤如下：

1）设系统初始的故障状态集为x=F，初始的测试集为t=T。

2）将故障状态集x用测试集t中的每个测试tj划分为k个子集。

根据式（4）计算各故障状态子集的概率。

用式（6）更新各个故障状态子集中故障概率：

然后用信息熵算法对各子集进行诊断策略优化，获得以tj为第一个测试的临时诊断树Dj。

用启发式函数k*计算临时诊断树Dj对状态集x的单位测试代价的诊断信息增量：

式中，IG（x；Dj）表示Dj提供的关于x的诊断信息量，COST（x；Dj）表示Dj的平均测试代价，分别由式（8）、式（9）计算。

式中，Dj（k）表示由诊断树Dj的顶点tj到叶子节点xjk的测试序列，表示该序列的长度，表示该序列中第i个被执行的测试的代价。

3）对状态集x选择具有最大单位测试代价的诊断信息量的tq。

4）故障状态集x被测试tq划分为k个子集，分别为，用式（5）更新各子集中的故障概率。

5）重新取t为原测试集删除测试tq后的测试集，x为各故障子集，重复执行步骤 2）～4），使测试子集中测试数量小于等于1时停止。

3 实例分析

采用文献［9］中的实例来分析基于准深度算法的多值测试诊断策略优化方法。实例来自文献［9］中的表2，它具有6个故障状态和4个测试，单个测试最多输出4种测试结果，是一个4维的多值测试系统，系统相关性矩阵及其参数如表2所示。

表2 系统相关性矩阵

当采用t1为第1个测试时，根据测试结果可将系统故障集分为 3 个模糊集｛f0，f3，f4｝，｛f1，f5｝和｛f2｝，｛f0，f3，f4｝概率为 0.70+0.10+0.05=0.85，｛f1，f5｝概率为0.01+0.12=0.13，｛f2｝概率为 0.02。

首先对3个模糊集依次运用信息熵算法建立诊断树，得到 f0的测试序列为｛t1，t2｝，f3和 f4的测试序列为｛t1，t2，t3｝，f1和 f5的测试序列为｛t1，t2｝，f2的测试序列为t1。

然后计算临时诊断树D1所获得的诊断信息和平均测试代价为：

因此，临时诊断树D1对状态集F的单位测试代价的诊断信息增量为：

同理，分别采用t2，t3和t4对状态集F构建临时诊断树，如图2所示。计算各临时诊断树对状态集的单位测试代价的诊断信息增量如下：

因此，状态集｛f0，f1，f2，f3，f4，f5｝的最优测试为单位测试代价的诊断信息量最大的测试t2。依据测试t2结果将状态集划分为｛f0，f1｝和｛f2，f3，f4，f5｝2 个模糊集，剩余测试集为｛t1，t3，t4｝，状态集｛f0，f1｝只有测试 t4可隔离，而状态集｛f2，f3，f4，f5｝再用准深度算法进行搜索，得到临时诊断树对状态集｛f2，f3，f4，f5｝的单位测试代价的诊断信息量最大的测试为t1，并将状态集划分为｛f2｝，｛f5｝和｛f3，f4｝，而状态集｛f3，f4｝只有测试t3可隔离，因此，优化的诊断策略如图3所示，总的期望测试代价为22.54。如果只用信息熵算法进行搜索，那么首先选择的测试为t1，总的期望测试代价为23.01。该算法与文献［9］中采用Rollout算法生成的诊断策略相同。

4 计算复杂度分析

诊断策略问题最复杂的情况是在故障树的构建过程中，所有的测试都被用到［14-15］。

在最复杂的情况下，用信息熵算法生成故障树将产生n层节点。其中：第i层的节点数为，故障树的总节点数为

准深度算法在生成诊断树的过程中产生n层节点。在前n-1层中，第i层的节点数为

5 结论

多值测试系统的诊断策略优化设计问题是一个计算爆炸问题，全局最优算法不适用于复杂多值测试系统的诊断策略优化设计。本文用准深度算法对信息熵算法进行优化，建立了基于准深度算法的多值测试系统诊断策略，通过实例分析，证明了准深度算法所得费用不大于信息熵算法，且准深度算法的计算时间可接受。因此，该算法可用于复杂多值测试的诊断策略优化设计。

［1］邱静，刘冠军，杨鹏，等.装备测试性建模与设计技术［M］.北京：科学出版社，2012.

［2］孙煜，刘松风，马力.贪心算法在系统故障诊断策略生成中的应用［J］.计算机系统应用，2011（1）：150-154.

［3］TU F，PATTIPATI K R.Rollout strategy for sequential fault diagnosis ［J］.IEEE Trans on Systems， Man and Cybernetics，2003，33（1）：86-99.

［4］PATTIPATI K R，ALEXANDRIDIS M G.Application of heuristic search and information theory to sequential fault diagnosis ［J］.IEEE Transactions on Systems，Man，and Cybernetics，1990，20（4）：872-887.

［5］李登，万福，尹亚兰，等.基于改进RIG算法的动态诊断策略生成［J］.电子测量与仪器学报，2014，28（2）：159-163.

［6］杨鹏，邱静，刘冠军.基于多值测试的诊断策略优化生成［J］.仪器仪表学报，2008，29（8）：1675-1678.

［7］黄以锋，景博，茹常剑.基于信息熵的多值属性系统诊断策略优化方法［J］.仪器仪表学报，2011，32（5）：1003-1008.

［8］王伟，胡清华，于霄，等.多值属性系统的故障诊断策略最优化方法［J］.仪器仪表学报，2008，29（5）：1073-1078.

［9］黄以锋，景博.基于Rollout算法的多值属性系统诊断策略［J］.控制与决策，2011，26（8）：1269-1272.

［10］刘远宏，刘建敏，冯辅周，等.基于Rollout信息启发式算法的故障诊断策略［J］.计算机工程，2015，41（8）：291-295.

［11］王成刚，刘志远，杨智勇.电子装备多值测试故障诊断策略设计［J］.兵工学报，2011，32（10）：1287-1291.

［12］张峻宾，蔡金燕，孟亚峰，等.基于蚁群算法的电子设备多值测试故障诊断策略［J］.火力与指挥控制，2014，39（9）：112-116.

［13］匡翠婷，宋家友，吕游.改进的基于霍夫曼编码的故障诊断策略［J］.计算机应用，2015，35（S1）：186-188.

［14］赵文俊，张强，匡翠婷.多值测试诊断策略优化设计［J］.计算机测量与控制，2015，23（12）：3636-3939.

［15］杨成林，田书林，龙兵.多值故障字典的测点选择与序测试设计［J］.系统工程与电子技术，2009，31（9）：2271-2275.