張毅偉，賁可榮

海軍工程大學(xué) 電子工程學(xué)院，武漢 430033

1 引言

隨著軟件產(chǎn)品的普及及其需求的多樣化，軟件的復(fù)雜性也不斷增加。如何提高軟件質(zhì)量是軟件工程致力于解決的關(guān)鍵問題之一，軟件測試是提高軟件質(zhì)量最重要的手段。隨著面向?qū)ο筌浖_發(fā)的應(yīng)用以及自動化測試的需要，基于模型的軟件測試（model-based software testing）[1]越來越受重視。它無需系統(tǒng)結(jié)構(gòu)的內(nèi)部信息，而是使用系統(tǒng)規(guī)范來派生測試用例。通常使用模型來建立一個系統(tǒng)規(guī)范[2]。

軟件工程的發(fā)展演變也由傳統(tǒng)的模式化轉(zhuǎn)向智能化?；谒阉鞯能浖こ蹋╯earch based software engineering，SBSE）是傳統(tǒng)的軟件工程與智能計算交叉的新的研究領(lǐng)域。它從實際問題的解空間出發(fā)，采用元啟發(fā)式搜索優(yōu)化算法，以適當(dāng)?shù)挠嬎汩_銷來解決可轉(zhuǎn)化為優(yōu)化問題的軟件問題?；谒阉鞯能浖こ桃言谲浖こ填I(lǐng)域取得了顯著的研究成果，尤其是在軟件測試方面的應(yīng)用得到了更多的關(guān)注，促進了軟件測試的發(fā)展。在此背景下，本文針對UML（unified modeling language）模型中依賴遷移難覆蓋的問題，提出一種改進的分組遺傳算法（improved grouping genetic algorithm，IGGA），把UML狀態(tài)圖中的遷移關(guān)系、變量等作為啟發(fā)式信息，搜索生成可執(zhí)行的遷移路徑。對算法的編碼方式以及適應(yīng)度函數(shù)進行設(shè)計，引入自適應(yīng)算子以及模擬退火機制，實驗結(jié)果驗證了本文方法在生成遷移路徑覆蓋率和生成效率方面的有效性。

2 研究背景

2.1 相關(guān)概念

為了解決裝箱問題（bin packing problem，BPP），F(xiàn)alkenauer提出了分組遺傳算法（grouping genetic algorithm，GGA）[3]。BPP是一個非確定性多項式難分組問題，需要將各種尺寸的物品在固定容量的箱子內(nèi)進行分組，并且需要盡可能地利用箱子內(nèi)的空間。GGA是一種將原本呈一列的染色體進行分組處理以適合分組問題結(jié)構(gòu)的一種遺傳算法。GGA與傳統(tǒng)遺傳算法（genetic algorithm，GA）有兩方面不同。

（1）為使分組問題的相關(guān)結(jié)構(gòu)成為染色體中的基因，GGA使用了特殊的編碼方案。個體中的小組都是有意義的組成部分，能夠表示關(guān)于它們所屬解決方案的預(yù)期質(zhì)量信息的最小部分。GGA中染色體表示如下：

[(2 7)(3 8)(1 9)]

（2）鑒于編碼方式的不同，需要使用適合染色體的特殊的遺傳算子。選擇運算使用比例選擇算子，遺傳的可能性與個體適應(yīng)度的概率成正比。交叉操作則是在被選擇的個體中隨機選擇兩個個體作為交叉對象，在染色體的分組間隨機產(chǎn)生交叉點，將一條染色體中兩個交叉點之間的基因插入到另一條染色體中。變異運算的實現(xiàn)取決于面臨的問題，F(xiàn)alkenauer提出的變異操作分為三種：創(chuàng)建一個新分組、刪除一個現(xiàn)有分組、將少量基因在分組之間進行置亂。

