测试数据生成是软件测试中最繁琐的过程，通过自动化方法生成测试数据将有效降低测试成本，提高软件测试的效率。近年来，随着智能计算的兴起，学者们开始考虑利用现代启发式搜索算法帮助求解复杂的软件测试问题。该方法被称为基于搜索的软件测试（Search Based Software Testing，SBST），并且已经成为测试数据自动生成领域的一个重要研究方向。在SBST中，测试数据生成问题被转化为最优化问题。具体来说，首先设计适度函数以评价候选测试数据的质量，然后利用启发式算法搜索适度函数的最优解，该最优解即为目标测试数据。　　适度函数和启发式算法是SBST中最关键的组成部分。然而，目前关于SBST的研究大多数集中于启发式算法而忽视了适度函数的设计。本文试图弥补这方面的研究缺陷。适度函数用于表达问题的启发式信息，利用这些信息，启发式算法才能进行高效的搜索。如果适度函数不能充分挖掘问题的启发式信息，那么任何启发式算法的搜索性能都会接近随机搜索。因此，适度函数的设计是SBST中最核心的问题。在本文中，针对分支覆盖问题，我们提出了一种动态适度函数，该适度函数利用一个负指数模型对程序中必要分支的覆盖难度进行评估，并且通过近似算法对测试数据的适度值进行高效计算;针对路径覆盖问题，我们提出了一种自适应性适度函数，该适度函数通过一种自适应的方式调整目标路径上的分支权重，使适度函数尽可能多地表达问题的启发式信息，降低启发式算法的搜索难度。此外，我们利用集成方法，通过结合多个弱的适度函数，获得一个更强的适度函数，并且通过结合多个优势互补的启发式算法，构成一个超启发式算法。实验分析表明这些方法在测试数据生成的有效性方面具有明显的优势。　　最后，本文将SBST的思想用于求解Petri网可达性问题。具体来说，通过Petri网的状态方程和极小T-不变量挖掘网结构的启发式信息，然后设计适度函数用于评价变迁序列的质量，在此基础上，提出一种模拟树生长算法生成Petri网系统的部分状态空间，以达到状态压缩的目的。由于可达性问题的难解性以及Petri网本身的不确定性，导致该问题的适度函数难以设计，因此目前相关的研究资料很少。本文首次将SBST的方法用于求解一般的Petri网可达性问题，实验结果表明该方法在缓解状态爆炸问题方面具有一定的优势。