馮 霞 郝慧敏

?

基于遺傳算法的IMX系統(tǒng)測試數(shù)據(jù)自動生成研究

馮 霞①②郝慧敏*①

①(中國民航大學(xué)計算機科學(xué)與技術(shù)學(xué)院 天津 300300)②(中國民航大學(xué)中國民航信息技術(shù)科研基地 天津 300300)

利用遺傳算法進行測試數(shù)據(jù)自動生成是近年來的研究熱點，其有效性高度依賴于適應(yīng)度函數(shù)的選取和初始種群的篩選。該文探索將遺傳算法應(yīng)用到IMX(Integrated Management X-software)系統(tǒng)測試數(shù)據(jù)自動生成以提高其回歸測試的質(zhì)量，將IMX系統(tǒng)專業(yè)測試人員手動生成的測試數(shù)據(jù)作為基礎(chǔ)測試數(shù)據(jù)，并提出一種基于測試路徑對目標(biāo)路徑覆蓋率的初始種群篩選標(biāo)準(zhǔn)。在三角形程序和IMX系統(tǒng)平臺上的實驗表明，所提方法在尋找測試數(shù)據(jù)時所用的時間和迭代次數(shù)較少，且生成的測試數(shù)據(jù)具有較好的多樣性。

測試數(shù)據(jù)自動生成；遺傳算法；初始種群篩選；適應(yīng)度函數(shù)；IMX系統(tǒng)

1 引言

IMX(Integrated Management X-software)系統(tǒng)是一套用于管理航空公司運行質(zhì)量和安全審計的軟件，系統(tǒng)的研發(fā)能夠幫助航空公司提升運營質(zhì)量和安全性能。IMX系統(tǒng)開發(fā)周期非常短，每隔一周就需要提交一個新版本，更新速度極快，因而對回歸測試的頻度和效率要求極高。這就要求開發(fā)團隊采取邊開發(fā)邊測試的策略，在頻繁修改代碼的同時完成測試工作。

遺傳算法是一種通過模擬自然進化過程搜索最優(yōu)解的智能算法，近年來利用遺傳算法實現(xiàn)高效測試數(shù)據(jù)自動生成，進而提高回歸測試效率的研究越來越受到關(guān)注。文獻[1]為提高測試效率，利用遺傳算法生成大量測試數(shù)據(jù)進行測試覆蓋，保證了較高的測試故障覆蓋率[2]。文獻[3]將遺傳算法應(yīng)用在復(fù)雜、多條件約束的軟件系統(tǒng)中，解決手工生成測試數(shù)據(jù)效率低下問題。文獻[4]在遺傳算法的基礎(chǔ)上動態(tài)地將稀有數(shù)據(jù)撲捉，調(diào)整權(quán)重增加稀有數(shù)據(jù)的適應(yīng)值，進而提高測試數(shù)據(jù)的生成效率。

考慮到不同初始種群和適應(yīng)度函數(shù)對算法有效性會產(chǎn)生直接影響[5]，文獻[6]針對并行程序利用基于合作式的協(xié)同進化遺傳算法實現(xiàn)覆蓋目標(biāo)路徑的測試數(shù)據(jù)自動生成，并對子種群和合并種群采用不同的適應(yīng)度函數(shù)評估。文獻[7]通過對基本適應(yīng)度函數(shù)的修正，采用自適應(yīng)適應(yīng)度函數(shù)避免了遺傳算法陷入早熟現(xiàn)象，提高了算法的搜索能力。文獻[8]采用遺傳算法生成回歸測試所需數(shù)據(jù)，通過計算測試路徑與目標(biāo)路徑的相似度來篩選初始種群，利用已有測試數(shù)據(jù)所含有利信息來優(yōu)化種群，提高遺傳算法的運行效率。

