和聲搜索算法用于測試性建模的測點布局優(yōu)化

叢 華，張 睿，劉遠(yuǎn)宏，馮輔周+

(1.陸軍裝甲兵學(xué)院 機械工程系，北京 100072；2.武警工程大學(xué) 裝備工程學(xué)院，陜西 西安 710000)

0 引 言

測點布局優(yōu)化問題是屬于典型的集合覆蓋和多目標(biāo)組合優(yōu)化問題[1]。解決該問題通常是在系統(tǒng)測試性模型輸出的故障-測試相關(guān)性矩陣基礎(chǔ)上，引入遺傳算法、粒子群等優(yōu)化算法來實現(xiàn)。文獻(xiàn)[2-4]通過采用不同的現(xiàn)代進(jìn)化算法獲得系統(tǒng)最優(yōu)測試集合，具有較快的收斂速度，但是在使用不同算法求解該問題的穩(wěn)定性方面還有待提高。

和聲搜索算法是通過模擬音樂演奏原理來進(jìn)行搜尋最優(yōu)解[5,6]。該算法結(jié)構(gòu)簡單，具有良好的結(jié)合性，在解決多變量優(yōu)化問題上比傳統(tǒng)的遺傳算法有著較好的穩(wěn)定性，求解全局最優(yōu)解的能力更好，已在多變量多維度調(diào)度問題[7-10]上得到應(yīng)用。

目前，和聲搜索算法未在解決設(shè)備系統(tǒng)的測點布局優(yōu)化問題上得到應(yīng)用,所以本文將傳統(tǒng)和聲搜索算法進(jìn)行改進(jìn)。首先將和聲中每個位置進(jìn)行離散編碼，并對算法中“即興創(chuàng)作”這一學(xué)習(xí)策略進(jìn)行改進(jìn)，引入一個新的控制參數(shù)—即興創(chuàng)作概率(improvisation rate，IR)。該參數(shù)數(shù)值變化為指數(shù)遞增，通過參數(shù)前期變化為小而慢，增強全局尋優(yōu)能力；后期變化大而快，增強求解速度。最后，將改進(jìn)和聲搜索算法的優(yōu)化結(jié)果與遺傳算法的優(yōu)化結(jié)果加以對比，驗證其具有良好的優(yōu)化性能，能更加快速穩(wěn)定地獲得最優(yōu)測試集。

1 測點布局優(yōu)化模型

1.1 測試性模型

傳統(tǒng)的測點布局優(yōu)化是通過技術(shù)人員的大量工業(yè)實踐經(jīng)驗分析得到的，主觀意識較強，往往存在一些隱蔽性較強的故障無法檢測的現(xiàn)象，覆蓋率不高，而且效率較低，只能針對簡單系統(tǒng)進(jìn)行優(yōu)化分析。對于大型復(fù)雜的系統(tǒng)，通常采用建立測試性模型進(jìn)行測點布局優(yōu)化，能夠準(zhǔn)確地描述故障與測試之間的對應(yīng)關(guān)系，并且可以有效地減少工作量，提高優(yōu)化效率。

測試性模型采用有向圖的方式表示系統(tǒng)組成單元、故障、測試等要素間的相關(guān)關(guān)系。常用的測試性模型有信息流模型、混和診斷模型和多信號流圖模型。在所有的測試性模型中，系統(tǒng)模塊表示系統(tǒng)內(nèi)組成單元的結(jié)構(gòu)，故障模塊表示系統(tǒng)組成部件具有的多種故障，在系統(tǒng)組成部件內(nèi)添加多種測試點，連接線用于表示單元、故障和測試之間信號傳遞。

建立測試性模型，輸出故障-測試性相關(guān)矩陣。以故障-測試相關(guān)性矩陣為基礎(chǔ)，得到故障與測試之間的關(guān)系，從而分析不同測點選擇方案，可以更加快速地分析該系統(tǒng)的測試性，并對其作出評價。故障-測試相關(guān)性矩陣是解決基于測試性模型的測點布局優(yōu)化問題的核心。

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

故障-測試相關(guān)性矩陣，即D矩陣，以此為解空間，尋求測試成本最低的最優(yōu)測試方案，并且滿足系統(tǒng)所提出的測試性指標(biāo)要求。

