一種面向路徑的測(cè)試數(shù)據(jù)自動(dòng)生成的組合方法*

于笳韻 劉傳才

（南京理工大學(xué)計(jì)算機(jī)科學(xué)與工程學(xué)院 南京 210094）

1 引言

軟件測(cè)試［1］是用來(lái)提高消費(fèi)者對(duì)軟件信心的主要技術(shù)。它是一種復(fù)雜耗時(shí)且勞動(dòng)密集型的工作，發(fā)展軟件測(cè)試自動(dòng)化技術(shù)將大大減少軟件測(cè)試的成本。

測(cè)試數(shù)據(jù)生成［2］是指識(shí)別一組滿(mǎn)足給定測(cè)試標(biāo)準(zhǔn)的程序輸入數(shù)據(jù)的過(guò)程。研究發(fā)現(xiàn)，將一些智能優(yōu)化算法應(yīng)用到測(cè)試數(shù)據(jù)自動(dòng)生成的過(guò)程中，可以明顯提高測(cè)試數(shù)據(jù)生成的效率。但目前得到普遍應(yīng)用的幾種算法仍存在一些問(wèn)題。比如，遺傳算法［3～4］搜索過(guò)程靈活，但容易陷入局部最優(yōu)，出現(xiàn)“早熟”；粒子群算法［5］邏輯清晰易懂且涉及到的未知參數(shù)較少，但后期爬山能力不強(qiáng)；蟻群算法［6］可以抑制“早熟”，但初期信息素匱乏，搜索效率較低；模擬退火算法［7］可以在一定程度上接受“惡化”解，但收斂速度較慢。本文提出設(shè)想，改進(jìn)粒子群算法，再將其與蟻群算法組合。在算法初期，先對(duì)粒子群算法進(jìn)行降階操作，將算法中的更新公式由二階降為一階，利用降階后的粒子群算法生成初步測(cè)試結(jié)果，再針對(duì)每個(gè)粒子的局部搜索過(guò)程，引入信息素機(jī)制，從而達(dá)到提高測(cè)試數(shù)據(jù)自動(dòng)生成效率的目的，以期為該領(lǐng)域提供一種新的研究思路。

2 背景知識(shí)

2.1 粒子群算法

粒子群算法的核心思想是：以沒(méi)有質(zhì)量和體積的粒子為對(duì)象，為每個(gè)粒子制定一個(gè)飛行速度和適應(yīng)值，各個(gè)粒子通過(guò)跟蹤全局最優(yōu)解和個(gè)體歷史最優(yōu)解來(lái)不斷更新自己，從而在多次迭代以后找到最優(yōu)解［8～9］。

近年來(lái)，相關(guān)領(lǐng)域的學(xué)者對(duì)粒子群算法的優(yōu)化改進(jìn)一直在進(jìn)行，集中體現(xiàn)在如下幾個(gè)方面：1）新增慣性權(quán)重［10］和收斂因子的概念，使算法的全局搜索力和局部搜索力達(dá)到相對(duì)平衡。2）給粒子的速度和位置重新賦值，比如使用新粒子替換不活潑粒子，避免算法過(guò)早收斂出現(xiàn)“早熟”。3）引入進(jìn)化計(jì)算技巧，如將遺傳算法引入粒子群算法［11］，改進(jìn)粒子群算法存在的弊端和不足。

粒子群算法計(jì)算速度快，全局搜索力強(qiáng)，實(shí)現(xiàn)起來(lái)簡(jiǎn)單高效。同時(shí)還擁有良好的記憶能力，方便個(gè)體之間信息共享，有利于搜索策略的調(diào)整，使粒子不斷向最優(yōu)解的方向靠攏。

2.2 蟻群算法

蟻群算法的核心思想如下：在開(kāi)始階段，螞蟻隨機(jī)搜索路徑，釋放信息素的同時(shí)分析其他螞蟻釋放的信息素。漸漸地，越來(lái)越傾向于選擇信息素濃度大的路徑，形成信息的正反饋，引導(dǎo)搜索變得更有規(guī)律，從而靠近全局最優(yōu)解。為了防止算法過(guò)早收斂，算法還引入了負(fù)反饋機(jī)制［12］，保證信息素適度揮發(fā)、較優(yōu)解得到增強(qiáng)。

