鬼佬大哥大
  • / 13
  • 下載費用:30 金幣  

基于多目標差異演化算法的軟件測試資源動態分配方法.pdf

摘要
申請專利號:

CN201510320713.0

申請日:

2015.06.10

公開號:

CN104899101A

公開日:

2015.09.09

當前法律狀態:

實審

有效性:

審中

法律詳情: 實質審查的生效IPC(主分類):G06F 9/50申請日:20150610|||公開
IPC分類號: G06F9/50; G06F11/36 主分類號: G06F9/50
申請人: 合肥工業大學
發明人: 張國富; 蘇兆品; 岳峰; 齊美彬; 蔣建國; 王永奇
地址: 230009安徽省合肥市屯溪路193號
優先權:
專利代理機構: 安徽合肥華信知識產權代理有限公司34112 代理人: 余成俊
PDF完整版下載: PDF下載
法律狀態
申請(專利)號:

CN201510320713.0

授權公告號:

|||

法律狀態公告日:

2015.10.07|||2015.09.09

法律狀態類型:

實質審查的生效|||公開

摘要

本發明公開了一種基于多目標差異演化算法的軟件測試資源動態分配方法,可應用于串并聯軟件系統的模塊化測試。它是針對目前測試資源分配方法不考慮隨著測試進程發生變化而導致資源浪費的情況。該方法包括步驟:S1,為可行解編碼;S2,測試階段劃分;S3,控制參數設置;S4,初始化種群;S5,變異操作;S6,交叉操作;S7,基于非支配排序的選擇操作;S8,判斷是否達到最大迭代次數,若否,則跳到S5;若是,則跳到S9;S9,為pareto解解碼;S10,判斷是否還存在未進行的測試階段,若否,則結束求解過程;若存在,跳到S11;S11,更新下一測試階段的測試資源,跳到S4,進入下一測試階段。

權利要求書

權利要求書
1.  基于多目標差異演化算法的軟件測試資源動態分配方法,其特征在于:包括以下步驟:
(1)、對所求問題進行分析,為可行解設計編碼方法;
(2)、對整個測試環節進行劃分,劃分為若干個測試階段;
(3)、對差異演化算法中的種群規模、迭代次數、交叉概率、變異概率等控制參數進行設置;
(4)、對種群進行初始化操作;
(5)、對種群中的個體進行變異操作;
(6)、對變異生成的個體與原種群中的個體進行交叉操作;
(7)、采用非支配排序機制進行選擇操作;
(8)、判斷是否達到最大迭代次數,若否,則跳到步驟(5),繼續進化操作;若是,則跳到步驟(9);
(9)、對pareto解進行解碼;
(10)、判斷是否還存在未進行的測試階段,若存在,跳到步驟(11);若否,則結束求解過程;
(11)、更新下一測試階段的測試資源,跳到步驟(4),進入下一測試階段。

2.  根據權利要求1所述的基于多目標差異演化算法的軟件測試資源動態分配方法,其特征在于:步驟(1)中為可行解進行一維整數向量編碼;且若軟件系統包含m個串聯子系統,每個子系統Sj(j=1,2,…,m)由nj個并聯模塊組成,則每個個體包含m個整數向量Γ1,…,Γj…,Γm,每個向量包含nj個元素tjk表示模塊Mjk所分配到的測試資源。

3.  根據權利要求1所述的基于多目標差異演化算法的軟件測試資源動態分配方法,其特征在于:步驟(2)中,將測試資源T分為p個測試階段:
(T0=0,T1],…,(Ti-1,Ti],…,(Tp-1,Tp=T]。

4.  根據權利要求1所述的基于多目標差異演化算法的軟件測試資源動態分配方法,其特征在于:步驟(3)中,對差異演化算法中的種群規模、迭代次數、 交叉概率、變異概率這些控制參數進行設置。

