基于粘貼模型的測試優(yōu)選＊

王紅霞 葉曉慧 潘佳梁 張 麗

（海軍工程大學電子工程學院1） 武漢 430033） （海軍工程大學圖書館2） 武漢 430033）

0 引 言

隨著武器裝備復雜程度的日益提高，對其進行測試性設(shè)計和故障診斷也變得越來越困難，因此，優(yōu)選測試對于BIT設(shè)計和診斷系統(tǒng)設(shè)計的作用也越來越重要.目前，測試性和故障診斷學界對測試選擇問題做了大量的初步研究，主要包括基于信息理論的排序選擇方法［1－4］，基于組合優(yōu)化的搜索算法［5－7］，以及基于矩陣分析的測試的方法［8－9］等，它們在一定程度上解決了測試選擇問題，但是也存在著一定的不足.基于信息理論的排序選擇方法是用信息熵來定義測試對于故障檢測和故障隔離的有用程度，并以此作為測試的權(quán)重，優(yōu)先選擇權(quán)重的測試，直到滿足測試性要求為止；基于組合優(yōu)化的搜索算法則首先定義測試選擇的目標函數(shù)和約束條件，然后采用各種智能優(yōu)化算法來求解.基于矩陣分析的測試的方法是通過分割相關(guān)矩陣，在初選測試點范圍內(nèi)不斷尋找信息量大、合理有效的測試.前2種方法涉及信息權(quán)重和目標函數(shù)的定義，主觀性較強.

從數(shù)學角度來講，測試選擇問題是一個組合優(yōu)化問題，在滿足Pdij＝1（理想測試）的約束條件下，測試選擇問題可以映射為一個集合覆蓋問題，由于基于覆蓋問題是一個NP完全問題.因此，尋求高效的優(yōu)化算法來解決測試優(yōu)選問題，對于加快測試過程和診斷等方面有著十分重要的現(xiàn)實意義.

DNA計算是一種以DNA分子與相關(guān)的某些生物酶等作為最基本材料的、基于某些生化反映等為基礎(chǔ)的一種新的計算模式，這種計算模式首先是由Adleman博士［10］于1994年提出來的，它的最大優(yōu)點是充分利用DNA分子具有海量存儲遺傳密碼，以及生化反應(yīng)巨大的并行性.它克服了電子計算機存儲量小與運算速度慢這2個嚴重的不足，具有運算速度快，信息存儲量巨大、耗能小等優(yōu)點.本文提出運用DNA計算模式中的基于粘貼運算的粘貼模型求解測試優(yōu)選問題.

1 粘貼模型

粘貼模型［11］是一種基于分子操作和隨機訪問內(nèi)存的一種DNA計算模型，是一種通用計算機系統(tǒng)，采用單鏈和雙鏈的混合形式進行編碼，它的優(yōu)點是在運算過程中不需要DNA鏈的延伸，也不需要酶的作用，并且DNA鏈可重復使用.

粘貼模型的信息表示法是基于堿基互補性、用DNA來表示信息的方法.這種方法利用兩種基本類型的單鏈DNA分子：存儲鏈和粘貼鏈.一個存儲鏈是u個堿基長（文中統(tǒng)稱鏈的長度為 ），且含有k個不重益的子鏈，其中，每個子鏈長度為v.因此，必須有u≥kv.下面假設(shè)每個子鏈順序相連，它們之間沒有堿基.在計算過程中，每一個子鏈等同于一個布爾變量（或者相當于一個比特位）.值得注意的是子鏈之間應(yīng)當是互不相同的，它們中任意2個關(guān)于一些堿基的位置應(yīng)該是不同的（這是確保每一個比特位的明顯特征）.

存儲鏈上的一個特定子鏈或者是開，或者是關(guān).如果一個粘貼鏈退火到存儲鏈中它的匹配子鏈上（簡單地說就是互補到匹配子鏈上），則這個特定的子鏈稱為開；反之，則該子鏈稱為關(guān).一個存儲復合體是存儲鏈的通稱，存儲復合體表示二進制數(shù)，其中，開（關(guān)）的子鏈表示該位為l（0）.因此，存儲復合體就是一個部分為雙串的DNA串.

粘貼模型中的計算由一系列合并、分離、設(shè)置和清除操作組成.輸入和輸出都是試管，為了讀出輸出結(jié)果，一個存儲復合體必須從輸出試管中分離出來，并確定其退火的粘貼鏈.

