基于IAG-ABC算法的路徑覆蓋測試用例生成技術(shù)

張 娜, 張 唯, 徐 璐, 吳 彪2,包曉安

(1.浙江理工大學(xué) 信息學(xué)院,杭州 310018; 2.山口大學(xué) 東亞研究科,日本 山口 753-8514)

0 引言

隨著軟件功能的不斷強(qiáng)大，軟件復(fù)雜度日益提高，軟件測試過程中所需的測試用例數(shù)量也不斷地增大。生成量少且覆蓋程度高的測試用例成為了提高軟件測試的效率的關(guān)鍵。遺傳算法因其簡單而具有良好的搜索性能在解決測試用例生成問題上得到了廣泛的應(yīng)用[1]。

目前，在已有的基于遺傳算法的測試用例生成研究中，張巖、鞏敦衛(wèi)[2]提出了一種通過改進(jìn)適應(yīng)度函數(shù)來增加稀有數(shù)據(jù)的適應(yīng)度值的方法提高了遺傳算法生成測試用例的效率。夏春艷[3]等人從穿過節(jié)點(diǎn)的難易程度出發(fā)設(shè)計(jì)適應(yīng)度函數(shù)，采用遺傳算法實(shí)現(xiàn)路徑覆蓋測試用例生成。丁蕊[4]等人基于遺傳算法提出關(guān)鍵點(diǎn)路徑表示法改進(jìn)算法適應(yīng)度函數(shù)，以快速生成路徑覆蓋測試數(shù)據(jù)。Xiao an Bao[5]等根據(jù)海明距離衡量個(gè)體相似度，量化計(jì)算種群多樣性并設(shè)計(jì)自適應(yīng)的交叉和變異算子，增強(qiáng)遺傳算法的搜索能力。高雪笛[6]等設(shè)計(jì)自適應(yīng)交叉、變異算子并引入模擬退火的個(gè)體保留機(jī)制，以加速數(shù)據(jù)優(yōu)化過程。

但是，已有的遺傳算法存在易陷入局部最優(yōu)解、未充分利用系統(tǒng)的反饋信息的缺陷。而人工蜂群算法能夠充分考慮系統(tǒng)的反饋信息從而更易搜索到全局最優(yōu)解，但存在初始搜索緩慢、盲目搜索的缺陷[7-10]。

綜上所述，本文提出一種自適應(yīng)遺傳-人工蜂群(IAG-ABC)算法。首先，改進(jìn)遺傳算法的遺傳策略，以提高遺傳算法后期種群多樣性，避免陷入局部最優(yōu)解；其次，設(shè)計(jì)一種新的局部搜索策略，以提高蜂群算法的局部搜索效率；最后，在初期通過自適應(yīng)遺傳算法得到解的分布，在后期通過改進(jìn)的人工蜂群算法尋找最優(yōu)解。針對(duì)路徑覆蓋的測試需求設(shè)計(jì)適應(yīng)度函數(shù)。從而將問題轉(zhuǎn)化成通過適應(yīng)度函數(shù)引導(dǎo)算法搜尋滿足適應(yīng)度函數(shù)的最優(yōu)解。

1 IAG-ABC算法

IAG-ABC算法整體分為改進(jìn)遺傳算階段和改進(jìn)人工蜂群算法階段。

1.1 IAG-ABC中的遺傳算法階段

IAG-ABC中的遺傳算法部分采用實(shí)數(shù)編碼的形式，為了降低優(yōu)良基因被破壞的風(fēng)險(xiǎn)，將輪盤賭和優(yōu)質(zhì)個(gè)體保留法相結(jié)合的方式進(jìn)行選擇。在交叉和變異操作中，交叉率Pc和變異率Pm是能夠影響算法的收斂和尋優(yōu)能力的重要參數(shù)。標(biāo)準(zhǔn)的遺傳算法中，無法根據(jù)當(dāng)前種群的多樣性選擇靈活地選擇交叉還是變異。本文引入?yún)?shù)α來度量進(jìn)化過程中的種群的多樣性，計(jì)算方法如公式(1)所示：

α=arcsin(favg/fmax)

(1)

其中：favg表示當(dāng)前種群中個(gè)體適應(yīng)度值的平均值，fmax表示當(dāng)前種群中最優(yōu)個(gè)體的適應(yīng)度值。同時(shí)，用反正弦函數(shù)能非線性地度量當(dāng)前種群的適應(yīng)度值的分散程度，用于直觀地描述種群多樣性。

本文設(shè)計(jì)的Pc和Pm計(jì)算公式如下式(2)和式(3)所示。其中，系數(shù)Pc1，Pc2，Pm1，Pm2的取值區(qū)間為(0,1)，可以在優(yōu)化過程中調(diào)整。

(2)

(3)

1.2 IAG-ABC中的人工蜂群算法階段

在標(biāo)準(zhǔn)的ABC算法中，雇傭蜂的開采(局部搜索)方式如式(4)所示，其中，其中，i,k∈{i=1,2,…N}且i≠k,j∈{i=1,2,…,D}，R為[-1,1]中的隨機(jī)數(shù)[11]。