總結(jié)以上研究，現(xiàn)有學(xué)者在利用遺傳算法實現(xiàn)測試數(shù)據(jù)自動生成時仍需解決的主要問題有：(1)針對不同的應(yīng)用，學(xué)者們提出了不同的適應(yīng)度函數(shù)，可見適應(yīng)度函數(shù)是高度依賴于數(shù)據(jù)集的。針對某一特定系統(tǒng)，如何選擇合適的適應(yīng)度函數(shù)仍然值得研究；(2)有效利用初始數(shù)據(jù)的有用信息可以提高算法的效率，如何針對測試的需求及數(shù)據(jù)集自身的特點，進而設(shè)定合理的篩選標(biāo)準(zhǔn)來更好地優(yōu)化數(shù)據(jù)，是另一個值得研究的問題。

本文研究遺傳算法在IMX系統(tǒng)測試數(shù)據(jù)自動生成中的應(yīng)用，主要貢獻為：(1)將IMX系統(tǒng)專業(yè)測試人員手動生成的測試數(shù)據(jù)作為基礎(chǔ)測試數(shù)據(jù)，有效利用了IMX測試人員的豐富經(jīng)驗。(2)提出一種基于路徑覆蓋率的初始種群篩選標(biāo)準(zhǔn)，在三角形程序和IMX系統(tǒng)程序中進行實驗，有效驗證了該方法在較少時間和迭代次數(shù)內(nèi)即可實現(xiàn)測試數(shù)據(jù)的自動生成。(3)針對IMX系統(tǒng)選擇出有效的適應(yīng)度函數(shù)計算方法，即分支距離與層接近度之和。

2 基于遺傳算法的測試數(shù)據(jù)生成

2.1 問題分析

遺傳算法是一種結(jié)合了生物學(xué)中自然選擇和遺傳學(xué)中生物進化的計算模型，可應(yīng)用在數(shù)學(xué)中以解決最優(yōu)化問題，最初由美國Michigan大學(xué)Holland教授于1975年首次提出。由于遺傳算法搜索最優(yōu)解的求解空間和自動測試數(shù)據(jù)生成的問題空間模型相似，所以越來越多的學(xué)者將遺傳算法用作測試數(shù)據(jù)自動生成來提高回歸測試的效率。

本文旨在研究IMX系統(tǒng)中基于遺傳算法的單目標(biāo)路徑測試數(shù)據(jù)生成問題。該問題可描述為：

(1)選取IMX系統(tǒng)中的一個核心程序；

采用遺傳算法解決IMX系統(tǒng)測試數(shù)據(jù)自動生成，需要將問題建模成最優(yōu)化問題。

將測試數(shù)據(jù)代入到程序中運行得出的路徑稱為測試路徑，這里把測試路徑與目標(biāo)路徑的接近程度作為該測試路徑的適應(yīng)度，記為,。根據(jù)適應(yīng)度函數(shù)，就可以為測試數(shù)據(jù)自動生成問題建立式(1)，式(2)最小化或最大化模型：

2.2初始種群篩選

利用遺傳算法實現(xiàn)測試數(shù)據(jù)自動生成時，初始種群的不同設(shè)定對算法性能產(chǎn)生極大影響，利用有效的篩選標(biāo)準(zhǔn)來優(yōu)化初始種群，可以增強算法的搜索能力，從而提高測試數(shù)據(jù)自動生成的效能。

2.2.1初始種群與算法性能 遺傳算法的種群是一代一代演化的，且當(dāng)前代的個體僅與上一代個體相關(guān)，與其之前所有個體無關(guān)[9]。遺傳算法的這一特征可用定義1描述。

文獻[10,11]在論述初始種群與遺傳算法性能關(guān)系時，給出了定義2和定理1：

定理1說明交叉算子可搜索到包含當(dāng)代種群中極小模式的所有個體，但無法搜索到不在極小模式中的全部個體。定理1反應(yīng)了交叉算子的搜索能力，同時表明，初始種群對交叉算子的搜索能力具有較強的決定性作用[12]；而遺傳算法的收斂速度依賴于交叉操作。由此可見，初始種群選擇對遺傳算法的收斂性能非常關(guān)鍵，且在實際應(yīng)用中，不合理的初始種群選擇，會增加算法的迭代次數(shù)，甚至?xí)顾阉鹘Y(jié)果陷入局部最優(yōu)，降低算法性能。

