許媛媛

摘要：為了從已有的測試用例中提取經(jīng)驗(yàn)知識、縮短測試用例設(shè)計(jì)時(shí)間，本文提出基于CBR（案例推理）的測試用例復(fù)用方法。首先對測試用例復(fù)用過程進(jìn)行分析，指出測試用例檢索是測試用例復(fù)用過程的關(guān)鍵。

在測試用例檢索中采用K近鄰法，并對K近鄰法進(jìn)行改進(jìn)，同時(shí)在改進(jìn)的算法中使用帶權(quán)重的距離度量算法。在此基礎(chǔ)上提出遺傳模擬退火算法，該算法可對測試用例屬性的權(quán)重進(jìn)行優(yōu)化，是遺傳算法和模擬退火算法的結(jié)合，可以有效避免遺傳算法的早熟問題，增強(qiáng)算法的全局尋優(yōu)能力，縮短搜索時(shí)間。通過實(shí)驗(yàn)可以證明，該算法比標(biāo)準(zhǔn)的遺傳算法和模擬退火算法具有更高的求解質(zhì)量和求解效率。

關(guān)鍵詞：測試用例復(fù)用；遺傳模擬退火算法；案例推理；測試用例檢索；屬性權(quán)重。

中圖分類號：TP301.6

文獻(xiàn)標(biāo)識碼：A

DOI：10.3969/j.issn.1003-6970.2015.09.030

0 引言

隨著軟件廣泛應(yīng)用于各個(gè)領(lǐng)域，軟件的質(zhì)量問題逐漸得到人們的關(guān)注。軟件測試是軟件質(zhì)量保證的重要手段，測試用例的設(shè)計(jì)占整個(gè)測試過程的60%，通過對測試用例的復(fù)用可以縮短測試設(shè)計(jì)時(shí)間，提高測試效率。

CBR是人工智能領(lǐng)域的一個(gè)重要推理技術(shù)，最早由耶魯大學(xué)的Roger Schank教授與其合作者提出，旨在利用已有的案例解決新的問題。將CBR技術(shù)應(yīng)用于測試用例復(fù)用，主要過程包括檢索、復(fù)用、修正、保存。CBR模型的核心是案例檢索，它直接決定了CBR整個(gè)過程的速度和精度，在目前的案例檢索算法中，K近鄰法由于簡單直觀而被普通采用，但也存在著兩個(gè)問題，一是隨著案例數(shù)目變多檢索時(shí)間會線性增長，二是在距離度量算法中沒有考慮特征權(quán)重。

對K近鄰法進(jìn)行改進(jìn)，采用帶權(quán)重的距離度量算法，提出遺傳模擬退火算法并將其用于優(yōu)化屬性權(quán)重。該算法是兩種算法的結(jié)合。遺傳算法搜索速度快，強(qiáng)調(diào)的是兩代之間的進(jìn)化關(guān)系，具有較好的兼容性，容易與其他算法結(jié)合，缺點(diǎn)是其交配有可能使最優(yōu)解遺失，陷入局部最優(yōu)解。而模擬退火算法以某一接受概率采納一個(gè)較差的解，因而可能會跳出局部最優(yōu)解，是一個(gè)全局最優(yōu)算法。遺傳模擬退火算法結(jié)合了兩種算法的優(yōu)點(diǎn)，通過實(shí)驗(yàn)可以證明，該算法比標(biāo)準(zhǔn)的遺傳算法和模擬退火算法具有更高的求解質(zhì)量和求解效率。

1 基于CBR的測試用例復(fù)用技術(shù)

基于CBR的測試用例復(fù)用過程是一個(gè)循環(huán)過程，遵循4R模型，檢索、復(fù)用、修正、保存，主要過程如圖所示。

1.1 用例表示

建立用例庫是復(fù)用過程的前提。測試用例包含名稱、標(biāo)識、說明、設(shè)計(jì)方法、前提和約束、測試輸入、測試步驟、預(yù)期結(jié)果等要素，主要用于驗(yàn)證軟件功能、性能、接口、人機(jī)交互界面、安裝、卸載、文檔等是否存在問題。

定義l測試用例可以表示為TC=。

用例名稱（Test Case Name，TCN）：描述測試用例的名稱；

用例標(biāo)識（Test Case ID，TCI）：用于唯一標(biāo)識測試用例；

用例說明（Test Case Description，TCD）：簡要說明測試驗(yàn)證的功能點(diǎn)及測試方法；

設(shè)計(jì)方法（Design Technique，DT）：說明采用的設(shè)計(jì)方法；

前提和約束（Precondition and Restriction，PR）：說明執(zhí)行的測試步驟所必須的前提條件；

測試輸入（Test Case Input，TCIN）：在執(zhí)行過程中需要輸入的具體內(nèi)容，按照設(shè)計(jì)方法設(shè)計(jì)輸入有效值、無效值、邊界值等；

測試步驟（Test Case Process，TCP）：把操作過程分成相對獨(dú)立的測試步驟；

預(yù)期結(jié)果（Excepted Result，ER）：執(zhí)行測試步驟產(chǎn)生對應(yīng)的預(yù)期結(jié)果；

1.2 基于K近鄰的測試用例檢索算法

案例的檢索是CBR的核心，最常用的檢索算法為K近鄰法。K近鄰法是一種基本的分類與回歸方法，算法簡單直觀。對新的輸入實(shí)例，在訓(xùn)練數(shù)據(jù)集中查找并計(jì)算與每個(gè)實(shí)例的距離，返回與該實(shí)例最近的K個(gè)實(shí)例，判斷這些實(shí)例的類別，該輸入實(shí)例屬于類別最多的那個(gè)類。

