Computing Optimal Populations for Binary Problems using Logic Minimization

The study of generalization in XCS has been mainly focused on single-step binary problems for which the optimal (accurate, maximally general) solution is known. In contrast, binary multi-step problems have primarily been studied in terms of performance. However, while there is an intuitive notion of generalization in multi-step environments, the optimal solutions for even the simplest multi-step problems are still unknown. This paper presents an approach to compute the optimal solutions for single-step and multi-step binary problems starting from their tabular solution. We first illustrate the approach using Boolean functions for which the optimal solutions are known. Then, we apply it to compute, for the first time, the optimal solutions for theWoods problems that have been used as a testbed to study XCS behavior in multi-step problems. The solutions confirm early intuitions on simple environments and shed new light on more complex problems. We compare the optimal solutions our approach computes with the condensed populations that XCS can evolve, showing that XCS consistently evolves a number of minimal solutions that increases with the number of learning problems. Finally, we extend our approach to compute the minimal representation of evolving classifier populations and compare the size of the evolved populations before and after condensation with their minimized counterparts.