Illinois Genetic Algorithms Laboratory

Butz, M. V., Goldberg, D. E., Lanzi, P. L., Sastry, K. (2004)
TR No.: 2004033 | Download PDF | Download PS

Abstract:
Michigan-style learning classifier systems evolve a problem solution maintaining a set of sub-solutions distributed to potentially overlapping problem subspaces. Together, the set of sub-solutions, represented by rules, represents the complete problem solution. An obvious challenge for such an evolving, distributed knowledge representation is the continuous support of all problem subspaces, that is, the niche support. This paper analyzes niche support in the accuracy-based learning classifier system XCS. We show that niche support is ensured by a niche-based deletion method plus an occurrence-based reproduction method. Dependent on niche occurrence and the number of niches, XCS is able to support a certain number of niches that satisfy a certain frequency of occurrence. The additional effect of overlapping niches is also evaluated. As a whole, the paper shows that XCS is able to maintain a number of overlapping niches with a computational effort that is linear in the inverse of the niche frequency to-be maintained. All results are supported by experimental evidence in Boolean function problems.