改進黑猩猩優(yōu)化算法的測試數(shù)據(jù)生成研究

高大喚，梁宏濤，杜軍威，于 旭，胡 強

青島科技大學(xué) 信息科學(xué)技術(shù)學(xué)院，山東 青島 266100

隨著軟件規(guī)模、需求及復(fù)雜度的不斷提升，軟件缺陷率不斷增長[1-2]，而發(fā)現(xiàn)軟件缺陷的唯一途徑就是對軟件進行測試。軟件測試作為軟件工程生命周期中的關(guān)鍵階段之一，其中測試數(shù)據(jù)縱貫軟件測試的全部流程。軟件測試的主要目標(biāo)是生成有效的測試數(shù)據(jù)，而如何在有限的時間內(nèi)生成有效的測試數(shù)據(jù)是軟件測試領(lǐng)域的研究難點之一[3]，在有限的時間內(nèi)選擇一組代碼覆蓋率較高的輸入數(shù)據(jù)是自動化測試數(shù)據(jù)生成技術(shù)的主要目標(biāo)[4]。在軟件測試技術(shù)的探索中，出現(xiàn)了眾多測試數(shù)據(jù)生成方法，基于啟發(fā)式的生成算法成為當(dāng)下學(xué)者的研究主流，并被廣泛應(yīng)用到測試數(shù)據(jù)[5-9]。

啟發(fā)式優(yōu)化算法在測試數(shù)據(jù)生成中的應(yīng)用可追溯到1976年，當(dāng)時美國研究人員Miller和Spooner[10]試圖在浮點測試數(shù)據(jù)生成中使用搜索算法，但是他們沒有繼續(xù)相關(guān)的工作；Khan等[11]將遺傳算法和變異分析方法進行融合用于測試數(shù)據(jù)自動生成，但只有運行變體，才能得到這個變體的分數(shù)，這就導(dǎo)致運行時間有所增加；何海鮮等[12]提出將布谷鳥改進算法用于測試數(shù)據(jù)自動生成，證明效果優(yōu)于其他算法，但是在降低冗余數(shù)據(jù)的生成效果方面并不明顯；Sahoo和Ray等[13]在測試數(shù)據(jù)生成中使用改進組合適應(yīng)度函數(shù)的粒子群算法可有效提高路徑覆蓋數(shù)量，但未考慮到覆蓋多個關(guān)鍵路徑的測試數(shù)據(jù)生成效率；Mahdieh等[14]提出將故障傾向性估計納入測試數(shù)據(jù)的優(yōu)先級排序中可提高測試數(shù)據(jù)的生成及優(yōu)先級排序效率，不足的是未考慮開發(fā)過程歷史中的測試用例執(zhí)行結(jié)果；何慶等[15]提出了在黑猩猩優(yōu)化算法中融合多策略，提高了算法的收斂速度，并在機械設(shè)計中得到很好的運用和效果，算法雖整體性能提高得不少，但其收斂速度相對過快。

雖上述文獻對各種啟發(fā)式優(yōu)化算法進行改進，在一定程度上能改善算法的尋優(yōu)精度和收斂效果[16-18]，進而提高測試數(shù)據(jù)的生成效率，但目前測試數(shù)據(jù)生成大多集中在啟發(fā)式搜索算法的某些單一算法上，如遺傳算法、蟻群算法等，這種算法有一些先天的局限，如過早收斂、搜索精度不足、容易陷入局部最優(yōu)解等[19-20]。另外，在測試數(shù)據(jù)生成方面對于新型的算法研究相對較少。黑猩猩優(yōu)化算法[21]（chimp optimization algorithm，ChOA）是2020年由Khishe等提出的一種新型算法。它不僅具有流程簡單、參數(shù)少、能與各種優(yōu)化問題結(jié)合的優(yōu)點，還具有兩大主要特點：一是將種群劃分為一個個獨立的個體，可以有效提高算法的勘探能力；二是引入混沌因子，有助于改善開發(fā)過程的收斂速度和精度[22]。不足是ChOA算法也存在易陷入局部最優(yōu)和收斂過早等問題。因此，本文提出一種正余弦擾動策略黑猩猩優(yōu)化算法，先使用拉丁超立方策略初始化種群，增加群體多樣化；其次引入非線性衰減收斂因子來平衡全局和局部開發(fā)能力；然后在位置更新時添加正余弦擾動因子，防止算法發(fā)生停滯現(xiàn)象；另外考慮到該算法目前尚未在測試數(shù)據(jù)生成領(lǐng)域中得到應(yīng)用，因此考慮將其應(yīng)用到測試數(shù)據(jù)的自動生成中；最后通過實驗對比驗證算法有效性及在測試數(shù)據(jù)生成中的生成效率和可行性[23]。

