馮 菲，孫玫肖，劉文韜

（中國鐵道科學(xué)研究院 電子計(jì)算技術(shù)研究所，北京 100081）

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

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

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

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

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

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

2 粒子群算法及其改進(jìn)

2.1 粒子群算法

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

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

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

2.2 簡化粒子群算法

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

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

2.3 改進(jìn)sPSO算法

2.3.1 進(jìn)一步提高收斂速度

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

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

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

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

2.3.2 進(jìn)一步提高收斂精度

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

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

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

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

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

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

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

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

2.4.2 改進(jìn)sPSO算法運(yùn)行包

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

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

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

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

Step4：計(jì)算每個(gè)粒子的適應(yīng)值；

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

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

Step7：更新粒子位置；

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

2.4.3 測試運(yùn)行

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

3 實(shí)例分析

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

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

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

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

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

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

4 結(jié)束語

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

[1] 嚴(yán) 陽.粒子群算法的改進(jìn)及其在非線性問題中的應(yīng)用[D].廣東：華南理工大學(xué)，2010.

[2] 紀(jì) 震，廖慧連，吳青華.粒子群算法及應(yīng)用[M].北京：科學(xué)出版社，2009.

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

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

[5] 張艷麗.基于PSO的路徑測試數(shù)據(jù)自動(dòng)生成方法研究[D].西安：西安科技大學(xué)，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 .