基于Memetic 算法的仿真用例集約簡(jiǎn)技術(shù)

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

（1.廣東省電力系統(tǒng)網(wǎng)絡(luò)安全企業(yè)重點(diǎn)實(shí)驗(yàn)室（南方電網(wǎng)科學(xué)研究院有限責(zé)任公司），廣東廣州 510080；2.浙江大學(xué)信息與電子工程學(xué)院，浙江杭州 310027）

0 引言

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

目前，在相關(guān)測(cè)試用例集約簡(jiǎn)技術(shù)中，從測(cè)試需求集或組合覆蓋著手的測(cè)試方法較多。其中，組合測(cè)試有正交試驗(yàn)設(shè)計(jì)法和兩兩組合覆蓋法等［3］。基于測(cè)試需求集的方法主要將約簡(jiǎn)問題抽象為數(shù)學(xué)問題，用數(shù)學(xué)方法求解。用得較多的有貪心算法、啟發(fā)式算法、遺傳算法以及蟻群算法等生物進(jìn)化算法［4］。

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

1 用例集約簡(jiǎn)模型

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

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

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

2 Memetic 算法

2.1 種群編碼及初始化

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

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

由于在本文的約簡(jiǎn)問題中有一些約束條件，不滿足約束條件的個(gè)體得到的是不可行解。當(dāng)不可行解較多時(shí)，從不可行解區(qū)域收斂至可行解區(qū)域會(huì)浪費(fèi)較多時(shí)間。本文采用貪心策略，如圖2 所示，在隨機(jī)產(chǎn)生的種群數(shù)量個(gè)體中，將所有用例按適應(yīng)度函數(shù)值從大到小排列。在種群初始化后，檢查初始化種群個(gè)體，若發(fā)現(xiàn)其為不可行解，則添加適應(yīng)度值大的用例使其變?yōu)榭尚薪狻?/p>

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

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

為使結(jié)果盡可能快速地向可行解區(qū)域收斂，將約束處理機(jī)制融入適應(yīng)度函數(shù)設(shè)計(jì)，并與后續(xù)的選擇策略相結(jié)合。當(dāng)個(gè)體滿足約束條件時(shí)，仿真時(shí)間較少的個(gè)體比仿真時(shí)間較多的個(gè)體優(yōu)先被選中，當(dāng)仿真時(shí)間相同時(shí)，用例集較小的個(gè)體優(yōu)先被選中。對(duì)可行解，計(jì)算每個(gè)個(gè)體的用例數(shù)與全部用例數(shù)的差與時(shí)間相關(guān)的數(shù)值和，并將其作為適應(yīng)度函數(shù)，對(duì)非可行解，用兩者的差值與時(shí)間參數(shù)值的和表示適應(yīng)度值，并令非可行解的適應(yīng)度函數(shù)值均小于0，令可行解的適應(yīng)度函數(shù)值均大于0。

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

2.3 全局搜索策略

在設(shè)計(jì)全局搜索策略時(shí)，將遺傳算法和差分進(jìn)化算法相結(jié)合，整體架構(gòu)以差分進(jìn)化算法為基礎(chǔ)。在初始化種群后，采用差分進(jìn)化算法運(yùn)行步驟，先變異、交叉，然后選擇如圖3 所示的混合全局搜索策略。

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

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

2.3.1 變異算子

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

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

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

2.3.2 交叉算子

通常，交叉策略用得較多的為二項(xiàng)交叉和指數(shù)交叉2 種。受文獻(xiàn)［9］啟發(fā)，本文采用動(dòng)態(tài)調(diào)整的方式，在種群更新中，每次迭代后更新交叉率。交叉率值（CR）由均值a和標(biāo)準(zhǔn)偏差決定，隨著種群的更新，均值a也相應(yīng)更新，以適應(yīng)不同進(jìn)化階段的特性。同時(shí)，隨適應(yīng)度變化做動(dòng)態(tài)調(diào)整，當(dāng)適應(yīng)度較小時(shí)增大交叉率，較大時(shí)適當(dāng)減小交叉率，使其盡快收斂。

