基于軟件體系結(jié)構(gòu)和廣義差分進(jìn)化的測試資源動(dòng)態(tài)分配算法

邵志勝，張國富，蘇兆品，李 磊

（1.合肥工業(yè)大學(xué)計(jì)算機(jī)與信息學(xué)院，合肥 230601；2.大數(shù)據(jù)知識(shí)工程教育部重點(diǎn)實(shí)驗(yàn)室（合肥工業(yè)大學(xué)），合肥 230601；3.智能互聯(lián)系統(tǒng)安徽省實(shí)驗(yàn)室（合肥工業(yè)大學(xué)），合肥 230009；4.工業(yè)安全與應(yīng)急技術(shù)安徽省重點(diǎn)實(shí)驗(yàn)室（合肥工業(yè)大學(xué)），合肥 230601）

（?通信作者電子郵箱1402369011@qq.com）

0 引言

軟件測試是軟件開發(fā)中的一個(gè)至關(guān)重要的環(huán)節(jié)，主要致力于發(fā)現(xiàn)和糾正軟件錯(cuò)誤，提升軟件系統(tǒng)的可靠性。眾所周知，軟件測試幾乎要耗費(fèi)軟件開發(fā)資源的一半，因此，如何合理分配測試資源，以耗費(fèi)盡可能少的測試資源，謀求盡可能高的軟件可靠性和盡可能少的測試成本，一直是軟件工程領(lǐng)域中的一個(gè)熱點(diǎn)和難點(diǎn)問題［1］。

傳統(tǒng)的方法大都局限于單目標(biāo)優(yōu)化，如在有限的測試時(shí)間內(nèi)追求可靠性最大或者測試成本最小，并采用動(dòng)態(tài)規(guī)劃或者拉格朗日乘子法等確定性方法進(jìn)行求解［2］。上述工作在面臨復(fù)雜軟件開發(fā)、軟件規(guī)模較大時(shí)往往很難在可接受的時(shí)間內(nèi)給出有效的解，因此，進(jìn)化計(jì)算技術(shù)被引入到軟件工程中，以期提升復(fù)雜軟件工程問題的求解效率［3］。

近年來，隨著基于搜索的軟件工程［4］的快速發(fā)展，多目標(biāo)測試資源分配（Multi-Objective Testing Resource Allocation，MOTRA）［5］受到越來越多的關(guān)注，一些多目標(biāo)進(jìn)化算法（Multi-Objective Evolutionary Algorithm，MOEA）［6］被用來求解MOTRA 問題，試圖在測試時(shí)間消耗、軟件可靠性和測試成本之間尋求一個(gè)合理的平衡。與傳統(tǒng)的動(dòng)態(tài)規(guī)劃、拉格朗日乘子法等確定性方法相比，MOEA 對(duì)Pareto 前沿的形狀或連續(xù)性不太敏感，可以在一次運(yùn)行中輸出一組解并最終生成Pareto 最優(yōu)解集［6］。因此，MOEA 作為MOTRA 問題的多目標(biāo)優(yōu)化器已經(jīng)變得越來越流行［7-14］。這些MOEA 可以為軟件項(xiàng)目經(jīng)理提供許多額外的選擇，這些選擇顯示了軟件可靠性、測試成本和消耗的測試時(shí)間之間的不同權(quán)衡，因此可以促進(jìn)對(duì)軟件測試環(huán)節(jié)進(jìn)行更加合理的規(guī)劃。

需要指出的是，在現(xiàn)代軟件工程中，軟件系統(tǒng)通常是通過選擇合適的、現(xiàn)成可重用的構(gòu)件，然后用明晰的軟件體系結(jié)構(gòu)組裝這些構(gòu)件來進(jìn)行開發(fā)。這項(xiàng)技術(shù)由于能夠顯著降低軟件的開發(fā)成本和時(shí)間，已在實(shí)際的軟件行業(yè)得到了廣泛的應(yīng)用。然而，已有研究大都針對(duì)傳統(tǒng)的并串聯(lián)模塊軟件模型［5］，鮮有涉及體系結(jié)構(gòu)軟件模型［15-16］的MOTRA 問題。如Wang 等［7］、Zhang 等［10］、Su 等［11］和Pietrantuono 等［12］利用第二代非支配遺傳算法（NSGA-Ⅱ）［17］，陸陽等［9］引入非支配排序差分進(jìn)化算法，牛福強(qiáng)等［13］和占德志等［14］采用第三代廣義差分進(jìn)化算法（Generalized Differential Evolution 3，GDE3）［18］來求解并串聯(lián)模塊軟件模型的MOTRA。在并串聯(lián)模塊軟件模型中，通常采用可靠性框圖（一個(gè)系統(tǒng)由多個(gè)串行子系統(tǒng)組成，每個(gè)子系統(tǒng)中至少有一個(gè)并行模塊）來直觀地描述系統(tǒng)各構(gòu)件的可靠性連接方式。雖然這種傳統(tǒng)的模型非常簡單直接，并且在實(shí)際的軟件系統(tǒng)中也得到了廣泛的應(yīng)用，但是它并沒有充分考慮系統(tǒng)的體系結(jié)構(gòu)（依賴于實(shí)際應(yīng)用中的運(yùn)行剖面）這一重要的系統(tǒng)特性［8］。

