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

程孟飛 丁 蕊

（牡丹江師范學院 牡丹江 157011）

1 引言

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

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

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

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

2 相關背景知識及定義

2.1 混沌映射

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

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

2.2 佳點集的定義與性質［7］

定義1佳點集

令r∈Gt為t維歐氏空間中的單位立方體中一點集，若形為Gt中的一點集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是任意小的正數）有關的常數，則稱Pn(i)為佳點集，r稱為佳點。取rk=2 cos(2πμ/p)，1≤μ≤t，p是滿足(p-t)/2≥t的最小素數，則r是佳點。取rk=ek，1≤k≤t，則r也是佳點（分圓域）。

2.3 遺傳算法

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

3 基于佳點集遺傳算法的測試用例生成方法

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

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

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

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

3.2 混沌交叉算子

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

對于二進制編碼的程序，選擇佳點集交叉算子［7］。

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

圖2 混沌交叉過程

3.3 適應度函數

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

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

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

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

4 實驗

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

1）所提算法的進化代數是否低于遺傳算法？

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

3）所提算法的覆蓋率是否優于遺傳算法？

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

表1 工業程序信息

至此，根據上表中的實驗數據結果，我們可以逐一回答之前的問題：

1）由表2可以看出，GPSGA和TOGA運行的進化代數都少于GA算法，這是因為使用具有啟發式信息的適應度函數以及實數編碼下的混沌交叉算子，說明基于佳點集遺傳算法的測試用例生成方法能提高進化效率。

2）表2實驗數據表明，在三角形分類和flex程序中，TOGA運行時間最長，這是因為佳點集交叉后生成的雙后代個體導致種群相似度高，降低了種群的多樣性；但在所有程序中GPSGA運行時間均少于GA和TOGA，這是因為設計的佳點集交叉算子能夠防止個體單一，陷入局部最優解，說明基于佳點集遺傳算法的測試用例生成方法能加快收斂速度。

表2 被測程序實驗結果

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

值得一提的是，在sed程序中TOGA算法占優勢，而在flex程序中，GPSGA算法較好，這是因為sed程序目標路徑之間相似度低，局部最優解少，不易陷入局部最優，而flex程序中目標路徑之間相似度大，種群中個體相似度過高會導致算法減慢，因此針對易陷入局部最優的程序采用GPSGA算法，局部最優解少的程序采用TOGA算法。

5 結語

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

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