基于UML模型的測試是基于模型軟件測試的一個重要方向。在軟件開發(fā)的各個時期，都能使用UML進行設(shè)計，得到規(guī)格說明和測試需求來實現(xiàn)測試的執(zhí)行。基于模型的測試覆蓋準則可以分為[4]：面向控制流的、面向狀態(tài)或遷移的。遷移覆蓋常被作為準則來衡量測試的充分性[5]。一條遷移路徑（transition path，TP）是從狀態(tài)圖的初始狀態(tài)開始的一系列遷移[6]。若一條遷移路徑中的遷移都能按照順序被觸發(fā)執(zhí)行，這就是一條可執(zhí)行的遷移路徑（feasible transition path，F(xiàn)TP）。

狀態(tài)圖中的遷移有時會涉及程序中的變量，且變量的值會影響到后續(xù)遷移的走向。變量的值由遷移中的行為改變。這樣的一組遷移就被稱為依賴遷移組（dependent transition group，DTG）。DTG的存在會導(dǎo)致遷移路徑的不可執(zhí)行。例如遷移a中的動作是i++，遷移b的守衛(wèi)條件是i≥5，若遷移a的執(zhí)行不足5次的話，就難以觸發(fā)遷移b的執(zhí)行。這會使得遷移路徑不能按照輸入序列來執(zhí)行，導(dǎo)致覆蓋率的下降。因此本文考慮將分組遺傳算法應(yīng)用于可執(zhí)行遷移路徑的生成中，并針對具體問題的特性將算法進行設(shè)計調(diào)整。

2.2 相關(guān)工作

針對基于模型的測試，已經(jīng)有多種方法被用來生成遷移路徑。Kalaji等人[7]使用傳統(tǒng)遺傳算法生成遷移路徑，提出了一種基于搜索的集成方法，用于EFSM（extended finite state machine）的自動化測試。該方法分為兩個階段：第一階段使用適應(yīng)度函數(shù)基于數(shù)據(jù)流依賴可行性度量的遺傳算法，來產(chǎn)生可行的TP；第二階段使用適應(yīng)度函數(shù)基于分支近距離函數(shù)的遺傳算法來搜索能夠觸發(fā)TP的輸入序列。但是該方法因為破壞了DTG而導(dǎo)致了路徑的不可行。Hierons等人[8]認為路徑中存在的過渡行為通常會導(dǎo)致不可行的路徑。并提出了一種繞開DTG，通過在遺傳算法中使用評估方法來指導(dǎo)搜索FTP，但是該方法僅能在涉及簡單遷移變量的狀態(tài)圖中適用。Li[4]提出了統(tǒng)一的路徑覆蓋準則體系和面向程序中罕至部分、重點區(qū)域和特定目標(biāo)組的符號執(zhí)行制導(dǎo)策略。該方法能夠針對不同程序取得較好的效果且能有效提高搜索效率。Choi等人[9]將GGA用于遷移路徑的生成，通過對不同系統(tǒng)的實驗取得了較高的遷移覆蓋率。Wu等人[10]提出一種面向路徑的可執(zhí)行遷移路徑生成方法，該方法所生成的路徑能覆蓋被修改影響的節(jié)點。Jungsup等人[11]提出了一種可重用的通用軟件平臺，該軟件框架不僅提供設(shè)計模式來查找目標(biāo)模型的測試用例，還使用常用功能來縮短開發(fā)時間，但是在生成FTP方面，提出的新測試框架難以覆蓋存在DTG的區(qū)域。

GGA已經(jīng)被用在許多領(lǐng)域來解決有關(guān)分組操作的問題。Chen等人[12]應(yīng)用GGA開發(fā)了一種機器選擇模型，來解決并行機床柔性作業(yè)車間調(diào)度問題。Salcedo等人[13]將GGA的遺傳算子進行改進并將其用于解決聚類問題，取得了比傳統(tǒng)方法更好的效果。GGA解決的問題中均包含可以分組的元素，狀態(tài)圖中可執(zhí)行遷移路徑的生成也具備該條件。本文借鑒Falkenauer[3]和Choi等人[9]的思想，針對DTG區(qū)域難覆蓋的問題，提出一種用于生成遷移路徑的改進分組遺傳算法（IGGA）。