1 黑猩猩優(yōu)化算法

ChOA是由Khishe于2020年提出的一種較為新穎的啟發(fā)式搜索算法，它的原理是仿照黑猩猩的社會行為進行狩獵進而達到尋優(yōu)的目的，分為四類黑猩猩[24]，即，攻擊黑猩猩（attacker）、驅(qū)逐黑猩猩（driver）、阻礙黑猩猩（barrier）和追趕黑猩猩（chaser），四類黑猩猩中攻擊黑猩猩是領(lǐng)導(dǎo)者，其他三類配合領(lǐng)導(dǎo)者進行打獵。下面是黑猩猩在驅(qū)逐和追趕獵物過程的數(shù)學(xué)模型：

其中，t為當(dāng)前迭代次數(shù)，D是黑猩猩與獵物間的距離，XP為獵物的位置，XC為黑猩猩的位置，A、C、m均為系數(shù)矢量，且A是決定黑猩猩與獵物距離的系數(shù)矢量，C是控制黑猩猩驅(qū)逐和追趕獵物的系數(shù)矢量，m表示社會激勵對黑猩猩個體位置的影響，A、C、m的表達式為：

其中，R1、R2屬于[0，1]區(qū)間內(nèi)的隨機值，f為線性遞減因子。

四種黑猩猩的位置更新公式如下：

其中，X為當(dāng)前黑猩猩的位置，Xa、Xb、Xc和Xd分別表示攻擊黑猩猩、阻礙黑猩猩、驅(qū)逐黑猩猩及追趕黑猩猩的位置，X(t+1)表示更新后t+1代黑猩猩的位置，C1、C2、C3和C4均為隨機分別在[0，1]區(qū)間的數(shù)。

在狩獵過程黑猩猩位置更新的數(shù)學(xué)模型如下：

其中，μ是隨機分布在[0，1]區(qū)間內(nèi)的數(shù)，Chaotic-value為混沌因子。

2 改進黑猩猩優(yōu)化算法

目前，在基本的ChOA中，使用隨機分布的方式初始化種群，這種方式導(dǎo)致種群的多樣性降低；其次，算法使用線性收斂因子來平衡全局和局部開發(fā)能力，會導(dǎo)致算法尋優(yōu)速度遲緩；最后，原始算法存在易陷入局部極值現(xiàn)象。因此，針對基礎(chǔ)算法存在的局限，提出多種改進策略，具體介紹如下。

2.1 拉丁超立方策略初始化種群

很多原始的啟發(fā)式優(yōu)化算法均采用隨機方式初始化種群，隨機分布具有隨機性、不確定性，這種方式會導(dǎo)致種群分布不均及算法搜索能力下降，但是群體優(yōu)化算法又依賴于群體的初始化位置。而混沌狀態(tài)是自然界普遍存在的一種非線性現(xiàn)象，具有遍歷性、不重復(fù)性和對初始值敏感性的特點，很多學(xué)者根據(jù)這些特點將其應(yīng)用于到算法優(yōu)化問題。目前大多數(shù)文獻常用的混沌映射是Logistic映射，但是Logistic映射存在中間分布均勻、兩端分布密集的問題。針對上述存在的問題，本文提出采用拉丁超立方初始化種群，由于它具有均勻分層的特征，可以均勻遍布整個空間，覆蓋率更高，能以較小的采樣規(guī)模獲得較高的采樣精度，因此，LHS映射比隨機方式和Logistic映射分布較為均勻，用來初始化種群的效果更佳，三種方法的對比效果如圖1所示。

圖1 LHS、Logistic及隨機方式的頻率分布直方圖Fig.1 Frequency distribution histogram of LHS，Logistic and Random

設(shè)全局搜索范圍[UB,LB]，初始種群規(guī)模為N，每維xi變量的定義域區(qū)間劃分為N個相等的小區(qū)間，數(shù)學(xué)模型如下：

設(shè)搜索空間是二維空間，拉丁超立方初始化種群如圖2（a）和（b）所示。

圖2 拉丁超立方初始化種群分布映射和直方圖Fig.2 Latin hypercube initialization population distribution map and histogram

由圖2可知，拉丁超立方初始化種群可使種群分布得更加均勻，覆蓋率更加廣泛，因此，采用拉丁超立方進行初始化種群可以提高種群的多樣化和種群的質(zhì)量。

2.2 非線性衰減收斂因子

動態(tài)變化的衰減收斂因子種類繁多，如：線性衰減收斂因子、高斯衰減收斂因子、對數(shù)衰減收斂因子、指數(shù)衰減收斂因子等，在標(biāo)準(zhǔn)的ChOA中，一般采用線性遞減因子來控制算法的全局和局部開采能力，但是這種方式并不能較好地權(quán)衡算法的全局和局部勘察能力，導(dǎo)致算法搜索速度遲緩，圖3是5種收斂因子對比曲線圖。

