基于Memetic 算法的仿真用例集約簡技術

楊祎巍，匡曉云，黃開天，洪超，鄭昌立，蔣小文*

（1.廣東省電力系統網絡安全企業重點實驗室（南方電網科學研究院有限責任公司），廣東廣州 510080；2.浙江大學信息與電子工程學院，浙江杭州 310027）

0 引言

回歸測試集是一組達到了目標覆蓋率的用例集合，一般通過制訂用例計劃實現或由自動隨機產生的方式構造，易導致一些點被多個用例重復覆蓋，造成用例冗余［1］。在回歸測試時，為縮短仿真時間，提高效率，希望找到極小的用例集合，在滿足覆蓋率的前提下，用盡量短的時間，完成回歸測試，在多次反復執行中，節省了大量時間，從而大大縮短項目完成時間。通常，對所有用例進行回歸測試，只適用于規模較小或項目時間較寬松的情況［2］。有時會根據對項目的理解，憑經驗從用例集中挑選一些用例進行計算，但效果并不理想，需具有與項目強相關的專業知識，通用性亦不好，當用例選擇不同時，結果差別很大，且不能同時滿足覆蓋率和精簡化的要求。

目前，在相關測試用例集約簡技術中，從測試需求集或組合覆蓋著手的測試方法較多。其中，組合測試有正交試驗設計法和兩兩組合覆蓋法等［3］?；跍y試需求集的方法主要將約簡問題抽象為數學問題，用數學方法求解。用得較多的有貪心算法、啟發式算法、遺傳算法以及蟻群算法等生物進化算法［4］。

在處理實際問題時，優化算法是將問題用類似的生物或數學模型代替，然后代入合適的策略進行求解。編碼與解碼互相對應，在算法搜索空間和實際問題的解空間之間進行轉換［5］。相較于其他進化算法，Memetic 算法在求解中增加了局部處理步驟，其作用是對全局處理后的個體做局部處理，在一些位置做突變，盡早將一些不好的個體篩除，從而減少運算次數，提升運算效率。影響Memetic 算法的關鍵因素是各算子的選擇和局部策略的性能［6］。

1 用例集約簡模型

分析測試用例集的特點發現，其與集合覆蓋問題的數學描述相似，可將約簡測試用例集的求解問題轉換為集合覆蓋問題的優化求解。集合覆蓋問題在日常生活中較常見，是一類帶有約束的離散優化問題，其變量和解一般為整數向量，如調度問題、選址問題等，是一類非確定多項（non-deterministic polynomial，NP）難問題。通俗講，集合覆蓋問題可解釋為：有2 個集合E和S，S中元素能全部覆蓋E中元素，如果S中有n個子集，每個子集對應一個耗費代價，在S的子集中能找到完全覆蓋集合E的集合，且耗費代價最?。?］。集合覆蓋示意如圖1 所示。測試用例集約簡問題，則是全部的功能覆蓋點集合E（為需要被覆蓋的集合），各用例組成的測試用例集為集合S，子集中每包含一個測試用例，其耗費代價將相應增加，在完全覆蓋所有被要求覆蓋的點的條件下，選擇耗費代價最小的子集，即測試用例集數量最少的集合。

圖1 集合覆蓋問題示意Fig.1 The model of test case suite reduction

假設有i個行元素的整體，代表所有需要覆蓋的功能點，有j個列元素的整體，代表所有用例集合，用式（1）表示，其中，xj表示用例集中第j個用例是否被選擇組成子集，xj是一個二值元素（取0 或1），取1 時說明第j個用例被選中，加入約簡用例組合，取0 時說明第j個用例未被選中；tj表示每個用例所需的仿真時間，aij表示第j個用例是否覆蓋第i個功能點；cj表示每個用例的耗費代價，在本文的約簡問題中，cj=1。

2 Memetic 算法

2.1 種群編碼及初始化

在測試用例約簡問題中，采用二進制編碼，每比特有2 種取值，分別表示用例的選擇與否。通過此方式，有n個用例的用例集用一個n位的二進制串表示，每位對應一個用例，其值反映用例是否被選擇。

