黃陳輝 吳海濤 阮江濤 錢 程

（上海師范大學(xué)信息與機(jī)電工程學(xué)院 上海 200234）

1 引言

軟件測(cè)試自動(dòng)化是對(duì)程序自動(dòng)生成測(cè)試數(shù)據(jù)，近些年越來(lái)越引起計(jì)算機(jī)研究員的關(guān)注。智能尋優(yōu)算法［1］能更好、更快地解決復(fù)雜的軟件測(cè)試問(wèn)題，如蟻群算法［2］、模擬退火［3］、遺傳算法［4］等。其中遺傳算法使用最為廣泛，因?yàn)樗梢愿咝幚砣謨?yōu)化、多峰值等問(wèn)題［5］。

遺傳算法解決測(cè)試用例自動(dòng)生成問(wèn)題是學(xué)者們爭(zhēng)先研究的熱點(diǎn)。例如鄭超群等提出改進(jìn)的交叉、變異算子，增加種群多樣性來(lái)避免過(guò)早收斂［6］，但改進(jìn)效果不明顯；丁蕊等［7］使用啟發(fā)式搜索來(lái)提高測(cè)試用例生成效率，但算法并行性沒(méi)有充分利用，性能改進(jìn)不明顯；高雪笛等［8］改進(jìn)算法適應(yīng)度函數(shù)設(shè)計(jì)，提高算法收斂速度，但仍不能很好解決大規(guī)模計(jì)算量的問(wèn)題，使算法迭代后期種群失去多樣性。同時(shí)他們忽略了遺傳算法對(duì)初始種群有一定依賴性，隨機(jī)生成方式已限制了尋找最優(yōu)解過(guò)程［9］。針對(duì)上述方法不足，本文設(shè)計(jì)了以下改進(jìn)策略：1）反向?qū)W習(xí)機(jī)制初始化種群，使得初始種群更靠近最優(yōu)解；2）改進(jìn)適應(yīng)度函數(shù)設(shè)計(jì)方式；3）使用混沌序列優(yōu)化遺傳算子的交叉、變異操作，提高算法的全局尋優(yōu)能力。

2 相關(guān)背景知識(shí)

2.1 反向數(shù)字

反向?qū)W習(xí)概念是Tizhoosh. H 于2005 年提出的，并證明它在現(xiàn)有學(xué)習(xí)方法的上的有效性［10］。假設(shè)正在搜索估算x（給定問(wèn)題的解），那么先應(yīng)該計(jì)算相反的數(shù)字。

定義1（反向數(shù)字）

a，b分別是 [a，b]區(qū)間中的上下限，x是源數(shù)，x~ 是源數(shù)的反向數(shù)字。

基于反向?qū)W習(xí)定義如下：假設(shè)f(x)為適應(yīng)度函數(shù)，g為評(píng)價(jià)函數(shù)，為x∈[a，b]的反向值，每次迭 代 中 計(jì) 算 的 是f(x) 與的 值 ，當(dāng)時(shí)，學(xué)習(xí)繼續(xù)，否則用。

考慮反向個(gè)體，選中更靠近的作為種群最初個(gè)體，那就是每個(gè)個(gè)體都離最優(yōu)解更近一步。

2.2 Logistic映射

混沌的遍歷性可以根據(jù)自己規(guī)律遍歷非重復(fù)的所有狀態(tài)［11～12］這一特性可以用來(lái)避免陷入局部最小解。本文使用logistic映射生成混沌序列。Logistic混沌映射概述如下。

Logistic 映射是一個(gè)一維映射，卻具有混沌模型所擁有特征和性質(zhì)。方程如式（2）所示：

式中μ為控制參數(shù)，且0 ≤μ≤ 4，0 ≤x≤ 1。該模型能準(zhǔn)確表現(xiàn)出生物群體數(shù)的波動(dòng)與時(shí)代變化的關(guān)系。若n表示進(jìn)化代數(shù)，那么xn表示第n代的出生數(shù)，xn+1表示第n+1 代的出生數(shù)。μ∈（3.56994，4］，映射處于混沌狀態(tài)。映射不變集為區(qū)間（0，1）。本文使用參數(shù)值為μ=4。

2.3 遺傳算法

遺傳算法在實(shí)際應(yīng)用中需要目標(biāo)語(yǔ)言的合理子集［13］。因此將遺傳算法形式化表示為

