基于改進蝙蝠算法的軟件缺陷預測模型

楊曉琴

(太原廣播電視大學，山西 太原 030002)

0 引 言

軟件缺陷預測是一種根據(jù)以往開發(fā)軟件模塊特征來預測未來開發(fā)軟件缺陷性的模型。軟件缺陷預測能夠預測軟件存在的缺陷位置和數(shù)量，能夠知道測試工作，提升測試工作效率，節(jié)約成本。

軟件缺陷預測技術涵蓋了動態(tài)、靜態(tài)兩種。以往的動態(tài)缺陷預測技術主要有Rayleigh分布模型、指數(shù)分布模型和S曲線分布模型。Rayleigh分布模型應用廣泛，Trachtenberg等開展了一系列實驗，進而實現(xiàn)對缺陷數(shù)據(jù)的驗證，從結果來看這些缺陷數(shù)據(jù)符合Rayleigh分布模型。Rescorla等在一系列研究之后，闡述了著名的指數(shù)分布模型，其將研究重點放在軟件驗收的測試階段，通過深入研究，確定了此階段軟件缺陷累計分布規(guī)律[1]?；赟曲線的分布模型能夠了解到，從軟件開發(fā)一直到回歸測試，在缺陷累計數(shù)量方面是符合S型的，最終意味著來到了軟件成熟階段。Alhazmi等在一系列研究之后，闡述了著名的AML模型，該模式作為S曲線模型中的代表模型，和實驗數(shù)據(jù)的擬合度較高，性能較好[2-3]。Joh等在對軟件生命周期中軟件缺陷模塊占比變動規(guī)律進行描述的過程中，主要基于Weibull統(tǒng)計分布來實現(xiàn)[4]，該方法能夠有效地評估軟件風險。

與動態(tài)軟件缺陷預測技術不同，靜態(tài)軟件缺陷預測技術一般將軟件預測問題進行轉化，最終變?yōu)闄C器學習中的一種分類問題，具體就是基于缺陷預測模型有效劃分待預測模塊，分為無缺陷以及有缺陷的模塊兩類。傳統(tǒng)分類技術相對豐富一些，如支持向量機(support vector machine，SVM)[5]、貝葉斯網(wǎng)絡(Bayesian network，BN)[6]、決策樹(decision tree)[7]、神經(jīng)網(wǎng)絡[8]以及K最近鄰分類算法[9]等。

支持向量機的兩個關鍵參數(shù)的選擇非常重要，會影響到支持向量機進行分類的最終效果。由于基于支持向量機軟件缺陷預測模型有著比較低的準確率，筆者為了解決這個問題，基于改進蝙蝠算法來完善支持向量機的軟件缺陷預測模型。改進蝙蝠算法能夠優(yōu)化支持向量機的關鍵參數(shù)，能獲得更好的分類模型，提高模型的分類準確性。為了驗證該預測模型的預測性能，利用NASA的MDP數(shù)據(jù)集進行測試，并與已有的缺陷預測模型進行比較。

1 相關工作

1.1 軟件缺陷預測模型

靜態(tài)缺陷預測技術可以根據(jù)歷史數(shù)據(jù)信息有效預測模塊缺陷傾向性，不過專家將負責抽取標記軟件模塊，同時軟件缺陷預測的性能也受度量元設計的影響。雖然動態(tài)的軟件缺陷預測技術能夠掌控軟件生命周期中所有缺陷的變動狀況，但是特征提取難度比較高，有著比較窄的覆蓋面，運行環(huán)境對其影響較大，文中主要對靜態(tài)軟件缺陷預測技術進行研究。

模型構建包含三個步驟：

(1)選取軟件模塊，全方位分析軟件代碼，對全部的屬性值進行統(tǒng)計，有效標記模塊所具有的缺陷性，這樣就可以獲得相對應的訓練數(shù)據(jù)集。在軟件模塊中，有效挑選n個樣本數(shù)據(jù)集為Dn={(x1,y1),…,(xn,yn)}，其中軟件模塊i的度量屬性是向量xi∈Rk，所有向量均包含多維的度量元，并表示為xi=(a1,…,ak)。yi∈Y是第i個模塊的類標記。專家將負責抽取標記軟件模塊數(shù)據(jù)集。

