基于佳點(diǎn)集遺傳算法的多路徑覆蓋測試用例生成*

程孟飛 丁 蕊

（牡丹江師范學(xué)院 牡丹江 157011）

1 引言

在軟件開發(fā)的整個進(jìn)程中，軟件測試是保障軟件質(zhì)量的重要手段［1］。隨著軟件規(guī)模的不斷增加，人工進(jìn)行軟件測試需要消耗大量時間和資源。對于面向路徑覆蓋的測試，如何在降低測試數(shù)據(jù)自動生成成本的同時提高軟件質(zhì)量，是具有重要意義的研究問題。

基于遺傳算法的多路徑覆蓋的測試用例生成是指通過一次運(yùn)行遺傳算法搜索到覆蓋被測程序中所有可行路徑的測試用例，以提高軟件測試效率，降低人工測試成本。軟件工程領(lǐng)域的眾多學(xué)者對智能優(yōu)化算法多路徑覆蓋測試數(shù)據(jù)生成技術(shù)進(jìn)行了深入的研究。Ahmed［2］首次提出多路徑覆蓋測試數(shù)據(jù)生成方法，設(shè)計(jì)層接近度與分支距離相結(jié)合的適應(yīng)度函數(shù)，與單路徑覆蓋測試數(shù)據(jù)生成方法相比，多路徑方法只需一次運(yùn)行就能找到覆蓋所有目標(biāo)路徑的測試數(shù)據(jù)，大大提高了測試效率；我們曾提出一種基于關(guān)鍵點(diǎn)的多路徑測試數(shù)據(jù)生成方法［3］，通過易覆蓋路徑和測試數(shù)據(jù)提供的信息用遺傳算法生成難覆蓋路徑的測試數(shù)據(jù)，提高了測試效率，基于此，又提出一種基于煙花爆炸的測試數(shù)據(jù)生成方法［4］，將啟發(fā)式信息融入煙花爆炸算法，進(jìn)一步提高了測試效率。

Liu［5］等認(rèn)為基于路徑覆蓋的測試用例自動生成是一個黑盒優(yōu)化問題；為此，姚香娟［6］等訓(xùn)練神經(jīng)網(wǎng)絡(luò)模擬適應(yīng)度值生成過程，降低了運(yùn)行程序帶來的時間消耗；因此，面向路徑覆蓋的測試用例生成作為一個黑盒問題是NP難問題，遺傳算法能有效解決此類復(fù)雜系統(tǒng)問題。但遺傳算法的搜索能力及迭代速度有限，在進(jìn)化過程中容易出現(xiàn)過早收斂以及收斂速度慢等問題。

佳點(diǎn)集遺傳算法（Good Point Set Genetic Algorithm，GPSAG）是張鈴教授提出的一種改進(jìn)的遺傳算法［7］，其作為一種改進(jìn)的遺傳算法已被成功應(yīng)用到特征選擇［8］、測試用例優(yōu)先級排序［9］等研究領(lǐng)域。該算法通過佳點(diǎn)集理論構(gòu)造出了一種佳點(diǎn)集交叉算子，佳點(diǎn)集交叉算子生成的個體不僅保留了雙親優(yōu)秀的基因，還能通過佳點(diǎn)算子產(chǎn)生佳點(diǎn)序列，避免種群個體尋優(yōu)抖振，陷入局部最優(yōu)解，使遺傳算法在收斂速度以及搜索精度都得到提升。因此，本文提出將佳點(diǎn)集遺傳算法融入到面向路徑的測試用例生成中，針對白盒測試中的路徑覆蓋測試用例生成問題，利用個體穿越路徑與未覆蓋路徑的相似度和分支距離作為適應(yīng)度，采用佳點(diǎn)集交叉算子和混沌交叉算子進(jìn)行交叉操作生成子代個體，以加快遺傳算法效率。

2 相關(guān)背景知識及定義

2.1 混沌映射

