论文部分内容阅读
摘 要：针对遗传算法在运算过程中产生的早熟问题，提出一种自适应动态优化策略（SAOGO），用以自动生成测试数据。通过优化变异概率等手段，实现了路径测试数据的自动生成。将Triangle（三角形判别问题）作为被检测程序进行性能测试，实验结果表明，基于该策略的测试数据自动生成系统能自动调整变异概率和保持优秀个体，有效的解决了早熟问题，同时也提高了自动生成测试数据的效率。
关键词：软件测试；路径测试数据；自适应动态优化策略
中图分类号：TP311.52
随着计算机技术的飞速的发展，在各行各业中计算机都成为了一个重要的工具。与其相适应的的软件也在飞速发展，软件的规模和复杂度也提高很快。作为软件开发过程中重要的步骤——软件测试的规模和复杂度也相应的提高了很多。软件测试是一项昂贵而又耗费劳力的工作，往往占软件开发总工作量的50%左右[1]。测试数据的自动生成由其能提高软件测试的效率和减少成本，一直是人们研究的重要对象。近几年来，如何生成测试数据的已转化成如何搜索合适测试数据，这使自动生成测试数据的成为可能。利用遗传算法，并根据测试数据自动生成问题的特点，可以生成高效的路径测试数据自动生成算法，具有一定的理论意义和工程实用价值。
1 SAOGO策略的引入
遗传算法的性能受到两个重要因素的影响，即“选择压力”和“种群多样性”。在种群今后的过程中，如果选择压力太大将会导致种群很快被少量的个体占据，种群的多样性被破坏，导致算法的结果为局部最优。这样的情况严重的降低遗传算法的性能，这被称为进化停滞（evolution stagnation）问题或种群早熟（population premahirity）问题。但是，如果选择较低的选择压力，虽然可以加大算法搜索的结果为全局最优的概率，但是却会严重的降低搜索的效率，甚至是算法退化为随机算法，这将会对遗传算法的搜索效率产生严重的影响。研究者们提出了一些方法，可以预防种群早熟现象的出现：（1）对初始种群的规模设置尽量的大。在大规模的种群中因其含有比较多的个体，其染色体的性态也比较多样，发生算法收敛到局部最优的情况的可能性较低。（2）提高变异操作的变异概率。更多的进行编译操作可以增加种群的新基因，提高了种群的多样性，但较高的变异概率使搜索的随机性增强，有可能降低适应值函数的导向性，反而降低了遗传算法的性能。（3）使用选择压力较小的存活操作和选择操作[2-3]。以上几种方法都只是对遗传算法的优化了其静态配置，只能预防种群早熟问题。当种群早熟问题发生时，它们没有更好的方法来对种群恢复其多样性。研究表明，对搜索过程进行启发式的动态优化，能改善智能随机搜索法的性能[4]。我们认为在遗传算法的搜索中引入启发式的动态优化方法同样可能提高搜索的性能。我们提出了一种自适应动态优化策略SAOGO来动态调整Pm的取值和交叉对象，以解决进化停滞问题和加快最优解的产生。
2 SAOGO策略
SAOGO的基本思想是：对种群的进化情况进行监视，并根据监控的情况自动的调整算法的部分参数设置，以保证进化处于良好的状态。合适的动态优化方法能有效的提高算法的自适应性和自动生成测试数据的成功率。
在遗传算法中，变异和交叉操作是非常重要的新个体产生手段，变异和交叉操作可以给种群带来新的基因，对遗传算法具有非常重要的意义。变异概率pm是遗传算法中的关键參数，变异操作的概率由变异概率Pm来决定。使用SAOGO策略定期的对群体中的染色体进行分析，当发现种群有出现早熟的征兆时，适时的提高Pm的取值，引入新的基因恢复染色体多样性，让算法从进化停滞状态中恢复过来。同时选择其中较优的个体进行保存，对其不进行交叉和变异操作，提高个体的适应性。染色体的多样性得到恢复后，将Pm调整到正常值，以避免出现遗传算法的搜索性能退化。
可以把SAOGO看作为一个监视器，其包含的重要参数有：监测周期MC表示的间隔多长的时间对种群进行检查、重复比例PRI指某个染色体在种群中重复出现的比例、较优个体集EID指在种群中重复比例较高的染色体、优化持续时间PGA指进行相应的变异和交叉操作的时间和优化强度EMP指将变异概率调高的比例。
SAOGO每隔MC轮对种群进行一次检查，如果有染色体在被种群中重复出现，且其比例已经超过预先设定PRI值，SAOGO将会把变异概率的值改为预设的EMP值。同时把该染色体保存在EID中，该概率将会维持PGA轮，然后将变异概率恢复为正常值。
图1
4 实验和结果分析
本文将以Triangle作为被检测程序，实际检验算法的效果。在软件测试研究中很多时候都把Triangle作为一个基准程序来使用，如图2为Triangle 程序的流程控制图。
实验开始前我们对遗传算法的参数做如下设置：种群大小初始化为M=60，染色体长度L=21，最大进化代数100，交叉概率pc=0.7，变异概率pm =0.03[5]。SAOGO的参数设置：监测周期MC=10，重复比例PRI=8，优化持续时间PGA=4，优化强度EMP=0.7。
图2 流程控制图
图3
图4
在实验过程中我们发现SAOGO是否开启和变异次数有很大的关系，总的来说 SAOGO策略对遗传算法的影响有以下三点：（1）当SAOGO策略的使用，导致大量新的基因的引入，保证了种群的多样性，避免了早熟现象的出现。（2）本实验中在适应度最高的个体父体产生于SAOGO策略开启时，在后续进行的9次实验中，其中有7次的最优个体产生于策略开启时。（3）在实验过程中我们为了检查保护最优个体是否有利于提高种群适应度，我们对同一组数据进行了开关保护最优个体的策略，最终的实验结果表明在开启保护最优个体策略时，加速了最终结果的形成。
通过对SAOGO策略的参数不同参数的设置，我们得出了图3和图4，对其进行研究分析可以发现不同的参数设置对命中率的提高是有较大的差别的。在我们的实验中发现SAOGO策略的参数较优配置为：监测周期MC=10，重复比例PRI=6，优化持续时间PGA=4，优化强度EMP=0.75。
5 结束语
路径测试数据自动生成是程序结构测试的一个重要方面。本文针对遗传算法中早熟的现象，提出了自适应动态优化策略SAOGO。通过实验验证该策略在路径测试数据的自动生成中的应用，同时给出了相关参数的设定。
参考文献：
[1]Bogdan.Korel.Automated Software Test Transactions on software engineering，1990（08）Data Generation[J].IEEE：870-879.
[2]律亚楠.基于遗传算法的测试数据生成研究[D].汕头大学，2008.
[3]冷剑.基于遗传算法的软件测试技术的研究[D].东北大学，2008.
[4]史亮.测试数据自动生成技术研究[D].东南大学，2006.
[5]李军，李艳辉，彭存银.基于自适应遗传算法的路径测试数据生成[J].计算机工程，2009（01）.
作者简介：孙为（1979.09-），男，湖北仙桃人，讲师，本科，研究方向：计算机科学。
作者单位：琼台师范高等专科学校信息技术系，海口 571100
关键词：软件测试；路径测试数据；自适应动态优化策略
中图分类号：TP311.52
随着计算机技术的飞速的发展，在各行各业中计算机都成为了一个重要的工具。与其相适应的的软件也在飞速发展，软件的规模和复杂度也提高很快。作为软件开发过程中重要的步骤——软件测试的规模和复杂度也相应的提高了很多。软件测试是一项昂贵而又耗费劳力的工作，往往占软件开发总工作量的50%左右[1]。测试数据的自动生成由其能提高软件测试的效率和减少成本，一直是人们研究的重要对象。近几年来，如何生成测试数据的已转化成如何搜索合适测试数据，这使自动生成测试数据的成为可能。利用遗传算法，并根据测试数据自动生成问题的特点，可以生成高效的路径测试数据自动生成算法，具有一定的理论意义和工程实用价值。
1 SAOGO策略的引入
遗传算法的性能受到两个重要因素的影响，即“选择压力”和“种群多样性”。在种群今后的过程中，如果选择压力太大将会导致种群很快被少量的个体占据，种群的多样性被破坏，导致算法的结果为局部最优。这样的情况严重的降低遗传算法的性能，这被称为进化停滞（evolution stagnation）问题或种群早熟（population premahirity）问题。但是，如果选择较低的选择压力，虽然可以加大算法搜索的结果为全局最优的概率，但是却会严重的降低搜索的效率，甚至是算法退化为随机算法，这将会对遗传算法的搜索效率产生严重的影响。研究者们提出了一些方法，可以预防种群早熟现象的出现：（1）对初始种群的规模设置尽量的大。在大规模的种群中因其含有比较多的个体，其染色体的性态也比较多样，发生算法收敛到局部最优的情况的可能性较低。（2）提高变异操作的变异概率。更多的进行编译操作可以增加种群的新基因，提高了种群的多样性，但较高的变异概率使搜索的随机性增强，有可能降低适应值函数的导向性，反而降低了遗传算法的性能。（3）使用选择压力较小的存活操作和选择操作[2-3]。以上几种方法都只是对遗传算法的优化了其静态配置，只能预防种群早熟问题。当种群早熟问题发生时，它们没有更好的方法来对种群恢复其多样性。研究表明，对搜索过程进行启发式的动态优化，能改善智能随机搜索法的性能[4]。我们认为在遗传算法的搜索中引入启发式的动态优化方法同样可能提高搜索的性能。我们提出了一种自适应动态优化策略SAOGO来动态调整Pm的取值和交叉对象，以解决进化停滞问题和加快最优解的产生。
2 SAOGO策略
SAOGO的基本思想是：对种群的进化情况进行监视，并根据监控的情况自动的调整算法的部分参数设置，以保证进化处于良好的状态。合适的动态优化方法能有效的提高算法的自适应性和自动生成测试数据的成功率。
在遗传算法中，变异和交叉操作是非常重要的新个体产生手段，变异和交叉操作可以给种群带来新的基因，对遗传算法具有非常重要的意义。变异概率pm是遗传算法中的关键參数，变异操作的概率由变异概率Pm来决定。使用SAOGO策略定期的对群体中的染色体进行分析，当发现种群有出现早熟的征兆时，适时的提高Pm的取值，引入新的基因恢复染色体多样性，让算法从进化停滞状态中恢复过来。同时选择其中较优的个体进行保存，对其不进行交叉和变异操作，提高个体的适应性。染色体的多样性得到恢复后，将Pm调整到正常值，以避免出现遗传算法的搜索性能退化。
可以把SAOGO看作为一个监视器，其包含的重要参数有：监测周期MC表示的间隔多长的时间对种群进行检查、重复比例PRI指某个染色体在种群中重复出现的比例、较优个体集EID指在种群中重复比例较高的染色体、优化持续时间PGA指进行相应的变异和交叉操作的时间和优化强度EMP指将变异概率调高的比例。
SAOGO每隔MC轮对种群进行一次检查，如果有染色体在被种群中重复出现，且其比例已经超过预先设定PRI值，SAOGO将会把变异概率的值改为预设的EMP值。同时把该染色体保存在EID中，该概率将会维持PGA轮，然后将变异概率恢复为正常值。
图1
4 实验和结果分析
本文将以Triangle作为被检测程序，实际检验算法的效果。在软件测试研究中很多时候都把Triangle作为一个基准程序来使用，如图2为Triangle 程序的流程控制图。
实验开始前我们对遗传算法的参数做如下设置：种群大小初始化为M=60，染色体长度L=21，最大进化代数100，交叉概率pc=0.7，变异概率pm =0.03[5]。SAOGO的参数设置：监测周期MC=10，重复比例PRI=8，优化持续时间PGA=4，优化强度EMP=0.7。
图2 流程控制图
图3
图4
在实验过程中我们发现SAOGO是否开启和变异次数有很大的关系，总的来说 SAOGO策略对遗传算法的影响有以下三点：（1）当SAOGO策略的使用，导致大量新的基因的引入，保证了种群的多样性，避免了早熟现象的出现。（2）本实验中在适应度最高的个体父体产生于SAOGO策略开启时，在后续进行的9次实验中，其中有7次的最优个体产生于策略开启时。（3）在实验过程中我们为了检查保护最优个体是否有利于提高种群适应度，我们对同一组数据进行了开关保护最优个体的策略，最终的实验结果表明在开启保护最优个体策略时，加速了最终结果的形成。
通过对SAOGO策略的参数不同参数的设置，我们得出了图3和图4，对其进行研究分析可以发现不同的参数设置对命中率的提高是有较大的差别的。在我们的实验中发现SAOGO策略的参数较优配置为：监测周期MC=10，重复比例PRI=6，优化持续时间PGA=4，优化强度EMP=0.75。
5 结束语
路径测试数据自动生成是程序结构测试的一个重要方面。本文针对遗传算法中早熟的现象，提出了自适应动态优化策略SAOGO。通过实验验证该策略在路径测试数据的自动生成中的应用，同时给出了相关参数的设定。
参考文献：
[1]Bogdan.Korel.Automated Software Test Transactions on software engineering，1990（08）Data Generation[J].IEEE：870-879.
[2]律亚楠.基于遗传算法的测试数据生成研究[D].汕头大学，2008.
[3]冷剑.基于遗传算法的软件测试技术的研究[D].东北大学，2008.
[4]史亮.测试数据自动生成技术研究[D].东南大学，2006.
[5]李军，李艳辉，彭存银.基于自适应遗传算法的路径测试数据生成[J].计算机工程，2009（01）.
作者简介：孙为（1979.09-），男，湖北仙桃人，讲师，本科，研究方向：计算机科学。
作者单位：琼台师范高等专科学校信息技术系，海口 571100