配對組合測試用例集生成的一種新策略

丁懷寶

摘 ?要： 基于人工蜂群（ABC）算法與粒子群優化（PSO）算法，提出了一種新的配對混合人工蜂群（PHABC）策略，用于求解含約束條件的配對組合測試中測試用例集的生成問題.實驗結果表明，即使在帶有參數約束的情況下，PHABC輸出的最佳組合測試集結果正確性更高，相較于其他現有的策略，性能更優.

關鍵詞： 配對組合測試; 人工蜂群（ABC）算法; 粒子群優化（PSO）算法; 配對混合人工蜂群算法（PHABC）; 約束

文獻標志碼： TP 312 ? ?文獻標志碼： A ? ?文章編號： 1000-5137（2020）04-0472-06

Abstract： A new pairwise hybrid artificial bee colony （PHABC） strategy based on artificial bee colony （ABC） algorithm and particle swarm optimization （PSO） algorithm was proposed in this paper.The novel algorithm could be used to resolve the generation of pairwise test suite with existing constraint factors.The results of the experiment showed that the accuracy of the PHABC output was more higher and the performance was more excellent than the existing research strategies，even with existing constraint factors.

Key words： pairwise testing; artificial bee colony（ABC） algorithm; particle swarm optimization（PSO） algorithm; pairwise hybrid artificial bee colony （PHABC） strategy; constraint

0 ?引 ?言

組合測試充分考慮了系統中各種因素以及因素間相互作用可能產生的影響，根據實際需要，用盡可能少的測試數據，盡可能多地覆蓋一些影響系統的因素.這種測試方法對于由系統中某些因素相互作用而導致的軟件故障具有較強的檢測能力.根據覆蓋程度的不同，組合測試方法可以分為：單因素覆蓋、兩兩組合覆蓋和三三組合覆蓋等.

兩兩組合覆蓋的組合測試，即配對組合測試，要求系統的任何一對輸入參數都必須被至少一個測試用例所覆蓋.研究發現，許多軟件系統的故障由測試參數及其之間的相互作用引起，因此，配對組合測試方法具有較高的理論研究價值和現實意義[1].

配對組合測試用例集可表示為2維覆蓋數組，參數之間存在約束條件的配對組合測試用例集可表示為2維約束覆蓋數組.為了提高測試的效率，2維約束覆蓋數組的規模應盡可能小.為此，很多搜索算法被應用到尋找規模最小或近似最小的2維約束覆蓋數組中.主要包括HSS[2]，SA_SAT[3]，mAETG_SAT[4]，PICT[5]，BTS[6]和LAHC[7]等.這些研究策略都是基于不同算法的改進策略，在解決配對組合測試用例集生成問題方面各有優勢.但是，生成最佳測試用例集仍然是一個多項式復雜程度的非確定性（NP）難題，尚待進一步探索.因此，本文提出了一種新的優化算法——混合人工蜂群（HABC）算法，該算法有效解決了ABC[8]算法中存在的初始參數隨機化問題和易陷入局部最優解等問題.此算法具體實施在帶有約束條件的配對組合測試用例集生成問題中，故稱為配對混合人工蜂群（PHABC）策略.

1 ?相關知識

1.1 測試用例集的表示方式

1.1.1 覆蓋矩陣（CA）[9]

組合測試用例集的測試用例列表CA（N;t，vp）包含4個基本參數：N，t，p和v，其中N表示測試用例的個數;t表示維數;p表示參數個數;v表示參數值的個數.例如，CA（25;2，56）表示該系統的測試用例集為2維矩陣（即兩兩組合），有25個測試用例（矩陣的行數），6個參數（矩陣的列數），每個參數可能的值的個數為5.CA要求所有參數值的類型要保持一致.

1.1.2 混合覆蓋矩陣（MCA）[9]

MCA（N;t，v_1^（p_1 ），v_2^（p_2 ），…，v_n^（p_n ））具有與CA參數相同的含義，但支持允許參數具有不同類型的值，其中，n表示參數總數.例如，MCA（36;2，536427）表示該混合覆蓋矩陣中有36個測試用例，該系統的測試用例集為2維矩陣，共有14個參數，包括3個具有5個值的參數，4個具有6個值的參數，7個具有2個值的參數.