通常，D矩陣為布爾矩陣，能夠描述系統(tǒng)內(nèi)各個故障模式與各測試點之間的關(guān)系。其數(shù)學(xué)模型可以用下述矩陣來表示，即

矩陣中的元素tij值取1時，表示第i個故障模式與第j個測試點具有相關(guān)性；反之，二者不相關(guān)。其中，行向量代表故障模式在各測試點上的響應(yīng)信息，列向量代表測試點所能檢測的故障信息。D矩陣有著建立系統(tǒng)故障與測試性能之間關(guān)系的能力，在D矩陣的基礎(chǔ)上計算系統(tǒng)的測試性指標(biāo)參數(shù)。

1.3 測試性指標(biāo)參數(shù)

測試性指標(biāo)參數(shù)用于評判系統(tǒng)的測試診斷能力，最優(yōu)測試集必須以滿足所規(guī)定的測試性指標(biāo)為前提，常用的測試性指標(biāo)有故障檢測率和故障隔離率。測點布局優(yōu)化問題中，當(dāng)D矩陣中存在某一行中元素不全為零，則該行對應(yīng)的故障為可檢測故障，所有可檢測故障組成可檢測故障集，即FD。故障檢測率的定義請參見文獻(xiàn)[11]，則當(dāng)考慮故障率時，故障檢測率的計算公式如下

(1)

式中：λi第i個故障的先驗概率；FD為可檢測故障集；F為所有故障模式集。

如果存在相同的兩行，則這兩行所對應(yīng)的故障不能隔離，否則能夠進(jìn)行故障隔離，所有可隔離故障組成可隔離故障集，即FI。故障隔離率的定義請參見文獻(xiàn)[11]，則當(dāng)考慮故障率時，故障隔離率的計算公式如下

(2)

式中：FI為可隔離故障集。

1.4 優(yōu)化模型

(3)

式中：T為所選測試集合，ti為測試集中元素，當(dāng)取值為1時，該測試點被選中；ci為第i個測點的測試成本。

通過測試性模型所獲得的D矩陣往往矩陣維數(shù)較大，不同于簡單系統(tǒng)的D矩陣。對于簡單系統(tǒng)以D矩陣為解空間，維數(shù)相對較少，有時通過窮舉法就可以直接得到最優(yōu)測試集，但是大型復(fù)雜系統(tǒng)來說，如果使用窮舉法求解計算量是巨大的，并且求解效率較低。所以通常借助優(yōu)化算法確定最優(yōu)測試集，文中采用和聲搜索算法進(jìn)行求解，縮短了搜索時間并且提高了搜索效率。

2 改進(jìn)和聲搜索算法的基本原理

2.1 基本和聲搜素算法

和聲搜索算法是由Geem等提出的一種新型啟發(fā)式全局優(yōu)化算法[12]。該算法通過模擬音樂家憑借自己的經(jīng)驗記憶在創(chuàng)作音樂時不斷進(jìn)行音調(diào)的調(diào)節(jié)，以求得最為完美的和聲的過程來進(jìn)行求解全局最優(yōu)解。

算法首先隨機產(chǎn)生一個具有HMS(harmony memory size)個和聲的和聲記憶庫，其中和聲代表可行性解，并對每個和聲進(jìn)行適應(yīng)度計算，用于最終篩選最優(yōu)和聲。然后，模擬音樂創(chuàng)作中3個步驟，即記憶學(xué)習(xí)、微調(diào)音調(diào)、即興創(chuàng)作，產(chǎn)生新的和聲Xnew，與記憶庫中的適應(yīng)度最差的進(jìn)行比較，若優(yōu)于原記憶庫中的和聲，則舊和聲會被取代。不斷重復(fù)上述過程更新和聲記憶庫，直到達(dá)到最大迭代次數(shù)為止，使得最終記憶庫中的和聲為最優(yōu)和聲。

2.2 改進(jìn)和聲搜索算法

2.2.1 編碼

傳統(tǒng)和聲搜索算法中一個和聲中的各個音調(diào)變量是對應(yīng)求解問題的自變量所取的數(shù)值，而基于D矩陣的測點布局優(yōu)化問題中需要將和聲轉(zhuǎn)變?yōu)闇y點的選取情況。因此對各個測點進(jìn)行編碼，生成n維的布爾數(shù)組，使和聲能夠表示測點是否選擇。當(dāng)系統(tǒng)內(nèi)可選測點數(shù)量為n，則和聲的長度為n，其中和聲中每個元素代表相應(yīng)編碼測點的決策變量，當(dāng)元素值取1時，表示該測點被選中，反之為0表示未被選中。