近年來(lái)，研究人員對(duì)蟻群算法的研究和改進(jìn)主要集中在以下幾個(gè)方面：1）提出MAX-MIN蟻群系統(tǒng)［13］，對(duì)信息素濃度值的上下限進(jìn)行限制，從而克服可能出現(xiàn)的停滯現(xiàn)象。2）提出動(dòng)態(tài)自適應(yīng)蟻群算法［14］，對(duì)信息素采取自適應(yīng)調(diào)整的方式，比如構(gòu)造不同的信息素更新公式，使得算法收斂性和穩(wěn)定性明顯增強(qiáng)。

蟻群算法利用正反饋機(jī)制不斷更新信息素［15］，使結(jié)果最終收斂于最優(yōu)解，保證了進(jìn)化過(guò)程的穩(wěn)定性。算法初期因?yàn)槿狈π畔⑺兀浵伒乃阉髅つ繜o(wú)序，信息素豐富以后，螞蟻間交流協(xié)作增多，蟻群越來(lái)越趨向于靠近最優(yōu)解，從無(wú)序到有序，體現(xiàn)了該算法的自組織性［16］。

3 粒子群－蟻群組合算法及其測(cè)試數(shù)據(jù)的生成

3.1 粒子群算法的優(yōu)化

目前，粒子群算法都是基于粒子的“位置”和“速度”兩個(gè)關(guān)鍵值，為了平衡全局搜索力和局部搜索力，標(biāo)準(zhǔn)粒子群算法在速度更新公式中加入了慣性權(quán)重w，搜索過(guò)程中，w隨迭代次數(shù)的增加線(xiàn)性遞減，起到相對(duì)控制粒子速度的作用。但搜索過(guò)程本身很復(fù)雜，且是非線(xiàn)性的，因此線(xiàn)性改變w并不能完全適應(yīng)搜索過(guò)程。

在標(biāo)準(zhǔn)粒子群算法中，粒子速度和位置更新公式如下：

D表示空間維度，n是粒子個(gè)數(shù)。xi=(xi1，xi2…xiD)表示第i個(gè)粒子的位置向量；vi=(vi1，vi2…viD)表示第i個(gè)粒子的速度向量；pbest=(pi1，pi2…piD)表示第i個(gè)粒子的個(gè)體歷史最優(yōu)解；gbest=(g1，g2…gD)表示整個(gè)粒子群的歷史最優(yōu)解。

粒子的飛行速度需要作限制，保證其不超過(guò)最大限定速度vmax，否則搜索過(guò)程可能會(huì)出現(xiàn)“溢出”現(xiàn)象。vmax值會(huì)對(duì)搜索過(guò)程產(chǎn)生影響，vmax偏大則全局搜索力更強(qiáng)，vmax偏小則局部搜索力更強(qiáng)。因此如何設(shè)置合適的vmax值從而保證粒子以恰當(dāng)?shù)乃俣纫苿?dòng)是一個(gè)難解的問(wèn)題。粒子的位置進(jìn)化公式中，當(dāng)前位置等于先前位置與當(dāng)前速度之和，但這不符合運(yùn)動(dòng)規(guī)律x=vt。理論上講，粒子速度不會(huì)影響粒子盡可能往最優(yōu)解靠近，反而當(dāng)速度過(guò)快時(shí)可能使粒子偏離正確的搜索方向，造成收斂又不準(zhǔn)確又慢的問(wèn)題。

綜上，考慮只將xi的直接變化納入迭代過(guò)程，簡(jiǎn)化后的方程如下所示：

改進(jìn)后的粒子群算法進(jìn)化方程階數(shù)降低，由二階降到一階，并且去掉了速度參數(shù)，簡(jiǎn)化了粒子的進(jìn)化過(guò)程，需要設(shè)置和調(diào)節(jié)的參數(shù)就只剩下慣性權(quán)重w。標(biāo)準(zhǔn)粒子群算法中w一般取小于l的值，并且隨迭代的進(jìn)行線(xiàn)性減少，這樣可以保證粒子速度得到控制，在算法進(jìn)化后期不斷減小，最終完成迭代并搜索到最優(yōu)解。但是在簡(jiǎn)化后的粒子群算法中，如果w小于l，由式（3）可以發(fā)現(xiàn)，w直接影響粒子位置，多次迭代以后，粒子的位置很可能會(huì)過(guò)于偏向低值區(qū)域，此時(shí)若是最優(yōu)解剛好在高值區(qū)域里，則可能無(wú)法被搜索到。

為了平衡粒子對(duì)搜索域的遍歷性，在經(jīng)過(guò)多次試驗(yàn)后，本文決定隨機(jī)選取每個(gè)粒子的w值，取值范圍為。經(jīng)過(guò)測(cè)試，w值從該區(qū)間中隨機(jī)選取時(shí)，既能保證粒子搜索遍歷性，也不會(huì)過(guò)于改變粒子當(dāng)前位置，可以保證算法的穩(wěn)定性。