1.1.3 約束覆蓋矩陣（CCA）[9]

除了CA和MCA，組合測試用例集中由于約束條件的限制，禁止出現的測試用例以CCA（N;t，vp，F{}）表示，其中，F{}表示被禁止的組合.例如，CCA（N;2，24，F{}），當F={（1，-1，0，-1），（-1，1，0，-1）}時，其中，-1表示非參數值，該系統的測試用例集為2維矩陣，且測試用例數量為16（24）個，（1，-1，0，-1）和（-1，1，0，-1）被禁止出現在最后的測試用例集中.

1.2 人工蜂群（ABC）算法

ABC算法將人工蜂群置于搜索空間中，尋找花蜜量高（適應度值）的蜜源的位置（可行解），得到最高蜂蜜量的蜜源的位置（最優解）.

ABC算法中，蜂群由受雇蜂、跟隨蜂和偵察蜂三類組成，其中一半的蜜蜂作為受雇蜂，剩余的一半作為跟隨蜂.受雇蜂尋找較高花蜜量的蜜源，并將蜜源信息（路線、位置和周邊潛在的蜜源）傳達給跟隨蜂;跟隨蜂根據受雇蜂提供的信息對蜜源進行搜索選擇.偵察蜂從受雇蜂中衍生而來，在原有蜜源被拋棄后，尋找新的、更好的蜜源.人工蜂群的行為方式可分為4個階段：蜜源初始化階段、受雇蜂階段、跟隨蜂階段及偵察蜂階段.通過不同階段的搜索操作，不斷執行循環迭代，直至找到蜂群的最優解或達到指定的迭代次數.

ABC算法主要步驟如下：

Step 1 ?初始化設置，產生初始蜂群;

Step 2 ?每只受雇蜂在其對應的蜜源及其鄰域進行搜索，并計算新搜索到的蜜源的適應度值，選擇保存適應度更高的蜜源的位置;

Step 3 ?跟隨蜂會根據受雇蜂帶回來的蜜源信息（適應度值）計算蜜源被選擇的概率，從而選擇一個蜜源位置，并在其鄰域進行搜索，若新搜索到的蜜源的適應度值優于原蜜源，則將新蜜源位置取代原蜜源位置;

Step 4 ?若某蜜源位置被搜索次數超過閾值，仍沒有找到具有更高適應度值的蜜源，則放棄該蜜源位置，同時受雇蜂轉化為偵察蜂，隨機搜索新的蜜源;

Step 5 ?記錄迄今為止最優的蜜源;

Step 6 ?如果滿足算法結束條件，則輸出最優解;否則，轉到Step 2.

1.3 粒子群優化（PSO）算法

PSO[10]算法通過群體中個體之間的協作和信息共享尋找最優解，其優點在于能求出多個粒子并存或合作時的最優解.假設種群中存在m個粒子，n個粒子群，第i個粒子的個體最優解為pid，i=1，2，…，m，d=1，2，…，n，所在整體粒子群的最優解為全局最優解gid，用d維速度vi=（vi1，vi2，…，vid）與位置xi=（xi1，xi2，…，xid）改變粒子的狀態，通過不斷變化速度與位置，產生新一代粒子群

v_i （d+1）=w×v_id+c_1×r_1×（p_id-x_id）+c_2×r_2×（g_id-x_id）， （1）

x_（i（d+1））=x_id+v_id， （2）

其中，r1，r2是[0，1]的均勻分布隨機數;w為權重因子，用于平衡全局搜索和局部搜索;c1，c2是加速常數或學習因子，用于調節該粒子向自身已尋找的最優位置和同伴已尋找的最優位置方向飛行的最大步長，取值[0，2].vid是粒子先前的速度;c_1×r_1×（p_id-x_id）為“自身認知”部分，是從當前點指向粒子自身最好點的一個矢量，表示粒子自身的經驗或記憶;c_2×r_2×（g_id-x_id）為“群體認知”部分，是從當前點指向種群最好點的一個矢量，表示粒子間的信息共享和相互合作.粒子通過自身的經驗和同伴中最好的經驗決定下一步的運動，從而有效地搜索到最好的位置.

