基于粘贴模型的测试优选＊

王红霞 叶晓慧 潘佳梁 张 丽

（海军工程大学电子工程学院1） 武汉 430033） （海军工程大学图书馆2） 武汉 430033）

0 引 言

随着武器装备复杂程度的日益提高，对其进行测试性设计和故障诊断也变得越来越困难，因此，优选测试对于BIT设计和诊断系统设计的作用也越来越重要.目前，测试性和故障诊断学界对测试选择问题做了大量的初步研究，主要包括基于信息理论的排序选择方法［1－4］，基于组合优化的搜索算法［5－7］，以及基于矩阵分析的测试的方法［8－9］等，它们在一定程度上解决了测试选择问题，但是也存在着一定的不足.基于信息理论的排序选择方法是用信息熵来定义测试对于故障检测和故障隔离的有用程度，并以此作为测试的权重，优先选择权重的测试，直到满足测试性要求为止；基于组合优化的搜索算法则首先定义测试选择的目标函数和约束条件，然后采用各种智能优化算法来求解.基于矩阵分析的测试的方法是通过分割相关矩阵，在初选测试点范围内不断寻找信息量大、合理有效的测试.前2种方法涉及信息权重和目标函数的定义，主观性较强.

从数学角度来讲，测试选择问题是一个组合优化问题，在满足Pdij＝1（理想测试）的约束条件下，测试选择问题可以映射为一个集合覆盖问题，由于基于覆盖问题是一个NP完全问题.因此，寻求高效的优化算法来解决测试优选问题，对于加快测试过程和诊断等方面有着十分重要的现实意义.

DNA计算是一种以DNA分子与相关的某些生物酶等作为最基本材料的、基于某些生化反映等为基础的一种新的计算模式，这种计算模式首先是由Adleman博士［10］于1994年提出来的，它的最大优点是充分利用DNA分子具有海量存储遗传密码，以及生化反应巨大的并行性.它克服了电子计算机存储量小与运算速度慢这2个严重的不足，具有运算速度快，信息存储量巨大、耗能小等优点.本文提出运用DNA计算模式中的基于粘贴运算的粘贴模型求解测试优选问题.

1 粘贴模型

粘贴模型［11］是一种基于分子操作和随机访问内存的一种DNA计算模型，是一种通用计算机系统，采用单链和双链的混合形式进行编码，它的优点是在运算过程中不需要DNA链的延伸，也不需要酶的作用，并且DNA链可重复使用.

粘贴模型的信息表示法是基于碱基互补性、用DNA来表示信息的方法.这种方法利用两种基本类型的单链DNA分子：存储链和粘贴链.一个存储链是u个碱基长（文中统称链的长度为 ），且含有k个不重益的子链，其中，每个子链长度为v.因此，必须有u≥kv.下面假设每个子链顺序相连，它们之间没有碱基.在计算过程中，每一个子链等同于一个布尔变量（或者相当于一个比特位）.值得注意的是子链之间应当是互不相同的，它们中任意2个关于一些碱基的位置应该是不同的（这是确保每一个比特位的明显特征）.

存储链上的一个特定子链或者是开，或者是关.如果一个粘贴链退火到存储链中它的匹配子链上（简单地说就是互补到匹配子链上），则这个特定的子链称为开；反之，则该子链称为关.一个存储复合体是存储链的通称，存储复合体表示二进制数，其中，开（关）的子链表示该位为l（0）.因此，存储复合体就是一个部分为双串的DNA串.

粘贴模型中的计算由一系列合并、分离、设置和清除操作组成.输入和输出都是试管，为了读出输出结果，一个存储复合体必须从输出试管中分离出来，并确定其退火的粘贴链.

用粘贴模型求解测试优选问题的基本思想，是用具有单链、双链混合的存储复合体来表示集合S＝｛1，2，…，q｝中全部2q种可能出现的选择.子集Ci被选中时，则对i进行标记，然后将那些标记着所含的全部p种物件的存储复合体分开，并且读出使用最少子集个数的那一个.

2 粘贴模型应用于测试优选

2.1 测试优选问题的描述

在诊断学中，测试优选的集合是能保证各测试性能指标的完备测试集（如果不是完备测试集，则必须添加测试点以保证其完备性，即保证关联矩阵中不存在全0行）.但是并不一定是最小完备测试集并且要测试的费用尽可能小.因此，测试优选的目的是找到满足测试性指标且测试费用最小的测试集合.

