基于改進遺傳算法的測試用例進化生成方法研究＊

林亞娜

(福州理工學院，福建 福州 350506)

0 引言

軟件測試中的路徑覆蓋測試是在單元測試階段比較常用的方法，測試用例的自動生成可以提高軟件測試效率，路徑覆蓋是一種重要的覆蓋標準，其目的是尋找覆蓋所有可能路徑的測試用例，進而發現軟件中存在的缺陷[1]。尋找覆蓋路徑的測試用例可抽象為尋求最優路徑的問題，遺傳算法是目前用于測試用例自動生成的有效的常用方法，遺傳算法在解決尋找最優路徑問題中有一定優勢。

Ahmed等[2]于2008 年首次提出基于遺傳算法（Genetic Algorithm）多路徑測試數據進化生成的方法，提出由層接近度和分支距離兩部分構成適應度函數，這種方法雖然能夠進化生成測試數據，但是計算量較大，效率不高。鞏敦衛等[3]提出一種用于多路徑覆蓋的測試數據生成方法，設計的適應度函數綜合考慮了個體穿越路徑與目標路徑的匹配程度，該方法可以通過較小的計算量高效地生成測試數據，而在匹配目標路徑的時候沒有考慮不可達路徑的問題。范書平等[4]提出利用種群中個體穿越程序分支的均衡度調整進化過程，使得對程序均衡度影響大的個體具有更多機會參與到后續進化中，提高測試數據的生成效率。夏春艷等[5]提出基于否定選擇遺傳算法的路徑覆蓋測試數據生成方法，動態優化遺傳算法的種群數據，減少冗余數據生成。黃陳輝[6]等提出一種混沌遺傳算法進行測試用例的進化生成，運用反向學習策略初始化種群，與簡單遺傳算法比較結果表明，這種方法可以提升測試用例生成方面的全局尋找最優解能力。

本文所提方法的核心由兩部分組成：①通過分析被測程序的流程圖得到可能的目標路徑集合，過濾不可達路徑以便節省進化數據匹配的資源成本；②對遺傳算法的適應度函數進行改進，通過分析分支走向以及加路徑權重的方式設計新的適應度函數，最后利用矩陣計算方法計算出適應度。當遺傳算法生成的測試數據路徑與目標路徑不匹配時，通過分析路徑走向以及路徑加權的計算，可以拉大測試數據路徑與目標路徑的差距，加速算法收斂速度，提高生成可用測試用例的效率。

1 改進遺傳算法生成測試用例的方法

1.1 路徑的構建

路徑的構建是通過分析程序流程圖，程序結構基本分三類：順序結構、選擇（分支）結構、循環結構。其中順序結構的程序不涉及路徑變化，在構建路徑過程中無需區分這類結構；選擇（分支）結構和循環結構是區分路徑的關鍵，循環結構采用Z 路徑覆蓋原則[7]，簡化了循環的次數，只考慮循環1 次和0 次兩種情況。本文主要針對這兩類結構分析目標路徑集合，首先定義兩個概念。

定義1路徑中節點的方向系數α，表示程序結構的走向，為1或-1。

針對選擇（分支）結構：

定義2路徑中的節點權值β，表示每個節點在當前路徑中所占的權重，越靠近起始點的節點，其影響越大，進而權重越大。假設當前路徑有n 個節點，第i個節點的權值為：

權值按照節點個數降序排列，即第1 個節點的權值β1為n，第2 個節點權值β2為n-1，以此類推。將路徑集合表示為一個n行m列的矩陣P，P[i][j]（i=1,2,...,n；j=1,2,...,m）表示第i 條路徑中第j 個節點所對應的值，該值由定義1 的節點方向系數與定義2 的節點權值相乘組成。

根據公式⑷可以構建出被測程序中所有目標路徑的矩陣P[i][j]以及進化生成的測試數據實際經過的路徑PA[i][j]。

1.2 適應度函數設計

適應度函數主要的任務是對比實際路徑與目標路徑的差異。差異越小，證明實際數據路徑與目標路徑越匹配，適應度值越接近1。目標路徑應是一個集合，首先排除目標路徑集合中分支點數與實際路徑分支點數不同的路徑，分支不同必然不可能匹配；其次，用實際路徑分別與目標路徑集合中的路徑做匹配并計算適應度，如得到完全匹配的數據，則保存當前的測試數據，并將已經匹配的目標路徑從目標路徑集合中刪除，將該條實際路徑的適應度設置為1；如未完全匹配，則通過計算實際路徑與各個目標路徑的適應度，計算其平均值即為該條實際路徑的適應度。

利用路徑的構建方法，將第t 代測試數據代入被測程序，通過程序插樁構建出第t 代測試數據的實際路徑，即1行r列矩陣PA,r表示該條實際路徑經過的分支點個數；目標路徑表示為矩陣P，其中P[i]表示目標路徑集合中的第i條路徑構建的矩陣，為1行r列矩陣，通過矩陣計算得到第t 代測試數據實際路徑的適應度函數：

