软件测试是保障软件质量的重要手段,其目的是在测试过程中尽可能多地发现软件存在的缺陷,因而其在整个软件开发过程中占有特别重要的位置。测试数据的好坏直接决定着测试的效果,因此软件测试中关键的问题是设计有效的测试数据。已有研究表明,路径覆盖是一种非常重要的软件测试充分性准则;遗传算法是自动生成路径覆盖测试数据的有效方法,但是已有研究成果在测试数据的生成效率和检错率上都有待提高。本文研究使用遗传算法自动生成路径覆盖测试数据的理论及方法。　　首先,针对现有方法对穿越难以覆盖节点的稀有数据缺乏保护措施问题,提出了在测试数据进化生成中动态捕捉稀有数据的方法。通过统计每代种群中目标路径各节点被穿越的个体数量,得到个体对生成穿越目标路径测试数据的贡献,以此作为权重调整个体的适应度,使稀有数据的适应度增加,在后续进化中得到保留,从而提高测试数据的生成效率。　　其次,提出了一种新的多路径覆盖测试数据生成方法。将被测程序表示成一棵二叉树,对目标路径采用赫夫曼编码方法表示成二进制串,依此设计了一种新的适应度函数,综合考虑个体穿越路径与每个目标路径的匹配程度,将提出的方法用于多个基准程序的测试,并与已有方法比较,结果表明所提方法计算量小,生成测试数据效率高。　　第三,针对已有方法生成的测试数据不能有效发现被测程序的缺陷,尤其是小概率缺陷的问题,提出了一种面向缺陷的路径覆盖测试数据进化生成方法。分别针对单路径和多路径情况,将路径覆盖和缺陷检测问题转化为约束多目标优化问题,以测试数据运行被测程序时发现的缺陷个数和缺陷的危险程度为目标,以穿越目标路径为约束,建立了该问题的数学模型,并提出了有针对性的求解方法。在实际软件测试中的应用表明,所提方法生成的测试数据不但穿越了目标路径,而且能有效检测到目标路径中的缺陷。　　最后,提出基于搜索空间缩减的路径覆盖测试数据进化生成理论。针对单路径覆盖测试数据生成问题,先确定目标路径与输入变量之间的关系,将可分目标路径分离出与部分分量相关的独立子路径;进化生成测试数据的过程中,固定被穿越子路径对应的输入分量,并缩小交叉和变异操作的范围,使种群在不断缩小的空间里寻找测试数据;然后针对多路径覆盖测试数据生成问题,提出了基于搜索空间缩减的多种群遗传算法,该方法将目标路径按照具有相同子路径进行分组,并确定每组公共子路径对应的分量,使用多个子种群分别进化生成各组目标路径的测试数据,进化过程中固定子种群内被穿越子路径对应的输入分量,并缩小交叉和变异操作的范围,使每个子种群在不断缩减的空间里寻找测试数据,有效提高了每个子种群内目标路径测试数据的生成效率,进而提高多路径覆盖测试数据进化生成效率。　　本论文所做的工作为路径覆盖测试数据的自动生成提供了新的思路,丰富了基于进化优化的软件测试理论,提高了测试数据的生成效率,保证了测试数据的质量,降低了软件测试成本,具有重要的理论意义和实际应用价值。