Recognizing faces with altered appearances is a challenging task and is only now beginning to be addressed by researchers. The paper presents an evolutionary granular approach for matching face images that have been altered by plastic surgery procedures. The algorithm extracts discriminating information from non-disjoint face granules obtained at different levels of granularity. At the first level of granularity, both pre and post-surgery face images are processed by Gaussian and Laplacian operators to obtain face granules at varying resolutions. The second level of granularity divides face image into horizontal and vertical face granules of varying size and information content. At the third level of granularity, face image is tessellated into non-overlapping local facial regions. An evolutionary approach is proposed using genetic algorithm to simultaneously optimize the selection of feature extractor for each face granule along with finding optimal weights corresponding to each face granule for matching. Experiments on pre and post-plastic surgery face images show that the proposed algorithm provides at least 15% better identification performance as compared to other face recognition algorithms. © 2011 IEEE.