基于AMCQPSO的測試流程優化方法研究

孫 健，孫欽蕾，李寶晨，連光耀，謝 穎

（1.軍械工程學院，河北 石家莊 050003；2.軍械技術研究所，河北 石家莊 050003）

0 引 言

測試性設計關系到裝備的研制、維修及保障工作，對其維修性、可靠性、可用性、戰備完好性、壽命周期費用及系統性能和安全都有直接或間接的影響[1]。其關鍵技術主要包括測試點的優選、測試流程的優化以及相關測試性參數的評估。由于與診斷效率及測試成本聯系緊密，測試流程的優化越來越受到人們的關注。

從數學角度來看，測試流程的優化問題屬于組合優化問題，目前主要解決方法有遺傳算法（genetic algorithm，GA）、動態規劃算法（dynamic programming，DP）和與或圖搜索（AND/OR graph search）算法。由于問題固有難度，現有算法的求解效率和精度都不盡如人意，尤其隨著裝備復雜程度的提高，集合規模的增大，迫切需要尋求新的有效算法，以獲得最優測試流程[2-3]。

為此，本文在量子粒子群（QPSO）算法的基礎上，提出了帶自適應變異的質心量子粒子群優化算法（centroid quantum particle swarm optimization with adaptive mutation，AMCQPSO），以更高的效率和更有效的手段實現測試流程的優化。

1 測試流程優化問題描述

測試流程的優化是指通過對系統的最優測試集中的各個測試進行合理的排序，以使整個測試時間最短、測試成本最低。

由于影響測試流程設計的因素非常多，在本文的研究中，選取其最主要因素。定義五元組（F，p，T，c，D）來對問題進行研究。其中 F=[f1，f2，…，fm]表示系統的故障模式集，p=[p（f0），p（f1），…，p（fm）]T表示系統各個故障模式的先驗概率集，Ts=[t1，t2，…，tn]表示經過優選得到的測試集，c=[c1，c2，…，cn]T表示綜合考慮時間、測試費用等的測試代價矢量，D表示故障模式-測試相關性矩陣[4]。

不同的測試順序對應不同的測試流程，并最終以二元診斷樹的形式體現，利用診斷樹可以得到隔離矩陣A，它的列為按照得到的順序排列后的各個測試，若測試tj用于隔離fi，則aij為1，否則為0。最終，測試成本可以表示為

因此，測試流程優化的過程就是運用智能優化算法構建合適的診斷樹，得到隔離矩陣A，使得測試成本Cost最少。

2 基于AMCQPSO的測試流程優化方法

基于上述分析，本文將測試流程優化問題轉換為測試集元素的排序問題，提出AMCQPSO算法，以實現測試流程的優化設計。

2.1 QPSO算法簡介

在標準的PSO算法中，粒子的狀態由位置和速度兩個因素決定，由于粒子的速度有限，因而其搜索空間也受限制，不能保證以概率1搜索到全局最優解。2004年，孫俊等人從量子力學的角度出發，在PSO模型的基礎上，提出了QPSO算法。該算法以DELTA勢阱為基礎，認為粒子具有量子行為，利用波函數φ（x，t）描述粒子狀態，通過求解薛定諤方程得到粒子在某點出現的概率密度函數，再利用Monte Carlo隨機模擬得到粒子的位置方程[5]。

式中：M——種群中粒子的數目；

d——粒子的維數；

u、φ——在[0，1]上均勻分布的隨機數；

mbest——種群中所有粒子的平均最好位置點；

Pi、Pg——粒子所經歷的最好位置和種群中所有粒子經歷的最好位置；

β——收縮擴張系數。

2.2 QPSO算法的改進

由于QPSO收斂速度快，若粒子群中的某一個粒子較早發現了一個局部最優位置，其他粒子在向它靠攏過程中并未發現更優位置，則會產生“早熟”現象而陷入局部最優。為此，從3方面對QPSO進行改進，提出了帶自適應變異的質心量子行為粒子群算法（AMCQPSO）。

2.2.1 質心粒子的構建

物理學上，在直角坐標系中，對由N個質點組成的質點系，其質心可表示為

