基于基因表達(dá)式編程的裝備測(cè)試需求建立方法?

王俊亞,陳棣湘,潘孟春

(國(guó)防科技大學(xué)機(jī)電工程與自動(dòng)化學(xué)院,湖南長(zhǎng)沙 410073）

自動(dòng)測(cè)試系統(tǒng)(Automatic Test System,ATS)是對(duì)那些能自動(dòng)完成激勵(lì)、測(cè)量、數(shù)據(jù)處理并顯示或輸出測(cè)試結(jié)果的一類系統(tǒng)的統(tǒng)稱[1].自從20世紀(jì)60年代第一代ATS出現(xiàn)以來(lái),在各國(guó)軍方和各航空公司的強(qiáng)烈需求牽引下,自動(dòng)測(cè)試技術(shù)已經(jīng)在系統(tǒng)集成[2]、測(cè)試總線[3]、測(cè)試資源模塊化和虛擬化[4]、軟件體系結(jié)構(gòu)[5]、測(cè)試數(shù)據(jù)形式化[6]等方面取得了極大成就.但是,在被測(cè)對(duì)象(Unit Under Test,UUT)測(cè)試需求分析與測(cè)試程序集(Test Program Set,TPS)之間的界限比較模糊,不利于ATS的模塊化和標(biāo)準(zhǔn)化.這個(gè)問(wèn)題自20世紀(jì)末在西方軍用ATS設(shè)計(jì)過(guò)程中得到了重視,但在我軍ATS的設(shè)計(jì)過(guò)程中還很少有相關(guān)的報(bào)告和研究文獻(xiàn).邊澤強(qiáng)、孟曉風(fēng)等人在實(shí)現(xiàn)柔性測(cè)試系統(tǒng)的快速組建和按需生成方面,利用IEEE STD 1641標(biāo)準(zhǔn)建立了UUT測(cè)試需求的標(biāo)準(zhǔn)化描述[7];王學(xué)奇、肖明清等人利用可擴(kuò)展標(biāo)記語(yǔ)言(Extensib le Markup Language,XM L)實(shí)現(xiàn)了UUT測(cè)試需求數(shù)據(jù)的跨平臺(tái)交換方法[8];根據(jù) Jackson等提出的面向問(wèn)題域的系統(tǒng)分析方法,劉金寧等提出了面向UUT問(wèn)題域的測(cè)試需求分析方法[9].美國(guó)TYX公司開發(fā)的ATS軟件開發(fā)平臺(tái)PAWS(ProfessionalATLASWork Station)不管是在軍方還是各民用航空電子領(lǐng)域都有廣泛的用途,其設(shè)計(jì)遵循IEEE 1226廣域測(cè)試網(wǎng)(A Broad Based Environment for Test,ABBET)的分層規(guī)范和VPP-2(VX IPlug&Play)接口協(xié)議,提供多種工具支持 TPS各個(gè)階段的開發(fā).其中包括三大組成部分:測(cè)試需求文檔,TPS開發(fā)平臺(tái),測(cè)試執(zhí)行系統(tǒng).其測(cè)試文檔的建立包括信號(hào)需求定義、測(cè)試策略定義和 TPS框架的生成.本文結(jié)合某型裝備的測(cè)試需求特征,提出了一種基于基因表達(dá)式編程的測(cè)試模型和測(cè)試需求的建立方法.在UUT結(jié)構(gòu)和工作原理未知的情況下,根據(jù) UUT的觀測(cè)數(shù)據(jù)建立其測(cè)試模型,分析其測(cè)試信號(hào)需求.

1 某型裝備制導(dǎo)電子箱測(cè)試需求分析

某型裝備由若干個(gè)功能電子箱組成,其中制導(dǎo)電子箱是一個(gè)專用的遙控型制導(dǎo)裝置.圖1(a)所示的制導(dǎo)電子箱結(jié)構(gòu)原理圖中,共包括6塊功能電路:采集校正電路、微機(jī)電路、接口電路、激活起動(dòng)電路、點(diǎn)火電路、電源電路.從圖1(b)制導(dǎo)電子箱的功能模型可以看出,制導(dǎo)電子箱主要提供控制算法,其輸入為一系列的誤差信號(hào)和控制信號(hào),輸出為經(jīng)過(guò)算法處理之后的控制信號(hào).

圖1 制導(dǎo)電子箱的結(jié)構(gòu)原理與功能模型Fig.1 The schematic and functionalm odel of the con trol and guide box

表1 測(cè)試信號(hào)需求分析Tab.1 The requirem en t analyze of the testsignal

從表1可以看出,制導(dǎo)電子箱激勵(lì)和響應(yīng)信號(hào)的種類和數(shù)量很多,涉及數(shù)字電平信號(hào)、模擬信號(hào)、時(shí)序信號(hào)、能量信號(hào)、編碼信號(hào)等;信號(hào)的變化范圍較大,尤以時(shí)序信號(hào)為甚.

2 基因表達(dá)式編程算法

2.1 基因表達(dá)式編程算法原理

Ferreira博士融合了遺傳編程(GP)和遺傳算法(GA)的優(yōu)點(diǎn),于2001年提出了基因表達(dá)式編程算法(Gene Expression Programming,GEP)[10].GEP在形式表達(dá)上繼承了GA的定長(zhǎng)線性編碼簡(jiǎn)單快捷的特點(diǎn),在基因表達(dá)上繼承了GP的樹形結(jié)構(gòu)靈活多變的特點(diǎn),用簡(jiǎn)單編碼解決復(fù)雜問(wèn)題,比傳統(tǒng)進(jìn)化計(jì)算快 2～4個(gè)數(shù)量級(jí)[11].由于GEP具有極強(qiáng)的全局搜索能力和計(jì)算能力,在關(guān)聯(lián)規(guī)則挖掘,符號(hào)回歸等領(lǐng)域用途廣泛.

利用GEP進(jìn)行進(jìn)化操作的基本流程如圖2所示,首先隨機(jī)生成初始的種群,包含若干個(gè)代表不同問(wèn)題解答的“染色體”或“個(gè)體”.然后將種群中的個(gè)體表達(dá)成對(duì)應(yīng)的表達(dá)式或程序,并計(jì)算每個(gè)表達(dá)式的適應(yīng)度,進(jìn)而根據(jù)適應(yīng)度和某種選擇規(guī)則進(jìn)行選擇、復(fù)制操作,讓適應(yīng)度比較高的個(gè)體有更高的機(jī)會(huì)保留到下一代中.接著對(duì)這些個(gè)體進(jìn)行各種遺傳操作,以引入新的個(gè)體.最后形成新一代種群.此過(guò)程重復(fù)進(jìn)行,直到找到符合要求的問(wèn)題解答.

在GEP中,除了和GA中類似的單點(diǎn)重組(交叉),兩點(diǎn)重組(交叉),單點(diǎn)變異等遺傳操作以外,還包括插串(Insert Sequence,IS)和根插串(Root Insert Sequence,RIS)等具有獨(dú)特動(dòng)作和含義的遺傳算子.這些是GEP所特有的遺傳算子,能夠?yàn)镚EP引入更多的新個(gè)體.