圖3 收斂因子曲線圖Fig.3 Convergence factor graph

圖3中可以看出，在5種遞減策略中，雖然不同策略在不同程度上都可以平衡算法的探索和開發(fā)能力，但是如果在尋優(yōu)初期收斂因子衰減過快，會使算法全局探索能力變?nèi)?，存在易陷入局部極值的問題，所以非線性立方衰減策略更具優(yōu)勢，因此，本文提出一種非線性立方衰減收斂因子。在算法迭代初期先擴大算法的搜索空間進行大范圍的全局開采，提高算法的尋優(yōu)效果，在此過程中收斂因子逐漸下降，算法開始收縮搜索范圍進行小范圍的局部開發(fā)，局部勘察有助于算法在短時間內(nèi)找到最優(yōu)值。非線性立方衰減收斂因子的數(shù)學(xué)模型為：

其中，t當(dāng)前迭代數(shù)，Tm為最大迭代數(shù)，f"為非線性衰減收斂因子。

標(biāo)準(zhǔn)ChOA算法中的線性收斂因子呈線性衰減，而本文提出的非線性立方衰減因子呈非線性衰減，這種方法不僅增大了算法的搜索范圍，提高了算法的全局開拓能力，也有利于算法的局部開采，提高算法的尋優(yōu)精度，避免算法陷入局部極值，縮短算法的尋求最優(yōu)值的時間成本。

2.3 正余弦擾動因子

在標(biāo)準(zhǔn)的ChOA算法中，黑猩猩位置更新主要靠每次迭代進行更新，通過計算適應(yīng)度值，選擇其中最優(yōu)的作為攻擊者黑猩猩，攻擊黑猩猩是四類黑猩猩的領(lǐng)導(dǎo)者，其位置更新的好壞直接決定了整體算法尋優(yōu)的效率和準(zhǔn)確度，但是這種對攻擊者黑猩猩的強依賴性不利于算法的尋優(yōu)。當(dāng)陷入局部范圍搜索時，其周圍將聚集大量其他黑猩猩，進而會導(dǎo)致算法陷入局部最優(yōu)，無法探索搜索空間中的新區(qū)域。為了避免這種現(xiàn)象，本文提出將正余弦波信號進行改進后的正余弦波因子融入到黑猩猩位置更新過程，引入該因子可使算法跳出局部范圍，提高算法的尋優(yōu)能力，使其避免墜入局部最優(yōu)，其迭代100次的圖形如圖4所示。

圖4 正余弦擾動因子分布Fig.4 Sine and cosine perturbation factor distribution

利用正余弦擾動因子動態(tài)變化的不確定性對四類黑猩猩在位置更新時進行不同程度的擾動，使得四類黑猩猩能向更廣泛的區(qū)域進行搜索，擴大了算法的搜索規(guī)模，降低了其他黑猩猩盲目跟隨攻擊者黑猩猩的概率，提高了算法跳出局部極值的能力。

正余弦擾動因子的數(shù)學(xué)模型公式如下：

其中，r1、r2屬于[0，1]區(qū)間內(nèi)的隨機值，λ是控制參數(shù)。

在標(biāo)準(zhǔn)ChOA中引入正余弦擾動因子后的四類黑猩猩的位置更新公式為：

2.4 算法實現(xiàn)流程

綜合上述改進策略，本文提出的正余弦擾動策略黑猩猩優(yōu)化算法（SC-ChOA），它是在標(biāo)準(zhǔn)的ChOA基礎(chǔ)上進行的改進，引入三個策略，其一使用拉丁超立方初始化種群，其二將ChOA的線性收斂因子改進為非線性衰減收斂因子，其三對標(biāo)準(zhǔn)ChOA主要依賴攻擊黑猩猩的特點進行改進，使用正余弦擾動因子對四類黑猩猩位置進行擾動。SC-ChOA算法的輸入為拉丁超立方初始化種群及相關(guān)參數(shù)，輸出為最優(yōu)黑猩猩個體的位置，具體實現(xiàn)步驟及偽代碼如下：

步驟1初始化種群規(guī)模，最大迭代次數(shù)Tm、搜索范圍UB、LB，并設(shè)置相應(yīng)參數(shù)。

步驟2采用LHS初始化種群Xi，i=1,2,…,N。

步驟3計算每個個體的適應(yīng)度值，找出最優(yōu)的前四個值記為四種黑猩猩個體，分別記為Xa、Xb、Xc和Xd。

步驟4根據(jù)公式更新系數(shù)向量A、C及非線性衰減收斂因子的值f"。