綜上，通過選用有效篩選標(biāo)準(zhǔn)，選取充分表征解空間個體信息的初始種群，就可增加交叉算子的搜索能力，進而減少進化代數(shù)和收斂時間，提高算法性能。

2.2.2篩選標(biāo)準(zhǔn) 利用一定的篩選標(biāo)準(zhǔn)對回歸測試中已有測試數(shù)據(jù)進行篩選，可以充分利用已有測試數(shù)據(jù)所含有用信息，從而提高測試數(shù)據(jù)生成的效率[13]。但不同的篩選標(biāo)準(zhǔn)，生成的測試數(shù)據(jù)效能差異很大，因此研究選擇適用于IMX系統(tǒng)的篩選標(biāo)準(zhǔn)對系統(tǒng)的測試非常重要。

IMX系統(tǒng)是基于白盒測試中的路徑覆蓋展開的測試，好的測試數(shù)據(jù)應(yīng)該覆蓋到盡可能多的節(jié)點路徑，因此本文提出根據(jù)路徑的覆蓋率來篩選初始種群。

按式(3)計算每個測試數(shù)據(jù)的路徑覆蓋率，并將其求和后計算均值得出測試數(shù)據(jù)的平均路徑覆蓋率，將大于或等于平均路徑覆蓋率的所有個體篩選出來，作為初始種群的部分個體，若篩選出的個體數(shù)量不足于預(yù)定義的初始種群數(shù)量，則其余個體將在被測程序所對應(yīng)的輸入域范圍內(nèi)隨機產(chǎn)生[8]。即滿足式(4)：

2.3適應(yīng)度函數(shù)選擇

針對IMX系統(tǒng)，本文分析比較了如下4種不同適應(yīng)度計算方法。

(1)分支距離+層接近度(方法1) 利用文獻[14]和文獻[15]提出的適應(yīng)度函數(shù)設(shè)計，即適應(yīng)度函數(shù)為分支距離與層接近度的兩者之和，且分支距離是被規(guī)范到(0,1)之間的一個數(shù)，這樣有效降低了分支距離和層接近度之間的落差。該方法中的適應(yīng)度值越小，表示越接近目標(biāo)路徑，因此應(yīng)該選取適應(yīng)度值較小的個體作為后續(xù)迭代的數(shù)據(jù)。

(2)分支距離(方法2) 對分支距離的計算，文獻[16]提出了一種新的設(shè)計方法，其基本設(shè)計思想是將初始的分支距離除以自身與常數(shù)的和(常數(shù)大于0)。將該分支距離作為適應(yīng)度函數(shù)時表示為

(3)層接近度(方法3) 對于層接近度方法的計算也有多種，本文采用文獻[5]中提到的計算方法，即統(tǒng)計測試路徑未覆蓋目標(biāo)路徑的節(jié)點的個數(shù)，記作，將該值除以目標(biāo)路徑的節(jié)點的個數(shù)。將其作為適應(yīng)度函數(shù)，則計算公式為

(4)擬合度(方法4) 采用測試路徑與目標(biāo)路徑的擬合度作為適應(yīng)度函數(shù)。將測試路徑和目標(biāo)路徑按節(jié)點序列匹配的方法計算出的子路徑記為。計算公式如式(7)[6,17]：

2.4 算法步驟

根據(jù)以上研究，利用遺傳算法實現(xiàn)測試數(shù)據(jù)自動生成的步驟如下：

(1)初始化所有參數(shù)；

(2)根據(jù)一定篩選標(biāo)準(zhǔn)對基礎(chǔ)數(shù)據(jù)進行選擇，將滿足標(biāo)準(zhǔn)的數(shù)據(jù)作為初始種群；

(3)判斷是否滿足算法停止條件，是則算法停止并輸出結(jié)果，否則執(zhí)行步驟(4)；

(4)采用輪盤賭方法對初始種群進行選擇操作；

(5)對上述選擇出的個體進行單點交叉操作；