2.2 基因表達(dá)式編程算法設(shè)計(jì)

圖2 基因表達(dá)式編程算法流程圖Fig.2 The flow char t of the GEP

通過(guò)對(duì)制導(dǎo)電子箱原理和功能模型的分析,可以發(fā)現(xiàn)其本質(zhì)是一個(gè)以處理器為核心的控制單元.其測(cè)試信號(hào)需求是一定數(shù)量的激勵(lì)信號(hào),要求控制單元的輸出滿足特定的控制要求.基于此,設(shè)計(jì)了基因表達(dá)式編程算法的構(gòu)造方法,標(biāo)準(zhǔn)基因表達(dá)式編程算法包括定義函數(shù)符集合和終結(jié)符集合確定、初始種群的生成、適應(yīng)度函數(shù)設(shè)計(jì)、選擇策略、遺傳算子確定等幾個(gè)方面.下面給出基因表達(dá)式編程算法的構(gòu)造原理.

2.2.1 函數(shù)符集合和終結(jié)符集合確定

基因表達(dá)式編程算法的函數(shù)符集合與終結(jié)符集合應(yīng)該滿足封閉性[12],即要求終結(jié)符集合中每一個(gè)函數(shù)的定義域和值域都是相同的,因此在終結(jié)集合中不能同時(shí)出現(xiàn)模擬信號(hào)和數(shù)字信號(hào).并且終結(jié)符集合中的函數(shù)一般不帶參數(shù).在不滿足封閉性的時(shí)候,遺傳操作就會(huì)產(chǎn)生大量的死基因,從而影響算法的效率,但是裝備實(shí)際需求的信號(hào)又是形式各異的:模擬信號(hào),數(shù)字信號(hào),協(xié)議信號(hào)(例如RS-232信號(hào),各種編碼信號(hào)等等),但是對(duì)其操作肯定是不滿足封閉性的.這就需要一個(gè)通用的信號(hào)定義和模型.如圖3所示的 IEEE 1641標(biāo)準(zhǔn)[13]對(duì)信號(hào)模型的定義.