2.2.2 計算適應(yīng)度

和聲表示可選測試點中不同測點的組合選擇方案。通過特定和聲對應(yīng)的測點在故障-測試相關(guān)性矩陣中對應(yīng)的列向量重新構(gòu)建新的子矩陣，并計算該矩陣的測試性指標(biāo)參數(shù)。在原優(yōu)化數(shù)學(xué)模型中，測點成本最少為最優(yōu)目標(biāo)，故障檢測率和故障隔離率為約束條件。文中采用基于懲罰函數(shù)的處理方法，對不滿足約束條件的解進(jìn)行懲罰，反之對滿足約定條件的解不進(jìn)行懲罰，個體適應(yīng)度的數(shù)學(xué)公式如下所示

(4)

其中，α、β與ε均為常數(shù)，代表懲罰因數(shù)，通常取值為α=0.7,β=0.5,ε=0.5。

2.2.3 產(chǎn)生新和聲

其中

(5)

式中：η1,η2為隨機參數(shù)。

由于所優(yōu)化問題為二進(jìn)制問題，和聲中元素為備選測點選取的決策變量，取值范圍僅為0、1。而傳統(tǒng)和聲算法中和聲元素表示為數(shù)值變量，采用即興創(chuàng)作方式生產(chǎn)新和聲時，只需在變量取之范圍內(nèi)隨機生成，保證了所生和聲的多樣性，所以傳統(tǒng)的即興創(chuàng)作應(yīng)用于測點布局優(yōu)化問題上并無實際意義，不僅會減小測點選取的多樣性，而且會影響求解該問題的收斂速度，因此在即興創(chuàng)作方式中，引入一個即興創(chuàng)作概率IR，并能夠隨迭代次數(shù)增加呈指數(shù)遞增變化。

當(dāng)隨機參數(shù)η2小于IR時，新和聲音調(diào)取值為0，反之，取值為1。在算法運行初期，IR數(shù)值變化減慢且取值較小，能夠增加和聲的多樣性，有利于在全局范圍內(nèi)搜索到最優(yōu)解；而在運行后期時IR數(shù)值變化速率加快且取值較大，能夠加快搜索速度，有助于增加算法的收斂性，參考文獻(xiàn)[13]中給出了IR的指數(shù)遞增變化表達(dá)式，可得IR計算公式如下所示

(6)

其中，k為本代的迭代次數(shù)，IRmax為即興創(chuàng)作概率的最大值，IRmin為即興創(chuàng)作概率的最小值，K為最大迭代次數(shù)。由于參數(shù)IR為概率值，取值范圍為(0,1)，所以IRmin=0.01,IRmax=0.99。則改進(jìn)后產(chǎn)生新和聲的數(shù)學(xué)表達(dá)式為

其中

(7)

式中：η1,η2為隨機參數(shù)。

2.3 和聲搜索算法用于測點布局優(yōu)化的優(yōu)化流程

步驟1 初始化和聲搜索算法各個控制參數(shù)，即確定和聲記憶庫大小HMS、記憶庫學(xué)習(xí)概率HMCR、音調(diào)微調(diào)概率PAR以及最大迭代次數(shù)K；

步驟2 依據(jù)故障-測試相關(guān)性矩陣中測試數(shù)量的大小，確定每個和聲的長度，并初始化隨機生成和聲記憶庫；

步驟3 計算本記憶庫中各個和聲所對應(yīng)的測試集的故障檢測率、故障隔離率和測點數(shù)目，然后計算求得各和聲的適應(yīng)度，作為擇優(yōu)依據(jù)；

步驟4 根據(jù)HMCR、PAR及IR這3個控制參數(shù)，并采用記憶學(xué)習(xí)、音調(diào)微調(diào)及即興創(chuàng)作3種方式，生成新的和聲；

步驟5 更新和聲記憶庫，對新和聲進(jìn)行判別：是否優(yōu)于原和聲記憶庫中最差和聲;

步驟6 當(dāng)?shù)螖?shù)滿足最大迭代次數(shù)時，停止運行算法，否則重復(fù)步驟3和步驟4。