相反，基于體系結(jié)構(gòu)的軟件模型能夠通過定量地識(shí)別軟件體系結(jié)構(gòu)中最關(guān)鍵的構(gòu)件來評(píng)估面向?qū)ο蠛突跇?gòu)件的軟件系統(tǒng)的可靠性，近年來越來越受到歡迎［15-16］。因此，研究體系結(jié)構(gòu)軟件模型的MOTRA 問題具有重要的現(xiàn)實(shí)意義。然而，時(shí)至今日僅有Yang 等［8］提出了一種歸一化加權(quán)求和多目標(biāo)差分進(jìn)化（Multi-Objective Differential Evolution based on Weighted Normalized Sum，WNS-MODE）算法。此外，上述工作簡單的假設(shè)軟件測試是一個(gè)靜態(tài)的過程。在實(shí)際的軟件測試中，軟件項(xiàng)目經(jīng)理通常會(huì)根據(jù)用戶需求和軟件測試結(jié)果動(dòng)態(tài)調(diào)整測試流程，即整個(gè)軟件測試環(huán)節(jié)往往被劃分成若干個(gè)測試階段［12-13］。在每個(gè)測試階段，軟件的可靠性以及發(fā)現(xiàn)的軟件錯(cuò)誤數(shù)可能因用戶需求或軟件測試結(jié)果而發(fā)生動(dòng)態(tài)變化，這時(shí)就需要根據(jù)變化后的測試環(huán)境動(dòng)態(tài)調(diào)整測試時(shí)間的分配，而上述靜態(tài)測試資源分配方法顯然難以適應(yīng)上述測試環(huán)境的動(dòng)態(tài)變化。

基于上述背景，本文面向體系結(jié)構(gòu)軟件模型，針對(duì)可靠性和發(fā)現(xiàn)的錯(cuò)誤數(shù)在不同測試階段動(dòng)態(tài)變化的測試環(huán)境，首先構(gòu)造了一種基于體系結(jié)構(gòu)的多階段多目標(biāo)測試資源分配模型，然后基于參數(shù)重估計(jì)、種群重新初始化、GDE3和歸一化加權(quán)求和設(shè)計(jì)了一種面向動(dòng)態(tài)可靠性和錯(cuò)誤數(shù)的多階段多目標(biāo)測試資源分配算法，最后通過仿真實(shí)驗(yàn)驗(yàn)證了所提方法的有效性。

1 問題描述

本節(jié)從文獻(xiàn)［8，15］中回顧體系結(jié)構(gòu)軟件模型的測試資源分配，并將其擴(kuò)展到本文的動(dòng)態(tài)測試問題。

首先，基于體系結(jié)構(gòu)的軟件模型如圖1 所示，整個(gè)軟件系統(tǒng)由n個(gè)構(gòu)件組成，構(gòu)件i和構(gòu)件j之間可能存在著一步轉(zhuǎn)移概率pij∈[0，1]，i，j∈{1，2，…，n}，表示構(gòu)件i運(yùn)行完后有pij的概率過渡到構(gòu)件j。對(duì)于每個(gè)構(gòu)件i，滿足，即從構(gòu)件i出去的所有一步轉(zhuǎn)移概率之和為1。

圖1 基于體系結(jié)構(gòu)的軟件模型Fig.1 Architecture-based software model

其次，體系結(jié)構(gòu)軟件模型看成是一個(gè)吸收馬爾可夫鏈（其中pij=1 的狀態(tài)稱為吸收狀態(tài)），其轉(zhuǎn)移矩陣為P=[ ]pijn×n，顯然，P中的每一行之和均為1。假設(shè)圖1 中共有l(wèi)個(gè)吸收狀態(tài)和n-l個(gè)非吸收狀態(tài)，則可把轉(zhuǎn)移矩陣劃分［8，14］為：

其中：0 是一個(gè)l×(n-l)的零矩陣（所有元素均為0）；I是一個(gè)l×l的單位矩陣（對(duì)角線上的元素均為1，其余元素均為0）；B是一個(gè)(n-l)×l的非零矩陣；Q是一個(gè)(n-l)×(n-l)的亞隨機(jī)矩陣（每一行的元素之和不超過1）。

根據(jù)吸收馬爾可夫鏈的性質(zhì)，矩陣I-Q有可逆矩陣M：

M中的每個(gè)元素為從一個(gè)非吸收狀態(tài)到另一非吸收狀態(tài)的預(yù)期訪問次數(shù)，記

為從初始狀態(tài)0到非吸收狀態(tài)i的預(yù)期訪問次數(shù)［8，14］。

和慣例［8，15］一樣，考慮測試時(shí)間作為主要的測試資源。系統(tǒng)總的可用測試時(shí)間為T?，可由參與測試的軟件工程師人數(shù)乘以每個(gè)工程師的工作時(shí)間而計(jì)算得到。假設(shè)整個(gè)軟件測試環(huán)節(jié)被分成了s個(gè)測試階段，每個(gè)測試階段的預(yù)期可用測試時(shí)間為，k∈{1，2，…，s}，滿足

則第k個(gè)測試階段實(shí)際可用測試時(shí)間為：

根據(jù)上述知識(shí)，使用經(jīng)典的可靠性增長模型來評(píng)估構(gòu)件軟件系統(tǒng)的可靠性。在可靠性增長模型中，系統(tǒng)的可靠性滿足非齊次泊松過程［8］：

