曹小鵬，張 瑩，唐 煜

(西安郵電大學 計算機學院，陜西 西安 710121)

0 引 言

在軟件開發(fā)過程中，為了確保軟件質(zhì)量，利用測試用例自動生成技術，以達到用最少的測試用例找到盡可能多的錯誤。目前遺傳算法、禁忌搜索算法、正交算法、粒子群算法、蟻群算法等啟發(fā)式搜索算法在測試用例自動生成技術得到廣泛應用，該技術將測試用例生成過程轉換為使用智能算法求解最優(yōu)值問題[1-2]。胡文歡等[3]在遺傳算法測試用例自動生成中引進突變控制策略和優(yōu)化解控制策略，有效提高了算法的搜索能力和獲取最優(yōu)解的性能。賈冀婷[4]針對粒子群算法容易陷入局部最優(yōu)問題，對算法增加了“鄰居”最優(yōu)位置，進而提高了算法的局部搜索能力，證明該算法所需的迭代次數(shù)和平均運行時間，明顯優(yōu)于遺傳算法等測試用例自動生成算法，提高了生成測試用例的自動化程度。董躍華等[5]引進一種新的啟發(fā)式搜索算法—花朵授粉算法應用于測試數(shù)據(jù)自動生成，證明該算法比改進的遺傳算法和粒子群算法在測試用例自動生成上的可行性高。對以上文獻分析可知，在測試用例自動生成方面采用智能優(yōu)化算法有較強優(yōu)勢，但同時隨著算法的迭代，種群樣本數(shù)越來越少，空間搜索能力下降，導致算法易陷入局部最優(yōu)值。

為了解決花朵授粉算法早熟的缺陷，文中借鑒蛙跳算法(SFLA)的思想，對花粉配子種群個體先計算適應度值，并按照適應度值從大到小順序進行排序，再劃分種群為多個子族群，更新各個子族群中的最差個體位置，提高算法局部收斂速度，再將混合算法應用于測試用例的自動生成。

1 相關概念

1.1 花朵授粉

花朵授粉算法[6]是YANG X S教授受自然界中顯花植物花朵授粉過程的啟發(fā)而提出的一種新型群體智能優(yōu)化算法。其授粉過程分為異花授粉和自花授粉。異花授粉是利用自然界的蝴蝶、蜜蜂、蒼蠅等傳播者，進行花朵間長距離傳播授粉，因此又稱為全局授粉；自花授粉是花朵的花粉傳播到自身，相當于近距離傳播，因此也稱為自花授粉。算法還提供轉換概率p來解決花朵授粉過程的全局搜索和局部搜索的切換問題。同時由于昆蟲等傳播者的長距離傳播遵循萊維飛行機制，所以全局授粉能力較強。現(xiàn)在，花朵授粉算法已在函數(shù)優(yōu)化[7]、無線傳感網(wǎng)[8]、電力系統(tǒng)[9]等領域中應用廣泛。該算法實現(xiàn)簡單、參數(shù)少、易調(diào)節(jié)，且綜合了布谷鳥算法和蝙蝠算法的優(yōu)點，是一種優(yōu)秀的智能優(yōu)化算法。

在FPA算法求解最優(yōu)化問題時，還需假設條件：每株開花的植物只開一朵花，且只會有一個花粉配子，此時一朵花的配子就是求解過程的一個解。經(jīng)過這樣簡化，一個配子或一朵花就相當于優(yōu)化問題的解。

該算法實現(xiàn)的具體步驟為：

(1)初始化所有參數(shù)，設定轉換概率p∈[0,1]切換全局搜索和局部搜索，花朵種群數(shù)為n，再計算出每個解的適應度值，求出當前的最優(yōu)解及最優(yōu)值。

(2)全局授粉過程如式1所示，此時轉換概率p>rand。

(1)

若求解最小優(yōu)化問題，目標搜索空間為D維，種群規(guī)模為N。其中第i個花粉粒子位置向量表示為Xi=(Xi1,Xi2,…,XiD)，i=1,2,…,N。整個種群的最優(yōu)位置為g*=(g*1,g*2,…,g*D)(全局最優(yōu)解)。參數(shù)L是步長，L的計算公式為：

(2)

其中，λ=3/2，Γ(λ)是標準的伽馬函數(shù)。

(3)局部授粉過程如式3所示，此時轉換概率p

(3)

(4)計算式1或式3獲得新解，如果新解的適應度值比當前解的適應度值優(yōu)，就用新解替換當前解。