表1 符號(hào)的含義

3 基于混沌遺傳算法生成測(cè)試用例

3.1 測(cè)試用例生成模型

測(cè)試用例集表示為測(cè)試用例ti集合T。給定|T|=n，有T={t1，t2，…，tn}。其方法模型如下：

圖1 混沌遺傳算法的測(cè)試用例自動(dòng)生成方法模型

首先分析被測(cè)程序，生成T的結(jié)構(gòu)和屬性說(shuō)明。其次，插入變量動(dòng)態(tài)跟蹤T的行為，具體操作：程序分支子關(guān)鍵點(diǎn)（即分支節(jié)點(diǎn)的兩個(gè)互為兄弟的后置關(guān)鍵點(diǎn)）插裝變量，賦初值1，當(dāng)執(zhí)行經(jīng)過(guò)該分支節(jié)點(diǎn)，值賦值為0。測(cè)試數(shù)據(jù)執(zhí)行路徑101010，101001，100110，100101，011010，011001，010110，010101。測(cè)試反饋信息是構(gòu)造適應(yīng)度函數(shù)的重要依據(jù)，目標(biāo)路徑剔除不可行路徑和隨機(jī)法很容易生成測(cè)試數(shù)據(jù)的路徑。最后，用正確表示的測(cè)試數(shù)據(jù)運(yùn)行插裝后程序，利用混沌遺傳算法遺傳操作測(cè)試數(shù)據(jù)，使得可以生成針對(duì)目標(biāo)路徑的測(cè)試用例。

3.2 編碼方式

本文采用二進(jìn)制編碼級(jí)聯(lián)法，三角形分類程序參數(shù)類型為數(shù)值型。設(shè)被測(cè)程序三個(gè)輸入取值范圍為［0，63］，那么二進(jìn)制表示參數(shù)有6位，即6個(gè)基因，分別為 10010，010010，111000，二進(jìn)制級(jí)聯(lián)編碼后就是10010010010111000，它們形成的整體稱為個(gè)體，即該問(wèn)題的染色體。

3.3 反向?qū)W習(xí)種群初始化策略

求解測(cè)試用例自動(dòng)生成問(wèn)題中，需使用反向?qū)W習(xí)的策略來(lái)初始化隨機(jī)生成的最初種群。需求解個(gè)體基因的反向基因，具體表述如下：設(shè)程序輸入范圍為［0，2n-1］，那么有

式（6）生成個(gè)體基因反向數(shù)字，生成新個(gè)體（反向個(gè)體）。方法步驟如下：

算法1 基于反向?qū)W習(xí)的種群初始化算法

輸入：均勻隨機(jī)數(shù)

輸出：初始種群p0

step1均勻生成一批隨機(jī)數(shù)，組成最初種群Initial_P；

step2對(duì)Initial_P每個(gè)個(gè)體基因利用公式（6），取反向基因，生成新個(gè)體，即反向個(gè)體；

step3 將step2 生成的反向個(gè)體組成反向種群Initial_P'；

step4 從最初種群Initial_P 和反向種群Initial_P'中依次取個(gè)體，計(jì)算適應(yīng)度函數(shù)值，得到適應(yīng)度函數(shù)值，再組合適應(yīng)度更高的個(gè)體，將其放進(jìn)最終初始種群的對(duì)應(yīng)位置中；

step5生成初始種群p0，參與遺傳算法進(jìn)化。

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

測(cè)試數(shù)據(jù)生成可以描述如下：對(duì)于給定程序P和P的路徑，認(rèn)為D是P的輸入空間，當(dāng)x(x∈D)作為輸入數(shù)據(jù)時(shí)，程序執(zhí)行期間將會(huì)導(dǎo)致路徑u被覆蓋。適應(yīng)度函數(shù)的形式化表示：

其中，u(x)表示個(gè)體x覆蓋的路徑；ui為待覆蓋的第i條路徑；b(ui，u(x))表示兩條路徑的層接近度，其值為從第1 個(gè)分岔點(diǎn)開(kāi)始ui與u(x)的不同分支語(yǔ)句的個(gè)數(shù)；|ui|是目標(biāo)路徑ui中包含的分支點(diǎn)的數(shù)目；m(ui)是路徑ui測(cè)試數(shù)據(jù)集中測(cè)試數(shù)據(jù)的個(gè)數(shù)，越易覆蓋的路徑會(huì)有越大的測(cè)試數(shù)據(jù)集，將會(huì)導(dǎo)致是適應(yīng)度函數(shù)越低。

