We consider two-dimensional phononic crystals formed from silicon and voids, and present optimized unit-cell designs for the following modes of elastic wave propagation: (1) out-of-plane, (2) in-plane, (3) combined out-of-plane and in-plane, and (4) flexural (on the basis of Mindlin plate theory). To feasibly search through an excessively large design space (similar to 10(40) possible realizations) we develop a specialized genetic algorithm and utilize it in conjunction with the reduced Bloch mode expansion method for fast band-structure calculations. Focusing on high-symmetry plain-strain square lattices, we report unit-cell designs exhibiting record values of normalized band-gap size for all four categories. For the case of combined polarizations, we reveal a smoothened design with a normalized band-gap size exceeding 60%. For the thin-plate problem, a manufacturable design is presented with a normalized band gap in excess of 57%.