王紅霞 葉曉慧 潘佳梁 張 麗

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

0 引 言

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

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

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

1 粘貼模型

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

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

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

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

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

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

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

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

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

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

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

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

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

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

其具體算法設(shè)計(jì)要點(diǎn)如下.

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

步驟2 對(duì)N0中的每個(gè)存儲(chǔ)復(fù)合體后p個(gè)子鏈進(jìn)行標(biāo)記.標(biāo)記后的結(jié)果是使得該存儲(chǔ)復(fù)合體前q個(gè)子鏈上每個(gè)雙鏈位段對(duì)應(yīng)的子集合Ci中的每個(gè)元素，在后p個(gè)子鏈對(duì)應(yīng)的位段標(biāo)記成雙鏈.最終，子鏈q＋j，1≤j≤p中滿足下列條件的子鏈會(huì)被打開：j屬于Ci，其中，i屬于由存儲(chǔ)復(fù)合體所表示的指標(biāo)集I.具體步驟如下.

步驟2.1 對(duì)于i＝1，施行分離操作.將試管N0分離試管＋（N0，1）和試管－（N0，1）；則試管＋（N0，1）有 16 個(gè)存儲(chǔ)復(fù)合體：1000000000，1100000000， 1010000000， 1001000000，1000100000， 1110000000， 1101000000，1100100000， 1011000000， 1010100000，1001100000， 1111000000， 1110100000，1101100000，1011100000，1111100000.

步驟2.2 對(duì)＋（N0，1）施行設(shè)置操作.set（＋（N0，i），q＋cji），其中，Cji是Ci中的所有元素；而C1＝｛f3，f4，f5｝，所以將＋（N0，1）中每個(gè)存儲(chǔ)復(fù)合體的第8，9，10個(gè)子鏈打開，之后這16個(gè)存儲(chǔ)復(fù)合體分別為：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 對(duì)于i＝2，3，…，q，重復(fù)執(zhí)行步驟2.1～步驟2.3.

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

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

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

3 實(shí)驗(yàn)結(jié)果分析

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

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

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

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

4 結(jié) 論

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

本方法不需要主觀設(shè)置算法的參數(shù)（比如遺傳算法和蟻群算法的適應(yīng)度函數(shù)）.實(shí)驗(yàn)中，本文用提出的方法對(duì)隨機(jī)生成的規(guī)模較大的測(cè)試集優(yōu)化結(jié)果好于文獻(xiàn)［6－7］的方法，文中矩陣中用1表示測(cè)試與故障之間的關(guān)系，即測(cè)試Pdij＝1的情況，當(dāng)Pdij＜1時(shí)，問題還需要進(jìn)一步研究.

［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)級(jí)BIT設(shè)計(jì)中的測(cè)試選擇方法［J］.計(jì)算機(jī)工程與應(yīng)用，2001（19）：127－129.

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

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

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

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

［9］楊 露，沈懷榮.測(cè)試點(diǎn)設(shè)計(jì)的一種快速優(yōu)化方法［J］.兵工學(xué)報(bào)，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］.上海理工大學(xué)學(xué)報(bào)，2008（1）：41－44.

［12］王小港.遺傳算法在VLSI設(shè)計(jì)自動(dòng)化中的應(yīng)用研究［D］.上海：中國科學(xué)院上海冶金研究所，2001.