(2)通過所選擇預測方法或技術對數(shù)據(jù)集進行訓練，最終將獲得所需的訓練樣本。對樣本的數(shù)據(jù)集進行學習，能夠在軟件模塊的屬性以及缺陷性間實現(xiàn)識別標準的有效構建，將多個模塊屬性向量進行輸入，這樣就可以獲得特定輸出，有助于全方位了解模塊所具有的缺陷性，得出軟件模塊屬性和缺陷相關的映射關系。

(3)對軟件缺陷預測技術、方法性能進行驗證。首先需要取得預測所獲得的結果，有效地評估技術或方法所具有的性能。相關指標主要有準確率、誤報率、AUC取值和缺陷檢出率等。不同的軟件或系統(tǒng)對于成本和安全性的要求不同，對于不同指標的要求不一樣，但是目的都是盡可能地節(jié)約軟件的測試成本，檢測出盡可能多的軟件缺陷。

單目標啟發(fā)式搜索算法在軟件缺陷預測中有著較多的應用，對軟件缺陷預測技術進行不斷完善，這樣軟件預測將達到更高的準確率。分析啟發(fā)式搜索算法可以了解到，其表現(xiàn)為搜索速度快，搜索精度高，能夠為NP難的問題搜索到滿意解，可以對缺陷預測技術的參數(shù)進行選擇，搜索出符合要求的參數(shù)值。

支持向量機在學習完訓練樣本之后，能夠找出最優(yōu)分類面和支持向量，并且對訓練的數(shù)據(jù)集的有效類型進行劃分，這樣分類面盡可能遠離于每一類的距離。若數(shù)據(jù)表現(xiàn)出線性不可分，依托核函數(shù)映射到高維的特征空間，這樣數(shù)據(jù)將獲得最優(yōu)的分類面。支持向量機在泛化能力方面表現(xiàn)十分出色，同時可以有效解決非線性分類問題。Elish等橫向對比了支持向量機以及其他的分類算法，由實驗結果了解到，支持向量機表現(xiàn)出了更好的性能[10]。

啟發(fā)式搜索算法在一定程度上可以優(yōu)化支持向量機，尤其是懲罰因子以及徑向基帶寬等層面，主要是對其取值進行優(yōu)化。王男帥等[11]使用遺傳算法做最佳度量屬性的選擇，避免有用的信息被過早篩除。姜慧研等[12]針對數(shù)據(jù)集，基于主成分分析法有效降維處理數(shù)據(jù)集，這樣模型將有更高的運算速度，之后再利用蟻群優(yōu)化算法對支持向量機的參數(shù)進行選擇。

1.2 支持向量機

1995年，Cortes和Vapnik第一次闡述了SVM。后者對非線性分類問題能夠進行有效的處理。支持向量機的原理是在空間中尋找一個分類面作為兩個類的分割，這個分類面距兩類樣本的距離越大越好，這樣可以更好地分開兩類樣本。支持向量機突出的一點是可以經(jīng)過核函數(shù)映射，在高位空間來處理線性不可分的情況。

支持向量機處理的樣本可以表示為(x1,y1),…,(xl,yl),x∈Rn,y∈{+1,-1}，其中l(wèi)為樣本數(shù)量，n為x的維數(shù)。支持向量機通過訓練尋找到支持向量進而找到一個離兩類間隔最大的分類面，作為兩類樣本的分界，表示為：

wTx+b=0

(1)

其中，wT表示最優(yōu)分類面的法向量；φ(x)表示將x映射到高維空間的核函數(shù)。

數(shù)據(jù)集中用于測試的樣本去掉類別標簽，最后的分類結果與原類別得出的結果進行對分類模型的性能衡量。

