基于蚁群算法的电子设备多值测试故障诊断策略*

张峻宾，蔡金燕，孟亚峰，李丹阳

（军械工程学院，石家庄 050003）

基于蚁群算法的电子设备多值测试故障诊断策略*

张峻宾，蔡金燕，孟亚峰，李丹阳

（军械工程学院，石家庄 050003）

测试序列优化设计是故障诊断中的重要组成部分，最优测试序列能提高故障诊断的效率，常见的故障诊断系统均基于二值属性，而多值属性系统的测试优化问题研究的较少。针对多值属性系统测试序列优化问题的特点，提出了一种改进蚁群算法，结合二值属性系统和多值属性系统的关系，设计了适应于多值属性优化的状态转移规则和信息素更新机制。针对在等测试费用和故障先验概率的情况下不能寻优的问题，制定了对应的优化标准，符合实际的测试需求。通过对比试验，证明了其能解决电子系统多值属性系统的序列优化问题，扩展了多值属性电子系统的测试优化策略。

多值测试，多值属性，故障诊断，蚁群算法，测试序列优化

引言

电子系统故障测试问题需要考虑其各种故障发生的先验概率和对应的测试代价［1-5］。设计求解最优的测试序列，使故障测试中在达到预定的隔离精度时，实现整体最小的测试代价，是故障测试优化研究的一个热点［1-3，6］。在故障测试优化过程中常常会遇到两个问题：

一是在故障隔离的过程中，存在被隔离的故障测试代价一样且发生概率一样的可能性，智能搜索算法就会出现盲目的进行优化，不能得到一个合理的测试序列。此时需要制定合理的优化策略规则对优化方案进行指导，产生最优的测试序列［7-8］。

二是目前主要研究的多针对二值属性系统的解决方法，对于多值属性系统的研究相对较少，在实际的测试诊断过程中，很多测试具有多值属性，因此，研究多值属性系统的测试序列优化问题是十分必要的。

在文献［1］提出了基于r元霍夫曼编码的启发函数实现多值测试的方案，但没有给出其进行多值测试算法的性能，不能直观地评价其优劣［1］；在文献［2］中提出了一种基于二值测试的优化算法（信息增量启发式算法）同多值逻辑相结合的改进诊断树方法，在一定程度上能够实现多值测试［2］；在文献［3］中提出了将序贯测试问题拆分为测点选择与序测试设计两个问题的解决方案，但在其测试代价比本文提出的算法高［3］；在文献［9］中提出了一种基于rollout的多值测试算法，其不能克服等测试费用和故障先验概率下正确的寻优［9］，而本文提出的算法和其相比，一样可以达到最优的效果，并能克服其缺点，等等。

本文针对系统故障诊断中的多值属性系统测试序列优化问题，提出了一种改进的蚁群算法，将成功运用在二值属性系统中的蚁群算法扩展到多值属性系统中，根据多值属性系统特点，设计了相应的状态转移规则和信息素更新机制，并采用蚁群算法和遗传算法相融合的联合优化策略，解决了多值属性系统的序列优化问题，为多值属性系统的测试优化问题提供了一条新的解决途径。

与此同时，针对在相同的测试代价和故障发生的先验概率的问题，制定了以遍历深度均值为主和遍历深度方差相结合的优化方案，加速了故障快速隔离。

1 测试优化标准

测试优化标准是智能搜索算法在寻优过程中的标准，也即是约束条件，多以测试代价最小作为评判准则［7-8，10］。

1.1 变测试费用下和故障先验概率下的测试优化标准

结合实际，可定义测试序列优化问题由四元矢量组（T，F，C，P）组成［1］。其中矢量集F表示系统的故障状态。F={f0，f1，…，fn}，（0≤i≤m），fi表示故障状态集中的第i种故障状态；系统中n个可测点组成可测集T={t1，t2，…，tn}，对应的测试费用集为C= {c1，c2，…，cn}；P=［p（f0），…p（fm）］T为系统中各故障状态发生的先验概率向量，其中p（fi）（0≤i≤m）表示对应故障状态fi发生的先验概率。