圖3 IEEE 1641標(biāo)準(zhǔn)定義的信號(hào)模型Fig.3 The signalm odel defined in the IEEE 1641

根據(jù)測(cè)試模型的用途,利用IEEE標(biāo)準(zhǔn)委員會(huì)在2010年9月17日最新發(fā)布的IEEE 1641標(biāo)準(zhǔn)設(shè)計(jì)了面向信號(hào)的函數(shù)符集合F={a,b,c,d,e,f,g,h,i}.其中a代表Average運(yùn)算,用來(lái)求信號(hào)的平均值;b代表Counter運(yùn)算,用來(lái)給編碼信號(hào)計(jì)數(shù);c代表Decode運(yùn)算,用來(lái)解碼已編碼的信號(hào);d代表Interval運(yùn)算,用來(lái)求信號(hào)的持續(xù)時(shí)間;e代表Peak運(yùn)算,用來(lái)求信號(hào)的峰值;f代表PeakNeg運(yùn)算,用來(lái)求信號(hào)的谷值;g代表 Instantaneous運(yùn)算,用來(lái)求信號(hào)的瞬時(shí)值;h代表 MaxInstantaneous運(yùn)算,作為最大值運(yùn)算;i代表MinInstantaneous運(yùn)算,作為最小值運(yùn)算.利用信號(hào)源類定義設(shè)計(jì)了終結(jié)符集合P={A,B,C,D,E,0,1,2,3,4,5,6,7,8,9},其中 A代表正弦信號(hào),B代表階躍信號(hào),C代表常值信號(hào),D代表噪聲信號(hào),E代表串行數(shù)字信號(hào),數(shù)字代表各個(gè)信號(hào)模型的數(shù)字參數(shù).

2.2.2 初始種群生成

考慮到測(cè)試模型的精確性,根據(jù)制導(dǎo)電子箱本身裝備的特點(diǎn),在求解該優(yōu)化問(wèn)題過(guò)程中,為了避免進(jìn)化算法過(guò)早地收斂到局部最優(yōu)解,采用基于小生境理論[14]的初始種群生成方法.

生物學(xué)上,小生境(Niche)[15]是指在特定環(huán)境中一種組織(Organism)的功能,而把有共同特性的組織稱作物種(Species).自然界的小生境為新物種的形成提供了可能性,是生物界保持近乎無(wú)限多樣性的根本原因之一.在基于小生境的算法中[16],把種群劃分為不同的子群,各子群就是具有相同特性的個(gè)體集合.子群間通過(guò)優(yōu)勝劣汰、適者生存這一機(jī)制進(jìn)行相互競(jìng)爭(zhēng).子群平均適應(yīng)值高,則其群體規(guī)模就大;反之群體規(guī)模就小.這樣,不但保持了種群中個(gè)體的多樣性,還保證種群向著預(yù)定的目標(biāo)發(fā)展.

2.2.3 適應(yīng)度函數(shù)確定

