基于Rollout算法的模拟电路测点选择

黄以锋 景 博 穆举国

(空军工程大学工程学院1，陕西 西安 710038;空军驻西安地区军事代表局2，陕西 西安 710077)

0 引言

测点选择问题是模拟电路故障诊断和可测性设计过程中的一个关键问题，得到了国内外学者的广泛关注。孙秀斌［1］、胡梅［2］、汪鹏［3］等人分别提出了采用可测性测度和故障隔离度等方法进行测点选择。故障字典法是一种重要的模拟电路故障诊断方法。

在故障字典法中，测点的选择是一个非常重要的环节，其目的是在故障都可隔离的前提下，选择测点数量最小的测点集。最小测点集问题已被证明是NP-hard问题［4］，随着模拟电路复杂度的提高，求取全局最优解将遇到计算爆炸问题。

目前，人们在局部最优算法的研究方面已有不少成果。Prasad［4］等提出了三种包含法和一种排除法;Starzyk［5］等提出了一种基于信息熵的方法;Yang［6］等在信息熵理论的基础上提出了基于启发式图搜索的方法;Golonek［7］、Zhang［8－9］等使用现代优化算法求取模拟电路的最小测点集。

Rollout算法是Bertsekas提出的一种用于组合优化问题的计算方法，并已被应用于随机调度和顺序测试等领域［10］。本文采用Rollout算法来解决模拟电路的测点选择问题。在整数编码故障字典的基础上，以信息熵算法为基础算法［5］，采用Rollout算法构建了一种新的测点选择算法。理论分析和仿真试验表明，该算法的计算效果优于信息熵算法。

1 问题描述

1.1 模糊集

由于模拟电路中的元件存在容差，在电路正常状态下和各种故障状态下，测点的电压不是一个确定的值，而是一个连续的小区间。这些小区间可能重叠，使该测点无法区分重叠的多个状态。为解决这个问题，可根据各个状态的测点电压区间，将电压分为若干个模糊域;测点电压区间落入某个模糊域的所有故障状态(包括正常状态)组成一个模糊集，然后依次用整数对模糊集进行编码。

1.2 整数编码故障字典

对所有测点的模糊集进行划分、编码后，可根据故障状态、测点和模糊集间的关系建立整数编码故障字典，其中F={f0，f1，…，fm}为故障状态集(包括正常状态)，T={t1，t2，…，tn}为可用测点集，dij为模糊集的整数编码。

1.3 测点优选目标

在故障字典中，若故障状态fa和fb分别属于测点tj的不同模糊集，则fa和fb可被测点tj隔离。若任意两个故障状态都可被某个测点隔离，则故障状态都可隔离。

测点选择的目的是在故障状态都可隔离的前提下，选择测点数量最小的测点集Ta。

式中:T为可用测点集;Tk为可隔离所有故障状态的测试集;|Tk|为测点集Tk中测点的个数。

2 测点选择方法

2.1 基于熵的测点选择方法

基于信息熵的测点选择方法，根据测点提供的信息量越大越有利于故障隔离的原理，不断选择信息量最大的测点组成优化的测试集，直至所有的故障都被隔离［5］。

根据信息理论，假设测点tj将故障状态集F划分为k个模糊集，则tj提供的关于F的信息量为:

式中:f为要隔离的所有故障状态的个数;Fij为测点tj的模糊集中编码为i的模糊集包含的元素个数。

定义熵E(j)为:

显然，选择信息量最大的测点等价于选择熵E(j)最小的测点。

信息熵算法计算的大致过程是首先用所有可用测点将故障状态集F划分为多个模糊集，用式(3)分别计算各个测点的熵，选择熵最小的测点tj;然后更新tj划分的各个子集的可用测点集和故障状态集，再用式(3)计算各个子集，选择熵最小的测点;不断循环计算，直至所有故障状态都被隔离。

2.2 基于Rollout算法的测点选择方法

Rollout算法是建立在另一种算法基础上的一种一步前向回溯算法。该算法不是一种最优算法，但其计算效果较基础算法好。

采用Rollout算法选择模拟电路测点的具体步骤如下。

①假设要测试的模拟电路的故障状态集为F0，可用测点集为T0，则初始化节点 F={F0}，可用测点集T={T0}。

②首先用测点集T中的每个测点tq将节点F中的所有故障状态集分别划分为多个子集，所有包含元素大于1个的子集组成节点Fq，对节点Fq中的所有子集xqj，用信息熵算法计算对应的优化测点集Tqj;然后用式(4)计算节点Fq的优化测点集Tq。