定义故障-测试相关矩阵D（m+1）×n=［dij］。其中dij表示测试点tj对故障状态fi的检测属性，测试tj的具有k维的测试属性，则dij取值为0～k-1。基于二值测试的相关矩阵D表示为：

相关矩阵D的行数代表故障状态的个数，相关矩阵D的列数代表测试矢量的个数。

定义测试代价J：

其中A=［aij］是一个（m+1）×n阶矩阵，当选择测试tj用于隔离故障状态fi时，aij=1，否则aij=0。

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

1.2 等测试费用下和故障先验概率下的测试优化标准

当未隔离的故障发生的先验概率P和测试费用集C都相等的时候，此时需要有新的合理的评判标准作为约束条件。在专家系统中，没必要一步一步地进行询问和判断，首先应该使用能将故障信息大致平分为两部分的测试矢量进行故障测试，类似于二分法。假设每个故障完全隔离时的遍历深度分别为depthi，故障集的平均遍历深度（average_depth）定义为：

例：假如某个电路具有4种故障F=［f1，f2，f3，f4］，其具有的测试矢量T=［t1，t2，t3，t4，t5，t6］分别能将故障按下页图1和图2的方式隔离。

在此情况下，如果出现的故障状态是f4，假如按照图1的方式进行故障隔离，需要施加3次测试矢量，而按照图2的方式进行隔离，只需要施加两次测试矢量。另一方面，故障隔离方式1隔离出所有的故障平均需要施加（1+2+3+3）/4=2.25次测试矢量，而故障隔离方式2平均需要施加（2+2+2+2）/4=2次测试矢量。当需要被隔离的故障种类很多的时候，故障隔离方式1比方式2测试矢量的平均次数也将显著增加。显然第2种故障隔离方式优于第1种故障隔离方式。

图1 故障隔离方式1

图2 故障隔离方式2

1.3 测试优化方案的重要步骤

将在二值属性系统中定义的二值向量s=［si］T在沿用至多值属性系统中，si只取值0或1，i∈［1，m］。用s表示系统目前的状态。系统故障状态全集表示为s=［11…1］T，si与故障状态fi对应，且：

测试矢量tj（1≤j≤n）代表故障—测试相关矩阵D第j列。tj的行数对应系统中故障状态数目。按一定顺序，用每列表示一组相应测试属性的测试向量，其中对应测试属性相同的值为1，否则为0。此时在二值测试矩阵D的基础上进行扩展，得到与多值属性对应的扩展测试矩阵Dk，在D的第1列前插入属性列。此时k的只是一种标识符，不代表其他的意义。比如：

针对Dk而言，此时Dk（：，1）有多少种不同的属性，其对应的测试矢量就有多少列。就式（3）而言，第1列有1、2、3、4共4种不同的属性，则对应的测试矢量有4种，而此测试矢量智能测出不同维数的故障，相同维数的故障不能进行分辨。

此处假设Dk的第j列的测试属性维数为k，则选择测试tj对当前状态集s进行测试隔离的过程可表示为：

Step1：s与tj相与，结果再同s相异或，得出的结果tj为中“0”属性项对s的检测隔离结果。

Step2：s分别与tj中各列向量相与，隔离出的子集用sl表示，其中（1≤l≤k）。

2 基于蚁群算法的多值属性系统的设计

蚁群算法（Ant Colony Algorithm，ACA）是一种模拟进化算法，能够成功解决众多优化问题［11-13］。多值属性系统和二值属性系统一样，其都可转为一种动态树结构的寻优问题。其主要流程如下：首先定义系统故障状态全集s=［11…1］T为初始蚁群，将每一种故障状态看作一只相应位置上的蚂蚁，每只蚂蚁的目标就是找到相应的故障状态。搜索过程中，当每只蚂蚁都找到相应的故障状态时，搜索结束［14］。