種群的數量是種群初始化的重要參數，對算法的運算性能有一定影響。為使計算量不至于過大、多樣性不會太低，通常選擇種群數量為20～100［8］。本文選取的種群數量為50，即每代種群中有50 種不同的用例集組合。

由于在本文的約簡問題中有一些約束條件，不滿足約束條件的個體得到的是不可行解。當不可行解較多時，從不可行解區域收斂至可行解區域會浪費較多時間。本文采用貪心策略，如圖2 所示，在隨機產生的種群數量個體中，將所有用例按適應度函數值從大到小排列。在種群初始化后，檢查初始化種群個體，若發現其為不可行解，則添加適應度值大的用例使其變為可行解。

圖2 貪心修正策略Fig.2 The greedy correction strategy

2.2 適應度函數

為使結果盡可能快速地向可行解區域收斂，將約束處理機制融入適應度函數設計，并與后續的選擇策略相結合。當個體滿足約束條件時，仿真時間較少的個體比仿真時間較多的個體優先被選中，當仿真時間相同時，用例集較小的個體優先被選中。對可行解，計算每個個體的用例數與全部用例數的差與時間相關的數值和，并將其作為適應度函數，對非可行解，用兩者的差值與時間參數值的和表示適應度值，并令非可行解的適應度函數值均小于0，令可行解的適應度函數值均大于0。

其中，n為原始用例集的用例數，gij為當前種群第i個個體X的第j位，總和即為用例集數，t(X)表示某個體代表的用例集運行的仿真時間，T表示原始用例集運行的仿真時間，cov（X）表示個體X的覆蓋率，cov（I）表示原始用例集的覆蓋率。

2.3 全局搜索策略

在設計全局搜索策略時，將遺傳算法和差分進化算法相結合，整體架構以差分進化算法為基礎。在初始化種群后，采用差分進化算法運行步驟，先變異、交叉，然后選擇如圖3 所示的混合全局搜索策略。

圖3 混合全局搜索策略Fig.3 The hybrid global strategy

由于差分進化的變異算子在實數域上，而本文討論的離散問題在實數域上搜索無效果，因此，首先，須采用遺傳算法中的變異算子處理二進制數據串，然后，由差分進化的交叉算子產生中間代種群，最后，在中間代種群與原始種群間做選擇。

2.3.1 變異算子

變異策略是全局策略中的重要操作，亦是保證種群多樣性的關鍵步驟，與染色體的編碼方式息息相關。本文采用的編碼變異方法具體表現為二進制串每個基因位上的數值在0 和1 間翻轉。對傳統一元變異充分性不足問題，用2 個基因位結合使用的方法解決，如圖4 所示，對2 條染色體采用二元變異操作，效果明顯好于一元變異［2］。

圖4 二元變異Fig.4 The binary variation

在本文設計的變異策略中，同時使用同或和異或2 種運算，2 個舊個體產生2 條新染色體，如此，每個基因位均為原來的0 和1，僅染色體組合不同，使得種群變化足夠豐富，同時保證了基因完整性。進行變異運算時，先將輸入的種群個體打亂，隨機排序，每次取相鄰的2 個個體做二元變異，n個個體種群就有n/2 個子集。

2.3.2 交叉算子

通常，交叉策略用得較多的為二項交叉和指數交叉2 種。受文獻［9］啟發，本文采用動態調整的方式，在種群更新中，每次迭代后更新交叉率。交叉率值（CR）由均值a和標準偏差決定，隨著種群的更新，均值a也相應更新，以適應不同進化階段的特性。同時，隨適應度變化做動態調整，當適應度較小時增大交叉率，較大時適當減小交叉率，使其盡快收斂。

其中，c為0～1 的常數，fmax表示當前種群最大的適應度，f′表示完全用例集的適應度。更新a之后，即可根據正態分布得到種群個體數量的CR 值，即scr列表，每個個體對應一個值。mean（scr）為Lehmer平均值，計算式為

2.3.3 選擇策略

以差分進化算法中常用的貪婪選擇方式為選擇策略，初始化后通過變異和交叉操作得到中間代種群，然后比較原始種群與中間代種群。在選擇策略中，比較原始種群與中間代種群對應個體的適應度值，適應度大的個體加入新的種群，如式（5）所示。

