吳新鋒，段 然，周 虎，許 琦

(1.北京航天自動控制研究所， 北京 100854； 2.宇航智能控制技術(shù)國家級重點實驗室， 北京 100854)

隨著航空航天等領(lǐng)域?qū)ρb備故障診斷能力的要求不斷提高，裝備測試性設(shè)計與優(yōu)化在裝備設(shè)計過程中逐漸得到高度重視，如何從包含大量測試的完備測試集中找出最優(yōu)的測試子集，使其在滿足既定測試性指標(biāo)的要求下，測試代價最小，解決這一NP難問題，文獻(xiàn)[1]根據(jù)相關(guān)性矩陣通過布爾邏輯運算的方法選擇最優(yōu)測試，但當(dāng)系統(tǒng)規(guī)模很大時，該方法顯然難以進(jìn)行；文獻(xiàn)[2]將測試優(yōu)化問題看作0-1規(guī)劃問題，運用隱枚舉法求解，也不適用于大型系統(tǒng)；文獻(xiàn)[3-6]使用遺傳算法、螢火蟲算法、量子算法、模擬退火算法的改進(jìn)或融合來解決測試選擇問題，取得了一定的效果。文中將遺傳算法與二進(jìn)制粒子群算法結(jié)合，遺傳算法(Genetic Algorithm，GA)具有良好的全局及局部搜索能力，但易產(chǎn)生早熟收斂現(xiàn)象，且搜索效率低、收斂慢，二進(jìn)制粒子群(Binary Particle Swarm Optimization，BPSO)算法搜索效率高，但算法不穩(wěn)定、易陷入局部最優(yōu)，結(jié)合二者優(yōu)點并適應(yīng)性改進(jìn)，提出改進(jìn)粒子群遺傳算法(Improved Binary Particle Swarm Optimization Genetic Algorithm,IBPSOG- A)，最后以超外差接收機(jī)系統(tǒng)為例進(jìn)行多次測試優(yōu)化，驗證該算法的有效性。

1 測試優(yōu)選問題建模

1.1 故障-測試相關(guān)性矩陣

故障-測試相關(guān)性矩陣[7]是通過故障的可達(dá)性分析，或者運用測試性建模與分析軟件建立測試性模型，通過軟件自動生成。故障-測試相關(guān)性矩陣是描述故障影響的信號集與測試測量的信號集之間相關(guān)關(guān)系的矩陣，如式(1)。若故障fi與測試tj的信號集有交集，稱測試tj能檢測到故障fi，則dij=1(i=1,2,…,m;j=1,2,…,n)，否則dij=0。

(1)

1.2 測試性參數(shù)計算

測試性參數(shù)主要包括故障檢測率(Fault Detection Rate，F(xiàn)DR)、故障隔離率(Fault Isolation Rate，F(xiàn)IR)及虛警率(Fault Alarm Rate，F(xiàn)AR)等，本文認(rèn)為測試結(jié)果是可靠的，因此只考慮故障檢測率與隔離率。

1) 故障檢測率

故障檢測率一般是指在規(guī)定時間內(nèi)，用規(guī)定的方法正確檢測到的故障數(shù)ND與被測單元發(fā)生的故障總數(shù)NT之比。若已知故障的先驗概率λi，則故障檢測率可表示為

(2)

式中:λDi為檢測到的故障集FD中的第i個故障的先驗概率；λk為所有的故障集F中第k個故障的先驗概率。

定義：能檢測到fi的測試集為Tfi={tj|dij=1,j=1,2,…,n}，測試tj能檢測到的故障集為Ftj={fi|dij=1,i=1,2,…,m}。

根據(jù)故障-測試相關(guān)性矩陣求故障檢測率時，式(2)中能檢測到的故障集合FD={fi|Tfi≠Φ,i=1,2,…,m}。

2) 故障隔離率

故障隔離率一般是指在規(guī)定時間內(nèi)，用規(guī)定的方法正確隔離到不大于規(guī)定等級L的可更換單元數(shù)的故障數(shù)NI與同一時間內(nèi)檢測到的故障數(shù)ND之比。同樣用先驗概率可表示為

(3)

式中：λDk為檢測到的故障集FD中的第k個故障的先驗概率；λIi為可隔離到不大于規(guī)定可更換單元數(shù)的故障組成的集合中第i個故障的先驗概率。

任意兩個故障fi、fk可以被隔離的條件是它們對應(yīng)的測試集有不同的測試，用數(shù)學(xué)語言表達(dá)就是

(4)

式中，“⊕”表示集合的“異或”運算。

定義：故障fi所在的模糊組為Nfi={fk|Tfi⊕Tfk=Φ,k=1,2,…,m}，Nfi中故障數(shù)為Ni。若Ni≤L，則稱fi能被隔離到不大于規(guī)定等級L。