除了制導(dǎo)電子箱的觀測(cè)數(shù)據(jù)和用途之外,對(duì)制導(dǎo)電子箱的內(nèi)部工作原理了解較少,因此在適應(yīng)度函數(shù)的選擇上,采用 R-square作為制導(dǎo)電子箱測(cè)試模型辨識(shí)的適應(yīng)度計(jì)算函數(shù).其計(jì)算方法如下

式中:Ri表示第i個(gè)個(gè)體所對(duì)應(yīng)的函數(shù)模型的復(fù)相關(guān)系數(shù),-1≤Ri≤1;fi表示第i個(gè)個(gè)體的適應(yīng)度函數(shù)值.Ri的計(jì)算方法如下

式中:Pi,j是指第j個(gè)樣本中第i個(gè)個(gè)體事先指定的匹配精度;Tj表示訓(xùn)練數(shù)據(jù)中第j個(gè)樣本的數(shù)據(jù)輸入;n表示樣本個(gè)數(shù).

2.2.4 選擇操作

選擇操作就是從群體中按個(gè)體的適應(yīng)度函數(shù)值選擇出較適應(yīng)環(huán)境的個(gè)體.考慮到測(cè)試模型的生成必須能夠正確地反映被測(cè)裝備的測(cè)試需求,其正確性必須首先滿足.同時(shí)為了簡(jiǎn)化算法的復(fù)雜度,采用輪盤賭算法和精英主義算法的結(jié)合.

在精英主義算法中,每一代適應(yīng)度值最大的個(gè)體都會(huì)被無(wú)條件復(fù)制到下一代,從而保證了算法能夠快速收斂到全局最優(yōu)值.另外還對(duì)適應(yīng)度最高的個(gè)體的基因進(jìn)行備份,以免在其交叉或變異中被破壞掉.若發(fā)現(xiàn)比當(dāng)前保存的基因適應(yīng)度更高的基因,則用其替換當(dāng)前保存的基因.

在保存當(dāng)前最優(yōu)解之后,采用輪盤賭算法對(duì)剩余個(gè)體進(jìn)行選擇,個(gè)體的適應(yīng)度越高,被復(fù)制到下一代的概率就越大.各個(gè)體在下一代群體中的期望生存數(shù)目為

式中:N為種群中個(gè)體總數(shù);fi為第i個(gè)個(gè)體的適應(yīng)度值.

2.2.5 其它遺傳操作

在基因表達(dá)式編程算法中,遺傳算子一共有8種,主要包括:變異算子、倒串算子、IS插串算子、RIS插串算子、基因變換算子、單點(diǎn)重組算子、兩點(diǎn)重組算子和基因重組算子.其中單點(diǎn)重組算子和兩點(diǎn)重組算子是最重要的兩個(gè)算子,是算法進(jìn)化的主要?jiǎng)恿?lái)源;變異算子主要用于維持種群的多樣性,避免算法過(guò)早地陷入局部最優(yōu)解;插串算子是基因表達(dá)式編程算法獨(dú)有的遺傳算子,為算法提供更強(qiáng)的魯棒性和適應(yīng)性;而基因重組主要是對(duì)多基因進(jìn)行操作的.

3 系統(tǒng)實(shí)現(xiàn)與電子箱生成測(cè)試需求分析

在完成基因表達(dá)式編程算法中各部分的設(shè)計(jì)構(gòu)造后,還要完整給出對(duì)應(yīng)的算法實(shí)現(xiàn),只需在此基礎(chǔ)上給出具體的算法流程及主要參數(shù)即可.

算法主要由運(yùn)算符集合和變量集合確定、初始種群生成、適應(yīng)度計(jì)算、選擇策略和遺傳操作等步驟.在MATLAB中采用面向?qū)ο蟮木幊趟枷?因此算法實(shí)現(xiàn)的核心就是兩個(gè)類的編寫,一個(gè)是種群的類,入口參數(shù)包括:種群對(duì)應(yīng)的染色體類型,種群大小,種群頭部長(zhǎng)度,基因組數(shù),基因鏈接方式等,類中定義了best屬性用以表示當(dāng)前的最好染色體,generate()函數(shù)生成初始種群;另一個(gè)是染色體的類,構(gòu)造染色體主要針對(duì)應(yīng)用的對(duì)象即測(cè)試模型的構(gòu)造,其入口參數(shù)與種群的類相似,類中定義了fitness()、solved()和cycle()三個(gè)函數(shù),分別表示適應(yīng)度函數(shù)、終止條件滿足函數(shù)和改造染色體函數(shù).

