丁懷寶

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

關(guān)鍵詞： 配對組合測試; 人工蜂群（ABC）算法; 粒子群優(yōu)化（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 ?引 ?言

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

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

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

1 ?相關(guān)知識

1.1 測試用例集的表示方式

1.1.1 覆蓋矩陣（CA）[9]

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

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

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

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

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

1.2 人工蜂群（ABC）算法

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

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

ABC算法主要步驟如下：

Step 1 ?初始化設(shè)置，產(chǎn)生初始蜂群;

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

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

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

Step 5 ?記錄迄今為止最優(yōu)的蜜源;

Step 6 ?如果滿足算法結(jié)束條件，則輸出最優(yōu)解;否則，轉(zhuǎn)到Step 2.

1.3 粒子群優(yōu)化（PSO）算法

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

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]的均勻分布隨機數(shù);w為權(quán)重因子，用于平衡全局搜索和局部搜索;c1，c2是加速常數(shù)或?qū)W習(xí)因子，用于調(diào)節(jié)該粒子向自身已尋找的最優(yōu)位置和同伴已尋找的最優(yōu)位置方向飛行的最大步長，取值[0，2].vid是粒子先前的速度;c_1×r_1×（p_id-x_id）為“自身認知”部分，是從當前點指向粒子自身最好點的一個矢量，表示粒子自身的經(jīng)驗或記憶;c_2×r_2×（g_id-x_id）為“群體認知”部分，是從當前點指向種群最好點的一個矢量，表示粒子間的信息共享和相互合作.粒子通過自身的經(jīng)驗和同伴中最好的經(jīng)驗決定下一步的運動，從而有效地搜索到最好的位置.

PSO算法主要步驟如下：

Step 1 ?初始化粒子群中各個參數(shù);

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

Step 3 ?比較粒子的當前適應(yīng)度值與歷史最優(yōu)適應(yīng)度值，更新歷史最優(yōu)值;

Step 4 ?比較當前適應(yīng)度與種群歷史最優(yōu)位置適應(yīng)度值，更新歷史最優(yōu)值;

Step 5 ?若獲得最優(yōu)值，則輸出最優(yōu)值結(jié)果;否則，跳轉(zhuǎn)Step 2繼續(xù)進行迭代.

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

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

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

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]的均勻分布隨機數(shù)，pa是HABC算法子種群中的隨機蜜源（隨機解）.與1.3節(jié)相同，適應(yīng)度值（概率）較高的蜜源會被優(yōu)先選擇.

HABC算法主要步驟如下：

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

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

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

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

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

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

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

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

3 ?實驗結(jié)果

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

1） 待測系統(tǒng)1：CCA（N，2，33，F(xiàn){}），其中，F(xiàn)={（-1，2，0），（-1，1，0），（0，-1，1），（2，2，-1），（2，-1，2），（1，2，2）};

2） 待測系統(tǒng)2：CCA（N，2，43，F(xiàn){}），其中，F(xiàn)={（0，1，-1），（2，-1，3），（3，3，0），（2，1，-1）}.

3） 待測系統(tǒng)3：CCA（N，2，53，F(xiàn){}），其中，F(xiàn)={（1，1，-1），（4，-1，2），（4，-1，4），（4，3，1），（4，2，-1），（1，3，-1）}.

4） 待測系統(tǒng)4：CCA（N，2，63，F(xiàn){}），其中，F(xiàn)={（3，5，-1），（-1，3，4），（2，0，-1），（-1，1，2），（3，-1，1），（-1，3，1），（5，4，4）}.

5） 待測系統(tǒng)5：CCA（N，2，73，F(xiàn){}），其中，F(xiàn)={（-1，0，5），（5，5，3），（4，-1，0），（6，4，-1），（1，4，-1），（6，3，-1）}.

由于PHABC策略的隨機性，使每個待測系統(tǒng)獨立運行20次獲取最優(yōu)解，得到各策略對于帶有約束的待測系統(tǒng)產(chǎn)生的測試用例數(shù)量，如表1所示.

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

4 ?結(jié) ?論

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

參考文獻：

[1] 聶長海，徐文寶，史亮.一種新的二水平多因素系統(tǒng)兩兩組合覆蓋測試數(shù)據(jù)生成算法 [J].計算機學(xué)報，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] 王艷玲，李龍澍，胡哲.群體智能優(yōu)化算法 [J].計算機技術(shù)與發(fā)展，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.

（責(zé)任編輯：包震宇）