This work explores different evolutionary approaches to Protein
Structure Prediction (PSP), a highly constrained problem. These
are the utilization of a repair procedure, and the use of
evolutionary operators whose functioning is closed in feasible
space. Both approaches rely on hybridizing the evolutionary
algorithm (EA) with a backtracking algorithm. The so-obtained
hybrid EAs are described, and empirically compared to a
penalty-based EA. The utilization of the repair procedure reveals
itself as a very appropriate technique for tackling this problem.