(6)將未覆蓋目標(biāo)路徑的節(jié)點對應(yīng)的輸入變量進行變異操作；

(7)是否滿足最大(最小)適應(yīng)度函數(shù)或最大迭代次數(shù)，是則輸出結(jié)果，否則繼續(xù)迭代。

3 實驗

3.1 IMX系統(tǒng)被測程序

對于IMX系統(tǒng)，所選的被測程序為審計(audit)模塊中的審計狀態(tài)(audit)變化過程，即航空公司在進行審計時，根據(jù)符合項和不符合項的狀態(tài)，審計狀態(tài)發(fā)生相應(yīng)變化的流程。其中，審計狀態(tài)包括SCHEDULED, CONDUCTED, READY FOR CLOSURE, CLOSED。

表1 測試數(shù)據(jù)信息

audit的各個狀態(tài)轉(zhuǎn)換如圖1所示。

圖1 audit狀態(tài)轉(zhuǎn)換

程序修改條件語句由if(findingQty<= unconformityQty||findingOKQty

3.2 三角形程序

三角形程序主要功能是根據(jù)三條邊的大小來判斷三角形所屬類別。程序修改條件語句由if((a= =b) ||(a==c)||(b==c))變?yōu)閕f((a==b && b!=c)||(a==c && c!=b)||(b==c && a!=c))，因此，所選取的目標(biāo)路徑應(yīng)包含修改節(jié)點，目標(biāo)路徑為：三角形類別是等腰三角形。

3.3實驗參數(shù)設(shè)置

在利用遺傳算法生成測試數(shù)據(jù)時，采用ASCII碼編碼，輪盤賭選擇策略，并采用單點交叉(Pc=0.8)和單點變異(Pm=0.2)，實驗中最大迭代次數(shù)均為1000次，運行次數(shù)均為20。

初始種群規(guī)模與算法解空間大小相關(guān)，且直接影響到遺傳算法的收斂性或計算效率。種群規(guī)模過小，則易早熟，從而過早收斂；過大則會耗費大量的資源，代價增高。通常，可根據(jù)實際情況在10~200之間選定[18]，也可選取4~6個，其中為被測程序中參數(shù)的個數(shù)[19]。

為確定初始種群規(guī)模的大小，本文分別選取種群規(guī)模為10,20,40,50,80,160, 在IMX系統(tǒng)上進行了實驗驗證。

種群規(guī)模(P)與收斂時間(T)和收斂代數(shù)(GEN)關(guān)系如圖2，圖3所示。

圖2表明隨著種群不斷增多，算法的收斂時間逐漸增大，當(dāng)種群規(guī)模為40到80之間時，時間先減小，隨后又呈上升趨勢。由圖3可知，算法的收斂代數(shù)會隨著初始種群規(guī)模的不斷增加而逐漸降低，最后趨于平緩。可見，選擇過小或過大的種群規(guī)模會降低算法的性能[5]。因此，針對IMX系統(tǒng)，本文選擇初始種群規(guī)模為50。

3.4不同篩選標(biāo)準(zhǔn)實驗

3.4.1 IMX系統(tǒng)程序 將本文2.2節(jié)的路徑覆蓋率篩選標(biāo)準(zhǔn)、文獻[8]中相似度篩選標(biāo)準(zhǔn)以及傳統(tǒng)方法三者進行比較。其中，傳統(tǒng)方法是指在利用遺傳算法生成測試數(shù)據(jù)時，對已有的測試數(shù)據(jù)隨機選擇作為算法的初始種群，并未充分利用基礎(chǔ)數(shù)據(jù)含有的有用信息。

算法停止條件為滿足設(shè)定的適應(yīng)度值和最大迭代次數(shù)。本次實驗中選取層接近度與分支距離結(jié)合作為遺傳算法的適應(yīng)度函數(shù)。不同篩選標(biāo)準(zhǔn)實驗結(jié)果如表2所示。

圖2 收斂時間和種群規(guī)模關(guān)系 圖3 收斂代數(shù)均值和種群規(guī)模關(guān)系