(4)

因此，局部搜索過程中存在一定的隨機(jī)性，這是算法的初期搜索效率不高的主要原因。已有的研究表明，鑒檔案精英學(xué)習(xí)[12]的方法中的精英個(gè)體引導(dǎo)策略能夠有效提高算法的搜索效率。本文借鑒其思想，設(shè)計(jì)了基于當(dāng)前最優(yōu)解引導(dǎo)的自適應(yīng)局部搜索策略，如式(5)所示：

(5)

(6)

其中：EDij表示局部搜索步長，計(jì)算方法如式(6)所示。本文用當(dāng)前個(gè)體與目前最優(yōu)個(gè)體之間的空間歐式距離表示EDij。若EDij的值越大，則兩個(gè)個(gè)體之間的差異越大，則需要自適應(yīng)地增大搜索步長，提高搜索效率。反之，則需要自適應(yīng)地縮小搜索范圍。若新蜜源的適應(yīng)度值大于舊蜜源，則對(duì)舊蜜源進(jìn)行替換，否則繼續(xù)進(jìn)行局部搜索。

觀察蜂根據(jù)公式(7)選擇待開采蜜源，其中，F(xiàn)i表示的是第i個(gè)蜜源對(duì)應(yīng)的適應(yīng)度值。

(7)

當(dāng)一個(gè)蜜源被開采后殆盡(達(dá)到最大搜索次數(shù)limit)時(shí)進(jìn)入偵查蜂階段，采用如下公式(8)尋找新蜜源。其中，xij為新蜜源的第j維分量，j∈{i=1,2,…,D}，R是范圍在(0,1)內(nèi)的一個(gè)隨機(jī)數(shù)，xmaxj和xminj分別為蜜源的第j維分量的上下界。

xij=xminj+R×(xmaxj-xminj)

(8)

2 基于IAG-ABC算法的測試用例生成

IAG-ABC算法并于路徑覆蓋的測試用例生成。如圖(1)所示，是基于IAG-ABC算法的測試用例自動(dòng)生成的模型圖。

圖1 基于IAG-ABC算法的測試用例生成模型

2.1 適應(yīng)度函數(shù)的設(shè)計(jì)

一般地，評(píng)判某個(gè)測試用例數(shù)據(jù)對(duì)程序路徑的覆蓋程度的標(biāo)準(zhǔn)有分支距離或者層接近度。本文按照Mcdermid[13]所提的插樁法對(duì)程序進(jìn)行插樁，然后執(zhí)行測試用例中的輸入數(shù)據(jù)，以獲取測試用例的分支距離和層接近度的信息。

具體步驟如下：假設(shè)被測程序中有n個(gè)分支謂詞和m個(gè)關(guān)鍵節(jié)點(diǎn)，該被測程序有N個(gè)輸入?yún)?shù)，則測試用例有D維，X=(x1,x2,…，xD)，則需要在第i個(gè)分支謂詞前插入分支距離函數(shù)bdi(x1,x2, …，xD)，i∈[1,n]，將測試用例X的分支距離函數(shù)值記為BD(X)，計(jì)算方法如式(9)所示，BD(X)的值越小表示，該用例的分支覆蓋強(qiáng)度越高；在程序的每個(gè)關(guān)鍵節(jié)點(diǎn)前插入計(jì)數(shù)語句，用于統(tǒng)計(jì)測試用例X所經(jīng)過的節(jié)點(diǎn)個(gè)數(shù)，最后與完全覆蓋目標(biāo)路徑所需經(jīng)過的節(jié)點(diǎn)個(gè)數(shù)相減，取差值的絕對(duì)值記為層接近度函數(shù)AL(X)，AL(X)的值越小，表示該測試用例穿越目標(biāo)路徑的節(jié)點(diǎn)個(gè)數(shù)越多，路徑覆蓋強(qiáng)度越強(qiáng)。最后，適應(yīng)度值F按公式(10)進(jìn)行計(jì)算，F(xiàn)的值越小，表明測試用例的覆蓋目標(biāo)路徑的程度越高。

(9)

F=AL(X)+BD(X)

(10)

2.2 算法流程

輸入：初始化種群TN，IAG-ABC算法中遺傳算法的最大迭代次數(shù)N、系數(shù)Pc1，Pc2，Pm1，Pm2的初始值、種群規(guī)模，搜索維度D(測試用例輸入?yún)?shù)的個(gè)數(shù))；IAG-ABC算法中人工蜂群算法的蜜蜂總數(shù)、最大搜索次數(shù)limit和最大迭代次數(shù)M；

輸出：所搜過程中的最優(yōu)解T。

Begin

1)按照公式(10)計(jì)算初始種群中個(gè)體的F值；

2)采用輪盤賭和最優(yōu)個(gè)體保留法進(jìn)行選擇；

3)按照式(1)計(jì)算α的值；

4)根據(jù)α的值，按照式(2)和(3)計(jì)算Pc和Pm，并確定交叉和變異的先后順序；