步驟5通過正余弦擾動因子進一步更新四類黑猩猩的位置及其他黑猩猩的位置。

步驟6判斷是否達到最大迭代次數(shù)，若無，則跳轉(zhuǎn)到步驟3，否則結(jié)束算法，并輸出最優(yōu)黑猩猩的位置Xa。

SC-ChOA算法流程如圖5所示。

圖5 SC-ChOA算法流程圖Fig.5 SC-ChOA algorithm flowchart

2.5 時間復(fù)雜度分析

算法的時間復(fù)雜度是關(guān)于輸入規(guī)模n的函數(shù)，可直接反映算法的收斂速度，用來檢驗算法運行效率的關(guān)鍵指標(biāo)，在標(biāo)準(zhǔn)ChOA算法中，假設(shè)種群規(guī)模N，搜索空間維度n，參數(shù)初始化時間為t1，隨機初始化種群的時間為t2，則標(biāo)準(zhǔn)ChOA初始化階段的時間復(fù)雜度為：

設(shè)計算種群個體適應(yīng)度值所需時間為f(n)，選擇前四個最優(yōu)值個體位置的時間為t3，更新線性衰減收斂因子的時間為t4，根據(jù)前四個最優(yōu)個體更新種群其他黑猩猩個體位置所需時間為t5，則標(biāo)準(zhǔn)ChOA迭代尋優(yōu)階段的時間復(fù)雜度為：

因此，標(biāo)準(zhǔn)的ChOA算法迭代尋優(yōu)過程總的時間復(fù)雜度為：

在SC-ChOA算法中，初始化相關(guān)參數(shù)所需時間與標(biāo)準(zhǔn)ChOA相同，采用拉丁超立方策略初始化種群所需時間為t6，在算法迭代階段非線性衰減收斂因子遞減時間為t7，執(zhí)行正余弦擾動因子的時間為t8，更新四類黑猩猩位置所需時間為t9，則SC-ChOA算法的時間復(fù)雜度為：

根據(jù)相關(guān)文獻研究表明，遺傳算法（genetic algorithm，GA）的時間復(fù)雜度為：

綜上所述，SC-ChOA算法和標(biāo)準(zhǔn)ChOA算法的時間復(fù)雜度屬于同一數(shù)量級別，對算法改進并沒有增加算法的時間復(fù)雜度，且均小于GA算法的時間復(fù)雜度，即：

3 實驗仿真與結(jié)果分析

3.1 實驗設(shè)計與測試函數(shù)

實驗設(shè)備：Windows 10操作系統(tǒng)，計算機處理器3.30 GHz，內(nèi)存16 GB，算法使用MATLAB R2016a編寫。為了評價SC-ChOA算法的實際效果，與標(biāo)準(zhǔn)的ChOA[25]及常用的GA[26]進行實驗對比，選擇10個不同特征的測試函數(shù)，其中f1～f5為單峰值函數(shù)；f6～f8為多峰值函數(shù)；f9～f10為固定維度多峰函數(shù)，如表1所示。

表1 測試函數(shù)Table 1 Test function

3.2 算法尋優(yōu)性能分析

為了證明改進算法SC-ChOA的有效性及其動態(tài)收斂性，將本文加入的拉丁超立方初始化、非線性衰減收斂因子及正余弦擾動因子三個策略的SC-ChOA算法與標(biāo)準(zhǔn)ChOA算法及GA算法在10個不同特性的測試函數(shù)上進行實驗對比。

為確保實驗公平性，取空間維度d=30，最大迭代次數(shù)Tm=100，群體規(guī)模N=30，每個函數(shù)運行30次，取最優(yōu)值、平均值、標(biāo)準(zhǔn)差及算法的運行時間四個性能指標(biāo)來評價每個算法的尋優(yōu)效果，最優(yōu)值和平均值可以用來反映算法的尋優(yōu)效果和收斂速度，標(biāo)準(zhǔn)差可以反映算法的穩(wěn)定性和魯棒性，運行時間對應(yīng)算法的收斂速度，運行時間越少，說明算法收斂速度越快，反之亦然，具體對比結(jié)果如表2所示。

