基于遗传算法测试用例的生成和优化VIP专享VIP免费

第2110541卷年10月南京大学学报(自然科学)JOURNALOFNANJINGUNIVERSITY(NATURALSCIENCES)Vol.41Oct.,2005基于遗传算法测试用例的生成和优化李伟，王波，武清芳，闰平超(北京市7223信箱10分箱，北京，100072)摘要:遗传算法是通过模拟自然进化过程，将问题的解逐步向最优化方向进化软件测试的目的是发现软件中未发现的缺陷，而测试用例的设计是关键.主要研究了遗传算法在侧试用例的生成和优化方面的方法和应用.关键词:遗传算法.侧试用例.适应度值，遗传程序设计中圈分类号:TP301.6TheGenerationandOptimizationofTestCaseBasedonGeneticAlgorithmLiWei，WangBo,W“Qing-Fang,YanPing-Chao(BeijingP.0Box722310气Beijing,100072，China)Abstract:GeneticAlgorithmisanalogoustotheprocessofthenatureevolutionandsolvetheproblemtothemostoptimizationsolvegradually.Thegoalofthesoftwaretestingistofindthefaultshidinginthetestedsoftwareandthedesignoftestcaseisstickingpoint.Thispaperfocusontheissueofapplyinggeneticalgorithmtogenerateandoptimizaethetestingcase.Keywords:geneticalgorithm,test~，fitnessvalue,geneticprogramming遗传算法是一种借鉴生物界自然选择、自然遗传机制和进化机制的优化算法是模拟达尔文的遗传选择和自然淘汰的生物进化过程的计算模型，是由美国Michigan大学的J.Holland教授于1975年首先提出.组合优化是遗传算法最基本也是最重要的研究领域之一近几年来，随着对于遗传算法研究的不断深人完善，越来越多的人认识了解了遗传算法，并把它应用到越来越广泛的领域，例如机器学习、模式识别、图像处理、神经网络、工业优化控制和社会科学等方面，并取得了很大的成功.由于遗传算法的整体搜索策略和优化计算时不依赖于梯度信息，所以它尤其适合于处理传统搜索方法难以解决的高度复杂的非线性问题.随着计算机技术和软件设计技术的迅猛发展，计算机应用软件的规模和复杂度随之增长，同时加上时间和市场的压力，带来的主要问题是软件的质量和可靠性变得越来越低.软件测试作为一种提高软件质量和可靠性的重要手段，其目的在于发现软件中以前不曾发现的缺陷，以减少软件中潜在的缺陷，以保证软件投人使用后发生故障的机率降到最小.测试用例的设计和生成在软件测试中起着关键的作用.遗传算法作为一种新型的、模拟生物进化过程的随机化优化方法，十几年来在组合优化领域得到了相当广泛的研究和应用测试用例质量的提高和优化是一个非线性优化问题，可以很好地利用遗传算法来解决该问题.本文主要研究第41卷李伟等:基于遗传算法测试用例的生成和优化635了遗传算法在软件测试用例的生成和优化等方面的应用，以提高软件测试用例的质量1通用遗传算法遗传算法是一种有效的解决最优化问题的方法.从1975年提出以来，它逐渐发展成为一种通过模拟自然进化过程解决最优化间题的计算模型，其工作原理是:用一个目标准则选择最合适的个体，构建新一代的个体.从上一代到下一代的目标准则是遗传算法的关注点.当然还包括其它内容，如适应度函数f的定义和适应度值的选取.一般遗传算法的流程如图1所不遗传算法的特点是计算简单，改进速度快，其作用对象为群体而非个体.应用遗传算法解决某类问题，需先对要解决的问题分解，分解成的最小单元应与生物的基因相对应.个体的集合构成群体，群体中的个体具有相同的大小(即同一群体中所有个体具有相同的基因数).适应度函数的值表示了要解决问题中的个体的质量.择又称复制或再生(reproduanction):是从群体中选择优胜的个体，淘汰劣质个体的操作.判断个体优良与否的准则是各自的适应度值.其目的是把优化的个体直接遗传到下一代或通过配对交叉产生下一代的个体.交叉:是把两个父代的个体的部分结构加以互换重组而生成新个体的操作.交叉可分两步进行:首先对配对库中的个体进行随机配对;其次在配对个体中随机设定交叉点，配对的个体彼此交换部分信息.如个体A和B形成一对(A,B)，可以形成新的个体对(A',B'),A'是有A的前k个基因和B的后n一k个基因组成，B'是由B的前k个基因和A的后n一k个基因组成.变异:是对群体中的个体串的某些基因座上的基因值做变...