Implementierung eines Klassifizierungssystems

Author:	Marcus Hutter (1991)
Comments:	72 pages with listing, in German
Keywords:	Artificial Intelligence; Genetic Algorithms; Classifier System
Reference:	Diplomarbeit, TU-München, Lehrstuhl für KI, 1991
Paper:	PostScript (485kb) or PDF (330kb)
C-Source:	cfssim.c (49kb) - cfsexmple.c (7kb)
Note:	Contains the first proof (in Section 2.2.4) of the equivalence of ranking and tournament selection (defined in Section 2.1.4).

Abstract: A classifier system is a massively parallel rule based system, whose components (classifier) can exchange messages, whose behavior is is assessed by a teacher (reinforcement), and which is able to learn by means of credit assignment and a genetic algorithm. For an introduction we have to refer to the, meanwhile extensive, literature; see especially Goldberg (1989). The concept of a classifier system was first developed by Holland (1986), but meanwhile a multitude of variants and extensions exist (Booker et. al, 1989). So far it is impossible to compare these variants in their performance, statements on the quality of the various approaches are, hence, hard to impossible. The program developed in this diploma thesis allows, for the first time, a direct comparison of the most important variants. The thesis describes the program, in which we have taken special attention to an efficient implementation.

Zusammenfassung: Ein Klassifizierungssystem (CFS, engl. Classifiersystem) ist ein massiv paralleles regelbasiertes System, dessen Komponenten (Classifier) Nachrichten (Messages) austauschen können, dessen Verhalten von einem Lehrer beurteilt wird (Reinforcement) und das mittels Credit-Assignment und genetischen Algorithmen fähig ist zu lernen. Für eine einführende Darstellung muß auf die inzwischen sehr umfangreiche Literatur, insbesondere Goldberg (1989), verwiesen werden. Das Konzept des CFS wurde zuerst von Holland (1986) entwickelt, inzwischen gibt es aber eine Vielzahl von Varianten und Erweiterungen (Booker et. al, 1989). Bisher ist es nicht möglich, diese Varianten in ihrer Performance zu vergleichen, eine Aussage über die Güte der verschiedenen Ansätze ist somit kaum oder überhaupt nicht möglich. Das in dieser Diplomarbeit erstellte Programm gestattet erstmals bzgl. der wichtigsten Varianten einen direkten Vergleich. In den folgenden Kapiteln wird dieses Programm, bei dem besonders auf eine effiziente Implementierung geachtet wurde, beschrieben.

BibTeX Entry

@MastersThesis{Hutter:92cfs,
  author =       "Marcus Hutter",
  school =       "Theoretische Informatik, TU M{\"u}nchen",
  title =        "{I}mplementierung eines {K}lassifizierungs-{S}ystems",
  year =         "1991",
  pages =        "72 pages with C listing, in German",
  url =          "http://www.hutter1.net/ai/pcfs.htm",
  ps =           "http://www.hutter1.net/ai/pcfs.ps",
  pdf =          "http://www.hutter1.net/ai/pcfs.pdf",
  abstract =     "A classifier system is a massively parallel rule based system,
                  whose components (classifier) can exchange messages, whose behavior is
                  is assessed by a teacher (reinforcement), and which is able to learn by
                  means of credit assignment and a genetic algorithm. For an introduction
                  we have to refer to the, meanwhile extensive, literature; see especially
                  Goldberg (1989). The concept of a classifier system was first developed
                  by Holland (1986), but meanwhile a multitude of variants and extensions
                  exist (Booker et. al, 1989). So far it is impossible to
                  compare these variants in their performance, statements on the
                  quality of the various approaches are, hence, hard to impossible.
                  The program developed in this diploma thesis allows, for the first time,
                  a direct comparison of the most important variants.
                  The thesis describes the program, in which we have taken special attention
                  to an efficient implementation.",
  note =         "72 pages with C listing, in German",
}