組合測(cè)試用例生成的向量累加優(yōu)化算法

宋曉秋，靳龍龍，彭樹敏

(中國(guó)航天科工集團(tuán)第二研究院 七〇六所，北京 100854)

0 引 言

組合測(cè)試方法的研究與應(yīng)用得到了長(zhǎng)足的發(fā)展[1,2]。近些年，由于實(shí)際應(yīng)用中會(huì)伴隨著各種各樣的約束條件，所以帶有約束條件的組合測(cè)試用例生成問題越來越受到關(guān)注[3-5]。

在武器裝備軟件的系統(tǒng)級(jí)測(cè)試中，許多測(cè)試充分性指標(biāo)介于兩兩組合[6,7]和三三組合[8,9]之間，即在所有參數(shù)滿足兩兩組合覆蓋的基礎(chǔ)上，對(duì)其中的關(guān)鍵參數(shù)附加要求滿足三三組合覆蓋。這是一種特殊的約束條件要求，是在兩兩組合的基礎(chǔ)上附加三三組合的條件，工程中稱之為二三組合。針對(duì)這種特殊的混合組合要求，目前還沒有行之有效的成熟算法，需要構(gòu)造特殊的算法予以解決[10]。

本文采用了一種將組合測(cè)試問題轉(zhuǎn)化為向量累加優(yōu)化問題的方法，通過向量累加優(yōu)化問題的求解，反過來得到組合測(cè)試問題的解。這種方法使得無論組合測(cè)試是何種組合要求，轉(zhuǎn)化為向量累加優(yōu)化的問題后，其求解算法都是一樣的，有效地解決了實(shí)際工程中組合測(cè)試的特殊組合問題。

1 向量累加優(yōu)化問題

定義1 設(shè)Ai=(ai,1,ai,2,…,ai,n)T∈Rn,i=1,2,…,m，滿足：

(1)?i∈{1,2,…,m}，Ai中存在k個(gè)1，其余均為0；

證畢。

能求解出向量累加優(yōu)化問題最優(yōu)解的算法稱為精確算法，無法求解出最優(yōu)解，但盡量接近最優(yōu)解的算法稱為近似算法。

2 向量累加優(yōu)化問題的求解算法

2.1 基本定義

證明：無妨假設(shè)B、C和D的元素均是由小到大的排序。

證畢。

2.2 剔除法算法

針對(duì)向量累加優(yōu)化問題，初始化Ei=0，i=1,2,…,m(Ei=-1表示剔除Ai，Ei=1表示選中Ai，Ei=0表示Ai待處理)。

記J={j|Ej=0}，J*={j|Ej=-1}，J**={j|Ej=1}。

剔除法算法的步驟為：

步驟1 如果J=φ，則轉(zhuǎn)步驟4；

步驟4 輸出解Aj，j∈J**，結(jié)束。

該算法經(jīng)歷一次步驟3，就會(huì)減少一個(gè)向量，由于是有限個(gè)向量，所以步驟4必然會(huì)執(zhí)行到。

2.3 添加法算法

針對(duì)向量累加優(yōu)化問題，初始化S=A1，E1=1，Ei=0，i=2,…,m(Ei=1表示選中Ai，Ei=0表示Ai待處理)。

記J={j|Ej=0}，J*={j|Ej=1}。

添加法算法的步驟為：

步驟1 計(jì)算Bj=S+Aj，j∈J；

步驟3 如果S中存在零元素，轉(zhuǎn)步驟1；

步驟4 輸出解Aj，j∈J*，結(jié)束。

該算法經(jīng)歷一次步驟2，就會(huì)添加一個(gè)向量，由于是有限個(gè)向量，所以步驟4必然會(huì)執(zhí)行到。

2.4 正交法算法

正交法算法是添加法算法的改進(jìn)，其思路也是從某一個(gè)向量開始逐個(gè)添加向量，直到所有添加進(jìn)的向量累積和滿足要求為止，最后所有添加進(jìn)的向量集即為近似的最優(yōu)解。為了使添加的向量盡量少，每次選擇與當(dāng)前向量累加和向量盡可能正交的向量進(jìn)行添加，這種正交包含了兩種含義，一種是向量的非零位置向量的正交，另一種是向量本身的正交。

