Group I/II materials exhibit unexpected structural phase transitions at high pressures, providing potential insight into the origins of elemental superconductivity. We present here a computational study of elemental barium and binary sodium-calcium alloys to identify both known and unknown phases of barium under pressure, as well as stable high-pressure compounds in the immiscible Na-Ca system. To predict stability, we performed density functional theory calculations on randomly generated structures and evolved them using a genetic algorithm. For barium, we observed all of the expected phases and a number of new metastable structures, excluding the incommensurate Ba-IV structure. We also observed a heretofore unreported structure ($\alpha$-Sm) predicted to be the ground state from 30-42 GPa. In the Na-Ca system, we demonstrate feasibility of our search method, but have been unable to predict any stable compounds. These results have improved the efficacy of the genetic algorithm, and should provide many promising directions for future work.