當遇到線性不可分的樣本集時，可以通過核函數(shù)的復雜計算，將這些樣本映射到維數(shù)更高的特征空間，在新特征空間中進行訓練找到分類面。這里使用徑向基函數(shù)(RBF)，公式如下：

(2)

參數(shù)σ用于控制RBF的半徑。分類函數(shù)為：

(3)

其中，ai∈[0,C]，C叫做懲罰參數(shù)。

支持向量機的兩個參數(shù)C和σ很大程度上影響了分類性能。然而，傳統(tǒng)上是按照經(jīng)驗給定參數(shù)值。為了提供適當?shù)膮?shù)，提出應用LBA來優(yōu)化支持向量機，該混合算法稱為結合LBA和SVM的混合改進算法(簡稱LBA-SVM)。

2 LBA-SVM的軟件缺陷預測模型

2.1 蝙蝠算法

蝙蝠算法[13-14]是基于模擬蝙蝠捕獲獵物行為的啟發(fā)式群智能優(yōu)化算法，該算法是在受該物種獨特的回聲定位行為的模擬啟發(fā)下提出的。標準蝙蝠算法的結構如下：

fi=fmin+(fmax-fmin)β

(4)

(5)

(6)

其中，β∈[0,1]是一個隨機向量，X*是當前全局最佳位置。根據(jù)所求解的問題類型，在固定λi(或fi)的同時改變fi(或λi)。在實際求解過程中，可以根據(jù)問題的領域大小確定fi的取值，比如使用fmin=0和fmax=100。開始時每只蝙蝠隨機分配頻率，頻率是從[fmin,fmax]平均得出的。局部搜索時，每只蝙蝠的更新公式如下：

Xnew=Xold+εAt

(7)

(8)

其中，α和γ是恒量，α類似于模擬退火算法中冷卻進程表中的冷卻因素。

基于以上分析，蝙蝠搜索算法的主要步驟可以描述如下：

(1)初始化蝙蝠各參數(shù)：位置Xi(0)，速度Vi(0)，響度Ai(0)，脈沖發(fā)射速率ri(0)以及脈沖頻率fi(0)；

(2)按照式5和式6更新蝙蝠個體的速度和位置；

(3)對于每個個體i，產(chǎn)生一個介于(0，1)之間的隨機數(shù)rand1，如果rand1

(4)隨機產(chǎn)生(0,1)之間的隨機數(shù)rand2，如果rand2

(5)更新群體最優(yōu)位置p(t)；

(6)如果滿足結束條件則終止算法，否則轉入步驟2。

2.2 基于Levy飛行的蝙蝠算法

自然界中的動物尋找食物地點的行為具有隨機性，包括搜索方向以及步長。動物的一般活動路徑也是一個隨機的移動過程。后續(xù)的行為方向和步長取決于動物當前所處位置(或狀態(tài))。Levy飛行可以描述為一個運動的實體，通常會進行小步長的移動，能夠偶爾邁出異常大的步子，從而改變一個體系的行為。它的運動方向是隨機的，但是其運動步長是按照冪次率分布的。Levy飛行的一個特點是小步的移動占多數(shù)，但是也會少數(shù)時刻選擇大步的移動，這能夠保證個體搜索的不重復性。

在標準蝙蝠算法中，所有蝙蝠個體的速度更新公式中受到個體當前最優(yōu)位置的影響，導致蝙蝠個體比較容易陷入局部最優(yōu)，而且很難從局部極值點跳出。文中在局部搜索中引入Levy飛行[15-16]，利用Levy飛行隨機游走的特性，利用隨機步長以有偏方式進行隨機移動，使得蝙蝠個體在局部搜索中進行隨機游走，從局部最優(yōu)中跳出，獲得更好的解。蝙蝠個體局部搜索進行萊維飛行根據(jù)代數(shù)決定，到了一定代數(shù)進行一次，這樣既兼顧了原本的局部搜索方案，又不至于陷入局部極值點。根據(jù)經(jīng)驗設置每10代在局部搜索中進行一次萊維飛行。

