段嘉奇,林明達,周 晴

(1.復(fù)雜航天系統(tǒng)電子信息技術(shù)重點實驗室(中國科學(xué)院國家空間科學(xué)中心),北京 100190; 2.中國科學(xué)院大學(xué),北京 100049)

軟件系統(tǒng)復(fù)雜性日益增加,手動創(chuàng)建測試用例效率低,難以滿足測試要求,自動生成測試用例無疑對提高軟件測試效率具有重要意義。擴展有限狀態(tài)機(extended finite state machine,EFSM)是一種可同時攜帶控制流和數(shù)據(jù)流信息的軟件描述模型,常用于基于模型的軟件測試用例的自動生成[1-2]。在EFSM測試用例生成過程中,需要首先生成測試序列再生成測試數(shù)據(jù),因此快速地生成高質(zhì)量的測試序列是自動化測試用例生成的關(guān)鍵。然而,高性能自動化測試序列集生成算法需同時滿足以下條件:1)測試序列集內(nèi)每個序列均是可行的;2)測試序列集滿足全遷移覆蓋;3)測試序列集規(guī)模小;4)測試序列生成算法效率高。這對自動化測試序列生成任務(wù)提出了挑戰(zhàn)。因此,本文開展了快速生成小規(guī)模測試序列集算法的研究。

遺傳算法(genetic algorithm,GA)作為目前較為流行的啟發(fā)式搜索算法,可用于求解遷移覆蓋的測試序列生成問題。文獻[3-5]首次提出了一種有效生成可行遷移路徑的方法,該方法根據(jù)控制流和數(shù)據(jù)流的依賴關(guān)系評估路徑的可行性,針對模型中的每一條遷移,通過多次執(zhí)行GA算法指導(dǎo)路徑的搜索。雖能以較高概率生成可行遷移路徑,但對于具有“計數(shù)器變量問題”的路徑,僅是采取了“繞過”的策略,因此最終生成的測試序列集無法滿足全遷移覆蓋。針對該問題,文獻[6-7]利用分組遺傳算法,通過綁定依賴計數(shù)器變量的遷移,使生成的序列集很好地滿足了全遷移覆蓋,但由于生成單個序列的計算量較大,算法整體運算效率較低。文獻[8]提出了一種先利用圖遍歷搜索算法得到滿足控制流的候選序列集,再篩選滿足數(shù)據(jù)流序列的方法,該方法生成的測試序列集存在冗余序列,導(dǎo)致測試序列集規(guī)模較大。文獻[9-10]利用多目標搜索算法,綜合考慮了序列的可行性和遷移覆蓋率,以及序列集的規(guī)模,但過多的優(yōu)化目標也降低了成功搜索到最優(yōu)解的概率。文獻[11-12]通過引入種群多樣性度量方法增加個體間差異,壓縮了測試序列集規(guī)模,但仍存在因早熟收斂導(dǎo)致的無法滿足全遷移覆蓋的問題,且僅是在種群初始化階段就要生成大量的可行遷移路徑,極大增加了算法的時間開銷。自適應(yīng)多種群遺傳算法可有效克服傳統(tǒng)遺傳算法早熟收斂和搜索能力弱的缺陷,如文獻[13-14]根據(jù)種群多樣性自適應(yīng)調(diào)整交叉和變異算子,一定程度上克服了早熟問題,文獻[15-16]通過引入多種群機制并行搜索,加快了收斂速度等,但將自適應(yīng)多種群遺傳算法應(yīng)用在EFSM測試序列生成問題上的研究較少。

針對以上問題,本文嘗試將改進的自適應(yīng)多種群遺傳算法(improved adaptive multi-population genetic algorithm,IAMGA)應(yīng)用到EFSM測試序列生成問題中,意在探索一種面向全遷移的一次性快速生成較小規(guī)模的測試序列集方法。為了使測試序列集更好地滿足全遷移覆蓋,引入多種群機制,以增加種群的多樣性;為了提高序列集生成效率,引入自適應(yīng)方法,根據(jù)種群進化程度動態(tài)地調(diào)整交叉和變異概率;為了壓縮序列集規(guī)模,先正向生成能產(chǎn)生遷移增益的可行序列,再反向去除未產(chǎn)生增益的冗余序列。經(jīng)實驗驗證,IAMGA算法在不同EFSM模型下,均能以較高的成功率生成滿足全遷移覆蓋的小規(guī)模測試序列集。