3 改進的分組遺傳算法

本章介紹將分組遺傳算法（GGA）進行改進的方法。本文方法主要是針對具有DTG的狀態(tài)圖，對其他狀態(tài)圖同樣適用。下面通過一個具體的狀態(tài)圖（如圖1所示）說明算法的改進工作。GGA具有通過分組來進行交叉操作的特性，需要把特定的標(biāo)記作為分組保護起來?；谀Ｐ偷臏y試能夠在一個DTG上收集數(shù)據(jù)，然后在一個分組里面將DTG綁定。以下針對本文涉及問題的特性，對GGA進行改進。

Fig.1 Example of state diagram圖1 狀態(tài)圖示例

3.1 個體編碼

利用遺傳算法對實際應(yīng)用問題求解時，需要通過編碼將問題的解空間轉(zhuǎn)換為遺傳算法的搜索空間。本文采用對整數(shù)表示的遷移路徑進行分組編碼的方式，進化的個體為若干遷移路徑組成的集合。其中遷移路徑的數(shù)字表示在生成遷移信息表之后用整數(shù)對所有的遷移依次標(biāo)注?；陧樞虻谋硎颈挥米鹘鉀Q可執(zhí)行遷移路徑生成問題的染色體的表現(xiàn)形式。染色體中的基因?qū)?yīng)于經(jīng)過的遷移。個體的編碼如圖2表示。

Fig.2 Chromosome encoding method圖2 個體編碼方式

個體被分為數(shù)個小組，小組中包含基因。用遷移路徑的序號表示路徑，有利于降低個體編碼的復(fù)雜度[14]。本文提出一種原始基因的方式來保護可執(zhí)行遷移序列。初始化染色體之后，分組中創(chuàng)建一個原始基因，原始基因不會被改變。如圖2中三角形所指，首先放置的原始基因被指定為小組號。

當(dāng)進行遺傳操作時，原始基因?qū)团c它們相聯(lián)系的遷移組織在一起。相同組號的分組極有可能包含相似的基因。對不同的小組設(shè)置組號，由不同的組號標(biāo)記染色體中的分組來保持基因的多樣性，有助于提高遷移覆蓋率。原始基因在分組被淘汰前將一直存在個體中并且引導(dǎo)個體分組進化的方向。

3.2 初始化算法

種群初始化過程創(chuàng)建了一個染色體相互作用的環(huán)境，產(chǎn)生與設(shè)定種群大小相同的初始化染色體。本文考慮優(yōu)先將DTG插入小組。初始化從隨機插入基因開始。最先插入的基因為原始基因，記作t′。

若t′的守衛(wèi)條件中包含內(nèi)部變量，則t′就是受影響的遷移。在狀態(tài)圖中搜索另一個包含動作能夠滿足t′守衛(wèi)條件并產(chǎn)生影響的遷移，記為t。搜索到t之后，則分析t中包含的動作和為了到達t′所需要經(jīng)過t的次數(shù)，并在染色體內(nèi)添加所需次數(shù)的t。若t′不存在依賴的遷移t，則此過程中就不添加新基因。搜索t的過程如圖3所示。搜索t從第一級的遷移集合tn1中選擇直接連接到t′的遷移開始。從tn1中尋找的t要包含動作來滿足t′中的條件守衛(wèi)。如果在tn1中沒有找到t，連接到下一級的遷移集合tn2中的遷移就作為備選。以此類推，整個搜索過程不斷深入直至找到t。