5.  根據權利要求1所述的基于多目標差異演化算法的軟件測試資源動態分配方法,其特征在于:步驟(4)中,對種群進行初始化操作,按照不同測試階段采用不同的種群初始化方法;
在步驟(4)中,對于第i=1個測試階段(T0=0,T1],由于系統各個模塊的可靠性都較低,采用隨機的方法初始化每個子系統中每個模塊的測試資源:
tjk=rand(0,T1)k=1rand(0,T1-Σj=1j-1maxk∈[1,nj]{tjk})k=2,3,···,nj]]>
其中,rand(u1,u2)函數表示在區間(u1,u2)內隨機取整數;
在步驟(4)中,對于第i個(i≥2)測試階段(Ti-1,Ti],種群初始化的方法是根據模塊已達到的可靠性rjk分配測試資源:
tjk=rand(0,Ti-Ti-1-Σj=1j-1maxk&Element;[1,nj]{tj,k})rjk<θ0rjk&GreaterEqual;θ]]>
其中,θ是用戶希望達到的模塊可靠性閾值,rjk是模塊Mjk已經達到的可靠性值。

6.  根據權利要求1所述的基于多目標差異演化算法的軟件測試資源動態分配方法,其特征在于:步驟(5)中,對種群中的個體進行變異操作,采用方法是DE/best/2/bin模式。

7.  根據權利要求1所述的基于多目標差異演化算法的軟件測試資源動態分配方法,其特征在于:步驟(6)中,對變異生成的個體與原種群中的個體進行位交叉操作,生成2個不同的個體。

8.  根據權利要求1所述的基于多目標差異演化算法的軟件測試資源動態分配方法,其特征在于:步驟(7)中,采用非支配排序機制進行選擇操作,選擇的對象集合包括原種群個體、變異后的個體以及交叉產生的個體;
步驟(7)中,非支配排序機制是指對種群按照優化目標函數進行分層,并計算個體擁擠度來衡量個體在每層的優劣,然后根據個體的分層和擁擠度的大小 選取較優的個體組成新的種群;
步驟(7)中,優化目標函數為:
MaxRi(x/(Ti-Ti-1))=Πj=1m{1-Πk=1nj[1-rjk(x/tijk)]}]]>
MinCi=Σj=1mΣk=1njCjk(rijk)]]>
MinTia=Σj=1mtij=Σj=1mmaxk{tijk}]]>
s.t.
Tia≤Ti-Ti-1
0<tijk≤Ti-Ti-1
其中,tijk表示模塊Mjk在第i個測試階段所分配到的測試資源,rijk表示模塊Mjk在第i個測試階段的可靠性值,且rijk=rjk(x/tijk),Ri(x/(Ti-Ti-1))、Ci和Tia分別表示軟件系統在第i個測試階段的總體可靠性、總體測試代價和系統實際消耗的總測試資源,rjk(x/tijk)和Cjk(rijk)分別表示模塊Mjk在第i個測試階段的可靠性和測試代價,均為測試資源的函數。

9.  根據權利要求1所述的基于多目標差異演化算法的軟件測試資源動態分配方法,其特征在于:步驟(9)中,對pareto解進行解碼,具體操作包括:計算每個模塊的可靠性rjk,計算每個模塊的測試代價Cjk,計算軟件系統的實際測試時間Tia。

10.  根據權利要求1所述的基于多目標差異演化算法的軟件測試資源動態分配方法,其特征在于:步驟(11)中,更新下一測試階段的測試資源,方法為:
Ti←Ti-(Ti-Ti-1-Tia)。

說明書