改進(jìn)和聲算法的流程，如圖1所示。

圖1 改進(jìn)和聲算法的流程

3 實例分析

為檢驗改進(jìn)和聲搜索算法對于求解測點布局優(yōu)化問題的優(yōu)越性，以文獻(xiàn)[3]給出的某設(shè)備的故障-測試相關(guān)性矩陣為例，見表1，其中故障源有15種，備選測試點有20個，每個測試點測試代價記作為1，各個故障模式的先驗故障率分別為10-3×[1.0,1.0,1.0,1.0,1.0,1.0,1.0,2.0,1.0,1.0,1.0,2.5,1.5,1.0,1.0]。與遺傳算法的優(yōu)化結(jié)果進(jìn)行對比實驗，算法中的相關(guān)參數(shù)見表2、表3。

根據(jù)文獻(xiàn)中所提出的測試性指標(biāo)要求：γFD≥95%,γFI≥80%。對可選的20個測試進(jìn)行編碼，依次為t1～t20,并建立規(guī)模為30個和聲的和聲記憶庫，依據(jù)所設(shè)置的3個控制參數(shù)進(jìn)行和聲搜索求解優(yōu)化。最終得到最優(yōu)測點選擇方案為{t1,t3,t4,t9,t10,t11,t12,t13,t14,t19,t20}，此時故障檢測率為96.6%，故障隔離率為86.4%，均滿足所提出的測試性指標(biāo)要求，最小的測試成本為11。采用遺傳算法進(jìn)行求解優(yōu)化，得到的最優(yōu)測點選擇方案與和聲搜索算法的結(jié)果一致，并進(jìn)行了求解速度與穩(wěn)定性的對比實驗。

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

表2 改進(jìn)和聲搜索算法初始化參數(shù)

表3 遺傳算法初始化參數(shù)

實驗一：對比算法求解速度

在處理器為Intel(R)Core(TM)i5 CPU 1.80 GHz的電腦上，使用Matlab編程，分別獨立運行100次，不同算法每一次的求解時間，如圖2所示。從圖2中在運行100次中遺傳算法的求解時間集中分布在(1，2)之間，要普遍大于改進(jìn)和聲搜索算法的求解時間。取100次求解時間的平均值，見表4。實驗對比結(jié)果表明改進(jìn)和聲搜索算法能夠更加快速地找到最優(yōu)解，所以能夠在短時間內(nèi)解決大型復(fù)雜系統(tǒng)的測點布局優(yōu)化問題。

圖2 求解時間對比

表4 平均求解時間對比結(jié)果

實驗二：對比算法穩(wěn)定性

為對比不同算法獲取最優(yōu)解的穩(wěn)定性，分別運行100次，各算法運行后得到最優(yōu)測試方案的統(tǒng)計直方圖如圖3所示。從中可以看出改進(jìn)后的和聲搜索算法所優(yōu)化結(jié)果中最優(yōu)測點選擇方案占總數(shù)的96%，遺傳算法占82%。算法穩(wěn)定性對比結(jié)果：改進(jìn)和聲搜索算法>遺傳算法。實驗結(jié)果表明改進(jìn)和聲搜索算法的獲取全局最優(yōu)解的能力更強，比遺傳算法陷入局部最優(yōu)解的概率更低，能夠有較大的概率獲取真實的最優(yōu)測試集。

圖3 運行結(jié)果統(tǒng)計直方圖

4 結(jié)束語

為解決遺傳算法求解測點布局優(yōu)化問題穩(wěn)定性不強，易陷入局部最優(yōu)解的問題，采用了和聲搜索算法，并針對所優(yōu)化問題為二進(jìn)制尋優(yōu)問題，對該算法進(jìn)行改進(jìn)，引入一個新的控制參數(shù)—即興創(chuàng)作概率。通過與遺傳算法優(yōu)化結(jié)果對比，得出改進(jìn)后的和聲搜索算法在尋求全局最優(yōu)解的能力上有者較好的能力，減小了陷入局部最優(yōu)解的概率，提高了搜索全局最優(yōu)解的穩(wěn)定性，并且求解搜尋速度較快，具有較好的綜合性能，驗證了對于求解測點布局優(yōu)化問題上的有效性，具有一定的工程應(yīng)用價值。