Data Complexity and Evolutionary Learning

We study the behavior of XCS, a classifier based on genetic algorithms. XCS summarizes the state-of-the-art of the genetic based machine learning field and benefits from long experience and research in the area. We describe the learning mechanisms of XCS by which a set of rules describing the class boundaries is evolved. We study XCS's behavior related to data complexity and identify conditions of difficulty for XCS in the complexity measurement space as those with long boundaries, high class interleaving, and high nonlinearities. Comparison with other classifiers in the complexity space allows to identify domains of competence for XCS as well as domains of poor performance. The study lays the basis to further apply the same methodology to analyze the domains of competence of other classifiers.