基于遺傳算法的測(cè)試用例生成方法基于遺傳算法的測(cè)試用例生成方法#E1>=E2E2-E1<=E1<E2E1-E2<E1<=E2E1-E2<=E仁=E2abs(E1-E2)==E1!=E2-abs(E1-E2)<由表可知，當(dāng)分支謂詞為假時(shí)，分支函數(shù)為正；當(dāng)分支謂詞為真時(shí)，分支函數(shù)為負(fù)。而要使某條路徑被覆蓋時(shí)，該路徑上的所有分支謂詞應(yīng)取真值，則分支函數(shù)應(yīng)為負(fù)。由于分支函數(shù)直接構(gòu)成了適應(yīng)度函數(shù)，不能為負(fù)值，故而將分支函數(shù)修改為：當(dāng)分支謂詞為真時(shí)，分支函數(shù)取0;當(dāng)分支謂詞取假時(shí)，分支函數(shù)依然取真值。因此如果某條路徑的所有分支函數(shù)都為0時(shí)表示該路徑被全部覆蓋。在本文中，使用的適應(yīng)度函數(shù)為：(3-3)111fit(x)(3-3)1+f(xi) 1+f(x2) 1+f(x3)其中，f(xi)為各分支插樁后的分支函數(shù)值。3.3.3策略選擇策略選擇運(yùn)算也叫復(fù)制運(yùn)算，模擬了生物界優(yōu)勝劣汰的自然選擇現(xiàn)象。通過(guò)選擇將優(yōu)勝的個(gè)體直接到下一代或通過(guò)配對(duì)交叉產(chǎn)生新一代個(gè)體再到下一代。選擇運(yùn)算的依據(jù)是個(gè)體的適應(yīng)度，適應(yīng)度高的個(gè)體被選擇到下一代的概率就大，甚至可能被多次復(fù)制，而適應(yīng)度低的個(gè)體則可能一次都沒(méi)被選中而淘汰。選擇的概率一般取Ps為0.1至0.2。常用的選擇運(yùn)算的方法有輪盤賭轉(zhuǎn)法、隨機(jī)遍歷抽樣、錦標(biāo)賽選擇等，其中以輪盤賭轉(zhuǎn)法最為常用。該算法將所有染色體的適應(yīng)度總和看做一個(gè)輪子的圓周，而各染色體按其適應(yīng)度占適應(yīng)度總和的比例值大小占據(jù)一個(gè)扇區(qū)。 每次進(jìn)行選擇時(shí)相當(dāng)于輪盤的一次轉(zhuǎn)動(dòng)，轉(zhuǎn)到哪個(gè)扇區(qū)則該扇區(qū)的染色體被選中。這樣適應(yīng)度越高的染色體被選中的概率就越大。若某染色體的適應(yīng)度為 f(xi)，則被選中的概率為：PsPsf(xjf(Xi)圖3-2是一個(gè)簡(jiǎn)單的賭輪的例子：13% 35% 15% 0.67 37%--T 1 卜 * 1個(gè)體1 個(gè)體2 個(gè)體3 個(gè)體4圖3-2輪盤賭轉(zhuǎn)法示意圖3-2中隨機(jī)數(shù)為0.67落在了個(gè)體4的段內(nèi)，本次選擇了個(gè)體4。（2） 交叉策略交叉運(yùn)算是算法中產(chǎn)生新個(gè)體的主要手段，其模擬的是生物學(xué)中的雜交現(xiàn)象。交叉運(yùn)算通過(guò)使兩個(gè)體的局部交換而使雙方的優(yōu)點(diǎn)有可能結(jié)合產(chǎn)生更好的新個(gè)體。一般控制產(chǎn)生交叉運(yùn)算的概率Pc為0.5至0.8。在二進(jìn)制編碼中，根據(jù)交叉點(diǎn)的不同可以分為單點(diǎn)交叉、兩點(diǎn)交叉、均勻交叉等。在本文中采用的是單點(diǎn)交叉的方法，即首先在親代中隨機(jī)選取一個(gè)交叉點(diǎn)（染色體的某個(gè)碼位），然后將兩個(gè)親代在該點(diǎn)及之后的染色體部分進(jìn)行交換。（3） 變異策略變異運(yùn)算模擬的是生物中的基因突變現(xiàn)象。通過(guò)變異操作可以增強(qiáng)算法中群體的多樣性，防止未成熟收斂現(xiàn)象，同時(shí)也使算法具備了局部隨機(jī)搜索能力， 是實(shí)現(xiàn)全局優(yōu)化性能的重要算子之一。通常，變異的控制概率較小，Pm一般取值為0.001至0.1。在二進(jìn)制編碼方式中，變異運(yùn)算即是將某些基因位上的基因值取反，即 0變1或1變0。一般變異個(gè)體的選擇及變異位置都是隨機(jī)確定的。二進(jìn)制編碼中的變異方法有基本位變異、均勻變異、高斯變異和二元變異等。本文采用的是基本位變異方法，即先隨機(jī)選擇某變異個(gè)體，再隨機(jī)確定染色體的一個(gè)變異點(diǎn)將該碼位置反。3.3.4參數(shù)控制除了上面提到的選擇、下：交叉、變異的概率外，在算法中還有一些參數(shù)主要如①種群規(guī)模群體規(guī)模較大可以增加算法的多樣性，提高GA搜索的質(zhì)量，防止算法未成熟收斂。但是群體規(guī)模大使個(gè)體適應(yīng)度的計(jì)算量大大增加，影響了算法的效率。因此應(yīng)根據(jù)不同的實(shí)際情況確定不同的種群規(guī)模。 Goldberg證明了在二進(jìn)制編碼的前提下，若個(gè)體長(zhǎng)度為L(zhǎng),則種群規(guī)模的最優(yōu)值為2l/2o辺染色體長(zhǎng)度染色體長(zhǎng)度即是編碼長(zhǎng)度，也即是表示個(gè)體的字符串的長(zhǎng)度。染色體的長(zhǎng)度由具體問(wèn)題決定，當(dāng)解的取值范圍越大、求值精度越大則染色體長(zhǎng)度越大，帶來(lái)的計(jì)算時(shí)間也相應(yīng)越長(zhǎng)。⑨算法終止條件一般來(lái)說(shuō)，算法的終止條件為預(yù)先設(shè)定的最大進(jìn)化代數(shù)，通常取100到500o也可以為某一特定條件，事具體問(wèn)題而定。以上參數(shù)為通常情況下的取值，當(dāng)然并非是固定不變的。在不同的算法中可以根據(jù)實(shí)際情況作相應(yīng)的調(diào)整，只要能提高算法的運(yùn)行效率就是可行的。3.4本章小結(jié)本章是論文的核心章節(jié)，對(duì)算法應(yīng)用于測(cè)試用例的生產(chǎn)方法進(jìn)行了系統(tǒng)的介紹。首先介紹了算法生成測(cè)試用例的基本內(nèi)含，然后提出了基本框架，最后對(duì)本文中算法實(shí)現(xiàn)的相關(guān)操作進(jìn)行了描述，包括編碼策略、適應(yīng)度函數(shù)構(gòu)造、選擇策略、交叉策略、變異策略等。第四章實(shí)驗(yàn)及結(jié)果分析4.1待測(cè)程序分析4.1.1待測(cè)程序引入本章中將以三角形分類程序?yàn)槔齺?lái)驗(yàn)證算法。 三角形分類程序在許多軟件測(cè)試研究中被作為基準(zhǔn)程序來(lái)使用，因?yàn)槠浒逦謴?fù)雜的邏輯，并且即使將一個(gè)較大范圍的整數(shù)作為輸入，也只有少量的輸入組合能滿足代碼的某些特定分支。例如當(dāng)輸入為1到10的整數(shù)時(shí)，1000組輸入只有10組能滿足判斷為“等邊三角形”的分支。三角形源程序?yàn)椋篠tringtri_type(inta,intb,intc){stringtype;if(a>b)change(a,b);if(a>c)change(a,c);if(b>c)change(b,c);if(a+b>c){ if(a==b||b==c){ if(a==c)type="等邊三角形”；elsetype="等腰三角形”；}elsetype="普通三角形”；}elsetype= "不是三角形”；returntype;}4.1.2程序流程分析該程序流程圖如圖4-1所示，程序分為兩部分，先將輸入值由小到大排序,再將三角形進(jìn)行分類。

