Recent years have seen great advances in our ability to predict crystal structures from first principles. However, previous algorithms have focused on the prediction of bulk crystal structures, where the global minimum is the target. Here, we present a general atomistic approach to simulate in multicomponent systems the structures and free energies of grain boundaries and heterophase interfaces with fixed stoichiometric and non-stoichiometric compositions. The approach combines a new genetic algorithm using empirical interatomic potentials to explore the configurational phase space of boundaries, and thereafter refining structures and free energies with first-principles electronic structure methods. We introduce a structural order parameter to bias the genetic algorithm search away from the global minimum ( which would be bulk crystal), while not favouring any particular structure types, unless they lower the energy. We demonstrate the power and efficiency of the algorithm by considering non-stoichiometric grain boundaries in a ternary oxide, SrTiO(3).