用粘貼模型求解測試優(yōu)選問題的基本思想，是用具有單鏈、雙鏈混合的存儲復合體來表示集合S＝｛1，2，…，q｝中全部2q種可能出現(xiàn)的選擇.子集Ci被選中時，則對i進行標記，然后將那些標記著所含的全部p種物件的存儲復合體分開，并且讀出使用最少子集個數(shù)的那一個.

2 粘貼模型應(yīng)用于測試優(yōu)選

2.1 測試優(yōu)選問題的描述

在診斷學中，測試優(yōu)選的集合是能保證各測試性能指標的完備測試集（如果不是完備測試集，則必須添加測試點以保證其完備性，即保證關(guān)聯(lián)矩陣中不存在全0行）.但是并不一定是最小完備測試集并且要測試的費用盡可能小.因此，測試優(yōu)選的目的是找到滿足測試性指標且測試費用最小的測試集合.

由于測試優(yōu)選是建立在故障與測試之間的關(guān)聯(lián)矩陣上，因此先設(shè)系統(tǒng)故障狀態(tài)和對應(yīng)的測試之間的關(guān)聯(lián)矩陣Dm×n（m為故障狀態(tài)的數(shù)量，n是測試的數(shù)量），其中關(guān)聯(lián)矩陣中的元素dij＝1表示測試tj能檢測故障狀態(tài)fi；而dij＝0表示tj不能檢測故障狀態(tài)fi；cj是測試tj的費用.

測試優(yōu)選可以描述為：F＝｛f1，f2，…，fm｝是具有m個故障狀態(tài)的一個非空集合，t＝｛t1，t2，…，tn｝是具有n個測試的非空集合，ti→｛f1，f2，…，fk｜1≤k≤n｝是由F中的非空子集構(gòu)成的集合.測試優(yōu)選問題是要在 中一個子集，使其滿足（l為子集的個數(shù)）能檢測到F中的所有故障，并且使其具有最小的期望測試費用.

例如，表1是一個系統(tǒng)的故障——測試關(guān)聯(lián)矩陣，有5個測試和5個故障狀態(tài).

表1 測試關(guān)聯(lián)矩陣

2.2 測試優(yōu)選的粘貼模型

使用粘貼模型的算法解決測試優(yōu)選問題，算法思想就是從n列中，按照某種規(guī)則依次選擇若干列蓋住所有的行，使得這些被選中列的代價之和盡量地小.

其具體算法設(shè)計要點如下.

步驟1 初始試管N0和存儲復合體的設(shè)計.用一個序數(shù)對表示N0，即N0是一個（q＋p，q）庫，是由具有q＋p個子鏈存儲復合體組成的庫.其中，每個存儲復合體前q個子鏈或開或關(guān)（指1，2，…，q中哪些數(shù)屬于由該存儲復合體所表示的特定的子集I），后p個子鏈是關(guān)的.因此，一個（q＋p，q）庫中含有2q個不同類型的存儲復合體，表示S＝｛1，2，…，q｝的2q個子集.在N0中，存儲復合體的前q個子鏈代表實際的輸人，而后p個子鏈可以用作中間存儲器的輸出.在測試優(yōu)選問題中，q對應(yīng)于測試關(guān)聯(lián)矩陣的列數(shù)n，p＝q表示故障被全部檢測.以表1中的數(shù)據(jù)來說明算法計算過程，則q＝5，其對應(yīng)的初始試管和存儲復合體為32個.

步驟2 對N0中的每個存儲復合體后p個子鏈進行標記.標記后的結(jié)果是使得該存儲復合體前q個子鏈上每個雙鏈位段對應(yīng)的子集合Ci中的每個元素，在后p個子鏈對應(yīng)的位段標記成雙鏈.最終，子鏈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）施行設(shè)置操作.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，重復執(zhí)行步驟2.1～步驟2.3.

步驟3 保留最后個子鏈全部為開的存儲復合體，清除其余的存儲復合體.則最后保留的存儲復 合 體 有： 0101011111， 1110011111，1101011111， 1010111111， 1001111111，0111011111， 0110111111， 0101111111，1111011111， 1110111111， 1101111111，1011111111，0111111111，1111111111.

步驟4 從N0中檢測出前5個子鏈開的數(shù)目最小的一個存儲復合體.0101011111，即最小測試集為｛t2，t4｝.

步驟5 計算最小測試集的費用，如果滿足指標要求，則算法結(jié)束，否則返回步驟4找出次小的測試集.

3 實驗結(jié)果分析