算法流程如下:

1)定義p roblem類,包含一個(gè)獲取數(shù)據(jù)的函數(shù)和一個(gè)獲取變量名稱的方法;

2)定義繼承染色體類的sp類,定義了終止符集合和函數(shù)符集合的兩個(gè)函數(shù),并且重新定義了fitness和solved方法;

3)利用種群類的generate函數(shù)生成初始種群;執(zhí)行以下循環(huán):

4)定義最大循環(huán)次數(shù);

5)如果sp類的best屬性通過(guò)方法solved(),退出循環(huán);

6)否則調(diào)用方法cycle();

7)算法結(jié)束.

分析上述算法可以看出,終止循環(huán)的兩個(gè)條件是:①完成預(yù)先設(shè)定的最大進(jìn)化代數(shù);②種群中的最優(yōu)個(gè)體經(jīng)受solved()的考驗(yàn).算法中有幾個(gè)可調(diào)參數(shù),循環(huán)最大次數(shù)為1 000;種群大小一般設(shè)置在10～100;變異算子的概率一般在0.001～0.1之間;倒串算子、IS插串算子和 RIS插串算子的概率一般在0.01～0.2之間;單點(diǎn)重組和兩點(diǎn)重組算子的概率一般在0.2～0.7之間;基因變換和基因變換算子的概率一般也在0.01～0.2之間.

根據(jù)以上測(cè)試模型自動(dòng)生成系統(tǒng)算法設(shè)計(jì),可以根據(jù)制導(dǎo)電子箱的輸入輸出數(shù)據(jù)生成其測(cè)試需求.測(cè)試需求分兩部分內(nèi)容:測(cè)試信號(hào)和測(cè)試方法.

假設(shè)測(cè)試資源不受限制的情況下得到如下測(cè)試模型:

對(duì)該模型可作以下解讀:各個(gè)染色體的第一個(gè)終結(jié)符集合中元素代表系統(tǒng)所需要的測(cè)試信號(hào),后半部分的數(shù)字代表信號(hào)模型的各個(gè)參數(shù),根據(jù)上述結(jié)果可以得知:制導(dǎo)電子箱所需信號(hào)集合為{正弦信號(hào),常值信號(hào),串行數(shù)字信號(hào),噪聲信號(hào)};測(cè)試方法就是分別利用求峰谷值得到正弦信號(hào)的最大最小值,對(duì)常值信號(hào)求平均值得到信號(hào)的平均值,對(duì)數(shù)字信號(hào)進(jìn)行計(jì)數(shù)來(lái)得到時(shí)間量,對(duì)編碼信號(hào)進(jìn)行解碼得到原信號(hào).

根據(jù)解碼得到的結(jié)果可以看出,通過(guò)算法得到的測(cè)試信號(hào),就測(cè)試信號(hào)而言比制導(dǎo)電子箱所需要的信號(hào)多出一個(gè)噪聲信號(hào),這是因?yàn)樵谒惴ㄌ幚磉^(guò)程中,把常值信號(hào)看作是帶有噪聲的信號(hào),這樣在測(cè)試需求信號(hào)中就有相應(yīng)的體現(xiàn).

4 結(jié)束語(yǔ)

本文借鑒美國(guó)TYX公司的自動(dòng)測(cè)試系統(tǒng)軟件產(chǎn)品PAWS中測(cè)試需求建立方法以及國(guó)內(nèi)相關(guān)專家已取得的成果,提出了基于基因表達(dá)式編程算法的裝備測(cè)試需求自動(dòng)生成方法并進(jìn)行了系統(tǒng)實(shí)現(xiàn).實(shí)驗(yàn)結(jié)果表明了該方法的有效性,為下一步實(shí)現(xiàn)基于模型的自動(dòng)測(cè)試系統(tǒng)提供了基礎(chǔ).但此方法目前還存在一些不足之處,比如在函數(shù)符集合和終止符的設(shè)計(jì)上不夠全面,缺乏對(duì)測(cè)試模型的自動(dòng)評(píng)價(jià)體系等,這些都是需要進(jìn)一步研究的問(wèn)題.