3.2 粒子群算法與蟻群算法的組合

簡(jiǎn)化后的粒子群算法計(jì)算量有所減少，實(shí)現(xiàn)過(guò)程也變得相對(duì)容易。但是可以發(fā)現(xiàn)，在粒子位置進(jìn)化公式中，雖然考慮到了前期粒子全局最優(yōu)解和個(gè)體最優(yōu)解的影響，可如果遇到比較復(fù)雜的多峰值問(wèn)題求解，或者當(dāng)全局最優(yōu)解和局部最優(yōu)解比較靠近時(shí)，還是很容易出現(xiàn)“早熟”，即粒子陷入局部最優(yōu)解附近的搜索域飛不出來(lái)。因此，我們嘗試將粒子群算法與蟻群算法組合，在算法初期先利用簡(jiǎn)化后的粒子群算法生成信息素分布，再引入信息素反饋機(jī)制，降低陷入局部最優(yōu)的風(fēng)險(xiǎn)。

粒子位置按照式（3）更新，對(duì)每個(gè)粒子的個(gè)體歷史最優(yōu)解 pbest進(jìn)行增益評(píng)估，即在pbest鄰域內(nèi)搜索產(chǎn)生k個(gè)點(diǎn)，對(duì)包含 pbest在內(nèi)的這k+1個(gè)點(diǎn)按式（4）作概率計(jì)算，最后選擇概率較大的點(diǎn)作為新粒子，保證信息素濃度與粒子進(jìn)化增益值成正比。

s0為給定值，取值范圍為，F(xiàn)(j)是關(guān)于 j的適應(yīng)度函數(shù)。算法具體實(shí)現(xiàn)過(guò)程如圖1所示。

圖1 粒子群－蟻群組合算法流程圖

適應(yīng)度函數(shù)如何構(gòu)造也是一個(gè)十分難解的問(wèn)題，因?yàn)檫m應(yīng)度函數(shù)對(duì)算法的搜索效率會(huì)產(chǎn)生較大影響。綜合考慮約束條件，本文選取常見(jiàn)的“分支函數(shù)疊加法”［17］。分支函數(shù)量化了被測(cè)值滿(mǎn)足選定路徑的程度［18］。假設(shè)被測(cè)路徑上有n個(gè)分支點(diǎn)，分支謂詞決定了程序執(zhí)行哪個(gè)分支，在每個(gè)分支點(diǎn)前都插入相應(yīng)的分支函數(shù) f1，f2，…，fn，則適應(yīng)度函數(shù)值與分支謂詞、分支函數(shù)的關(guān)系如表1所示。

表1 分支函數(shù)值與適應(yīng)度函數(shù)值的關(guān)系表

若分支判斷語(yǔ)句為true，適應(yīng)度函數(shù)值為0；若分支判斷語(yǔ)句為false，適應(yīng)度函數(shù)值取分支函數(shù)值。若路徑所經(jīng)過(guò)的判斷語(yǔ)句不止一個(gè)，則適應(yīng)度函數(shù)值為，F(xiàn)越小，表明測(cè)試數(shù)據(jù)越接近目標(biāo)路徑，F(xiàn)=0時(shí)，則表明測(cè)試數(shù)據(jù)完全符合目標(biāo)路徑。

4 實(shí)驗(yàn)

在研究用智能算法生成測(cè)試數(shù)據(jù)時(shí)，大都以三角形分類(lèi)程序?yàn)槔切畏诸?lèi)程序邏輯清晰，比較適合用來(lái)測(cè)試算法的適應(yīng)程度。本文同樣針對(duì)三角形分類(lèi)判定程序，分別使用標(biāo)準(zhǔn)粒子群算法和改進(jìn)后的粒子群-蟻群組合算法進(jìn)行測(cè)試數(shù)據(jù)自動(dòng)生成實(shí)驗(yàn)。

4.1 測(cè)試數(shù)據(jù)生成結(jié)果對(duì)比

以三角形判定為被測(cè)程序，設(shè)置粒子群初始粒子數(shù)為100，第i個(gè)粒子可以被表示成 xi=(xi1，xi2，xi3)，每個(gè)粒子的三條邊隨機(jī)選取區(qū)間內(nèi)的數(shù)。

應(yīng)用標(biāo)準(zhǔn)粒子群算法進(jìn)行測(cè)試數(shù)據(jù)自動(dòng)生成時(shí)，c1和c2均設(shè)置為2，w值設(shè)置為隨著迭代次數(shù)增加由0.7到0.3之間線(xiàn)性遞減，設(shè)最大迭代次數(shù)為15，實(shí)驗(yàn)結(jié)果如圖2所示。

