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

李清霞

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

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

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

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

1 烏鴉搜索算法

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

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

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

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

為了解決上述問題，本文提出了一種改進的烏鴉搜索算法。該算法使用已被應用于許多啟發式算法的柯西變異算子[15]代替飛行長度，并將P設置為第i代迭代時每個群體可產生的最大相對誤差?？挛髯儺愃阕拥囊胗行У靥岣吡薎CSA算法的搜索性能和效率。

2 改進的烏鴉搜索算法

改進的烏鴉搜索算法利用烏鴉的覓食行為，結合柯西算子和動態P值，利用變異操作來生成測試數據集?？挛魉阕釉谏尚挛恢脮r考慮烏鴉的初始位置，由于柯西的隨機數有時可能很高，因此它可以防止解陷入局部最優。動態P的值有助于搜索到最優解，故柯西算子和動態P值方面的改進有助于探索全局最優解，并取得良好的效果。

2.1 適應度函數

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

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

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

2.2 算法實現

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

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

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

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

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

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

式中：Q表示程序；R表示測試數據集。

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

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

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

3 實驗結果與分析

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

3.1 基準程序

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

表1 基準程序詳細信息

3.2 評價標準

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

3.3 參數設置

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

表2 實驗參數表

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

表3 算法參數設置

3.4 結果分析

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

表4 各算法的變異得分

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

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

3.5 算法復雜度分析

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

表5 算法循環復雜度

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

4 結論

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

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