種群初始化流程如圖4所示。初始化過程中用到的狀態(tài)圖信息有遷移總數(shù)、遷移集合、遷移信息表、輸入個體中的基因個數(shù)、種群規(guī)模。添加產(chǎn)生影響遷移t的完成標(biāo)志著遷移搜索階段的結(jié)束，隨后在小組中添加隨機基因，直到達到個體的初始長度。個體的初始長度為狀態(tài)圖中的遷移總數(shù)，與達到遷移全覆蓋的最短可執(zhí)行遷移路徑的長度一致。

Fig.3 Search process of generating dependent transition圖3 產(chǎn)生依賴遷移搜索過程

3.3 適應(yīng)度算法

Fig.4 Flow chart of population initialization圖4 種群初始化流程圖

適應(yīng)度是個體對環(huán)境的適應(yīng)程度，它取決于遺傳特性。適應(yīng)度函數(shù)的設(shè)計包括建立一個問題的目標(biāo)以及定義必須被滿足的元素以判斷染色體是否接近最優(yōu)解。通常需要選取相應(yīng)的覆蓋策略來衡量測試的充分性。本文使用遷移覆蓋準則。遷移路徑要盡可能覆蓋更多的遷移。本文研究的適應(yīng)度函數(shù)主要考慮個體滿足狀態(tài)圖遷移覆蓋的程度，基因的關(guān)聯(lián)性也占一定權(quán)重，不具備關(guān)聯(lián)性的遷移路徑將無法執(zhí)行。關(guān)聯(lián)關(guān)系檢測主要是檢查下一次遷移的源狀態(tài)和上一次遷移的目標(biāo)狀態(tài)是否相同。若不一致，則被視為遷移路徑中間斷開，適應(yīng)度值隨之降低。在針對DTG的遷移覆蓋判斷前需要對路徑可行性進行檢查，其中涉及到遷移信息表。

適應(yīng)度函數(shù)如式（1）～式（3）所示：

式中，ω1、ω2表示權(quán)重，ω1>ω2，θ,λ∈[0,1],θ,λ∈Z，θ表示基因間的關(guān)聯(lián)性，λ表示遷移是否被覆蓋，ti表示遷移i，具體評價個體適應(yīng)度的流程如圖5所示。圖5中的fitness增加按照適應(yīng)度函數(shù)進行，種群進化中個體的適應(yīng)度值包括兩方面：

（1）某個體覆蓋遷移越多，則適應(yīng)度值越大；

（2）某個體中基因所代表遷移間的關(guān)聯(lián)性越好，則適應(yīng)度值越大。

Fig.5 Flow chart of fitness evaluation圖5 適應(yīng)度評價流程圖

3.4 遺傳操作算子

種群中的染色體通過遺傳算子來實現(xiàn)相互作用。獲得最優(yōu)解的速度很大程度上依賴對問題設(shè)計遺傳算子的準確性。現(xiàn)有的分組遺傳算法不適用于解決可執(zhí)行遷移路徑的生成問題。本節(jié)針對研究內(nèi)容設(shè)計選擇、交叉、變異和修補四種遺傳算子。

3.4.1 選擇算子

選擇算子用來確定進入下一代的個體，以及產(chǎn)生子代個體的數(shù)量。選擇是一個基于適應(yīng)度值的操作，適應(yīng)度值越高的個體被選擇的概率更大。本文采用輪盤賭法和最優(yōu)保留機制來選擇種群個體。個體傳遞到程序中運行，由適應(yīng)度函數(shù)得到適應(yīng)度值。按適應(yīng)度值將個體由大到小排列，選取一定比例的大適應(yīng)度個體直接加入下一代種群中。剩余個體被選中的概率與其適應(yīng)度值成正比。numns表示種群中未被選中的個體數(shù)量，T表示未被選中的個體，F(xiàn)(T)是適應(yīng)度函數(shù)，T被選中遺傳到下一代群體的概率如式（4）所示：

3.4.2 交叉算子

Fig.6 Process of crossover圖6 個體交叉過程