基于K近鄰的測試用例檢索算法則是將測試用例的屬性看作多維空間中的維，測試用例看作多維空間中的點(diǎn)，特征空間中兩個(gè)點(diǎn)的距離是兩個(gè)點(diǎn)相似度的反映，計(jì)算目標(biāo)用例和測試用例庫中已有用例的距離，返回距離最小的K個(gè)用例。

1.2.2 屬性權(quán)重

用例中各個(gè)屬性的重要性由屬性的權(quán)重來表示，屬性權(quán)重對檢索的質(zhì)量和速度都起到了重要作用。用例屬性權(quán)重的確定方法主要有主觀賦權(quán)法和客觀賦權(quán)法。主觀賦權(quán)法主要是專家根據(jù)主觀經(jīng)驗(yàn)來確定屬性權(quán)重，如Delphi法、層次分析法等，研究較為成熟，但客觀性較差。而客觀賦權(quán)法是根據(jù)實(shí)際數(shù)據(jù)由數(shù)學(xué)規(guī)則來確定屬性權(quán)重，如熵值法、均方差權(quán)重法、Critic法、最小二乘法、神經(jīng)網(wǎng)絡(luò)方法、遺傳算法等，此類方法不依賴人的主觀判斷，因而客觀性較強(qiáng)。為提高相似案例的檢索能力，本文使用遺傳模擬退火算法來優(yōu)化屬性權(quán)重。

2 基于遺傳模擬退火算法的屬性權(quán)重優(yōu)化

2.1 遺傳模擬退火算法

本文提出的遺傳模擬退火算法通過引入模擬退火原理克服了遺傳算法的早熟問題，同時(shí)提高了檢索效率。

遺傳算法是一種全局搜索算法，適合求解大規(guī)模的全局優(yōu)化問題。借用了生物進(jìn)化論中“適者生存”的規(guī)律，模擬生物遺傳和進(jìn)化過程中選擇、交配、變異機(jī)制。缺點(diǎn)是可能陷入局部最優(yōu)解，原因是在搜索過程中，根據(jù)優(yōu)勝劣汰思想，種群優(yōu)良個(gè)體增加而逐漸使其失去多樣性，且變異概率較低，不足以跳出局部最優(yōu)解，從而造成程序?qū)ふ也坏饺肿顑?yōu)解。

模擬退火算法源于對固體退火過程的模擬，以一定概率選擇鄰域中費(fèi)用值大的狀態(tài)。模擬退火的這種特性可以克服遺傳算法可能陷入局部最優(yōu)解的缺點(diǎn)。

遺傳算法結(jié)合了這兩種算法的特點(diǎn)，增強(qiáng)了搜索能力和效率。主要過程如下：

2.2 基于遺傳模擬退火算法的屬性權(quán)重優(yōu)化

用例之間的相似度度量是用例檢索的關(guān)鍵，而用例屬性權(quán)重對用例的相似度度量起到了至關(guān)重要的作用。在改進(jìn)的CBR檢索算法中使用了帶權(quán)重的距離度量算法，給用例的每個(gè)屬性賦予一定的權(quán)重，通過遺傳模擬退火算法優(yōu)化屬性權(quán)重。

遺傳模擬退火算法首先隨機(jī)產(chǎn)生一組初始解，通過選擇、交配、變異的遺傳操作開始尋求全局最優(yōu)解，然后再對遺傳操作所產(chǎn)生的個(gè)體進(jìn)行模擬退火，并將模擬退火產(chǎn)生的結(jié)果作為下一代群體的初始解。循環(huán)此過程，直到滿足終止規(guī)則，得到最終群體。

2.3 實(shí)驗(yàn)結(jié)果

利用測試用例作為實(shí)驗(yàn)數(shù)據(jù)，選擇屬性用例名稱、用例說明、設(shè)計(jì)方法、前提和約束、測試輸入、測試步驟、預(yù)期結(jié)果作為觀測屬性，測試用例的相似度作為決策屬性。

通過遺傳算法來確定這7個(gè)觀測屬性的權(quán)重，其中每個(gè)屬性的權(quán)重代表了該屬性對測試用例相似度的決定能力，結(jié)果如表1所示。

實(shí)驗(yàn)結(jié)果中，遺傳模擬退火算法的分類精度最高，表明該算法比標(biāo)準(zhǔn)的遺傳算法和模擬退火算法具有更高的求解質(zhì)量。

3 結(jié)論

本文給出了基于CBR的測試用例復(fù)用方法，對檢索算法K近鄰法進(jìn)行了改進(jìn)，使用帶權(quán)重的距離度量算法更能突出屬性對測試用例相似度的不同影響。并給出了基于遺傳模擬退火算法的屬性權(quán)重優(yōu)化，遺傳模擬退火算法主要以遺傳算法為主體，引入模擬退火的集中擴(kuò)散機(jī)制和加速適應(yīng)函數(shù)，該算法具有遺傳算法的優(yōu)勝劣汰思想，同時(shí)通過融入模擬退火算法思想克服了遺傳算法的早熟問題，縮短了搜索時(shí)間。理論分析和實(shí)驗(yàn)結(jié)果均表明遺傳模擬退火算法在求解質(zhì)量和效率上優(yōu)于標(biāo)準(zhǔn)的遺傳算法和模擬退火算法。