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

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

0 引言

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

目前，在已有的基于遺傳算法的測(cè)試用例生成研究中，張巖、鞏敦衛(wèi)[2]提出了一種通過改進(jìn)適應(yīng)度函數(shù)來增加稀有數(shù)據(jù)的適應(yīng)度值的方法提高了遺傳算法生成測(cè)試用例的效率。夏春艷[3]等人從穿過節(jié)點(diǎn)的難易程度出發(fā)設(shè)計(jì)適應(yīng)度函數(shù)，采用遺傳算法實(shí)現(xiàn)路徑覆蓋測(cè)試用例生成。丁蕊[4]等人基于遺傳算法提出關(guān)鍵點(diǎn)路徑表示法改進(jìn)算法適應(yīng)度函數(shù)，以快速生成路徑覆蓋測(cè)試數(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ì)路徑覆蓋的測(cè)試需求設(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表示局部搜索步長(zhǎng)，計(jì)算方法如式(6)所示。本文用當(dāng)前個(gè)體與目前最優(yōu)個(gè)體之間的空間歐式距離表示EDij。若EDij的值越大，則兩個(gè)個(gè)體之間的差異越大，則需要自適應(yīng)地增大搜索步長(zhǎ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算法的測(cè)試用例生成

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

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

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

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

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

(9)

F=AL(X)+BD(X)

(10)

2.2 算法流程

輸入：初始化種群TN，IAG-ABC算法中遺傳算法的最大迭代次數(shù)N、系數(shù)Pc1，Pc2，Pm1，Pm2的初始值、種群規(guī)模，搜索維度D(測(cè)試用例輸入?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è)常用測(cè)試基準(zhǔn)函數(shù)，其信息如表1所示。

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

其中，F(xiàn)1和F2是單峰函數(shù)，用于檢驗(yàn)算法的尋優(yōu)精度；F3和F4是多峰函數(shù)，用于檢測(cè)算法的全局尋優(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算法在測(cè)試用例生成上的有效性，本文選取了軟件測(cè)試中常用的5個(gè)工業(yè)程序[14]并采用GA、IAGA和IAG-ABC來生成測(cè)試用例，被測(cè)程序的基本信息如表2所示。

表2 被測(cè)程序信息表

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

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

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

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

4 結(jié)束語

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