改進的烏鴉搜索算法在軟件測試用例生成中的應(yīng)用

李清霞

東莞理工學院城市學院 計算機與信息學院，廣東 東莞 523419

軟件測試是對軟件應(yīng)用程序進行評估，以確定其是否存在缺陷的過程，這個過程確保了軟件產(chǎn)品的質(zhì)量。但是軟件測試是一個相當昂貴的過程，其占據(jù)了軟件開發(fā)成本的50%[1]。在軟件測試過程中，測試用例的生成是最為關(guān)鍵的一步。測試用例以前以手工生成為主，但后來為了提高測試用例的質(zhì)量以及節(jié)省時間和資源，手工生成測試用例的方法逐步被自動化生成測試用例所取代[2]。一般情況，新的測試用例生成可以通過原測試用例進行變異形成。因此，只需要在原測試用例的基礎(chǔ)上自動變異便可以實現(xiàn)自動化生成測試用例[3]。

軟件行業(yè)的自動化測試已經(jīng)將測試效率從20%提高到80%[4]。一般情況下，自動化測試采用啟發(fā)式算法自動或半自動地生成測試用例，而且還可以提供測試的分支覆蓋，以實現(xiàn)更快的測試速度、減少測試數(shù)據(jù)等[5]。為了實現(xiàn)軟件測試中測試用例生成的自動化，將啟發(fā)式算法如智能仿生算法應(yīng)用于自動化測試中以生成和優(yōu)化測試用例[6]。例如，采用蟻群算法(ant clony optimization，ACO)對測試用例進行生成和優(yōu)化后，測試用例減少了62%[7]。

除了蟻群算法，遺傳算法(genetic algorithm，GA)、螢火蟲算法(firefly algorithm，F(xiàn)A)、人工蜂群算法(artificial bee colony algorithm，ABC)和粒子群算法(particle swarm optimization，PSO)等基于啟發(fā)式技術(shù)的智能仿生算法也被用于軟件自動化測試中[8]。Bueno 等[9]提出了一種基于遺傳算法和模擬退火的隨機測試用例生成方法，該方法利用了測試集的差異，成功地提高了測試用例的變異效率和覆蓋率。Srivatsava 等[10]引入了螢火蟲算法，結(jié)合螢火蟲的行為，利用圖歸約方法產(chǎn)生最佳測試數(shù)據(jù)序列，該方法提供了測試路徑，可用于昂貴的測試過程。Lam 等[11]提出了利用人工蜂群算法進行測試數(shù)據(jù)集優(yōu)化的方法，該方法適用于小規(guī)模程序。為了減少測試用例的數(shù)量，粒子群優(yōu)化算法也被用于軟件自動化測試中[12]。針對軟件測試用例自動化生成的效率問題，本文提出了一種改進的烏鴉搜索算法(improved crow search algorithm，ICSA)，利用其變異算子生成有效且優(yōu)質(zhì)的測試用例以實現(xiàn)自動化軟件測試。該算法引入變異敏感度測試的概念[13]，用相對誤差作為變異敏感度的度量，克服傳統(tǒng)軟件測試的缺點。然后采用相對誤差作為算法的適應(yīng)度函數(shù)，利用柯西變異算子避免局部搜索最優(yōu)。最后，將該算法與其他啟發(fā)式算法(遺傳算法、粒子群算法、蟻群算法和烏鴉搜索算法)進行了實驗比較。

1 烏鴉搜索算法

烏鴉以其聰明才智而聞名，烏鴉可以觀察到其他鳥類的食物隱藏方式。烏鴉由于記憶力很好，在觀察了其他鳥的活動后，可以偷吃其他鳥的食物。烏鴉也知道如何利用其盜竊經(jīng)驗來避免食物被偷。利用烏鴉覓食的行為，Askarzadeh[14]提出了烏鴉搜索算法。

1)烏鴉j不知道后面跟著烏鴉i，在這種情況下，烏鴉i會找到烏鴉j的食物隱藏位置。因此烏鴉i將得到一個新的位置，這個位置由以下等式給出