(5)如果在步驟2獲得的解中有適應度值優(yōu)于全局最優(yōu)值，則用新解替換當前全局最優(yōu)解。

(6)如果算法達到終止條件，則輸出最優(yōu)值和最優(yōu)解，結束迭代，否則，返回步驟2繼續(xù)進行位置更新。

1.2 蛙跳算法(SFLA)

蛙跳算法是一種解決組合優(yōu)化問題的新型智能優(yōu)化算法。該算法模擬自然界青蛙捕食的過程，并在求解優(yōu)化問題時將解當作種群的青蛙，通過模仿青蛙在尋找食物過程中的合作與競爭實現(xiàn)對最優(yōu)解的搜索。

SFLA算法描述如下：對于求解D維空間的優(yōu)化問題，隨機生成F只青蛙群體Q=(X1,X2,…,XF)作為初始種群。第i只青蛙的位置記為Xi=(Xi1,Xi2,…,XiD)，計算種群中全部青蛙的適應值f(Xi)，并依照適應值的大小對個體進行降序排列，記錄當前全局最優(yōu)個體Xg。將整個青蛙群體分割成m個子族群，且每個子族群包含n只青蛙，即滿足F=m×n。族群分割公式為：

Mi={Xi+m(h-1)∈Q|1≤h≤n}

(4)

其中，Mi為第i個子族群。每個子族群中最優(yōu)個體為XS，最差個體為XW。局部子族群最差個體XW按如下規(guī)則更新。

更新策略為：

Lj=γ(XS-XW)

(5)

(6)

(2)向全局最優(yōu)個體學習。如若規(guī)則1中新個體適應度值劣于原來最差個體適應值，則用全局最優(yōu)個體Xg替代XS，再依據(jù)式5和式6進行更新。

(3)隨機更新。若經(jīng)過規(guī)則1與規(guī)則2生成的新適應值劣于原來的適應值，則在搜索空間范圍內(nèi)依照XW隨機生成一個新解替換原來式中的XW。

重復以上操作，直到滿足終止條件。其中，γ為[0，1]內(nèi)的均勻分布隨機數(shù)；j=1,2,…,m；Lj為青蛙更新步長；Lmax為最大更新步長，Lmin為最小更新步長。

2 FPA算法的改進以及在測試用例生成中的應用

2.1 改進算法

通過對SFLA算法和FPA算法的分析，發(fā)現(xiàn)蛙跳算法可以彌補花朵授粉算法的不足。針對花朵授粉算法局部搜索能力低下、易陷入早熟現(xiàn)象等問題，根據(jù)SFLA對花粉位置進行更新。首先，將花朵種群分割成不同的子族群，每個子族群按照蛙跳算法的規(guī)則進行更新?；ǘ鋫€體向子族群之間最優(yōu)個體XS學習，若更新失敗，再向全局最優(yōu)個體Xg學習，如若2次都更新失敗，則在可行域內(nèi)隨機產(chǎn)生一個新解替換局部最差個體XW。其次，每個子族群達到最大演化代數(shù)后，再將所有的子族群打亂重新混合，讓花粉種群信息互換，以免種群匯集，保持多樣性。由此可知，文中將兩種算法結合，得到一種混合優(yōu)化算法，即混合群體爬山策略的FPA(hybrid FPA of colony mountain climbing strategy，CMSFPA)。

為了加強算法局部尋優(yōu)能力，維持種群多樣性，防止種群花粉粒子向全局最優(yōu)值處匯聚，對子族群的進化過程中只采用XS，而沒有采用g*(或Xg)?；旌纤惴鞒倘鐖D1所示。

做為中建人的一員，全年在外施工是常態(tài)，對于家里自是無暇顧及，數(shù)次搬家、兩次裝修，撫養(yǎng)孩子，孝敬老人統(tǒng)統(tǒng)甩給了妻子，偶爾回到總部開會，也是匆匆來匆匆走，老人曾說他就是一個“野人”。然而，電話的那一頭，卻總是“兒子的胃病好點沒，爹的假牙換了沒……”他對家人的惦念一直留在心里，隨著年齡的增長，他越來越注意抽出時間與父母嘮家常，倔強的父親也逐漸理解了這個“不孝”的兒子。

圖1 CMSFPA算法流程

2.2 CMSFPA算法在測試用例生成中的應用