其中，Vi+1(t)為新一代種群的第t個個體，Ui(t)和Vi(t)分別為中間代個體與當前代個體。

2.4 局部搜索策略

在常見的幾種局部搜索策略中，禁忌搜索的局部尋優能力最強［10］，為此，本文采用禁忌搜索策略。在完成全局策略的變異和交叉算子運算后進行局部搜索。禁忌搜索策略一般流程如圖5 所示。

圖5 禁忌搜索策略一般流程Fig.5 The general process of taboo search strategy

禁忌搜索中的關鍵因素有：禁忌長度、候選解、終止準則、禁忌對象、鄰域結構、特赦準則等［11-12］。結合本文的測試用例集約簡問題，對禁忌搜索策略做一定改進。在Memetic 算法中，局部搜索通常需多次運算，每次迭代時間雖較單獨的全局搜索策略稍長，但因其迭代次數更少，所需總時間較少。本文中，因為最終的約簡集合為最優個體所代表的用例集，所以應保證最優個體不陷入局部最優解，同時為減少計算用時，在全局搜索后，選取在種群中適應度排名前10%的個體，用局部搜索更新這些個體。其中禁忌長度設為5，鄰域操作為隨機翻轉某兩比特位，每次產生6 個鄰域解，循環10 次，結束。

3 實驗與分析

在完成上述算法設計后，進行實驗分析。實驗平臺為基于通用驗證方法學（universal verification methodology，UVM）的仿真驗證平臺，如圖6 所示。設計模塊為一款軟硬件可配置的串行接口IP（RPC），串口協議特性如表1 所示，為可靈活配置的面積優化的串行協議控制器，通過狀態機編程可使用不同的協議。該IP 支持配置為I2C、SPI 的主機或從機模式及標準UART 接口，此外，也可配置非標準接口。

表1 串口協議特性Table 1 The serial protocol features

圖6 實驗平臺架構Fig.6 The experimental platform architecture

以I2C 為實驗對象，以選定的用例集所能覆蓋的功能點為全集，從回歸測試集中選取5 組不同規模的用例集，分別運用標準遺傳算法和本文的Memetic 算法進行約簡實驗。實驗比較了約簡后的用例集規模、約簡過程算法運行時間、約簡后用例集的仿真時間。表2 為不同規模用例集約簡結果，其趨勢圖如圖7 所示，由圖7 可知，Memetic 算法較標準遺傳算法的約簡效果更好。表3 為在不同規模用例集下不同算法約簡的運行時間，圖8 為其總體趨勢，由圖8 可知，Memetic 算法比標準遺傳算法的運行時間更少，速度更快。表4 為不同規模用例集下不同算法約簡的仿真時間比較，圖9 為其直方圖。綜上可知，本文算法約簡效果更好，時間更節省，測試代價降低更顯著。

表2 不同規模用例集約簡結果Table 2 The results of test case suite reduction for different scales

表3 不同規模用例集下不同算法約簡的運行時間Table 3 The runtime of different algorithm in test case suite reduction for different scales

圖7 用例集約簡結果Fig.7 The results of test case suite reduction

圖8 用例集約簡運行時間Fig.8 The run time of test case suite reduction

表4 不同規模用例集下不同算法約簡的仿真時間Table 4 The simulation time of different algorithm in test case suit reduction for different scale

圖9 用例集仿真時間Fig.9 The simulation time of test case suite

4 結論

在調研用例集約簡技術的基礎上，首先，對約簡問題進行了數學建模。然后，根據模型特點建立了Memetic 算法，對其中的全局策略和局部策略進行了設計，研究了改進算法中的各個算子，并將其應用于約簡優化問題。對于用例集約簡實驗，在實際項目基礎上，設計了相應的UVM 仿真驗證平臺，形成了用例集，并對其進行仿真分析，達到了覆蓋率要求，形成統一覆蓋率庫。最后，分別應用標準遺傳算法和本文Memetic 算法對用例集進行約簡實驗，結果表明，本文算法性能更優、更節省時間、約簡效果更顯著，具有較好的實際應用價值。