其中，τ為軟件系統(tǒng)的有效工作時(shí)間，通常為給定的常數(shù)；μ0，i為構(gòu)件i的預(yù)期訪問次數(shù)，可由式（1）、（2）得到。此外，λ(?)為構(gòu)件i的錯(cuò)誤強(qiáng)度函數(shù)，通常由錯(cuò)誤均值函數(shù)［15］：

求偏導(dǎo)得到，即

軟件測試帶來的成本非常復(fù)雜，包含各種因素，考慮風(fēng)險(xiǎn)成本的系統(tǒng)成本模型［8］為：

其中：c0為軟件測試準(zhǔn)備成本；c4為軟件失效產(chǎn)生的成本；為構(gòu)件i的測試階段糾正軟件錯(cuò)誤的成本；為構(gòu)件i運(yùn)行階段糾正軟件錯(cuò)誤的成本；為構(gòu)件i的一般測試成本（大都指人力成本）；0 ＜σi＜1為構(gòu)件i的一般測試成本折扣率。

綜上所述，基于體系結(jié)構(gòu)軟件模型的動(dòng)態(tài)測試資源分配問題可描述為如下的一個(gè)多階段三目標(biāo)優(yōu)化模型：

滿足如下約束：

其中：式（10）是為了最大化第k個(gè)測試階段的系統(tǒng)可靠性、最小化系統(tǒng)成本和測試時(shí)間消耗；式（11）為每個(gè)測試階段的可靠性下限；式（12）、（13）為每個(gè)測試階段的測試時(shí)間上限。

與文獻(xiàn)［8，14］不同的是，上述模型考慮了軟件的多階段動(dòng)態(tài)測試，而且還考慮了不同階段其可靠性約束和可用的測試時(shí)間可能會(huì)發(fā)生變化。

2 測試資源動(dòng)態(tài)分配算法設(shè)計(jì)

式（10）～（13）是一個(gè)典型的動(dòng)態(tài)多約束多目標(biāo)優(yōu)化問題，對(duì)求解器的性能要求較高。Yang等［8］已經(jīng)驗(yàn)證在求解構(gòu)件軟件的MOTRA 時(shí)，多目標(biāo)差分進(jìn)化算法比經(jīng)典的非支配遺傳算法［17］的搜索性能更好，因此，本文引入GDE3［18］來求解構(gòu)件軟件測試資源動(dòng)態(tài)分配問題，稱為DTRA-GDE3（Dynamic Testing Resource Allocation based on GDE3）算法。

為了更加清晰地說明本文所提出的DTRA-GDE3，下面將詳細(xì)介紹DTRA-GDE3 算法中的一些關(guān)鍵細(xì)節(jié)，并給出算法的整體框架和具體步驟。

2.1 基本GDE3算法

GDE3 算法［18］繼承了差分進(jìn)化算法的全局搜索能力，且引入了非支配遺傳算法［17］中的非支配排序、約束違背度和擁擠距離計(jì)算等算子，能夠更好地保證解的收斂性和多樣性。GDE3算法的基本步驟如下：

1）根據(jù)約束條件隨機(jī)生成種群規(guī)模為N的初始種群。

2）根據(jù)目標(biāo)函數(shù)和約束條件評(píng)估種群中每個(gè)個(gè)體的目標(biāo)函數(shù)值和約束違背程度。

3）對(duì)種群中的每個(gè)個(gè)體p∈{1，2，…，N}執(zhí)行如下操作：

a）從種群中隨機(jī)選擇三個(gè)與p互不相同的其他個(gè)體q1，q2，q3。

b）在個(gè)體所有的基因位中隨機(jī)選擇一位g?。

c）生成新個(gè)體q：對(duì)于個(gè)體中的每一個(gè)基因位g，在（0，1）之間生成一個(gè)隨機(jī)數(shù)r，執(zhí)行

其中：CR∈[0，1]為交叉概率，F(xiàn)∈[0，2]為縮放因子。

d）評(píng)估新個(gè)體q的目標(biāo)函數(shù)值和約束違背程度。

e）如果新個(gè)體q能夠支配當(dāng)前個(gè)體p，則將個(gè)體q放入新種群中；如果當(dāng)前個(gè)體p能夠支配新個(gè)體q，則將當(dāng)前個(gè)體p放入新種群中；如果新個(gè)體q和當(dāng)前個(gè)體p互不支配，則將這兩個(gè)個(gè)體同時(shí)放入新種群中。

4）如果新種群的規(guī)模超過了N，計(jì)算新種群中每個(gè)個(gè)體的擁擠距離，并對(duì)新種群進(jìn)行非支配排序，保留N個(gè)最好的個(gè)體。

5）如果沒有達(dá)到最大迭代次數(shù)Gmax，轉(zhuǎn)步驟3），否則結(jié)束算法，輸出新種群。

由上述流程可以看出，GDE3算法的時(shí)間主要耗費(fèi)在對(duì)新種群的非支配排序，其時(shí)間復(fù)雜度為O(MNlogN)［17］，其中M為優(yōu)化的目標(biāo)數(shù)，因此，GDE3 算法總的時(shí)間復(fù)雜度為O(GmaxMNlogN)。