1 EFSM模型

1.1 EFSM模型描述與符號定義

EFSM可形式化地表示為一個六元組M=(S,s0,I,O,V,T),其中S為一組有限狀態(tài)集合;s0為模型的初始狀態(tài)(s0∈S);I為輸入集合;O為輸出集合;V為內(nèi)部變量的有限集合;T為遷移集合。遷移集合T的每個遷移變量t可以用一個五元組表示(ss,i,g,Oop,se),其中ss為t的源狀態(tài);i為輸入(i∈I);g為守衛(wèi),是當前變量的謂詞判定條件,可以為空,也可以是一個邏輯表達式的集合;Oop為該遷移觸發(fā)后的一系列操作,由輸出語句、變量賦值語句組成;se為t的目的狀態(tài)。

為便于說明,對EFSM模型中的相關(guān)術(shù)語作出如下規(guī)定和解釋:

定義1遷移路徑(transition path,TP):可能生成的測試序列,由若干個遷移組成的但無法被EFSM模型成功執(zhí)行的遷移路徑,表示為TP=(t1,t2,…,ti,tj,…,tn),其中ti的目的狀態(tài)是tj的源狀態(tài)。

定義2可行遷移路徑(feasible transition path,FTP):生成的測試序列,由若干個遷移組成的且可被EFSM模型成功執(zhí)行的遷移路徑,表示為FTP=(t1,t2,…,ti,tj,…,tn),t1的源狀態(tài)是模型的初始狀態(tài),tn的目的狀態(tài)是模型的終止狀態(tài),且至少存在一組測試數(shù)據(jù),能觸發(fā)該序列中的所有遷移。

定義3可行遷移路徑集合(feasible transition path set,FTPS):生成的測試序列集,由若干個FTP組成的集合,表示為FTPS=(FTP1,FTP2,…,FTPm),其中m表示生成的測試序列集的規(guī)模。

定義4遷移覆蓋增益:TP中含有未覆蓋遷移集合中的遷移在未覆蓋遷移集合中的占比。

定義5冗余序列:FTPS中相對于其他FTP未能產(chǎn)生遷移覆蓋增益的序列。

1.2 EFSM測試序列生成問題分析

為保證EFSM測試序列生成的效率和質(zhì)量,需考慮以下方面:1)序列的可行性;2)測試序列集的遷移覆蓋率;3)測試序列集的規(guī)模。以當前較為典型的EFSM模型——ATM[17]為例,對EFSM測試序列生成問題進行分析,ATM模型見圖1。

圖1 ATM模型

1.2.1 序列可行性分析

由于EFSM模型中含有控制流信息和數(shù)據(jù)流信息,因此在生成測試序列時,既要考慮有向圖中的可行性,又要考慮遷移間的數(shù)據(jù)流依賴。當一個序列中的兩個遷移上的動作和謂詞判定之間存在矛盾,即無法找到滿足謂詞條件的輸入時,該序列是不可行的。如圖1中的一條測試序列TP1=(t1,t4,t5,t7,t11,t15,t9,t23),遷移t5對變量l的賦值操作為l=′e′,而t11的謂詞判定條件為l=′s′,則此時二者發(fā)生沖突,導(dǎo)致TP1不可行。在進行測試序列生成時,應(yīng)避免產(chǎn)生存在遷移沖突的測試序列。

1.2.2 序列集覆蓋性分析

為保證測試的充分性,常采用全遷移覆蓋(all transitions coverage,ATC)準則指導(dǎo)測試序列生成。然而,在EFSM模型中存在一類問題——“計數(shù)器變量問題”,影響了序列集的遷移覆蓋率。如圖1中一條包含計數(shù)器變量a的測試序列FTP1=(t1,t2,t2,t2,t3),由于遷移t3的謂詞判定條件為a=3,需執(zhí)行3次t2才能觸發(fā)t3,概率為1/8,而觸發(fā)t4的概率為7/8。因此在一般情況下,含有被計數(shù)器變量觸發(fā)遷移的FTP的生成難度更大。

1.2.3 序列集規(guī)模分析

測試序列集中的冗余序列會導(dǎo)致測試效率下降。如圖1中的測試序列FTP2=(t1,t2,t4,t5,t23)、FTP3=(t1,t2,t4,t6,t23)和FTP4=(t1,t4,t6,t7,t9,t23),可知FTP3為冗余序列,因為FTP3不能對FTP2和FTP4所包含的遷移集合產(chǎn)生遷移覆蓋增益,因此在測試時,只需測試FTP2和FTP4即可,不需要測試FTP3。

