張紅敏 周鳳

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

一、遺傳算法

遺傳算法（Genetic Algorithm）是最初由美國(guó)Michigan大學(xué)J.Holland教授于1975年首先提出來(lái)的，是模擬達(dá)爾文生物進(jìn)化論的自然選擇和遺傳學(xué)機(jī)理的生物進(jìn)化過(guò)程的計(jì)算模型，是一種通過(guò)模擬自然進(jìn)化過(guò)程搜索最優(yōu)解的方法。遺傳算法包含5個(gè)要素：初始化種群，選擇，交叉，變異，更新初始群體，結(jié)束條件。

模擬退火算法是根據(jù)固體退火原理，將固體加熱到充分高的溫度，再讓其徐徐冷卻，加溫時(shí)，固體內(nèi)部的粒子隨著溫度上升變?yōu)闊o(wú)序狀，內(nèi)能增大，而徐徐冷卻時(shí)粒子漸趨有序，在每個(gè)溫度都達(dá)到到平衡態(tài)，最后在常溫時(shí)達(dá)到基態(tài)，內(nèi)能減為最小【1】。

由于遺傳算法具有良好的全局搜索能力，但是對(duì)于局部空間搜索卻不是很有效，容易產(chǎn)生早熟收斂現(xiàn)象，陷入局部最優(yōu)【2】。為了解決這個(gè)問(wèn)題，可以將模擬退火算法結(jié)合到遺傳算法中，模擬退火算法的局部搜索能力可以解決遺傳算法局部搜索能力差以及早熟現(xiàn)象，同時(shí)也解決了模擬退火算法全局搜索能力差和效率不高的問(wèn)題。

二、軟件測(cè)試

軟件測(cè)試是運(yùn)行程序并發(fā)現(xiàn)程序錯(cuò)誤的過(guò)程。測(cè)試是為了發(fā)現(xiàn)程序中的錯(cuò)誤，而不是證明程序中沒(méi)有錯(cuò)誤。而測(cè)試用例應(yīng)該包括為測(cè)試某個(gè)程序路徑或者確定是否滿(mǎn)足某個(gè)特定需求而編制的一組測(cè)試輸入、執(zhí)行條件和與之對(duì)應(yīng)的預(yù)期結(jié)果。一個(gè)好的測(cè)試用例是能夠快速有效的發(fā)現(xiàn)程序中的錯(cuò)誤。一般把測(cè)試分為兩類(lèi)：白盒測(cè)試也稱(chēng)為結(jié)構(gòu)測(cè)試、透明盒測(cè)試、邏輯驅(qū)動(dòng)測(cè)試或基于代碼的測(cè)試，是按照程序內(nèi)部的結(jié)構(gòu)測(cè)試程序，通過(guò)測(cè)試來(lái)檢測(cè)產(chǎn)品內(nèi)部動(dòng)作是否按照設(shè)計(jì)規(guī)格說(shuō)明書(shū)的規(guī)定正常進(jìn)行，檢驗(yàn)程序中的每條通路是否都能按預(yù)定要求正確工作；黑盒測(cè)試也稱(chēng)為功能測(cè)試或數(shù)據(jù)驅(qū)動(dòng)測(cè)試，是通過(guò)測(cè)試來(lái)確認(rèn)每個(gè)功能是否得到完整實(shí)現(xiàn)，檢測(cè)每個(gè)功能是否都能正常使用。而黑盒測(cè)試的測(cè)試用例設(shè)計(jì)通常是用等價(jià)劃分法。

用等價(jià)類(lèi)劃分法首先要?jiǎng)澐值葍r(jià)類(lèi)：輸入規(guī)定了的取值范圍或值的個(gè)數(shù)就可以確定一個(gè)有效等價(jià)類(lèi)和兩個(gè)無(wú)效等價(jià)類(lèi)。輸入規(guī)定了的輸入值的集合或者一個(gè)布爾量可以確定一個(gè)有效等價(jià)類(lèi)和一個(gè)無(wú)效等價(jià)類(lèi)。輸入規(guī)定的輸入數(shù)據(jù)的一組值（假設(shè)m個(gè)）且對(duì)每一個(gè)輸入值分別處理可以確定m個(gè)有效等價(jià)類(lèi)和一個(gè)無(wú)效等價(jià)類(lèi)。輸入的數(shù)據(jù)必須遵守一定的規(guī)則可以確定一個(gè)有效等價(jià)類(lèi)和若干個(gè)無(wú)效等價(jià)類(lèi)。已劃分的等價(jià)類(lèi)中各元素處理方式不同時(shí)應(yīng)將等價(jià)類(lèi)再劃分為更小的等價(jià)類(lèi)。其次確定測(cè)試用例：給等價(jià)類(lèi)編號(hào)設(shè)計(jì)一個(gè)重復(fù)使其盡可能多地覆蓋尚未被覆蓋過(guò)的合理等價(jià)類(lèi)直到所有合理等價(jià)類(lèi)被測(cè)試用例覆蓋的測(cè)試用例。設(shè)計(jì)一個(gè)使其只覆蓋一個(gè)不合理等價(jià)類(lèi)的測(cè)試用例。

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

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

（2）選擇退火算子

在軟件測(cè)試中，測(cè)試的目的是發(fā)現(xiàn)程序中至今沒(méi)有發(fā)現(xiàn)的錯(cuò)誤，一個(gè)好的測(cè)試用例就相當(dāng)于遺傳算法中適應(yīng)度值大的個(gè)體，本文將初始群體中的100個(gè)個(gè)體進(jìn)行適應(yīng)度評(píng)價(jià)，個(gè)體適應(yīng)度值越大，該個(gè)體被遺傳到下一代的概率也越大。

①隨機(jī)選擇初始群體兩個(gè)個(gè)體A、B，計(jì)算其個(gè)體適應(yīng)度值f（A）和f（B）。

②如果f（A）

③重復(fù)①、②操作直到新的一代群體中也包含100個(gè)個(gè)體。

（3）選擇。染色體的選擇方法可以采用錦標(biāo)賽法和輪盤(pán)賭法，本文采用輪盤(pán)賭法，通常適應(yīng)度大的被選擇的幾率較高。

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

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

（6）終止條件。當(dāng)進(jìn)化代數(shù)超過(guò)某個(gè)值而適應(yīng)度不變時(shí)或者進(jìn)化代數(shù)達(dá)到最大值時(shí)。最后留下的也即最優(yōu)的軟件測(cè)試用例。

四、結(jié)束語(yǔ)

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

參考文獻(xiàn)

[1]季海婧.基于模擬退火—量子遺傳算法的路徑測(cè)試數(shù)據(jù)自動(dòng)生成方法研究[D].浙江：杭州師范大學(xué)，2012.

[2]楊清平.基于改進(jìn)遺傳算法的測(cè)試用例自動(dòng)生成研究[D].廣東：廣東工業(yè)大學(xué)，311.

[3]李欣，基于貝葉斯網(wǎng)絡(luò)和遺傳算法的測(cè)試用例生成模型[D].重慶：重慶交通大學(xué)，2012.

（作者單位：貴州大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院）