根據(jù)故障-測試相關(guān)性矩陣求故障檢測率時，式(3)中能隔離到規(guī)定等級L的故障集FI={fi|Ni≤L,i=1,2,…,m}。

1.3 測試優(yōu)選模型

測試優(yōu)選是從原完備測試集(測試集能滿足測試性參數(shù)指標(biāo))中找到一個測試子集，使其在滿足測試性參數(shù)指標(biāo)的前提下測試代價最小。測試代價一般指除測試可靠性以外的測試時間、測試費用、測試復(fù)雜度及其他的消耗等。

設(shè)原測試集T中每個測試的代價為cj，備選測試集Ts?T，則測試代價為

(5)

若測試性參數(shù)指標(biāo)為：故障檢測率FDRSET，隔離率FIRSET，則測試優(yōu)選問題即為式(6)的求帶約束的極小值問題

(6)

對式(6)進(jìn)行處理，將帶約束的極小值問題轉(zhuǎn)化為無約束的極大值問題，其指標(biāo)函數(shù)為

(7)

式中，α、β、γ均為正整數(shù)，通過調(diào)節(jié)相應(yīng)參數(shù)的大小進(jìn)而調(diào)節(jié)指標(biāo)函數(shù)對相關(guān)量的敏感程度，但取值太大容易造成振蕩。

2 IBPSOGA算法

IBPSOGA算法是在GA的框架基礎(chǔ)上，對測試集采用二進(jìn)制編碼(某一位上“1”表示選擇該測試，“0”表示不選該測試)，對GA的遺傳操作：選擇、交叉、變異，分別進(jìn)行改進(jìn)得到的一種用于測試優(yōu)選的算法。

2.1 BPSO算法

PSO算法是在1995年由美國社會心理學(xué)家James Kennedy和電氣工程師Russell Eberhart受到鳥類尋找棲息地等大量群體行為的啟發(fā)，提出的一種基于群體進(jìn)化的隨機(jī)優(yōu)化技術(shù)，其基本思想是粒子飛向“個體最優(yōu)”與“群體最優(yōu)”。PSO的進(jìn)化公式為

(8)

式中，vis、xis分別為第i個粒子的速度、位置的第s維分量，學(xué)習(xí)因子c1、c2為非負(fù)常數(shù)，rand1、rand2為[0,1]上相互獨立的隨機(jī)數(shù)。

針對離散優(yōu)化問題，后來又提出了BPSO，和PSO的區(qū)別在于粒子所處位置的各維分量只能取{0,1}，速度不加限制，位置更新時將速度映射為概率，根據(jù)該概率來決定位置的更新。位置更新策略如式(9)

(9)

式中，rand為隨機(jī)產(chǎn)生的[0,1]之間的隨機(jī)數(shù)。

另外，為了平衡粒子群的全局搜索能力與局部搜索能力，使其進(jìn)化前期具有較好的全局搜索能力，進(jìn)化后期接近最優(yōu)解時具有較好的局部搜索能力，本文對式(8)的速度更新采用線性遞減的慣性權(quán)重因子，速度更新公式如下

(10)

式中，gen、maxgen分別為當(dāng)前迭代次數(shù)和最大迭代次數(shù)。

2.2 GA改進(jìn)策略

GA是受到自然界生物優(yōu)勝劣汰、適者生存的遺傳進(jìn)化規(guī)律啟發(fā)而提出的一種隨機(jī)優(yōu)化搜索方法，直接以目標(biāo)函數(shù)作為搜索信息，采用概率化的搜索方法，自適應(yīng)地調(diào)整搜索方向，且算法具有內(nèi)在的并行性計算特點，可適合大規(guī)模復(fù)雜問題的優(yōu)化[8]。GA的遺傳操作主要有選擇、交叉與變異，下面分別針對這三項操作進(jìn)行改進(jìn)。

1) 選擇

根據(jù)各染色體適應(yīng)度函數(shù)占整個種群適應(yīng)度函數(shù)和的比例，隨機(jī)選擇產(chǎn)生下一代種群。該操作模擬自然界適者生存的規(guī)律，適應(yīng)度大的個體直接復(fù)制成為下一代個體，這樣就有很大概率存在適應(yīng)度大的個體會被重復(fù)選擇，導(dǎo)致種群多樣性降低，而且父代個體直接成為子代個體，個體的位置并沒有變化，這樣搜索效率也會降低。

因此針對這些缺點，提出利用BPSO算法對父代種群進(jìn)行成熟來產(chǎn)生下一代種群，這樣適應(yīng)度小的個體會朝著適應(yīng)度大的個體方向移動，加快了搜索速度，同時避免了個體復(fù)制導(dǎo)致的種群多樣性降低。

2) 交叉