2.2 構(gòu)件參數(shù)重估計(jì)

在動(dòng)態(tài)測試資源分配中，前一個(gè)階段k的測試結(jié)果顯然會(huì)影響當(dāng)前k+1測試階段的開展。對(duì)于構(gòu)件i，前一個(gè)階段k被糾正的錯(cuò)誤多，當(dāng)前k+1階段的剩余錯(cuò)誤數(shù)就會(huì)減少。此外，與文獻(xiàn)［13-14］不同的是，本文根據(jù)實(shí)際軟件測試環(huán)境，還考慮在前一個(gè)階段k可能會(huì)發(fā)現(xiàn)新的錯(cuò)誤（例如糾正軟件錯(cuò)誤帶來的新錯(cuò)誤等），這時(shí)當(dāng)前k+1 階段的剩余錯(cuò)誤數(shù)可能會(huì)增加，相應(yīng)地，錯(cuò)誤檢測率也會(huì)變化。因此，在優(yōu)化當(dāng)前k+1階段的測試資源分配時(shí)，需要利用極大似然估計(jì)［13-14］基于前一階段k在構(gòu)件i上消耗的測試時(shí)間、糾正的錯(cuò)誤數(shù)和發(fā)現(xiàn)的新錯(cuò)誤數(shù)，對(duì)當(dāng)前k+1階段構(gòu)件i的參數(shù)重新進(jìn)行估計(jì)：

2.3 種群重新初始化

由于在每個(gè)測試階段，可靠性約束（11）、測試時(shí)間約束（12）、（13）以及構(gòu)件參數(shù)均是動(dòng)態(tài)變化的，因此，在優(yōu)化每個(gè)測試階段的測試時(shí)間分配時(shí)，需要在種群進(jìn)化前依據(jù)新的約束空間對(duì)種群重新初始化，以盡可能地讓種群靠近當(dāng)前階段的可行解區(qū)域。此外，可以通過分析模型，把測試時(shí)間盡可能地分配給最需要的構(gòu)件，從而讓系統(tǒng)盡可能地滿足當(dāng)前階段的可靠性約束，驅(qū)使種群快速向可行解區(qū)域進(jìn)化，提升算法對(duì)動(dòng)態(tài)環(huán)境的適應(yīng)性。

根據(jù)可靠性約束（11）可以看到，要想測試時(shí)間分配方案滿足給定的可靠性下限約束，每個(gè)構(gòu)件i分配到的測試時(shí)間至少存在一個(gè)下限。同理，根據(jù)測試時(shí)間上限約束（12），每個(gè)構(gòu)件i分配到的測試時(shí)間至少存在一個(gè)上限。如果能把區(qū)間盡可能地縮小，則可以在種群初始化時(shí)，利用這個(gè)區(qū)間驅(qū)使每個(gè)個(gè)體盡可能地同時(shí)滿足給定的可靠性下限約束和測試時(shí)間上限約束，即盡量讓每個(gè)個(gè)體可行。基于上述考慮，首先，根據(jù)式（5）和（8）可以得到：

以式（16）作為等式約束條件，利用經(jīng)典的拉格朗日乘子法［2］求解最小化總測試時(shí)間消耗，即滿足時(shí)最少需要投入的總測試時(shí)間，然后可推導(dǎo)出此時(shí)每個(gè)構(gòu)件投入的測試時(shí)間為：

再由式（12），得到

表示第k階段可用的測試時(shí)間總量，則可得出且。這是因?yàn)?，時(shí)可靠性不可能滿足超過時(shí)則會(huì)違背測試時(shí)間約束。

通過上述種群重新初始化策略，可以在每一個(gè)階段，迅速讓個(gè)體逼近同時(shí)滿足可靠性和測試時(shí)間約束的可行解區(qū)域，加快種群的進(jìn)化，提升算法的收斂性能。

2.4 歸一化加權(quán)求和選取方案

每一個(gè)階段優(yōu)化完成后，需要從解集中選取一個(gè)最佳分配方案來規(guī)劃當(dāng)前測試階段。本文使用流行的歸一化加權(quán)求和方法［8，14］進(jìn)行測試時(shí)間分配方案的選?。?/p>

其中：w1，w2，w3∈[0，1]表示各個(gè)目標(biāo)的重要程度，滿足w1+w2+w3=1；為第j個(gè)目標(biāo)的歸一化值，如式（22）。

其中：min(fj)和max(fj)分別表示解集中第j個(gè)目標(biāo)上的最小值和最大值。

基于式（21）對(duì)解集中所有的解進(jìn)行歸一化加權(quán)求和，然后選擇值最小的f對(duì)應(yīng)的解作為當(dāng)前階段的測試時(shí)間分配方案。

此外，在本文中，隨著測試階段數(shù)的增加，投入的測試時(shí)間總量不斷加大，這時(shí)可以更加注重可靠性的權(quán)重，因?yàn)檐浖y試的最終目標(biāo)就是為了最大化系統(tǒng)的可靠性［1］。因此，隨著階段數(shù)的增加，本文動(dòng)態(tài)增加可靠性目標(biāo)f1的權(quán)重w1。

2.5 DTRA-GDE3算法框架