說明書基于多目標差異演化算法的軟件測試資源動態分配方法
技術領域
本發明涉及軟件測試方法領域,具體是一種基于多目標差異演化算法的軟件測試資源動態分配方法。
背景技術
隨著軟件系統的廣泛應用,軟件復雜度不斷提高,包括的模塊越多。在測試過程中,每個模塊都需要經過測試。特別是在軟件的單元測試中,不同模塊的測試活動都在激烈爭奪有限的測試資源,不同的測試活動也會帶來不同的成本的上升與可靠性的增加。軟件工程師必須清楚如何將測試資源分配給不同的模塊測試。測試資源分配問題就是如何把有限的測試資源分配給每一個模塊,從而保證軟件系統的可靠性最大。
測試資源分配問題是系統可靠性優化中的關鍵和重要問題。自二十世紀九十年代以來,已經成為研究的熱點問題。目前的研究大都是基于測試代價、系統可靠性、測試資源為核心的多目標優化問題。
但是已有的測試資源分配模型和分配方法均屬于靜態分配測試資源的方法,即根據系統初始時刻各模塊的可靠性進行測試資源的分配,很少考慮各模塊可靠性隨著測試進程發生變化的情況。這些模型和方法的缺點是會造成測試資源大量浪費在可靠性已經很高、不在需要測試資源的模塊上,導致在測試完成后,有些模塊的可靠性遠遠低于系統的可靠性,使軟件測試的效果不佳。
發明內容
本發明的目的是提供一種基于多目標差異演化算法的軟件測試資源動態分配方法,以解決現有技術軟件測試資源分配方案因不考慮各模塊可靠性隨著測試進程發生變化的情況而導致測試資源浪費、測試效果差的問題,。
為了達到上述目的,本發明所采用的技術方案為:
基于多目標差異演化算法的軟件測試資源動態分配方法,其特征在于:包括以下步驟:
(1)、對所求問題進行分析,為可行解設計編碼方法;
(2)、對整個測試環節進行劃分,劃分為若干個測試階段;
(3)、對差異演化算法中的種群規模、迭代次數、交叉概率、變異概率等控制參數進行設置;
(4)、對種群進行初始化操作;
(5)、對種群中的個體進行變異操作;
(6)、對變異生成的個體與原種群中的個體進行交叉操作;
(7)、采用非支配排序機制進行選擇操作;
(8)、判斷是否達到最大迭代次數,若否,則跳到步驟(5),繼續進化操作;若是,則跳到步驟(9);
(9)、對pareto解進行解碼;
(10)、判斷是否還存在未進行的測試階段,若存在,跳到步驟(11);若否,則結束求解過程;
(11)、更新下一測試階段的測試資源,跳到步驟(4),進入下一測試階段。
所述的基于多目標差異演化算法的軟件測試資源動態分配方法,其特征在于:步驟(1)中為可行解進行一維整數向量編碼;且若軟件系統包含m個串聯子系統,每個子系統Sj(j=1,2,…,m)由nj個并聯模塊Mj1,…,Mjk,…,組成,則每個個體包含m個整數向量Γj,…,Γj…,Γm,每個向量包含nj個元素tj1,…,tjk,…,,tjk表示模塊Mjk所分配到的測試資源。
所述的基于多目標差異演化算法的軟件測試資源動態分配方法,其特征在于:步驟(2)中,將測試資源T分為p個測試階段:
(T0=0,T1],…,(Ti-1,Ti],…,(Tp-1,Tp=T]。
所述的基于多目標差異演化算法的軟件測試資源動態分配方法,其特征在于:步驟(3)中,對差異演化算法中的種群規模、迭代次數、交叉概率、變異概率等控制參數進行設置。
所述的基于多目標差異演化算法的軟件測試資源動態分配方法,其特征在于:步驟(4)中,對種群進行初始化操作,按照不同測試階段采用不同的種群初始化方法;
在步驟(4)中,對于第i=1個測試階段(T0=0,T1],由于系統各個模塊的可 靠性都較低,采用隨機的方法初始化每個子系統中每個模塊的測試資源:
tjk=rand(0,T1)k=1rand(0,T1-Σj=1j-1maxk&Element;[1,nj{tjk)k=2,3,&CenterDot;&CenterDot;&CenterDot;,nj]]>
其中,rand(u1,u2)函數表示在區間(u1,u2)內隨機取整數;
在步驟(4)中,對于第i個(i≥2)測試階段(Ti-1,Ti],種群初始化的方法是根據模塊已達到的可靠性rjk分配測試資源:
tjk=rand(0,Ti-Ti-1-Σj=1j-1maxk&Element;[1,nj{tjk)rjk<θ0rjk&GreaterEqual;θ]]>
其中,θ是用戶希望達到的模塊可靠性閾值rjk是模塊Mjk已經達到的可靠性值。
所述的基于多目標差異演化算法的軟件測試資源動態分配方法,其特征在于:步驟(5)中,對種群中的個體進行變異操作,采用方法是DE/best/2/bin模式。
所述的基于多目標差異演化算法的軟件測試資源動態分配方法,其特征在于:步驟(6)中,對變異生成的個體與原種群中的個體進行位交叉操作,生成2個不同的個體。
所述的基于多目標差異演化算法的軟件測試資源動態分配方法,其特征在于:步驟(7)中,采用非支配排序機制進行選擇操作,選擇的對象集合包括原種群個體、變異后的個體以及交叉產生的個體;
步驟(7)中,非支配排序機制是指對種群按照優化目標函數進行分層,并計算個體擁擠度來衡量個體在每層的優劣,然后根據個體的分層和擁擠度的大小選取較優的個體組成新的種群;
步驟(7)中,優化目標函數為:
MaxRi(x/(Ti-Ti-1))=Πj=1m{1-Πk=1nj[1-rjk(x/tijk)]}]]>
MinCiΣj=1mΣk=1njCjk(rijk)]]>
MinTia=Σj=1mtij=Σj=1mmaxk{tijk}]]>
s.t.
Tia≤Ti-Ti-1
0<tijk≤Ti-Ti-1
其中,tijk表示模塊Mjk在第i個測試階段所分配到的測試資源,rijk表示模塊Mjk在第i個測試階段的可靠性值,且rijk=rjk(x/tijk),Ri(x/(Ti-Ti-1))、Ci和Tia分別表示軟件系統在第i個測試階段的總體可靠性、總體測試代價和系統實際消耗的總測試資源,rjk(x/tijk)和Cjk(rijk)分別表示模塊Mjk在第i個測試階段的可靠性和測試代價,均為測試資源的函數。
所述的基于多目標差異演化算法的軟件測試資源動態分配方法,其特征在于:步驟(9)中,對pareto解進行解碼,具體操作包括:計算每個模塊的可靠性rjk,計算每個模塊的測試代價Cjk,計算軟件系統的實際測試時間Tia。
所述的基于多目標差異演化算法的軟件測試資源動態分配方法,其特征在于:步驟(11)中,更新下一測試階段的測試資源,方法為:
Ti←Ti-(Ti-Ti-1-Tia)。
本發明提出了一種基于多目標差異演化算法的軟件測試資源動態分配方法,考慮各模塊可靠性隨著測試進程發生變化的情況,在測試進程中動態地為各個模塊分配測試資源,可以節省系統測試資源的消耗,提高測試效率,提高軟件系統的可靠性。本發明優點為:
(1)本發明采用的是以測試資源為約束、聯合優化系統可靠性、系統測試代價和實際消耗的系統測試資源,不會由于三者分離而產生某一方面性能損失;
(2)本發明將整個測試環節劃分為若干個測試階段,在每個測試階段根據前一測試階段的可靠性為每個模塊動態地分配測試資源,解決了已有測試資源分配方案帶來的測試資源浪費、測試效率低的缺陷;
(3)本發明中采用的是基于非支配排序機制的多目標差異演化算法,搜索速度快、解質量高,因此可以在系統可靠性、系統測試代價和實際消耗的系統測 試資源之間達到平衡;
(4)最后,由于演化算法操作簡單,性能好,曾在首屆IEEE演化計算大賽中表現超群,非常適合在實際系統中取得應用,有較好的應用前景。
附圖說明
圖1為本發明實施例中基于多目標差異演化算法的軟件測試資源動態分配方法的流程示意圖;
圖2為本發明實施對象串并行軟件系統結構示意圖。
圖3為本發明采用的一維整數向量編碼示意圖。
圖4為軟件測試環節劃分示意圖。
圖5為本發明一個實時實例串并行軟件系統結構示意圖。
圖6為本發明的一個實施實例中本發明技術與現有技術結果的對比。
具體實施方式
本發明為了解決現有技術中軟件測試資源分配方案因不考慮各模塊可靠性隨著測試進程發生變化的情況而導致測試資源浪費、測試效果差的問題,提供了一種基于多目標差異演化算法的軟件測試資源動態分配方法,該方法主要應用于如圖2所示的串并行軟件系統的模塊測試中。如圖1的流程圖所示,本發明中的方法的基本過程為:
S1,對所求問題進行分析,為可行解設計編碼方法;
S2,對整個測試環節進行劃分,劃分為若干個測試階段;
S3,對差異演化算法中的種群規模、迭代次數、交叉概率、變異概率等控制參數進行設置;
S4,對種群進行初始化操作;
S5,對種群中的個體進行變異操作;
S6,對變異生成的個體與原種群中的個體進行交叉操作;
S7,采用非支配排序機制進行選擇操作;
S8,判斷是否達到最大迭代次數,若否,則跳到S5,繼續進化操作;若是,則跳到S9;
S9,對pareto解進行解碼;
S10,判斷是否還存在未進行的測試階段,若存在,跳到S11;若否,則結 束求解過程。
S11,更新下一測試階段的測試資源,跳到S4,進入下一測試階段;
下面對本發明的方案做進一步的說明。在本發明的方案中,首先假設串并行軟件系統由m個串聯子系統構成,每個子系統Sj(j=1,2,…,m)由nj個冗余模塊Mj1,…,Mjk,…,并聯組成;每個模塊的測試是單獨進行的;任意模塊Mjk的平均失效次數符合非齊次泊松過程分布;每次失效(錯誤)的發生是相互獨立的。
步驟S1中涉及編碼設計:
采用一維整數向量編碼表示一個個體,如圖3所示。在每個編碼中,有m個整數向量,Γj,…,Γj…,Γm,每個向量包含nj個元素tj1,…,tjk,…,。Γj表示子系統Sj中每個模塊分配到的測試資源向量,且
Γj=[tj1,tj2,...,tjnj]]]>,tjk>0,k=1,2,…,nj
其中tjk表示模塊Mjk所分配到的測試資源。
步驟S2中涉及測試階段劃分:
如圖4所示,將測試資源T分為p個測試階段:
(T0=0,T1],…,(Ti-1,Ti],…,(Tp-1,Tp=T]
步驟S3中涉及控制參數設計:包括種群規模、迭代次數、交叉概率、變異概率、模塊可靠性閾值等進行設置;
在本發明的一個實施實例中,種群規模N=20,迭代次數G=200,縮放系數F=0.5,交叉概率CR=0.5,模塊可靠性閾值θ=0.99。
步驟S4中涉及種群初始化設計:種群初始化是按照不同測試階段采用不同的方法進行。
(1)對于第i=1個測試階段(T0=0,T1],由于系統各個模塊的可靠性都較低,采用隨機的方法初始化每個子系統中每個模塊的測試資源。
tjk=rand(0,T1)k=1rand(0,T1-Σj=1j-1maxk&Element;[1,nj{tjk)k=2,3,&CenterDot;&CenterDot;&CenterDot;,nj]]>
其中,rand(u1,u2)函數表示在區間(u1,u2)內隨機取整數,tjk表示模塊Mjk所 分配到的測試資源。
在本發明的一個實施實例中,如圖5,第i=1個測試階段(T0=0,T1]的種群初始化過程為:對于模塊M11,在(T0=0,T1]之間隨機生成測試資源數t11;對于子系統S2,分別對模塊M21、M22、M23和M24在剩余的資源區間(0,T1-t11)內分別生成隨機資源數t21、t22、t23和t24;對于子系統S3,分別對模塊M31和M32在剩余的資源區間內分別生成隨機資源數t31和t32;依次類推,為每一個模塊生成一個測試資源。
(2)對于第i個(i≥2)測試階段(Ti-1,Ti],種群初始化的方法是根據模塊已達到的可靠性rjk分配測試資源。
tjk=rand(0,Ti-Ti-1-Σj=1j-1maxk&Element;[1,nj{tjk)rjk<θ0rjk&GreaterEqual;θ]]>
其中,θ是用戶希望達到的模塊可靠性閾值rjk是模塊Mjk已經達到的可靠性值。
步驟S5中涉及變異操作設計:本發明采用的變異操作為

