An analysis of generalization in XCS with symbolic conditions

We analyze generalization in the extended classifier system (XCS) with symbolic conditions, based on genetic programming, briefly XCSGP. We start from the results presented in the literature, which showed that XCSGP could not reach optimality in Boolean problems when classifier conditions involved logical disjunctions. We apply a new implementation of XCSGP to the learning of Boolean functions and show that our version can actually reach optimality even when disjunctions are allowed in classifier conditions. We analyze the evolved generalizations and explain why logical disjunctions can make the learning more difficult in XCS models and why our version performs better than the earlier one. Then, we show that in problems that allow many generalizations, so that or clauses are less "convenient", XCSGP tends to develop solutions that do not exploit logical disjunctions as much as one might expect. However, when the problems allow few generalizations, so that or clauses become an interesting way to introduce simple generalizations, XCSGP exploit them so as to evolve more compact solutions.