由于質心的特殊性，其往往具有其他粒子所沒有的特性，更能體現全局性；因此，可以從粒子群的空間特征出發，為量子粒子群構建一個質心粒子。參考文獻[6]，將粒子的適應度值value（Pi）作為“質量”，對于規模為m，維數為n的粒子群，可得其質心X的位置為

在QPSO進化過程中，利用質心更新部分Pg，在保證群體多樣性的同時，可以加快收斂速度。

2.2.2 收縮擴張系數的自適應調節

由于收縮擴張系數β在QPSO中起著很重要的作用，它決定了算法的收斂性能及速度，因此有必要建立合適的系數調節機制。通常的方法是線性減少法，即

為了更好的提高算法的搜索范圍及速度，可以引入另一種方法——自適應調節機制[7]。首先，建立誤差函數ΔF

通過誤差函數，可以得到各個粒子與全局最優位置的接近程度。對于靠近最優位置的粒子，即ΔF小的粒子，β值應取大一些；對于遠離最優位置的粒子，即ΔF大的粒子，β值應取小一些。因此，令y=lg（ΔF），可以構建β的自適應調節函數

利用自適應調節機制控制系數β，能夠從一定程度上提高算法的收斂速度和全局搜索能力，較第一種線性遞減法具有更好的優勢。

2.2.3 變異因子的引入

由于種群在不斷進化過程中，個體間的差異逐漸減小，可以利用適應度方差σ2和聚集度h來表示種群當前的狀態[8]，表達式為

式中：N——種群的規模；

value（Xid）——在第d次進化下第i個粒子的適應度值；

f——歸一化因子。

適應度方差σ2反映了粒子群個體的聚集程度，σ2越小，表明個體間差異越小。

其中，分子表示第d次進化下的粒子與當前全局最優位置間的最大距離，分母表示在已進行的d次進化中粒子與其相應的全局最優位置的最大距離。聚集度h反映了個體間的分布情況，h越小，各粒子越靠近。

因此，隨著進化次數的增加，σ2趨于0，而h越小的時候，粒子群易陷入局部最優，出現“早熟”。為此，引入變異因子，以一定概率對各粒子極值添加擾動，具體步驟如下：

Step2根據式（8）和（9）分別計算適應度；

Step3計算變異概率p：

Step4產生 0～1的隨機數 rand（）；

Step5 比較 rand（）和 p。若 rand（）＜p，則對各粒子的歷史最優位置進行變異操作：

通過在一定條件下對粒子進行變異操作，有效地避免了粒子的“扎堆”現象，增加了其全局搜索能力，提高了效率。

2.3 基于AMCQPSO的測試流程優化方法的實現

2.3.1 粒子的編碼

粒子的維數為最優測試集中測試的個數n，粒子的規模為待隔離故障模式數m。定義粒子每一維的取值為0～1，根據解空間各維的數值進行排序，即為其所對應測試的順序。如對于一個5維粒子，結果為[0.3，2，-1，0.6，5]，則解空間為[2，4，1，3，5]，優化的測試流程為 T3→T1→T4→T2→T5。

2.3.2 適應度函數

設Testk為所確定的測試順序，則根據式（1），可知粒子的適應度函數為

由于適應度函數代表了測試成本，則算法的選取法則為 min（fitness）。

2.3.3 算法的實現步驟

Step1初始化種群規模m、維數n、各粒子位置Xi、歷史最優位置Pi、種群最優位置Pg及最大迭代次數 dmax，令 d=0；

Step2根據式（12）計算各粒子的適應度值；

Step3 更新 Pid、Pg；

Step4根據式（4）計算質心位置，并計算其適應度值 fitness（Pc）；

Step5 若 fitness（Pc）優于 fitness（Pg），則更新當前Pg=Pc，并更新當前適應度值最小的粒子的歷史最優Pkd=Pc；否則，進行下一步；

Step6根據式（2）、式（7）更新粒子的位置；

Step7根據式（8）、式（9）計算適應度方差 σ2和聚集度h，并由式（10）計算變異概率p；

Step8 生成 0～1 隨機數 rand（），若 rand（）＜p，則根據式（11）進行變異操作；否則，進行下一步；