1.3 序列可行性度量方法

為模擬被測系統(tǒng)的動態(tài)行為,利用transitions工具包[18]建立EFSM可執(zhí)行模型,根據(jù)控制流信息定義模型的狀態(tài)和遷移,根據(jù)數(shù)據(jù)流信息定義綁定在遷移上的條件約束和行為。為判斷被EFSM模型執(zhí)行的TP是否為FTP,需對序列的可行性進行度量,序列可行性度量方法如下:

Step1初始化EFSM模型的變量和狀態(tài),在模型中動態(tài)執(zhí)行TP中的遷移。

Step2判斷當前遷移是否滿足數(shù)據(jù)流約束,若變量的當前值符合當前遷移的謂詞判定條件,則執(zhí)行Step3,否則執(zhí)行Step4。

Step3判斷當前遷移是否滿足控制流約束,若滿足,則將模型的當前狀態(tài)設(shè)為當前遷移的目的狀態(tài),執(zhí)行遷移上綁定變量的更新等操作,再將當前遷移設(shè)為TP中的下一個遷移,執(zhí)行Step2。若不滿足,則執(zhí)行Step4。

Step4若模型當前狀態(tài)為“exit”,則將該TP作為FTP加入到FTPS中;否則直接返回第一個不可行遷移的位置。

2 IAMGA算法

2.1 種群初始化

為直觀地表示測試序列和EFSM模型中遷移的邏輯關(guān)系,采用符號編碼,符號集代表EFSM模型中的遷移集合,一個基因位代表一個遷移,個體代表一個可能生成的序列。為簡化研究問題,個體長度固定為符號集大小。

種群采用隨機初始化的方式,假定個體長度為L,種群規(guī)模為N,從符號集中隨機選擇L個遷移組成一個個體,并重復(fù)上述操作N次,完成種群初始化。

2.2 適應(yīng)度函數(shù)

適應(yīng)度函數(shù)用于評估TP與FTP的接近程度。大多數(shù)測試序列生成任務(wù)的目標僅是生成滿足全遷移覆蓋的測試序列集,因此很多研究在設(shè)計適應(yīng)度函數(shù)時只考慮了遷移覆蓋率,這存在兩點問題:1)具有較高遷移覆蓋率的個體未必具有較高的路徑通過率,難以進化為FTP,導(dǎo)致全局收斂速度下降;2)具有較高遷移覆蓋率的個體進化為FTP后,未必能對測試序列集的遷移覆蓋率產(chǎn)生增益,這將導(dǎo)致測試序列集規(guī)模增加。針對以上問題,為提高全局收斂速度引入了個體的路徑通過率,為減小測試序列集規(guī)模引入了個體的遷移覆蓋增益。

(1)

個體的遷移覆蓋增益Gn(i)可表示為

(2)

(3)

2.3 選擇算子

選擇算子用于在種群進化過程中保留適應(yīng)度較高的個體,淘汰適應(yīng)度較低的個體。然而,傳統(tǒng)GA的選擇算子針對整個種群進行選擇,這會使種群多樣性變差,導(dǎo)致“早熟”問題。針對該問題,本文通過改進傳統(tǒng)的多種群遺傳算法(multi-population genetic algorithm,MGA),將其應(yīng)用在測試序列生成任務(wù)的選擇過程中。

圖3實例演示了某代種群的選擇過程。首先根據(jù)個體的可行遷移將整個種群劃分為若干個子種群,使可行遷移完全相同的個體組成一個子種群,在每個子種群內(nèi)使用輪盤賭選擇法對個體進行選擇,不同子種群的選擇操作互不影響。個體被選擇的概率P(i)可表示為

圖3 選擇過程

(4)

式中:M為子種群規(guī)模,f(i)為個體的適應(yīng)度函數(shù)。

2.4 交叉算子

交叉算子用于個體間基因重組以推動種群進化。在測試序列生成任務(wù)中,該過程對應(yīng)于TP通過彼此間交換遷移,以逐步收斂為FTP。然而,傳統(tǒng)GA的交叉算子通常存在以下問題:1)交叉概率是固定的,不能動態(tài)地反映不同種群進化階段對交叉的需求;2)交叉的基因位是隨機的,不能有效提高后代個體的適應(yīng)度。

(5)

式中:N為種群規(guī)模,γp(i)為個體的路徑通過率。