5)進(jìn)行交叉和變異操作產(chǎn)生新種群并計(jì)算個(gè)體的適應(yīng)度值；

6)記錄種群最優(yōu)解，判斷是否達(dá)到最大迭代次數(shù)N，若是則執(zhí)行步驟7)；否則，返回步驟2)；

7)按照公式(5)進(jìn)行局部搜索，尋找適應(yīng)度值更高的蜜源代替原蜜源；

8)按照公式(7)進(jìn)行選擇蜜源，在其附近根據(jù)公式(5)開采；

9)某蜜源開采殆盡時(shí)，根據(jù)公式(8)進(jìn)行蜜源位置的重置；

10)記錄優(yōu)質(zhì)蜜源，判斷人工蜂群算法的迭代次數(shù)是否大于等于M，是則輸出T，算法終止，否則返回步驟6)。

End

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

3.1 實(shí)驗(yàn)對(duì)象

本文對(duì)標(biāo)準(zhǔn)遺傳算法(GA)、文獻(xiàn)[6]中的自適應(yīng)遺傳(IAGA)算法和本文的IAG-ABC算法進(jìn)行性能對(duì)比，實(shí)驗(yàn)均在MATLAB R2016b上實(shí)現(xiàn)。采用5個(gè)常用測試基準(zhǔn)函數(shù)，其信息如表1所示。

表1 測試基準(zhǔn)函數(shù)信息表

其中，F(xiàn)1和F2是單峰函數(shù)，用于檢驗(yàn)算法的尋優(yōu)精度；F3和F4是多峰函數(shù)，用于檢測算法的全局尋優(yōu)能力；F5則是一個(gè)復(fù)雜的單峰函數(shù)，用于評(píng)價(jià)算法是否易于陷入局部最優(yōu)解。由于遺傳算法的變異率和交叉率沒有恒定的參數(shù)，本文借鑒Schaffer等[15]人的研究，在以上兩個(gè)實(shí)驗(yàn)中設(shè)置GA算法的交叉率設(shè)為0.9，變異率設(shè)為0.2；IAGA和IAG-ABC中的交叉率計(jì)算公式中的Pc1=0.8,Pc2=0.6，變異率計(jì)算公式中的Pm1=0.05,Pm2=0.005；三種算法的搜索維度均為30。

為了驗(yàn)證本文所提的IAG-ABC算法在測試用例生成上的有效性，本文選取了軟件測試中常用的5個(gè)工業(yè)程序[14]并采用GA、IAGA和IAG-ABC來生成測試用例，被測程序的基本信息如表2所示。

表2 被測程序信息表

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

在三種算法求解函數(shù)最小值優(yōu)化問題的實(shí)驗(yàn)中，為了避免實(shí)驗(yàn)過程中存在的隨機(jī)性，分別對(duì)每個(gè)函數(shù)進(jìn)行了50次實(shí)驗(yàn)，然后記錄實(shí)驗(yàn)過程中的均值、方差以及達(dá)到規(guī)定精度所需的平均時(shí)間的平均值，見表3。

表3 三種算法在測試基準(zhǔn)函數(shù)上的實(shí)驗(yàn)結(jié)果

從表3中的數(shù)據(jù)可以看出，相對(duì)于GA和IAGA算法，IAG-ABC算法所尋得的平均最優(yōu)解更接近理論最優(yōu)、方差更小、能在更少的時(shí)間內(nèi)達(dá)到規(guī)定的精度，表明算法的性能更優(yōu)且更加穩(wěn)定，證明了本文所提改進(jìn)策略的有效性。

表4所示是三種算法在生成路徑覆蓋的測試用例過程中所需的平均迭代次數(shù)和所生成的測試用例的路徑覆蓋率的結(jié)果對(duì)比，圖2是記錄三種算法運(yùn)行50次生成路徑覆蓋的測試用例所需時(shí)間分布的箱形圖。

表4 三種算法的測試用例生成性能對(duì)比

圖2 算法在生成測試用例中所需時(shí)間對(duì)比

由表4和圖2可知，IAG-ABC算法生成測試用例所需的迭代次數(shù)更少且生成的測試用例的覆蓋率更高，且所需要的時(shí)間更短。

4 結(jié)束語

本文分別對(duì)標(biāo)準(zhǔn)的遺傳算法和人工蜂群算法進(jìn)行了改進(jìn)，在改進(jìn)之后將兩者進(jìn)行優(yōu)勢互補(bǔ)，將遺傳算法的運(yùn)行結(jié)果作為蜂群算法的初始種群，使用改進(jìn)的人工蜂群算法進(jìn)行最優(yōu)解的搜索。通過實(shí)驗(yàn)證明了本文所提的IAGA-ABC算法相對(duì)于已有的IAGA算法在收斂速度和全局搜索能力上的優(yōu)勢，有助于提高路徑覆蓋的測試用例生成效率和路徑覆蓋率。目前，已有許多研究提出了關(guān)于遺傳算法的各種改進(jìn)，而混合算法還存在一定的研究空間。在未來的研究中，將會(huì)考慮融合其他智能搜索算法，以提高測試用例生成的效率。