圖4-1圖4-1三角形分類程序流程圖4.1.3路徑分析通過(guò)對(duì)根據(jù)3.3.2，對(duì)待測(cè)程序插樁：Stringtri_type(inta,intb,intc)適應(yīng)度函數(shù)F=1/(1+f1)+1/(1+f2)+1/(1+f3); //適應(yīng)度函數(shù)returnF; }4.3參數(shù)設(shè)定及程序?qū)崿F(xiàn)4.3.1參數(shù)設(shè)定（1）編碼在本例子中，由于程序輸入為三角形的三條邊的長(zhǎng)度， 因此設(shè)定輸入值類型為0~63的整數(shù)，采用二進(jìn)制級(jí)聯(lián)編碼方法，每個(gè)參數(shù)編碼長(zhǎng)度為 6位，精度為1，并將三個(gè)參數(shù)進(jìn)行級(jí)聯(lián)（如參數(shù)000000、111111、101010級(jí)聯(lián)后為

000000111111101010,級(jí)聯(lián)后染色體長(zhǎng)度為18位。操作參數(shù)在本實(shí)驗(yàn)中，設(shè)定操作的參數(shù)如表4-2所示:表4-2操作參數(shù)設(shè)定種群大小選擇策略及概率交叉策略及概率變異策略及概率最大進(jìn)化代數(shù)100輪盤賭轉(zhuǎn)法，0.1單點(diǎn)交叉，0.8基本位變異，0.1100算法終止條件本實(shí)驗(yàn)中設(shè)定算法終止條件為滿足以下兩個(gè)條件之一：①找到最優(yōu)解，即適應(yīng)度為100的解；?達(dá)到最大進(jìn)化代數(shù)，當(dāng)程序進(jìn)化滿100代后，不管有沒(méi)找到最優(yōu)解都將退出。4.3.2部分程序?qū)崿F(xiàn)本文中的三角形分類程序是在MicrosoftVisualStudio2005的環(huán)境下采用C++語(yǔ)言實(shí)現(xiàn)的。以下為該程序的主要算法模塊:(1)染色體定義模塊，該模塊完成了染色體的編碼:structsides{inta;intb;測(cè)試的三個(gè)數(shù)據(jù)// 該組的染色體該組數(shù)的適應(yīng)度標(biāo)記是否操作過(guò)測(cè)試的三個(gè)數(shù)據(jù)// 該組的染色體該組數(shù)的適應(yīng)度標(biāo)記是否操作過(guò)bitset<3*BIT>chromosome;intsufficiency; //boolisOp; } //(2)計(jì)算適應(yīng)度，采用插樁法:intgetSufficiency(inta,intb,intc){intf,f1,f2,f3;if(a>b)change(a,b);if(a>c)change(a,c);if(b>c)change(b,c);f1=c-(a+b);〃if(a+b>c)f2=min<int>(abs(a-b),abs(b-c));〃if(a==b||b==c)f3=abs(a-c);〃if(a==c)type= "等邊三角形”；//elsetype="等腰三角形”；//elsetype= "普通三角形”；〃el setype="不是三角形”；//returntype;if(f1<0){fl=0;}f=(100/(1+f1)+100心+f2)+100心+f3))/3;returnf;}選擇操作，使用了輪盤賭轉(zhuǎn)法：voidselect(sidesnewGroup[],sidesoldGroup[]){resetFlag(oldGroup);intaPos[GROUP]; // 存儲(chǔ)每組數(shù)據(jù)在轉(zhuǎn)盤中的位置aPos[0]=oldGroup[0].sufficiency;for(inti=1;i<GROUP;i++){aPos[i]=oldGroup[i].sufficiency;aPos[i]+=aPos[i-1];}for(inti=0;i<SELECTION;){intrandom=rand()%aPos[GROUP-1]; // 產(chǎn)生隨即數(shù)，0到群體中的最后一組數(shù)據(jù)所在的位置找到該隨機(jī)數(shù)所在位置 ，如果位置重復(fù)了就重新選擇for(intj=0;j<GROUP;j++){if(random<=aPos[j]){if(!oldGroup[j].isOp){newGroup[i]=oldGroup[j];oldGroup[j].isOp=true;i++;break;}else{break;}}}}}交叉操作，先用輪盤賭轉(zhuǎn)法選擇，再用單點(diǎn)交叉法進(jìn)行交叉：voidcross(sidesnewGroup[],sidesoldGroup[]){intaPos[GROUP];aPos[0]=oldGroup[0].sufficiency;for(inti=1;i<GROUP;i++){aPos[i]=oldGroup[i].sufficiency;aPos[i]+=aPos[i-1];}for(inti=0;i<CROSS;){intrandom=rand()%aPos[GROUP-1];for(intj=0;j<GROUP;j++){if(random<=aPos[j]){if(!oldGroup[j].isOp){newGroup[int(SELECTION)+i]=oldGroup[j];oldGroup[j].isOp=true;i++;break;}else{break;}}}}//兩兩進(jìn)行交叉，并更新每組的適應(yīng)值for(inti=SELECTION;i<SELECTION+CROSS;i+=2){intrandom=rand()%(3*BIT); // 隨機(jī)選一個(gè)位置進(jìn)行交叉stringstr1=newGroup[i].chromosome.to_string();stringstr2=newGroup[i+1].chromosome.to_string();stringnew1=str1.substr(0,random+1)+str2.substr(random);stringnew2=str2.substr(0,random+1)+str1.substr(random);bitset<12>bsNew1(new1);bitset<12>bsNew2(new2);//更新染色體newGroup[i].chromosome=bsNew1;newGroup[i+1].chromosome=bsNew2;//更新數(shù)字resetNum(newGroup[i]);resetNum(newGroup[i+1]);//更新適應(yīng)度newGroup[i].sufficiency = getSufficiency(newGroup[i].a,newGroup[i].b,newGroup[i].c);newGroup[i +1].sufficiency=getSufficiency(newGroup[i +1].a,newGroup[i+1].b,newGroup[i+1].c);}}變異操作，采用基本位變異方法：voidaberrance(sidesnewGroup[],sidesoldGroup[]){intpos=SELECTION+CROSS;for(inti=0;i<GROUP;i++){if(!oldGroup[i].isOp){intrandom=rand()%(3*BIT); // 隨機(jī)產(chǎn)生變異位newGroup[pos]=oldGroup[i];newGroup[pos].chromosome.flip(3*BIT-random-1);resetNum(newGroup[pos]);//更新適應(yīng)度newGroup[pos].sufficiency = getSufficiency(newGroup[pos].a,newGroup[pos].b,newGroup[pos].c);pos++;}}}4.4結(jié)果分析對(duì)算法自身的進(jìn)化能力分析以三角形分類程序的判為“等邊三角形”的路徑w4為例，運(yùn)行程序，發(fā)現(xiàn)在51代時(shí)找到了最優(yōu)解，表4-3、4-4、4-5分別為第0代、第13代、第51代

的適應(yīng)度為前10的個(gè)體情況：表4-3第0代適應(yīng)度前10的個(gè)體丨體編號(hào)染色體編碼參數(shù)值適應(yīng)度ABC11101010111000111005328286721001101010011001113841395830110110110100101102726225540001110011000010007128555100110101101101100384544546011011100011100010273534537111011111010101011595843518110110111000111011545659499100001011110011100333028491011001111100011101051565848表4-4第13代適應(yīng)度前10的個(gè)體丨體編號(hào)染色體編碼參數(shù)值適應(yīng)度ABC101000000101101000016111672210100011110110100040614068310100010100001001040401868410101100101110101143114367501010001011101011020232258611110110110011111061446251710011110011000101039381051801101011110111110026616050900001110100110100034140501001111110010110011131373948表4-5第51代適應(yīng)度前10的個(gè)體丨體編號(hào)染色體編碼參數(shù)值適應(yīng)度ABC110110110110110110145454510020011110011110100011515177731001110011111001113915396841001101101111001103855386851111111111110001106363667601000000111101000116151761700100100111000111191415548110000111010111011485859529011000100111011001243925521000111001000001001014161851由這三張表可見(jiàn)，隨著進(jìn)化過(guò)程的繼續(xù)，群體的總體適應(yīng)度在增加，說(shuō)明算法正朝著最優(yōu)解的方向收斂，直至找到最優(yōu)解。這說(shuō)明算法在程序測(cè)試數(shù)據(jù)自動(dòng)生成中是有一定作用的，它能逐漸改善個(gè)體，使其越來(lái)越接近我們的標(biāo)準(zhǔn)路徑，最終達(dá)到我們?cè)O(shè)定的標(biāo)準(zhǔn)路徑。（2）算法與隨機(jī)法比較隨機(jī)法是目前大多數(shù)測(cè)試工具生成測(cè)試用例所使用的算法， 其思想已在本文第一章中介紹過(guò)。為了顯示算法的優(yōu)越性，現(xiàn)分別使用算法和隨機(jī)法對(duì)三角形分類程序中的四條路徑進(jìn)行20次的搜索，分析這兩種算法的成功率與運(yùn)行速度，對(duì)比結(jié)果如表4-6所示：表4-6兩種算法運(yùn)行結(jié)果路算法隨機(jī)法徑平均進(jìn)收斂成功率平均運(yùn)行時(shí)平均進(jìn)收斂成功率平均運(yùn)行時(shí)號(hào)化代數(shù)次數(shù)（%間（ms）化代數(shù)次數(shù)（%間（ms）W102010020201000W202010020201000W302010030201000W42720100813316800由表4-6可知，使用隨機(jī)法的平均運(yùn)行時(shí)間較算法短，但隨機(jī)法對(duì)于稍微復(fù)雜的路徑進(jìn)行搜索時(shí)成功率明顯下降，表中在w4路徑的搜索結(jié)果中，隨機(jī)法的成功率為80%搜索效果較算法差。而算法雖然運(yùn)行時(shí)間稍久于隨機(jī)法，但其四條路徑的成功率均為100%特別是在復(fù)雜路徑中也能找到最優(yōu)解，充分發(fā)揮了其全局尋優(yōu)能力。在實(shí)際運(yùn)用中，測(cè)試數(shù)據(jù)覆蓋率的高低是軟件質(zhì)量的基本保障,因此算法成功率顯然比運(yùn)行時(shí)間更為重要，可見(jiàn)算法的優(yōu)越性。4.5本章小結(jié)本章以三角形分類程序?yàn)槔褂盟惴ㄟM(jìn)行測(cè)試用例的生成， 是前幾章內(nèi)容的結(jié)晶。文中先對(duì)待測(cè)程序的流程和路徑等進(jìn)行了分析， 然后對(duì)程序進(jìn)行插樁，并對(duì)相關(guān)參數(shù)進(jìn)行了設(shè)定，然后展示了程序主要模塊的代碼，最后通過(guò)分析程序的運(yùn)行結(jié)果，并和隨機(jī)法作了比較，顯示了算法的優(yōu)越性。第五章總結(jié)與展望軟件測(cè)試是軟件工程中的重要環(huán)節(jié)，隨著軟件技術(shù)的發(fā)展和軟件規(guī)模的擴(kuò)大，軟件測(cè)試日益凸顯其重要性。而測(cè)試數(shù)據(jù)是軟件測(cè)試的基礎(chǔ)。傳統(tǒng)的手工構(gòu)建測(cè)試數(shù)據(jù)工作量大，浪費(fèi)了大量的人力、物力資源，且測(cè)試效率低。因此測(cè)試用例的自動(dòng)生成成為了國(guó)內(nèi)外學(xué)者研究的熱點(diǎn)。算法作為一種優(yōu)化的搜索算法，在軟件測(cè)試中得到了廣泛的應(yīng)用和研究。本文作者通過(guò)對(duì)大量文獻(xiàn)中測(cè)試用例生成方法和算法的學(xué)習(xí)，將算法應(yīng)用到測(cè)試用例的生成上。文中首先介紹了軟件測(cè)試及算法的國(guó)內(nèi)外研究現(xiàn)狀，然后介紹了軟件測(cè)試和算法的基本概念，接著提出了基于算法生成測(cè)試用例的內(nèi)含、框架及模型，最后以三角形分類程序?yàn)槔?yàn)證了基于生成測(cè)試用例的可行性。由于時(shí)間問(wèn)題，本文還存在許多問(wèn)題和不足，將作為進(jìn)一步研究的主要內(nèi)容和方向：第一，本文只用到了算法，并沒(méi)有將其它算法與之混合使用以改進(jìn)性能。第二，本文中算法所使用的適應(yīng)度函數(shù)及算子均采用的是比較簡(jiǎn)單且使用廣泛的算法，并沒(méi)有將這些算法做進(jìn)一步的研究和改進(jìn)。第三，本文最后實(shí)現(xiàn)的程序只是一個(gè)產(chǎn)生測(cè)試數(shù)據(jù)的原始工具模型， 特別在用戶界面方面還很欠缺，需要進(jìn)一步完善。致謝語(yǔ)四年的本科學(xué)習(xí)生涯很快就要過(guò)去了，在本論文完成之際，我首先要感謝***老師，*老師在我從論文選題至今給了我不少建議，使我受益良多，是我能順利完成論文的關(guān)鍵所在。*老師治學(xué)嚴(yán)謹(jǐn)，待人和藹，使我以后工作、學(xué)習(xí)中為人處事的榜樣。同時(shí)還要衷心感謝***老師。*老師在擔(dān)任班導(dǎo)師期間時(shí)常給我們教授學(xué)習(xí)和工作的實(shí)際經(jīng)驗(yàn)，使我對(duì)于日后的工作方向有了明確的定位，也將在我日后的工作中繼續(xù)產(chǎn)生良好的作用。感謝***同學(xué)在程序?qū)崿F(xiàn)部分的幫助。感謝我的家人以及所有在生活中、學(xué)習(xí)中幫助過(guò)我或給予過(guò)我良好啟發(fā)的人。參考文獻(xiàn)RonPatton. 軟件測(cè)試（第二版）[M].北京：機(jī)械工業(yè)出版社，2006:4-5趙曉華，計(jì)算機(jī)軟件可靠性與質(zhì)量管理[M].北京:中國(guó)經(jīng)濟(jì)出版社，1992徐仁佐.軟件可靠性工程[M].清華大學(xué)出版社，2007.5王小平，曹立明.算法理論、應(yīng)用與軟件實(shí)現(xiàn)[M].西安:西安交通大學(xué)出版社,2001.⑸許秀梅.基于退火免疫算法的測(cè)試數(shù)據(jù)生成方法研究[D].北京：北京交通大學(xué)，2007⑹樂(lè)鑫喜.基于退火算法的測(cè)試用例自動(dòng)生成[D].武漢：武漢理工大學(xué)，2005律亞楠.基于算法的測(cè)試數(shù)據(jù)生成研究[D].汕頭：汕頭大學(xué)，2008錢肖英.基于算法的測(cè)試數(shù)據(jù)自動(dòng)生成方法的研究[D].杭州：浙江工商大學(xué)，2008馬志兵.基于算法的測(cè)試數(shù)據(jù)自動(dòng)生成技術(shù)研究[D].青島：青島大學(xué)，2009顧鵬.基于算法的測(cè)試用例產(chǎn)生系統(tǒng)關(guān)鍵技術(shù)研究[D].武漢：華中科技大學(xué)，2006陳雨?基于算法的測(cè)試用例生成[D].上海：東華大學(xué)，2009林惠娟.基于算法的測(cè)試用例自動(dòng)生成技術(shù)研究[D].成都：四川大學(xué)，2006D.BirdandC.Munoz.Automaticgenerationofrandomself-checkingtestcases[J].IBMSystemJ.vol.22,NO.3.1983:229-245P.D.Coward.Symbolicexecutionandtesting[J].InformationandSoftwareTeehnology.1991,2:53-64C.V.Ramamoorthy,S.Ho.AndW.Chen.OntheautomatedgenerationofProgramtestdata[J]. IEEETrans.SoftwareEng.Vol.SE—2,NO.1.1981:117-127RamamoorthyC.V.OntheautomatedgenerationofProgramtestdata[J].IEEETransonSoftwareEng,1976,4:215-222KorelB.Automatedsoftwaretestdatageneration[J].IEEETrans.onSoftwareEngineering,1990,16(8):870-879.NeelamGuPta,AdityaP.