This paper describes a new interleaver construction technique for turbo code. The technique searches as much as possible pseudo-random interleaving patterns under a certain condition using genetic algorithms(GAs). The new interleavers have the superiority of the S-random interleavers and this interleaver construction technique can reduce the time taken to generate pseudo-random interleaving patterns under a certain condition. Tbe results obtained indicate that the new interleavers yield an equal to or better performance than the Srandom interleavers. Compared to the S-random interleaver,this design requires a lower level of computational complexity.