表2初始數(shù)據(jù)數(shù)量為50的篩選標(biāo)準(zhǔn)比較

實驗次數(shù)路徑覆蓋率篩選標(biāo)準(zhǔn)相似度篩選標(biāo)準(zhǔn)傳統(tǒng)方法 1(READY_FOR, 150, 45, 74, 50, 29)(READY_FOR, 90, 30, 20, 11, 7)(READY_FOR, 12, 2, 4, 2, 2)(READY_FOR, 84, 0, 23, 20, 14) 2(READY_FOR, 50, 10, 23, 0, 0)(READY_FOR, 50, 40, 10, 9, 9)(READY_FOR, 28, 0, 5, 5, 1) 3(READY_FOR, 12, 2, 10, 9, 9)(READY_FOR, 12, 2, 10, 9, 9)(READY_FOR, 23, 1, 5, 3, 2) 4(READY_FOR, 50, 40, 10, 9, 9)(READY_FOR, 50, 40, 10, 9, 9)(READY_FOR, 76, 9, 29, 22, 0) 5(READY_FOR, 50, 40, 5, 4, 3)(READY_FOR, 50, 40, 10, 9, 9)(READY_FOR, 51, 15, 17, 6, 4) 6(READY_FOR, 12, 2, 10, 9, 9)(READY_FOR, 12, 2, 10, 9, 9)(READY_FOR, 75, 32, 42, 26, 16) 7(READY_FOR, 41, 2, 22, 10, 2)(READY_FOR, 50, 40, 5, 4, 4)(READY_FOR, 41, 2, 22, 10, 2) 8(READY_FOR, 50, 40, 10, 9, 9)(READY_FOR,50, 40, 10, 9, 9)(READY_FOR, 50, 23, 19, 10, 3) 9(READY_FOR, 86, 28, 43, 31, 20)(READY_FOR, 12, 2, 10, 9, 9)(READY_FOR, 43, 1, 9, 7, 1) 10(READY_FOR, 50, 10, 17, 0, 0)(READY_FOR, 12, 2, 10, 9, 9)(READY_FOR, 70, 35, 35, 35, 25) 11(READY_FOR, 50, 40, 10, 9, 9)(READY_FOR, 12, 2, 10, 9, 9)(READY_FOR, 54, 11, 10, 8, 8) 12(READY_FOR, 90, 30, 54, 14, 9)(READY_FOR, 50, 40, 10, 9, 9)(READY_FOR, 12, 2, 10, 9, 9)(READY_FOR, 86, 28, 43, 31, 21) 13(READY_FOR, 80, 37, 37, 31, 15)(READY_FOR, 90, 30, 58, 37, 20)(READY_FOR, 50, 10, 18, 0, 0)(READY_FOR, 50, 40, 10, 9, 9)(READY_FOR, 92, 24, 19, 10, 1) 14(READY_FOR, 23, 1, 5, 3, 1)(READY_FOR, 80, 20, 56, 31, 6)(READY_FOR, 54, 30, 23, 19, 19) 15(READY_FOR, 54, 30, 23, 19, 19)(READY_FOR, 50, 40, 10, 9, 9)(READY_FOR, 80, 37, 37, 31, 15) 16(READY_FOR, 50, 40, 7, 6, 0)(READY_FOR, 50, 40, 9, 5, 2)(READY_FOR, 12, 2, 10, 9, 9)(READY_FOR, 39, 0, 8, 8, 7) 17(READY_FOR, 48, 20, 22, 19, 3)(READY_FOR, 150, 45, 102, 20, 5)(READY_FOR, 65, 22, 30, 26, 26) 18(READY_FOR, 50, 40, 10, 9, 9)(READY_FOR, 12, 2, 10, 9, 9)(READY_FOR, 36, 13, 22, 22, 14) 19(READY_FOR, 50, 40, 6, 6, 3)(READY_FOR, 12, 2, 10, 9, 9)(READY_FOR, 29, 1, 21, 13, 6) 20(READY_FOR, 12, 2, 10, 9, 9)(READY_FOR, 12, 2, 10, 9, 9)(READY_FOR, 86, 46, 35, 24, 23) 時間均值(s)0.1620.1660.321 迭代均值(次)4.4004.700211.150

