Abstract: How to solve the problem of Automatic Test Pattern Generation（ATPG） of combinational circuits more efficiently is an important issue for VLSI.By the research of Ant Colony Optimization（ACO） algorithm which solves different types of optimization and search problems，on basis of the path sensitization method of combinational circuits，with a deterministic algorithm tool of boolean satisfiability（SAT），a new ATPG algorithm of combinational circuits based on ACO is presented.Results of the experiments indicate that the ACO algorithm is feasible.

Key words: Automatic Test Pattern Generation（ATPG）, Satisfiability（SAT） problem, ant colony optimization, combinational circuit

摘要： 如何高效地解决数字电路测试生成问题是VLSI领域中的核心。通过对蚁群算法在不同类型的组合优化和搜索问题上的应用研究，基于组合电路测试的路径敏化方法，借助SAT确定性算法工具，提出了一个新的蚁群算法模型来解决组合电路测试生成问题，并通过实验验证其可行性。

关键词: 自动测试图形生成, 可满足性问题, 蚁群算法, 组合电路