PSO算法主要步驟如下：

Step 1 ?初始化粒子群中各個參數;

Step 2 ?利用適應度值公式計算每一個粒子的適應度值;

Step 3 ?比較粒子的當前適應度值與歷史最優適應度值，更新歷史最優值;

Step 4 ?比較當前適應度與種群歷史最優位置適應度值，更新歷史最優值;

Step 5 ?若獲得最優值，則輸出最優值結果;否則，跳轉Step 2繼續進行迭代.

2 ?配對混合人工蜂群（PHABC）策略

為獲得比PSO和ABC算法更出色的性能，結合兩者的優點，針對帶有約束條件的配對組合測試用例集的生成問題，提出了一種新的算法——混合人工蜂群（HABC）算法.HABC算法利用PSO算法中的各粒子之間的信息共享能力改進ABC算法中初始蜜源隨機化的問題，同時利用其較強的全局搜索能力，緩解ABC算法易陷入局部最優解問題.

如果一個新粒子被選擇的概率大于當前粒子被選擇的概率，則更新粒子位置和速度，通過引入與蜂群共享的信息更新其速度

v_（i（d+1））=w×v_id+c_1×r_1×（p_id-x_id）+c_2×r_2×（g_id-x_id）+c_3×r_3×（pa_d-x_id）， （8）

其中，r3和r1，r2類似，是分布在[0，1]的均勻分布隨機數，pa是HABC算法子種群中的隨機蜜源（隨機解）.與1.3節相同，適應度值（概率）較高的蜜源會被優先選擇.

HABC算法主要步驟如下：

Step 1 ?分別初始化ABC和PSO子群;

Step 2 ?每只受雇蜂在其對應的蜜源鄰域進行搜索，并計算新蜜源的適應度值，若其適應度值更高，則新蜜源位置取代原蜜源位置;

Step 3 ?跟隨蜂根據受雇蜂帶回來的蜜源信息（適應度值），計算該蜜源被選擇的概率，定位概率最高的蜜源，并在該蜜源鄰域進行搜索，若新蜜源的適應度值高于原蜜源，則新蜜源位置取代原蜜源位置;

Step 4 ?若新蜜源被選擇的概率高于原蜜源，則新蜜源取代原蜜源位置;否則，受雇蜂（或跟隨蜂）變成偵察蜂，隨機選擇一個蜜源，算法迭代次數增1;

Step 5 ?執行粒子群搜索階段，如果一個新粒子被選擇的概率大于當前概率，則更新粒子位置和速度;否則，繼續搜索粒子，算法迭代次數增1;

Step 6 ?將各子種群的最優解作為全局最優解，如果2個子種群中任何一個算法滿足終止條件，則算法終止，輸出最優解;否則，算法轉到Step 2.

HABC算法流程圖如圖1所示.

將混合人工蜂群算法（HABC）運用到配對組合測試（pairwise testing）用例生成的策略稱為PHABC策略.

3 ?實驗結果

將PHABC策略與目前比較流行的工具和策略BTS，mAETG_SAT，HSS，PICT，SA_SAT和LAHC相比較，基準數據從現有已發布結果的相關研究中獲取[6-7，11-12].為了獲得最佳結果，已將PHABC參數調整為c1=c2=c3=2.0，w=0.9，ABC算法最大迭代次數為100，PHABC算法最大迭代次數為1 000次，最優解個數為N=5.該實驗是在Windows 7操作系統臺式計算機上進行，Java版本JDK1.8.實驗中含約束的待測系統CCA如下：

1） 待測系統1：CCA（N，2，33，F{}），其中，F={（-1，2，0），（-1，1，0），（0，-1，1），（2，2，-1），（2，-1，2），（1，2，2）};

2） 待測系統2：CCA（N，2，43，F{}），其中，F={（0，1，-1），（2，-1，3），（3，3，0），（2，1，-1）}.