圖2 標(biāo)準(zhǔn)粒子群算法實(shí)驗(yàn)結(jié)果圖

應(yīng)用粒子群-蟻群組合算法進(jìn)行測(cè)試數(shù)據(jù)自動(dòng)生成時(shí)，每個(gè)粒子的w值隨機(jī)取區(qū)間中的數(shù)，k=10，迭代次數(shù)上限值設(shè)為15，實(shí)驗(yàn)結(jié)果如圖3所示。

圖3 粒子群－蟻群組合算法實(shí)驗(yàn)結(jié)果圖

對(duì)比兩次實(shí)驗(yàn)結(jié)果，可以發(fā)現(xiàn)，使用標(biāo)準(zhǔn)粒子群算法生成的測(cè)試數(shù)據(jù)時(shí)，各個(gè)種類(lèi)的三角形粒子數(shù)目差異蠻大；而在使用粒子群-蟻群組合算法生成數(shù)據(jù)時(shí)，因?yàn)槭艿叫畔⑺氐挠绊?，等邊三角形和等腰三角形的粒子?shù)量相對(duì)減少，適應(yīng)度較小的非三角形粒子數(shù)量有所增加。也就是說(shuō)，不同路徑上粒子數(shù)量的差距明顯得到抑制，改進(jìn)后的算法優(yōu)化效果較明顯。

4.2 算法運(yùn)行效率的比較

選擇等邊三角形判定路徑作為被測(cè)路徑，運(yùn)用標(biāo)準(zhǔn)粒子群算法和粒子群-蟻群組合算法分別運(yùn)行等邊三角形判定程序。標(biāo)準(zhǔn)粒子群算法中，c1=c2=2，w值取隨著迭代程度加強(qiáng)線(xiàn)性減少，取值范圍，迭代次數(shù)上限值設(shè)為1000。組合算法中，w隨機(jī)選取，取值范圍為，k=10，迭代次數(shù)上限值設(shè)為1000。

兩種算法各運(yùn)行5次，記錄每次實(shí)驗(yàn)運(yùn)行得出最終結(jié)果時(shí)所耗費(fèi)的CPU運(yùn)行時(shí)間，對(duì)比實(shí)驗(yàn)結(jié)果，可得圖4。

圖4 兩種算法運(yùn)行效率的比較

可以發(fā)現(xiàn)，組合算法運(yùn)行時(shí)間普遍低于標(biāo)準(zhǔn)粒子群算法，也就是說(shuō)，在對(duì)算法進(jìn)行優(yōu)化后，算法效率有所提高，搜索過(guò)程更高效，找到全局最優(yōu)解所需要花費(fèi)的時(shí)間更少。

5 結(jié)語(yǔ)

本文將優(yōu)化的粒子群算法和蟻群算法作組合，新方法充分凝聚了兩個(gè)算法的優(yōu)點(diǎn)，變得更加簡(jiǎn)便易懂，對(duì)于未知參數(shù)的設(shè)置也有所減少，確保了算法的準(zhǔn)確性和穩(wěn)定性。組合算法以粒子群優(yōu)化算法為主線(xiàn)，先對(duì)粒子群算法進(jìn)行降階操作，慣性權(quán)重隨機(jī)選取，然后利用簡(jiǎn)化后的粒子群算法進(jìn)行初步搜索，再針對(duì)每個(gè)粒子的局部搜索引入信息素機(jī)制，有效防止搜索過(guò)程陷入“早熟”。實(shí)驗(yàn)結(jié)果表明，將此組合算法用于測(cè)試用例的自動(dòng)生成，最大程度地體現(xiàn)了兩個(gè)算法的優(yōu)勢(shì)。利用反饋信息增強(qiáng)全局搜索能力，保證整個(gè)求解過(guò)程適應(yīng)度高的粒子個(gè)體與適應(yīng)度低的粒子個(gè)體數(shù)目差距不會(huì)過(guò)大，有效地提升了測(cè)試數(shù)據(jù)自動(dòng)生成的穩(wěn)定性和平衡性，相對(duì)解決了搜索過(guò)程易“早熟”的問(wèn)題。同時(shí)，算法的運(yùn)行效率明顯得到提高，數(shù)據(jù)量較大時(shí)可以有效節(jié)約運(yùn)行時(shí)間，使得測(cè)試數(shù)據(jù)自動(dòng)化生成更可靠、更合理，實(shí)用價(jià)值更高。