Problem solution sustenance in XCS: Markov chain analysis of niche support distributions and the impact on computational complexity
27 September 2006Butz, M. V., Goldberg, D. E., Lanzi, P. L., Sastry, K. (2006) Genetic Programming and Evolvable Machines. [ Springer Link] [Preprint Report - PDF] [Preprint Report - PS].
Abstract:
Michigan-style learning classifier systems iteratively evolve a distributed solution to a problem in the form of potentially overlapping subsolutions. Each problem niche is covered by subsolutions that are represented by a set of predictive rules, termed classifiers. The genetic algorithm is designed to evolve classifier structures that together cover the whole problem space and represent a complete problem solution. An obvious challenge for such an online evolving, distributed knowledge representation is to continuously sustain all problem subsolutions covering all problem niches, that is, to ensure niche support. Effective niche support depends both on the probability of reproduction and on the probability of deletion of classifiers in a niche. In XCS, reproduction is occurrence-based whereas deletion is support-based. In combination, niche support is assured effectively. In this paper we present a Markov chain analysis of the niche support in XCS, which we validate experimentally. Evaluations in diverse Boolean function settings, which require non-overlapping and overlapping solution structures, support the theoretical derivations. We also consider the effects of mutation and crossover on niche support. With respect to computational complexity, the paper shows that XCS is able to maintain (partially overlapping) niches with a computational effort that is linear in the inverse of the niche occurrence frequency.
Related Posts:
- Toward routine billion-variable optimization using genetic algorithms
- Towards billion bit optimization via efficient genetic algorithms
- Sub-structural niching in non-stationary environments
- Sporadic model building for efficiency enhancement of the hierarchical BOA
- Combating user fatigue in iGAs: Partial ordering, support vector machines, and synthetic fitness
No comments yet