3.5 遺傳操作

1）選擇操作

本文采用輪盤賭個(gè)體選擇方式復(fù)制符合要求的個(gè)體到新種群，值越高被選擇概率就越大。

2）混沌交叉

傳統(tǒng)遺傳算法容易陷入早熟，收斂到局部最優(yōu)，同時(shí)上述適應(yīng)度函數(shù)設(shè)計(jì)使測(cè)試數(shù)據(jù)易匯集在已生成測(cè)試數(shù)據(jù)的路徑，需要改進(jìn)交叉方式，提高遺傳算法搜索范圍。具體操作如下：

（1）首先控制交叉操作的頻率

任取一個(gè)初值x0，如果p小于x0的情況下，可以進(jìn)行交叉；反之，則不交叉。即：

式中pc是預(yù)先選定的值，將交叉概率設(shè)置為0.9，使得種群中可以較充分交叉。

（2）混沌序列確定交叉點(diǎn)位置

設(shè)有L 位長(zhǎng)染色體，在（0，1）區(qū)間上隨機(jī)取一個(gè)數(shù)xn為初值，產(chǎn)生（0，1）區(qū)間混沌序列xn+1。公式q=(int)xn+1*L把序列映射至染色體基因位空間，使交叉發(fā)生在此位置，形成新子代，僅更換部分點(diǎn)基因，改動(dòng)較小，這樣可避免在產(chǎn)生子代過(guò)程中種群發(fā)生尋優(yōu)抖振問(wèn)題。

3）混沌變異

同上所述，變異操作的進(jìn)行也可以由產(chǎn)生的混沌序列來(lái)控制。理論基礎(chǔ)同上，不做贅述。

對(duì)個(gè)體進(jìn)行混沌交叉，混沌變異操作，首先，兩兩隨機(jī)組合種群內(nèi)的各個(gè)體，在此基礎(chǔ)上生成的每對(duì)組合，由系統(tǒng)隨機(jī)生成一個(gè)（0，1）之間的隨機(jī)數(shù)，由交叉概率決定是否交叉，若交叉，則采用經(jīng)線性映射的混沌序列xn+1，所對(duì)應(yīng)的位置進(jìn)行交叉操作，否則，看下一對(duì)。

混沌不重復(fù)遍歷特定范圍內(nèi)的所有狀態(tài)用來(lái)避免陷入局部最優(yōu)。它對(duì)初值敏感可以保證即使兩個(gè)最佳解是非常接近的，但仍然是兩個(gè)完全不同的染色體，因此種群可以保持多樣性。

3.6 混沌遺傳算法步驟

綜上所述，本文提出的生成混沌遺傳算法測(cè)試用例自動(dòng)生成的流程和算法流程圖如圖2。

圖2 基于混沌遺傳算法測(cè)試用例自動(dòng)生成流程

1）初始化參數(shù)：隨機(jī)生成最初種群，初始種群規(guī)模，交叉和變異概率，最大迭代次數(shù)；

2）種群初始化模塊：先生成最初種群，利用反向?qū)W習(xí)對(duì)個(gè)體基因求解反向數(shù)字，新生成的反向個(gè)體與最初個(gè)體同時(shí)求適應(yīng)度函數(shù)值，選擇適應(yīng)度函數(shù)值高的進(jìn)行下一步操作；

3）運(yùn)行插裝后的程序，求解初始種群的適應(yīng)度函數(shù)值；

4）遺傳操作：通過(guò)輪盤賭選擇策略選擇進(jìn)入下一代的種群，同時(shí)通過(guò)混沌序列決定遺傳算法的交叉、變異操作，首先控制交叉（變異）操作的頻率，決定交叉（變異）與否，如果交叉（變異），再根據(jù)隨機(jī)生成的混沌序列來(lái)選擇需要進(jìn)行交叉或者變異的位置。

4 實(shí)驗(yàn)分析

本文選擇了6 個(gè)不同規(guī)模程序作為被測(cè)程序，來(lái)評(píng)價(jià)提出的方法的性能，同時(shí)與其他方法對(duì)比，并進(jìn)行結(jié)果分析，所有方法均采用Matlab 軟件環(huán)境，實(shí)驗(yàn)回答了以下兩個(gè)問(wèn)題：

