基于改進鯨魚優化的覆蓋表生成算法*

劉向婷，曹小鵬

(西安郵電大學計算機學院，陜西 西安 710121)

1 引言

軟件系統的大多故障是由各參數之間的相互作用導致的[1]，為了檢驗這些故障，測試用例的設計顯得尤為重要。但是，如果輸入參數過多或取值復雜時，測試用例的個數將非常龐大，窮盡測試顯得不切實際。在此，組合測試解決了這一難題，它能有效實現各因素取值的充分覆蓋，同時能夠生成規模較小的覆蓋表[2]。

組合測試最小覆蓋表生成已證實是一個NP完全問題，為解決該問題，國內外學者研究了多種方法。其主要分為3類[3]：貪心算法、啟發式搜索算法和數學方法，其中啟發式算法是解決組合測試問題最有效的方法。啟發式算法將覆蓋表生成問題轉化為函數優化問題，即使用遺傳算法GA(Genetic Algorithm)、粒子群算法PSO(Particle Swarm Optimization)、模擬退火算法SA(Simulated Annealing)等元啟發式算法來實現。但是，啟發式搜索算法普遍具有易陷入局部最優的缺陷，表現為收斂精度和收斂速度較低。

本文基于鯨魚優化算法WOA(Whale Optimization Algorithm)[4]來實現覆蓋表生成。WOA是由Mirjalili等[4]在2016年提出的一種新元啟發式算法，該算法相比粒子群算法、蟻群算法等，具有參數少、易于實現、收斂速度快和收斂精度高等優點[5]。目前，WOA已廣泛應用于圖像檢索[6]、工程優化[7]、醫學[8]等領域，但WOA最初是針對連續問題開發的，其演化過程是在不斷更新鯨魚個體位置而進行的，它不能直接用于解決離散覆蓋表生成問題，且對一些復雜優化問題，容易陷入局部最優和出現早熟收斂現象。因此，本文提出一種改進鯨魚優化的覆蓋表生成算法WOACTG(Coverage Table Generation algorithm based on improved Whale Optimization Algorithm)。該算法首先對鯨魚個體位置進行離散化，并設計合適的適應度函數來更新鯨魚種群，然后在開發與探索階段加入演化算子，在此基礎上，針對覆蓋表生成中算法本身的局限問題，加入平均海明距離和約束處理策略進行優化。該算法用來解決組合測試中覆蓋表生成問題，支持變力度和約束模型的處理，以最小化覆蓋表的規模為目的，本文給出了相對應的實驗，從整體上評估了該算法的性能。

Table 1 Test model of mobile phone camera function表1 手機相機功能測試模型

Table 2 2-way coverage table of mobile phone camera function表2 手機相機功能測試2-way覆蓋表

Table 3 Added test cases on the basis of table 2 for VSCA(12;2,3223,CA(3,3122))表3 可變強度覆蓋表VSCA(12;2,3223,CA(3,3122))在表2基礎上補充的測試用例

Table 4 Fixed strength instance models without constraints表4 固定力度不帶約束實例模型

Table 5 Variable strength instance models without constraints VSCA(2,-,-,CA(-))表5 變力度不帶約束實例模型VSCA(2,-,-,CA(-))

Table 6 Fixed strength instance models with constraints表6 固定力度帶約束實例模型

Table 7 Experiment results of 2-way fixed strength表7 2-way固定力度實驗結果

Table 8 Experiment results of 3-way fixed strength表8 3-way固定力度實驗結果

Table 9 Experiment results of 2-way variable strength表9 2-way變力度實驗結果

Table 10 Experiment results of fixed strength with constraints表10 固定力度帶約束實驗結果

2 相關工作

