随着集成电路规模和复杂度的迅速提高，集成电路的测试工作变得更加复杂和重要。测试向量的生成速度和分布对测试收敛速度具有决定性的作用。数字电路可以分为时序逻辑和组合逻辑两类，使用全扫描设计技术可以将时序电路测试生成转变为组合电路的测试生成问题。因此，组合电路的自动测试模式生成（ATPG）问题成为研究的焦点。借助于近年SAT求解算法的研究成果，基于SAT的测试向量自动生成成为了研究热点。本文介绍了数字电路的故障模型、测试生成技术以及如何将数字电路故障测试问题转化为SAT问题。研究了SAT求解的经典算法(DPLL)、局部搜索算法和基于遗传算法的SAT求解过程。分析了遗传算法与SAT结合需要解决的两个问题，其一是在求解的过程中容易出现的早熟现象，其二是遗传算法本身局部最优与收敛速度的矛盾。提出了基于改进遗传算法的SAT求解器，针对SAT求解问题的特性对遗传算法的适应度函数、选择算子、交叉算子以及变异算子进行改进，改善了局部SAT求解算法的早熟现象。最后，对所提出的基于改进遗传算法的SAT求解器进行了仿真实验，实验结果表明改进后的遗传算法具有较高的求解效率，而且能够缓解收敛速度与局部最优解的矛盾，能够尽早地判断是否出现早熟现象并进行处理。