In many real world optimization problems, including Redundancy Allocation Problem (RAP), there is a need to optimize more than one objective function simultaneously. In this paper, a new multi objective formulation is presented for the RAP by considering the reliability and cost of the system as the objective functions. The previous formulations have been proposed based on the assumption that all components of a subsystem are homogeneous. This constraint leads to an increase in the designing cost and prevents from reaching to higher quantities of the system reliability. The presented formulation in this research provides an opportunity for the subsystems components to be non-homogeneous in the required conditions. Due to the complexity of the RAPs, a Multi-objective Evolutionary Algorithm (MOEA) namely, Non-dominated Sorting Genetic Algorithm II (NSGA-II) is developed to identify the Pareto optimal front. The results show that in addition to a high capability in generating the Pareto optimal solutions, the proposed NSGA-II has a high efficiency in increasing the system reliability and reducing the designing costs simultaneously. (C) 2017 Elsevier Ltd. All rights reserved.