通過表2的最優(yōu)值和平均值可直接反映出算法的尋優(yōu)效果和收斂速度的能力。首先，從最優(yōu)值的結(jié)果可以看出，SC-ChOA在求解單峰函數(shù)f2、f4及多峰函數(shù)f6時均取得了最優(yōu)值0，在求解兩個固定維度多峰函數(shù)f9和f10時，也取得了最優(yōu)值1和3。在求解多峰值函數(shù)f7的最優(yōu)值時，因為f7是山谷形狀的，其全局最優(yōu)值位于山谷最低端，很難取到最優(yōu)值，但是SC-ChOA和ChOA的平均尋優(yōu)精度可達到10-80以上，而GA的平均尋優(yōu)精度只能達到10-70以上，另外，SC-ChOA相比于ChOA和GA在達到尋優(yōu)精度的基礎(chǔ)上，其運行時間也比標(biāo)準(zhǔn)ChOA和GA的運行時間少，這說明SC-ChOA在求解最優(yōu)值時不論單峰函數(shù)、多峰函數(shù)還是固定維度的多峰函數(shù)，SC-ChOA算法都具有良好的穩(wěn)定性和魯棒性。其次，從平均值的結(jié)果可以看出，標(biāo)準(zhǔn)ChOA求解函數(shù)最優(yōu)值的尋優(yōu)能力有限，而SC-ChOA在f2、f4和f6均獲得了最優(yōu)解，這是因為在標(biāo)準(zhǔn)ChOA中引入了正余弦擾動因子對函數(shù)局部最優(yōu)解進行了擾動，使其向全局最優(yōu)解靠攏，提高了算法的尋優(yōu)精度和收斂速度。在求解f5和f7時，SC-ChOA和ChOA的尋優(yōu)精度達到級別相近，均可直接收斂到最優(yōu)解附近，但是SC-ChOA相比于ChOA的運行時間少很多，提高了收斂速度，這是因為在標(biāo)準(zhǔn)ChOA中引入了非線性立方衰減收斂因子，有效平衡了算法的全局和局部搜索能力，加快算法收斂速度，縮短算法的尋求最優(yōu)值的時間成本。對于形狀類似于拋物面存在大量的局部極值的函數(shù)f1、f2、f3和f8，僅有改進的SC-ChOA取得了最優(yōu)值，而標(biāo)準(zhǔn)ChOA和GA均未取得最優(yōu)解，這說明在標(biāo)準(zhǔn)ChOA中引入三個策略得到的SC-ChOA算法更有助于求解具有大量局部極值的函數(shù)。綜上所述，無論在尋優(yōu)精度還是穩(wěn)定性上，融入三種策略的SC-ChOA均表現(xiàn)出一定的優(yōu)勢。

表2 10個測試函數(shù)實驗結(jié)果Table 2 Experimental results of 10 test functions

3.3 算法收斂性分析

為了更加直觀地反映三種算法在求解不同特征測試函數(shù)f1～f10的尋優(yōu)精度和動態(tài)收斂性，圖6給出了三種算法在10個測試函數(shù)的收斂曲線圖。

由圖6可以看出，對于10個測試函數(shù)，SC-ChOA在算法迭代初期的收斂曲線下降速度較快，在迭代末期的開拓性能也優(yōu)于其他兩個算法，且在整個尋優(yōu)迭代過程，SC-ChOA的收斂曲線均在ChOA和GA下面，這表明引入的拉丁超立方初始化種群和非線性衰減收斂因子策略不僅能保證算法的全局開拓能力和種群的多樣性，也有效提高了算法的收斂速度。圖6（a）～（e）是單峰函數(shù)的收斂曲線圖，從圖中可以看出，ChOA算法的收斂曲線在迭代初期T=30附近，均出現(xiàn)陷入算法停滯的現(xiàn)象，而改進算法SC-ChOA在迭代初期可以快速下降，且在整個迭代過程沒有出現(xiàn)明顯的陷入算法停滯的狀態(tài)，這表明融入的正余弦擾動因子策略能帶領(lǐng)群體找到全局最優(yōu)值，有助于群體跳出局部極值，進而有效地改進了標(biāo)準(zhǔn)ChOA算法存在的易陷入局部極值的問題，并且加入了非線性立方衰減收斂因子可有效平衡算法的全局和局部勘察能力；圖6（f）～（h）是多峰函數(shù)的收斂曲線圖，從圖中可以發(fā)現(xiàn)SC-ChOA的收斂曲線在整個迭代過程可快速下降，并取到最優(yōu)解，雖然在算法迭代初期ChOA的收斂曲線也可以快速下降，但其存在算法停滯現(xiàn)象，如f8在迭代次數(shù)T=40次后，算法沒能跳出局部極值完全進入了停滯狀態(tài)，導(dǎo)致算法最終未取到最優(yōu)解。而GA均為未取到最優(yōu)值，且SC-ChOA和ChOA的尋優(yōu)精度均比GA提高了至少50個數(shù)量級，這說明新型黑猩猩優(yōu)化算法的尋優(yōu)效果明顯優(yōu)于傳統(tǒng)的遺傳算法。對于函數(shù)f6、f7，雖然SC-ChOA和ChOA都能達到尋優(yōu)精度，但是SC-ChOA達到尋優(yōu)精度時所用的迭代次數(shù)明顯小于ChOA，如對于f6，SC-ChOA找到最優(yōu)值時所用的迭代次數(shù)大約為50次，而ChOA找到最優(yōu)值時所用的迭代次數(shù)大約為70次；對于f7，SC-ChOA找到最優(yōu)值時所用的迭代次數(shù)大約為30次，而ChOA找到最優(yōu)值時所用的迭代次數(shù)大約為50次，這進一步說明了引入正余弦擾動因子和非線性衰減收斂因子策略的SC-ChOA可以提高算法的收斂速度，減少算法找到最優(yōu)解時所消耗的迭代次數(shù)。圖6（i）、（j）是固定維度的多峰函數(shù)的收斂曲線圖，從圖中可以看出，三種算法均可達到尋優(yōu)精度，且SC-ChOA和ChOA的收斂曲線下降速度高于GA，另外，對于f9，SC-ChOA和ChOA找到最優(yōu)值時所用的迭代次數(shù)大約分別為35次、80次；對于f10，SC-ChOA和ChOA找到最優(yōu)值時所用的迭代次數(shù)大約分別為60次、90次，這明顯可以看出融入三種策略的SC-ChOA相比于標(biāo)準(zhǔn)ChOA在算法整個尋優(yōu)過程中的收斂速度有很大程度的提高，且SC-ChOA和ChOA均優(yōu)于GA。