Step9判斷粒子適應度是否達到收斂條件或d是否達到dmax。若達到二者中的一個，則跳至Step11；否則，跳至Step10；

Step10 d++，跳至 Step2；

Step11 輸出 Pg、fitness（Pg），對 Pg各維數值排序，設計出測試流程。

3 實例驗證

為考察算法的性能，本文從兩方面對AMCQPSO進行驗證：

3.1 算法的有效性

選取3個典型函數來求解最小值，其中f1（x）為單峰函數，用來測試算法的收斂速度；f2（x）、f3（x）為多峰函數，是典型的非線性多模態函數，具有廣泛的搜索空間、大量的局部極值點，用來測試算法的全局搜索能力。3種類型函數的相關參數見表1。

表1 3種典型函數的相關參數

分別運用QPSO算法和AMCQPSO算法，多次重復實驗取平均值，得到的結果如表2。

表2 實驗結果

從表2可以看出，較QPSO算法而言，AMCQPSO算法具有較好的收斂速度、求解精度及全局搜索能力。

3.2 算法的實用性

以文獻[9]中超外差接受系統為例，對其進行測試流程優化方法的研究。在其優選出的測試集為{T1，T2，T5，T6，T8，T11，T19，T20，T21，T24，T26，T27，T30，T33，T34}的前提下，分別用2種方法優化后的測試流程為：

（1）利用貪婪算法得到的測試流程為

T6→T33→T24→T21→T26→T1→T11→T2→T5→T8→T19→T20→T27→T30→T34

Cost=4.7931

（2）利用改進AO*算法得到的測試流程為

T30→T26→T34→T19→T6→T21→T27→T2→T1→T24→T20→T8→T5→T33→T11

Cost=4.6349

利用改進動態貪婪算法得到的最優測試集為

Tr={T4，T8，T6，T10，T14，T19，T21，T22，T23，T26，T27，T28，T30，T31，T34，T36}

在此基礎上，分別利用QPSO算法、混沌粒子群算法及本文所提出的AMCQPSO算法，優化得到的測試流程均為

T30→T34→T28→T27→T8→T31→T19→T26→T4→T21→T36→T10→T22→T14→T23

Cost=3.4435

由此可知，利用AMCQPSO能得到與QPSO和混沌粒子群相同的最優測試流程，但算法運行時間卻優于兩者，且測試成本僅為貪婪算法的71.84%、改進AO*算法的74.30%，具有較好的實用價值。

4 結束語

本文在QPSO的基礎上，提出AMCQPSO算法，利用質心粒子和對收縮擴張系數自適應調節提高了收斂速度，并通過添加變異因子有效地保持了種群的多樣性，使得算法能夠跳出局部最優，有效避免了“早熟”現象的發生。從實驗結果可以看出，AMCQPSO具有較好的收斂速度、求解精度及全局搜索能力，能夠實現測試流程的優化，為后續測試性設計的工作奠定了一定基礎。

[1]Gould E.Modeling it both ways：hybrid diagnostic modeling and its application to hierarchical system designs[C]∥ IEEE Autotestcon，2004：577-581.

[2]黃考利，連光耀.裝備測試性建模與應用[M].北京：兵器工業出版社，2010：16-19.

[3]石君友.測試性設計分析與驗證[M].北京：國防工業出版社，2011（4）：15-24.

[4]蔣榮華，王厚軍，龍兵.基于DPSO的改進AO*算法在大型復雜電子系統最優序貫測試中的應用[J].計算機學報，2008，31（10）：1836-1840.

[5]孫俊.量子行為粒子群優化算法研究[D].無錫：江南大學，2009（3）：12-29.

[6]汪永生，李均利.質心粒子群優化算法[J].計算機工程與應用，2011，47（3）：34-37.

[7]康燕，孫俊，須文波.具有量子行為的粒子群優化算法的參數選擇[J].計算機工程與應用，2007，43（23）：40-42.

[8]劉俊芳，高岳林.帶自適應變異的量子粒子群優化算法[J].計算機工程與應用，2011，47（3）：41-43.

[9]蘇永定.機電產品測試性輔助分析與決策相關技術研究[D].長沙：國防科技大學，2004.