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

李清霞

東莞理工學(xué)院城市學(xué)院 計(jì)算機(jī)與信息學(xué)院，廣東 東莞 523419

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

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

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

1 烏鴉搜索算法

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

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

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

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

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

2 改進(jìn)的烏鴉搜索算法

改進(jìn)的烏鴉搜索算法利用烏鴉的覓食行為，結(jié)合柯西算子和動(dòng)態(tài)P值，利用變異操作來(lái)生成測(cè)試數(shù)據(jù)集?？挛魉阕釉谏尚挛恢脮r(shí)考慮烏鴉的初始位置，由于柯西的隨機(jī)數(shù)有時(shí)可能很高，因此它可以防止解陷入局部最優(yōu)。動(dòng)態(tài)P的值有助于搜索到最優(yōu)解，故柯西算子和動(dòng)態(tài)P值方面的改進(jìn)有助于探索全局最優(yōu)解，并取得良好的效果。

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

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

式中τ是最大相對(duì)誤差，這有助于用更加廣泛地使用測(cè)試用例來(lái)測(cè)試程序。

相對(duì)誤差隨著測(cè)試用例值的變化而增加，即當(dāng)選擇適當(dāng)?shù)臏y(cè)試用例時(shí)，相對(duì)誤差會(huì)增加。

2.2 算法實(shí)現(xiàn)

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

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

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

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

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

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

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

圖1 為改進(jìn)算法的流程，算法偽代碼如下：

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

圖1 改進(jìn)的烏鴉搜索算法流程

3 實(shí)驗(yàn)結(jié)果與分析

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

3.1 基準(zhǔn)程序

針對(duì)實(shí)驗(yàn)測(cè)試，使用了10 個(gè)基準(zhǔn)程序來(lái)驗(yàn)證所有對(duì)比算法的效果，這10 個(gè)基準(zhǔn)程序見(jiàn)表1。

表1 基準(zhǔn)程序詳細(xì)信息

3.2 評(píng)價(jià)標(biāo)準(zhǔn)

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

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

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

表2 實(shí)驗(yàn)參數(shù)表

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

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

3.4 結(jié)果分析

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

表4 各算法的變異得分

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

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

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

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

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

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

4 結(jié)論

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

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