混沌映射［10］是一種確定性系統(tǒng)產(chǎn)生的隨機(jī)序列，遍歷性和普適性的性質(zhì)使它用來代替隨機(jī)生成方法，可以使元素均勻的分布在空間中，避免隨機(jī)方法產(chǎn)生序列的不均勻以及盲目性問題。本文用Logistic映射生成混沌序列來代替佳點(diǎn)序列。式（1）給出了Logistic映射產(chǎn)生的混沌序列：

其中zn表示生成的第n個種群個體，μ用來控制zn在［0，1］范圍內(nèi)，一般取μ∈[0，4]。

2.2 佳點(diǎn)集的定義與性質(zhì)［7］

定義1佳點(diǎn)集

令r∈Gt為t維歐氏空間中的單位立方體中一點(diǎn)集，若形為Gt中的一點(diǎn)集Pn(i)={(r1×i，r2×i，…，ri×i，)，i=1，2，…，n}的 偏 差O(n)滿 足O(n)=C(r，X)n(-1+X)，其中C(r，X)是只與r，X（X是任意小的正數(shù)）有關(guān)的常數(shù)，則稱Pn(i)為佳點(diǎn)集，r稱為佳點(diǎn)。取rk=2 cos(2πμ/p)，1≤μ≤t，p是滿足(p-t)/2≥t的最小素?cái)?shù)，則r是佳點(diǎn)。取rk=ek，1≤k≤t，則r也是佳點(diǎn)（分圓域）。

2.3 遺傳算法

遺傳算法（Genetic Algorithm，GA）是一種全局啟發(fā)式優(yōu)化算法，被廣泛用于函數(shù)優(yōu)化、組合優(yōu)化、機(jī)器學(xué)習(xí)、信號處理、自動控制和軟件測試數(shù)據(jù)自動化生成等領(lǐng)域。基于遺傳算法的測試用例自動生成的步驟是：首先在程序輸入域中隨機(jī)生成初始種群；然后對初始種群中個體進(jìn)行編碼，對被測程序進(jìn)行插裝，運(yùn)行被測程序獲得適應(yīng)度值，方便后續(xù)的選擇、交叉和變異操作；最后個體染色體進(jìn)行一系列選擇、交叉、變異使所有個體（待最優(yōu)解）一同向著最優(yōu)解靠近，直至找到最優(yōu)測試用例集或達(dá)到最大迭代次數(shù)。因此基于遺傳算法的測試用例生成是一個全局收斂算法，但標(biāo)準(zhǔn)遺傳算法在進(jìn)化過程中容易出現(xiàn)過早收斂和收斂速度慢的問題，影響算法進(jìn)化效率。

3 基于佳點(diǎn)集遺傳算法的測試用例生成方法

3.1 面向多路徑覆蓋測試用例生成的佳點(diǎn)集遺傳算法

本文借鑒佳點(diǎn)集理論設(shè)計(jì)佳點(diǎn)集交叉算子進(jìn)行面向多路徑覆蓋的測試用例自動生成，并提出兩點(diǎn)改進(jìn)：一是根據(jù)個體穿越路徑與未覆蓋路徑集之間的相似度構(gòu)造層接近度和改進(jìn)分支距離的適應(yīng)度函數(shù)；二是針對佳點(diǎn)集遺傳算法在實(shí)數(shù)編碼的情況下，出現(xiàn)佳點(diǎn)集交叉?zhèn)€體溢出問題，提出一種適于實(shí)數(shù)編碼的混沌交叉方法，提高算法搜索效率。

本文提出的基于佳點(diǎn)集遺傳算法的測試用例生成方法模型如圖1所示。

圖1 基于佳點(diǎn)集遺傳算法的測試用例生成模型

3.2 混沌交叉算子