蚁群搜索的最终目标是在当测试费用和故障发生的先验概率不等的时候，在所有故障被隔离的情况下，所有蚂蚁经过的测试代价之和（即J）最小；当出现某些需要被隔离的故障的测试费和发生的先验概率都一样的时候，此时在所有故障被完全隔离的情况下，遍历深度最小的测试序列作为最优测试序列；基于此的遍历深度一样的时候，遍历深度方差最小将作为辅助的评判手段［13］。

对于一个拥有m个故障状态的状态集，将其中所有故障都隔离出来至多需要m-1次有效测试。由于所给的测试集是一个完备测试集，因而蚁群算法的初始解空间必然存在。

在解空间初始化之后，还需要制定蚁群的状态转移规则。令初始时刻每个故障点的信息素为“1，从而构成了一个全1向量：

nf_ele=［1 1 1…1］，其个数对应系统中测试数目。nf_ele的更新将在每带搜索结束后每代搜索结束后根据当代最优的测试序列值进行更新。

当前状态s选择下一个测试矢量的转移概率为

其中allow_test（s）k代表蚂蚁k下一步允许使用的测试集。η是一个启发函数，代表了从一个测试矢量转移到施加另一个测试矢量的期望程度。α和β分别表示信息素和启发式因子的相对重要程度。

当所有蚂蚁完成一次故障遍历（故障完全隔离）之后，结合多值属性系统的特点，各路径上的信息素更新按照以下公式进行：

H为常数，ρ表示路径上信息素的蒸发系数，1-ρ表示信息数的持久系数，Δnf_ele（st）表示信息数的增量，evytestcost为每次的测试代价，采用分层加权的策略，pj对应第l层的概率总和，δ为层间衰减系数。

启发函数η采用以下规则：

充分考虑了测试代价、测试属性等关键问题。其中test_dim（s）表示测试Dk（：，1）用于区别状态s的测试属性维数，即经过施加Dk（：，1）后原状态s被分割成的子集个数。cost（s）为测试Dk（：，1）代价。

当检测到未隔离的故障测试费用和故障先验概率相等的时候，此时启动计数功能，每个故障分别各自计数，当施加一次测试矢量，被分割的故障均自动计数1次。当被隔离出的故障是单故障的时候，此故障计数停止。以此类推，直到所有的故障均被隔离完毕得到这些故障的遍历深度depthi。此时计算故障的平均遍历深度average_depth。在蚁群算法中，当平均遍历深度在规定搜索代数内没有发生的时候，停止搜索，输出最优解。

3 实例验证

本文采用文献［3］中的实例，对所提出的算法进行验证，其故障-测试矩阵如表1所示。

其对应测试费用为C=［9 12 15 8］，对应的蚁群算法中各参数取值如下：λ=0.9，Q=2，α=1，β=0.6，

表1 故障-测试矩阵表1

ρ=0.95，通过蚁群算法，在迭代到第6次的时实现了收敛，且此时对应的测试代价为：J=22.54，同原文献［9］中用Rollout算法得出的最优解一致，验证了蚁群算法在多只测试故障诊断中的有效性，同时得到了和Rollout算法一样的诊断树。此时的故障测试遍历深度平均值为：average_depth=。

表2 故障-测试矩阵2

为了进一步验证本文提出的算法对多值测试系统故障诊断优化的有效性，对文献［6］中的案例进行了对比验证。

图3 最优故障测试优化树

此时对应的蚁群算法此时各参数仍然取值如下：λ=0.9，Q=2，α=1，β=0.6，ρ=0.95。为了和文献形成对比，本次试验也重复进行3000次试验进行数据统计，最优测试代价99%在J=5.70，优于文献［6］的测试代价绝大部分在20左右的结论，而且使用蚁群算法能够在最小迭代次数内实现收敛。其测试优化树为如图3所示。

