基于軟件體系結構和廣義差分進化的測試資源動態分配算法

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

（1.合肥工業大學計算機與信息學院，合肥 230601；2.大數據知識工程教育部重點實驗室（合肥工業大學），合肥 230601；3.智能互聯系統安徽省實驗室（合肥工業大學），合肥 230009；4.工業安全與應急技術安徽省重點實驗室（合肥工業大學），合肥 230601）

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

0 引言

軟件測試是軟件開發中的一個至關重要的環節，主要致力于發現和糾正軟件錯誤，提升軟件系統的可靠性。眾所周知，軟件測試幾乎要耗費軟件開發資源的一半，因此，如何合理分配測試資源，以耗費盡可能少的測試資源，謀求盡可能高的軟件可靠性和盡可能少的測試成本，一直是軟件工程領域中的一個熱點和難點問題［1］。

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

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

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

相反，基于體系結構的軟件模型能夠通過定量地識別軟件體系結構中最關鍵的構件來評估面向對象和基于構件的軟件系統的可靠性，近年來越來越受到歡迎［15-16］。因此，研究體系結構軟件模型的MOTRA 問題具有重要的現實意義。然而，時至今日僅有Yang 等［8］提出了一種歸一化加權求和多目標差分進化（Multi-Objective Differential Evolution based on Weighted Normalized Sum，WNS-MODE）算法。此外，上述工作簡單的假設軟件測試是一個靜態的過程。在實際的軟件測試中，軟件項目經理通常會根據用戶需求和軟件測試結果動態調整測試流程，即整個軟件測試環節往往被劃分成若干個測試階段［12-13］。在每個測試階段，軟件的可靠性以及發現的軟件錯誤數可能因用戶需求或軟件測試結果而發生動態變化，這時就需要根據變化后的測試環境動態調整測試時間的分配，而上述靜態測試資源分配方法顯然難以適應上述測試環境的動態變化。

基于上述背景，本文面向體系結構軟件模型，針對可靠性和發現的錯誤數在不同測試階段動態變化的測試環境，首先構造了一種基于體系結構的多階段多目標測試資源分配模型，然后基于參數重估計、種群重新初始化、GDE3和歸一化加權求和設計了一種面向動態可靠性和錯誤數的多階段多目標測試資源分配算法，最后通過仿真實驗驗證了所提方法的有效性。

1 問題描述

本節從文獻［8，15］中回顧體系結構軟件模型的測試資源分配，并將其擴展到本文的動態測試問題。

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

圖1 基于體系結構的軟件模型Fig.1 Architecture-based software model

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

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

根據吸收馬爾可夫鏈的性質，矩陣I-Q有可逆矩陣M：

M中的每個元素為從一個非吸收狀態到另一非吸收狀態的預期訪問次數，記

為從初始狀態0到非吸收狀態i的預期訪問次數［8，14］。

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

則第k個測試階段實際可用測試時間為：

根據上述知識，使用經典的可靠性增長模型來評估構件軟件系統的可靠性。在可靠性增長模型中，系統的可靠性滿足非齊次泊松過程［8］：

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

求偏導得到，即

軟件測試帶來的成本非常復雜，包含各種因素，考慮風險成本的系統成本模型［8］為：

其中：c0為軟件測試準備成本；c4為軟件失效產生的成本；為構件i的測試階段糾正軟件錯誤的成本；為構件i運行階段糾正軟件錯誤的成本；為構件i的一般測試成本（大都指人力成本）；0 ＜σi＜1為構件i的一般測試成本折扣率。

綜上所述，基于體系結構軟件模型的動態測試資源分配問題可描述為如下的一個多階段三目標優化模型：

滿足如下約束：

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

與文獻［8，14］不同的是，上述模型考慮了軟件的多階段動態測試，而且還考慮了不同階段其可靠性約束和可用的測試時間可能會發生變化。

2 測試資源動態分配算法設計

式（10）～（13）是一個典型的動態多約束多目標優化問題，對求解器的性能要求較高。Yang等［8］已經驗證在求解構件軟件的MOTRA 時，多目標差分進化算法比經典的非支配遺傳算法［17］的搜索性能更好，因此，本文引入GDE3［18］來求解構件軟件測試資源動態分配問題，稱為DTRA-GDE3（Dynamic Testing Resource Allocation based on GDE3）算法。

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