為了提高種群多樣性，算法的收斂性以及避免形成局部最優(yōu)，本文引入了改進的動態(tài)自適應(yīng)交叉算子[15]，個體兩兩發(fā)生交叉的概率如式（5）所示。

其中，pc1>pc2，f是需要交叉?zhèn)€體的較高的適應(yīng)度值，fmax是剩余個體中適應(yīng)度的最大值，favg是種群適應(yīng)度的平均值。通過這個過程，交叉后的個體中將不存在相同組號的小組，個體可以確保相同基因的重現(xiàn)。交叉后個體的長度問題，將用后文中的修補算子加以限制。

3.4.3 變異算子

交叉操作形成了新的子代個體。若父代個體在某交叉區(qū)域內(nèi)的小組號均相同，則不能產(chǎn)生新的基因型。變異算子是對個體的基因進行變異，從而產(chǎn)生新的個體。Falkenauer提出了3種變異方法，本文將變異操作設(shè)計為淘汰已有小組。

按照一定概率選擇作為變異目標(biāo)的個體隨機地選擇并刪除其中的一個小組。但是當(dāng)個體中小組的數(shù)量少于3個，變異后個體的交叉點形成不了交叉區(qū)域且會降低個體的多樣性。故個體中組數(shù)少于3個就停止變異操作。與交叉算子類似，本文在設(shè)計變異算子時也引入改進的自適應(yīng)變異算子，個體發(fā)生變異的概率如式（6）所示。

對于交叉、變異之后個體，本文應(yīng)用模擬退火算法來接受。當(dāng)產(chǎn)生新個體P′T時，接受其的概率由Metropolis準則確定[16]：若新個體的適應(yīng)度更高，則接受新個體；否則以一定的概率接受質(zhì)量并未提高的新個體，其概率計算如式（7）所示：

式中，fk+1是新個體的適應(yīng)度值；fk是原個體的適應(yīng)度值；tk+1是該算法中的溫度條件控制參數(shù)；ptk+1

是接受概率。

3.4.4 修補算子

針對不同的狀態(tài)圖，滿足遷移覆蓋的遷移路徑的長度不同。遷移的重復(fù)執(zhí)行也可能導(dǎo)致個體長度的不斷增長。選取一個長度值Len對個體進行限制。若交叉、變異操作后的個體長度與Len不一致，則需要對個體進行修補，具體如算法1所示。

算法1修補算子

輸入：染色體中基因數(shù)numg、染色體中小組數(shù)numgp、個體長度限制Len。

輸出：修補后的個體chromosome。

長于Len的個體，先刪除與前后不關(guān)聯(lián)的基因。若基因均相關(guān)，則隨機刪去一個小組。雖然基因是相關(guān)聯(lián)的，但是由于已覆蓋路徑的重插入，導(dǎo)致個體很長卻不能確保覆蓋率。組號不同的小組可能覆蓋了相同的區(qū)域。為此本文采用一種在刪除完成之后，隨機刪除分組的修補方法。刪除一些已經(jīng)存在的分組能夠為新元素騰出更多的空間，讓染色體中的小組能夠覆蓋不同的區(qū)域。短于Len的個體，尋找不關(guān)聯(lián)的基因，并在一個基因之后加入能與其相關(guān)聯(lián)的基因。若基因均關(guān)聯(lián)，則在個體末尾加入關(guān)聯(lián)基因，直至長度達到Len為止。

以上是本文對GGA的改進，將遷移編號作為基因并為每個小組設(shè)置組號，通過組號的異同判別個體是否覆蓋相同區(qū)域。通過搜索狀態(tài)圖的原始信息初始化種群。評價適應(yīng)度時考慮覆蓋率與關(guān)聯(lián)關(guān)系兩項，給出了適應(yīng)度函數(shù)公式。將輪盤賭法與最優(yōu)保留機制結(jié)合來選擇個體，利用GGA不同的交叉變異方式進行遺傳操作，引入自適應(yīng)的遺傳算子以及模擬退火的接受機制以提高求解速度，最后針對個體的長度問題提出了相應(yīng)的修補算子。

