牛福強(qiáng)，張國(guó)富,2，蘇兆品,2，岳 峰

(1.合肥工業(yè)大學(xué) 計(jì)算機(jī)與信息學(xué)院，安徽 合肥 230601；2.合肥工業(yè)大學(xué) 工業(yè)安全與應(yīng)急技術(shù)安徽省重點(diǎn)實(shí)驗(yàn)室，安徽 合肥 230601)

0 引 言

獲得高質(zhì)量和滿足市場(chǎng)需求度的軟件是軟件測(cè)試最為重要的目標(biāo)，軟件測(cè)試?yán)孟臏y(cè)試資源檢測(cè)軟件故障，發(fā)現(xiàn)并修復(fù)軟件漏洞是獲取高可靠性軟件的必要途徑[1,2]。軟件測(cè)試消耗的資源接近軟件開(kāi)發(fā)總資源的一半[3]。隨著基于搜索的軟件工程的迅速發(fā)展[7]，一些演化計(jì)算技術(shù)被用來(lái)求解測(cè)試資源分配問(wèn)題[8,9]，如遺傳算法[10]、蟻群優(yōu)化[11]。

在現(xiàn)實(shí)環(huán)境當(dāng)中，軟件測(cè)試是動(dòng)態(tài)的、不確定的，同一個(gè)測(cè)試模塊在不同測(cè)試階段所展現(xiàn)出的特征也有差別。軟件系統(tǒng)中的模塊錯(cuò)誤數(shù)量在測(cè)試行為執(zhí)行前已經(jīng)被預(yù)估，其每個(gè)模塊相關(guān)參數(shù)和分配到的測(cè)試資源也不會(huì)隨著錯(cuò)誤的發(fā)現(xiàn)、前期測(cè)試階段獲得的經(jīng)驗(yàn)而進(jìn)行相應(yīng)的調(diào)整，這種靜態(tài)環(huán)境下的最優(yōu)化測(cè)試資源分配問(wèn)題在以往工作中[4-6]進(jìn)行了非常全面的研究。Zeephongsekul等[12]通過(guò)統(tǒng)計(jì)歷史階段的發(fā)現(xiàn)的錯(cuò)誤數(shù)量以及檢測(cè)出每個(gè)錯(cuò)誤的時(shí)間點(diǎn)對(duì)下一個(gè)階段的模塊參數(shù)利用極大似然估計(jì)進(jìn)行了重估。Chaudhary等[13]針對(duì)最大化檢測(cè)錯(cuò)誤數(shù)的優(yōu)化問(wèn)題提出了一種基于差分進(jìn)化算法的多階段測(cè)試資源分配算法(MS-DE)。陸陽(yáng)等[14]采取將測(cè)試資源劃分成多個(gè)階段分配給軟件系統(tǒng)，階段資源可以根據(jù)每個(gè)模塊的可靠性進(jìn)行相應(yīng)的調(diào)整，以便幫助解集更快收斂。但是模塊參數(shù)并沒(méi)有根據(jù)檢測(cè)出的錯(cuò)誤數(shù)進(jìn)行參數(shù)的重估，仍然屬于測(cè)試行為未發(fā)生的靜態(tài)環(huán)境下，所進(jìn)行的多階段測(cè)試資源的預(yù)分配，與實(shí)際中的測(cè)試存在較大的差異，不符合動(dòng)態(tài)測(cè)試資源分配中的動(dòng)態(tài)屬性。

本文結(jié)合了傳統(tǒng)研究中基于演化算法多個(gè)目標(biāo)同時(shí)優(yōu)化的特點(diǎn)以及動(dòng)態(tài)測(cè)試資源分配中的基于歷史信息動(dòng)態(tài)調(diào)整模塊參數(shù)以及每個(gè)測(cè)試階段的測(cè)試資源。測(cè)試人員可以根據(jù)實(shí)際的需求在每個(gè)測(cè)試階段獲得的目標(biāo)解集中選出偏好解，根據(jù)該偏好解執(zhí)行測(cè)試并收集相關(guān)的錯(cuò)誤信息，收集到的錯(cuò)誤信息將會(huì)用于之后的測(cè)試階段參數(shù)的估計(jì)，從而使下一階段優(yōu)化中獲得符合實(shí)際的解決方案。并且能夠基于實(shí)際情況將有限的測(cè)試資源分配需求度高的模塊，從而獲得滿足市場(chǎng)需求的高可靠性軟件系統(tǒng)。

1 問(wèn)題描述