式中:|xqj|为故障状态子集xqj中元素的个数。

③比较测点集T中每个测点对应的优化测点集中测点的个数，按照式(5)，选择最小测点集对应的测点。若有多个最小测点集，则选择其中序号最小的测点ta。

式中:|Tq|为测点集Tq中测点的个数。

④将测点ta加入到测点集Tmin。比较ta对应的节点Fa，若节点Fa为空集，计算结束，Tmin就是优化后的最小测试集;否则，定义节点F=Fq，T为原测点集删除测点ta后的测点集，重复步骤②～④。

在Rollout算法的计算过程中，每前进一步，都用信息熵算法进行试探并选择最优的结果，不难分析出，Rollout算法的计算结果优于信息熵算法。

节点Fj的与或树如图1所示。

图1 节点Fj的与或树Fig.1 The AND/OR tree of node Fj

图1中，Fj为树的任意一个可扩展节点。对于节点Fj，信息熵算法和Rollout算法都能计算出一个优化测试点。假设ti为信息熵算法计算出的优化测试点，Ti为节点Fi对应的测点集，ta为Rollout算法计算出的优化测试点，Ta为节点 Fa对应的测点集。在Rollout算法中，需要用信息熵算法作试探性的前向搜索，如假设选择了一个测试点ti，然后用信息熵算法计算出测点集Fi，得到优化测点集中测点的数量。同理，可计算出若选择其他测点将得到的优化测点集中测点的数量，选择数量最小测点的ta。所以选择测点ta，将得到的优化测点集中测点的个数一定会小于或等于选择测点ti，即:

下面用两个实例来说明Rollout算法的详细计算过程。

实例1来自于文献［4］的例1，该电路共有9个故障状态和4个可用测点。用Rollout算法计算实例1的具体过程如图2所示，其中虚线的椭圆表示节点，实线的椭圆表示状态集，长方形的方框表示选择相应测点后计算出的优化测点集，0、1、2、3表示选择相应测点后计算出的优化测点集中测点的个数。采用Rollout算法的计算步骤如下。

首先进行初始化，初始时，节点F中只有一个故障状态集 F0={f0，f1，…，f8}，可用测点集 T={t1，t2，t3，t4};然后用4个测点展开节点F中的状态集，得到4个子节点，并用式(4)计算各子节点的优化测点集，由于测点t4对应的优化测点集{t1，t2}最小，测点t4被选中;最后将测点t4加入测点集Tmin，更新F和T，重复第②步到第④步，直至计算结束。最终得到优化测点集Tmin={t4，t1，t2}。若用信息熵算法进行计算，得到的优化测试集为{t1，t2，t3，t4}。

图2 实例1的计算结果Fig.2 The computing result of example 1

实例2来自于文献［4］的例5，该电路共有19个故障状态和11个可用测点。电路图和电路的整数编码故障字典详见文献［4］。图3展示了实例2的计算过程。从图3可以看出，在节点的展开过程中，依次选择了测点 t11、t1、t5和 t9，优化测试集为{t1，t5，t9，t11}，与信息熵算法的计算结果一致。

图3 实例2的计算结果Fig.3 The computing result of example 2

3 试验分析

为了比较算法的计算效果，在英特尔双核处理器E2140、内存 1 GB 和 Windows XP，Matlab7.1环境下，编写了信息熵算法和Rollout算法的Matlab程序。

随机生成1～10个具有100个故障状态、40个测点和6个模糊集的故障字典，然后分别用信息熵算法和Rollout算法计算这10个故障字典的优化测点集。在采用Rollout算法计算得出的优化测点集中，测点数量最多为5个，而信息熵算法得出的测点数量最少为10个。因此，Rollout算法的计算效果明显优于信息熵算法。在计算时间方面，信息熵算法用时不到0.1 s，Rollout算法也仅需3 s。

为了说明故障状态、可用测点集和模糊集对两种算法计算效果的影响，进行了以下3组试验。3组试验结果如图4所示。

图4 不同情况下的计算结果Fig.4 The computing results under different cases

①随机产生8个故障状态为100个、可用测点为40个、模糊集分别为3～10的故障字典，分别用信息熵算法和Rollout算法计算出优化测点集，求得优化测点集中测点的个数，从而得到测点个数与模糊集个数之间的关系曲线。为了更准确地描述它们之间的关系，重复计算5组故障字典，得到测点个数的平均值与模糊集个数之间的关系曲线如图4(a)所示。