圖6 三種算法收斂對比圖Fig.6 Convergence comparison chart of three algorithms

綜上所述，表2的實驗結(jié)果與圖6的收斂曲線驗證了本文所提改進算法的有效性。SC-ChOA均達到了尋優(yōu)精度，且收斂速度也是相對較快的，雖然ChOA在某些測試函數(shù)上未取到最優(yōu)值，但是其收斂速度優(yōu)于GA算法。因此，對于單峰函數(shù)、多峰函數(shù)及固定維度的多峰函數(shù)，無論在尋優(yōu)精度上，還是收斂速度上，SCChOA相比于ChOA和GA均具有較好的尋優(yōu)性能和收斂速度。

4 SC-ChOA測試數(shù)據(jù)生成應(yīng)用與分析

測試數(shù)據(jù)生成問題是軟件測試領(lǐng)域普遍關(guān)注的重要問題，測試數(shù)據(jù)的生成效率直接決定了軟件測試的整體效率。在軟件測試技術(shù)的探索中，出現(xiàn)了眾多測試數(shù)據(jù)生成方法，其中，基于啟發(fā)式優(yōu)化算法成為當(dāng)下學(xué)者的研究主流，其思想是將測試數(shù)據(jù)生成問題通過適應(yīng)度函數(shù)轉(zhuǎn)化為一個函數(shù)最優(yōu)化問題，然后利用啟發(fā)式優(yōu)化算法進行求解。本文為驗證改進算法SC-ChOA在解決實際問題中的有效性，將其應(yīng)用于測試數(shù)據(jù)生成中，下面進行詳細的介紹。

4.1 測試數(shù)據(jù)生成模型框架

測試數(shù)據(jù)生成模型主要包括3個模塊：

（1）靜態(tài)分析模塊

通過對測試程序的分析，得到程序控制流程圖，從中選擇測試程序的目標(biāo)路徑，并得到算法的部分參數(shù)。同時，根據(jù)流程圖得到測試主程序的插樁程序。

（2）測試驅(qū)動模塊

該模塊主要負責(zé)建立適應(yīng)度函數(shù)，在測試運行的過程中，輸入為算法返回的測試數(shù)據(jù)集，使用這些測試數(shù)據(jù)集驅(qū)動被測程序。并且通過適應(yīng)度函數(shù)評價測試用例，返回適應(yīng)度值給算法部分。

（3）算法生成測試數(shù)據(jù)模塊

該模塊是測試數(shù)據(jù)自動生成的重要模塊。算法完成初始化任務(wù)后，將初始數(shù)據(jù)輸入到測試驅(qū)動模塊，對測試驅(qū)動模塊傳來的適應(yīng)度值進行檢查，判斷當(dāng)前運行結(jié)果是否是最優(yōu)解或迭代次數(shù)達到最大，若符合條件，算法終止，輸出最優(yōu)的測試數(shù)據(jù)，否則繼續(xù)迭代，直到找到最優(yōu)解。改進啟發(fā)式搜索算法的測試生成模型框架如圖7所示。

圖7 基于SC-ChOA算法的測試數(shù)據(jù)生成模型框架Fig.7 Test data generation model framework based on SC-ChOA algorithm

4.2 程序插樁技術(shù)與適應(yīng)度函數(shù)構(gòu)造

4.2.1 程序插樁技術(shù)

