基于霍夫曼编码的与或树启发式的多值测试算法研究

《基于霍夫曼编码的与或树启发式的多值测试算法研究》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、基于霍夫曼编码的与或树启发式的多值测试算法研究潘兴涛赵文俊空军工程大学航空机务士官学校摘要：对复杂航空电子装备，采用棊于二值测试的故障诊断策略设计算法，将损失大量信息，降低测试精度和效率。本文针对多值测试的诊断策略优化设计问题进行研宄，提出基于霍夫曼编码的与或树启发式搜索算法，通过实例仿真验证该算法是可行的。关键词：多值测试;启发式搜索算法;航空电子;近年来，随着飞机机载航电系统越来越数字化、综合化，复杂航空电子装备的维护也越来越具有挑战，常出现故障虚警率高、维修排故难等问题。该问题引起了国内外学者的广泛关注，提出了不少自适应算法，括基于信息增量的贪婪

2、算法、动态规划算法、遗传算法等，并取得不少研究成果，但0前大多数研究都是基于二值测试(Binarytest)的，而实际屮有很多测试具有多值输出，即多值测试(Multi-valuedtest)。因此，研光多值测试的诊断策略优化设计问题，以解决多值测试的诊断策略问题。1问题形式化描述多值测试与二值测试故障诊断问题类似，也可以由五元组(F，P，T，C，D)进行描述。其中多值测试的F、P、T和C与二值测试的含义和表示是相同的，分别为被测系统的故障状态有限集合，系统各种诊断结论的先验概率分布集合，系统可用的测试集，测试代价集合。与二值测试不同之处在于故障-测试依

3、赖矩阵D=[dtj]{mU)Xn,二值测试中D矩阵是只有测试通过和测试失败的二值矩阵，矩阵元素札只冇0和1;而多值测试中D矩阵是一个多值矩阵，矩阵元素札可以是0到v-1屮任意整数，v表示多值测试屮测试输出最多的个数。2多值测试下诊断树生成算法采用基于霍夫曼编码的与或树启发式搜索算法来解决多值测试下的测试排序问题，其基本思想是:针对待扩展节点，根据测试的不同输出依次计算通过每个测试所产生的枝节点，应用基于霍夫曼编码的启发式函数计算出隔离这些枝节点所需的最小隔离代价。如式（1）所示。再用式（2）依次计算出每个可用测试的启发式函数值。通过比较选出启发式函数值

4、最小的测试作为最佳测试向下展开。在建立诊断树过程中，不断选择启发式函数值小的测试向下展开，直到得到最终的优化诊断树。多值测试条件下，基于霍夫曼编码的与或树启发式搜索算法生成诊断树的具体步骤如下：步骤1:设置初始节点。将与或树的根节点设置为系统所有可能的故障状态,记为故障状态模糊集X，把故障状态模糊集X作为当前待扩展节点。步骤2:对于待扩展节点X，生成对应的可用备选测试集合（包括当前标记路径上未用过的测试），依次从备选测试集合中选择测试，然后执行以下操作：步骤2.1:选择一个测试，记为T」，根据用多值测试的诊断推理机式（2）推出执行测试t后的各个子集Xj

5、a（）步骤2.235Y=Xja（）,由式（3）计算子集Y的概率；步骤2.3:判断Y中故障的个数是否等于1，若是，则说明该节点是终端叶节点，标记为可解（true），并设置h（Y）=0;否则，用式（1）计算Y的启发式函数值h⑺。步骤2.4:由式（4）计算X对应的测试Tj的隔离费用估计h（X）。步骤3:对步骤2.4中得到的待扩展节点X对砬的可用备选测试启发式函数值进行比较，选择启发式函数值最小的测试1^作为第一个最佳测试。步骤4:用步骤3中优选的测试tk将故障模糊集X扩展为a个子集Xka()。步骤5:设子集Xka()为当前待扩展的故障模糊集X,重复步骤2.4

6、,直到与或树中所有的故障集都不能再分解为止。3实例验证以参考文献［1］给出的系统为例。该系统共有6个故障状态:f。、f、f2、f3、f4和f5,其屮f。为系统正常(无故障)状态;4个可用的测试点：h、t2、和U测试代价集£={◦，，c2,c3,c4}={10,13,16,9};系统的故障概率集和相关性矩阵如表1所示。表1系统相关性矩阵下载原表对于初始故障集XHfQ,fbf2,f3,f.bf5}，根据步骤2和步骤3，故障集X通过每个可用测试tj(l

7、最佳测试，将根节点向下展开。根据步骤4，测试么将根节点XHf。，fbf2,f3,f4,f5}分为三个新的子节点，分别为故障模糊集Xu={f。，f3，f4}、X12={fbf5}和Xl3={f2h图1初始故障集X通过测试tj(l^j^4)的平均隔离代价下载原图选择XlF{f。，f3,fJ作为当前故障模糊集X，根据步骤2和步骤3，故障集Xn通过可用测试t2、t3的平均隔离代价如图2所示，由图可知节点Xn通过t2的平均隔离代价比t3小，因此，选择测试tj乍为Xu的最佳测试，将节点Xu向下展开。测试t2将故障模糊集Xu={f。，f3，f.J分为两个新的子节点，

8、分别为故障模糊集X斤{f3,f4}和X21={f。}。故障模糊集X2(Hf3,f4}可用的测试