定義4 設(shè)向量V=(v1,v2,…,vn)T∈Rn，則向量I(V)=(i(v1),i(v2),…,i(vn))T∈Rn稱為向量V的非零位置向量，其中

針對(duì)向量累加優(yōu)化問題，初始化S=A1，E1=1，Ei=0，i=2,…,m(Ei=1表示選中Ai，Ei=0表示Ai待處理)。

記J={j|Ej=0}，J**={j|Ej=1}。

正交法算法的步驟為：

步驟1 計(jì)算αj=cos，j∈J；

步驟3 記J*={j|αj=αq,j∈J}，計(jì)算βj=cos，j∈J*；

步驟5 如果S中存在零元素，轉(zhuǎn)步驟1；

步驟6 輸出解Aj，j∈J**，結(jié)束。

步驟1 計(jì)算內(nèi)積αj=(I(S),I(Aj))，j∈J；

步驟3 記J*={j|αj=αq,j∈J}，計(jì)算內(nèi)積βj=(S,Aj)，j∈J*；

步驟5 如果S中存在零元素，轉(zhuǎn)步驟1；

步驟6 輸出解Aj，j∈J**，結(jié)束。

該算法經(jīng)歷一次步驟4，就會(huì)添加一個(gè)向量，由于是有限個(gè)向量，所以步驟6必然會(huì)執(zhí)行到。

3 向量累加優(yōu)化問題在組合測(cè)試中的應(yīng)用

典型的組合測(cè)試有：

(1)兩兩組合測(cè)試，覆蓋任意兩個(gè)參數(shù)的所有取值組合。

(2)三三組合測(cè)試，覆蓋任意3個(gè)參數(shù)的所有取值組合。

(3)二三組合測(cè)試，覆蓋所有參數(shù)的兩兩組合，以及部分參數(shù)的三三組合。

設(shè)有N個(gè)測(cè)試用例Ti，i=1,2,…,N，以規(guī)定的組合要求為元素，形成測(cè)試用例的標(biāo)識(shí)向量Ai。在標(biāo)識(shí)向量Ai中，如果指定的取值組合出現(xiàn)，則對(duì)應(yīng)元素為1，否則為0。由此，組合測(cè)試問題轉(zhuǎn)化為了標(biāo)識(shí)向量Ai的向量累加優(yōu)化問題。

例3：測(cè)試問題2231的測(cè)試用例共12個(gè)，T1=(1,1,1)T,T2=(1,1,2)T,T3=(1,1,3)T,T4=(1,2,1)T,T5=(1,2,2)T,T6=(1,2,3)T,T7=(2,1,1)T，T8=(2,1,2)T，T9=(2,1,3)T,T10=(2,2,1)T,T11=(2,2,2)T,T12=(2,2,3)T,兩兩組合測(cè)試的標(biāo)識(shí)向量設(shè)計(jì)為

A=(δ(t1:1,t2:1),δ(t1:1,t2:2),

δ(t1:2,t2:1),δ(t1:2,t2:2),

δ(t1:1,t3:1),δ(t1:1,t3:2),δ(t1:1,t3:3),

δ(t1:2,t3:1),δ(t1:2,t3:2),δ(t1:2,t3:3),

δ(t2:1,t3:1),δ(t2:1,t3:2),δ(t2:1,t3:3),

δ(t2:2,t3:1),δ(t2:2,t3:2),δ(t2:2,t3:3))T

∈R16

其中

對(duì)應(yīng)的12個(gè)標(biāo)識(shí)向量為

A1=(1,0,0,0,1,0,0,0,0,0,1,0,0,0,0,0)T

A2=(1,0,0,0,0,1,0,0,0,0,0,1,0,0,0,0)T

A3=(1,0,0,0,0,0,1,0,0,0,0,0,1,0,0,0)T

