The Protein Structure Prediction (PSP) problem consists of predicting the structure of a protein from its amino acids sequence, and have received much attention lately. In fact, being able to predict the structure of a protein, would allow to know the function of the protein. In this paper, we propose a multi-objective evolutionary algorithm for the PSP problem. The prediction model consists of a set of rules that determine possible contacts between amino acids. Such rules are based on four specific amino acid properties, which are involved in the folding process: hydrophobicity, polarity, net charge and residue size. In order to increase the interpretability of the results, rules are organized in a 20x20 matrix where each cell contains the specific rules for a possible pair of residues. The high accuracy values obtained confirm the validity of our proposal. © 2011 IEEE.