We present an evolutionary algorithm which predicts stable atomic structures and phase diagrams by searching the energy landscape of empirical and ab-initio Hamiltonians. Composition and geometrical degrees of freedom may be varied simultaneously. We show that this method utilizes information from favorable local structure at one composition to predict that at others, achieving far greater efficiency of phase diagram prediction than a method which relies on sampling compositions individually. We detail this and a number of other efficiency-improving techniques implemented in the Genetic Algorithm for Structure Prediction (GASP) code that is now publicly available. Applications are presented in three categories. First, we predict phase diagrams of elemental barium and europium under pressure and show that our methodology compliments experimental studies of those systems. Second, we show that phase diagram prediction is a primary component of ab initio Li-ion battery electrode characterization. We present studies of the Li-Si and Li-Ge binary phase diagrams that allow us to determine the voltage characteristics of silicon and germanium battery anodes. We also predict the stability of previouslyunreported binary structures in both of those materials systems. Third, we use the method to test empirical energy models. It is important that such models reproduce the energy landscape of the true system they are meant to represent. The GASP code can verify this if it is so and find errenous structures to augment the fitting database if it is not. Our results suggest that genetic algorithm searches can be used to improve the methodology of empirical potential design. This thesis takes advantage of the Cornell graduate school's "papers" option. That is, it is primarily composed from the author's first-author publications, in particular, Refs. [149, 148, 152, 151]. Additionally, one of the pleasures of computational materials science research is that it has a synergistic relationship with experiment and lends itself to many fruitful collaborations. These provide insights and richer publications than would be possible by either path alone. Thus this thesis also describes applications of our methodology to collaborative works described in Refs. [17, 145, 114]. In these cases, I focus on my own contributions in this thesis and refer the reader to the original publications for the full picture.