基于FPGA的递归最小二乘算法的研究与实现

基于遗传算法的测试用例生成方法基于遗传算法的测试用例生成方法#E1>=E2E2-E1<=E1<E2E1-E2<E1<=E2E1-E2<=E仁=E2abs(E1-E2)==E1!=E2-abs(E1-E2)<由表可知，当分支谓词为假时，分支函数为正；当分支谓词为真时，分支函数为负。而要使某条路径被覆盖时，该路径上的所有分支谓词应取真值，则分支函数应为负。由于分支函数直接构成了适应度函数，不能为负值，故而将分支函数修改为：当分支谓词为真时，分支函数取0;当分支谓词取假时，分支函数依然取真值。因此如果某条路径的所有分支函数都为0时表示该路径被全部覆盖。在本文中，使用的适应度函数为：(3-3)111fit(x)(3-3)1+f(xi) 1+f(x2) 1+f(x3)其中，f(xi)为各分支插桩后的分支函数值。3.3.3策略选择策略选择运算也叫复制运算，模拟了生物界优胜劣汰的自然选择现象。通过选择将优胜的个体直接到下一代或通过配对交叉产生新一代个体再到下一代。选择运算的依据是个体的适应度，适应度高的个体被选择到下一代的概率就大，甚至可能被多次复制，而适应度低的个体则可能一次都没被选中而淘汰。选择的概率一般取Ps为0.1至0.2。常用的选择运算的方法有轮盘赌转法、随机遍历抽样、锦标赛选择等，其中以轮盘赌转法最为常用。该算法将所有染色体的适应度总和看做一个轮子的圆周，而各染色体按其适应度占适应度总和的比例值大小占据一个扇区。 每次进行选择时相当于轮盘的一次转动，转到哪个扇区则该扇区的染色体被选中。这样适应度越高的染色体被选中的概率就越大。若某染色体的适应度为 f(xi)，则被选中的概率为：PsPsf(xjf(Xi)图3-2是一个简单的赌轮的例子：13% 35% 15% 0.67 37%--T 1 卜 * 1个体1 个体2 个体3 个体4图3-2轮盘赌转法示意图3-2中随机数为0.67落在了个体4的段内，本次选择了个体4。（2） 交叉策略交叉运算是算法中产生新个体的主要手段，其模拟的是生物学中的杂交现象。交叉运算通过使两个体的局部交换而使双方的优点有可能结合产生更好的新个体。一般控制产生交叉运算的概率Pc为0.5至0.8。在二进制编码中，根据交叉点的不同可以分为单点交叉、两点交叉、均匀交叉等。在本文中采用的是单点交叉的方法，即首先在亲代中随机选取一个交叉点（染色体的某个码位），然后将两个亲代在该点及之后的染色体部分进行交换。（3） 变异策略变异运算模拟的是生物中的基因突变现象。通过变异操作可以增强算法中群体的多样性，防止未成熟收敛现象，同时也使算法具备了局部随机搜索能力， 是实现全局优化性能的重要算子之一。通常，变异的控制概率较小，Pm一般取值为0.001至0.1。在二进制编码方式中，变异运算即是将某些基因位上的基因值取反，即 0变1或1变0。一般变异个体的选择及变异位置都是随机确定的。二进制编码中的变异方法有基本位变异、均匀变异、高斯变异和二元变异等。本文采用的是基本位变异方法，即先随机选择某变异个体，再随机确定染色体的一个变异点将该码位置反。3.3.4参数控制除了上面提到的选择、下：交叉、变异的概率外，在算法中还有一些参数主要如①种群规模群体规模较大可以增加算法的多样性，提高GA搜索的质量，防止算法未成熟收敛。但是群体规模大使个体适应度的计算量大大增加，影响了算法的效率。因此应根据不同的实际情况确定不同的种群规模。 Goldberg证明了在二进制编码的前提下，若个体长度为L,则种群规模的最优值为2l/2o辺染色体长度染色体长度即是编码长度，也即是表示个体的字符串的长度。染色体的长度由具体问题决定，当解的取值范围越大、求值精度越大则染色体长度越大，带来的计算时间也相应越长。⑨算法终止条件一般来说，算法的终止条件为预先设定的最大进化代数，通常取100到500o也可以为某一特定条件，事具体问题而定。以上参数为通常情况下的取值，当然并非是固定不变的。在不同的算法中可以根据实际情况作相应的调整，只要能提高算法的运行效率就是可行的。3.4本章小结本章是论文的核心章节，对算法应用于测试用例的生产方法进行了系统的介绍。首先介绍了算法生成测试用例的基本内含，然后提出了基本框架，最后对本文中算法实现的相关操作进行了描述，包括编码策略、适应度函数构造、选择策略、交叉策略、变异策略等。第四章实验及结果分析4.1待测程序分析4.1.1待测程序引入本章中将以三角形分类程序为例来验证算法。 三角形分类程序在许多软件测试研究中被作为基准程序来使用，因为其包含清晰而又复杂的逻辑，并且即使将一个较大范围的整数作为输入，也只有少量的输入组合能满足代码的某些特定分支。例如当输入为1到10的整数时，1000组输入只有10组能满足判断为“等边三角形”的分支。三角形源程序为：Stringtri_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所示，程序分为两部分，先将输入值由小到大排序,再将三角形进行分类。