4 遷移路徑生成

由以上改進的算法，可以得出基于IGGA的可執(zhí)行遷移路徑的生成框架，分為狀態(tài)圖分析模塊和算法模塊。狀態(tài)圖分析模塊是對圖的遷移結(jié)構(gòu)進行分析，生成3.2節(jié)、3.3節(jié)中提到的遷移信息表。以圖1為例，遷移信息表如表1所示。

Table1 Information of transitions表1 遷移信息表

每一次迭代以后都會產(chǎn)生新個體作為下一輪迭代的初始種群。需要的迭代次數(shù)通常意味著算法優(yōu)化的收斂狀態(tài)。算法模塊根據(jù)遷移信息表進行相應(yīng)的操作。本文是以生成的符合條件的染色體為最優(yōu)解，同時以是否達到算法預(yù)定的最大迭代次數(shù)為終止條件?；贗GGA算法生成可執(zhí)行遷移路徑具體的流程步驟如圖7所示。

Fig.7 Flow chart of FTP generate based on IGGA圖7 基于IGGA的可執(zhí)行路徑遷移生成流程圖

具體步驟如下：

步驟1由狀態(tài)圖生成遷移信息表。

步驟2設(shè)置初始化的參數(shù)，包括種群規(guī)模、最大遺傳代數(shù)Gen、交叉概率pc、變異概率pm等參數(shù)。

步驟3由3.1節(jié)所述的編碼方式和3.2節(jié)所述的初始化方法，產(chǎn)生初始種群Pop。

步驟4使用3.3節(jié)中的算法計算適應(yīng)度值。

步驟5檢查是否滿足終止條件：個體適應(yīng)度值為(Len-1)ω1+ω2Len或是達到設(shè)定的遺傳代數(shù)，若滿足條件，則轉(zhuǎn)到步驟10。

步驟6對種群中個體按照3.4節(jié)中的方法進行選擇。

步驟7對剩余個體使用交叉和變異算子進行自適應(yīng)的交叉和變異操作。

步驟8將新產(chǎn)生的個體根據(jù)3.4節(jié)中所提操作修補至長度Len，產(chǎn)生新的種群集合Pop′。

步驟9重復(fù)執(zhí)行步驟4至步驟8，若達到一定遺傳代數(shù)Gen，則Len+1，并進行下一輪迭代。

步驟10停止遺傳操作，輸出滿足的個體及其覆蓋率。

5 實驗與分析

為分析討論算法參數(shù)和驗證算法的有效性，本文的實驗分為兩部分：5.1節(jié)以inres initiator協(xié)議和ATM兩個系統(tǒng)為例，比較本文設(shè)計的算法與文獻[7]、文獻[9]、文獻[11]中方法在生成可執(zhí)行遷移路徑（FTP）上的覆蓋率；5.2節(jié)通過比賽判定系統(tǒng)（game winner check，GWC）、警報系統(tǒng)（alert system，AS）、錯誤等級檢測系統(tǒng)（fault level check，F(xiàn)LC）三個狀態(tài)圖為例，與文獻[9]中方法比較生成同樣數(shù)量的FTP所需要的遺傳代數(shù)，通過結(jié)果分析本文方法的性能，觀察其在加快求解速度方面的效果。

文中進行的實驗程序使用Matlab語言編寫，并在MatlabR2015a中運行。實驗的硬件配置為2.50 GHz Intel?CoreTMi5-3210M CPU、4 GB 內(nèi)存，安裝了Microsoft Windows 7 32 bit操作系統(tǒng)的計算機。

