In this paper, we present maintenance cost optimization techniques under reliability constraints based on evolutionary algorithms for complex systems in the context of the Reliability-Centered-Maintenance (RCM). Our main goal is to find the best maintenance policy for this system by minimizing the maintenance cost function of the system, under the constraint of the required reliability for a given period. This policy identifies the optimum times in which the components must perform preventive maintenance (PM). The maintenance cost can be considered as a PM, an unscheduled maintenance (UM) and a replacement maintenance (RM) cost. The PM action is, therefore, considered to have an imperfect effect on the component in this work. The imperfect PM is executed whenever the component reliability reaches a certain threshold. The proposed method allows us to find the reliability threshold *i* = 1, 2,*n*) correspond to the optimal reliability threshold. In this study, we use the evolutionary algorithm to find the optimal reliability threshold *j*. A comparative study is performed to evaluate the performance of the Lévy-flight firefly (LFA) algorithm and particle swarm optimization (PSO) algorithm in finding the global optimum.