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

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

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

0 引言

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

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

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

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

1 IAG-ABC算法

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

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

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

α=arcsin(favg/fmax)

(1)

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

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

(2)

(3)

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

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

(4)

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

(5)

(6)

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

觀察蜂根據公式(7)選擇待開采蜜源，其中，Fi表示的是第i個蜜源對應的適應度值。

(7)

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

xij=xminj+R×(xmaxj-xminj)

(8)

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

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

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

2.1 適應度函數的設計

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

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

(9)

F=AL(X)+BD(X)

(10)

2.2 算法流程

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

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

Begin

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

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

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

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

5)進行交叉和變異操作產生新種群并計算個體的適應度值；

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

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

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

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

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

End

3 實驗及結果分析

3.1 實驗對象

本文對標準遺傳算法(GA)、文獻[6]中的自適應遺傳(IAGA)算法和本文的IAG-ABC算法進行性能對比，實驗均在MATLAB R2016b上實現。采用5個常用測試基準函數，其信息如表1所示。

表1 測試基準函數信息表

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

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

表2 被測程序信息表

3.2 實驗結果分析

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

表3 三種算法在測試基準函數上的實驗結果

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

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

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

圖2 算法在生成測試用例中所需時間對比

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

4 結束語

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