A4=(0,1,0,0,1,0,0,0,0,0,0,0,0,1,0,0)T

A5=(0,1,0,0,0,1,0,0,0,0,0,0,0,0,1,0)T

A6=(0,1,0,0,0,0,1,0,0,0,0,0,0,0,0,1)T

A7=(0,0,1,0,0,0,0,1,0,0,1,0,0,0,0,0)T

A8=(0,0,1,0,0,0,0,0,1,0,0,1,0,0,0,0)T

A9=(0,0,1,0,0,0,0,0,0,1,0,0,1,0,0,0)T

A10=(0,0,0,1,0,0,0,1,0,0,0,0,0,1,0,0)T

A11=(0,0,0,1,0,0,0,0,1,0,0,0,0,0,1,0)T

A12=(0,0,0,1,0,0,0,0,0,1,0,0,0,0,0,1)T

由此，2231的兩兩組合測(cè)試問題轉(zhuǎn)化為了12個(gè)標(biāo)識(shí)向量Ai的向量累加優(yōu)化問題。由剔除法算法求解出的解為{A2,A4,A6,A7,A9,A11}，即T2、T4、T6、T7、T9和T11可滿足兩兩組合覆蓋。

目前有許多兩兩組合算法和三三組合算法，但二三組合算法相對(duì)較少。由向量累加優(yōu)化問題在組合測(cè)試中的應(yīng)用可以看出，無論組合測(cè)試中的何種組合要求，一旦轉(zhuǎn)換為向量累加優(yōu)化問題，其求解算法是一樣的。所以，向量累加優(yōu)化問題在組合測(cè)試中應(yīng)用的優(yōu)勢(shì)在于，它能解決諸如二三組合測(cè)試這樣的特殊要求的組合測(cè)試，當(dāng)然付出的代價(jià)是時(shí)間開銷和資源開銷的增加。

4 數(shù)值實(shí)驗(yàn)

算法采用C語言編程，計(jì)算機(jī)主頻2.33 GHz，內(nèi)存2 GB，操作系統(tǒng)Windows XP。

4.1 兩兩組合測(cè)試的數(shù)值實(shí)驗(yàn)

為了驗(yàn)證向量累加優(yōu)化算法對(duì)兩兩組合覆蓋的測(cè)試用例優(yōu)化能力，選取文獻(xiàn)[7]中的28個(gè)實(shí)驗(yàn)方案進(jìn)行實(shí)驗(yàn)。實(shí)驗(yàn)結(jié)果見表1，表中的“-”項(xiàng)表示因計(jì)算機(jī)資源開銷太大或計(jì)算時(shí)間太長(zhǎng)而未得到計(jì)算結(jié)果。

表1的實(shí)驗(yàn)結(jié)果表明：

表1 與文獻(xiàn)[7]方法的對(duì)比實(shí)驗(yàn)結(jié)果

(1)剔除法的計(jì)算機(jī)資源開銷大、計(jì)算時(shí)間長(zhǎng)，在完成計(jì)算的16個(gè)實(shí)驗(yàn)結(jié)果中，有4個(gè)結(jié)果比文獻(xiàn)[7]中最差的略差，有6個(gè)結(jié)果與文獻(xiàn)[7]中最好的一樣，沒有比文獻(xiàn)[7]中最好的更好的。

(2) 添加法的計(jì)算機(jī)資源和計(jì)算時(shí)間較剔除法有了很大的改善，在完成計(jì)算的25個(gè)實(shí)驗(yàn)結(jié)果中，有4個(gè)結(jié)果比文獻(xiàn)[7]中最差的略差，有12個(gè)結(jié)果與文獻(xiàn)[7]中最好的一樣，有1個(gè)結(jié)果比文獻(xiàn)[7]中最好的更好。

(3)正交法的計(jì)算機(jī)資源和計(jì)算時(shí)間較添加法進(jìn)一步有了很大的改善，在完成計(jì)算的26個(gè)實(shí)驗(yàn)結(jié)果中，有2個(gè)結(jié)果比文獻(xiàn)[7]中最差的略差，有12個(gè)結(jié)果與文獻(xiàn)[7]中最好的一樣，有1個(gè)結(jié)果(序號(hào)9，測(cè)試用例集見表2)比文獻(xiàn)[7]中最好的更好。

