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

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