We propose an improved prediction method of the tertiary structures of $alpha$-helical membrane proteins based on the replica-exchange method by taking into account helix deformations. Our method allows wide applications because transmembrane helices of native membrane proteins are often distorted. In order to test the effectiveness of the present method, we applied it to the structure predictions of glycophorin A and phospholamban. The results were in accord with experiments.