為了驗證算法的有效性，分別對已知最優(yōu)解的測試關(guān)聯(lián)矩陣和隨機生成的測試關(guān)聯(lián)矩陣進行測試優(yōu)選.為便于進行比較，選擇文獻［12］中測試數(shù)據(jù)進行分析.用m＊n＊表示矩陣的相關(guān)數(shù)據(jù)，m表示行數(shù)（故障狀態(tài)數(shù)），n表示列數(shù)（測試數(shù)），如m10n8表示有行數(shù)是10列數(shù)是8.表2是已知最優(yōu)解的測試優(yōu)選結(jié)果，表3是對隨機生成滿足要求的矩陣優(yōu)選的結(jié)果.

表2 測試優(yōu)選結(jié)果（已知最優(yōu)解）

表3 測試優(yōu)選結(jié)果（已知最優(yōu)解）

為了驗證算法的性能，又隨機生成了多種維數(shù)的矩陣進行驗證分析，結(jié)果發(fā)現(xiàn)：本文提出的算法實現(xiàn)的測試優(yōu)選的結(jié)果與故障－測試矩陣中的列向量順序無關(guān).從算法中，可以看出，矩陣中列向量的排序有Pnn種，如例子n＝5，即有120種列向量的組合，每種組合對應(yīng)的初始試管N0和存儲復合體都相同.因為初始試管N0是由2q個子集組成，在算法步驟2.2設(shè)置操作后，每種組合對應(yīng)的＋（N0，i）將不再相同，但是＋（N0，i）合并后，保留的最后p個子鏈全部為開的存儲復合體表面不相同，但實質(zhì)上對應(yīng)的最小的測試集是一樣的，即測試集的另一種組合表示.如相關(guān)矩陣中列向量t1t2t3t4t5是本文的計算順序，計算結(jié)果最小測試集為｛t2，t4｝；調(diào)整后的順序為t′1t′2t′3t′4t′5＝t3t4t5t1t2，則計算結(jié)果為最小測試集為｛t′2，t′5｝?｛t2，t4｝.同樣，把t1t2t3t4t5表 示 為120種其他任一種順序，最終也可以得到與t1t2t3t4t5一樣的結(jié)果.

4 結(jié) 論

本文提出的基于DNA粘貼模型的測試集優(yōu)化方法，是把測試集優(yōu)化問題轉(zhuǎn)化為一個集合覆蓋問題，針對測試集優(yōu)化問題的特點，改進DNA的粘貼模型的算法來實現(xiàn)測試集合的優(yōu)化問題.本方法具有三個特點：（1）與故障－測試矩陣中的列向量順序無關(guān)；這個特點比基于蟻群算法的方法相比具有一定的優(yōu)越性，因為它對測試的排列順序不敏感.（2）計算結(jié)果中無冗余測試.算法要求后p個子鏈全部為開的存儲復合體的前q個子鏈為開的最小測試集，假設(shè)結(jié)果中有冗余測試，則它將是最小測試集的超集.（3）矩陣冗余列向量可能會產(chǎn)生無解的情況，因為冗余列向量可能會導致后p個子鏈不全部為開.因此要對矩陣進行化簡，使得其無冗余測試.

本方法不需要主觀設(shè)置算法的參數(shù)（比如遺傳算法和蟻群算法的適應(yīng)度函數(shù)）.實驗中，本文用提出的方法對隨機生成的規(guī)模較大的測試集優(yōu)化結(jié)果好于文獻［6－7］的方法，文中矩陣中用1表示測試與故障之間的關(guān)系，即測試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］黎瓊煒，胡 政，易曉山.系統(tǒng)級BIT設(shè)計中的測試選擇方法［J］.計算機工程與應(yīng)用，2001（19）：127－129.

［5］蘇永定，錢彥嶺，邱 靜.基于啟發(fā)式搜索策略的測試選擇問題研究［J］.中國測試技術(shù)，2005（5）：46－48.

［6］俞龍江，彭喜源，彭 宇.基于蟻群算法的測試集優(yōu)化［J］.電子學報，2003（8）：1 178－1 181.

［7］喬家慶，付 平，尹洪濤.基于遺傳排序的測試集優(yōu)化［J］.電子學報，2007（12）：2 335－2 338.

［8］張復春，張鳳鳴，顧文燦.關(guān)于測點分布的矩陣分析［J］.測試技術(shù)學報，2004（2）：114－117.

［9］楊 露，沈懷榮.測試點設(shè)計的一種快速優(yōu)化方法［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設(shè)計自動化中的應(yīng)用研究［D］.上海：中國科學院上海冶金研究所，2001.