表2 正交法針對(duì)表1中序號(hào)9生成的測(cè)試用例集

(4)總體上正交法優(yōu)于添加法，添加法優(yōu)于剔除法。但序號(hào)6和序號(hào)18體現(xiàn)了剔除法優(yōu)于添加法和正交法的結(jié)果，序號(hào)21和序號(hào)22體現(xiàn)了添加法優(yōu)于正交法的結(jié)果。

4.2 三三組合測(cè)試的數(shù)值實(shí)驗(yàn)

為了驗(yàn)證向量累加優(yōu)化算法對(duì)三三組合覆蓋的測(cè)試用例優(yōu)化能力，選取文獻(xiàn)[8]中的4個(gè)實(shí)驗(yàn)方案進(jìn)行實(shí)驗(yàn)。實(shí)驗(yàn)結(jié)果見表3。實(shí)驗(yàn)結(jié)果表明，向量累加優(yōu)化算法整體上明顯優(yōu)于文獻(xiàn)[8]中的方法。在表3中，正交法優(yōu)勢(shì)明顯，但針對(duì)方案4，剔出法得到了優(yōu)于其它方法的較好結(jié)果。針對(duì)方案4，剔除法生成的測(cè)試用例集見表4。

表3 與文獻(xiàn)[8]方法的對(duì)比實(shí)驗(yàn)結(jié)果

表4 剔除法針對(duì)表3中序號(hào)4生成的測(cè)試用例集

4.3 二三組合測(cè)試的數(shù)值實(shí)驗(yàn)

為了驗(yàn)證向量累加優(yōu)化算法對(duì)二三組合覆蓋的測(cè)試用例生成的有效性，選取了6個(gè)實(shí)驗(yàn)方案進(jìn)行實(shí)驗(yàn)，實(shí)驗(yàn)結(jié)果見表5。在表5中，正交法優(yōu)勢(shì)明顯，但針對(duì)方案6，剔出法得到了優(yōu)于其它方法的較好結(jié)果。針對(duì)方案1、方案2、方案3，正交法生成的測(cè)試用例集見表6。針對(duì)方案6，剔除法生成的測(cè)試用例集見表7。

表5 二三組合測(cè)試的實(shí)驗(yàn)結(jié)果

表6 正交法針對(duì)表5中序號(hào)1、2、3生成的測(cè)試用例集

表7 剔除法針對(duì)表5中序號(hào)6生成的測(cè)試用例集

表5、表6和表7的實(shí)驗(yàn)結(jié)果表明：

向量累加優(yōu)化算法能夠方便有效地生成滿足二三組合覆蓋的測(cè)試用例，且優(yōu)化能力強(qiáng)。

5 結(jié)束語

利用向量累加優(yōu)化算法求解組合測(cè)試用例生成問題，其優(yōu)勢(shì)是無論求解何種組合要求的問題，求解算法是一樣的。因此，對(duì)于那些特殊組合要求的組合測(cè)試問題，向量累加優(yōu)化算法提供了行之有效的統(tǒng)一的解決方法。向量累加優(yōu)化算法的劣勢(shì)是時(shí)間和資源的開銷較大，對(duì)規(guī)模非常大的組合測(cè)試問題就顯得無能為力了。

本文給出的向量累加優(yōu)化算法并未考慮向量中1值元素的分布特點(diǎn)，今后可以將向量中1值元素的分布特點(diǎn)引入求解算法之中，通過設(shè)計(jì)針對(duì)性的處理步驟，可能會(huì)使向量累加優(yōu)化算法的優(yōu)化能力得到進(jìn)一步地提升。未來，通過對(duì)向量累加優(yōu)化算法的進(jìn)一步研究，有可能得到優(yōu)化能力更強(qiáng)的新算法，甚至可能針對(duì)某類問題得到求解最優(yōu)解的精確算法。