Enhancing Rule Construction in Grammatical Evolution with Advanced Crossover Techniques

Many real-world problems can be formulated as classification tasks in machine learning and addressed using a wide range of advanced algorithms developed for this purpose. Among these approaches, methods based on Grammatical Evolution (GE) can also be employed, such as GenClass, a technique designed to automatically construct classification rules. Although GenClass has been successfully applied to a variety of classification problems, its evolutionary search process may suffer from limitations such as entrapment in local minima of the error function and premature convergence, which can prevent the method from discovering high-quality classification rules. The present work proposes an enhanced version of GenClass through the introduction of advanced crossover techniques operating on the integer-valued chromosomes employed by the method, with the aim of improving the evolutionary search process and reducing classification error. The proposed crossover operators follow two different strategies. Some of them are purely stochastic, introducing greater diversity into the evolutionary search, whereas others exploit information already generated during the Grammatical Evolution process to perform targeted exchanges of genetic material between chromosomes. In this way, the latter operators attempt to guide the evolutionary search toward more promising regions of the search space while preserving useful information discovered during previous generations. The proposed techniques were evaluated on a diverse collection of real-world classification datasets, including several problems characterized by a large number of patterns and/or a large number of classes. The experimental results demonstrate that the Standard crossover strategy provides the most consistent improvement over the original GenClass method, reducing the average classification error from 16.13% to 13.42% across 31 classification datasets. This improvement remains statistically significant after excluding four related EEG-derived datasets and applying a correction for multiple comparisons. Among the three investigated crossover strategies, the simplest approach, Standard, achieved the lowest average classification error, whereas the more elaborate grammar-guided Targeted and TargetedWorst variants did not provide further improvements.