2.1 基本GDE3算法

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

1）根據約束條件隨機生成種群規模為N的初始種群。

2）根據目標函數和約束條件評估種群中每個個體的目標函數值和約束違背程度。

3）對種群中的每個個體p∈{1，2，…，N}執行如下操作：

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

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

c）生成新個體q：對于個體中的每一個基因位g，在（0，1）之間生成一個隨機數r，執行

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

d）評估新個體q的目標函數值和約束違背程度。

e）如果新個體q能夠支配當前個體p，則將個體q放入新種群中；如果當前個體p能夠支配新個體q，則將當前個體p放入新種群中；如果新個體q和當前個體p互不支配，則將這兩個個體同時放入新種群中。

4）如果新種群的規模超過了N，計算新種群中每個個體的擁擠距離，并對新種群進行非支配排序，保留N個最好的個體。

5）如果沒有達到最大迭代次數Gmax，轉步驟3），否則結束算法，輸出新種群。

由上述流程可以看出，GDE3算法的時間主要耗費在對新種群的非支配排序，其時間復雜度為O(MNlogN)［17］，其中M為優化的目標數，因此，GDE3 算法總的時間復雜度為O(GmaxMNlogN)。

2.2 構件參數重估計

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

2.3 種群重新初始化

由于在每個測試階段，可靠性約束（11）、測試時間約束（12）、（13）以及構件參數均是動態變化的，因此，在優化每個測試階段的測試時間分配時，需要在種群進化前依據新的約束空間對種群重新初始化，以盡可能地讓種群靠近當前階段的可行解區域。此外，可以通過分析模型，把測試時間盡可能地分配給最需要的構件，從而讓系統盡可能地滿足當前階段的可靠性約束，驅使種群快速向可行解區域進化，提升算法對動態環境的適應性。

根據可靠性約束（11）可以看到，要想測試時間分配方案滿足給定的可靠性下限約束，每個構件i分配到的測試時間至少存在一個下限。同理，根據測試時間上限約束（12），每個構件i分配到的測試時間至少存在一個上限。如果能把區間盡可能地縮小，則可以在種群初始化時，利用這個區間驅使每個個體盡可能地同時滿足給定的可靠性下限約束和測試時間上限約束，即盡量讓每個個體可行?；谏鲜隹紤]，首先，根據式（5）和（8）可以得到：

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

再由式（12），得到

表示第k階段可用的測試時間總量，則可得出且。這是因為，時可靠性不可能滿足超過時則會違背測試時間約束。

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

2.4 歸一化加權求和選取方案

每一個階段優化完成后，需要從解集中選取一個最佳分配方案來規劃當前測試階段。本文使用流行的歸一化加權求和方法［8，14］進行測試時間分配方案的選取：

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

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

基于式（21）對解集中所有的解進行歸一化加權求和，然后選擇值最小的f對應的解作為當前階段的測試時間分配方案。

此外，在本文中，隨著測試階段數的增加，投入的測試時間總量不斷加大，這時可以更加注重可靠性的權重，因為軟件測試的最終目標就是為了最大化系統的可靠性［1］。因此，隨著階段數的增加，本文動態增加可靠性目標f1的權重w1。

2.5 DTRA-GDE3算法框架

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

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

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

3 仿真實驗結果與分析

為了驗證本文所提算法的有效性，與文獻［8］的WNSMODE 算法進行對比分析。WNS-MODE 算法是Yang 等［8］為求解構件軟件的MOTRA 而設計的一種高效多目標優化算法。

3.1 實驗參數和評價指標

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

表1 系統模型參數Tab.1 Parameters of system model

表2 構件參數范圍Tab.2 Parameter range of components

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

所有對比算法的代碼均基于C++編寫，為了能夠進行統計分析，每個實例均在Intel Core i5 CPU @ 3.2 GHz、8 GB RAM個人計算機上獨立運行30次。

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

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

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

3.2 容量值結果

為了方便后續描述，將DTRA-GDE3 所獲得的解集標記為A，WNS-MODE得到的解集標記為B。

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

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

表4 復雜系統中兩種算法的容量值結果Tab.4 Capacity value results of two algorithms in complex system

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

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

3.3 覆蓋值結果