圖2 給出了本文DTRA-GDE3 算法的流程，其基本思想是：在每個(gè)測試階段開始時(shí)，首先基于上一階段的測試結(jié)果（糾正的錯(cuò)誤數(shù)和新發(fā)現(xiàn)的錯(cuò)誤數(shù)），利用極大似然估計(jì)對(duì)構(gòu)件的參數(shù)進(jìn)行重新估計(jì)，以讓構(gòu)件參數(shù)適應(yīng)測試環(huán)境的變化；然后基于更新后的構(gòu)件參數(shù)和模型參數(shù)（當(dāng)前可用的測試時(shí)間總量和可靠性約束），利用二分法和拉格朗日乘子法確定每個(gè)構(gòu)件測試時(shí)間的上下限，以讓決策變量適應(yīng)測試環(huán)境的變化；緊接著，利用GDE3 算法優(yōu)化當(dāng)前階段的MOTRA；最后，利用歸一化加權(quán)求和選取當(dāng)前階段的最佳分配方案規(guī)劃當(dāng)前階段的測試活動(dòng)。

圖2 DTRA-GDE3算法的流程Fig.2 Flowchart of DTRA-GDE3 algorithm

二分法和拉格朗日乘子法的時(shí)間復(fù)雜度為O(n)，確定每個(gè)構(gòu)件的測試時(shí)間上下限的時(shí)間復(fù)雜度最多為O(n2)，因此在上述流程中，DTRA-GDE3 算法的時(shí)間主要耗費(fèi)在GDE3 中，其時(shí)間復(fù)雜度為O(GmaxMNlogN)。因此，DTRA-GDE3 算法總的時(shí)間復(fù)雜度為O(sGmaxMNlogN)，其中s為測試階段數(shù)。

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

為了驗(yàn)證本文所提算法的有效性，與文獻(xiàn)［8］的WNSMODE 算法進(jìn)行對(duì)比分析。WNS-MODE 算法是Yang 等［8］為求解構(gòu)件軟件的MOTRA 而設(shè)計(jì)的一種高效多目標(biāo)優(yōu)化算法。

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

本文考慮兩種體系結(jié)構(gòu)軟件系統(tǒng)：單輸入單輸出（Single-Input and Single-Output，SISO）系統(tǒng)和多輸入多輸出（Multi-Input and Multi-Output，MIMO）系統(tǒng)［8］。此外，如圖1 所示，體系結(jié)構(gòu)軟件模型的復(fù)雜性除了構(gòu)件數(shù)，主要體現(xiàn)在系統(tǒng)中狀態(tài)轉(zhuǎn)移邊的總數(shù)。因此，為了更加全面地進(jìn)行對(duì)比分析，在SISO 系統(tǒng)和MIMO 系統(tǒng)上分別采用三種不同的規(guī)模：10 個(gè)構(gòu)件、約40 條狀態(tài)轉(zhuǎn)移邊的簡單系統(tǒng)；20 個(gè)構(gòu)件、約150 條狀態(tài)轉(zhuǎn)移邊的復(fù)雜系統(tǒng)；50個(gè)構(gòu)件、約800條狀態(tài)轉(zhuǎn)移邊的大型系統(tǒng)。模型參數(shù)如表1所示，共有3個(gè)測試階段。構(gòu)件的初始參數(shù)范圍如表2 所示，這些參數(shù)范圍均來自文獻(xiàn)［8，14］。此外，c0=50，c4=50 000。本文依據(jù)上述參數(shù)對(duì)SISO系統(tǒng)和MIMO系統(tǒng)各隨機(jī)生成10個(gè)不同的實(shí)例。

表1 系統(tǒng)模型參數(shù)Tab.1 Parameters of system model

表2 構(gòu)件參數(shù)范圍Tab.2 Parameter range of components

DTRA-GDE3 和WNS-MODE 的算法參數(shù)設(shè)置如下：種群規(guī)模為250，每階段都迭代500 次，CR=0.9，F(xiàn)=0.1。此外，在WNS-MODE 中，歸一化加權(quán)求和的權(quán)重固定為w1=0.1，w2=0.4，w3=0.5。在DTRA-GDE3 中，w1，w2，w3在三個(gè)階段的值分別為｛0.1，0.4，0.5｝、｛0.04，0.35，0.61｝和｛0.01，0.3，0.69｝，在第二和第三階段的值分別在［20，60］和［3，12］中隨機(jī)生成。

所有對(duì)比算法的代碼均基于C++編寫，為了能夠進(jìn)行統(tǒng)計(jì)分析，每個(gè)實(shí)例均在Intel Core i5 CPU @ 3.2 GHz、8 GB RAM個(gè)人計(jì)算機(jī)上獨(dú)立運(yùn)行30次。

為了衡量解集的優(yōu)劣，使用經(jīng)典的覆蓋值（Coverage value，Cv）［19］指標(biāo)。Cv 直觀地比較了一個(gè)算法得到的解有多少被對(duì)比算法的解所支配，可作為收斂性指標(biāo)來比較不同算法的解集的質(zhì)量。假設(shè)A和B分別表示兩個(gè)不同算法得到的解集，如果A中的一個(gè)解在任何目標(biāo)上都不比B中的另一個(gè)解差，則稱A中的這個(gè)解覆蓋了B中的一個(gè)解。Cv(A，B)表示A覆蓋B的百分比，即B中被A覆蓋的解在B中的占比。Cv(A，B) ＞Cv(B，A)表示A對(duì)應(yīng)的算法要比B對(duì)應(yīng)的算法收斂性更好。為了計(jì)算在每個(gè)實(shí)例上對(duì)比算法的覆蓋值，對(duì)于每個(gè)實(shí)例，將30 次獨(dú)立運(yùn)行得到的解集合并在一起，并去掉重復(fù)的解，然后比較合并解集之間的覆蓋值［20］。

