AO＊算法详解(一) 测试优化背景知识与推理模型建立

电子系统的测试性分析在电子工程应用中具有很大的价值，接下来的几篇文章中，我会系统地和大家介绍测试优化中最常见的一种方法——AO*算法。由于说明算法的战线过长，用三篇文章介绍，内容分别为：

（一）测试优化背景知识与推理模型建立

（二）AO*算法的最优策略生成原理

（三）算法的总体过程及MATLAB实现

本文介绍测试优化的研究背景及前期模型建立。

测试优化背景

随着系统复杂性的增加，产品生命周期的缩短、生产成本的降低以及技术的革新，智能工具的需求在产品的生命周期的各个阶段变得越来越重要。对于高度集成的复杂系统，其相关元素高度聚合，系统元素的底层设计细节对工程人员不透明，因此对于系统故障状态的检测成为系统测试性设计中的一个十分重要的环节。测试优化针对电子产品设计对缩短研制、实验、投入使用的周期，提高系统可靠性的客观需求，提供合适的故障诊断测试方案，使得电子产业自动化程度达到显著提升。好的测试优化方法对工程应用有很大的价值。近年，AO*算法因其生成策略的高效性被广泛应用，在接下来的部分将针对该方法的推理依据信息进行简单的介绍，在后续的文章中会对该方法进行详细的讲解。

? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?

推理模型建立

测试性分析的流程如图所示，可以看出故障信息是测试优化的核心依据，根据故障和测点之间的定性分析，从结构模型中生成推理模型（在测试优化中，由于该推理模型反映了测试与故障间的依赖信息，更多是称为依赖模型），用以表示系统中的因果关系。依据定性的因果关系约束，来推理测试流程。?因此，测试性依赖模型是整个算法的输入与核心部分之一。建立测试性依赖模型，需要人工分析电子系统的控制流程，整个过程涵盖基本的控制系统操作以及系统功能、性能测试的要求，测试和控制过程的必要需求。

? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?

? 该流程需要针对系统典型功能单元，进行测试性离线建模，来构建系统多层级故障传播模型。基于系统物理组成与逻辑功能，以及通过对功能与故障模式的分析，可利用多信号流模型将系统划分为若干相对独立的现场可更换单元，同时建立不同单元、单元与测试之间的依赖关系，并离线形成可屏蔽指定失效模式的多层故障传播模型。

? 整个建模过程可将系统中所有包含诊断信息的可测试性变量定义为信号节点，并建立信号传播、交联、测试因果关系，以及构建层次化复杂系统结构描述，需要注意的是其建模方法围绕功能模块外部测试/诊断特性，不涉及内部机理、技术实现细节。将控制系统内置的测试单元（如BIT单元）作为基本测试状态感知器，进而将各类原始、含噪信息压缩、抽象并转换为诊断、预测所需要的征兆，并按照部件的故障概率和传播故障权重进行划分。同时对候选故障测试点进行故障可能性排序，来减少故障源的重复测试，并区分故障源的测试级别。所有测试均被视为二值测试，即每个测试结果只分为达标与不达标两种类型，故测试序列与二叉树的故障诊断树等价，进而将测试序列的求解问题转化为对最优故障诊断树的求解。另一方面，由于故障诊断树在形式上与与或图类似，即可以将故障诊断树视为广义的与或图，因此可以利用启发式搜索算法对可行的故障诊断树路径进行广度搜索与深度搜索，以获得最优序贯测试流程。

? ?对于测试性设计，其目标是保证系统足够可观测（或可控制），因此根据系统的可测性和可控性结合结构框图或多信号流图建立依赖信息。例如某磁带播放机结构框图和多信号依赖关系如下图所示，这里，我们假设系统内无测点，因此该系统的性能只能通过它的四个输出进行监测，假设内部无可测试的点，则可以通过系统的框图或者多信号流图得到其故障依赖矩阵如下表所示。

? ? ? ? ? ? ? ? ? ?

? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?

? 通过该表可以定性的反映系统的测试因果信息，从而可以通过测试优化方法产生正确的测试决策流程。同时，除了正确性，测试优化的另一目标是生成一组总体测试代价最小的测试序列以识别系统的故障。因此，除了系统的依赖关系，对于测试流程的优化还考虑了各个故障的先验概率、测点的测试代价和各个测点的测试时间。

? ?综上，故障依赖模型包括以下信息：

? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?

（1）S?= {s0,?s1,?s2,……,sM}表示系统的各种状态，s0表示系统没有故障发生的状态，s1到sM表示系统发生不同故障的状态。

（2）P?= {p0,?p1,?p2,……,?pM}是各个系统状态发生的先验故障概率向量，需要注意的是，本方案假定系统只能处于某个故障状态或无故障状态，且在进行序贯测试前需要对先验故障概率向量P进行归一化。

（3）T?= {?t1,?t2,……,?tN}是系统N个可用的测试集合。

（4）C?= {c1,?c2,……,?cN}表示对应的测试代价向量，其中测试代价采用测试时间、测试费用及其他相关因素进行衡量。

（5）D是一个N(M+1)阶的0-1矩阵，其每个元素表示测试与系统故障的关系，被定义为故障-测试依赖矩阵。对于测试tj，如果测试tj能诊断出故障状态si，那么dij?= 1，否则dij?= 0，其中i?= 0,1,…,M，j?= 1,2,…,N。显然对于无故障状态s0，对任意i，均有d0j?= 0。

? 通过这些信息反映的测点的诊断能力和效率，AO*算法产生适应实际情况的最优测试方案，在下一篇文章中，我们将介绍AO*算法的最优策略生成原理。