②随机产生5组故障字典，每组故障字典由12个故障字典组成。这12个故障字典的故障状态都为100个，模糊集都为6个，可用测点个数分别为20个、25个、…、75个。分别用信息熵算法和Rollout算法计算出优化测点集，求得优化测点集中测点个数的平均值，得到该平均值与可用测点个数之间的关系曲线如图4(b)所示。

③随机产生5组故障字典，每组故障字典由9个故障字典组成。这9个故障字典的测点个数都为40个，模糊集都为6个，故障状态个数分别为30个、45个、…、150个。分别用信息熵算法和Rollout算法计算出优化测点集，求得优化测点集中测点个数的平均值，得到该平均值与故障状态的个数之间的关系曲线如图4(c)所示。

以上3组试验结果表明，Rollout算法计算出的测点个数都小于信息熵算法，且Rollout算法的曲线较平滑，说明计算结果较稳定。

另外，从图4(a)可以看出，随着模糊集数量的增加，Rollout算法的优化测点数量有明显减少的趋势，信息熵算法不明显，这说明随着模糊集数量的增加，Rollout算法的优势更突出。从图4(b)可以看出，随着可用测点数量的增加，Rollout算法的优化测点数量有减少的趋势，而信息熵算法不明显，这说明随着可用测点数量的增加，Rollout算法的优势在扩大。在图4(c)中，信息熵算法的曲线上升的速度明显大于Rollout算法，说明随着故障状态数量的增加，Rollout算法的优势更明显。

4 结束语

故障字典法是模拟电路的一种常用的故障诊断方法，测点选择是该方法中的一个重要环节，其目的是在故障都可隔离的前提下，选择测点数量最小的测点集。本文针对最小测点集问题，在整数编码故障字典和信息熵算法的基础上建立了基于Rollout算法的测点选择方法，给出了算法的详细计算步骤，并通过实例展示了算法的详细计算过程。

本文通过理论分析，证明了Rollout算法的计算效果优于信息熵算法。试验结果也表明Rollout算法的计算效果优于信息熵算法，而且随着故障字典复杂度的提高，优势更加明显。本文提出的方法计算效果较好、计算时间短，可用于复杂模拟电路的测点选择，同时对模拟电路的可测性设计也具有一定的参考价值。

［1］孙秀斌，陈光禑，谢永乐.模拟集成电路的测试节点选择［J］.电子信息学报，2004，26(4):645 －650.

［2］胡梅，王红，杨士元，等.模拟电路软故障诊断测试节点优选的仿真研究［J］.系统仿真学报，2009，21(12):3837 －3841.

［3］汪鹏，杨士元.模拟电路故障诊断测试节点优选新算法［J］.计算机学报，2006，29(10):1781 －1785.

［4］Prasad V C，Badu N S C.Selection of test nodes for analog fault diagnosis in dictionary approach［J］.IEEE Transactions on Instrumentation and Measurement，2000，49(6):1289 －1297.

［5］Starzyk J A，Liu D，Liu Z H，et al.Entropy-based optimum test points selection for analog fault dictionary techniques［J］.IEEE Transactions on Instrumentation and Measurement，2004，53(3):754 －761.

［6］Yang Chenglin，Tian Shulin，Long Bing.Application of heuristic graph search to test-points selection for analog fault dictionary techniques［J］.IEEE Transactions on Instrumentation and Measurement，2009，58(7):2145－ 2158.

［7］Golonek T，Rutkowski J.Genetic-algorithm-based method for optimal analog test points selection ［J］.IEEE Transactions on Circuits and Systems II:Express Briefs，2007，54(2):117 －121.

［8］Zhang Chaojie，He Guo，Liang Shuhai.Test point selection of analog circuits based on fuzzy theory and ant colony algorithm［C］∥IEEE AUTOTESTCON 2008，Salt Lake City，2008.

［9］张超杰，贺国，梁述海，等.基于改进粒子群算法的模拟电路测试点选择［J］.华中科技大学学报:自然科学版，2009，37(11):31 －34.

［10］Tu F，Pattipati K R.Rollout strategy for sequential fault diagnosis［J］.IEEE Transactions on Systems，Man and Cybernetics-Part A:Systems and Humans，2003，33(1):86 －99.