劉向婷，曹小鵬

(西安郵電大學(xué)計(jì)算機(jī)學(xué)院，陜西 西安 710121)

1 引言

軟件系統(tǒng)的大多故障是由各參數(shù)之間的相互作用導(dǎo)致的[1]，為了檢驗(yàn)這些故障，測試用例的設(shè)計(jì)顯得尤為重要。但是，如果輸入?yún)?shù)過多或取值復(fù)雜時(shí)，測試用例的個(gè)數(shù)將非常龐大，窮盡測試顯得不切實(shí)際。在此，組合測試解決了這一難題，它能有效實(shí)現(xiàn)各因素取值的充分覆蓋，同時(shí)能夠生成規(guī)模較小的覆蓋表[2]。

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

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

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

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

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

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

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

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

Table 7 Experiment results of 2-way fixed strength表7 2-way固定力度實(shí)驗(yàn)結(jié)果

Table 8 Experiment results of 3-way fixed strength表8 3-way固定力度實(shí)驗(yàn)結(jié)果

Table 9 Experiment results of 2-way variable strength表9 2-way變力度實(shí)驗(yàn)結(jié)果

Table 10 Experiment results of fixed strength with constraints表10 固定力度帶約束實(shí)驗(yàn)結(jié)果

2 相關(guān)工作

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

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

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

3 背景

3.1 組合測試中的約束

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

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

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

在實(shí)際系統(tǒng)中，參數(shù)間的作用強(qiáng)度可能不同，對于組合測試，本文用可變強(qiáng)度覆蓋表來實(shí)現(xiàn)參數(shù)間不同組合的覆蓋。

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

3.2 覆蓋表生成框架

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

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

輸入：參數(shù)個(gè)數(shù)n，各參數(shù)取值v，覆蓋強(qiáng)度τ。

輸出：覆蓋表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;/*調(diào)用算法2生成一條適應(yīng)值最大的測試用例p*/

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

5.endwhile

6.returnT

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

3.3 鯨魚優(yōu)化算法

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

3.3.1 開發(fā)階段(包圍獵物/泡泡網(wǎng)攻擊方法)

(1)包圍獵物。

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

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

(1)

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

(2)

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

A=2a·r-a

(3)

C=2·r

(4)

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

(2)螺旋更新機(jī)制。

在螺旋更新階段，搜索代理以螺旋運(yùn)動(dòng)的方式向目標(biāo)移動(dòng)。數(shù)學(xué)模型如下所示：

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

(5)

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

(6)

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

(7)

其中，p是[0,1]的隨機(jī)數(shù)。

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

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

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

(8)

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

(9)

其中，Xrand(t)是從當(dāng)前種群中隨機(jī)選擇搜索代理的位置而不是選擇最優(yōu)的。

3.4 鯨魚優(yōu)化算法生成一條測試用例的流程

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

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

(10)

其中，τ表示覆蓋強(qiáng)度，T表示生成的覆蓋集，Sτ(T)表示所有τ組合被T所覆蓋的個(gè)數(shù)，取適應(yīng)值較大的作為最優(yōu)候選解。

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

輸入：參數(shù)個(gè)數(shù)n，各參數(shù)取值v，待覆蓋組合S。

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

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

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

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

4.while(t

5. //適應(yīng)值評估階段

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

7. 計(jì)算鯨魚適應(yīng)值fitness(Xi(t));

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

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

10. //位置更新階段

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

12. 更新a，A，C，l和p;//A是一個(gè)系數(shù)向量

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表示當(dāng)前迭代，Max_Iteration表示最大迭代次數(shù)。

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

4 改進(jìn)鯨魚優(yōu)化的覆蓋表生成算法

4.1 鯨魚優(yōu)化算法的離散化方法

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

(11)

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

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

4.2 迭代演化算子

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

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

(12)

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

4.3 優(yōu)化策略

4.3.1 位置調(diào)優(yōu)

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

(13)

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

4.3.2 約束處理

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

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

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

(14)

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

4.4 基于鯨魚優(yōu)化的覆蓋表生成算法

WOACTG算法的核心是利用編碼轉(zhuǎn)換方法將鯨魚位置表示成一個(gè)整數(shù)子集的結(jié)果，然后用適用于覆蓋表生成的適應(yīng)度函數(shù)來評估鯨魚個(gè)體的優(yōu)劣，使其不斷向當(dāng)前最優(yōu)個(gè)體靠近，最后用改進(jìn)的方法進(jìn)行更新，找到全局最優(yōu)解。WOACTG算法流程圖如圖1所示。

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

WOACTG步驟如算法3所示。

算法3WOACTG步驟

輸入：參數(shù)個(gè)數(shù)n，各參數(shù)取值v，覆蓋強(qiáng)度τ。

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

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

步驟2利用Yi(0)=φ(Xi(0))，1≤i≤N計(jì)算個(gè)體Xi(0)對應(yīng)的可行解，并根據(jù)適應(yīng)值函數(shù)fitness(Xi(0))，尋找當(dāng)前最佳解。

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

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

(2)判斷當(dāng)前種群中每個(gè)個(gè)體更新是否完成，若完成則利用Y(t+1)=φ(Xi(t+1))計(jì)算可行解，并根據(jù)適應(yīng)值函數(shù)確定X*(t+1)，否則轉(zhuǎn)至步驟(1)；

步驟4判斷算法是否達(dá)到最大迭代次數(shù)，若達(dá)到，則輸出全局最優(yōu)值，否則跳轉(zhuǎn)至步驟3進(jìn)行下一次迭代。

5 實(shí)驗(yàn)

5.1 實(shí)驗(yàn)設(shè)計(jì)

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

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

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

5.2 性能比較

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

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

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

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

(2)變力度不帶約束。

基于表5的模型，用WOACTG與已有文獻(xiàn)中覆蓋表生成算法進(jìn)行比較，其結(jié)果如表9所示。

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

(3)固定力度帶約束。

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

6 結(jié)束語

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