2)烏鴉j知道烏鴉i在跟蹤它。因此，烏鴉j將通過欺騙烏鴉i來保護它的食物來源。為了躲避烏鴉i跟蹤，烏鴉j將會隨機進入搜索空間的位置來愚弄烏鴉i：

根據(jù)式(1)和(2)，烏鴉的位置會在搜索空間中更新。通過對新位置的適應(yīng)度函數(shù)進行評價，如果新位置的適應(yīng)度優(yōu)于原來位置的適應(yīng)度，則就用新的位置更新原來的位置。

為了解決上述問題，本文提出了一種改進的烏鴉搜索算法。該算法使用已被應(yīng)用于許多啟發(fā)式算法的柯西變異算子[15]代替飛行長度，并將P設(shè)置為第i代迭代時每個群體可產(chǎn)生的最大相對誤差。柯西變異算子的引入有效地提高了ICSA算法的搜索性能和效率。

2 改進的烏鴉搜索算法

改進的烏鴉搜索算法利用烏鴉的覓食行為，結(jié)合柯西算子和動態(tài)P值，利用變異操作來生成測試數(shù)據(jù)集。柯西算子在生成新位置時考慮烏鴉的初始位置，由于柯西的隨機數(shù)有時可能很高，因此它可以防止解陷入局部最優(yōu)。動態(tài)P的值有助于搜索到最優(yōu)解，故柯西算子和動態(tài)P值方面的改進有助于探索全局最優(yōu)解，并取得良好的效果。

2.1 適應(yīng)度函數(shù)

在改進的烏鴉搜索算法中，利用柯西變異算子來對測試用例進行變異，而適應(yīng)度函數(shù)的目標就是評價這些變異優(yōu)劣。采用由Hook 等[13]提出的相對誤差適應(yīng)度函數(shù)來檢驗算法中是否存在變異。設(shè)Po(t)和Pm(t)分別為變異前和變異后測試用例生成的結(jié)果，則

式中τ是最大相對誤差，這有助于用更加廣泛地使用測試用例來測試程序。

相對誤差隨著測試用例值的變化而增加，即當選擇適當?shù)臏y試用例時，相對誤差會增加。

2.2 算法實現(xiàn)

本節(jié)討論如何實現(xiàn)改進的烏鴉搜索算法以完成最佳測試用例生成和變異檢測。設(shè)烏鴉對應(yīng)于d維搜索空間中的測試用例，其中d對應(yīng)于測試用例的維數(shù)，烏鴉種群的大小對應(yīng)于測試用例的數(shù)量(N)。

測試用例在搜索空間中的位置按照前面的規(guī)則進行定義。測試用例的初始數(shù)據(jù)是隨機初始化的，利用適應(yīng)度函數(shù)對原始位置的測試用例進行評價，即適應(yīng)度函數(shù)檢驗初始種群的測試用例是否能產(chǎn)生較高的相對誤差。適應(yīng)度函數(shù)在第i次迭代時檢查與初始種群的最大相對誤差，然后根據(jù)烏鴉搜索算法，選擇隨機測試用例，并根據(jù)式(3)更新其位置：

式中ri和rj是均勻分布在0 和1 之間的隨機數(shù)。最大感知概率Pm對應(yīng)于在第i次迭代時產(chǎn)生具有最高相對誤差的測試用例，然后更新目前位置并存儲起來。

使用式(4)生成測試用例的新位置：

式中C是從柯西分布中抽取的隨機數(shù)。柯西隨機數(shù)有時非常大，從而幫助烏鴉跳出局部搜索空間。如果利用柯西分布確定烏鴉位置超過mj,it，則利用緩存中優(yōu)化后的測試用例對程序進行測試。

為了更好評價測試用例的變異效果，采用變異得分的概念來衡量算法應(yīng)用于軟件測試中的效果。變異得分可根據(jù)被終止的變異體個數(shù)q 和變異體總數(shù)s 計算得出，公式為

式中：Q表示程序；R表示測試數(shù)據(jù)集。

圖1 為改進算法的流程，算法偽代碼如下：

設(shè)置群大小和迭代次數(shù)，初始化烏鴉的位置和緩存。

圖1 改進的烏鴉搜索算法流程

