基于遗传算法的路径测试数据自动生成研究

《基于遗传算法的路径测试数据自动生成研究》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、基于遗传算法的路径测试数据自动生成研究摘要：针对遗传算法在运算过程中产生的早熟问题，提出一种自适应动态优化策略（SAOGO），用以自动生成测试数据。通过优化变异概率等手段，实现了路径测试数据的自动生成。将Triangle（三角形判别问题）作为被检测程序进行性能测试，实验结果表明，基于该策略的测试数据自动生成系统能自动调整变异概率和保持优秀个体，有效的解决了早熟问题，同时也提高了自动生成测试数据的效率。关键词：软件测试；路径测试数据；自适应动态优化策略中图分类号：TP311.526随着计算机技术的飞速的发展，在各行各业中计算机都成为了一个重要的工具。与其相适应的的软件也在飞速发展，软件的

2、规模和复杂度也提高很快。作为软件开发过程中重要的步骤――软件测试的规模和复杂度也相应的提高了很多。软件测试是一项昂贵而又耗费劳力的工作，往往占软件开发总工作量的50%左右[1]。测试数据的自动生成由其能提高软件测试的效率和减少成本，一直是人们研究的重要对象。近几年来，如何生成测试数据的已转化成如何搜索合适测试数据，这使自动生成测试数据的成为可能。利用遗传算法，并根据测试数据自动生成问题的特点，可以生成高效的路径测试数据自动生成算法，具有一定的理论意义和工程实用价值。1SAOGO策略的引入遗传算法的性能受到两个重要因素的影响，即“选择压力”和“种群多样性”。在种群今后的过程中，如果选择压

3、力太大将会导致种群很快被少量的个体占据，种群的多样性被破坏，导致算法的结果为局部最优。这样的情况严重的降低遗传算法的性能，这被称为进化停滞（evolutionstagnation）问题或种群早熟（population6premahirity）问题。但是，如果选择较低的选择压力，虽然可以加大算法搜索的结果为全局最优的概率，但是却会严重的降低搜索的效率，甚至是算法退化为随机算法，这将会对遗传算法的搜索效率产生严重的影响。研究者们提出了一些方法，可以预防种群早熟现象的出现：（1）对初始种群的规模设置尽量的大。在大规模的种群中因其含有比较多的个体，其染色体的性态也比较多样，发生算法收敛到局部最

4、优的情况的可能性较低。（2）提高变异操作的变异概率。更多的进行编译操作可以增加种群的新基因，提高了种群的多样性，但较高的变异概率使搜索的随机性增强，有可能降低适应值函数的导向性，反而降低了遗传算法的性能。（3）使用选择压力较小的存活操作和选择操作[2-3]。以上几种方法都只是对遗传算法的优化了其静态配置，只能预防种群早熟问题。当种群早熟问题发生时，它们没有更好的方法来对种群恢复其多样性。研究表明，对搜索过程进行启发式的动态优化，能改善智能随机搜索法的性能[4]。我们认为在遗传算法的搜索中引入启发式的动态优化方法同样可能提高搜索的性能。我们提出了一种自适应动态优化策略SAOGO来动态调整

5、Pm的取值和交叉对象，以解决进化停滞问题和加快最优解的产生。2SAOGO策略SAOGO的基本思想是：对种群的进化情况进行监视，并根据监控的情况自动的调整算法的部分参数设置，以保证进化处于良好的状态。合适的动态优化方法能有效的提高算法的自适应性和自动生成测试数据的成功率。在遗传算法中，变异和交叉操作是非常重要的新个体产生手段，变异和交叉操作可以给种群带来新的基因，对遗传算法具有非常重要的意义。变异概率pm是遗传算法中的关键参数，变异操作的概率由变异概率Pm来决定。使用SAOGO策略定期的对群体中的染色体进行分析，当发现种群有出现早熟的征兆时，适时的提高Pm的取值，引入新的基因恢复染色体多

6、样性，让算法从进化停滞状态中恢复过来。同时选择其中较优的个体进行保存，对其不进行交叉和变异操作，提高个体的适应性。染色体的多样性得到恢复后，将Pm调整到正常值，以避免出现遗传算法的搜索性能退化。6可以把SAOGO看作为一个监视器，其包含的重要参数有：监测周期MC表示的间隔多长的时间对种群进行检查、重复比例PRI指某个染色体在种群中重复出现的比例、较优个体集EID指在种群中重复比例较高的染色体、优化持续时间PGA指进行相应的变异和交叉操作的时间和优化强度EMP指将变异概率调高的比例。SAOGO每隔MC轮对种群进行一次检查，如果有染色体在被种群中重复出现，且其比例已经超过预先设定PRI值，

7、SAOGO将会把变异概率的值改为预设的EMP值。同时把该染色体保存在EID中，该概率将会维持PGA轮，然后将变异概率恢复为正常值。图14实验和结果分析本文将以Triangle作为被检测程序，实际检验算法的效果。在软件测试研究中很多时候都把Triangle作为一个基准程序来使用，如图2为Triangle程序的流程控制图。实验开始前我们对遗传算法的参数做如下设置：种群大小初始化为M=60，染色体长度L=21，最大进化代数100，交叉概率pc=0.7