程序插樁技術(shù)是由Gallagher提出的，思想是在每個語句分支中插入適當(dāng)函數(shù)獲取執(zhí)行時的信息，來評價測試數(shù)據(jù)。被測程序的測試技術(shù)是由Huang最先發(fā)明的，在程序結(jié)構(gòu)中添加代碼來收集程序執(zhí)行信息，并用以記錄在驅(qū)動程序工作過程中測試結(jié)果的內(nèi)在活動和關(guān)鍵特性[27]。

測試數(shù)據(jù)自動生成系統(tǒng)的主要實現(xiàn)方式是基于測試程序中的樁插入，其基本思路為：

（1）首先對數(shù)據(jù)進行隨機初始化；

（2）判斷單個驅(qū)動程序執(zhí)行路徑與目標(biāo)路徑的偏差；

（3）最后采用逐步迭代的方法生成測試數(shù)據(jù)。

為了更好地解釋程序插樁法，以三角形類型判斷為例進行插樁，三角形決策流程圖如圖8所示。

圖8 三角形類型判定程序流程圖Fig.8 Flowchart of triangle type judgment program

以下是插樁后的三角形類型判別MATLAB源代碼：

4.2.2 構(gòu)造適應(yīng)度函數(shù)

算法是否需要進行迭代的依據(jù)是個體的適應(yīng)度值，適應(yīng)度函數(shù)的構(gòu)造是測試操作模塊的關(guān)鍵技術(shù)，也是SC-ChOA算法應(yīng)用于測試數(shù)據(jù)自動生成的重要環(huán)節(jié)，測試數(shù)據(jù)的生成轉(zhuǎn)化為使用SC-ChOA算法尋找目標(biāo)函數(shù)的最優(yōu)解的過程，因此適應(yīng)度函數(shù)的構(gòu)造將影響算法在測試數(shù)據(jù)自動生成中的效率。適應(yīng)度函數(shù)使用分支謂詞的分支距離計算，如表3所示。

表3 分支謂詞的距離構(gòu)造函數(shù)Table 3 Distance constructors for branch predicates

評價測試數(shù)據(jù)的好壞的一個重要標(biāo)準(zhǔn)是程序執(zhí)行過程的覆蓋率，計算覆蓋率首先需要對被測程序的分支進行插樁，再對被測程序的目標(biāo)路徑進行插樁。覆蓋率公式為：

其中，Xi表示第i分支的測試數(shù)據(jù)，x表示該分支的值，f(i)表示第分支的覆蓋率。若f(i)≤0表示覆蓋該分支，則令f(i)=0；若f(i)＞0，則該值就是測試數(shù)據(jù)和分支的距離，值越大意味著測試數(shù)據(jù)離分支越遠。總的適應(yīng)度函數(shù)公式如下：

其中，F(xiàn)的取值范圍在（0，1]之間，值越大則表示測試數(shù)據(jù)越好。當(dāng)F=1時，表示該測試數(shù)據(jù)可完全覆蓋該目標(biāo)路徑。

4.3 應(yīng)用與分析

實驗選取7個常用的程序作為基準(zhǔn)程序，這些程序具有代表性，不僅包含選擇結(jié)構(gòu)、循環(huán)結(jié)構(gòu)及復(fù)雜的嵌套結(jié)構(gòu)，還含有算術(shù)運算符、關(guān)系運算符和邏輯運算符及整型、浮點型、字符型、字符串等數(shù)據(jù)類型，常被用于測試數(shù)據(jù)生成領(lǐng)域。程序的具體描述，其程序ID、變量數(shù)、分支數(shù)、搜索范圍和程序描述如表4所示。

表4 測試基準(zhǔn)程序Table 4 Test benchmark

為保證實驗的公正性，3種算法在某些參數(shù)設(shè)置上保持一致，如群體大小、最大迭代次數(shù)等，其他參數(shù)參考其他文獻設(shè)置，并使用迭代次數(shù)、覆蓋率、生成測試數(shù)據(jù)數(shù)及運行時間為評價標(biāo)準(zhǔn)。

以三角形類型判定程序為例，通過三種算法進行實驗比較，取平均值為評價標(biāo)準(zhǔn)。實驗結(jié)果的相關(guān)數(shù)據(jù)如表5所示。

表5 三角形類型判別程序?qū)嶒灲Y(jié)果Table 5 Experimental results of triangle discriminator

