基于改進sPSO算法的測試數(shù)據(jù)自動生成方法研究

馮 菲，孫玫肖，劉文韜

（中國鐵道科學研究院 電子計算技術研究所，北京 100081）

軟件測試作為保證軟件質量、提高軟件可靠性的重要手段，其重要性已經被提升到前所未有的高度。自動化測試能夠有效地減輕測試人員的負擔并提高測試效率, 因此，對該領域的研究具有重要的理論價值和實際意義。而測試數(shù)據(jù)自動生成是自動化測試過程中十分重要的環(huán)節(jié)。

1 測試數(shù)據(jù)自動生成

測試數(shù)據(jù)選擇作為軟件測試中最核心的環(huán)節(jié)之一，為測試工作指明方向的同時也保障了軟件測試結果的有效性。以前生成測試數(shù)據(jù)最常采用的方法是向前核查和逆向回溯，整個過程由測試人員依據(jù)個人經驗手工完成，這不僅需要消耗大量的人力和時間，而且具有一定的局限性。為了實現(xiàn)測試數(shù)據(jù)自動生成，軟件測試中的語句覆蓋、路徑覆蓋等問題可以歸結為面向路徑的測試數(shù)據(jù)生成問題（以下簡稱為問題Q）。

問題Q的自動求解為軟件測試提供了新的思路，一方面大幅度提高了測試效率，之前需要手工完成的大量重復性勞動被程序的自動執(zhí)行所替代，另一方面也提高了測試質量，將測試過程中人為造成的錯誤有效減少，從而保證了測試過程的可靠性。

通過對問題Q的探索和研究，得到了一些具有理論和實際意義的方法，其中基于程序執(zhí)行的方法是重點，如隨機數(shù)法、Korel法、迭代松弛法、基于搜索的方法。

基于搜索的方法中以遺傳算法為核心算法的測試數(shù)據(jù)自動生成方法已被廣泛研究和改進，目前人們開始研究將其它搜索算法用于測試數(shù)據(jù)自動生成，以便找到更好的方法生成測試數(shù)據(jù)，本文以改進后的粒子群算法為核心算法實現(xiàn)測試數(shù)據(jù)自動生成。

2 粒子群算法及其改進

2.1 粒子群算法

1995年，兩位美國學者共同提出了粒子群算法(PSO)，他們受早期對鳥類群體行為研究結果的啟發(fā)，利用生物群體模型，并借用個體學習和文化傳遞的觀念，提出了PSO這一仿生類算法[1]。

基本粒子群算法描述如下：搜索空間維數(shù)記作D，粒子個數(shù)記作m，粒子i所在位置記作xi=(xi1, xi2,…, xiD)，i=1, 2,…, m。將 xi代入適應值函數(shù)得到相應的適應值，依據(jù)適應值評價xi的好壞。將粒子i的速度記作vi=(vi1, vi2,…, viD)T。記粒子i的個體最優(yōu)位置為Pi=(Pi1, Pi2,…, PiD)T，全局最優(yōu)位置為Pg=(Pg1, Pg2,…, PgD)T。每次進行迭代時，根據(jù)以下公式更新粒子的速度和位置：

其中，i=1, 2,…, m，d=1, 2,…, D；慣性因子ω≥0；學習因子r1和 r2是兩個隨機數(shù)，介于 [0,1]之間 ；vid∈ [－vmax, vmax]，vmax是常數(shù)。

2.2 簡化粒子群算法

基本粒子群算法中，同時包含了speed和position兩個概念，即迭代方程中同時存在vid和xid，在此基礎上對粒子群算法進行的改進大都比較復雜，無論是算法本身，算法的實現(xiàn)，還是證明其收斂性。

簡化粒子群優(yōu)化（sPSO）的提出，證明了粒子群的進化過程與粒子速度無關，去掉了粒子速度這一參數(shù)，將原來的二階方程降到了一階，并證明其收斂性，去掉vid簡化后的粒子群方程可表示為：

2.3 改進sPSO算法

2.3.1 進一步提高收斂速度

慣性權值作為粒子群算法中的一個重要參數(shù)，其主要作用是平衡整個粒子群的全局搜索能力和局部搜索能力，從而顯著提高粒子群優(yōu)化算法的收斂速度。因此，可以從優(yōu)化慣性權值ω入手，提高粒子群優(yōu)化算法的收斂速度。