通過上述實驗可以看出：(1)傳統(tǒng)的遺傳算法需要消耗0.321 s，迭代211.150次才可找到測試數(shù)據(jù)?？梢妭鹘y(tǒng)遺傳算法的效率較為低下。(2)相似度方法和路徑覆蓋率方法在時間和迭代次數(shù)上相差不多，且該值遠遠小于傳統(tǒng)方法對應(yīng)值。但是通過相似度方法篩選的測試數(shù)據(jù)失去了多樣性，找到相同數(shù)據(jù)次數(shù)較多，而路徑覆蓋率方法提高了測試數(shù)據(jù)的多樣性。(3)隨著測試數(shù)據(jù)的增多，利用路徑覆蓋率篩選標(biāo)準(zhǔn)生成測試數(shù)據(jù)時所需的時間和迭代次數(shù)將均少于相似度方法，本文方法的優(yōu)勢逐漸凸顯。

3.4.2三角形程序?qū)嶒炘O(shè)置 為驗證2.2節(jié)所提方法的可靠性和普遍性，同時將其應(yīng)用在對三角形程序的測試上。由于是回歸測試，所以已經(jīng)具有一些可以覆蓋原來三角形程序所對應(yīng)目標(biāo)路徑的測試數(shù)據(jù)。對于傳統(tǒng)方法，是隨機選取已有的測試數(shù)據(jù)作為算法的初始種群，對于路徑覆蓋率篩選標(biāo)準(zhǔn)和相似度篩選標(biāo)準(zhǔn)來說，則是分別利用對應(yīng)篩選標(biāo)準(zhǔn)選取符合要求的數(shù)據(jù)作為初始種群的一部分，其余個體則是在輸入域內(nèi)隨機產(chǎn)生。

適應(yīng)度函數(shù)選用層接近度與分支距離之和計算。實驗結(jié)果如表3所示。

表3三角形程序?qū)嶒灡容^

評價指標(biāo)路徑覆蓋率篩選標(biāo)準(zhǔn)相似度篩選標(biāo)準(zhǔn)傳統(tǒng)方法 時間均值(s)0.4750.8171.032 迭代均值(次)57.800448.600660.850

由以上實驗可知，本文方法所用的時間和迭代次數(shù)均為最小，且在100次以內(nèi)就可找到覆蓋目標(biāo)路徑的測試數(shù)據(jù)，效率極高。而相似度篩選標(biāo)準(zhǔn)方法和傳統(tǒng)方法，需消耗很多時間和迭代次數(shù)，且存在找不到覆蓋目標(biāo)路徑測試數(shù)據(jù)的現(xiàn)象。由此足以證明本文方法的有效性。

3.5 不同適應(yīng)度函數(shù)實驗

采用2.3節(jié)中介紹的方法應(yīng)用在IMX系統(tǒng)上進行對比。以路徑覆蓋率準(zhǔn)則對初始種群進行篩選。實驗結(jié)果如表4所示。

表4不同適應(yīng)度函數(shù)性能比較

評價指標(biāo)方法1方法2方法3方法4 時間均值(s)0.1620.4140.3152.439 迭代均值(次)4.70038.20020.600754.400

由上實驗得出，在利用遺傳算法進行測試數(shù)據(jù)生成時，選取不同的適應(yīng)度函數(shù)指標(biāo)對數(shù)據(jù)生成的效率有很大影響。對于IMX系統(tǒng)來說，方法4所需時間是方法1的15倍之多，且迭代次數(shù)也遠遠超過了方法1，效率非常低下。方法2和方法3相對于方法4，效率得到了很大提高，但迭代過程中每次都會產(chǎn)生大量的覆蓋率為0.0%的無用數(shù)據(jù)。采用方法1時需要最少的時間和迭代次數(shù)，且產(chǎn)生的測試數(shù)據(jù)具有較好的多樣性，多數(shù)數(shù)據(jù)的覆蓋率都能達到90.0%以上，大大增強了測試的效率。由此可知，對于IMX系統(tǒng)，應(yīng)將分支距離與層接近度之和作為遺傳過程中適應(yīng)度函數(shù)的評價指標(biāo)。