為了進(jìn)一步對(duì)比算法的整體性能，使用流行的超體積指標(biāo)［21］。超體積指的是非支配解集與參考點(diǎn)之間的目標(biāo)空間的體積，可以從整體上衡量整個(gè)解集的收斂性和多樣性。通常，超體積值越大意味著解集的質(zhì)量越好。需要注意的是，參考點(diǎn)的選擇對(duì)于計(jì)算超體積至關(guān)重要。為了確定合適的參考點(diǎn)，對(duì)于每個(gè)實(shí)例，首先將所有算法的30 次獨(dú)立運(yùn)行獲得的解合并在一起，然后去掉重復(fù)解，再對(duì)剩下的解進(jìn)行非支配排序，去掉所有的支配解，對(duì)于余下的非支配解，可將參考點(diǎn)設(shè)置為每個(gè)目標(biāo)上最差值的1.1 倍，這種方法已被驗(yàn)證可以在解集的收斂性和多樣性之間達(dá)到一個(gè)良好平衡［20］。

除了一般多目標(biāo)優(yōu)化問題的質(zhì)量指標(biāo)（如覆蓋值和超體積）外，在基于搜索的軟件工程中，還強(qiáng)烈建議能夠適應(yīng)用戶顯式/隱式偏好的問題特定指標(biāo)來評(píng)估解集［22］。在這里，考慮容量值指標(biāo)［23］。容量值指的是算法最終得到的非支配可行解的個(gè)數(shù)，即滿足所有約束條件的非支配解數(shù)目。和上面一樣，對(duì)于每個(gè)實(shí)例，將30 次獨(dú)立運(yùn)行得到的解集合并在一起，并去掉重復(fù)的解。

3.2 容量值結(jié)果

為了方便后續(xù)描述，將DTRA-GDE3 所獲得的解集標(biāo)記為A，WNS-MODE得到的解集標(biāo)記為B。

表3～5 分別給出了DTRA-GDE3 和WNS-MODE 算法在簡單、復(fù)雜和大型SISO 和MIMO 系統(tǒng)上20 個(gè)實(shí)例的容量值結(jié)果，分別用 |A| 與 |B| 表示代表A、B算法獲得解集的容量值，即滿足條件的解的個(gè)數(shù)。由表3和表4可以看出，在簡單和復(fù)雜SISO和MIMO系統(tǒng)上，本文DTRA-GDE3算法在任何一次運(yùn)行中都能找到很多可行的非支配解，而WNS-MODE 算法在第1階段就只能找到很少的可行解，在第2 階段和第3 階段更少，甚至30 次運(yùn)行都找不到可行解，如簡單SISO 系統(tǒng)的實(shí)例1 的第2階段，簡單MIMO 系統(tǒng)的實(shí)例3的第2階段，復(fù)雜MIMO 系統(tǒng)的實(shí)例4的第2階段。特別地，在表5中，DTRA-GDE3在10個(gè)實(shí)例上獲得的可行解均接近7 500 個(gè)，但WNS-MODE 算法在10個(gè)實(shí)例上幾乎找不到可行解。

表3 簡單系統(tǒng)中兩種算法的容量值結(jié)果Tab.3 Capacity value results of two algorithms in simple system

表4 復(fù)雜系統(tǒng)中兩種算法的容量值結(jié)果Tab.4 Capacity value results of two algorithms in complex system

表5 大型系統(tǒng)中兩種算法的容量值結(jié)果Tab.5 Capacity value results of two algorithms in large system

總的來說，在SISO 系統(tǒng)上，DTRA-GDE3 在簡單、復(fù)雜和大型三個(gè)規(guī)模上獲得的解集的平均容量值分別為7 499、7 041和7 393，而WNS-MODE 算法在三個(gè)不同規(guī)模獲得的平均容量值卻僅有925、473 和3，DTRA-GDE3 在整體上的容量值提升了約15倍。在MIMO系統(tǒng)上，DTRA-GDE3在三個(gè)不同規(guī)模上獲得的解集的平均容量值分別為7 500、7 168、7 419，而WNS-MODE 算法在三個(gè)不同規(guī)模上獲得的平均容量值分別為803、373 和1，DTRA-GDE3 在整體上的容量值提升了約18倍。綜合考慮兩種系統(tǒng)，DTRA-GDE3 較WNS-MODE 在容量值上提升了約16 倍；而且，規(guī)模越大，DTRA-GDE3 算法的優(yōu)勢越明顯。上述實(shí)驗(yàn)結(jié)果表明，本文DTRA-GDE3 算法要比WNS-MODE 算法具有更好的探索能力，可以很好地適應(yīng)不同的系統(tǒng)規(guī)模，挖掘更多的非支配可行解。

3.3 覆蓋值結(jié)果

