和聲搜索算法用于測試性建模的測點布局優化

叢 華，張 睿，劉遠宏，馮輔周+

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

0 引 言

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

和聲搜索算法是通過模擬音樂演奏原理來進行搜尋最優解[5,6]。該算法結構簡單，具有良好的結合性，在解決多變量優化問題上比傳統的遺傳算法有著較好的穩定性，求解全局最優解的能力更好，已在多變量多維度調度問題[7-10]上得到應用。

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

1 測點布局優化模型

1.1 測試性模型

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

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

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

1.2 故障-測試相關性矩陣

故障-測試相關性矩陣，即D矩陣，以此為解空間，尋求測試成本最低的最優測試方案，并且滿足系統所提出的測試性指標要求。

通常，D矩陣為布爾矩陣，能夠描述系統內各個故障模式與各測試點之間的關系。其數學模型可以用下述矩陣來表示，即

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

1.3 測試性指標參數

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

(1)

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

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

(2)

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

1.4 優化模型

(3)

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

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

2 改進和聲搜索算法的基本原理

2.1 基本和聲搜素算法

和聲搜索算法是由Geem等提出的一種新型啟發式全局優化算法[12]。該算法通過模擬音樂家憑借自己的經驗記憶在創作音樂時不斷進行音調的調節，以求得最為完美的和聲的過程來進行求解全局最優解。

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

2.2 改進和聲搜索算法

2.2.1 編碼

傳統和聲搜索算法中一個和聲中的各個音調變量是對應求解問題的自變量所取的數值，而基于D矩陣的測點布局優化問題中需要將和聲轉變為測點的選取情況。因此對各個測點進行編碼，生成n維的布爾數組，使和聲能夠表示測點是否選擇。當系統內可選測點數量為n，則和聲的長度為n，其中和聲中每個元素代表相應編碼測點的決策變量，當元素值取1時，表示該測點被選中，反之為0表示未被選中。

2.2.2 計算適應度

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

(4)

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

2.2.3 產生新和聲

其中

(5)

式中：η1,η2為隨機參數。

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

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

(6)

其中，k為本代的迭代次數，IRmax為即興創作概率的最大值，IRmin為即興創作概率的最小值，K為最大迭代次數。由于參數IR為概率值，取值范圍為(0,1)，所以IRmin=0.01,IRmax=0.99。則改進后產生新和聲的數學表達式為

其中

(7)

式中：η1,η2為隨機參數。

2.3 和聲搜索算法用于測點布局優化的優化流程

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

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

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

步驟4 根據HMCR、PAR及IR這3個控制參數，并采用記憶學習、音調微調及即興創作3種方式，生成新的和聲；

步驟5 更新和聲記憶庫，對新和聲進行判別：是否優于原和聲記憶庫中最差和聲;

步驟6 當迭代次數滿足最大迭代次數時，停止運行算法，否則重復步驟3和步驟4。

改進和聲算法的流程，如圖1所示。

圖1 改進和聲算法的流程

3 實例分析

為檢驗改進和聲搜索算法對于求解測點布局優化問題的優越性，以文獻[3]給出的某設備的故障-測試相關性矩陣為例，見表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]。與遺傳算法的優化結果進行對比實驗，算法中的相關參數見表2、表3。

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

表1 故障—測試相關性矩陣

表2 改進和聲搜索算法初始化參數

表3 遺傳算法初始化參數

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

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

圖2 求解時間對比

表4 平均求解時間對比結果

實驗二：對比算法穩定性

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

圖3 運行結果統計直方圖

4 結束語

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