圖1 總的可用測(cè)試時(shí)間多階段劃分

(1)

在每個(gè)測(cè)試階段執(zhí)行前，測(cè)試管理者都要從當(dāng)前階段算法給出最優(yōu)解集選取一個(gè)最符合當(dāng)前市場(chǎng)需求或者高可靠性的偏好解作為執(zhí)行方案。而該偏好解給出總消耗的測(cè)試時(shí)間必定小于或等于該測(cè)試階段可用的總測(cè)試時(shí)間，因此在第i階段可用的總測(cè)試時(shí)間與實(shí)際消耗的測(cè)試資源之間的關(guān)系滿足

(2)

(3)

可以求解上述一階微分方程，我們可以發(fā)現(xiàn)模塊j在階段i中平均檢測(cè)到的錯(cuò)誤數(shù)與消耗的測(cè)試時(shí)間呈指數(shù)關(guān)系，如下

(4)

在衡量軟件系統(tǒng)質(zhì)量的標(biāo)準(zhǔn)中，軟件內(nèi)平均每個(gè)模塊剩余錯(cuò)誤數(shù)量是軟件可靠性最為直接、有效的表述。每一個(gè)模塊在軟件系統(tǒng)中的相對(duì)重要程度隨著測(cè)試階段的不同而有所不同，可以根據(jù)需求進(jìn)行相應(yīng)的調(diào)整。軟件系統(tǒng)在第i個(gè)測(cè)試階段的剩余錯(cuò)誤總數(shù)為

(5)

綜上所述，為能夠獲得滿足市場(chǎng)需求的軟件系統(tǒng)，在每個(gè)階段給予可用消耗的測(cè)試時(shí)間以及軟件系統(tǒng)剩余的錯(cuò)誤總數(shù)雙重約束下，力求最小化軟件系統(tǒng)錯(cuò)誤總數(shù)以及最小化測(cè)試時(shí)間消耗，從而形成多階段、兩目標(biāo)、動(dòng)態(tài)求解測(cè)試時(shí)間分配優(yōu)化問(wèn)題模型

(6)

2 多階段NSGA-II動(dòng)態(tài)分配算法

2.1 NSGA-II

多目標(biāo)優(yōu)化算法NSGA-II[10]是最為經(jīng)典的演化算法之一，該優(yōu)化算法的性能已經(jīng)在以往的研究以及工程實(shí)踐中得到廣泛的認(rèn)可。NSGA-II能夠簡(jiǎn)單有效選取全局最優(yōu)解，并且在同時(shí)優(yōu)化兩個(gè)目標(biāo)問(wèn)題模型中具有較大的優(yōu)勢(shì)。經(jīng)過(guò)研究人員不斷研究，NSGA-II的性能也變得更加完善，但該算法的整體框架和基本思想沒(méi)有改變。多目標(biāo)算法NSGA-II針對(duì)兩個(gè)目標(biāo)雙重約束問(wèn)題基本框架為：在測(cè)試時(shí)間限制范圍內(nèi)生成規(guī)模為N的初始種群，即含一個(gè)有N個(gè)解的解集，該N個(gè)解是隨機(jī)生成、廣泛分布的，對(duì)初始種群進(jìn)行非支配排序，非支配排序的原則是在兩個(gè)目標(biāo)能夠支配其它解排在上層，稱之為非支配解；在目標(biāo)中各有優(yōu)劣，將會(huì)排序分布在同一層。然后在非支配排序后種群中利用二進(jìn)制錦標(biāo)賽選擇兩個(gè)父代個(gè)體，進(jìn)行二進(jìn)制交叉以及多項(xiàng)式變異的遺傳操作，從而產(chǎn)生兩個(gè)子代個(gè)體。將父代與子代個(gè)體進(jìn)行合并，種群大小為2N，對(duì)合并后的種群進(jìn)行非支配排序，非支配排序過(guò)程中，不只通過(guò)兩個(gè)目標(biāo)的最優(yōu)程度進(jìn)行判斷，還需要加入個(gè)體違背約束的程度，一個(gè)個(gè)體違背約束的程度越高，得到的排序位置越靠近下層，淘汰的幾率也就越高。然后根據(jù)非支配排序的位置選取N個(gè)子代種群，不同層的選擇上層，較優(yōu)的非支配解將容易保存下來(lái)；同層之間計(jì)算擁擠距離，保留擁擠距離相對(duì)較大的，從而保證子代種群的多樣性。通過(guò)非支配關(guān)系以及擁擠距離保持子代的精英性以及多樣性。子代總是能夠支配父代，重復(fù)上述步驟，不斷趨近Pareto前沿[14]，直到滿足算法終止條件。具體流程如圖2所示。二進(jìn)制錦標(biāo)賽選擇、模擬二進(jìn)制交叉和多項(xiàng)式變異3個(gè)基本操作的具體細(xì)節(jié)請(qǐng)參照文獻(xiàn)[16]，這里不再贅述。