由于测试优选是建立在故障与测试之间的关联矩阵上，因此先设系统故障状态和对应的测试之间的关联矩阵Dm×n（m为故障状态的数量，n是测试的数量），其中关联矩阵中的元素dij＝1表示测试tj能检测故障状态fi；而dij＝0表示tj不能检测故障状态fi；cj是测试tj的费用.

测试优选可以描述为：F＝｛f1，f2，…，fm｝是具有m个故障状态的一个非空集合，t＝｛t1，t2，…，tn｝是具有n个测试的非空集合，ti→｛f1，f2，…，fk｜1≤k≤n｝是由F中的非空子集构成的集合.测试优选问题是要在 中一个子集，使其满足（l为子集的个数）能检测到F中的所有故障，并且使其具有最小的期望测试费用.

例如，表1是一个系统的故障——测试关联矩阵，有5个测试和5个故障状态.

表1 测试关联矩阵

2.2 测试优选的粘贴模型

使用粘贴模型的算法解决测试优选问题，算法思想就是从n列中，按照某种规则依次选择若干列盖住所有的行，使得这些被选中列的代价之和尽量地小.

其具体算法设计要点如下.

步骤1 初始试管N0和存储复合体的设计.用一个序数对表示N0，即N0是一个（q＋p，q）库，是由具有q＋p个子链存储复合体组成的库.其中，每个存储复合体前q个子链或开或关（指1，2，…，q中哪些数属于由该存储复合体所表示的特定的子集I），后p个子链是关的.因此，一个（q＋p，q）库中含有2q个不同类型的存储复合体，表示S＝｛1，2，…，q｝的2q个子集.在N0中，存储复合体的前q个子链代表实际的输人，而后p个子链可以用作中间存储器的输出.在测试优选问题中，q对应于测试关联矩阵的列数n，p＝q表示故障被全部检测.以表1中的数据来说明算法计算过程，则q＝5，其对应的初始试管和存储复合体为32个.

步骤2 对N0中的每个存储复合体后p个子链进行标记.标记后的结果是使得该存储复合体前q个子链上每个双链位段对应的子集合Ci中的每个元素，在后p个子链对应的位段标记成双链.最终，子链q＋j，1≤j≤p中满足下列条件的子链会被打开：j属于Ci，其中，i属于由存储复合体所表示的指标集I.具体步骤如下.

步骤2.1 对于i＝1，施行分离操作.将试管N0分离试管＋（N0，1）和试管－（N0，1）；则试管＋（N0，1）有 16 个存储复合体：1000000000，1100000000， 1010000000， 1001000000，1000100000， 1110000000， 1101000000，1100100000， 1011000000， 1010100000，1001100000， 1111000000， 1110100000，1101100000，1011100000，1111100000.

步骤2.2 对＋（N0，1）施行设置操作.set（＋（N0，i），q＋cji），其中，Cji是Ci中的所有元素；而C1＝｛f3，f4，f5｝，所以将＋（N0，1）中每个存储复合体的第8，9，10个子链打开，之后这16个存储复合体分别为：1000000111，1100000111，1010000111， 1001000111， 1000100111，1110000111， 1101000111， 1100100111，1011000111， 1010100111， 1001100111，1111000111， 1110100111， 1101100111，1011100111，1111100111.

步骤2.3 N0←合并（＋（N0，i），－（N0，i））.

步骤2.4 对于i＝2，3，…，q，重复执行步骤2.1～步骤2.3.

步骤3 保留最后个子链全部为开的存储复合体，清除其余的存储复合体.则最后保留的存储复 合 体 有： 0101011111， 1110011111，1101011111， 1010111111， 1001111111，0111011111， 0110111111， 0101111111，1111011111， 1110111111， 1101111111，1011111111，0111111111，1111111111.

步骤4 从N0中检测出前5个子链开的数目最小的一个存储复合体.0101011111，即最小测试集为｛t2，t4｝.

步骤5 计算最小测试集的费用，如果满足指标要求，则算法结束，否则返回步骤4找出次小的测试集.

3 实验结果分析

为了验证算法的有效性，分别对已知最优解的测试关联矩阵和随机生成的测试关联矩阵进行测试优选.为便于进行比较，选择文献［12］中测试数据进行分析.用m＊n＊表示矩阵的相关数据，m表示行数（故障状态数），n表示列数（测试数），如m10n8表示有行数是10列数是8.表2是已知最优解的测试优选结果，表3是对随机生成满足要求的矩阵优选的结果.

