The paper presents an automatic technique for structure optimization of a deterministic test pattern generator (TPG). The TPG is composed of a linear register and a non-linear combinational function that can invert any bit in the generated patterns. Consequently, any arbitrary test sequence can be produced. This kind of a TPG is suitable for on-line built-in self-test (BIST) implementations where a set of deterministic test patterns is required. In order to reduce the gate count of the BIST structure a genetic algorithm (GA) is employed. In contrast to conventional approaches, a GA concurrently optimizes multiple parameters that influence the final solution. Experimental results on ISCAS benchmarks demonstrate the efficiency of the approach.