This paper discusses the NP-complete problem of reconfiguring two-dimensional degradable processor arrays under the row and column rerouting constraints. One major drawback of the previous algorithms is that a rerouting scheme to construct logical rows/columns can be applied only in one direction, either row or column direction, to handle the difficulty of this reconfiguration problem. We propose a new approach for the reconfiguration of degradable processor arrays employing a genetic algorithm (GA). The GA is used to evolve rerouting strategies for constructing logical rows/columns. A strategy based rerouting scheme is proposed to reroute the inter-connections of fault-free PEs in both row and column directions. The performances of our algorithm are compared with previous studies and it indicates that the proposed algorithm achieves better results in terms of harvest and degradation.