Illinois Genetic Algorithms Laboratory

Butz, M., Kovacs, T., Lanzi, P. L., Wilson, S. W. (2002)
TR No.: 2002011 | Download PDF | Download PS

Abstract:
The XCS classifier system evolves accurate, maximally general solutions to a wide variety of machine learning, data, and robotics problems, but a theoretical basis for these properties has not been presented. This paper develops and tests a model for the generalization pressure, and establishes conditions for the existence of effective fitness or accuracy pressure in XCS. The conditions, termed “challenges”, are tested on very large Boolean multiplexer problems, which XCS learns successfully when initialized according to the conditions. The extent to which the reward landscape can provide fitness guidance for the genetic algorithm is also examined. The work provides rules of thumb for applying XCS to large problems, and lays the foundation for research on XCS’s learning complexity.