测试序列优化问题是在考虑系统中各种故障发生的先验概率和各种测试代价的情况下，设计一组最优的测试序列，使其满足故障隔离精度的要求，并且整体的测试代价最小。一般将测试序列优化问题看作一种最小代价动态树的构造问题，该问题已被证明是NP-complete问题，传统的全局寻优算法在解决这一问题时因为计算量过大而难以在实际中应用。在实际的测试诊断过程中，考虑到时间和测试代价，刻意追求一种全局最优的测试方案并无太大意义；因此，采用近似算法来求解最优测试序列成为解决测试序列优化问题的研究热点。

目前主要的解决方法是以信息熵概念为基础的各种启发式方法^{[1, 2, 3, 4, 5, 6]}。Shakeri等人基于信息熵概念，采用霍夫曼编码方法构建启发函数，提出AO算法及其改进的AO^*算法；Tu Fang提出了一种基于信息熵的Rollout启发式搜索算法，提高了算法的效率和优化质量；黄以锋将Rollout算法扩展到多值属性系统，对算法性能进行了分析；杨成林提出了一种将测试节点优选和测试序列优化相结合的解决方案。

以上提出的各种方法都是基于信息熵概念的启发式搜索算法，由于太过于依赖启发函数，对于问题内在信息的挖掘不够，难以保证找到全局最优解。针对以上问题，根据二值属性系统的特点，定义了状态集向量及测试向量，将测试隔离过程表示为向量的位运算过程，在此基础上提出一种改进的蚁群算法，利用蚁群搜索过程中的反馈信息，充分挖掘问题本身的信息特征，制定了相应的状态转移规则，并提出了分层加权的信息素更新策略，引入遗传算法中的变异方法，提高了搜索效率和优化质量。

测试序列优化问题由以下要素组成：

（1）系统的故障状态由一个有限集F表示。F={f₀，f₁，…，f_n}，其中f₀通常可表示为系统无故障状态，f_i（0≤i≤m）表示m种故障状态中的第i种故障状态。

（2）系统中各故障状态发生的先验概率为P。P=[p（f₀），…，p（f_m）]^T，其中p（f_i）（0≤i≤m）表示故障状态fi发生的先验概率。

（3）系统中n个可测点组成可测集T={t₁，t₂，…，t_n}，与之对应的测试费用集为C=[c₁，c₂，…，c_n]。

（4）故障-测试相关矩阵D_（m+1）×n=[d_ij]，其中当测试点t_j察觉到故障状态f_i时，d_ij=1，否则d_ij=0。如表 1所示。显然当f₀表示系统无故障状态时，d_0j=0（1≤j≤n）。

表 1 故障-测试相关矩阵

表选项

（5）定义测试代价J

其中A=[a_ij]是一个（m+1）×n阶矩阵，当选择测试t_j用于隔离故障状态f_i时，a_ij=1，否则a_ij=0。

测试序列优化问题可描述为在可测集T中选择一组测试，并给出一种测试序列方案，使能够隔离状态集F中的全部故障状态，并使代价J最小。

根据二值属性特点，给出如下定义：

定义1：在二值属性系统中，定义二值状态集向量s=[s_i]^T（0≤i≤m，s_i=1 or 0）。用s表示系统目前的状态集。其中当f_i在当前的故障状态集中时，s_i=1，否则s_i=0。

由以上定义，系统故障状态全集表示为s=[1，1，…，1]^T，当隔离出故障f_k（0≤k≤m）时，s=[0，…，0，1，0，…，0]^T，即s_k=1。

定义2：定义测试向量test_j=D（：，j）（1≤j≤n）。其中j为与测试向量相应的测试，D（：，j）为D矩阵的第j列。

二值系统中选择测试t_j对当前状态集s进行测试隔离的过程，可表示为测试向量test_j与当前状态集s的位与运算以及s与以上结果的位减运算。即隔离出的两个子集用s₁和s₀表示，则s₁=s∧test_j，s₀=s-s₁。

定义3：当s∧test_j≠s且s∧test_j≠0时，则test_j对于状态s具有隔离能力，称t_j为状态s的有效测试。

由定义3可得以下推论：

推论1：对于一个拥有m+1个故障的状态集，将其中的故障全部隔离至多需要m次有效测试。

测试序列优化问题可描述为选择一组测试向量test，将故障状态全集s=[11…1]^T隔离为单故障状态，且使式（1）所示的测试代价最小。

蚁群算法由M.Dorigo于1991年在其博士论文中首次被提出，其设计的人工蚁模型中引入了真实蚂蚁觅食行为中的正反馈机制、信息素挥发机制以及基于概率的状态转移策略，形成一种有效的群智能寻优算法。之后经过多次改进，成功解决了许多复杂的组合优化问题，这些初步研究已显示出蚁群优化算法在求解复杂优化问题（特别是离散优化问题）方面的优越性，是一种很有发展前景的方法^[7]。

测试序列优化问题是一种特殊的动态规划问题，用传统的蚁群算法解决具有一定难度。为解决此类问题，首先定义系统故障状态全集s=[11…1]^T为初始蚁群，将每一种故障状态看作一只相应位置上的蚂蚁，每只蚂蚁的目标就是找到相应的故障状态。搜索过程中，当每只蚂蚁都找到相应的故障状态时，此代搜索结束。算法的整体流程如图 1所示。