表2 测试优选结果（已知最优解）

表3 测试优选结果（已知最优解）

为了验证算法的性能，又随机生成了多种维数的矩阵进行验证分析，结果发现：本文提出的算法实现的测试优选的结果与故障－测试矩阵中的列向量顺序无关.从算法中，可以看出，矩阵中列向量的排序有Pnn种，如例子n＝5，即有120种列向量的组合，每种组合对应的初始试管N0和存储复合体都相同.因为初始试管N0是由2q个子集组成，在算法步骤2.2设置操作后，每种组合对应的＋（N0，i）将不再相同，但是＋（N0，i）合并后，保留的最后p个子链全部为开的存储复合体表面不相同，但实质上对应的最小的测试集是一样的，即测试集的另一种组合表示.如相关矩阵中列向量t1t2t3t4t5是本文的计算顺序，计算结果最小测试集为｛t2，t4｝；调整后的顺序为t′1t′2t′3t′4t′5＝t3t4t5t1t2，则计算结果为最小测试集为｛t′2，t′5｝⇔｛t2，t4｝.同样，把t1t2t3t4t5表 示 为120种其他任一种顺序，最终也可以得到与t1t2t3t4t5一样的结果.

4 结 论

本文提出的基于DNA粘贴模型的测试集优化方法，是把测试集优化问题转化为一个集合覆盖问题，针对测试集优化问题的特点，改进DNA的粘贴模型的算法来实现测试集合的优化问题.本方法具有三个特点：（1）与故障－测试矩阵中的列向量顺序无关；这个特点比基于蚁群算法的方法相比具有一定的优越性，因为它对测试的排列顺序不敏感.（2）计算结果中无冗余测试.算法要求后p个子链全部为开的存储复合体的前q个子链为开的最小测试集，假设结果中有冗余测试，则它将是最小测试集的超集.（3）矩阵冗余列向量可能会产生无解的情况，因为冗余列向量可能会导致后p个子链不全部为开.因此要对矩阵进行化简，使得其无冗余测试.

本方法不需要主观设置算法的参数（比如遗传算法和蚁群算法的适应度函数）.实验中，本文用提出的方法对随机生成的规模较大的测试集优化结果好于文献［6－7］的方法，文中矩阵中用1表示测试与故障之间的关系，即测试Pdij＝1的情况，当Pdij＜1时，问题还需要进一步研究.

［1］Pattipati K R.Application of heuristic search and information theory to sequential fault diagnosis［J］.IEEE Transactions on Systems，Man，And Cybernetics，1990，20（4）：872－886.

［2］Raghavan V，Shakeri M，Pattipati K.Optimal and near－optimal test sequencing algorithms with realistic test models［J］.IEEE Transaction on Tystems，Man，and Cyberentics，1999，22（2）：11－26.

［3］Wei W，Qing H，Daren Y.Application of multival－ued test sequencing to fault diagnosis［C］／／The Eighth International Conference on Electronic Measurement and Instruments，ICEMI＇2007，China，Xi＇an，Aug.16 2007－July 18 2007：4737－4740.

［4］黎琼炜，胡 政，易晓山.系统级BIT设计中的测试选择方法［J］.计算机工程与应用，2001（19）：127－129.

［5］苏永定，钱彦岭，邱 静.基于启发式搜索策略的测试选择问题研究［J］.中国测试技术，2005（5）：46－48.

［6］俞龙江，彭喜源，彭 宇.基于蚁群算法的测试集优化［J］.电子学报，2003（8）：1 178－1 181.

［7］乔家庆，付 平，尹洪涛.基于遗传排序的测试集优化［J］.电子学报，2007（12）：2 335－2 338.

［8］张复春，张凤鸣，顾文灿.关于测点分布的矩阵分析［J］.测试技术学报，2004（2）：114－117.

［9］杨 露，沈怀荣.测试点设计的一种快速优化方法［J］.兵工学报，2007（3）：349－352.

［10］Adleman L.Molecular computation of solutions to combinational problems ［J］. Science，1994，266（266）：1 021－1 024.

［11］王鸣涛，叶春明，马慧民.基于DNA粘贴模型求解最小集合覆盖问题［J］.上海理工大学学报，2008（1）：41－44.

［12］王小港.遗传算法在VLSI设计自动化中的应用研究［D］.上海：中国科学院上海冶金研究所，2001.