[1] 張寶珍.美國(guó)空軍第一種通用自動(dòng)測(cè)試系統(tǒng)VDATS[J].航空維修與工程,2010(1):31-32.

Zhang Baozhen.VDATS,the first versatile depot ATS of USAF[J].Aviation Maintenance&Engineering,2010(1):31-32.(in Chinese)

[2] 李行善.自動(dòng)測(cè)試系統(tǒng)集成技術(shù)[M].北京:北京航空航天大學(xué)出版社,2004.

[3] Yuan Mei,W ang Dahai.LXIC class device design in LAN based ATE[J].IEEE International Conference on Industrial In formatics,2006:995-999.

[4] 張瑋.基于模型化思想的模擬電路ATE測(cè)試與診斷技術(shù)研究[D].北京:航空航天大學(xué),2003.

[5] Kevin Coggins.VDATS and the DoD ATS Framework[J].IEEE Autotestcon,2008(9):8-11.

[6] IEEE Standards Coordinating Comm ittee 20(IEEE SCC20).IEEE Std 1671.IEEE Trial-Use Standard for Automatic Test Markup Language(ATM L)[EB/OL].[2006-11-26].http://standards.ieee.org.

[7] 邊澤強(qiáng),孟曉風(fēng).測(cè)試需求和資源的標(biāo)準(zhǔn)化描述模型[J].電子測(cè)量技術(shù),2008,31(7):111-114.

Bian Zeqiang,Meng Xiaofeng.Standard test requestand resourcemodel in flexible test system[J].Electronic Measurement Technology,2008,31(7):111-114.(in Chinese)

[8] 王學(xué)奇,肖明清.基于XM L的測(cè)試需求描述及其實(shí)現(xiàn)[J].計(jì)算機(jī)工程與應(yīng)用,2005,23(2):112-114,172.

Wang Xueqi,Xiao Mingqing.XML-based representation and realization for test requirement[J].Computer Engineering and App lication,2005,23(2):112-114,172.(in Chinese)

[9] 劉金寧,張大勇.面向UUT問(wèn)題域的測(cè)試需求分析方法研究[J].工業(yè)自動(dòng)化儀表,2008,29(1):12-14.

Liu Jinning,Zhang Dayong.Research on analysismethod for UUT prob lem domain-oriented test demand[J].Process Automation Instrumentation,2008,29(1):12-14.(in Chinese)

[10] Candida Ferreira.Gene expression programm ing:a new adaptive algorithm for solving problems[J].Comp lex Systems,2001,13(2):87-129.

[11] Candida Ferreira.Gene exp ression programm ing:a new adaptive algorithm for solving p roblems[J].Comp lex Systems,2001,13(2):87-129.

[12] 左 吉力.基因表達(dá)式編程核心技術(shù)研究[D].成都:四川大學(xué),2004.

[13] IEEE Standards Coordinating Committee 20(IEEE SCC20).IEEE Std 1641.IEEEStandard for Signaland Test Definition(STD)[EB/OL].[2010-05-19].http://standards.ieee.org.

[14] 李太勇,唐常杰.基于小生境基因表達(dá)式編程的多模函數(shù)優(yōu)化[J].四川大學(xué)學(xué)報(bào)(工程科學(xué)版),2009,4(2):162-166.

Li Taiyong,Tang Changjie.Mu ltimodal function op timization based on nichegeneexpression programm ing[J].Journal of Sichuan University(Engineering Science Edition),2009,4(2):162-166.

[15] De Jong K A.Ananalysis of the behavior of a class of genetic adap tive systems[D].Michigan:University of Michigan,1975.

[16] Goldberg D E,Richardson J.Genetic algorithms with sharing for multimodal function optimization[C].Genetic Algorithms and Their Applications:Proceedings of the Second International Con ference on Genetic Algorithm s,1987:41-49.