Protein structure prediction is one of the main challenges in Bioinformatics. An useful representation for protein 3D structure is the protein contact map. In this work, we propose an evolutionary approach for contact map prediction based on amino acids physicochemical properties. The evolutionary algorithm produces a set of rules that identifies contacts between amino acids. The rules obtained by the algorithm imposes a set of conditions on four amino acid properties in order to predict contacts. Results obtained confirm the validity of the proposal. © 2011 Springer-Verlag.