4 結(jié)束語

為提高對IMX系統(tǒng)的測試效率，本文采用遺傳算法實現(xiàn)回歸測試中測試數(shù)據(jù)的自動生成。針對不同的初始種群篩選標(biāo)準(zhǔn)和適應(yīng)度函數(shù)對測試數(shù)據(jù)有效性的影響進行了研究，并提出了路徑覆蓋率篩選標(biāo)準(zhǔn)，在IMX系統(tǒng)核心程序和三角形類別判定程序中的實驗表明，本文方法在生成測試數(shù)據(jù)時所需時間和迭代次數(shù)均較少。進而又通過對多種不同適應(yīng)度函數(shù)計算方法的比較實驗，選取了分支距離與層接近度之和作為IMX系統(tǒng)的適應(yīng)度度量方法。

[1] Swain S and Mohapatra D P. Genetic Algorithm-Based Approach for Adequate Test Data Generation[M]. India: Intelligent Computing, Networking, and Informatics, Springer, 2014: 453-462.

[2] 鄺繼順, 劉杰鏜, 張亮. 基于鏡像對稱參考切片的多掃描鏈測試數(shù)據(jù)壓縮方法[J]. 電子與信息學(xué)報, 2015, 37(6): 1513-1519.

Kuang Ji-shun, Liu Jie-tang, and Zhang Liang. Test data compression method for multiple scan chain based on mirror-symmetrical reference slices[J].&, 2015, 37(6): 1513-1519.

[3] Michael C C, McGraw G E, Schatz M A,.. Genetic algorithms for dynamic test data generation[C]. Proceedings of the 12th IEEE International Conference on Automated Software Engineering, 1997: 307-308.

[4] 張巖, 鞏敦衛(wèi). 基于稀有數(shù)據(jù)撲捉的路徑覆蓋測試數(shù)據(jù)進化生成方法[J]. 計算機學(xué)報, 2013, 36(12): 2429-2440.

Zhang Yan and Gong Dun-wei. Evolutionary generation of test data for paths coverage based on scarce data capturing[J]., 2013, 36(12): 2429-2440.

[5] 劉向輝, 韓文報, 權(quán)建. 基于遺傳策略的格基約化算法[J]. 電子與信息學(xué)報, 2013, 35(8): 1940-1945.

Liu Xiang-hui, Han Wen-bao, and Quan Jian. A new lattice reduction algorithm based on genetic strategy[J].&, 2013, 35(8): 1940-1945.

[6] Tian T and Gong D. Test data generation for path coverage of message-passing parallel programs based on co-evolutionary genetic algorithms[J]., 2014, 22(79): 1-32.

[7] 嚴(yán)韜, 陳建文, 鮑拯. 基于改進遺傳算法的天波超視距雷達二維陣列稀疏優(yōu)化設(shè)計[J]. 電子與信息學(xué)報, 2014, 36(12): 3014-3020.

Yan Tao, Chen Jian-wen, and Bao Zheng. Optimization design of sparse 2-D arrays for Over-The-Horizon Readar (OTHR) based on improved genetic algorithm[J].&, 2014, 36(12): 3014-3020.

[8] 鞏敦衛(wèi), 任麗娜. 回歸測試數(shù)據(jù)進化生成[J] . 計算機學(xué)報, 2014, 37(3): 489-499.

Gong Dun-wei and Ren Li-na. Evolutionary genetation of regression test data[J]., 2014, 37(3): 489-499.

[9] 曹凱, 陳國虎, 江樺, 等. 自適應(yīng)引導(dǎo)進化遺傳算法[J]. 電子與信息學(xué)報, 2014, 36(8): 1884-1890.

Cao Kai, Chen Guo-hu, Jiang Hua,. Guided self-adaptive evolutionary genetic algorithm[J].&, 2014, 36(8): 1884-1890.

