基于蚁群算法的结构测试数据自动生成方法研究

作     者：胡馨月 

作者单位：哈尔滨工程大学 

学位级别：硕士

导师姓名：张国印

授予年度：2020年

学科分类：12[管理学] 1201[管理学-管理科学与工程(可授管理学、工学学位)] 081104[工学-模式识别与智能系统] 081203[工学-计算机应用技术] 08[工学] 0835[工学-软件工程] 0811[工学-控制科学与工程] 0812[工学-计算机科学与技术（可授工学、理学学位）] 

主      题：软件测试 数据自动生成 不可行路径 蚁群算法 进化策略 

摘      要：自动化测试的应用越来越广泛,其中基于启发式搜索算法的测试数据自动生成方法由于其覆盖能力强、生成速度快,而广受关注。路径覆盖已被证实是发现错误能力最强的覆盖标准,所以本文从路径入手,先用基于关键点路径的测试数据自动生成模型进行路径预处理,筛掉易覆盖和不可行路径,剩下的难覆盖路径用全局性极强的蚁群算法进行覆盖。本文先就关键点模型中的不可行检测方法提出改进,然后对蚁群算法提出改进,最后把它们结合为一个完整的测试模型。本文主要工作如下:先针对关键点路径模型中不可行路径检测方法检测不全面、用时长的问题,提出动静结合的不可行路径检测方法,在分析阶段结合静态法和动态法的优势。在已有的用关联分析提取条件判断语句间相关性的方法基础上,引入数据流分析,把赋值语句与条件判断语句间的相关性也提取出来,有效提高检测的精度。然后针对基本蚁群算法初期局部搜索随机,导致收敛过慢,以及整体覆盖率低的问题,提出了具有进化策略的蚁群算法。在局部搜索中加入进化策略,使用高斯变异算子,使蚂蚁不再随机移动,增强蚂蚁局部搜索的能力。还增加了信息素的新定义,阻止蚂蚁访问已被遍历过的分支,避免产生冗余解,增加开发新路径的能力。增加新的布尔适应度函数,若当前蚂蚁已成功遍历至少一个新分支,则不用全局转移,加快生成速度。最后选出多个适合评估分支可达性的基准程序做对比实验,并根据多个指标分析实验结果,对比本文算法与改进前的算法、现有通用算法的性能。实验证明,本文方法能够提高生成的测试数据的覆盖率,加快收敛速度,对数值水池的测试自动化工作具有价值。