This paper presents a proposal to improve REGAL, a concept learning system based on a distributed genetic algorithm that learns first-order logic multi-modal concept descriptions in the field of classification tasks. This algorithm has been a pioneer system and source of inspiration for others. Studying the philosophy and experimental behaviour of REGAL, we propose some improvements based principally on a new treatment of counterexamples that promote its underlying goodness in order to achieve better performances in accuracy, interpretability and scalability, so that the new system meets the main requirements for classification rules extraction in data mining. The experimental study carried out shows valuable improvements compared with both REGAL and G-Net distributed genetic algorithms and interesting results compared with some state-of-the-art representative algorithms in this field. © 2010 Springer-Verlag.