隨機(jī)選擇兩個染色體，按照交叉概率，隨機(jī)選擇交叉位置進(jìn)行同位置交叉，常見的有單點交叉、多點交叉等。交叉操作是遺傳算法實現(xiàn)全局搜索的重要手段，但在遺傳進(jìn)化后期，會有很多相似度很高的染色體，因此就會產(chǎn)生很多無效的交叉操作，如圖1所示，染色體A、B的1～4位及第8位相同，那么這些位置進(jìn)行交叉操作沒有改變?nèi)旧w的編碼，是無效交叉，只有染色體上基因不同的位置進(jìn)行交叉才能產(chǎn)生新個體。

圖1 無效的交叉操作

為了避免這種無效交叉，提高搜索效率，首先提取待交叉的兩個染色體上基因不同的位置，設(shè)基因不同的位置的集合為P，不同的位置個數(shù)即集合P的元素個數(shù)為Np，則隨機(jī)選擇集合P中的「Np/2?個位置進(jìn)行交叉，“「x?”表示x向上取整。若P為空集即Np=0，則不交叉。

3) 變異

隨機(jī)選擇一個染色體，隨機(jī)選擇該染色體的一個基因位，按照變異概率進(jìn)行變異，該操作是遺傳算法實現(xiàn)局部搜索的重要手段。如果種群中某一基因位很單一(0占大比例或1占大比例)，變異概率一般也很小，可能該基因位會在進(jìn)化過程中越來越單一，或者變異操作的時候會向更單一的方向變異，這樣就會導(dǎo)致種群多樣性的降低，為了維持種群多樣性，提出“基因系數(shù)”的概念，不同基因位根據(jù)其“基因系數(shù)”動態(tài)調(diào)整自身的變異概率，而且由當(dāng)前基因位的基因來決定是否變異，以避免基因向更單一的方向變異。

定義：在一個種群中，對于第j個基因位，“1”所占比例為p1j，“0”所占比例為p0j，p1j+p0j=1，則基因系數(shù)定義為“1”的信息熵與“0”的信息熵之和，為

GC(j)=-p1jlog2p1j-p0jlog2p0j

(11)

式(11)中，當(dāng)pij=0時，約定log2pij=0(i=0,1)。

當(dāng)|p1j-p0j|越小，基因系數(shù)越大，物種中該基因多樣性維持越好，二者相等時，GC=1，此時基因系數(shù)最大；|p1j-p0j|越大，基因系數(shù)越小，物種中該基因多樣性維持越差，當(dāng)全部是“1”或“0”時，基因系數(shù)達(dá)到最小值0。為了維持基因的多樣性，在基因系數(shù)越大時，使變異概率越小，基因系數(shù)越小時，變異概率越大，提出式(12)的基于基因系數(shù)動態(tài)調(diào)整的變異概率

(12)

式中，pm0為變異概率，一般取0.01～0.1，變異概率動態(tài)變化通過K來調(diào)節(jié)，K∈[1,m]，因此變異概率在區(qū)間內(nèi)按指數(shù)變化，有效調(diào)節(jié)基因系數(shù)，來維持基因多樣性。

2.3 IBPSOGA實現(xiàn)流程

式(7)的指標(biāo)函數(shù)是測試代價的單調(diào)減函數(shù)，是故障檢測率、隔離率的單調(diào)增函數(shù)，因此直接將其作為種群的適應(yīng)度函數(shù)，IBPSOGA實現(xiàn)流程如下：

1) 參數(shù)初始化：初始化學(xué)習(xí)因子c1、c2，慣性權(quán)重ωmax、ωmin，交叉概率pc，變異概率pm及系數(shù)m，種群大小Popsize，最大迭代次數(shù)maxgen；

2) 種群初始化：對測試集采用二進(jìn)制編碼，隨機(jī)生成一個大小為Popsize的種群，隨機(jī)生成各粒子的速度；

3) BPSO成熟：首先計算種群適應(yīng)度，獲得個體極值和種群極值，然后采用帶線性遞減慣性權(quán)重因子的BPSO對種群進(jìn)行成熟，更新各粒子的位置和速度；

4) 交叉：進(jìn)行Popsize次交叉操作，每次交叉隨機(jī)選擇兩個染色體，提取二者基因不同的基因位，按照交叉概率判斷是否交叉，若交叉則在不同的基因位集合中隨機(jī)選擇「Np/2?個基因位進(jìn)行交叉，否則該次不交叉；

5) 變異：進(jìn)行Popsize次變異操作，每次變異隨機(jī)選擇一個染色體，隨機(jī)選擇一個基因位，判斷若p1j>p0j且當(dāng)前基因位為0，或者p1j

