Abstract
In this paper we take initial steps toward a theory of generalization and
learning in the learning classifier system XCS. We start from Wilson's
generalization hypothesis which states that XCS has an intrinsic tendency to
evolve accurate, maximally general classifiers. We analyze the different
evolutionary pressures in XCS and derive a simple equation that supports the
hypothesis theoretically. The equation is tested with a number of experiments
that confirm the model of generalization pressure that we provide. Then, we focus
on the conditions, termed ``challenges'', that must be satisfied for the
existence of effective fitness or accuracy pressure in XCS. We derive two
equations that suggest how to set the population size and the covering
probability so as to ensure the development of fitness pressure. We argue that
when the challenges are met, XCS is able to evolve problem solutions reliably.
When the challenges are not met, a problem may provide intrinsic fitness guidance
or the reward may be biased in such a way that the problem will still be solved.
The equations and the influence of intrinsic fitness guidance and biased reward
are tested on large Boolean multiplexer problems. The paper is a contribution to
understanding how XCS functions and lays the foundation for research on XCS's
learning complexity.
Translated title of the contribution | Toward a Theory of Generalization and Learning in XCS |
---|---|
Original language | English |
Pages (from-to) | 28 - 46 |
Number of pages | 19 |
Journal | IEEE Transactions on Evolutionary Computation |
Volume | 8 (1) |
DOIs | |
Publication status | Published - Feb 2004 |
Bibliographical note
Publisher: Institute of Electrical and Electronic EngineersOther: http://www.cs.bris.ac.uk/Publications/pub_info.jsp?id=2000070