Genetic Algorithms for Sequential Circuit Test Generation

Abstract

Genetic algorithms (GAs) are computational procedures that mimic the natural process of evolution. GAs have found increased popularity in solving optimization problems in the past several years. In this talk, we address the application of GAs to the problem of sequential circuit test generation, which is known to be a very difficult problem. Numerous heuristics are typically used in deterministic algorithms for test generation to speed up the process, but execution time is still on the order of days and weeks for large industrial circuits. When GAs are used for simulation-based test generation, significant reductions in execution time are observed, and fault coverages increase as well if appropriate encodings and fitness functions are used.

The talk will begin with an overview of the two basic types of GAs, GA terminology, and genetic operators. A simple test generation example will then be used to illustrate the operation of a GA. A GA framework for test generation will be presented next, and results of experiments to evaluate various GA parameters will be given. Integration of GAs with deterministic algorithms and incorporation of problem-specific knowledge in the form of finite state machine sequences will be discussed. The talk will conclude by describing how the GA framework can be applied to the problem of test sequence compaction.