基于模擬退火遺傳算法的軟件測試用例研究

張紅敏 周鳳

引言：本文在探討模擬退火遺傳算法的基礎上，結合軟件測試的基本過程，提出在軟件測試中用模擬退火遺傳算法尋求最佳測試用例，以便提高軟件測試效率，并給出一般性的原理和算法。

一、遺傳算法

遺傳算法（Genetic Algorithm）是最初由美國Michigan大學J.Holland教授于1975年首先提出來的，是模擬達爾文生物進化論的自然選擇和遺傳學機理的生物進化過程的計算模型，是一種通過模擬自然進化過程搜索最優解的方法。遺傳算法包含5個要素：初始化種群，選擇，交叉，變異，更新初始群體，結束條件。

模擬退火算法是根據固體退火原理，將固體加熱到充分高的溫度，再讓其徐徐冷卻，加溫時，固體內部的粒子隨著溫度上升變為無序狀，內能增大，而徐徐冷卻時粒子漸趨有序，在每個溫度都達到到平衡態，最后在常溫時達到基態，內能減為最小【1】。

由于遺傳算法具有良好的全局搜索能力，但是對于局部空間搜索卻不是很有效，容易產生早熟收斂現象，陷入局部最優【2】。為了解決這個問題，可以將模擬退火算法結合到遺傳算法中，模擬退火算法的局部搜索能力可以解決遺傳算法局部搜索能力差以及早熟現象，同時也解決了模擬退火算法全局搜索能力差和效率不高的問題。

二、軟件測試

軟件測試是運行程序并發現程序錯誤的過程。測試是為了發現程序中的錯誤，而不是證明程序中沒有錯誤。而測試用例應該包括為測試某個程序路徑或者確定是否滿足某個特定需求而編制的一組測試輸入、執行條件和與之對應的預期結果。一個好的測試用例是能夠快速有效的發現程序中的錯誤。一般把測試分為兩類：白盒測試也稱為結構測試、透明盒測試、邏輯驅動測試或基于代碼的測試，是按照程序內部的結構測試程序，通過測試來檢測產品內部動作是否按照設計規格說明書的規定正常進行，檢驗程序中的每條通路是否都能按預定要求正確工作；黑盒測試也稱為功能測試或數據驅動測試，是通過測試來確認每個功能是否得到完整實現，檢測每個功能是否都能正常使用。而黑盒測試的測試用例設計通常是用等價劃分法。

用等價類劃分法首先要劃分等價類：輸入規定了的取值范圍或值的個數就可以確定一個有效等價類和兩個無效等價類。輸入規定了的輸入值的集合或者一個布爾量可以確定一個有效等價類和一個無效等價類。輸入規定的輸入數據的一組值（假設m個）且對每一個輸入值分別處理可以確定m個有效等價類和一個無效等價類。輸入的數據必須遵守一定的規則可以確定一個有效等價類和若干個無效等價類。已劃分的等價類中各元素處理方式不同時應將等價類再劃分為更小的等價類。其次確定測試用例：給等價類編號設計一個重復使其盡可能多地覆蓋尚未被覆蓋過的合理等價類直到所有合理等價類被測試用例覆蓋的測試用例。設計一個使其只覆蓋一個不合理等價類的測試用例。

三、用模擬退火遺傳算法需求最佳測試用例

（1）編碼。模擬退火遺傳算法需要將軟件測試中的一個問題的可行解從解空間轉換到遺傳算法所能解決的搜索空間。初始化種群規模為100，編碼方法可以選擇浮點法、grey法則和二進制法，本文每個參數的編碼方式采用二進制編碼。

（2）選擇退火算子

在軟件測試中，測試的目的是發現程序中至今沒有發現的錯誤，一個好的測試用例就相當于遺傳算法中適應度值大的個體，本文將初始群體中的100個個體進行適應度評價，個體適應度值越大，該個體被遺傳到下一代的概率也越大。

①隨機選擇初始群體兩個個體A、B，計算其個體適應度值f（A）和f（B）。

②如果f（A）

③重復①、②操作直到新的一代群體中也包含100個個體。

（3）選擇。染色體的選擇方法可以采用錦標賽法和輪盤賭法，本文采用輪盤賭法，通常適應度大的被選擇的幾率較高。

（4）交叉。在遺傳算法的遺傳操作中，交叉運算決定了遺傳算法的全局搜索能力【3】。將父代中的任意兩個個體進行交叉產生最新染色體。進行退火操作，如果最佳適應度大于最新染色體適應度，就用最新染色體適應度取代之前的最佳適應度，否則以概率P（exp（（f（A）-f（B））/T））接受最新個體。重復操作，直至以概率0.7完成所有的交叉操作。

（5）變異。在遺傳算法的遺傳操作中，變異操作決定了遺傳算法的局部搜索能力【3】。變異方法的選擇浮點法和單點法。本文采用浮點法。隨機選擇一個的內部選擇兩個節點進行變異，如果新產生的個體適應度小于原個體適應度，就用最新個體取代原個體，否則以概率P（exp（（f（A）-f（B））/T））接受最新個體。重復此操作。直至以概率0.05完成所有的交叉操作。

（6）終止條件。當進化代數超過某個值而適應度不變時或者進化代數達到最大值時。最后留下的也即最優的軟件測試用例。

四、結束語

綜上所述，本文重在在軟件測試中使用模擬退火遺傳算法需找最好的軟件測試用例。以一種高效率的方式完成軟件中的黑盒測試，并找出最佳測試用例。

參考文獻

[1]季海婧.基于模擬退火—量子遺傳算法的路徑測試數據自動生成方法研究[D].浙江：杭州師范大學，2012.

[2]楊清平.基于改進遺傳算法的測試用例自動生成研究[D].廣東：廣東工業大學，311.

[3]李欣，基于貝葉斯網絡和遺傳算法的測試用例生成模型[D].重慶：重慶交通大學，2012.

（作者單位：貴州大學 計算機科學與技術學院）