4 总 结

测试优化问题是故障诊断的重要内容，故障属性不可能千篇一律的被作为二值属性进行研究，这样势必会浪费很多有用信息，降低故障诊断的效率，增加测试代价。与二值属性系统相比，多值属性系统更加复杂，在工程上也应用更多。

本文提出的基于蚁群算法实现多值属性系统的测试优化策略的方案能够达到降低测试代价、提高测试效率作用的目的。扩展了多值属性测试优化的途径。

二值属性系统和多值属性系统有相互的联系。对比试验也证明了本文提出的算法能够降低测试代价，相比其他文献中提出的算法，具有明显的优越性，有一定的工程应用价值。

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

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

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

［4］ 薄翠梅，柏杨进，杨海荣，等.多切面分类改进独立成份与支持向量机集成故障诊断方法［J］.控制理论与应用，2012，29（2）：229-234.

［5］ 林海军，滕召胜，迟 海，等.基于信息融合的汽车衡称重传感器故障诊断［J］.控制理论与应用，2010，27（1）：25-31.

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

［7］ Krishna R P，Mark G A.Application of Heuristic Search and Information Theory to Sequential Fault Diagnosis［J］.IEEE Trans on Systems，Man and Cybernetics，1990，20（7）：872-887.

［8］ Starzyk J A，Liu D，Liu Z H，et al.Entropy-Based Optimum Test Nodes Selection for Analog Fault Dictionary Techniques［J］.IEEE Trans.on InstruMentation Measurement，2004，37（53）：754-761.

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

［10］Fang T，Pattipati K R，Deb S，et al..Computationally Efficient Algorithms for Multiple Fault Diagnosis in Large Graph Based Systems［J］.IEEE Transactions on Systems，Man，and Cybernetics，2003，30（1）：73－85.

［11］张景虎，边振兴.基于蚁群算法的图像边缘检测研究［J］.火力与指挥控制，2010，35（2）：115-118.

［12］刘 伟，王太勇，周 明，等.基于蚁群算法的工艺路线生成及优化［J］.计算机集成制造系统，2010，16（7）：1378-1382.

［13］杨 帆，胡春平，颜学峰.基于蚁群系统的参数自适应粒子群算法及其应应用用［J］.控制理论与应用，2010，27（11）：1479-1488.

［14］陈 伟，陈 杰，辛 斌.求解面向进攻的武器-目标分配问题的蚁群算法［J］.火力与指挥控制，2012，37（4）：37-41.

Research on Fault Diagnosis Strategy of Electronic Systems Multi-value Test Based on Ant Colony Algorithm

ZHANG Jun-bin，CAI Jin-yan，MENG Ya-feng，LI Dan-yang
（Ordnance Engineering College，Shijiazhuang，050003，China）

Test sequencing optimization design is an important part of fault diagnosis.The optimized test sequence can improve the ability of fault diagnosis.The binary attribute systems were researched widely，while there are fewer researches on multi-value attribute systems.According to the multi-value attribute system test sequencing problems，a novel Ant Colony Algorithm was advanced. Combining the relation between binary attribute systems and multi-value attribute systems，multi-value attribute optimization state transition rule and pheromone update mechanism were designed.Under the same fault prior probability and test cost，a novel optimization standard was advanced，it satisfies test requirements.The contrast experiments prove that the proposed scheme can solve multi-value attribute electronic systems fault diagnosis and the strategy has been extended.

multi-value test，multi-value attribute，fault diagnosis，Ant colony Algorithm，test sequencing optimization

TP391

A

1002-0640（2014）09-0112-05

2013-07-20

2013-09-15

国家自然科学基金资助项目（61271153、61372039）

张峻宾（1987- ），男，四川绵阳人，硕士研究生。研究方向：信号与信息处理系统故障诊断、故障自修复。