This work presents an evolutionary-based automatic technique for structure optimization of a deterministic test pattern generator. This kind of test pattern generator is composed of a specific linear register and a non-linear combinational function that can invert any bit in the generated patterns; as a result, any arbitrary test
sequence can be produced. Such a solution is suitable for on-line built-in self-test implementations where functional units are tested in their idle cycles. In order to reduce the gate count of the built-in self-test structure a genetic algorithm is employed. In contrast to conventional approaches our multi-objective approach
concurrently optimizes multiple parameters within multiple design aspects (type of register cells, order of patterns in the generated test sequence, bit-order of a test pattern) that influence the final solution. Experimental results with combinational benchmarks demonstrate the efficiency of the proposed evolutionary approach.