針對問題2,為了簡化問題,僅是針對由序列可行性度量所反饋的第一個不可行遷移進行交叉,即只是考慮基因位的交叉,而不考慮基因片段的交叉。

此外,種群進化后期基因多樣性變差,為克服迭代過程中無效的交叉操作對運算效率的影響,引入了交叉進化函數(shù)fc(k),用于度量種群的進化停滯程度。交叉進化函數(shù)fc(k)由正弦函數(shù)經(jīng)三角平移變換后得到,可表示為

(6)

式中:k為距離上一次產(chǎn)生FTP所經(jīng)歷的種群迭代次數(shù),τ為進化停滯代數(shù)的門限。

因此,種群內(nèi)每個個體的交叉概率Pc可表示為

(7)

為避免“近親繁殖”,選取不同子種群的個體進行交叉。圖4實例演示了某次交叉過程。對于個體i,交叉點C1為第一個不可行遷移的位置。首先,隨機選擇一個與i在不同子種群的個體j,分別計算出兩個體的路徑通過率γp(i)、γp(j)。然后,比較γp(i)和γp(j),若γp(i)≥γp(j),認為個體i的進化程度較高,已經(jīng)包含了個體j的可行遷移,因此從個體j的不可行遷移中隨機選擇一個交叉點C2;反之,若γp(i)<γp(j),認為個體j的進化程度較高,選擇個體j中的可行遷移能使個體i有效進化,因此從個體j的可行遷移中隨機選擇一個交叉點C2。最后,將C1與C2的基因位進行交換。

圖4 交叉過程

2.5 變異算子

變異用于個體內(nèi)基因突變以豐富種群多樣性。在測試序列生成任務(wù)中,當TP無法通過交叉進化時,則從符號集中隨機選擇遷移,以加速進化為FTP。本文對變異算子的設(shè)計與交叉算子類似。變異進化函數(shù)fm(k)可表示為

(8)

式中:k為距離上一次產(chǎn)生FTP所經(jīng)歷的種群迭代次數(shù),τ為進化停滯代數(shù)的門限。

由式(8)可知,fm(k)與fc(k)在[0,τ]區(qū)間內(nèi)關(guān)于τ/2對稱,即fc(k)+fm(k)=1(k>0)。

因此,種群內(nèi)每個個體的變異概率Pm可表示為

(9)

圖5實例演示了某次變異過程。對于個體i,變異點M1為第一個不可行遷移的位置,并從符號集中隨機選擇一個遷移替換M1的基因位。

圖5 變異過程

2.6 算法過程

算法流程見圖6。具體步驟如下:

圖6 IAMGA算法流程圖

Step1對種群進行初始化。

Step2根據(jù)序列可行性度量方法,將生成的FTP加入到FTPS中。判斷當前FTPS是否滿足ATC,若滿足,則執(zhí)行Step7,否則執(zhí)行Step3。

Step3判斷當前種群代數(shù)是否達到最大迭代次數(shù),若未達到,則執(zhí)行Step4,否則算法結(jié)束。

Step4根據(jù)個體的可行遷移將整個種群劃分為若干個子種群,在各子種群內(nèi)計算所有個體的個體適應(yīng)度,并使用輪盤賭選擇法對個體進行選擇。

Step5根據(jù)式(7)計算個體的交叉概率,若滿足交叉條件,則采用交叉策略對不同子種群間的個體進行交叉操作。

Step6根據(jù)式(9)計算個體的變異概率,若滿足變異條件,則采用變異策略對個體進行變異操作。種群個體全部更新完成后,返回Step2。

Step7倒序遍歷生成的測試序列集并壓縮規(guī)模,若該測試序列產(chǎn)生遷移覆蓋增益,則保留;否則將其剔除。遍歷完成后,得到最終的測試序列集。

由以上過程可知,IAMGA算法生成的測試序列集沒有冗余序列,證明過程見表1。

表1 測試序列集不存在冗余序列的證明

3 實驗驗證與分析

實驗選取2種典型的具有“計數(shù)器變量問題”的模型ATM模型和Cashier模型[19],并將全遷移覆蓋成功率、滿足全遷移覆蓋的測試序列集規(guī)模和收斂時的迭代次數(shù)作為評價指標,對IAMGA算法的有效性和性能進行分析和驗證,實驗參數(shù)設(shè)置見表2。

表2 實驗參數(shù)設(shè)置

