This paper proposes a new memetic approach to address the problem of obtaining the optimal set of individual Self-Similar Contractive Functions (SSCF) for the reconstruction of self-similar binary IFS fractal images, the so-called SSCF problem. This memetic approach is based on the hybridization of the modified cuckoo search method for global optimization with a new strategy for the Levy flight step size (MMCS) and the adaptive step size random search (ASSRS) heuristics for local search. This new method is applied to some illustrative examples of self-similar fractal images with satisfactory graphical and numerical results. Our approach represents a substantial improvement with respect to a previous method based on the original cuckoo search algorithm for all contractive functions of the examples in this paper.