[發明專利]基于CS-SPSO算法的組合測試用例生成方法

有效

• 申請號: 201910596404.4
• 申請日: 2019-07-03
• 公開（公告）號: CN110334026B
• 公開（公告）日: 2023-03-24
• 發明（設計）人: 包曉安;金瑜婷;董亮亮;郭煒杰
• 申請（專利權）人: 浙江理工大學
• 主分類號: G06F11/36
• 分類號: G06F11/36;G06N3/006
• 代理公司: 杭州求是專利事務所有限公司 33200
• 代理人: 鄭海峰

1.一種基于CS-SPSO算法的組合測試用例生成方法，其特征在于包括如下步驟：

(1)對輸入空間進行建模，獲取各因素及其取值范圍；

(2)通過對約束條件分析，獲取需覆蓋的n個因素的取值組合，即組合覆蓋集S；

(3)根據n個因素中包含的取值范圍個數對n個因素進行非遞增排序，按照排序最靠前的兩個因素的取值進行組合并進行約束條件的分析，得到兩兩組合集S′，其中兩兩組合集S′中包含了若干個兩兩組合；

(4)從S′中隨機取出一個兩兩組合s′，將剩余的n-2個因素與s′生成的所有組合映射成粒子，初始化每個粒子的位置矢量X_i，并分成N個等大的小種群，各小種群在各自所在的領域并行尋優；

(5)每個小種群并行計算適應度函數，得到每個粒子的適應值；

(6)更新每個粒子的最佳位置p_i和整個種群的最佳位置p_g，根據粒子與當前最優粒子之間的距離對慣性權重w進行自適應調整，尋找個體最優解和群體最優解，直到達到預設的最大迭代次數；

所述的步驟(6)具體為：

第i個粒子在第t代時用一個位置指標來描述：為d維向量；第i個粒子搜索至第t代時的個體歷史最優位置為p_i＝(p_i1，p_i2，…，p_ij，…，p_id)，搜索至第t代時的整個粒子群的歷史最優位置為p_g＝(p_g1,p_g2,…,p_gd)，則在第t+1代時，第i個粒子的第j維位置的迭代更新公式如下：

其中，w為慣性權重，對下次移動產生影響，c₁和c₂為學習因子，r₁和r₂為[0,1]內的隨機數；

w的更新公式如下：

其中，w_max、w_min分別表示初始化時慣性權重的最大值和最小值，f(.)表示適應度函數，表示平均適應值；

(7)將N個小種群的群體最優解作為布谷鳥算法的初始值，通過Lévy飛行計算出全局最優解，生成單條測試用例；

(8)將步驟(7)生成的單條測試用例存入組合測試用例集TS中，并從組合覆蓋集S中剔除已覆蓋的組合，得到新的組合覆蓋集S(t+1)，從兩兩組合集S′中剔除兩兩組合s′，得到新的兩兩組合集S′(t+1)；

(9)判斷兩兩組合集S′(t+1)是否為空，若否，重復步驟(4)～(8)，若是，執行步驟(10)；

(10)判斷組合覆蓋集S(t+1)是否為空，若是，輸出組合測試用例集TS，若否，則隨機取出組合覆蓋集S(t+1)中的一個取值組合，重復步驟(4)～(9)。

2.根據權利要求1所述的基于CS-SPSO算法的組合測試用例生成方法，其特征在于所述的步驟(7)具體為：

(7.1)將N個小種群各自的歷史最優位置p_g作為初始鳥巢位置x_i；

(7.2)計算鳥巢位置的適應值fitness(x_i)并記錄當前最優解，其返回值為鳥巢位置x_i在組合覆蓋集S中所能覆蓋的取值組合的數目；

(7.3)更新當前最優鳥巢位置gBest，第i個鳥巢在第t次迭代的位置為在第t+1代時，布谷鳥的路徑和位置更新公式為：

其中，α為步長縮放因子，為點乘運算，為位置的變化量，L(λ)為Lévy隨機搜索路徑，L(λ)的更新公式為：

L～u＝t^-λ(1λ≤3)

宿主鳥以一定概率Pa發現外來鳥后重建巢的位置路徑，新建的鳥巢的位置公式為：

其中，r，∈是服從均勻分布的隨機數，Heaviside(x)是跳躍函數(x0,＝1；x0,＝0)，是其他任意兩個鳥巢位置；

(7.4)重復步驟(7.2)-(7.3)，直到達到預設的最大迭代次數，返回最優鳥巢位置gBest。

3.根據權利要求1所述的基于CS-SPSO算法的組合測試用例生成方法，其特征在于所述的步驟(8)具體為：

(8.1)更新組合測試用例集TS(t+1)＝TS(t)∪{gBest}；

(8.2)計算最優鳥巢位置 gBest所包含的組合s，剔除已覆蓋的組合，得到新的組合覆蓋集S(t+1)＝S(t)-s；

(8.3)從兩兩組合集S′中剔除兩兩組合s′，得到新的兩兩組合集S′(t+1)＝S′(t)-s′。