在進行上述實驗之前，本文引入文獻[16]中狀態(tài)圖的結(jié)構(gòu)復(fù)雜度對于狀態(tài)圖理解的影響來分析每一級個體長度搜索代數(shù)的因素。其使用狀態(tài)圖中的簡單狀態(tài)的數(shù)量（number of simple state，NS）、圈復(fù)雜度（cyclomatic complexity，CC）、遷移的數(shù)量（number of transition，NT）來定量表示狀態(tài)圖結(jié)構(gòu)的復(fù)雜度，圈復(fù)雜度定義為|NS-NT+2|[17]。本文將元素分別設(shè)置為實驗組和對比組，觀察其對搜索代數(shù)的影響。在實驗結(jié)果的基礎(chǔ)上，對于某一狀態(tài)圖，所需要的遺傳代數(shù)Gen可以近似表示為式（8），其中α是比例權(quán)重。在總體流程中，若某長度Len的個體搜索滿Gen次，則將個體長度Len+1，并進行下一個迭代周期。

本文還研究交叉概率pc、變異概率pm、種群大小Popsize對于總的遺傳代數(shù)G以及個體長度Len的影響，并得出針對示例狀態(tài)圖的最優(yōu)遺傳參數(shù)。

5.1 算法覆蓋率實驗分析

為了驗證本文算法生成FTP的有效性，本節(jié)將以inres initiator協(xié)議和ATM兩個系統(tǒng)實例，將本文算法運行結(jié)果與文獻[7]、文獻[9]、文獻[11]中方法的結(jié)果作比較。兩個系統(tǒng)的狀態(tài)圖如圖8和圖9所示。為了簡化，原圖中的事件均用en表示，遷移用tn表示，只表示出涉及依賴遷移組（DTG）的守衛(wèi)條件和行為。inres initiator和ATM是典型的包含DTG的系統(tǒng)。ATM狀態(tài)圖中，t2、t3、t4包含變量attempt的判別條件，t2中包含引起變量attempt值變化的行為，故t2、t3、t4構(gòu)成了DTG。inres initiator協(xié)議狀態(tài)圖中，t3、t8、t10包括變量counter判別的守衛(wèi)條件和變量counter加1的行為，t4、t9、t11中包括變量counter的判別守衛(wèi)條件，故t3、t4、t8、t9、t10、t11構(gòu)成了DTG。實驗所取的遺傳參數(shù)如表2所示。

Table2 Genetic parameters of experiment表2 實驗所取遺傳參數(shù)

在上述兩個系統(tǒng)UML模型的基礎(chǔ)上，利用給定的遺傳參數(shù)生成可執(zhí)行的遷移路徑，4種方法的區(qū)別在于：文獻[7]使用原始的遺傳算法（GA）；文獻[9]使用分組遺傳算法（GGA）；文獻[11]采用一種新的測試框架MISF（model-independent software framework）；本文采用改進的分組遺傳算法（IGGA），并引入自適應(yīng)遺傳算子與模擬退火接受機制，生成遷移路徑的覆蓋率如表3所示。

Table3 Comparison of transition path coverage表3 生成遷移路徑覆蓋率結(jié)果比較

由表3可以看出，對于上述兩個系統(tǒng)狀態(tài)圖使用本文方法能夠達到100%的遷移覆蓋，相比于使用傳統(tǒng)遺傳算法分別提高了4.16%和25%，相比于使用MISF分別提高了20.48%和33.33%，與采用GGA的覆蓋率持平。本文使用的IGGA將DTG保護在個體的遺傳分組中，使得其依賴關(guān)系不被破壞，從而能夠達到難覆蓋的遷移路徑。使用GGA的種群規(guī)模均是80，本文使用IGGA時，種群規(guī)模分別減小了25%和12.5%，說明IGGA能夠在縮小種群大小的前提下達到相同的遷移覆蓋效果。本節(jié)實驗中IGGA與GGA達到的覆蓋率效果相同，將在5.2節(jié)中實驗分析比較本文的IGGA與GGA在生成遷移路徑時所需代數(shù)等方面的差別。