Q1：與其他方法做對(duì)比，本文提出的方法是否能夠達(dá)到更高的路徑覆蓋率？

Q2：與其他方法做對(duì)比，本文提出的方法是否具有較少的時(shí)間消耗？

4.1 被測(cè)程序基本信息

實(shí)驗(yàn)分別采用三角形分類實(shí)驗(yàn)程序，3 個(gè)數(shù)排序，interserve，totino，spice，schedule2 為被測(cè)程序，本文選取4 個(gè)工業(yè)測(cè)試程序，它們被大量應(yīng)用于測(cè)試用例的生成中［15］。

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

4.2 實(shí)驗(yàn)方法和評(píng)價(jià)體系

本文方法（記為ICGA），通過(guò)與標(biāo)準(zhǔn)遺傳算法（SGA），改進(jìn)后的遺傳算法（IGA）作對(duì)比，來(lái)分析改進(jìn)后的算法性能。選擇操作為輪盤賭。遺傳操作中的交叉方式為為單點(diǎn)交叉，概率為0.9；變異方式為單點(diǎn)變異，概率為0.1。所有方法的種群規(guī)模都為50，最大迭代數(shù)為1000。

對(duì)于不同方法均采用以下指標(biāo)進(jìn)行性能比較（每種方法分別獨(dú)立運(yùn)行50次）：

1）路徑覆蓋率（cov），表示為測(cè)試數(shù)據(jù)覆蓋的路徑數(shù)與所有路徑數(shù)的比值。

2）測(cè)試數(shù)據(jù)生成時(shí)間（t），是指生成測(cè)試數(shù)據(jù)所需要的時(shí)間。

4.3 實(shí)驗(yàn)結(jié)果

為了驗(yàn)證被測(cè)程序目標(biāo)路徑的覆蓋率，運(yùn)用不同方法做對(duì)比，實(shí)驗(yàn)結(jié)果如表3。

為了驗(yàn)證被測(cè)程序的測(cè)試數(shù)據(jù)生成時(shí)間，運(yùn)用不同方法做對(duì)比，實(shí)驗(yàn)結(jié)果如表4。

表3 不同方法對(duì)被測(cè)的程序路徑覆蓋率

表4 不同方法對(duì)被測(cè)程序程序的測(cè)試數(shù)據(jù)生成時(shí)間（s）

4.4 實(shí)驗(yàn)數(shù)據(jù)分析

根據(jù)實(shí)驗(yàn)結(jié)果，可以逐一回答前文提到的問(wèn)題Q1、Q2。

Q1：表 3 可以看出，在 3 個(gè)數(shù)排序，interserve，totino，spice，schedule2 中達(dá)到了最大路徑覆蓋率，就等于說(shuō)本文的方法模型適合于測(cè)試數(shù)據(jù)自動(dòng)生成。IGA 在三角形分類程序有輕微優(yōu)勢(shì)，說(shuō)明對(duì)某些應(yīng)用程序優(yōu)先選擇易覆蓋路徑，將進(jìn)一步提升方法性能。

圖3 不同方法對(duì)被測(cè)的程序路徑覆蓋率

圖4 不同方法對(duì)被測(cè)程序程序的測(cè)試數(shù)據(jù)生成時(shí)間（s）

Q2：結(jié)合表3、表4 本文方法對(duì)于程序3 個(gè)數(shù)排序，interserve，totino，spice，schedule2，達(dá)到最高覆蓋率同時(shí)，時(shí)間總是最少的，對(duì)于三角形分類程序雖然覆蓋率略低于SGA 和IGA，但本文方法生成測(cè)試用例時(shí)間少于前兩者。隨著程序規(guī)模擴(kuò)大，本文方法實(shí)用性更強(qiáng)。

5 結(jié)語(yǔ)

本文改進(jìn)了種群初始化策略、遺傳算法交叉、變異操作和適應(yīng)度函數(shù)的設(shè)計(jì)，提高了算法的全局尋優(yōu)能力。實(shí)驗(yàn)驗(yàn)證本文方法在測(cè)試用例自動(dòng)生成方面優(yōu)于其他方法。隨著軟件測(cè)試的免疫能力越強(qiáng)，越需要增加其他覆蓋要求，這也是值得進(jìn)一步研究的問(wèn)題。