基于AMCQPSO的測試流程優(yōu)化方法研究

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

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

0 引 言

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

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

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

1 測試流程優(yōu)化問題描述

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

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

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

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

2 基于AMCQPSO的測試流程優(yōu)化方法

基于上述分析，本文將測試流程優(yōu)化問題轉(zhuǎn)換為測試集元素的排序問題，提出AMCQPSO算法，以實現(xiàn)測試流程的優(yōu)化設(shè)計。

2.1 QPSO算法簡介

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

式中：M——種群中粒子的數(shù)目；

d——粒子的維數(shù)；

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

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

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

β——收縮擴張系數(shù)。

2.2 QPSO算法的改進

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

2.2.1 質(zhì)心粒子的構(gòu)建

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

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

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

2.2.2 收縮擴張系數(shù)的自適應(yīng)調(diào)節(jié)

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

為了更好的提高算法的搜索范圍及速度，可以引入另一種方法——自適應(yīng)調(diào)節(jié)機制[7]。首先，建立誤差函數(shù)ΔF

通過誤差函數(shù)，可以得到各個粒子與全局最優(yōu)位置的接近程度。對于靠近最優(yōu)位置的粒子，即ΔF小的粒子，β值應(yīng)取大一些；對于遠離最優(yōu)位置的粒子，即ΔF大的粒子，β值應(yīng)取小一些。因此，令y=lg（ΔF），可以構(gòu)建β的自適應(yīng)調(diào)節(jié)函數(shù)

利用自適應(yīng)調(diào)節(jié)機制控制系數(shù)β，能夠從一定程度上提高算法的收斂速度和全局搜索能力，較第一種線性遞減法具有更好的優(yōu)勢。

2.2.3 變異因子的引入

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

式中：N——種群的規(guī)模；

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

f——歸一化因子。

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

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

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

Step2根據(jù)式（8）和（9）分別計算適應(yīng)度；

Step3計算變異概率p：

Step4產(chǎn)生 0～1的隨機數(shù) rand（）；

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

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

2.3 基于AMCQPSO的測試流程優(yōu)化方法的實現(xiàn)

2.3.1 粒子的編碼

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

2.3.2 適應(yīng)度函數(shù)

設(shè)Testk為所確定的測試順序，則根據(jù)式（1），可知粒子的適應(yīng)度函數(shù)為

由于適應(yīng)度函數(shù)代表了測試成本，則算法的選取法則為 min（fitness）。

2.3.3 算法的實現(xiàn)步驟

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

Step2根據(jù)式（12）計算各粒子的適應(yīng)度值；

Step3 更新 Pid、Pg；

Step4根據(jù)式（4）計算質(zhì)心位置，并計算其適應(yīng)度值 fitness（Pc）；

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

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

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

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

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

Step10 d++，跳至 Step2；

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

3 實例驗證

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

3.1 算法的有效性

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

表1 3種典型函數(shù)的相關(guān)參數(shù)

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

表2 實驗結(jié)果

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

3.2 算法的實用性

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

（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

利用改進動態(tài)貪婪算法得到的最優(yōu)測試集為

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

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

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

Cost=3.4435

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

4 結(jié)束語

本文在QPSO的基礎(chǔ)上，提出AMCQPSO算法，利用質(zhì)心粒子和對收縮擴張系數(shù)自適應(yīng)調(diào)節(jié)提高了收斂速度，并通過添加變異因子有效地保持了種群的多樣性，使得算法能夠跳出局部最優(yōu)，有效避免了“早熟”現(xiàn)象的發(fā)生。從實驗結(jié)果可以看出，AMCQPSO具有較好的收斂速度、求解精度及全局搜索能力，能夠?qū)崿F(xiàn)測試流程的優(yōu)化，為后續(xù)測試性設(shè)計的工作奠定了一定基礎(chǔ)。

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

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

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

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

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

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

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

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

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