在覆蓋表問題上，2012年，時貴英[9]通過分析遺傳算法、粒子群算法和蟻群算法的優缺點后，提出了一種新的改進粒子群算法，該算法雖然有效克服了粒子群算法易發生早熟收斂的缺陷，但缺乏對不同算法之間的對比；吳化堯等人[10]在2012年提出了一種適應于覆蓋表生成的自適應粒子群算法，且戚榮志等人[11]在2017年基于覆蓋表生成問題，提出了一種Spark的島模型并行化遺傳算法，以上2種算法雖然在多組參數取值下生成大多覆蓋表均能獲得最優結果，但都缺乏對變力度和約束的考慮；2018年，包曉安等人[12]研究了覆蓋強度對覆蓋表性能的影響，但對粒子群算法易陷入局部最優和后期收斂速度慢的問題沒有進行相應考慮。

鯨魚優化算法最初是針對連續問題而開發的，但目前已被應用于各種離散優化問題中。2019年，Jiang等人[13]用離散鯨魚優化算法解決綠色車間調度問題，通過實驗揭示所提算法在該問題上有很大優勢；2019年，Hussien等人[14]對原始WOA進行改進，提出一種二元鯨魚優化算法，用于處理離散二進制優化問題，將其應用于22個基準函數、3個工程優化問題和1個真實的旅行商問題中，并與5種常見啟發式搜索算法進行比較，其準確性和速度均具有明顯優勢。因此，該算法應用于覆蓋表的離散優化問題有很大潛力。

在約束處理問題上主要有3類方法：基于貪婪方法[15]、基于模擬退火的方法[16]和基于SAT求解器的方法[17]?；谪澙贩椒m然提高了測試用例的生成速度，但生成規模相對較大；模擬退火雖然能生成較小規模的覆蓋表，但不能保證獲得最佳結果。Cohen等人[15]于2008年首次利用可滿足性問題(SAT)求解器來處理約束，生成35個含約束的2-way覆蓋表；Yu等人[18]在2015年基于禁止元組，提出了約束覆蓋表生成，該方法生成的覆蓋表規模較大，但生成時間較少；與此不同的是，2015年，Yamada等人[19]使用增量SAT求解器來優化組合測試套件，并驗證了相比于貪心算法、模擬退火算法，在生成規模和生成時間上都有優勢。

3 背景

3.1 組合測試中的約束

組合測試中的約束是一個重要的研究問題。在實際覆蓋表生成中，參數間的相互約束是普遍存在的[20,15]，未考慮可能會產生大量無效的測試用例，從而對測試結果的有效性產生影響。例如表1是對手機相機功能的測試模型。該模型共有5個參數，閃光模式和拍照模式分別有3個不同取值，美顏、攝像頭模式、手機后臺廣播分別有2個不同取值。由于錄像時音控通道被占用，因此當錄像時，手機不可能在后臺播放內容，即P2中的錄像和P5中的On不能同時取值，意味著(-，錄像，-，-，On)將無法實現。同時，現實場景中，參數間的關系緊密程度也不統一，從而存在變力度情況。組合測試通過對參數間的約束進行合理的設計，可以大大提高覆蓋表生成的效率。

上述測試模型假設只針對任意2參數間的組合覆蓋，則僅需如表2所示的9條測試用例。在所有的測試用例集中，所有的滿足約束的2-way組合至少出現一次。例如，對于參數拍照模式和美顏來說，與其相關的3×2=6個2-way組合都在表2中至少出現過一次，同時，所有測試用例都滿足相應的約束條件，即(-，錄像，-，-，On)不會出現。相關的6個2-way組合為：

(-，拍照，On，-，-)，(-，拍照，Off，-，-)，(-，錄像，On，-，-)，(-，錄像，Off，-，-)，(-，全景，On，-，-)，(-，全景，Off，-，-)。

在實際系統中，參數間的作用強度可能不同，對于組合測試，本文用可變強度覆蓋表來實現參數間不同組合的覆蓋。

假設在上述待測模型中，參數拍照模式、美顏、攝像頭模式之間的相互作用較強，我們將此稱為可變強度覆蓋，其測試用例在表2的基礎上增加3條，如表3所示，模型表示為VSCA(12;2,3223,CA(3,3122))。此覆蓋表不僅包含5個參數所有的2-way組合，參數拍照模式、美顏、攝像頭間的3-way組合3ⅹ22=12也至少出現了一次。

3.2 覆蓋表生成框架