當慣性權值較小時，如果粒子群算法能夠找到全局最優(yōu)解，它所經歷的搜索時間很短，即所有的粒子趨向于快速匯聚到一起[2]。當最優(yōu)解在初始搜索空間內，粒子群算法能夠迅速找到全局最優(yōu)解，否則將永遠找不到。當慣性權值較大時，粒子群算法更像全局搜索算法，總是探索新的區(qū)域，將需要更多的迭代來達到全局最優(yōu)，并且更有可能無法找到最優(yōu)解。

為了平衡整個粒子群的全局搜索能力和局部搜索能力，這里采用不同粒子分別隨機在給定范圍內對ω進行取值的方法，ω取值范圍是[0.6,1.3]，這種取值方法平衡了粒子群的全局搜索能力和局部搜索能力，也不會導致算法失效。

另外，學習因子c1和c2分別代表了粒子對自身的學習和粒子群中粒子之間的協(xié)作，反映了粒子與群體間其它粒子的信息交流。當c1較大時粒子更傾向于自身經驗信息；當c2較大時粒子更傾向于群體經驗信息，可能過早的收斂于局部最優(yōu)值。較理想的情況是，搜索初期，保證粒子的多樣性基礎上，使算法盡快進入局部搜索，以提高搜索效率；而搜索末期，粒子要保留一定的搜索能力，以擺脫局部極值的干擾。本文利用了線性策略動態(tài)調整學習因子，以獲得更好的適應值。c1從2.5線性遞減至0.5，c2從0.5線性遞增至2.5，實現(xiàn)在搜索初期對模型中的“認知部分”進行加強，而搜索后期則加強“社會部分”。

2.3.2 進一步提高收斂精度

sPSO算法一般前期收斂速度可觀,后期易陷入局部極值導致收斂速度驟降,影響其收斂精度，這種粒子群算法后期性能下降的狀態(tài)稱為“亞穩(wěn)定態(tài)”。針對亞穩(wěn)定態(tài)問題, 出現(xiàn)了如雜交PSO、變異PSO、模擬退火等添加極值擾動算子的策略，這些方法的共同特點是擾動亞穩(wěn)定態(tài)的粒子,迫使粒子進行下一輪搜索,相比在原地停滯不前更有可能找到全局最優(yōu)解。這里的觸發(fā)條件是進化停滯步數(shù)t，當t滿足需要進行擾動觸發(fā)條件時同時擾動Pi和 Pg，極值擾動算子為：

其中：ti是個體極值進化停滯步數(shù)，tg是全局極值進化停滯步數(shù)；Ti是個體極值停滯步數(shù)閾值，tg是全局極值停滯步數(shù)閾值；r3ti>Ti和r4tg>Tg為兩個帶條件的均勻隨機函數(shù)。將上面（4）式和（5）式分別代入公式（3）中，得到：

2.4 基于改進sPSO算法的測試數(shù)據(jù)自動生成模型

該模型主要包括測試環(huán)境構造、改進sPSO算法運行包和測試運行3個部分，各部分之間的關系如圖1所示。

圖1 基于改進sPSO算法的測試數(shù)據(jù)自動生成模型

2.4.1 測試環(huán)境構造

測試環(huán)境構造是整個系統(tǒng)的前提和基礎，首先利用程序控制流圖進行程序分析，選擇需要覆蓋的目標路徑，選擇參數(shù)、限定參數(shù)取值范圍，完成對分支函數(shù)以及適應值函數(shù)的構造，進行程序插裝。

程序插裝的前提是要保持被測程序原有的邏輯完整性和正確性，在此基礎上在程序中有針對性地插入一些探針，程序的執(zhí)行過程中通過探針獲取一些運行特征數(shù)據(jù)。通過對這些數(shù)據(jù)進行分析，從而獲得程序的控制流信息和數(shù)據(jù)流信息，還可以通過進一步分析得到邏輯覆蓋等動態(tài)信息。適應值函數(shù)是粒子群算法與具體應用問題的唯一交互，其構造的好壞直接影響到算法的搜索效率。這里采用“分支函數(shù)疊加法”構造測試路徑的適應值函數(shù)。

2.4.2 改進sPSO算法運行包