圖2 NSGA-II算法流程

2.2 參數(shù)估計(jì)

(7)

(8)

利用上述的對(duì)數(shù)似然函數(shù)可以得到如下的微分方程組

(9)

2.3 種群重新初始化

2.4 約束處理

根據(jù)上一節(jié)編碼方式和種群初始化，我們不難發(fā)現(xiàn)即使個(gè)體中的每個(gè)元素符合約束條件，個(gè)體有可能不符合約束式(6)中約束條件。除此之外，根據(jù)演化算法的迭代進(jìn)化過(guò)程中，遺傳操作包括交叉操作、變異操作都有可能導(dǎo)致個(gè)體中的元素以及個(gè)體違背上述的約束條件。盡管演化算法能夠淘汰不符合約束的個(gè)體，大量的違規(guī)個(gè)體通過(guò)遺傳操作將會(huì)大概率產(chǎn)生的違規(guī)的子代，不利于種群的進(jìn)化，減慢種群的收斂速度。因此我們需要對(duì)個(gè)體中的元素以及個(gè)體進(jìn)行測(cè)試時(shí)間上的約束，幫助算法快速收斂。本文對(duì)種群初始化以及交叉、變異操作后，對(duì)種群中的每個(gè)個(gè)體以及個(gè)體元素進(jìn)行密切監(jiān)控，若存在違背約束條件則對(duì)編碼進(jìn)行修正，具體修正思路如下：

上述約束處理能夠減少違規(guī)解的參與遺傳進(jìn)化當(dāng)中，有利于加快種群進(jìn)化的收斂速度；另外這種約束處理添加了隨機(jī)性能夠保證個(gè)體的合法性，又能夠保持種群的多樣性。

2.5 算法描述

綜上所述，我們將參數(shù)估計(jì)、種群初始化以及約束處理與傳統(tǒng)的NSGA-II相結(jié)合產(chǎn)生多階段兩個(gè)目標(biāo)動(dòng)態(tài)測(cè)試時(shí)間分配算法(MS-NSGA-II)，該算法的整體思想是，能夠解決同時(shí)優(yōu)化兩個(gè)目標(biāo)、雙重約束下的測(cè)試時(shí)間分配問(wèn)題。測(cè)試管理者可以根據(jù)偏好選取符合實(shí)際的解，根據(jù)偏好解動(dòng)態(tài)調(diào)整后續(xù)測(cè)試階段的可用測(cè)試時(shí)間。

圖3 MS-NSGA-II多目標(biāo)動(dòng)態(tài)測(cè)試時(shí)間分配算法流程

3 實(shí)驗(yàn)結(jié)果與分析

3.1 實(shí)驗(yàn)參數(shù)和評(píng)價(jià)指標(biāo)

在進(jìn)行實(shí)驗(yàn)驗(yàn)證之前，我們需要配置相應(yīng)的軟件系統(tǒng)模塊參數(shù)以及算法相關(guān)參數(shù)。

表1 模塊的初始參數(shù)

在本文中我們結(jié)合了兩個(gè)目標(biāo)模型和多階段的特性，為了說(shuō)明所提出的MS-NSGA-II的優(yōu)點(diǎn)，將采用動(dòng)態(tài)單目標(biāo)MS-DE[13]和靜態(tài)多目標(biāo)NSGA-II與其對(duì)比，3種算法所用到的參數(shù)見(jiàn)表2。

表2 算法的基本參數(shù)

另外，我們需要對(duì)算法的結(jié)果進(jìn)行處理和評(píng)估，以便比較算法之間的優(yōu)劣。評(píng)價(jià)多目標(biāo)優(yōu)化結(jié)果的兩種經(jīng)典標(biāo)準(zhǔn)容量值(capacity)和滿足客戶解的標(biāo)準(zhǔn)覆蓋指標(biāo)[10](standard cover metric)。容量值是表示算法解集中滿足一定標(biāo)準(zhǔn)的解的數(shù)量，數(shù)量越多算法性能越好；覆蓋指標(biāo)是解集A中的解覆蓋解集B中所有解的百分比，百分比大的算法性能優(yōu)良。