3.1 算法有效性驗證與分析

為驗證IAMGA算法的有效性,分別在8組不同的種群規(guī)模下對2種模型各實驗100次,仿真結(jié)果見圖7和圖8,具體統(tǒng)計結(jié)果見表3和表4。

表3 不同種群規(guī)模下的統(tǒng)計結(jié)果(ATM)

圖7 不同種群規(guī)模下的仿真結(jié)果(ATM)

圖8 不同種群規(guī)模下的仿真結(jié)果(Cashier)

圖7為ATM模型的仿真結(jié)果。由圖7(a)可知,在不同種群規(guī)模下的平均遷移覆蓋率均能達到95%以上,但當種群規(guī)模為250時,不同實驗的遷移覆蓋率分布較為分散。由圖7(b)可知,當種群規(guī)模在500以上時,全遷移覆蓋成功率可達80%以上;當種群規(guī)模在750以上時,全遷移覆蓋成功率可達90%以上;當種群規(guī)模在1 500以上時,全遷移覆蓋成功率可達到100%。由圖7(c)可知,不同種群規(guī)模下所生成的測試序列集規(guī)模都在5～6之間,差異較小;種群規(guī)模越大,生成的測試序列集規(guī)模的平均值也越大;當種群規(guī)模在1 000以下時,可搜索到達到最小測試序列集規(guī)模的序列組合。由圖7(d)可知,不同種群規(guī)模下達到收斂時迭代次數(shù)的平均值分布在100～400之間,且隨著種群規(guī)模增加,達到收斂時的迭代次數(shù)也隨之減小。

圖8為Cashier模型的仿真結(jié)果。由圖8(a)可知,在不同種群規(guī)模下的平均遷移覆蓋率均能達到95%以上,但當種群規(guī)模為250時,相對于ATM模型分布更加集中。由圖8(b)可知,當種群規(guī)模在1 000以上時,全遷移覆蓋成功率可達90%以上,但均無法達到100%。由圖8(c)可知,不同種群規(guī)模下所生成的測試序列集規(guī)模也都在5～6之間,差異較小;種群規(guī)模越大,生成的測試序列集規(guī)模的平均值也越大;在不同種群規(guī)模下均可搜索到達到最小測試序列集規(guī)模的序列組合。由圖8(d)可知,不同種群規(guī)模下達到收斂時迭代次數(shù)的平均值分布在150～300之間,且隨著種群規(guī)模增加,達到收斂時的迭代次數(shù)同樣也隨之減小。

由以上仿真結(jié)果和分析知,在選取適當?shù)姆N群規(guī)模的條件下,IAMGA算法在2種模型上均能以較高的全遷移覆蓋成功率生成較小規(guī)模的測試序列集,且均能搜索到最小測試序列集規(guī)模的序列組合。但IAMGA算法在2種模型上的表現(xiàn)存在差異,需對其進一步分析。

表3和表4分別給出了全遷移覆蓋成功率達到80%以上的未覆蓋遷移的統(tǒng)計結(jié)果。可知Cashier模型未覆蓋的遷移全部為屬于“計數(shù)器變量問題”的遷移t15,而ATM模型未覆蓋的遷移除了具有“計數(shù)器變量問題”的遷移t3,還有具有“并聯(lián)關(guān)系”的遷移組合{t11,t12}、{t19,t20}等。由ATM和Cashier的模型圖可知,相比于ATM模型,Cashier模型的“計數(shù)器變量問題”位置更深,算法搜索到越深位置的路徑時,由于種群規(guī)模一定,而子種群數(shù)量變多,因此子種群的規(guī)模變小,導(dǎo)致在選擇個體時,具有“計數(shù)器變量問題”的個體更難被選到。同理,ATM模型具有“并聯(lián)關(guān)系”的遷移組合的位置更深,因此當種群規(guī)模較小時,具有較深的“并聯(lián)關(guān)系”遷移的個體很難被選到。

此外,相較于ATM模型,Cashier模型更加簡單,因此在同一種群規(guī)模下收斂時的平均迭代次數(shù)更小。由于種群規(guī)模越大,單次迭代的計算量越多,因此應(yīng)根據(jù)不同的模型和任務(wù)類型,選擇合適的種群規(guī)模。

3.2 算法性能對比與分析