3） 待測系統3：CCA（N，2，53，F{}），其中，F={（1，1，-1），（4，-1，2），（4，-1，4），（4，3，1），（4，2，-1），（1，3，-1）}.

4） 待測系統4：CCA（N，2，63，F{}），其中，F={（3，5，-1），（-1，3，4），（2，0，-1），（-1，1，2），（3，-1，1），（-1，3，1），（5，4，4）}.

5） 待測系統5：CCA（N，2，73，F{}），其中，F={（-1，0，5），（5，5，3），（4，-1，0），（6，4，-1），（1，4，-1），（6，3，-1）}.

由于PHABC策略的隨機性，使每個待測系統獨立運行20次獲取最優解，得到各策略對于帶有約束的待測系統產生的測試用例數量，如表1所示.

由表1可以看出，PHABC算法比其他策略的運行結果更好，在1號待測系統和5號待測系統中產生了更少的測試用例數量，BTS，HSS，LAHC和SA_SAT次之，mATEG_SAT和PICT運行結果較差.

4 ?結 ?論

將ABC和PSO算法有機結合，提出PHABC策略，用于求解含約束條件的配對組合測試中測試用例集的求解問題.通過實驗分析，證明該策略的可行性及高效性.在以后的研究工作中，將進一步改進PHABC策略，使其能夠適用于所有交互強度的組合測試.

參考文獻：

[1] 聶長海，徐文寶，史亮.一種新的二水平多因素系統兩兩組合覆蓋測試數據生成算法 [J].計算機學報，2006，29（6）：841-848.

NI C H，XU W B，SHI L.A new pairwise covering test data generation algorithm for the system with many 2-level factors [J].Chinese Journal of Computers，2006，29（6）：841-848.

[2] ALSEWARI A R A，ZAMLI K Z.Design and implementation of a harmony-search-based variable-strength t-way testing strategy with constraints support [J].Information and Software Technology，2012，54（6）：553-568.

[3] COHEN M B，DWYERM B，SHI J.Constructing interaction test suites for highly-configurable systems in the presence of constraints：a greedy approach [J].IEEE Transactions on Software Engineering，2008，34（5）：633-650.

[4] COHEN M B，DWYER M B，SHI J.Exploiting constraint solving history to constructinteraction test suites [C]//Academic and Industrial Conference Practice and ResearchTechniques.Windsor：IEEE，2007：121-132.

[5] CZERWONKA J.Pairwise testing in real world [C/OL]//Proceedings of 24th Pacific Northwest Software Quality Conference，2006[2020-05-30].http：//msdn.microsoft.com/en-us/library/cc150619.

[6] ALSARIERA Y A，AHMED H A S，ALAMRI H S，et al.A bat-inspired testing strategy for generating constraints pairwise test suite [J].Advanced Science Letters，2018，24：7245-7250.

[7] ZAMLI K Z，ALSEWARI A R，AL-KAZEMI B.Comparative benchmarking of constraints t-way test generation strategy based on late acceptance hill climbing algorithm [J].International Journal of Software Engineering & Computer Sciences，2015，1：15-27.

[8] KARABOGA D.An idea based on honey bee swarm for numerical optimization [R].Kayseri：Erciyes University，2005.

[9] 王艷玲，李龍澍，胡哲.群體智能優化算法 [J].計算機技術與發展，2008，18（8）：114-117.

WANG Y L，LI L S，HU Z.Swarm intelligence optimization algorithm [J].Computer Technology and Development，2008，18（8）：114-117.

[10] KENNEDY J，EBERHART R.Particle swarm optimization[C]//International Conference on Neural Networks.Honolulu：IEEE，2002：1-23.

[11] ALSEWARI A A，ZAMLI K Z，ALKAZEMI B.Generating t-way test suite in the presence of constraints [J].Journal of Engineering and Technology，2015，6（2）：52-66.

[12] LI L S，CUI Y X，YANG Y.Combinatorial test cases with constraints in software systems [C]//International Conference on Computer Supported Cooperative Work in Design.Wuhan：IEEE，2012：195-199.

（責任編輯：包震宇）