图4-1图4-1三角形分类程序流程图4.1.3路径分析通过对根据3.3.2，对待测程序插桩：Stringtri_type(inta,intb,intc)适应度函数F=1/(1+f1)+1/(1+f2)+1/(1+f3); //适应度函数returnF; }4.3参数设定及程序实现4.3.1参数设定（1）编码在本例子中，由于程序输入为三角形的三条边的长度， 因此设定输入值类型为0~63的整数，采用二进制级联编码方法，每个参数编码长度为 6位，精度为1，并将三个参数进行级联（如参数000000、111111、101010级联后为

000000111111101010,级联后染色体长度为18位。操作参数在本实验中，设定操作的参数如表4-2所示:表4-2操作参数设定种群大小选择策略及概率交叉策略及概率变异策略及概率最大进化代数100轮盘赌转法，0.1单点交叉，0.8基本位变异，0.1100算法终止条件本实验中设定算法终止条件为满足以下两个条件之一：①找到最优解，即适应度为100的解；®达到最大进化代数，当程序进化满100代后，不管有没找到最优解都将退出。4.3.2部分程序实现本文中的三角形分类程序是在MicrosoftVisualStudio2005的环境下采用C++语言实现的。以下为该程序的主要算法模块:(1)染色体定义模块，该模块完成了染色体的编码:structsides{inta;intb;测试的三个数据// 该组的染色体该组数的适应度标记是否操作过测试的三个数据// 该组的染色体该组数的适应度标记是否操作过bitset<3*BIT>chromosome;intsufficiency; //boolisOp; } //(2)计算适应度，采用插桩法: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;}选择操作，使用了轮盘赌转法：voidselect(sidesnewGroup[],sidesoldGroup[]){resetFlag(oldGroup);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<SELECTION;){intrandom=rand()%aPos[GROUP-1]; // 产生随即数，0到群体中的最后一组数据所在的位置找到该随机数所在位置 ，如果位置重复了就重新选择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;}}}}}交叉操作，先用轮盘赌转法选择，再用单点交叉法进行交叉：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;}}}}//两两进行交叉，并更新每组的适应值for(inti=SELECTION;i<SELECTION+CROSS;i+=2){intrandom=rand()%(3*BIT); // 随机选一个位置进行交叉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;//更新数字resetNum(newGroup[i]);resetNum(newGroup[i+1]);//更新适应度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); // 随机产生变异位newGroup[pos]=oldGroup[i];newGroup[pos].chromosome.flip(3*BIT-random-1);resetNum(newGroup[pos]);//更新适应度newGroup[pos].sufficiency = getSufficiency(newGroup[pos].a,newGroup[pos].b,newGroup[pos].c);pos++;}}}4.4结果分析对算法自身的进化能力分析以三角形分类程序的判为“等边三角形”的路径w4为例，运行程序，发现在51代时找到了最优解，表4-3、4-4、4-5分别为第0代、第13代、第51代

的适应度为前10的个体情况：表4-3第0代适应度前10的个体丨体编号染色体编码参数值适应度ABC11101010111000111005328286721001101010011001113841395830110110110100101102726225540001110011000010007128555100110101101101100384544546011011100011100010273534537111011111010101011595843518110110111000111011545659499100001011110011100333028491011001111100011101051565848表4-4第13代适应度前10的个体丨体编号染色体编码参数值适应度ABC101000000101101000016111672210100011110110100040614068310100010100001001040401868410101100101110101143114367501010001011101011020232258611110110110011111061446251710011110011000101039381051801101011110111110026616050900001110100110100034140501001111110010110011131373948表4-5第51代适应度前10的个体丨体编号染色体编码参数值适应度ABC110110110110110110145454510020011110011110100011515177731001110011111001113915396841001101101111001103855386851111111111110001106363667601000000111101000116151761700100100111000111191415548110000111010111011485859529011000100111011001243925521000111001000001001014161851由这三张表可见，随着进化过程的继续，群体的总体适应度在增加，说明算法正朝着最优解的方向收敛，直至找到最优解。这说明算法在程序测试数据自动生成中是有一定作用的，它能逐渐改善个体，使其越来越接近我们的标准路径，最终达到我们设定的标准路径。（2）算法与随机法比较随机法是目前大多数测试工具生成测试用例所使用的算法， 其思想已在本文第一章中介绍过。为了显示算法的优越性，现分别使用算法和随机法对三角形分类程序中的四条路径进行20次的搜索，分析这两种算法的成功率与运行速度，对比结果如表4-6所示：表4-6两种算法运行结果路算法随机法径平均进收敛成功率平均运行时平均进收敛成功率平均运行时号化代数次数（%间（ms）化代数次数（%间（ms）W102010020201000W202010020201000W302010030201000W42720100813316800由表4-6可知，使用随机法的平均运行时间较算法短，但随机法对于稍微复杂的路径进行搜索时成功率明显下降，表中在w4路径的搜索结果中，随机法的成功率为80%搜索效果较算法差。而算法虽然运行时间稍久于随机法，但其四条路径的成功率均为100%特别是在复杂路径中也能找到最优解，充分发挥了其全局寻优能力。在实际运用中，测试数据覆盖率的高低是软件质量的基本保障,因此算法成功率显然比运行时间更为重要，可见算法的优越性。4.5本章小结本章以三角形分类程序为例使用算法进行测试用例的生成， 是前几章内容的结晶。文中先对待测程序的流程和路径等进行了分析， 然后对程序进行插桩，并对相关参数进行了设定，然后展示了程序主要模块的代码，最后通过分析程序的运行结果，并和随机法作了比较，显示了算法的优越性。第五章总结与展望软件测试是软件工程中的重要环节，随着软件技术的发展和软件规模的扩大，软件测试日益凸显其重要性。而测试数据是软件测试的基础。传统的手工构建测试数据工作量大，浪费了大量的人力、物力资源，且测试效率低。因此测试用例的自动生成成为了国内外学者研究的热点。算法作为一种优化的搜索算法，在软件测试中得到了广泛的应用和研究。本文作者通过对大量文献中测试用例生成方法和算法的学习，将算法应用到测试用例的生成上。文中首先介绍了软件测试及算法的国内外研究现状，然后介绍了软件测试和算法的基本概念，接着提出了基于算法生成测试用例的内含、框架及模型，最后以三角形分类程序为例验证了基于生成测试用例的可行性。由于时间问题，本文还存在许多问题和不足，将作为进一步研究的主要内容和方向：第一，本文只用到了算法，并没有将其它算法与之混合使用以改进性能。第二，本文中算法所使用的适应度函数及算子均采用的是比较简单且使用广泛的算法，并没有将这些算法做进一步的研究和改进。第三，本文最后实现的程序只是一个产生测试数据的原始工具模型， 特别在用户界面方面还很欠缺，需要进一步完善。致谢语四年的本科学习生涯很快就要过去了，在本论文完成之际，我首先要感谢***老师，*老师在我从论文选题至今给了我不少建议，使我受益良多，是我能顺利完成论文的关键所在。*老师治学严谨，待人和蔼，使我以后工作、学习中为人处事的榜样。同时还要衷心感谢***老师。*老师在担任班导师期间时常给我们教授学习和工作的实际经验，使我对于日后的工作方向有了明确的定位，也将在我日后的工作中继续产生良好的作用。感谢***同学在程序实现部分的帮助。感谢我的家人以及所有在生活中、学习中帮助过我或给予过我良好启发的人。参考文献RonPatton. 软件测试（第二版）[M].北京：机械工业出版社，2006:4-5赵晓华，计算机软件可靠性与质量管理[M].北京:中国经济出版社，1992徐仁佐.软件可靠性工程[M].清华大学出版社，2007.5王小平，曹立明.算法理论、应用与软件实现[M].西安:西安交通大学出版社,2001.⑸许秀梅.基于退火免疫算法的测试数据生成方法研究[D].北京：北京交通大学，2007⑹乐鑫喜.基于退火算法的测试用例自动生成[D].武汉：武汉理工大学，2005律亚楠.基于算法的测试数据生成研究[D].汕头：汕头大学，2008钱肖英.基于算法的测试数据自动生成方法的研究[D].杭州：浙江工商大学，2008马志兵.基于算法的测试数据自动生成技术研究[D].青岛：青岛大学，2009顾鹏.基于算法的测试用例产生系统关键技术研究[D].武汉：华中科技大学，2006陈雨•基于算法的测试用例生成[D].上海：东华大学，2009林惠娟.基于算法的测试用例自动生成技术研究[D].成都：四川大学，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.