图 1 算法搜索整体流程

图选项

每个蚁群的具体搜索过程如图 2。每次搜索开始令s=[11…1]^T为系统故障状态全集，故障状态全部隔离时，搜索结束。

图 2 蚁群的搜索过程

图选项

传统的蚁群算法在解决动态树结构寻优问题时往往效果不佳，对于复杂的问题甚至难以得到最优解或较理想的近优解，因此必须在传统蚁群算法的基础上进行改进。

由定义3可知，在隔离同一故障时相同的测试不可能出现两次，且由推理1可知，在所给测试能够保证隔离出故障集中的每一个故障时，算法一定能够找到一组解，从而保证了算法初始解空间的存在。

初始时刻定义信息素向量Tau=[11…1]^T，为1行n列的行向量，其中n为全部测试数。当前状态s选择下一个测试test的转移概率为

其中α为信息素浓度对于转移概率的重要程度，β为启发函数对于转移概率的重要程度，可根据具体情况确定α、β值。蚁群将根据式（2）给出的转移概率公式，采用轮盘赌方法确定下一次选择的测试^[8]。

式（2）中allow函数的功能是在每次测试完成后，根据当前状态s，给出下一次所有可用的测试集，即定义3中定义的有效测试集。k可理解为可选测试的指针。传统的蚁群算法往往忽略启发函数项，经试验启发函数对算法的最优解质量具有重要的影响，因此本文在综合考虑了测试代价、故障概率的基础上，给出一个启发函数Eta，其设计思想是尽量选择使测试后产生的两个子集中总故障概率平衡的测试，表达式如下：

其中，即s1状态中所含故障状态的概率总和；，cost_test为测试test的代价。

在动态树结构的寻优问题中，树中节点的层次位置是重要的信息，对于搜寻最优解有很大的影响。而传统的蚁群算法中，信息素的更新往往是均匀的，没有利用节点的层次位置信息，因而很难在动态树结构的寻优问题中找到最优解，针对以上问题本文提出了一种分层加权的信息素更新机制，信息素更新公式为

初始时刻，信息素向量中各元素的值相等。在以后的搜索中，将对每代搜索出的最优的测试序列进行信息素更新。式（4）中ρ为每代信息素保留的权值，1-ρ为信息素衰减系数。式（6）中Q为常数，cost为每代最优的测试代价；λ为本文定义的层间衰减系数；l为隔离故障状态f_i时经过的测试数，即经过第一个测试点时l=1，经过第n个测试点时l=n；表示在最优测试序列的第l层中隔离故障f_i用到的测试test_j的总概率。经过分层加权处理，算法更易于区分测试的层次和重要度，加快算法的收敛速度。

为提高算法的全局搜索能力，避免算法因信息素差距过大而过早进入停滞状态，本文将采用最大最小蚂蚁系统策略限定信息素浓度值。

为了避免蚁群算法陷入局部最优值，引入遗传算法的变异思想，在每代搜索结束后对信息素向量中浓度值低于阈值的项进行变异，提高其浓度值至最大值。经试验证明，变异操作可有效提高算法搜索到最优值的概率。

为验证算法的有效性，本文将对文献^[1]中的超外差接收机系统进行测试序列优化。该系统有22个先验概率和36个预备测试，测试代价均为1，其相关矩阵D如表 2所示，其中矩阵元素值为1表示该测试检测到相应故障，否则值为0。各故障的先验概率为

P=[0.001 85，0.009 23，0.185，0.001 85，0.001 85，0.009 23，0.001 85，0.009 23，0.185，0.185，0.185，0.001 85，0.009 23，0.185，0.009 23，0.001 85，0.009 23，0.001 85，0.00185，0.001 85，0.001 85，0.001 85]^T

表 2 超外差接收机系统故障-测试相关矩阵

表选项

表 3所示算法采用的参数值，最终给出最优解中的一组如图 3，最优测试代价为3.353 5，和文献^[1]中的最优测试代价3.35比较，本文提出的算法给出了一个比较满意的结果^[9]。

表 3 算法主要参数说明

表选项

图 3 测试序列优化结果

图选项

测试代价值随进化代数的变化情况如图 4所示，可以看出算法以较高的效率收敛于最优值。

图 4 测试代价优化过程

图选项

本文对电子装备故障测试诊断中的测试序列优化问题进行了研究，对测试序列优化问题进行了分析和定义，提出了一种改进的蚁群算法对序列优化问题进行求解，本文给出的解决方案主要有2个特点：

（1）根据二值属性系统特点，定义了状态集向量、测试向量、有效测试等概念，将故障的测试隔离过程转化为状态集向量和测试向量的位运算过程，为序列优化问题提供了基本的数学描述。

（2）对传统蚁群算法进行改进，设计了灵活的状态转移规则，提出了一种分层加权和遗传变异相结合的信息素更新机制，为将蚁群算法应用于动态树结构的寻优问题提供了一种新思路。

与传统的单一依靠启发函数的方法相比，本文提出的算法在搜索过程中可以更加充分地发掘问题本身提供的信息，能够更有效地找到全局最优解。仿真实验证明该算法是一种行之有效的方法，具有一定的工程应用价值。