根據(jù)CMSFPA混合算法流程及測試用例生成的基本理論，創(chuàng)建了混合測試用例自動生成算法的系統(tǒng)模型框架，包含3個模塊，如圖2所示。

模塊一為測試環(huán)境的搭建模塊。該模塊是建立框架的基準，對被測程序進行靜態(tài)分析，然后根據(jù)選擇的目標路徑進行參數(shù)選擇及分支函數(shù)插樁；模塊二為CMSFPA算法模塊。該算法是核心部分，首先對CMSFPA進行參數(shù)設置以及隨機初始化一組解，然后對產(chǎn)生的解評估適應度，如果滿足終止條件就輸出最優(yōu)解，如果不滿足最優(yōu)解就利用CMSFPA算法對初始解進行迭代操作，以此來對解進行更新，直到尋得足夠優(yōu)的位置或算法達到終止條件；模塊三為測試執(zhí)行模塊。CMSFPA測試執(zhí)行模塊在測試用例生成框架中起到了實時調(diào)用并運行的作用，它主要完成對插樁后的被測測序的實時調(diào)用和運行，再將得到的適應度值傳遞給CMSFPA算法模塊使用。

圖2 CMSFPA算法測試用例自動生成框架

2.3 適應度函數(shù)的構造

適應度函數(shù)構造直接影響FPA效率。一般情況下，適應度函數(shù)由目標函數(shù)轉化而來。設計時要滿足以下條件：(1)單值，連續(xù)，非負，最大化；(2)合理，一致；(3)計算量??；(4)通用性強。

優(yōu)良的適應度函數(shù)能夠快速求出最優(yōu)解。因此，能否合理并成功地構造適應度函數(shù)，是提高算法效率的關鍵點。換而言之，其適應度值反映了種群個體測試用例的測試效率，對應的值越高表明測試效率越高，因而測試用例能夠在較短時間覆蓋更多的目標路徑，就能找到更多的程序錯誤。

基于文中測試用例生成模型框架的特性，綜合考慮各方因素，選取“分支函數(shù)”[10]插裝法來構造適應度函數(shù)，定義如下：假設被測程序中指定的某條路徑有m個分支點，即Path=n1,n2,…,nm。首先，在每個分支點前插入適當?shù)姆种Ш瘮?shù)f1,f2,…,fm；其次，把這m個分支函數(shù)疊加：F=f1+f2+…+fm，并將疊加后的F作為適應度函數(shù)，其中fi∈[1,m]的值表示當前實際測試路徑與指定邏輯路徑的偏差距離。

文中假設的全部分支謂詞都是形如MopN的簡單關系表達式。M、N均為運算對象(包括運算表達式)，op為運算符[11](包括<，<=，==，！=，>，>=)。適應度函數(shù)值判斷分析見表1。

表1 適應度函數(shù)值判斷分析

如表1所示，根據(jù)分支函數(shù)fi=N-M可知，f越大表明測試用例距離指定路徑越遠，f越小表明測試用例距離指定路徑越近。選取分支路徑有以下2種情況：(1)分支判斷語句為真，則fi<0，其對應的適應度函數(shù)值等于0；(2)分支判斷語句為假，則fi>0，其對應的適應度函數(shù)值等于N-M的值。因此，為了產(chǎn)生某目標路徑測試用例，需要獲取目標函數(shù)值為0的F。

3 實驗結果與分析

3.1 實驗方案

選取三個開源程序為被測對象，程序的詳細信息如表2所示。

表2 測試程序

程序1的目標路徑為等邊三角形；程序2的目標路徑為輸入的10個字符均為16進制的字符，且其轉化為10進制之后的總和在50～100之間；程序3的目標路徑是判斷數(shù)組中全部變量是否為0

實驗將標準的FPA和PSO、CMSFPA分別應用于自動生成模型測，再對三者進行對比分析。算法涉及的參數(shù)為：PSO的學習因子c1、c2=2，慣性權重系數(shù)ω隨迭代次數(shù)的增加由0.9線性減小到0.4，F(xiàn)PA與CMSFPA的轉換概率p=0.8。隨后利用迭代次數(shù)和運行時間作為實驗成果的評價指標[14]。最后產(chǎn)生的全部目標路徑測試用例的用時越短、進化代數(shù)越少，說明算法改進效率越高。

3.2 最優(yōu)解迭代次數(shù)和最優(yōu)解迭代時間對比

