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

作     者：程孟飞 

作者单位：牡丹江师范学院 

学位级别：硕士

导师姓名：丁蕊

授予年度：2023年

学科分类：08[工学] 081104[工学-模式识别与智能系统] 0811[工学-控制科学与工程] 

主      题：遗传算法 多路径覆盖 测试数据生成 佳点集 并行种群 超启发式算法 

摘      要：基于遗传算法的多路径覆盖测试数据自动生成技术是为解决人工测试易错和测试成本高的问题产生的,作为一种高效的白盒测试技术,已在软件测试领域被广泛应用。随着软件规模和功能的复杂化,仍存在需要进一步解决的困难问题:比如算法过早收敛问题、种群多样性单一导致陷入局部最优问题、大搜索范围内测试数据生成效率低、缺乏理论指导以及算法设计难度大的问题等。针对上述问题,本文研究提高多路径覆盖测试数据生成效率的方法。主要工作如下:1.在基于传统遗传算法的测试数据生成问题中,容易出现过早收敛和路径覆盖率低的问题。利用佳点集误差小、精度高的优点,提出一种改进的佳点集遗传算法进行多路径覆盖测试数据的生成。算法首先根据混沌学习策略生成初始种群;然后使用佳点集和混沌方法改进遗传算法的交叉算子,并设计了考虑个体穿越路径与目标路径矩阵间相似度和分支距离相结合的适应度函数;实验表明,所提算法能有效缓解交叉算子精度低导致的过早收敛和路径覆盖率低的问题。2.在所提佳点集遗传算法的基础上,针对相似度高及搜索空间大的软件,提出一种基于移民并行种群遗传算法测试数据生成方法,用于解决测试数据生成中出现的搜索效率不佳问题。首先,利用一维线性混沌映射和反向学习方法生成反向种群;然后,设计改进的层接近度和分支距离相结合的适应度函数;最后,利用对路径插装个体穿越该路径的分支距离信息,提高未覆盖路径测试数据的搜索效率。在算法迭代过程中,各种群间设置移民算子生成精英种群,反向种群内使用预选择策略,动态优化子代种群。理论分析及实验验证说明了方法的有效性。3.众多算法的涌现扩大了软件程序的搜索范围,如何确定适合的算法来解决测试数据生成问题带来了严峻的挑战,因此如何选择合适的启发式算法指导生成测试数据又成为一个难题。为此,在上述两种改进方法的研究基础上,提出一种基于超启发式算法的测试数据生成方法。首先,建立基于超启发式算法的测试数据生成方法模型;然后,对于超启发式算法的高层策略层采用随机选择机制,低层算法库采用结合测试数据生成问题设计的3种不同交叉算子和2种变异算子结合构造形成的6种算法;对基准程序和工业程序的实验说明了本方法的有效性。