6) 計算種群適應(yīng)度，尋找種群極值，判斷若種群極值連續(xù)N次未變化則結(jié)束迭代，輸出種群最優(yōu)的個體，否則返回第(3)步繼續(xù)迭代。

3 算法驗證

通過對典型實例超外差接收機(jī)系統(tǒng)[9]進(jìn)行測試優(yōu)選，來驗證IBPSOGA的有效性。超外差接收機(jī)系統(tǒng)有22個故障模式，36個測試，各個測試的代價均相同，設(shè)為單位1。測試性參數(shù)指標(biāo)要求FDRSET≥0.95，F(xiàn)IRSET≥0.95，該系統(tǒng)的故障-測試相關(guān)性矩陣及各故障模式的故障率如表1所示。

對于上述超外差接收機(jī)的測試優(yōu)選，設(shè)置參數(shù)如下：種群大小Popsize=30，交叉概率pc=0.8，變異概率pm=0.05，變異概率調(diào)節(jié)參數(shù)m=e，二進(jìn)制粒子群學(xué)習(xí)因子c1=0.2，c2=0.2，慣性權(quán)重wmax=0.9，wmin=0.4，最大迭代次數(shù)maxgen=200，若種群最優(yōu)適應(yīng)度連續(xù)30次未變化則迭代結(jié)束。種群適應(yīng)度函數(shù)中α= 4，β=2，γ=2.

迭代結(jié)束后，得到的優(yōu)化結(jié)果是[0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,1,0,0,1,1,0,1,0,0]，即選擇的測試為[t8,t26,t28,t31,t32,t34]，此時故障檢測率FDR=96.86%，隔離率FIR=96.57%，測試代價為6，種群適應(yīng)度函數(shù)迭代曲線如圖2所示，種群最優(yōu)適應(yīng)度在第24步達(dá)到全局最優(yōu)。

圖2 種群適應(yīng)度迭代曲線

考慮到種群初始化的隨機(jī)性及算法的隨機(jī)性，對該算例進(jìn)行100次測試優(yōu)選，并且使用與IBPSOGA優(yōu)化時相同的優(yōu)化參數(shù)、種群大小、最大迭代次數(shù)、迭代結(jié)束條件及適應(yīng)度函數(shù)，分別運用標(biāo)準(zhǔn)的GA和BPSO算法對該算例進(jìn)行測試優(yōu)選，得到100次優(yōu)化結(jié)果中各代價優(yōu)化結(jié)果出現(xiàn)的次數(shù)如表2所示，計算到達(dá)最終優(yōu)化結(jié)果的平均迭代次數(shù)，BPSO是32.75，GA是39.93，IBPSOGA是39.91。

表1 故障-測試相關(guān)性矩陣及故障率

表2 各算法100次優(yōu)化優(yōu)化結(jié)果對比

從表2中可以看到IBPSOGA在100次優(yōu)化結(jié)果中有69次收斂到最優(yōu)代價6，遠(yuǎn)大于BPSO與GA收斂到6的次數(shù)，而且相對BPSO與GA到達(dá)最終優(yōu)化結(jié)果的平均迭代次數(shù)基本沒有增加，說明本文提出的IBPSOGA算法可以以較大概率收斂于全局最優(yōu)解，所以以GA為框架，結(jié)合BPSO針對GA遺傳操作的改進(jìn)是有效的。

而針對超外差接收機(jī)這個實例，文獻(xiàn)[3]利用改進(jìn)遺傳模擬退火算法得到最優(yōu)代價為9，文獻(xiàn)[4]利用量子遺傳算法得到最優(yōu)結(jié)果為10，文獻(xiàn)[5]利用離散螢火蟲算法得到最優(yōu)代價為12，因此采用IBPSOGA能獲得更小的測試代價，而且有較大的成功概率。

4 結(jié)論

對基于故障-測試相關(guān)性矩陣的測試優(yōu)選問題進(jìn)行了建模，提出在GA框架下結(jié)合BPSO對標(biāo)準(zhǔn)GA的選擇、交叉、變異操作進(jìn)行改進(jìn)，采用帶線性遞減慣性權(quán)重因子的BPSO代替選擇操作，交叉操作中隨機(jī)選擇不同的基因位進(jìn)行交叉，以減少無效交叉，變異操作中提出基因系數(shù)的概念，不同的基因位采用動態(tài)變化的變異概率維持種群的多樣性，盡量避免早熟收斂現(xiàn)象。結(jié)合實例，運用IBPSOGA、標(biāo)準(zhǔn)GA、標(biāo)準(zhǔn)BPSO算法對優(yōu)化問題進(jìn)行求解，優(yōu)化結(jié)果表明，該算法能以較大概率搜索到全局最優(yōu)解，且尋優(yōu)迭代次數(shù)相對GA與BPSO基本不變，證明了IBPSOGA能更有效地解決測試優(yōu)化問題。