应用自适应差分进化算法优化软件测试数据的研究

作     者：翁晴晴 

作者单位：安徽大学 

学位级别：硕士

导师姓名：李龙澍

授予年度：2018年

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

主      题：软件测试 差分进化 反向学习 质心原理 自适应参数控制 

摘      要：软件测试作为保证软件产品质量的重要手段,一直以来受到行业人士及学者的关注。软件测试的主要目的是在测试过程中尽可能多地发现软件产品中存在的错误或潜在缺陷,很显然软件测试是软件开发过程中非常重要的环节。而软件测试中测试用例的生成效率及质量又影响着整个测试流程的效果,因此如何设计出一个高效的测试用例生成方法,对软件测试来说至关重要。差分进化算法是一种具有较强的全局收敛能力和鲁棒性的进化算法,属于基于群体的启发式优化算法的一种。差分进化算法本身具有容易实现、结构简单、鲁棒性强和收敛速度快等优势,能够很好地应用于软件测试用例的自动化产生。但是标准的差分进化算法需要人工依照先验知识事先设置好控制参数,并在后期不断调整以提高算法效率;而且同其他智能搜索算法类似,在算法进化后期易陷入局部最优,不能很好地直接用于软件测试用例的产生,因此如何改进差分进化算法对收敛速度和收敛精度的提高,更好的应用于测试用例的自动化产生非常重要。本文主要围绕自适应差分进化算法的优化展开研究,并及将其应用于基于路径覆盖的测试用例的自动化产生。主要工作在于:首先,本文对软件测试的重要性进行了概述;同时对现有的差分进化算法及自适应差分进化算法的优缺点进行了分析总结,并对差分进化算法的研究现状进行了概述:另外,介绍了软件测试的研究现状及测试用例生成的现有方法,并分析了各种方法的优缺点。第二,针对现有自适应差分进化算法容易陷入局部最优和收敛精度较低的问题,本文结合机器学习中的反向学习策略,提出了基于反向学习的增强型自适应差分进化算法(Opposition-based Learning of Adaptive Differential Evolution,OL-ADE)。改进后的OL-ADE算法通过反向精英学习机制,从用于变异策略的原有个体种群中得到反向精英个体种群,并从二者的种群集合中选择出适应度值更好的个体用于变异操作,这不仅丰富了种群的多样性,而且增强了种群在进化过程中的局部搜索能力;同时,采用高斯分布来动态调整变异操作中用于缩放的个体,提高了种群的单个个体的寻优能力。通过以上操作不仅扩充了种群多样性的,而且可以避免算法过早收敛,并在整体上对算法的全局搜索能力与局部寻优能力做出平衡。第三,在基于路径覆盖的测试用例的自动生成问题中,针对现有智能搜索算法存在的本身参数较多、算法的迭代次数多、测试数据生成效率不高等问题。本文提出了一种基于质心的自适应差分进化算法(Adaptive Differential Evolution based on Center of Mass,CADE),并用于测试用例的自动化生成。本文算法在变异策略选择阶段,利用质心原理的思想,对变异个体进行选择,该方法保证了种群向着最优值方向进化,加快了种群的收敛速度;同时利用控制参数的自适应调整来控制个体的缩放规模,提高种群多样性,从而保证种群在进化过程中因个体过于集中而陷入局部最优时,能跳出局部最优。为验证所提CADE算法的有效性,将其应用于软件测试用例的自动化产生,并与传统的算法进行对比。实验表明,本文优化后的算法,能够提高软件测试用例生成的效率和性能。