A symbolic fault simulator is integrated in a Genetic Algorithm (GA) environment to perform Automatic Test Pattern Generation (ATPG) for synchronous sequential circuits. In a two phase algorithm test length and fault coverage as well are optimized. However, there are circuits with bad random testability properties, that are also hard to test using genetically optimized test patterns. Thus, deterministic aspects are included in the GA environment to improve fault coverage. Experiments demonstrate that tests with higher fault coverages and considerably shorter test sequences than in previously presented approaches are obtained.