交叉是增加種群多樣性的重要途徑，在佳點(diǎn)集交叉過程中，k值是構(gòu)建佳點(diǎn)集序列的重要參數(shù)，不同k參數(shù)會生成不同的佳點(diǎn)集交叉后代。若選擇多個交叉后代作為子代個體，容易造成子代個體中相似度過高，導(dǎo)致個體失去競爭力而過早收斂；但對于目標(biāo)路徑相似度低的程序，多個子代個體又可以加快種群進(jìn)化。因此，根據(jù)不同程序選擇不同數(shù)量的交叉?zhèn)€體是提高種群進(jìn)化效率的關(guān)鍵。本文中選擇k取1時的單子代以及k取1和k取2時產(chǎn)生的雙個體進(jìn)行測試用例生成，以比較說明佳點(diǎn)集遺傳算法的實(shí)用性，并針對不同被測程序的編碼方式設(shè)計(jì)不同的交叉方式。

對于二進(jìn)制編碼的程序，選擇佳點(diǎn)集交叉算子［7］。

對于實(shí)數(shù)編碼的程序，由于二進(jìn)制編碼中生成的佳點(diǎn)集處于［0，1］之間，將佳點(diǎn)集映射到實(shí)數(shù)搜索范圍會導(dǎo)致個體跳出搜索范圍，為此本文提出一種混沌交叉算子，其與佳點(diǎn)集交叉算子類似，認(rèn)為相同基因片段為優(yōu)秀片段，并將其遺傳到子代個體的相同位置。即混沌交叉算子與佳點(diǎn)集交叉算子的不同之處在于，將個體不同位置的元素用混沌映射生成的混沌序列替換，生成子代個體，參與進(jìn)化，基因保留策略和混沌的遍歷性可以使生成的個體既保留雙親優(yōu)秀基因又能防止個體基因單一造成的過早收斂問題。圖2給出了混沌交叉過程。

圖2 混沌交叉過程

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

在遺傳算法進(jìn)化過程中，適應(yīng)度函數(shù)指的是在遺傳算法進(jìn)化過程中對個體進(jìn)行評價，是體現(xiàn)優(yōu)勝劣汰的重要過程。本文設(shè)計(jì)個體穿越路徑與未覆蓋路徑的相似度與分支距離相結(jié)合的適應(yīng)度函數(shù)，宏觀上，綜合考慮個體穿越路徑與所有未覆蓋路徑之間的相似度之和作為個體適應(yīng)度值，可以使已覆蓋路徑的測試數(shù)據(jù)啟發(fā)式信息引導(dǎo)搜索未覆蓋路徑，微觀上，鑒于分支距離過大可能會使相似度信息無法發(fā)揮作用［11］，設(shè)計(jì)規(guī)范化的層接近度［12］設(shè)計(jì)適應(yīng)度函數(shù)，以提高搜索效率。適應(yīng)度函數(shù)形式化如下。

其中，b(x，xi)Ci表示第i個個體穿越路徑與未被覆蓋路徑的相似度，cj表示第i個個體與第j條目標(biāo)路徑之間的層接近度di，bi表示分支距離［13］，branch指的是個體在所有路徑上的分支距離和的規(guī)范化處理，bi越小branch就越大，個體越優(yōu)，因此適應(yīng)度函數(shù)越大，個體就越好。

3.4 基于佳點(diǎn)集遺傳算法的測試用例生成方法偽代碼

算法2給出了GPSGA的偽代碼，其中，算法終止條件設(shè)置為找到覆蓋所有目標(biāo)路徑的測試數(shù)據(jù)或達(dá)到設(shè)定的最大迭代次數(shù)［14］。

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

為驗(yàn)證所提方法的性能，本文選擇基準(zhǔn)程序和工業(yè)程序進(jìn)行實(shí)驗(yàn)。所有程序在Matlab2016軟件環(huán)境下運(yùn)行，Windows XP操作系統(tǒng)，機(jī)器主頻是2.80GHz，內(nèi)存為8 GB，混沌控制參數(shù)μ=4。應(yīng)用遺傳算法（GA）、雙后代佳點(diǎn)集遺傳算法（Two Offspring Good Point Set Inheritance，TOGA，指使用k取1和2時的雙后代作為子代個體）、和本文提出的方法（GPSGA）生成測試用例，通過實(shí)驗(yàn)旨在回答以下三個問題：

