[發明專利]一種基于貪婪算法和搜索算法的混合算法的組合測試用例生成算法

在審

• 申請號: 202010906633.4
• 申請日: 2020-09-01
• 公開（公告）號: CN111984542A
• 公開（公告）日: 2020-11-24
• 發明（設計）人: 勾善義
• 申請（專利權）人: 勾善義
• 主分類號: G06F11/36
• 分類號: G06F11/36
• 代理公司: 暫無信息
• 代理人: 暫無信息

1.一種基于貪婪算法和搜索算法的混合算法的組合測試用例生成算法，其主要步驟如下：

步驟1)、生成滿足要求的覆蓋數組。

步驟2)、首先選擇貪婪算法，如圖2，根據貪婪算法特性逐步覆蓋數組。

步驟3)、當覆蓋標準達到K后，貪婪算法遇到瓶頸，選擇搜索算法代替，如圖3，以期達到更優的效果。

進一步的，所述步驟1)的具體步驟如下：

步驟1.0)、首先是構建數組，構建覆蓋數組的總體目標是創建一個二維數組，其中所有與指定輸入關聯的t元組都會被覆蓋。

步驟1.1)、組合測試使用覆蓋表CA作為測試用例集，CA是一個大小為M×k維的矩陣。本發明中，測試用例條數，即覆蓋表的大小標記為N；覆蓋強度標記為t；待測系統參數個數為其中，取值個數為v_i的參數有k_i(1≤i≤m，m≤k)個，v_i(1≤i≤k)表示第i個參數取值集合，|v_i|表示第i個參數取值個數。則CA表有如下表示：

進一步的，所述步驟2)的具體步驟如下：

步驟2.1)、通過使用貪婪算法，將每個因子與某個級別的值綁定在一起，可以為該集合一次建立一行。一旦所有t元組都被覆蓋，覆蓋數組就完成了。本發明可以動態設置參數K，當覆蓋率達到K時，將貪婪算法轉換為搜索算法，避免陷入局部最優。

步驟2.2)、手動選擇第一個測試用例T，或者自動選擇T，T的選擇會影響后續測試用例的生成。

步驟2.3)、根據步驟2.2)選中的測試用例T，選擇測試用例T’，選擇標準是轉換成本最低，如果同時存在多個T’，則選擇其中一個。在此階段，覆蓋率逐漸上升。

進一步的，所述步驟3)的具體步驟如下：

步驟3.1)、用戶可以根據自己的實際需求，設置一個覆蓋標準值K。如果標準值K設置得過高，則有可能在貪婪算法陷入局部最優時仍未達到K，會影響性能。

步驟3.2)、當覆蓋率到達K時，本發明將選擇搜索算法繼續生成測試用例。

步驟3.4)、假定S為SUT應涵蓋的所有未覆蓋2值組合的集合，Tg為生成的測試用例的集合。對于每個測試候選t，t(2-way)表示t覆蓋的S中的所有2-way值組合。則有：

Fitness(t)＝|t(2-way)∩S|

其中Fitness用來衡量每個候選者的質量。以此來選擇候選者。因為這是搜索算法的一般方法，因此對于其他強度的組合也適用。

步驟3.5)、當步驟3.4)中S為空時，CA完全覆蓋，流程結束。