3 實驗結(jié)果與分析

在軟件環(huán)境為MATLAB 2018b，硬件環(huán)境為8 GB 內(nèi)存、64 位Intel(R)I5 2.30 GHz 處理器的條件下對該算法進行了仿真實驗。然后將本文的算法與遺傳算法、粒子群算法、蟻群算法和烏鴉搜索算法的仿真結(jié)果進行了比較。

3.1 基準程序

針對實驗測試，使用了10 個基準程序來驗證所有對比算法的效果，這10 個基準程序見表1。

表1 基準程序詳細信息

3.2 評價標準

變異得分是一種性能度量，它提供了如何有效地檢測或終止變異的數(shù)量。變異得分可以衡量啟發(fā)式算法應(yīng)用于軟件測試中的效果，因此本文采用式(5)來計算變異得分作為比較算法應(yīng)用于軟件測試性能的評估指標。

3.3 參數(shù)設(shè)置

表2 給出了實驗測試參數(shù)，其中種群的個體成員是指GA 中的染色體、PSO 中的粒子、ACO中的螞蟻、CSA 和ICSA 中的烏鴉。對于較小的程序，設(shè)置最大迭代次數(shù)it,m=300。對于較大的程序，由于其執(zhí)行時間較長，所以對于其最大迭代次數(shù)it,m設(shè)置為100 或50。

表2 實驗參數(shù)表

表3 給出了每個算法的參數(shù)，其中一些參數(shù)取自于文獻[16]。

表3 算法參數(shù)設(shè)置

3.4 結(jié)果分析

經(jīng)過實驗測試，表4 和圖2 給出了各種對比算法的變異得分及得分分析。通過對比可以看出本文算法相對于其他算法在軟件測試方面的改進。

表4 各算法的變異得分

圖2 各算法的變異得分分析

從表4 和圖2 得到的結(jié)果表明，對于程序binSearch、calDay 和GCD，ICSA 算法獲得了大約98 的高變異分數(shù)。然而，針對OdeRK4 程序的最低得分92 分也高于或等于其他算法對于所有程序的最高得分。從實驗結(jié)果可以看出，遺傳算法在所有算法中的變異得分都很低，即使是CSA 算法的變異得分，也都高于GA、PSO 和ACO。由于ICSA 算法是針對CSA 算法的改進，所以ICSA算法在所有算法中變異得分最高也屬于正常。這是因為ICSA 算法在柯西變異算子的幫助下防止烏鴉陷入局部最優(yōu)搜索，而傳統(tǒng)算法無法解決解陷入局部最優(yōu)的問題。另外，適應(yīng)度函數(shù)的強度以及烏鴉搜索算法的均衡搜索模式在很大程度上也有助于提高變異得分。

3.5 算法復(fù)雜度分析

循環(huán)復(fù)雜度是指程序的源代碼中量測線性獨立路徑的個數(shù)。由于本文算法是應(yīng)用于軟件測試中，所以利用循環(huán)復(fù)雜度對所有對比算法的復(fù)雜度進行了評估。表5 給出了所有對比算法的循環(huán)復(fù)雜度。

表5 算法循環(huán)復(fù)雜度

復(fù)雜度評估結(jié)果表明，與其他算法相比，ICSA算法具有最小的循環(huán)復(fù)雜度即最少的線性獨立路徑數(shù)，因而易于開發(fā)和測試。

4 結(jié)論

一個有效的優(yōu)化算法能夠提供最優(yōu)的測試用例數(shù)，防止陷入局部最優(yōu)。本文所提出的ICSA算法利用柯西變異算子自動生成最優(yōu)的測試數(shù)據(jù)集，解決了解陷入局部優(yōu)的問題。在ICSA 算法中，采用了相對誤差作為適應(yīng)度函數(shù)，通過識別有效的測試用例來提高變異得分。實驗結(jié)果表明，所提出的ICSA 算法的變異得分大幅高于用于對比測試的GA、PSO、ACO 和CSA 算法。

與其他算法相比，ICSA 算法具有更好的效果。因此，ICSA 算法可以用于軟件測試中有效測試用例的進化。