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.
%0 Journal Article
%1 Butz:2007a
%A Butz, Martin V.
%A Goldberg, David E.
%A Lanzi, Pier Luca
%A Sastry, Kumara
%D 2007
%J Genetic Programming and Evolvable Machines
%K - LCS Learning Markov Mutation Niching Solution XCS analysis chain classifier sustenance systems
%P 5-37
%T Problem solution sustenance in XCS: Markov chain analysis of niche
support distributions and the impact on computational complexity
%V 8
%X 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.
@article{Butz:2007a,
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.},
added-at = {2009-06-26T15:25:19.000+0200},
author = {Butz, Martin V. and Goldberg, David E. and Lanzi, Pier Luca and Sastry, Kumara},
biburl = {https://www.bibsonomy.org/bibtex/2eaae3e93e2a06a4ef561f0ba5b15dcb9/butz},
description = {diverse cognitive systems bib},
interhash = {bf3fcf0f60dbb9030e15f7d9b4a2a201},
intrahash = {eaae3e93e2a06a4ef561f0ba5b15dcb9},
journal = {Genetic Programming and Evolvable Machines},
keywords = {- LCS Learning Markov Mutation Niching Solution XCS analysis chain classifier sustenance systems},
owner = {butz},
pages = {5-37},
timestamp = {2009-06-26T15:25:24.000+0200},
title = {Problem solution sustenance in {XCS}: Markov chain analysis of niche
support distributions and the impact on computational complexity},
volume = 8,
year = 2007
}