随着软件的飞速发展,人们对软件安全性的堪忧越来越深,软件的缺陷会造成巨大的财产损失,甚至危害人身安全。鉴于此软件测试已经逐渐成为软件工程赖以生存的重要保障。软件测试的目的是增强软件的可靠性,这是一项极其耗时的工作。在一个软件工程中,软件测试将花费近半的开发经费。一般来说测试的主要目标是用有限的测试数据,尽可能多的发现软件中潜在的错误。在这种情况下,测试用例的重要性是不可非议的,如何在减少所需测试数据量的同时增大路径覆盖率已经成为高效测试的关键。研究人员们在自动测试数据生成上提出了一系列的策略,然而这些策略都有一定的缺陷。一种新的软件测试数据生成的方法是,利用程序执行过程中产生的反馈信息,在可能的数据域搜寻最优解,这时测试数据的生成被看作是最优化问题,即利用启发式搜索算法进行寻优的问题。遗传算法是目前应用频率最高的搜索算法,它在测试数据生成领域中也取得了良好的效果。但是从性能来看,遗传算法仍然有一定的局限性,在一些问题上会陷入困境。本文引入Memetic算法,并将Memetic算法应用到测试数据生成中。它在遗传算法的基础上加入了局部搜索能力,能有效抑制早熟现象的产生。本文主要对Memetic算法在测试数据生成中涉及的适应度函数和局部搜索机制进行设计。然后通过实验结果分析Memetic算法的性能。本文将从两方面分析算法的性能——迭代时间和收敛速度,迭代时间指算法一次运行所需的时间;收敛速度依赖算法一次执行中需要的迭代次数,迭代次数越少,收敛速度越快。迭代时间代表着算法的执行能力,收敛速度代表着算法的搜索能力。多路径覆盖的测试数据生成也是提高测试数据生成效率的一种可靠的途径,它能够利用路径相似性,减少重复迭代所耗费的时间。本文利用Memetic算法来实现多路径测试数据生成,研究它的具体设计方法并分析其性能。但是在多路径测试数据生成中也暴露出Memetic算法的迭代时间较长的缺点,因此从平均迭代时间的角度考虑,本文引入粒子群算法(PSO)的思想对Memetic算法进行改进,PSO算法的局部性能有效增强Memetic算法的局部搜索能力,同时它的计算量较小,可以减少Memetic算法的迭代时间。最后本文通过实验将Memetic算法与改进后的Memetic算法进行对比。实验表明Memetic算法可以提高测试数据生成效率,它在单路径和多路径的测试数据生成中表现出的性能均优于遗传算法。