Toward a Theory of Generalization and Learning in XCS

MV Butz, TMD Kovacs, PL Lanzi, SW Wilson

Research output: Contribution to journalArticle (Academic Journal)

170 Citations (Scopus)

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 contributionToward a Theory of Generalization and Learning in XCS
Original languageEnglish
Pages (from-to)28 - 46
Number of pages19
JournalIEEE Transactions on Evolutionary Computation
Volume8 (1)
DOIs
Publication statusPublished - Feb 2004

Bibliographical note

Publisher: Institute of Electrical and Electronic Engineers
Other: http://www.cs.bris.ac.uk/Publications/pub_info.jsp?id=2000070

Fingerprint Dive into the research topics of 'Toward a Theory of Generalization and Learning in XCS'. Together they form a unique fingerprint.

  • Cite this