1）所提算法的進(jìn)化代數(shù)是否低于遺傳算法？

2）所提算法在時間損耗方面是否優(yōu)于遺傳算法？

3）所提算法的覆蓋率是否優(yōu)于遺傳算法？

實(shí)驗(yàn)選擇三角形分類程序、冒泡排序、sed和flex為被測程序，它們被廣泛應(yīng)用于軟件測試研究領(lǐng)域［15］。三角形分類初始種群規(guī)模設(shè)置為50，最大迭代次數(shù)50，冒泡程序種群規(guī)模為30，最大迭代次數(shù)20，其他參數(shù)設(shè)置如下：交叉概率0.9，變異概率0.1，搜索范圍［0，255］，二進(jìn)制編碼，混沌交叉，單點(diǎn)變異，每種算法運(yùn)行50次，取平均值，sed和flex程序都采用實(shí)數(shù)編碼，混沌交叉，單點(diǎn)變異。當(dāng)實(shí)驗(yàn)終止時，記錄所有算法的進(jìn)化代數(shù)、運(yùn)行時間和覆蓋率。表1給出工業(yè)程序的基本信息，表2給出了被測程序的實(shí)驗(yàn)結(jié)果。

表1 工業(yè)程序信息

至此，根據(jù)上表中的實(shí)驗(yàn)數(shù)據(jù)結(jié)果，我們可以逐一回答之前的問題：

1）由表2可以看出，GPSGA和TOGA運(yùn)行的進(jìn)化代數(shù)都少于GA算法，這是因?yàn)槭褂镁哂袉l(fā)式信息的適應(yīng)度函數(shù)以及實(shí)數(shù)編碼下的混沌交叉算子，說明基于佳點(diǎn)集遺傳算法的測試用例生成方法能提高進(jìn)化效率。

2）表2實(shí)驗(yàn)數(shù)據(jù)表明，在三角形分類和flex程序中，TOGA運(yùn)行時間最長，這是因?yàn)榧腰c(diǎn)集交叉后生成的雙后代個體導(dǎo)致種群相似度高，降低了種群的多樣性；但在所有程序中GPSGA運(yùn)行時間均少于GA和TOGA，這是因?yàn)樵O(shè)計(jì)的佳點(diǎn)集交叉算子能夠防止個體單一，陷入局部最優(yōu)解，說明基于佳點(diǎn)集遺傳算法的測試用例生成方法能加快收斂速度。

表2 被測程序?qū)嶒?yàn)結(jié)果

3）由表2可知，GPSGA和TOGA運(yùn)行的覆蓋率都高于GA算法，說明基于佳點(diǎn)集遺傳算法的測試用例生成方法提高了路徑覆蓋率。

值得一提的是，在sed程序中TOGA算法占優(yōu)勢，而在flex程序中，GPSGA算法較好，這是因?yàn)閟ed程序目標(biāo)路徑之間相似度低，局部最優(yōu)解少，不易陷入局部最優(yōu)，而flex程序中目標(biāo)路徑之間相似度大，種群中個體相似度過高會導(dǎo)致算法減慢，因此針對易陷入局部最優(yōu)的程序采用GPSGA算法，局部最優(yōu)解少的程序采用TOGA算法。

5 結(jié)語

本文利用佳點(diǎn)集誤差小精度高的優(yōu)點(diǎn)，將佳點(diǎn)集遺傳算法融合到面向多路徑覆蓋的測試用例生成中，設(shè)計(jì)混沌交叉算子以及相似度信息引導(dǎo)搜索的適應(yīng)度函數(shù)，實(shí)驗(yàn)表明，本文方法能夠有效減少進(jìn)化代數(shù)和測試數(shù)據(jù)搜索時間，并獲得更高的路徑覆蓋率。

未來，我們將通過動態(tài)增加種群多樣性來改善單位空間中佳點(diǎn)集算子產(chǎn)生個體的稀疏性問題，以期能進(jìn)一步加快測試用例生成效率。