3.2 與動(dòng)態(tài)單目標(biāo)的對(duì)比

在該部分實(shí)驗(yàn)當(dāng)中，我們比較MS-NSGA-II以及MS-DE兩種算法。首先針對(duì)30(n=30)個(gè)模塊的軟件系統(tǒng)進(jìn)行實(shí)驗(yàn)，另外還需要將總的測(cè)試時(shí)間分為3個(gè)測(cè)試階段(p=3)：[0,70 000]、[70 000,130 000]、[130 000,200 000]。MS-DE為單目標(biāo)優(yōu)化，因此只針對(duì)式(6)中的Si優(yōu)化。每個(gè)階段檢測(cè)出的錯(cuò)誤數(shù)根據(jù)式(4)的值附近隨機(jī)給出，兩種算法保持一致。每個(gè)階段的偏好解設(shè)置剩余錯(cuò)誤數(shù)最少的(MS-DE只能獲取該類型的解)。將所獲得的最終解集進(jìn)行畫圖，如圖4所示。由圖可以看出，MS-DE優(yōu)化后獲得一個(gè)單解，而MS-NSGA-II每個(gè)測(cè)試階段都會(huì)獲得一個(gè)解集，最終解集中有相當(dāng)一部分解的系統(tǒng)剩余錯(cuò)誤數(shù)少于MS-DE的單解。因此我們可以得出MS-NSGA-II能夠提供多個(gè)候選解的同時(shí)，系統(tǒng)剩余錯(cuò)誤數(shù)量最少的解優(yōu)于MS-DE的單解。

圖4 MS-DE和MS-NSGA-II得到的解集

為了更加凸顯出MS-NSGA-II的優(yōu)點(diǎn)，我們以MS-DE的單解作為偏好解，在MS-NSGA-II的解集中挑選出好于該偏好解(Si目標(biāo)值小于等于4.457 99)統(tǒng)計(jì)數(shù)量，并且將剩余錯(cuò)誤數(shù)最小的列見(jiàn)表3。由表3中數(shù)據(jù)可以得到無(wú)論從解的質(zhì)量以及數(shù)量，MS-NSGA-II的解集都要優(yōu)于MS-DE的單解，因此MS-NSGA-II的算法性能要好于MS-DE。

表3 系統(tǒng)剩余錯(cuò)誤數(shù)苛刻閾值下的解

3.3 與靜態(tài)多目標(biāo)的對(duì)比

同樣我們針對(duì)30個(gè)模塊系統(tǒng)進(jìn)行測(cè)試時(shí)間分配，NSGA-II和MS-NSGA-II兩個(gè)算法的之間的性能。由于NSGA-II為靜態(tài)環(huán)境下的測(cè)試時(shí)間分配，所以只有一個(gè)測(cè)試階段；在此部分為了說(shuō)明多階段的優(yōu)點(diǎn)我們將MS-NSGA-II的測(cè)試時(shí)間劃分成4種環(huán)境：2個(gè)、3個(gè)、4個(gè)和5個(gè)測(cè)試階段與NSGA-II進(jìn)行比較，每個(gè)測(cè)試環(huán)境各測(cè)試階段的測(cè)試資源劃分見(jiàn)表4。

表4 每個(gè)測(cè)試環(huán)境的階段數(shù)和測(cè)試時(shí)間劃分

針對(duì)兩種算法每個(gè)環(huán)境進(jìn)行30組的實(shí)驗(yàn)，選取其中一組實(shí)驗(yàn)畫圖，如圖5所示。由于兩個(gè)算法都獲得是解集，因此可以從圖中看出兩個(gè)解集匯成不同的曲線，該曲線能夠說(shuō)明測(cè)試時(shí)間和剩余錯(cuò)誤數(shù)之間的關(guān)系。另外4種環(huán)境下MS-NSGA-II的米子點(diǎn)解集處于NSGA-II點(diǎn)解集的下方，通過(guò)支配關(guān)系的比較，我們能夠得出MS-NSGA-II的解集要好于NSGA-II的解集。另外我們看出測(cè)試階段數(shù)越多解集的質(zhì)量并不一定好，在環(huán)境3、4中的解集質(zhì)量不如環(huán)境1、2中的解集質(zhì)量。MS-NSGA-II解集好于NSGA-II原因在于多階段的參數(shù)估計(jì)形成正反饋，可以將有限的測(cè)試時(shí)間分配給更需要的模塊，因此表明MS-NSGA-II的性能優(yōu)于NSGA-II。為了說(shuō)明算法能夠動(dòng)態(tài)調(diào)整各個(gè)測(cè)試階段的測(cè)試時(shí)間，充分的利用測(cè)試時(shí)間，我們?cè)诃h(huán)境4中(p=5時(shí))選取兩個(gè)模塊，將測(cè)試階段和每個(gè)階段分配到的測(cè)試時(shí)間畫圖，如圖6所示。從圖中我們可以得到，模塊1在前面階段分配到的測(cè)試資源較多，也就是可靠性達(dá)到一定時(shí)，算法將不會(huì)再把測(cè)試時(shí)間分配給該模塊。模塊2在前面測(cè)試階段分配到的資源較少，可靠性較低，算法通過(guò)調(diào)整在后期測(cè)試階段分配給該模塊的資源增多。因此MS-NSGA-II算法具有動(dòng)態(tài)調(diào)整資源的功能。