Fig.8 ATM state diagram圖8 ATM系統(tǒng)狀態(tài)圖

Fig.9 Inres initiator system state diagram圖9 Inres initiator系統(tǒng)狀態(tài)圖

5.2 算法性能實驗分析

為驗證本文改進遺傳算法的性能，本節(jié)以文獻[9]中的比賽判定系統(tǒng)（GWC）、警報系統(tǒng)（AS）、錯誤等級檢測系統(tǒng)（FLC）三個狀態(tài)圖為例，比較IGGA和GGA在生成遷移路徑時的收斂速度。上述三個系統(tǒng)狀態(tài)圖如圖10～圖12所示。同樣依照前文所述方法，所取的遺傳參數(shù)如表4所示。本節(jié)的三個系統(tǒng)狀態(tài)圖均包含依賴遷移組，且其中依賴變量的值在不斷增大，這也使得生成可執(zhí)行遷移路徑的難度逐漸變大。

根據(jù)表4的遺傳參數(shù)和采用文獻[9]中的實驗規(guī)模進行實驗，對每個狀態(tài)圖生成500條遷移路徑。實驗結(jié)果比較如表5所示。

由表5可以看出，對三個系統(tǒng)狀態(tài)圖進行實驗，本文方法由于引入了自適應(yīng)的遺傳算子和模擬退火的接受機制從而加快了收斂的速度。在生成相同數(shù)量可執(zhí)行遷移路徑的前提下，所需的迭代次數(shù)分別減少了14.33%、16.41%、19.66%，生成的遷移路徑長度基本相同。另外，從這個結(jié)果也可以看出對于難覆蓋的遷移路徑越長的系統(tǒng)狀態(tài)圖，本文方法求解速度的提高也越明顯。綜上所述，使用IGGA生成遷移路徑的方法無論是在遷移覆蓋率還是種群規(guī)模都具有優(yōu)勢，引入的自適應(yīng)遺傳算子和接受機制有效加速了算法的優(yōu)化進度，使其具有更好的尋優(yōu)性能。

Fig.10 GWC system state diagram圖10GWC系統(tǒng)狀態(tài)圖

Fig.11 AS system state diagram圖11 AS系統(tǒng)狀態(tài)圖

Fig.12 FLC system state diagram圖12 FLC系統(tǒng)狀態(tài)圖

Table4 Genetic parameters of experiment表4 實驗所取遺傳參數(shù)表

Table5 Comparison of experiment results of transition path表5 生成遷移路徑實驗結(jié)果比較

6 結(jié)束語

本文利用分組遺傳算法中分組的思想將依賴遷移組歸到一起，通過對編碼方式和適應(yīng)度函數(shù)的設(shè)計，使得生成的遷移路徑能夠覆蓋依賴遷移組。引入了自適應(yīng)的遺傳算子并用模擬退火機制接受交叉后的個體，對每次迭代后得到的個體進行修補，使其滿足搜索規(guī)則。實驗分析了狀態(tài)圖結(jié)構(gòu)對遺傳代數(shù)的影響，討論了遺傳參數(shù)對算法性能的影響，對比實驗驗證了本文方法達到了遷移覆蓋的有效性，結(jié)果表明本文方法能夠在生成相同數(shù)量可執(zhí)行遷移路徑的前提下縮小種群規(guī)模及迭代次數(shù)，具有更好的尋優(yōu)性能。

本文進一步的工作是能否引入新的搜索策略，進一步提高效率，如何自動生成相應(yīng)的測試數(shù)據(jù)來觸發(fā)遷移路徑的執(zhí)行，將本文方法通過參數(shù)調(diào)節(jié)等方式應(yīng)用于除考慮事件之外的更加復(fù)雜的情形。這些也是基于模型自動化測試中需要繼續(xù)研究的內(nèi)容。