We present a new and simple algorithmic approach to help predict protein structures from amino acid sequences based on energy minimization. In the search for the minimal energy conformation, we analyze and exploit the protein structures found at the various local minima to direct the search the global minimum. As such, we explore the energy landscape efficiently by considering only the space of local minima instead of the whole feasible space of conformations. Our specific algorithmic approach is comprised of two different elements: local minimization and operators from genetic algorithms. Unlike existing hybrid approaches where the local optimization is used to fine-tune the solutions, we focus primarily on the local optimization and employ stochastic sampling through genetic operators for diversification. Our empirical results indicate that each local minimum is representative of the substructures contained in the set of solutions surrounding the local minima. We applied our approach to determining the minimal energy conformation of proteins from the protein data bank (PDB) using the CHARMM and UNRES energy model. We compared against standard genetic algorithms and Monte Carlo approaches as well as the conformations found in the PDB as the baseline. In all cases, our new approach computed the lowest energy conformation.