其中，c為0～1 的常數(shù)，fmax表示當(dāng)前種群最大的適應(yīng)度，f′表示完全用例集的適應(yīng)度。更新a之后，即可根據(jù)正態(tài)分布得到種群個(gè)體數(shù)量的CR 值，即scr列表，每個(gè)個(gè)體對(duì)應(yīng)一個(gè)值。mean（scr）為L(zhǎng)ehmer平均值，計(jì)算式為

2.3.3 選擇策略

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

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

2.4 局部搜索策略

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

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

禁忌搜索中的關(guān)鍵因素有：禁忌長(zhǎng)度、候選解、終止準(zhǔn)則、禁忌對(duì)象、鄰域結(jié)構(gòu)、特赦準(zhǔn)則等［11-12］。結(jié)合本文的測(cè)試用例集約簡(jiǎn)問題，對(duì)禁忌搜索策略做一定改進(jìn)。在Memetic 算法中，局部搜索通常需多次運(yùn)算，每次迭代時(shí)間雖較單獨(dú)的全局搜索策略稍長(zhǎng)，但因其迭代次數(shù)更少，所需總時(shí)間較少。本文中，因?yàn)樽罱K的約簡(jiǎn)集合為最優(yōu)個(gè)體所代表的用例集，所以應(yīng)保證最優(yōu)個(gè)體不陷入局部最優(yōu)解，同時(shí)為減少計(jì)算用時(shí)，在全局搜索后，選取在種群中適應(yīng)度排名前10%的個(gè)體，用局部搜索更新這些個(gè)體。其中禁忌長(zhǎng)度設(shè)為5，鄰域操作為隨機(jī)翻轉(zhuǎn)某兩比特位，每次產(chǎn)生6 個(gè)鄰域解，循環(huán)10 次，結(jié)束。

3 實(shí)驗(yàn)與分析

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

表1 串口協(xié)議特性Table 1 The serial protocol features

圖6 實(shí)驗(yàn)平臺(tái)架構(gòu)Fig.6 The experimental platform architecture

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

表2 不同規(guī)模用例集約簡(jiǎn)結(jié)果Table 2 The results of test case suite reduction for different scales

表3 不同規(guī)模用例集下不同算法約簡(jiǎn)的運(yùn)行時(shí)間Table 3 The runtime of different algorithm in test case suite reduction for different scales

圖7 用例集約簡(jiǎn)結(jié)果Fig.7 The results of test case suite reduction

圖8 用例集約簡(jiǎn)運(yùn)行時(shí)間Fig.8 The run time of test case suite reduction

表4 不同規(guī)模用例集下不同算法約簡(jiǎn)的仿真時(shí)間Table 4 The simulation time of different algorithm in test case suit reduction for different scale

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

4 結(jié)論

在調(diào)研用例集約簡(jiǎn)技術(shù)的基礎(chǔ)上，首先，對(duì)約簡(jiǎn)問題進(jìn)行了數(shù)學(xué)建模。然后，根據(jù)模型特點(diǎn)建立了Memetic 算法，對(duì)其中的全局策略和局部策略進(jìn)行了設(shè)計(jì)，研究了改進(jìn)算法中的各個(gè)算子，并將其應(yīng)用于約簡(jiǎn)優(yōu)化問題。對(duì)于用例集約簡(jiǎn)實(shí)驗(yàn)，在實(shí)際項(xiàng)目基礎(chǔ)上，設(shè)計(jì)了相應(yīng)的UVM 仿真驗(yàn)證平臺(tái)，形成了用例集，并對(duì)其進(jìn)行仿真分析，達(dá)到了覆蓋率要求，形成統(tǒng)一覆蓋率庫(kù)。最后，分別應(yīng)用標(biāo)準(zhǔn)遺傳算法和本文Memetic 算法對(duì)用例集進(jìn)行約簡(jiǎn)實(shí)驗(yàn)，結(jié)果表明，本文算法性能更優(yōu)、更節(jié)省時(shí)間、約簡(jiǎn)效果更顯著，具有較好的實(shí)際應(yīng)用價(jià)值。