組合測試的關鍵問題是覆蓋表的生成，其研究目標是如何生成較小規模的覆蓋表。在眾多構造覆蓋表的方法中，使用最多的策略是One-test-at-a-time[21,22]，該策略相應的偽代碼如算法1所示：

算法1One-test-at-a-time策略

輸入：參數個數n，各參數取值v，覆蓋強度τ。

輸出：覆蓋表T。

1.T=?;S=the set of validτ-way combinations to be covered;//S等于所有待覆蓋的組合對

2.while(S≠?)do

3.generate a valid test casepto cover the most uncovered combinations;/*調用算法2生成一條適應值最大的測試用例p*/

4.addpintoT,and remove theτ-way combinations that are covered bypfromS/*把p加入T中，并從S中去除p所能覆蓋的所有τ組合*/

5.endwhile

6.returnT

在算法1中，通過引入適應度函數來衡量候選覆蓋表的質量。這里S表示所有未被覆蓋的組合，適應度函數fitness(p)的返回值為測試用例p在S中覆蓋的組合數目。

3.3 鯨魚優化算法

基本鯨魚優化算法(WOA)模仿了座頭鯨的捕食行為，其數學模型包括包圍獵物、泡泡網攻擊和搜索獵物3部分[4]。為了對這些特征進行建模，用以下公式對搜索代理X的位置進行更新。

3.3.1 開發階段(包圍獵物/泡泡網攻擊方法)

(1)包圍獵物。

狩獵過程中，座頭鯨首先觀察獵物的位置并將其包圍。在優化問題中，由于初始時最優解是未知的，因此WOA假設當前最佳候選解是目標獵物或接近最優，其他搜索代理尋求在最佳搜索代理的方向上嘗試更新他們的位置。其數學模型如式(1)和式(2)所示：

D=|C·X*(t)-X(t)|

(1)

X(t+1)=X*(t)-A·D

(2)

其中，D是當前搜索代理與t迭代時最佳搜索代理之間的長度，t表示當前迭代,X*(t)是到目前為止獲得的最佳解，X(t)是位置向量，·表示逐個元素的乘法。在包圍獵物時，搜索代理在當前找到的最佳候選解的方向上更新其狀態。A和C是系數向量，計算方法如下所示：

A=2a·r-a

(3)

C=2·r

(4)

其中，a是從2到0是線性遞減的，r中的元素是[0,1]均勻分布的隨機數，A的元素在[-a,a]取隨機值。式(2)中搜索代理(即鯨魚)根據已知最佳解(即獵物)來更新其位置。

(2)螺旋更新機制。

在螺旋更新階段，搜索代理以螺旋運動的方式向目標移動。數學模型如下所示：

X(t+1)=D′·ebl·cos(2πl)+X*(t)

(5)

D′=|X*(t)-X(t)|

(6)

其中，D′表示鯨魚和獵物(到目前獲得的最佳解)之間的長度，b是定義對數螺旋線形狀的常數，l是[-1,1]的隨機數。當座頭鯨在一個不斷收縮的圓環沿著螺旋形路徑移動時，WOA實現了2種行為：包圍獵物和螺旋更新。為了模擬這2種行為，假設以50%的概率在收縮環繞機制或螺旋模型更新之間進行選擇，從而使鯨魚的位置在此得到優化。數學模型如下所示：

(7)

其中，p是[0,1]的隨機數。

3.3.2 勘探階段(隨機搜索獵物)

為了提高WOA的探索能力，引入一種隨機搜索代理代替目前最佳搜索代理來更新鯨魚的位置。當向量的隨機值大于1或者小于-1時，選擇隨機搜索代理實現搜索，以增強算法的全局搜索能力，否則選取當前獲得的最佳解實現搜索，即通過式(2)來更新搜索代理的位置。其數學模型表示如下：

D=|C·Xrand(t)-X(t)|

(8)

X(t+1)=Xrand(t)-A·D

(9)

其中，Xrand(t)是從當前種群中隨機選擇搜索代理的位置而不是選擇最優的。

3.4 鯨魚優化算法生成一條測試用例的流程