圖5 NSGA-II和MS-NSGA-II得到的解集

圖6 每個(gè)階段分配的測(cè)試時(shí)間

另外，以上比較了兩種算法整個(gè)解集的比較，我們還需要采用更為嚴(yán)格的標(biāo)準(zhǔn)比較兩種算法的性能，即設(shè)置更為嚴(yán)格的閾值解Si≤6.6下的兩種算法容量值之間的比較，以及符合嚴(yán)格閾值解的覆蓋值比較。經(jīng)過(guò)30次實(shí)驗(yàn)結(jié)果進(jìn)行統(tǒng)計(jì)平均見(jiàn)表5，由表所得MS-NSGA-II得到的平均容量值要大于NSGA-II，盡管在測(cè)試環(huán)境4中，MS-NSGA-II略大于NSGA-II，說(shuō)明在相同的實(shí)驗(yàn)環(huán)境當(dāng)中，MS-NSGA-II多階段反饋能夠幫助解集快速收斂的特點(diǎn)，從而獲得的更多的滿意解。在30次實(shí)驗(yàn)中挑選出Si≤6.6的解完成覆蓋值的比較并進(jìn)行統(tǒng)計(jì)分析，我們給出了覆蓋值的均值和標(biāo)準(zhǔn)差, 并基于Wilcoxon Rank Sum檢驗(yàn)[17](0.05的顯著性水平)進(jìn)行顯著性分析，用黑體標(biāo)出差異顯著的最佳均值。如表6所示，在測(cè)試環(huán)境1、2、3中MS-NSGA-II覆蓋值要明顯優(yōu)于NSGA-II，說(shuō)明在前3個(gè)測(cè)試環(huán)境中，MS-NSGA-II能夠挖掘到了更好的測(cè)試時(shí)間分配方案。但是，在測(cè)試環(huán)境4中MS-NSGA-II并沒(méi)有表現(xiàn)出較大的優(yōu)勢(shì)。綜合圖5以及表5、表6中數(shù)據(jù)，容量值和覆蓋值都有所下降，因此得出測(cè)試階段數(shù)量增多并不能夠幫助獲得高質(zhì)量的解集。原因在于總的迭代次數(shù)是有限的，測(cè)試階段數(shù)增加，每個(gè)測(cè)試階段的迭代次數(shù)減少，各階段的解集并沒(méi)有達(dá)到算法收斂需求。

表5 NSGA-II和MS-NSGA-II的平均容量值

表6 NSGA-II和MS-NSGA-II的覆蓋值(均值±標(biāo)準(zhǔn)差)

4 結(jié)束語(yǔ)

軟件測(cè)試消耗大量的測(cè)試資源，本文將動(dòng)態(tài)優(yōu)化以及多目標(biāo)相結(jié)合，提出一種基于NSGA-II的多階段兩個(gè)目標(biāo)動(dòng)態(tài)測(cè)試資源分配算法。該算法兼具了動(dòng)態(tài)測(cè)試資源多階段正反饋的屬性以及多目標(biāo)同時(shí)優(yōu)化的優(yōu)點(diǎn)，其中參數(shù)估計(jì)、種群初始化以及約束處理能夠自適應(yīng)調(diào)整每個(gè)測(cè)試階段的測(cè)試資源幫助解集快速收斂。通過(guò)與動(dòng)態(tài)單目標(biāo)MS-DE和靜態(tài)多目標(biāo)NSGA-II的對(duì)比實(shí)驗(yàn)分析，MS-NSGA-II能夠提供更多更高質(zhì)量的測(cè)試資源分配方案。在未來(lái)的研究中，我們將致力于如何合理的劃分測(cè)試階段。