其中,F為縮放因子,F∈[0,2];是變異后的個體;x1,x2,x3,x4,x5是隨機整數,表示個體在種群中的序號;是當代最優個體。
步驟S6中涉及交叉操作設計:交叉操作是對原來個體和變異后的個體進行的,本發明采用的交叉操作是位交叉。設交叉后的個體和則:
Γ~lj=Γljrandj(0,1)CRΓ~ljrandj(0,1)>CR]]>
Γ~lj=Γ~ljrandj(0,1)CRΓljrandj(0,1)>CR]]>
其中CR是交叉因子,CR∈[0,1],控制個體間交叉的程度;rand(0,1)函數表示在區間(0,1)內取得隨機數。
步驟S7中涉及選擇操作設計:本發明采用的是非支配排序機制進行的選擇操作,步驟為:根據目標函數采用快速非支配排序對種群進行分層,并通過計算個體擁擠度的方式衡量個體在每層的優劣,根據個體的分層和擁擠度的大小選取相應的個體組成新的種群。
本發明采用的目標函數為
MaxRi(x/(Ti-Ti-1))=Πj=1m{1-Πk=1nj[1-rjk(x/tijk)]}]]>
MinCiΣj=1mΣk=1njCjk(rijk)]]>
MinTia=Σj=1mtij=Σj=1mmaxk{tijk}]]>
s.t.
Tia≤Ti-Ti-1
0<tijk≤Ti-Ti-1
其中,tijk表示模塊Mjk在第i個測試階段所分配到的測試資源,rijk表示模塊Mjk在第i個測試階段的可靠性值,且rijk=rjk(x/tijk),Ri(x/(Ti-Ti-1))、Ci和Tia分別表示軟件系統在第i個測試階段的總體可靠性、總體測試代價和系統實際消耗的總測試資源,rjk(x/tijk)和Cjk(rijk)分別表示模塊Mjk在第i個測試階段的可靠性和測試代價,均為測試資源的函數,表示為:
rjk(x/tjk)=1-Πk=1nj[1-rjk(x/tjk)]]]>
Cjk(rjk)=xjk&CenterDot;eyjk&CenterDot;rjk-zjk]]>
其中,ajk、bjk、xjk、yjk和zjk是是固定的參數。
本發明采用的快速非支配排序算法步驟為:
(1)計算每個個體的np值和sp值,記錄np=0的所有個體為Pareto第一級,其中np為支配個數,表示在可行解空間中,可以支配解p的所有解的數量,sp為被支配個體的集合,表示在可行解空間中,被解p所支配的解的集合。
(2)按順序訪問第一級的sp集合中的所有個體,對其np值執行減一操作,如果得到np為0,則該個體為Pareto第二級;
(3)按順序訪問第二級的sp集合中的所有個體,對其np值執行減一操作,如果得到np為0,則該個體為Pareto第三級;
(4)重復以上操作,直到將種群中的所有個體分配到Pareto級別。
本發明采用的擁擠度計算方法為:
(1)對于種群中的任意一個個體i,初始化擁擠度的值為0,即θdis tan cei=0.]]>
(2)對于每個目標函數,根據第τ個目標函數值對種群中的所有個體按照升序排序。
(3)記錄第一個個體和最有一個個體的擁擠度為無窮大,即第γ個個體的擁擠度為第γ+1和第γ個體的所有目標函數值之差的和,,θdis tan ceγ=θdis tan ceγ+(Fγ+1τ-Fγ-1τ)/(Fmaxτ-Fminτ).]]>
其中,表示種群中第γ個個體的擁擠度,表示種群中第γ個個體的第τ個目標函數值的大小,和分別表示種群中第τ個目標函數的最大值和最小值。
步驟S9中涉及個體解碼設計:包括計算每個模塊的可靠性rjk、每個模塊的測試代價Cjk和系統的實際測試時間Tia。
步驟S11中涉及下一測試階段測試資源的更新操作設計:下一個測試階段的測試資源更新按照:
Ti+1-Ti&DoubleLeftArrow;Ti+1-Ti+(Ti-Ti-1-Tia).]]>
圖6為本發明的一個實施實例中本發明技術與現有技術結果的對比。從圖6可以看出,本發明能夠在節省測試資源的前提下獲得較高的測試代價。
本發明為了解決現有技術中軟件測試資源分配方案因不考慮各模塊可靠性隨著測試進程發生變化的情況而導致測試資源浪費、測試效果差的問題,提供了 一種基于多目標差異演化算法的軟件測試資源動態分配方法,該方法可應用于串并行軟件系統的模塊測試中。

關 鍵 詞:
基于 多目標 差異 演化 算法 軟件 測試 資源 動態分配 方法
  專利查詢網所有資源均是用戶自行上傳分享,僅供網友學習交流,未經上傳用戶書面授權,請勿作他用。
關于本文
本文標題:基于多目標差異演化算法的軟件測試資源動態分配方法.pdf
鏈接地址:http://www.wwszu.club/p-6373678.html
關于我們 - 網站聲明 - 網站地圖 - 資源地圖 - 友情鏈接 - 網站客服客服 - 聯系我們

[email protected] 2017-2018 zhuanlichaxun.net網站版權所有
經營許可證編號:粵ICP備17046363號-1 
 


收起
展開
鬼佬大哥大