This paper presents a bio-inspired technique for the generation of a deterministic test pattern generator. In contrast to conventional methods, the proposed evolutionary-based approach reduces the gate count of a built-in self-test structure, which is used for the automatic fault detection. The reduced-gate-count structure is needed to achieve the test structure with a smaller hardware area overhead, while still satisfying the reliability constraints. The presented optimization approach searches concurrently for the optimal combination of the register cells structure, the test patterns order in the generated test sequence, and the bit order of the test patterns. A comparison of the results with similar studies shows the efficiency of the proposed evolutionary approach, which is therefore very useful in the design of robust and fault-tolerant systems, while maintaining the minimum size of the hardware overhead.