由于WNS-MODE 算法在大型規模上幾乎找不到可行解，因此，表6 和表7 分別給出了兩種算法在簡單和復雜SISO 和MIMO 系統上20 個實例的覆蓋值結果?？梢钥闯?，DTRAGDE3算法的覆蓋值除了在簡單MIMO 系統實例8的第3階段略遜于WNS-MODE 外，在其他簡單和復雜SISO 和MIMO 系統的所有實例的所有階段上均顯著優于WNS-MODE 算法。在某些實例上，DTRA-GDE3算法的覆蓋值達到了100%，即可以完全支配WNS-MODE 算法的解集，如簡單SISO 系統的實例1和實例4的第2階段，簡單MIMO 系統的實例1和實例3的第2階段和第3 階段，實例2 的第3 階段，實例10 的第2 階段。尤其在復雜系統上，DTRA-GDE3 在24 種情形下覆蓋值達到100%，而WNS-MODE算法在10種情形下覆蓋值為零。

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

表7 復雜系統中兩種算法的覆蓋值結果 單位：%Tab.7 Coverage value results of two algorithms in complex system unit：%

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

3.4 超體積結果

表8 和表9 分別給出了兩種算法在簡單和復雜SISO 和MIMO 系統上20個實例的超體積結果（均值和標準差）。可以看出，除了在簡單SISO 系統實例9 第3 階段上DTRA-GDE3 得到的超體積不大于WNS-MODE 算法外，在其他簡單和復雜SISO 和MIMO 系統的任何實例任何階段上，DTRA-GDE3得到的超體積均要優于WNS-MODE 算法。特別地，在某些實例上WNS-MODE 的超體積為0，說明解集中的解均被參考點支配或者找不到任何可行解，如簡單SISO 系統實例1 的第2 階段，簡單MIMO 系統實例3的第2階段，復雜SISO 系統實例4的第1階段，復雜MIMO系統實例4的第2階段。

表8 簡單系統中兩種算法的超體積（均值和標準差）結果Tab.8 Hypervolume（mean and standard deviation）results of two algorithms in simple system

表9 復雜系統中兩種算法的超體積（均值和標準差）結果Tab.9 Hypervolume（mean and standard deviation）results of two algorithms in complex system

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

為了直觀地理解非支配解的分布以及更高的超體積代表的含義，在圖3 中，根據簡單MIMO 系統中的實例9 分別在三個階段選取和超體積均值比較接近的一次運行結果，繪出解集的分布情況。之所以選取這個實例，是因為它的超體積與整體超體積均值更接近。從圖3 可以看出，與WNS-MODE 算法相比，DTRA-GDE3 算法得到的解在目標空間中分布更廣，提供了更多的多樣性。此外，易觀察到DTRA-GDE3 算法似乎比WNS-MODE 算法具有更好的收斂性，有相當多的解優于WNS-MODE算法。

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

3.5 運行時間結果

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

圖4 兩種算法在MIMO系統上的運行時間（均值和標準誤差）Fig.4 Running times（means and standard errors）of two algorithms on MIMO systems

3.6 討論

從上面的容量值、覆蓋值和超體積的實驗結果可以看出，與WNS-MODE 算法相比，本文的DTRA-GDE3 算法可以很好地滿足體系結構軟件模型的動態測試需求，能夠為每個測試階段提供更多、更好的測試時間分配方案。這是因為，在DTRA-GDE3 算法中，根據參數重估計，可以很好地適應糾正和發現的錯誤數的變化；其次，根據種群重新初始化，可以讓個體盡可能地滿足測試時間和可靠性約束，從而接近可行解區域，促使DTRA-GDE3 算法高效地適應環境的變化。而WNS-MODE 算法雖然也對測試時間的變化采取了相應的約束處理技術，但是其首先滿足的是測試時間約束，而沒有考慮可靠性約束，因此其探索可行解的能力非常有限。

本文從SISO 和MIMO 兩種系統的簡單、復雜和大型三種規模進行了對比分析。實驗結果表明，對于一些復雜難解的多目標優化問題，完全可以根據問題本身來挖掘有用的信息，利用問題本身的知識來縮小MOEA 種群的探索范圍，避免無效的重復搜索，從而提升MOEA 解決復雜動態多約束優化問題的能力。

4 結語

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