其中，n表示目標路徑集合過濾后的路徑條數，過濾指目標路徑集合中去掉不可達路徑及路徑中節點數與實際路徑不一致的路徑，PA表示實際路徑矩陣，P 表示過濾后的目標路徑矩陣，i 指P 中的第i 條路徑，T 上標表示矩陣的轉置。式⑸得到的結果為一個自然數，為了便于比較，將結果限定在一個范圍，做歸一化處理，將式⑸得到的結果分布到實際路徑矩陣的秩的平方中，將適應度值限定在[-1，1]閉區間內，最終得到歸一化后的適應度函數如下：

適應度函數的設計綜合考慮了不匹配節點出現的前后位置，不匹配出現的越靠前，則代表實際路徑與目標路徑集合中的路徑不匹配程度越大，經過公式⑹計算得到的適應度值越接近-1，表示該數據匹配程度低，在遺傳算法中被選擇為親代數據的幾率越小。將路徑抽象為矩陣，經過矩陣計算，根據不匹配節點出現的位置，計算適應度，能夠體現路徑之間的匹配程度，通過式⑴、式⑵方向系數和式⑶權值的設計，可適當拉大匹配路徑的差異，加速算法收斂。

預制裝配式建筑施工技術及其配套裝備的創新研究…………………………………………………… 王潤華（10-203）

1.3 改進的遺傳算法生成測試用例方法

改進的遺傳算法流程圖如圖1所示：

圖1 改進遺傳算法的流程圖

算法的實現步驟共分六步：

步驟1在待測程序中插樁，構建出目標路徑集合，判斷分支節點處是否存在相關性因素，找出不可達路徑并從目標路徑集合中刪除，構建最終的目標路徑矩陣；

步驟2通過遺傳算法初始化種群，生成第一代種群的測試數據，代入測試數據執行被測程序，獲取每條測試數據的實際執行路徑；

步驟3評價實際路徑與目標路徑的匹配程度，如有完全匹配的測試數據，則保留該條數據作為測試用例，并將匹配上的目標路徑從目標路徑集合中刪除；如未完全匹配，根據公式⑸、⑹計算個體的適應度進而計算第一代測試數據的整體適應度；

步驟4判斷遺傳終止條件是否滿足，如已經滿足轉至步驟6，如未滿足終止條件，則繼續執行步驟5；遺傳終止條件為當前目標路徑集合中已無待匹配路徑，表示所有與目標路徑匹配的測試用例均已經生成或達到指定的進化代數上限；

步驟5根據初始化設置的交叉率、變異率執行遺傳算法中的交叉、變異程序，再次計算整體適應度；生成下一代種群進化的測試數據，跳轉回步驟4，再次判斷遺傳條件是否終止；

步驟6終止遺傳算法，輸出生成的測試數據。

2 實驗仿真分析

2.1 實驗準備

為了評價本文提出的改進的遺傳算法的有效性以及性能，選取四個基本測試進行測試，被測程序的基本信息如表1所示。

表1 待測程序基本信息

本文改進的遺傳算法采用輪盤賭選擇交叉的親代，單點交叉、單點變異進而生成下一代測試數據。每次實驗的參數設置如表2所示。實驗運行環境基本配置為2.3GHz 四核 Inter（R）i5-6300HQ 處理器，8GB 內存，Windows10 操作系統，JVM 版本1.8.0_121，開發語言為Java語言，集成平臺為Eclipse2019-09。

表2 實驗參數設置

2.2 算法可行性驗證

本文算法與隨機算法做比較，分別針對四個基本測試程序構建路徑并生成測試用例。對生成數據的覆蓋率、生成的測試用例數量、迭代的次數以及生成測試數據的時間等幾個關鍵指標進行對比，由于算法存在不確定性，每個算法得到的測試數據為該算法執行100次的平均結果，詳細數據如表3所示。

表3 改進的遺傳算法與隨機算法針對四組待測程序執行結果對比

通過分析實驗結果可得，在程序簡單、分支較少的程序中，本文算法與隨機算法的覆蓋率、生成測試用例個數與運行時間相差無幾，但是在分支數較多的程序中，比如在判斷三角形Angles 程序中，在生成測試用例數相同的情況下，本文算法的覆蓋率為100%，隨機算法為91%，本文算法覆蓋率高于隨機算法。在獲取下一天NextDate 程序中，本文算法生成的測試用例個數少于隨機算法，在此情況下，本文算法的覆蓋率仍高于隨機算法。當程序分支數變多時，在生成測試用例數量相同時，改進的算法覆蓋率仍可保持100%覆蓋路徑。在復雜程序中，改機的算法與隨機算法相比，覆蓋率提升4%～9%。通過本文改進遺傳算法生成數據，可以針對待測程序的具體情況，調整交叉率及變異率，改善算法的收斂速度，這是隨機算法無法做到的。

3 結束語

自動生成測試用例是自動化測試研究中的核心環節，本文將測試用例自動生成的問題抽象為尋求最優解問題，通過改進遺傳算法的適應度函數計算方法加快遺傳算法收斂，與隨機算法相比，能夠更快速的尋找到最適合的測試數據。設計適應度函數，拉大不匹配路徑之間的差距，從而快速獲得符合條件的測試數據，減少冗余測試數據的生成，提高測試覆蓋率。

將本文算法應用到基礎測試代碼中實驗，經過與隨機算法對比，得出本文算法在測試覆蓋率和進化代數方面具有一定的優越性。在過濾不可達路徑的過程中，尚未使用程序自動化完成，未來將針對這一步驟做進一步研究。