This paper presents a new parallel memetic algorithm (PMA) for solving the problem of classification in the process of Data Mining. We focus our interest on accelerating the PMA. In most parallel algorithms, the tasks performed by different processors need access to shared data, this creates a need for communication, which in turn slows the performance of the PMA. In this work, we will present the design of our PMA, In which we will use a new replacement approach, which is a hybrid approach that uses both Lamarckian and Baldwinian approaches at the same time, to reduce the quantity of informations exchanged between processors and consequently to improve the speedup of the PMA. An extensive experimental study performed on the UCI Benchmarks proves the efficiency of our PMA. Also, we present the speedup analysis of the PMA.