由于WNS-MODE 算法在大型規(guī)模上幾乎找不到可行解，因此，表6 和表7 分別給出了兩種算法在簡單和復(fù)雜SISO 和MIMO 系統(tǒng)上20 個(gè)實(shí)例的覆蓋值結(jié)果。可以看出，DTRAGDE3算法的覆蓋值除了在簡單MIMO 系統(tǒng)實(shí)例8的第3階段略遜于WNS-MODE 外，在其他簡單和復(fù)雜SISO 和MIMO 系統(tǒng)的所有實(shí)例的所有階段上均顯著優(yōu)于WNS-MODE 算法。在某些實(shí)例上，DTRA-GDE3算法的覆蓋值達(dá)到了100%，即可以完全支配WNS-MODE 算法的解集，如簡單SISO 系統(tǒng)的實(shí)例1和實(shí)例4的第2階段，簡單MIMO 系統(tǒng)的實(shí)例1和實(shí)例3的第2階段和第3 階段，實(shí)例2 的第3 階段，實(shí)例10 的第2 階段。尤其在復(fù)雜系統(tǒng)上，DTRA-GDE3 在24 種情形下覆蓋值達(dá)到100%，而WNS-MODE算法在10種情形下覆蓋值為零。

表6 簡單系統(tǒng)中兩種算法的覆蓋值結(jié)果 單位：%Tab.6 Coverage value results of two algorithms in simple system unit：%

表7 復(fù)雜系統(tǒng)中兩種算法的覆蓋值結(jié)果 單位：%Tab.7 Coverage value results of two algorithms in complex system unit：%

從總體上看，在SISO 系統(tǒng)上，DTRA-GDE3 在簡單和復(fù)雜兩種規(guī)模上獲得的解集的平均覆蓋值分別為91.26%和95.01%，而WNS-MODE 算法在這兩種規(guī)模上獲得的平均覆蓋值卻僅有14.21%和7.29%，DTRA-GDE3 在整體上的覆蓋值提升了約83個(gè)百分點(diǎn)。在MIMO系統(tǒng)上，DTRA-GDE3在兩種規(guī)模上獲得的解集的平均覆蓋值分別為92.18% 和95.26%，而WNS-MODE 算法在兩種規(guī)模上獲得的平均覆蓋值分別為12.17%和4.97%，DTRA-GDE3 在整體上的覆蓋值提升了約85 個(gè)百分點(diǎn)。綜合考慮兩種系統(tǒng)，DTRA-GDE3 較WNS-MODE 在覆蓋值上提升了約84 個(gè)百分點(diǎn)。上述實(shí)驗(yàn)結(jié)果表明，本文DTRA-GDE3 算法要比WNS-MODE 算法具有更好的收斂性，可以找到更好的非支配解。

3.4 超體積結(jié)果

表8 和表9 分別給出了兩種算法在簡單和復(fù)雜SISO 和MIMO 系統(tǒng)上20個(gè)實(shí)例的超體積結(jié)果（均值和標(biāo)準(zhǔn)差）?？梢钥闯觯嗽诤唵蜸ISO 系統(tǒng)實(shí)例9 第3 階段上DTRA-GDE3 得到的超體積不大于WNS-MODE 算法外，在其他簡單和復(fù)雜SISO 和MIMO 系統(tǒng)的任何實(shí)例任何階段上，DTRA-GDE3得到的超體積均要優(yōu)于WNS-MODE 算法。特別地，在某些實(shí)例上WNS-MODE 的超體積為0，說明解集中的解均被參考點(diǎn)支配或者找不到任何可行解，如簡單SISO 系統(tǒng)實(shí)例1 的第2 階段，簡單MIMO 系統(tǒng)實(shí)例3的第2階段，復(fù)雜SISO 系統(tǒng)實(shí)例4的第1階段，復(fù)雜MIMO系統(tǒng)實(shí)例4的第2階段。

表8 簡單系統(tǒng)中兩種算法的超體積（均值和標(biāo)準(zhǔn)差）結(jié)果Tab.8 Hypervolume（mean and standard deviation）results of two algorithms in simple system

表9 復(fù)雜系統(tǒng)中兩種算法的超體積（均值和標(biāo)準(zhǔn)差）結(jié)果Tab.9 Hypervolume（mean and standard deviation）results of two algorithms in complex system

從整體上來看，在SISO 系統(tǒng)上，DTRA-GDE3 相比WNSMODE的超體積在簡單和復(fù)雜規(guī)模上分別提升了約13%和22倍，在MIMO 系統(tǒng)上，DTRA-GDE3 相比WNS-MODE 的超體積在簡單和復(fù)雜規(guī)模上分別提升了約13%和69%。綜合考慮兩種系統(tǒng)，DTRA-GDE3 較WNS-MODE 在超體積上提升了約6倍。上述實(shí)驗(yàn)結(jié)果表明，本文DTRA-GDE3 算法要比WNSMODE算法具有更好的綜合性能。

為了直觀地理解非支配解的分布以及更高的超體積代表的含義，在圖3 中，根據(jù)簡單MIMO 系統(tǒng)中的實(shí)例9 分別在三個(gè)階段選取和超體積均值比較接近的一次運(yùn)行結(jié)果，繪出解集的分布情況。之所以選取這個(gè)實(shí)例，是因?yàn)樗某w積與整體超體積均值更接近。從圖3 可以看出，與WNS-MODE 算法相比，DTRA-GDE3 算法得到的解在目標(biāo)空間中分布更廣，提供了更多的多樣性。此外，易觀察到DTRA-GDE3 算法似乎比WNS-MODE 算法具有更好的收斂性，有相當(dāng)多的解優(yōu)于WNS-MODE算法。