LBA-SVM軟件缺陷預測模型利用加入萊維飛行局部搜索策略的蝙蝠算法優(yōu)化支持向量機，其流程如圖1所示。

(1)樣本數(shù)據(jù)集初始化。將數(shù)據(jù)集帶入模型，對樣本進行初始化處理。

(2)建立基于SVM的分類模型。將樣本數(shù)據(jù)集帶入支持向量機，通過十折交叉法進行訓練和測試。

(3)利用LBA算法對SVM進行優(yōu)化。初始化LBA中的個體位置為隨機的SVM參數(shù)，將LBA個體位置帶入SVM，通過SVM分類模型，測試參數(shù)的好壞，當?shù)螖?shù)未達到最大迭代次數(shù)時，進行個體位置更新，不斷優(yōu)化參數(shù)選擇。

(4)結果輸出。在代數(shù)達到最大迭代次數(shù)時，測試和評估模型的性能。

圖1 LBA-SVM軟件缺陷預測模型

3 仿真實驗

3.1 數(shù)據(jù)集及評價標準

該數(shù)據(jù)為NASA提供的MDP數(shù)據(jù)集中的四個數(shù)據(jù)集：CM1、KC1、PC1、JM1(http://mdp.ivv.nasa.gov/)。數(shù)據(jù)集信息如表1所示。

表1 數(shù)據(jù)集

分類問題的軟件缺陷預測根據(jù)正確預測和錯誤預測模塊數(shù)統(tǒng)計并計算相應比例來對模型進行評價，實際操作中，通常使用混淆矩陣對結果進行分析。實際上為缺陷模塊，分類結果一致的稱為TP，被誤分為非缺陷模塊的為FN；實際上非缺陷模塊被正確分類的總數(shù)為TN，被誤分為缺陷模塊稱為FP，如表2所示。

表2 混淆矩陣

準確度(accuracy)是最常用的指標，可以理解為預測正確的模塊數(shù)與總軟件模塊數(shù)的比值，如下:

(9)

3.2 實驗參數(shù)

為了驗證文中提出的軟件缺陷預測算法的性能，對其進行了仿真實驗，主要基于MatlabR2013a平臺來開展。使用十折交叉驗證方法設計仿真實驗。每個數(shù)據(jù)集平均分10份,其中9份做訓練,剩余1份對模型性能進行測試,最后取10次預測結果的平均值作為對算法預測能力的評價。

支持向量機兩個參數(shù)的范圍都是(0,1 000)。蝙蝠算法參數(shù)設置如表3所示。

表3 實驗參數(shù)

3.3 實驗結果

實驗結果如表4和圖2所示。

表4 實驗結果

圖2 實驗結果

與傳統(tǒng)的SVM模型、PSO-SVM模型、GA-SVM模型、BA-SVM模型進行比較，通過表4和圖2可以看到，傳統(tǒng)SVM的精度無法到達90%以上，而優(yōu)化過的算法中，準確率都有所提升。說明通過智能算法優(yōu)化參數(shù)，可以有效地提高傳統(tǒng)SVM模型的準確率。通過比較發(fā)現(xiàn)，在改進的模型中，提出的LBA-SVM的準確度明顯優(yōu)于其他算法，說明萊維飛行策略能夠有效地幫助傳統(tǒng)BA算法跳出局部最優(yōu)。利用改進后的算法優(yōu)化軟件缺陷預測模型使得準確度得到了進一步的提升。

4 結束語

支持向量機作為軟件缺陷預測模型的核心，具備很好的分類能力。文中從對支持向量機的兩個關鍵參數(shù)進行優(yōu)化出發(fā)，以提高軟件缺陷預測模型的準確率為目標，改進了標準蝙蝠算法的局部搜索能力，加入了萊維飛行，保證在隔一定代數(shù)后能夠有一次局部最優(yōu)點附近進行隨機游走，減少了蝙蝠算法陷入局部極值的可能性。通過四個數(shù)據(jù)集的實驗對比表明，LBA-SVM顯著提高了準確度。