Based on the two-stage genetic algorithm with mixed variables, both the topological configuration and the material parameters were considered to optimize a two dimensional solid/solid phononic crystals, and a wide-low frequency band-gap was obtained. The results show that both the material density and the elastic modulus of the scattering body have important effects on the band-gap characteristics of phononic crystals, but the higher elastic modulus is more likely to produce the wider low frequency band-gap. When the scattering body has a higher elastic modulus, the relative bandwidth of the phononic crystal can be greatly increased, and the density can further exert in modulation. Moreover, the larger the density difference and the elastic modulus difference between the scatterer and the matrix, the easier to produce a wider band-gap. This provides a theoretical basis for the band-gap modulation and design of phononic crystals.