[10] 徐宗本, 高勇. 遺傳算法過早收斂現(xiàn)象的特征分析及其預(yù)防[J]. 中國科學(xué): E 輯, 1996, 26(4): 364-375.

Xu Zong-ben and Gao Yong. The analysis and prevention of genetic algorithm premature convergence[J].(), 1996, 26(4): 364-375.

[11] Suzuki J. A Markov chain analysis on simple genetic algorithms[J]., 1995, 25(4): 655-659.

[12] 何大闊, 王福利, 賈明興. 遺傳算法初始種群與操作參數(shù)的均勻設(shè)計[J]. 東北大學(xué)學(xué)報: 自然科學(xué)版, 2005, 26(9): 828-831.

He Da-kuo, Wang Fu-li, and Jia Ming-xing. Uniform design of initial population and operation parameters of genetic algorithm[J].(), 2005, 26(9): 828-831.

[13] Xuan J and Monperrus M. Test case purification for improving fault localization[C]. FSE 2014 Proceedings of the 22nd ACM SIGSOFT International Symposium on Foundations of Software Engineering, New York, NY, USA, 2014: 52-63.

[14] McMinn P. Evolutionary search for test data in the presence of state behaviour[D]. [Master dissertation], University of Sheffield, 2005: 1-242.

[15] Harman M and McMinn P. A theoretical and empirical study of search-based testing: local, global, and hybrid search[J]., 2010, 36(2): 226-247.

[16] Arcuri A. It does matter how you normalise the branch distance in search based software testing[C]. Proceedings of the 3rd International Conference on Software Testing, Verification and Validation, Pairs, France, 2010: 205-214.

[17] Xie X Y, Xu B W, Shi L,.. Genetic test case generation for path-oriented testing[J]., 2009, 20(12): 3117-3136.

[18] 雷英杰, 等. MATLAB 遺傳算法工具箱及應(yīng)用[M]. 西安: 西安電子科技大學(xué)出版社, 2005: 60-61.

Lei Ying-jie,.. Application of Genetic Algorithm ToolBox Based on MATLAB[M]. Xian: Xidian University Publisher, 2005: 60-61.

[19] 劉曉霞. 種群規(guī)模對遺傳算法性能影響的研究[D]. [碩士論文], 華北電力大學(xué), 2010: 1-37.

Liu Xiao-xia. A research on population aize impaction on the performance of genetic algorithm[D]. [Master dissertation], North China Electric Power University, 2010: 1-37.

Research on Automatic Generation of Test Data in MX Based on Genetic Algorithms

Feng Xia①②Hao Hui-min①

①(,,300300,)②(,,300300,)

Using genetic algorithms to generate test data automatically is becoming a hot topic in recent years, the method on effectively generating data is highly dependent on choosing the proper fitness function and the selecting standard. The genetic algorithm is used on Integrated Management X-software (IMX) system to help it improve the quality of regression test. Those basic test data used in this paper are taken from the data that generated by professional testers in IMX, and an initial population selecting standard is proposed based on the coverage. Experiments on IMX and triangle program show that the proposed algorithm is more effective than others, for example, with less time and iteration the method can find the testing data correctly, especially on data variety.

Test data generation; Genetic algorithm; Initial population selecting; Fitness function; Integrated Management X-software (IMX) system

TP311

A

1009-5896(2015)10-2501-07

10.11999/JEIT150291

2015-03-09；改回日期：2015-06-15；

2015-07-27

郝慧敏 1048866836@qq.com

國際航空運輸協(xié)會(IATA)項目(70003418)和國家科技支撐計劃(2014BAJ04B02)

The International Air Transport Association Fund (70003418); The National Key Technology Research and Development Program of the Ministry of Science and Technology of China (2014BAJ04B02)

馮 霞： 女，1970年生，教授，博士，主要研究方向為數(shù)據(jù)挖掘和民航智能信息處理研究.

郝慧敏： 女，1990年生，碩士生，研究方向為數(shù)據(jù)挖掘和民航智能信息處理研究.