在實現(xiàn)CMSFPA、FPA、PSO三種算法分別產(chǎn)生實驗程序的測試用例中，引用文獻[15]數(shù)據(jù)，規(guī)模分別設置為140，180，220，260和300，設置最大進化代數(shù)為800?；谝陨显O置，將基本的PSO和混合的CMSFPA、基本的FPA作為核心算法應用于系統(tǒng)模型，其次，每個種群都互相獨立地進行10組測試實驗，對10次實驗產(chǎn)生的運行時間(運行時間為10次找到最優(yōu)迭代時間的平均值)和最優(yōu)解所需的迭代次數(shù)進行了對比分析。

表3是以上3種算法分別對程序1、2、3進行測試生成最優(yōu)解所需的最迭代次數(shù)。

表3 CMSFPA、FPA、PSO找到最優(yōu)解迭代次數(shù)對比

從表3可以看出，隨著種群規(guī)模的增加，三個測試程序?qū)ο蟛捎没旌系臏y試用例自動生成算法所需的迭代數(shù)普遍少于標準的花朵授粉算法和粒子群算法。說明文中算法明顯優(yōu)于標準的FPA、PSO。當種群規(guī)模達到300時，PSO、FPA、CMSFPA找到最優(yōu)解的效率比較顯著，但是隨著后期種群搜索空間減小，種群規(guī)模越來越少，導致種群多樣性下降，普通的PSO算法和FPA算法漸漸顯現(xiàn)缺陷。在被測程序運行期間有時會快速地找到好的測試數(shù)據(jù)，但在多次迭代演化后，測試數(shù)據(jù)一成不變，表明該算法已陷入了早熟狀態(tài)。可以看出當種群規(guī)模由300減少到140時，PSO算法和FPA算法找到最優(yōu)解迭代次數(shù)增加較多，比較容易陷入局部最優(yōu)解，而混合的FPA算法的迭代次數(shù)明顯比PSO算法和FPA算法少，說明混合的FPA算法成功地解決了早熟問題，并且提高了收斂速度。

對3種測試程序分別進行測試，記錄當種群的規(guī)模由140遞增到300時，CMSFPA 、 FPA 、PSO算法生成最優(yōu)解迭代時間的平均值，如實驗結果圖3～圖5。

圖3 程序1找到最優(yōu)解運行時間

從圖3可知，應用PSO、FPA、CMSFPA算法進行實驗，其中PSO、FPA產(chǎn)生最優(yōu)解迭代所需時間顯著大于CMSFPA所需時間，在迭代次數(shù)良好的條件下，CMSFPA平均運行時間比基本FPA減少在 40ms 以上，比基本PSO減少在60ms 以上。

圖4 程序編號程序2找到最優(yōu)解運行時間

從圖4可知，應用PSO、FPA、CMSFPA算法進行實驗，其中PSO、FPA產(chǎn)生最優(yōu)解迭代所需時間顯著大于CMSFPA所需時間，在迭代次數(shù)良好的條件下，CMSFPA平均運行時間比基本FPA減少在 170ms 以上，比基本PSO減少在180ms 以上。

圖5 程序3找到最優(yōu)解運行時間

從圖5可知應用PSO、FPA、CMSFPA算法進行實驗，其中PSO、FPA產(chǎn)生最優(yōu)解迭代所需時間顯著大于CMSFPA所需時間，在迭代次數(shù)良好的條件下，其平均運行時間比標準FPA減少在 240ms 以上，比標準PSO減少在370ms 以上。通過對以上三個圖的對比，可知混合的算法優(yōu)越性明顯。

綜上所述，與標準FPA、PSO算法相比，本文研究的CMSFPA算法測試用例自動生成框架不僅收斂速度快、平均運行時間短，還能有效解決局部最優(yōu)解缺陷，可以高效、精確地生成所需的測試用例。因而應用本文研究的CMSFPA 算法與標準算法相比生成測試用例的效果顯著。

4 結束語

為了提高測試用例自動生算法局部搜索能力，改善易于陷入早熟狀態(tài)的等問題。本文通過將花朵授粉算法融合蛙跳算法思想應用于測試用例自動生成，將花朵種群分成若干子族群，并根據(jù)SLFA規(guī)則學習并運行，不僅增強了FPA的局部搜索精度，而且改善了FPA陷入局部最優(yōu)值誤區(qū)狀況。最后實驗部分通過3個測試程序?qū)λ惴ㄟM行了對比驗證，實驗證明CMSFPA有較強的尋優(yōu)能力，對測試用例生成效率有了較大提高。