改進sPSO算法運行包是系統(tǒng)的中樞，在系統(tǒng)初始階段提取測試環(huán)境構造模塊中的參數(shù)及其范圍，初始化粒子位置，接收測試運行模塊的適應值信息，進行判斷后應用改進的sPSO算法更新粒子位置，直到找到全局最優(yōu)解。改進sPSO算法流程描述如下：

Step1：設置算法的相關參數(shù)，如粒子數(shù)目、粒子維度、搜索范圍、迭代次數(shù)上限等；

Step2：初始化粒子群，隨機生成粒子位置；

Step3：將當前位置寫入局部最優(yōu)集；

Step4：計算每個粒子的適應值；

Step5：找出全局最優(yōu)值；

Step6：更新全局最優(yōu)向量；

Step7：更新粒子位置；

Step8：如果未達到結束條件（status=0或達到迭代次數(shù)上限），返回Step4；否則輸出結果，結束算法。

2.4.3 測試運行

測試運行將系統(tǒng)各個部分連接成為一個整體，完成插裝后的被測程序在運行時被調用，將當前參數(shù)代入適應值函數(shù)，并將得到的適應值發(fā)給改進sPSO算法運行包，為算法提供評價個體優(yōu)劣的依據(jù)。

3 實例分析

三角形類別判定程序是在軟件測試研究中被廣泛應用的一個基準程序，本文利用該程序進行實驗仿真，并由C語言實現(xiàn)。分別用sPSO、RIW-sPSO和IMPR-sPSO來生成直角三角形路徑的測試數(shù)據(jù)，并對比這3種算法生成測試數(shù)據(jù)的運行結果。

當粒子群大小取值固定時（本次實驗中取值為100），使用sPSO、RIW-sPSO和IMPR-sPSO這3種算法分別運行20次找到最優(yōu)解的迭代次數(shù)，如圖2所示。

圖2 實驗中找到測試數(shù)據(jù)的迭代次數(shù)統(tǒng)計圖

以下是當粒子群大小取值不同時（60遞增到160，每次增加20粒子），使用sPSO、RIW-sPSO和IM PR-sPSO這3種算法分別運行20次找到最優(yōu)解的平均時間，如圖3所示。

圖3 試驗中找到測試數(shù)據(jù)的時間統(tǒng)計圖

圖2中黃線明顯較藍線和粉線平穩(wěn)，沒有過大的波動，說明了多次運行時IM PR-sPSO較sPSO和RIW-sPSO找到測試數(shù)據(jù)的迭代次數(shù)相差不大，即算法的穩(wěn)定性更好；圖3中黃線明顯較藍線和粉線位置低，說明了相同粒子數(shù)目前提下多次運行時IMPR-sPSO較sPSO和RIW-sPSO找到測試數(shù)據(jù)的平均時間最短，找到最優(yōu)解的平均時間最短；綜上所述，改進sPSO算法確實在收斂速度和收斂精度兩個方面都有提高，從而有效提高了搜索效率。

4 結束語

利用計算機的計算能力自動為目標程序生成高質量的測試數(shù)據(jù)，已經成為軟件測試領域中一個被廣泛關注和研究的問題。本文介紹了如何將改進sPSO算法應用于測試數(shù)據(jù)自動生成的具體實踐中。從簡單的粒子群算法入手，對其進行簡化，并針對其特點和不足從收斂速度和收斂精度兩方面入手進行改進，有效地提高了搜索效率。

[1] 嚴 陽.粒子群算法的改進及其在非線性問題中的應用[D].廣東：華南理工大學，2010.

[2] 紀 震，廖慧連，吳青華.粒子群算法及應用[M].北京：科學出版社，2009.

[3] 胡 旺，李志蜀.一種更簡化而高效的粒子群優(yōu)化算法[J].軟件學報，2007，18（4）：861-868.

[4] 陳琳玲.基于簡化粒子群算法的測試數(shù)據(jù)自動生成方法研究[D].西安：西南大學，2010.

[5] 張艷麗.基于PSO的路徑測試數(shù)據(jù)自動生成方法研究[D].西安：西安科技大學，2008.

[6] Ramamoorthy.C.V. On the automated generation of program test data[J].IEEE Transactions on software Engineering,1976,2(4):215-222.

[7] Kennedy J, Eberhart R. Particle swarm optim ization[C]. IEEE Int Conf on Neural Networks, 1995 .