This paper presents a new approach to design and 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. Such a TPG is suitable for on-line built-in self-test (BIST) implementations where functional units are tested in their idle cycles. To reduce the gate count of the BIST structure a genetic algorithm (GA) is employed. This approach and its multi-objective nature allows concurrent optimization of multiple parameters within multiple design aspects (register cells type, patterns order in the generated test sequence, bit order of a test pattern), which influence the final solution. Experimental results on combinational ISCAS benchmarks demonstrate the efficiency of the proposed evolutionary approach.