算法2給出了WOA生成一條測試用例的過程，該算法可以被算法1調用。在鯨魚算法生成覆蓋表時，將待測系統的參數看作一個d維空間，記鯨魚個體的位置為Xi(t)=(x1(t),x2(t),…,xd(t))，其表示一條候選測試用例。這里適應值函數用式(10)表示:

fitness(Xi(t))=|Sτ({Xi(t)})-Sτ(T)|

(10)

其中，τ表示覆蓋強度，T表示生成的覆蓋集，Sτ(T)表示所有τ組合被T所覆蓋的個數，取適應值較大的作為最優候選解。

算法2WOA生成一條測試用例的過程

輸入：參數個數n，各參數取值v，待覆蓋組合S。

輸出：測試用例X*(t)。

1.t=0，X*(t)=0;

2.for(每頭鯨魚Xi(t))do

3. 隨機初始化位置Xi(t);

4.while(t

5. //適應值評估階段

6.for(每頭鯨魚Xi(t))do{

7. 計算鯨魚適應值fitness(Xi(t));

8.if(fitness(Xi(t))==C(n,τ))then/*C(n,τ)表示一條測試用例最多覆蓋的組合數*/

9.returnXi(t)}/*種群中適應值最大的作為X*(t)*/

10. //位置更新階段

11.for(每頭鯨魚Xi(t))do

12. 更新a，A，C，l和p;//A是一個系數向量

13.if(p<0.5)then

14.if(|A|<1)then

15. 使用式(2)更新鯨魚的位置;

16.elseif(|A|≥1)then

17. 使用式 (9)更新鯨魚的位置;

18.endif

19.elseif(p≥0.5)then

20. 使用式 (5)更新鯨魚的位置;

21.endif;

22.t++;

23.endwhile;

24.returnX*(t)

算法2中，t表示當前迭代，Max_Iteration表示最大迭代次數。

由于鯨魚算法中的位置是實數值，即應用于覆蓋表時必須對位置進行取整，因此需要對算法進一步改進。本文給出2種優化策略，使其能更好地適用于覆蓋表生成。

4 改進鯨魚優化的覆蓋表生成算法

4.1 鯨魚優化算法的離散化方法

本文基于離散的概念，對鯨魚位置采用編碼轉換的思想，提出一種新的位置表示方法。在WOACTG中，用Y表示覆蓋表中一個候選解組合，記Y(t)=[y1(t),y2(t),…,yd(t)]∈[0,1,…,n-1]d(n≥2)為所求的一個可行解，其中d表示維度。這里將待測系統的參數看作一個d維空間，每頭鯨魚個體的位置表示一個候選解，記鯨魚個體的位置為Xi(t)=[x1(t),x2(t),…,xd(t)]∈[-P,P]d，鯨魚的位置轉化函數Y(t)=φ(Xi(t))表示如下：

(11)

上述公式將Xi(t)的d維實數空間向量[-P,P]d編碼轉換為離散向量[0,1,…,n-1]d(n≥2)，即分段函數是將[-P,P]d分成n個小區間，然后利用適應值函數來評估可行解Y(t)的大小，最終找到問題的最優解。

其中，P為一正實數，表示所求問題的取值范圍，一般P取值隨n的增大而增大。在WOACTG中，Y(t)=[y1(t),y2(t),…,yd(t)]∈{0,1}d,即采用個體編碼為{0,1}d上的一個d維整型向量來求解，變量yi(t)(0≤i≤n-1)表示項i是否被用于鯨魚位置的更新，取[-P,P]=[-3.0,3.0]。

4.2 迭代演化算子

對于啟發式搜索算法，開發與探索兩階段的平衡對于算法的搜索能力非常重要?；决L魚優化算法中使用系數|A|來平衡兩者之間的關系，若|A|≥1時，強調搜索代理遠離參考鯨魚，隨機選擇搜索代理實現全局搜索；相反，|A|<1使用到目前為止最佳的搜索代理實現位置更新。A的值隨α變化，而α是從2到0線性遞減的，不能充分展現算法的實際更新方式，因此對算法搜索與開發之間的平衡不能很好地展現。在此引入一迭代演化算子pi∈[0,1]，表示選擇已有組合中參數進行更新的概率。對于每頭鯨魚個體，在當前代中生成一個隨機數rand∈[0,1]，如果rand≤pi，則將在開發階段實現更新，否則，將在探索階段進行更新。若pi取值較大，在一定程度上能較快實現位置更新，但容易陷入局部最優；相反，探索階段的取值決定了對鯨魚個體新位置進行變異的概率，若取值較大，則可以增加種群的多樣性，但算法的收斂速度也隨之降低。因此，合適的pi選取對于算法性能有很大影響，用如下公式表示pi的值：

pi=pimax-(pimax-pimin)×(t/tmax)2

(12)

其中,pi為定義的選擇概率算子，pimax和pimin是pi的最大值和最小值，tmax為最大迭代次數。

4.3 優化策略

4.3.1 位置調優

為了衡量當前測試用例與已生成覆蓋表之間的緊密程度，本文引入了海明距離的概念，用d12表示2個測試用例c1與c2之間的海明距離，即2個測試用例間取值不同的參數個數。用平均海明距離H(c,T)表示測試用例c與覆蓋表T中每條測試用例間海明距離之和的平均值，其表示如下所示：

(13)

上式中，WOACTG在適應值最大的候選解與當前測試用例集之間選擇一個平均海明距離最小的作為全局最優解，如假設Xi(t)表示一條測試用例，若Xi(t)=(0,0,0,0)，則(0,0,1,1)與其平均海明距離為2，而(0,1,1,1)是3，即選擇前者作為全局最優解。這樣就可以在具有較大適應值的測試用例中，選擇海明距離最小的作為最優測試用例，從而為生成更小規模的覆蓋表提供可能性。

4.3.2 約束處理

如第3節所述，參數間的約束關系普遍存在，未考慮可能會產生大量無效的測試用例，從而對測試結果造成影響。因此，在覆蓋表生成中，約束處理至關重要。本文利用約束求解器法[16]和適應值懲罰項法[23]來避免約束。在初始化種群階段，使用SAT求解器來判斷每頭鯨魚的位置(即測試用例)是否滿足約束條件，若不滿足，則該鯨魚個體將不被放入到種群中。然后在適應值函數的評估中加入懲罰項，使可行解的適應值大于不可行解的適應值。適應值函數表示如下：

fitness(Xi(t))=|Sτ({Xi(t)})-

Sτ(T)|-γ·0.5·C(n,τ)

(14)

其中，C為一條測試用例最多覆蓋的組合數，當Xi(t)不滿足給定約束時,γ=1，否則γ=0。即在對全局最優的更新上，使用滿足約束的解去更新，這樣可以使覆蓋表中所有的測試用例都是約束滿足的，從而提高生成覆蓋表的效率。

4.4 基于鯨魚優化的覆蓋表生成算法

WOACTG算法的核心是利用編碼轉換方法將鯨魚位置表示成一個整數子集的結果，然后用適用于覆蓋表生成的適應度函數來評估鯨魚個體的優劣，使其不斷向當前最優個體靠近，最后用改進的方法進行更新，找到全局最優解。WOACTG算法流程圖如圖1所示。

Figure 1 Procedure of WOACTG algorithms圖1 WOACTG算法流程圖

WOACTG步驟如算法3所示。

算法3WOACTG步驟

輸入：參數個數n，各參數取值v，覆蓋強度τ。

輸出：最優測試用例X*(t)。

步驟1初始化種群N和C(n,τ)個τ組合。選擇一群鯨魚或搜索代理，在變量區間[-P，P]中隨機分配一組數值。

步驟2利用Yi(0)=φ(Xi(0))，1≤i≤N計算個體Xi(0)對應的可行解，并根據適應值函數fitness(Xi(0))，尋找當前最佳解。

步驟3迭代更新。該步驟需要一些子程序，下面將對其進行說明：

(1)生成[0,1]隨機數α，若α≥0.5，利用式(5)更新，否則，生成隨機數β，若β≥pi，通過式(9)更新，否則，利用式(2)更新；

(2)判斷當前種群中每個個體更新是否完成，若完成則利用Y(t+1)=φ(Xi(t+1))計算可行解，并根據適應值函數確定X*(t+1)，否則轉至步驟(1)；

步驟4判斷算法是否達到最大迭代次數，若達到，則輸出全局最優值，否則跳轉至步驟3進行下一次迭代。

5 實驗

5.1 實驗設計

實驗中，從文獻[11]選取了10個2-way和5個3-way的固定力度實例模型，從文獻[10,24]分別選取了5個2-way變力度不帶約束和固定力度帶約束實例模型，分別見表4～表6。

在算法性能比較中，因為有些文獻未給出覆蓋表生成時間，有的雖然給出，但因為實驗環境不同，存在較大差異，因此本實驗只對覆蓋表的規模進行比較。由于實驗的隨機性，為使結果更加準確，對每組實驗均執行30次求平均，得出覆蓋表規模的最小值、平均值及生成時間，時間單位為秒，不足一秒記為0，NA 表示對應值信息沒有在已有文獻中報告，將每行中的最小規模都加粗表示。ACTS數據通過運行工具生成，由于ACTS的確定性，實驗運行1次即可，其他算法沒有公開提供的工具，均是與相關文獻中公開數據進行對比的。實驗中參數設置基于已有文獻[4,14]和經驗，給出一組建議參數：種群population=100，最大迭代次數Max_Iteration=300，搜索代理數dim=30，參數Pi表示選擇已有組合中參數進行更新的概率，Pi取0.3。

實驗的軟硬件環境為：Intel(R) Core(TM) i5-8250U CPU @1.60 GHz、8.00 GB內存、64位Windows 10，實驗中所有代碼均使用C++實現。

5.2 性能比較

(1)固定力度不帶約束。

首先，基于表1的模型，用WOACTG與已有文獻中覆蓋表生成算法進行比較，其結果如表7和表8所示。

由表7結果可知，在2-way實例模型中，WOACTG的覆蓋表生成規模顯著優于PSO、GA、IPGAS 和ACTS算法的，在S2-3和MS2-8中，WOACTG生成覆蓋表規模小于SA算法的，其它實例模型中，模擬退火算法生成的規模均等于或小于WOACTG算法的，模擬退火算法的優勢主要在于它的搜索策略[16,26]。如何進一步提高鯨魚優化算法生成最優覆蓋表的能力將是以后的研究工作。

由表8可知，在3-way實例模型中，相比IPGAS、GA和ACTS，WOACT能生成更小規模的覆蓋表。在S3-4實例中，模擬退火算法表現優于WOACTG，其余實例中，WOACTG生成的覆蓋表規模要小于或等于模擬退火算法的。

(2)變力度不帶約束。

基于表5的模型，用WOACTG與已有文獻中覆蓋表生成算法進行比較，其結果如表9所示。

從表9分析可知,WOACTG在生成的覆蓋表規模上整體優于其他算法的，除了在VS2-2和VS2-3上大于PTS_CVS外，在其他算法以及模型上都取得了較優值，雖然VS2-4、VS2-5上與PSO或已有文獻規模相同，但遠小于PICT的。

(3)固定力度帶約束。

從表10中可以看出，WOACTG能在60%(3/5)的情況下生成小規模的覆蓋表，雖然在CS-1和Concurrency中生成的覆蓋表規模略大于已有算法的，但在時間上遠小于HHSA-H。

6 結束語

本文基于鯨魚優化算法提出了一種適用于覆蓋表生成的鯨魚優化算法。該算法根據編碼轉換思想，實現算法的離散化，從而完成覆蓋表的生成；加入海明距離來避免算法陷入局部最優，通過約束求解器和適應值懲罰項的方法，完成了參數之間的約束處理。實驗結果表明，該算法與已有IPGAS、PSO、GA、SA、ASCT、PTS_CVS、PICT和HHAS-H算法相比，能生成規模較小的覆蓋表，具有較好的性能優勢。在下一步的工作中，將研究初始化方法和參數調優來進一步提高算法性能，使覆蓋表生成朝著更加高效、自適應的方向發展。