由表5可知，改進算法SC-ChOA和標(biāo)準(zhǔn)ChOA比GA算法具有更高的效率，且覆蓋率均達到了100%，而GA覆蓋率只達到了90%，這是因為GA算法未生成覆蓋目標(biāo)路徑等邊三角形的測試數(shù)據(jù)。雖然標(biāo)準(zhǔn)ChOA和改進算法SC-ChOA的覆蓋率都達到了100%，但是SC-ChOA在生成覆蓋目標(biāo)路徑的測試數(shù)據(jù)時，生成測試數(shù)據(jù)總數(shù)僅有517個、所用的迭代次數(shù)只有14次，而ChOA相對于SC-ChOA產(chǎn)生了較多的冗余測試數(shù)據(jù)，且所用的迭代次數(shù)遠大于SC-ChOA。因此，SC-ChOA相比于ChOA和GA在生成滿足條件的測試數(shù)據(jù)效率方面及降低所用迭代次數(shù)上均具有一定的優(yōu)勢。為了更直觀地看出三種算法在生成測試數(shù)據(jù)上的對比效果，圖9是程序1使用三種算法生成覆蓋目標(biāo)路徑的測試數(shù)據(jù)總數(shù)和迭代次數(shù)的直方圖。

圖9 程序1生成的測試數(shù)據(jù)總數(shù)和迭代次數(shù)Fig.9 Total number of test data and number of iterations generated by program 1

使用和三角形類別判定同樣的方法及參數(shù)設(shè)置對表2中其他測試程序進行對比實驗，為了更直觀地看出SC-ChOA算法與其他兩種算法在生成測試數(shù)據(jù)方面的效率，圖10（a）和（b）是生成滿足目標(biāo)路徑的測試數(shù)據(jù)所生成的測試數(shù)據(jù)總量及迭代總數(shù)。

圖10 七個基準(zhǔn)程序測試數(shù)量和迭代次數(shù)對比Fig.10 Comparison of number of tests and number of iterations for seven benchmarks

由圖10可以看出，本文提出的SC-ChOA算法生成滿足目標(biāo)路徑的測試數(shù)據(jù)總數(shù)和此過程所用的迭代次數(shù)的折線圖均在ChOA和GA下面，這說明了改進的SC-ChOA算法不僅提高了測試數(shù)據(jù)生成的效率，減少了冗余數(shù)據(jù)的生成，還降低了生成滿足條件的測試數(shù)據(jù)所使用的迭代次數(shù)，這是因為在標(biāo)準(zhǔn)ChOA引入了正余弦擾動因子和非線性衰減收斂因子，使算法更好地平衡全局和局部搜索能力，避免算法陷入局部最優(yōu)，減少了迭代次數(shù)，進而降低了冗余數(shù)據(jù)的生成。因此，SCChOA算法相比于其他兩種算法在測試數(shù)據(jù)生成效率方面更具有優(yōu)勢。

圖11是對七個基準(zhǔn)程序進行10次實驗所使用的運行時間，可明顯看出，SC-ChOA算法很大程度上降低了在生成滿足條件的測試數(shù)據(jù)的運行時間，這歸因于SC-ChOA算法的尋優(yōu)精度和收斂速度優(yōu)于其他兩種算法。

圖11 七個基準(zhǔn)程序三種算法運行時間Fig.11 7 benchmark program run-time of three algorithms

綜上所述，本文提出的改進算法SC-ChOA可有效平衡整體和局部搜尋，不僅在測試數(shù)據(jù)生成的覆蓋率上有所提高，還降低了生成測試數(shù)據(jù)的迭代次數(shù)和時間，進而改善了測試數(shù)據(jù)的生成速率和效果。

5 結(jié)束語

為提高測試數(shù)據(jù)的生成效率，本文對標(biāo)準(zhǔn)ChOA進行改進提出引入多攻略的正余弦擾動黑猩猩優(yōu)化算法并將其用于測試數(shù)據(jù)生成方面。首先，引入拉丁超立方初始化種群，增加種群的多樣化；其次，對標(biāo)準(zhǔn)ChOA算法進行改進，并提出非線性衰減收斂因子，用于權(quán)衡算法的全局勘察和局部開采能力，縮短算法的收斂時間，進而加快收斂速度；另外，在黑猩猩每次迭代過程中融入正余弦擾動因子，阻止算法陷入局部范圍搜索，而導(dǎo)致算法出現(xiàn)停滯現(xiàn)象；最后，使用測試函數(shù)與標(biāo)準(zhǔn)ChOA算法及GA算法進行實驗對比，驗證算法的有效性，并將其應(yīng)用于測試數(shù)據(jù)生成領(lǐng)域。通過基準(zhǔn)程序?qū)θN不同算法進行實驗對比，結(jié)果表明，本文提出的算法SC-ChOA更加有效，可以應(yīng)用于軟件測試的全過程。在未來的工作中，將進一步思考如何將該算法與其他智能優(yōu)化算法進行合理的融合，使其更好地應(yīng)用于測試數(shù)據(jù)的生成及并行測試中。