圖3 兩種算法在簡單MIMO系統(tǒng)實(shí)例9上獲得的非支配解Fig.3 Non-dominated solutions obtained by two algorithms on Instance 9 of simple MIMO system

3.5 運(yùn)行時(shí)間結(jié)果

圖4 給出了兩種算法在MIMO 系統(tǒng)上不同規(guī)模的10 個(gè)實(shí)例上的運(yùn)行時(shí)間結(jié)果（均值和標(biāo)準(zhǔn)誤差）。從圖4 可以看出，DTRA-GDE3在簡單系統(tǒng)、復(fù)雜系統(tǒng)和大型系統(tǒng)上的平均運(yùn)行時(shí)間分別約為16.9 s、75.8 s 和37.6 s，而WNS-MODE 運(yùn)行時(shí)間分別約為2.2 s、14 s 和9 s。DTRA-GDE3 要比WNS-MODE稍微耗時(shí)一點(diǎn)。這是因?yàn)?，在求解本文的?gòu)件軟件測試資源動(dòng)態(tài)分配問題上，DTRA-GDE3 的時(shí)間復(fù)雜度為O(sGmaxMNlogN)，而WNS-MODE的時(shí)間復(fù)雜度為O(sGmaxMN)，而且，DTRA-GDE3 還需要多次調(diào)用拉格朗日乘子法來估計(jì)構(gòu)件的測試時(shí)間上下限，而且調(diào)用的次數(shù)也與解空間大小有關(guān)，具有一定的隨機(jī)性。需要強(qiáng)調(diào)的是，雖然DTRA-GDE3 相比WNS-MODE 平均慢了30 多秒，但是相比在容量值、覆蓋值和超體積三個(gè)指標(biāo)上的顯著提升，這點(diǎn)耗時(shí)是可以忽略不計(jì)的。

圖4 兩種算法在MIMO系統(tǒng)上的運(yùn)行時(shí)間（均值和標(biāo)準(zhǔn)誤差）Fig.4 Running times（means and standard errors）of two algorithms on MIMO systems

3.6 討論

從上面的容量值、覆蓋值和超體積的實(shí)驗(yàn)結(jié)果可以看出，與WNS-MODE 算法相比，本文的DTRA-GDE3 算法可以很好地滿足體系結(jié)構(gòu)軟件模型的動(dòng)態(tài)測試需求，能夠?yàn)槊總€(gè)測試階段提供更多、更好的測試時(shí)間分配方案。這是因?yàn)?，在DTRA-GDE3 算法中，根據(jù)參數(shù)重估計(jì)，可以很好地適應(yīng)糾正和發(fā)現(xiàn)的錯(cuò)誤數(shù)的變化；其次，根據(jù)種群重新初始化，可以讓個(gè)體盡可能地滿足測試時(shí)間和可靠性約束，從而接近可行解區(qū)域，促使DTRA-GDE3 算法高效地適應(yīng)環(huán)境的變化。而WNS-MODE 算法雖然也對(duì)測試時(shí)間的變化采取了相應(yīng)的約束處理技術(shù)，但是其首先滿足的是測試時(shí)間約束，而沒有考慮可靠性約束，因此其探索可行解的能力非常有限。

本文從SISO 和MIMO 兩種系統(tǒng)的簡單、復(fù)雜和大型三種規(guī)模進(jìn)行了對(duì)比分析。實(shí)驗(yàn)結(jié)果表明，對(duì)于一些復(fù)雜難解的多目標(biāo)優(yōu)化問題，完全可以根據(jù)問題本身來挖掘有用的信息，利用問題本身的知識(shí)來縮小MOEA 種群的探索范圍，避免無效的重復(fù)搜索，從而提升MOEA 解決復(fù)雜動(dòng)態(tài)多約束優(yōu)化問題的能力。

4 結(jié)語

測試資源分配是基于搜索的軟件工程中的一個(gè)熱點(diǎn)問題，主要研究如何規(guī)劃軟件工程師的測試時(shí)間，從而盡可能地縮短測試周期，降低測試成本，提高軟件系統(tǒng)的可靠性。本文針對(duì)體系結(jié)構(gòu)軟件模型的動(dòng)態(tài)測試問題，首先構(gòu)建了一種基于體系結(jié)構(gòu)和可靠性、錯(cuò)誤數(shù)動(dòng)態(tài)變化的多階段多目標(biāo)測試資源分配模型，然后基于參數(shù)重估計(jì)、種群重新初始化、廣義差分進(jìn)化和歸一化加權(quán)求和設(shè)計(jì)了一種面向動(dòng)態(tài)可靠性和錯(cuò)誤數(shù)的多階段多目標(biāo)測試資源分配算法。與已有工作相比，本文所提算法在容量值、覆蓋值和超體積三個(gè)主流性能指標(biāo)上獲得了更優(yōu)的結(jié)果。在今后的工作中，將考慮成本的約束，以及構(gòu)件的動(dòng)態(tài)增加等問題。