為驗證IAMGA算法的性能優(yōu)勢,選取AGA[20]、MGA[21]、AMGA[22]算法進行對比,各算法的實現(xiàn)方式及對比維度見表5,實驗參數(shù)設(shè)置與表2一致。根據(jù)上文分析結(jié)論,將種群規(guī)模設(shè)為1 000,分別使用4種算法對2種模型實驗100次。為盡可能減少種群初始化的隨機性對結(jié)果的影響,提前緩存100個隨機初始化的種群,以保證每次實驗各算法的初始種群相同。仿真結(jié)果見圖9和圖10,具體統(tǒng)計數(shù)據(jù)見表6和表7。

表5 各算法實現(xiàn)方式

表6 各算法性能仿真結(jié)果對比(ATM)

表7 各算法性能仿真結(jié)果對比(Cashier)

圖10 各算法性能對比(Cashier)

圖9為ATM模型的仿真結(jié)果。由圖9(a)可知,AGA算法的遷移覆蓋率均未達到100%,全遷移覆蓋的成功率為0。而IAMGA算法的全遷移成功率高達97%,未滿足全覆蓋的3次實驗的遷移覆蓋率也在90%以上,均優(yōu)于AGA算法。這是因為AGA算法未使用多種群策略,進化過程中種群多樣性逐漸變差,最終導(dǎo)致“早熟”;由圖9(b)可知,MGA算法的平均迭代次數(shù)為250,最小迭代次數(shù)為100。而IAMGA算法的平均迭代次數(shù)192,最小迭代次數(shù)為66,均優(yōu)于MGA算法。這是因為MGA算法未使用自適應(yīng)方法,交叉和變異的概率未能適應(yīng)種群的進化程度,導(dǎo)致收斂速度變慢;由圖9(c)可知,在遷移覆蓋率較低時,IAMGA算法的收斂速度略優(yōu)于MGA算法,而在遷移覆蓋率較高時,IAMGA算法的收斂速度明顯優(yōu)于MGA算法。這是因為在種群進化初期,兩種算法的交叉概率均較高,因此種群進化速度差異較小,而在種群進化后期,IAMGA算法的變異概率遠大于MGA算法,因此種群進化速度更快;由圖9(d)可知,AMGA算法生成的測試序列集規(guī)模全部在9～16之間,而IAMGA算法生成的測試序列集規(guī)模全部在3～8之間,這是因為IAMGA算法優(yōu)先選擇了能夠產(chǎn)生遷移覆蓋增益的個體,并通過對結(jié)果集倒序遍歷,保證了集合內(nèi)兩兩序列之間均能產(chǎn)生遷移覆蓋增益,有效去除了未產(chǎn)生遷移覆蓋增益的冗余序列。

圖10為Cashier模型的仿真結(jié)果。由圖10可知,各算法在Cashier模型上的表現(xiàn)與ATM結(jié)果相似,因此均可得出類似的分析結(jié)論,這表明IAMGA算法在不同模型上的性能均優(yōu)于其他3種算法。

表6和表7分別為ATM模型和Cashier模型的仿真結(jié)果統(tǒng)計。由表6可知,在ATM模型上,與AGA算法相比,IAMGA算法的平均遷移覆蓋率提高了134%;與MGA算法相比,IAMGA算法的平均迭代次數(shù)減少了23%;與AMGA算法相比,IAMGA算法的測試序列集平均規(guī)模減少了52%。由表7可知,在Cashier模型上,與AGA算法相比,IAMGA算法的平均遷移覆蓋率提高了54%;與MGA算法相比,IAMGA算法的平均迭代次數(shù)減少了20%;與AMGA算法相比,IAMGA算法的測試序列集平均規(guī)模減少了48%。因此,相比于以往的遺傳算法,IAMGA在遷移覆蓋率、收斂速度、序列集規(guī)模等方面的性能均有所提升。

4 結(jié) 論

1)對EFSM測試序列生成問題進行了分析,提出了IAMGA算法,根據(jù)遷移覆蓋增益設(shè)計了適應(yīng)度函數(shù),引入多種群機制改進了選擇過程,引入自適應(yīng)機制改進了交叉變異過程,最后通過回溯去除冗余序列壓縮了測試序列集規(guī)模。

2)仿真結(jié)果表明,與傳統(tǒng)遺傳算法相比,IAMGA算法能以90%以上的成功率生成滿足全遷移覆蓋的測試序列集,生成的測試序列集規(guī)模減小了50%,收斂速度提升了20%。本文提出的測試序列生成方法可有效提高EFSM測試序列集生成的效率和質(zhì)量。