%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%       LATEX-Format-File from Marcus Hutter 13.05.91       %%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%       Document-Style        %
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\documentstyle[12pt,german]{article}
\parskip=1.5ex plus 1ex minus 1ex
\parindent=0ex
\pagestyle{headings}
\topmargin=0cm
\oddsidemargin=0cm
\evensidemargin=0cm
\textwidth=16cm
\textheight=24.5cm
\setcounter{topnumber}{1}
\renewcommand{\bottomfraction}{0.7}
\sloppy
%\makeindex

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%      Macro-Definitions      %
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\newif\ifall\alltrue

%\allfalse % nur Teile compilieren
%\nofiles  % no .aux .toc ... files

%\catcode`\"=12
\catcode`\�=13\def�{\"A} \catcode`\�=13\def�{\"a}
\catcode`\�=13\def�{\"O} \catcode`\�=13\def�{\"o}
\catcode`\�=13\def�{\"U} \catcode`\�=13\def�{\"u}
\catcode`\�=13\def�{{\ss}}
\catcode`\�=13\def�{{\approx}}
%\catcode`\�=13\def�{{\infty}}
%\catcode`\�=13\def�{{\pm}}

%\def\ZG{Zufallsgr\"o\ss e}
%\def\ZZ{Zufallszahl}
%\def\GV{gleichverteilt}
%\def\WK{Wahrscheinlichkeit}
%\def\prop{proportional}
\def\ff{\Longrightarrow}
\def\gdw{\Longleftrightarrow}
\def\toinfty#1{\stackrel{#1\to\infty}{\longrightarrow}}
\def\nq{\hspace{-1em}}
\def\look{\(\uparrow\)}
\def\cpref#1{\ref{#1} auf Seite \pageref{#1}}
\def\ignore#1{}
\def\boxfig#1#2{
  \begin{figure} \fboxsep=8mm
  \framebox[\textwidth]{\centerline{#1}}
  \vspace{-2ex} \caption{#2}
  \end{figure} }
\newenvironment{listing}{\baselineskip=2.4ex\lineskiplimit=-9ex}{}
\def\CFS{CFS}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Example-Structures (to Copy)%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

% Box in Textwidth with centered Text
%   \fbox{\vbox{\hfil #\hfil}}
%   \framebox[\textwidth]{\centerline{#}
% Table-Format
%   \begin{table}
%   \begin{center}\begin{tabular}{|l|l|l|} \hline
%   \bf Col1 & \bf Col2 & \bf Col3 \\\hline\hline
%   Entry1   & Entry 2  & Entry3 \\\hline
%   ...
%   \end{tabular}\end{center}
%   \vspace{-3ex}\caption{Unterschrift}\end{table}


\begin{document}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%         Title-Page          %
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\ifall\begin{titlepage}\begin{center}       \vspace*{2cm}
  {\LARGE Diplomarbeit}               \\[2cm]
  {\Huge Thema: Implementierung eines \\
             Klassifizierungssystems} \\
  {\large (Programmbeschreibung)}     \\[2cm]
  {\LARGE Bearbeiter: Marcus Hutter}  \\[1cm]
  {\LARGE Betreuer: Gerhard Wei�}    \\[2cm]
  {\large Abgabedatum: 15.~Mai 1991}
\end{center}\end{titlepage}\fi

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%   Contents/Figures/Tables   %
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\ifall
  \tableofcontents
  \clearpage
  \listoffigures
  \listoftables
  \clearpage
\fi

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{ Einleitung }
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

Ein Klassifizierungssystem (CFS, engl. {\sl Classifiersystem}) ist ein
massiv paralleles regelbasiertes System, dessen Komponenten
{\sl (Classifier)} Nachrichten {\sl (Messages)} austauschen k�nnen,
dessen Verhalten von einem Lehrer beurteilt wird {\sl (Reinforcement)}
und das mittels {\sl Credit-Assignment} und genetischen Algorithmen
f�hig ist zu lernen.

F�r eine einf�hrende Darstellung mu� auf die inzwischen sehr
umfangreiche Literatur, insbesondere \cite{Goldberg}, verwiesen werden.

Das Konzept des CFS wurde zuerst von Holland \cite{Holland} entwickelt,
inzwischen gibt es aber eine Vielzahl von Varianten und Erweiterungen
(\look\cite{Booker,Proc}).

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 {\it direkten} Vergleich.
In den folgenden Kapiteln wird dieses Programm, bei dem besonders
auf eine effiziente Implementierung geachtet wurde, beschrieben.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{ Grundfunktionen }
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

In diesem Kapitel sollen die Funktionalit�t und die Implementierung
einiger elementarer Routinen beschrieben werden. Obwohl diese eher
allgemeiner Natur und nicht unbedingt spezifisch f�r CFS sind, sollen
sie aus folgenden Gr�nden trotzdem n�her erl�utert werden:
\begin{itemize}
\item Nur eine genaue Kenntnis der Funktionalit�t der Grundfunktionen
      kann eine klare Vorstellung des gesamten CFS vermitteln und gezielte
      Experimente erm�glichen.

\item F�r jemand, der dieses CFS erweitern oder als Motivation
      f�r ein eigenes verwenden will, stellen die Grundfunktionen eine
      solide Basis dar.
\end{itemize}
%
\subsection{ Selektion (Funktionalit�t) }\label{SelFkt}
%            ==========================
Ein zentraler Punkt in CFS ist die Selektion. Darunter ist folgendes
zu verstehen: \\
Aus einer (Multi)Menge $M$ von $n$ bewerteten Elementen, d.h.
$M=\{(Id_1,Val_1),\ldots,(Id_n,Val_n)\}$ wird eine Teil(multi)menge
$N=\{Id_{i_1},\ldots,Id_{i_k}\}$ von $k$ Elementen (die Bewertung wird
weggelassen) in Abh�ngigkeit der Bewertungen $Val_i$ ausgew�hlt,
wobei Einzelheiten vom Selektions-Modus abh�ngen.
Generell kann man sagen, da� Elemente mit
h�heren Bewertungen bevorzugt werden.

Die verschiedenen Selektions-Modi existieren in je zwei Varianten:
\begin{enumerate}
\item Elemente k�nnen mehrfach selektiert werden, d.h. mehrfach in der
      Ziel\-(multi)\-menge auftreten.
\item Elemente werden h�chstens einmal selektiert. Da die Elemente
      sequentiell selektiert werden (eines nach dem anderen), wird nach
      Auswahl eines Elements dieses einfach aus M gel�scht.
\end{enumerate}

Kommen wir nun zu den einzelnen Selektionsarten:

\subsubsection{ Dummy-Selection ({\tt SelMode=1}) }
%               ---------------------------------
Es werden beliebige (gleiche oder verschiedene) Elemente selektiert. \\
Diese Variante dient eigentlich internen Zwecken (wenn z.B. $k=N$), kann
aber auch f�r eigene Zwecke verwendet werden, wenn absolut egal ist,
welche $k$ Elemente selektiert werden sollen, z.B. Reduktion einer Menge
bei keinerlei (nicht einmal statistischer) Zusatzinformation.

\subsubsection{ Probability-Selection ({\tt SelMode=2 oder 6}) }
%               ----------------------------------------------
Dies ist eine statistische Selektion der im wesentlichen die Bewertung
der Elemente als Wahrscheinlichkeitsverteilung zugrunde liegt, d.h.
$Id_i$ wird mit Wahrscheinlichkeit $Val_i / \sum_{j=1}^n{Val_j}$ selektiert.
Dieses Verfahren wird $k$-mal (mit oder ohne L�schen der bereits
selektierten Elemente aus $M$) wiederholt.

{\tt SelMode=2} und {\tt SelMode=6} unterscheiden sich nur hinsichtlich
ihrer Implementierung (\look\ref{SelImpl}).

\subsubsection{ Best-Selection ({\tt SelMode=3}) }
%               --------------------------------
Es werden die $k$ (verschiedenen!) Elemente mit der gr��ten Bewertung
selektiert. \\
$k$-mal das gleiche beste Element zu w�hlen macht nicht
besonders viel Sinn und ergibt deshalb eine Warnung.

\subsubsection{ Scaled-Selection ({\tt SelMode=4}) }\label{SclSelFkt}
%               ----------------------------------
Die skalierte Selektion kann auf zwei verschiedene Weisen
interpretiert werden, deren �uivalenz in \cpref{SclSelImpl}
bewiesen wird.
\begin{enumerate}
\item Betrachte zwei Elemente und selektiere das h�her bewertete mit
      Wahrscheinlichkeit $p$ $(>0.5)$.
\item Sortiere die Elemente nach ihrer Bewertung, nummeriere sie linear,
      d.h. mit $(s,s+k,s+2k,\ldots,s+nk)$ durch (Linearisierung) und
      selektiere mit Wahrscheinlichkeit proportional zu dieser Nummer (wie in {\tt SelMode=2}).
\end{enumerate}

\subsubsection{ Random-Selection ({\tt SelMode=5}) }
%               ----------------------------------
Selektiere gleichverteilt, d.h. unabh�ngig von der Bewertung wird ein
Element mit Wahrscheinlichkeit $1/n$ selektiert. \\
Diese Methode dient zum Vergleich zwischen rein zuf�lligen und
bewertungsabh�ngigen Selektionsarten.

\subsection{ Selektion (Implementierung) }\label{SelImpl}
%            ===========================
Da Selektion eine zentrale Funktion ist, wurde der effizienten
Implementierung h�chste Aufmerksamkeit gewidmet. Der Mindestanspruch
lag, wie auch bei allen anderen Routinen, keinen Algorithmus mit
quadratischer Ordnung, sondern h�chstens Ordnung $O(n\log n)$ oder wenn
m�glich sogar $O(n)$ zu verwenden.
%
Die Funktion {\tt Select} wird mit folgenden Parametern aufgerufen:
\begin{description}
\item[{\verb|TIdVal A[]|:}]
     {\tt A} ist ein Array von Tupeln, deren erste
     Komponenten Identifier ({\tt index=int}) der Elemente darstellen
     (z.B. {\sl Message}-Nummer) und deren zweite die Bewertung
     ({\tt fixp=int}) enthalten.
\item[\tt int *NP:]
     {\tt *NP} gibt die Anzahle der Elemente in {\tt A} an und wird
     bei Selektion ohne Vielfachheit um {\tt k} vermindert.
\item[{\verb|index B[]|:}]
     {\tt B} nimmt die selektierten Identifier auf.
\item[\tt int k:]
     {\tt abs(k)} ist gleich der Anzahl der zu selektierenden Elemente.
     M�chte man mehrmals (zu versch.\ Zeitpunkten) Elemente aus {\tt A}
     selektieren, so mu� {\tt A} zuvor mittels {\tt MultSelInit(A,N,Mode)}
     initialisiert werden und im folgenden {\tt sign(k)=-1} gew�hlt
     werden. Bei einmaliger Selektion ({\tt sign(k)=1}) initialisiert
     {\tt Select} automatisch.
\item[\tt sbyte Mode:]
     {\tt abs(Mode)} ist der Selektions-Mode ($-$6 bis 6),\\
     {\tt sign(Mode)} gibt an, ob mit ($-1$) oder ohne ($+1$)
     Vielfachheit selektiert werden soll.
\end{description}
%
\paragraph{Beispiel:}\hfill\\
Skalierte Selektion aus {\tt A} der L�nge 10 ohne Vielfachheit.\\
Zuerst 3 Elemente, sp�ter noch einmal 2 Elemente.
%
\begin{verbatim}
      N=10;
      MultSelInit(A,N,4);
      Select(A,&N,B,-3,4);      /* nun ist N=7 */
      Select(A,&N,B,-2,4);      /* nun ist N=5 */
\end{verbatim}

\subsubsection{ Probability-Selection ({\tt SelMode=2}) }\label{ProbSelImpl}
%               --------------------------------------
Das Prinzip ist einfach: \\
Man denke sich einen Streifen aus lauter St�cken zusammengesetzt,
deren L�ngen gerade den Bewertungen entsprechen. Der Gesamtstreifen
hat so die L�nge $S=\sum_{i=0}^{n-1}{Val_i}$. Tippt man nun blind
(gleichverteilt zuf�llig) auf den Streifen, so erwischt man ein St�ck mit
Wahrscheinlichkeit proportional zu seiner L�nge.

Bei naiver Implementierung ben�tigt man im Mittel $n/2$ Additionen zur
Selektion eines Elements, bei geschickterer (Zwischenspeichern der
Partialsummen $\sum_{i=0}^k{Val_i}\quad\forall\;0\!\le\! k\!<\!n$
und {\sl Divide \& Conquere}) $\log n$
Vergleiche, aber weiterhin $n/2$ um ein Element zu l�schen. Dieses auch
auf $\log n$ zu dr�cken macht die Sache etwas verzwickter.
Die {\sl Divide \& Conquere} Idee wird beibehalten,
aber die Partialsummen durch eine Baumstruktur ersetzt.

Die Initialisierung von {\tt A} soll das Beispiel in Abbildung \ref{AInit}
verdeutlichen. Bei Arrayl�ngen, die keine Zweierpotenz sind, kann man
sich dieses durch Nullen auf die n�chste Zweierpotenz verl�ngert
denken.

\boxfig{
\unitlength=0.80mm
\begin{picture}(170,125)
\put(10,115){\framebox(10,10)[cc]{1}}
\put(20,115){\framebox(10,10)[cc]{4}}
\put(15,105){\circle{10}}
\put(15,105){\makebox(0,0)[cc]{5}}
\put(15,115){\vector(0,-1){5}}
\put(25,115){\line(0,-1){10}}
\put(25,105){\vector(-1,0){5}}
\put(20,110){\makebox(0,0)[cc]{+}}
\put(30,115){\framebox(10,10)[cc]{3}}
\put(40,115){\framebox(10,10)[cc]{2}}
\put(35,105){\circle{10}}
\put(35,105){\makebox(0,0)[cc]{5}}
\put(35,115){\vector(0,-1){5}}
\put(45,115){\line(0,-1){10}}
\put(45,105){\vector(-1,0){5}}
\put(40,110){\makebox(0,0)[cc]{+}}
\put(15,90){\circle{10}}
\put(15,90){\makebox(0,0)[cc]{10}}
\put(15,100){\vector(0,-1){5}}
\put(35,100){\line(0,-1){10}}
\put(35,90){\vector(-1,0){15}}
\put(20,95){\makebox(0,0)[cc]{+}}
\put(50,115){\framebox(10,10)[cc]{7}}
\put(60,115){\framebox(10,10)[cc]{5}}
\put(55,105){\circle{10}}
\put(55,105){\makebox(0,0)[cc]{12}}
\put(55,115){\vector(0,-1){5}}
\put(65,115){\line(0,-1){10}}
\put(65,105){\vector(-1,0){5}}
\put(60,110){\makebox(0,0)[cc]{+}}
\put(70,115){\framebox(10,10)[cc]{6}}
\put(80,115){\framebox(10,10)[cc]{8}}
\put(75,105){\circle{10}}
\put(75,105){\makebox(0,0)[cc]{14}}
\put(75,115){\vector(0,-1){5}}
\put(85,115){\line(0,-1){10}}
\put(85,105){\vector(-1,0){5}}
\put(80,110){\makebox(0,0)[cc]{+}}
\put(55,90){\circle{10}}
\put(55,90){\makebox(0,0)[cc]{26}}
\put(55,100){\vector(0,-1){5}}
\put(75,100){\line(0,-1){10}}
\put(75,90){\vector(-1,0){15}}
\put(60,95){\makebox(0,0)[cc]{+}}
\put(15,75){\circle{10}}
\put(15,75){\makebox(0,0)[cc]{36}}
\put(15,85){\vector(0,-1){5}}
\put(55,85){\line(0,-1){10}}
\put(55,75){\vector(-1,0){35}}
\put(90,115){\framebox(10,10)[cc]{4}}
\put(100,115){\framebox(10,10)[cc]{1}}
\put(95,105){\circle{10}}
\put(95,105){\makebox(0,0)[cc]{5}}
\put(95,115){\vector(0,-1){5}}
\put(105,115){\line(0,-1){10}}
\put(105,105){\vector(-1,0){5}}
\put(100,110){\makebox(0,0)[cc]{+}}
\put(110,115){\framebox(10,10)[cc]{9}}
\put(120,115){\framebox(10,10)[cc]{\it 0}}
\put(115,105){\circle{10}}
\put(115,105){\makebox(0,0)[cc]{9}}
\put(115,115){\vector(0,-1){5}}
\put(125,115){\line(0,-1){10}}
\put(125,105){\vector(-1,0){5}}
\put(120,110){\makebox(0,0)[cc]{+}}
\put(95,90){\circle{10}}
\put(95,90){\makebox(0,0)[cc]{14}}
\put(95,100){\vector(0,-1){5}}
\put(115,100){\line(0,-1){10}}
\put(115,90){\vector(-1,0){15}}
\put(100,95){\makebox(0,0)[cc]{+}}
\put(130,115){\framebox(10,10)[cc]{\it 0}}
\put(140,115){\framebox(10,10)[cc]{\it 0}}
\put(135,105){\circle{10}}
\put(135,105){\makebox(0,0)[cc]{\it 0}}
\put(135,115){\vector(0,-1){5}}
\put(145,115){\line(0,-1){10}}
\put(145,105){\vector(-1,0){5}}
\put(140,110){\makebox(0,0)[cc]{+}}
\put(150,115){\framebox(10,10)[cc]{\it 0}}
\put(160,115){\framebox(10,10)[cc]{\it 0}}
\put(155,105){\circle{10}}
\put(155,105){\makebox(0,0)[cc]{\it 0}}
\put(155,115){\vector(0,-1){5}}
\put(165,115){\line(0,-1){10}}
\put(165,105){\vector(-1,0){5}}
\put(160,110){\makebox(0,0)[cc]{+}}
\put(135,90){\circle{10}}
\put(135,90){\makebox(0,0)[cc]{\it 0}}
\put(135,100){\vector(0,-1){5}}
\put(155,100){\line(0,-1){10}}
\put(155,90){\vector(-1,0){15}}
\put(140,95){\makebox(0,0)[cc]{+}}
\put(95,75){\circle{10}}
\put(95,75){\makebox(0,0)[cc]{14}}
\put(95,85){\vector(0,-1){5}}
\put(135,85){\line(0,-1){10}}
\put(135,75){\vector(-1,0){35}}
\put(15,60){\circle{10}}
\put(15,60){\makebox(0,0)[cc]{50}}
\put(15,70){\vector(0,-1){5}}
\put(95,70){\line(0,-1){10}}
\put(95,60){\vector(-1,0){75}}
\put(20,80){\makebox(0,0)[cc]{+}}
\put(100,80){\makebox(0,0)[cc]{+}}
\put(20,65){\makebox(0,0)[cc]{+}}
\put(10,40){\framebox(10,10)[cc]{50}}
\put(15,55){\vector(0,-1){5}}
\put(20,40){\framebox(10,10)[cc]{4}}
\put(25,55){\vector(0,-1){5}}
\put(30,40){\framebox(10,10)[cc]{5}}
\put(35,55){\vector(0,-1){5}}
\put(40,40){\framebox(10,10)[cc]{2}}
\put(45,55){\vector(0,-1){5}}
\put(50,40){\framebox(10,10)[cc]{26}}
\put(55,55){\vector(0,-1){5}}
\put(60,40){\framebox(10,10)[cc]{5}}
\put(65,55){\vector(0,-1){5}}
\put(70,40){\framebox(10,10)[cc]{14}}
\put(75,55){\vector(0,-1){5}}
\put(80,40){\framebox(10,10)[cc]{8}}
\put(85,55){\vector(0,-1){5}}
\put(90,40){\framebox(10,10)[cc]{14}}
\put(95,55){\vector(0,-1){5}}
\put(100,40){\framebox(10,10)[cc]{1}}
\put(105,55){\vector(0,-1){5}}
\put(110,40){\framebox(10,10)[cc]{9}}
\put(115,55){\vector(0,-1){5}}
\put(120,40){\framebox(10,10)[cc]{\it 0}}
\put(125,55){\vector(0,-1){5}}
\put(130,40){\framebox(10,10)[cc]{\it 0}}
\put(135,55){\vector(0,-1){5}}
\put(140,40){\framebox(10,10)[cc]{\it 0}}
\put(145,55){\vector(0,-1){5}}
\put(150,40){\framebox(10,10)[cc]{\it 0}}
\put(155,55){\vector(0,-1){5}}
\put(160,40){\framebox(10,10)[cc]{\it 0}}
\put(165,55){\vector(0,-1){5}}
\put(10,0){\framebox(10,10)[cc]{1}}
\put(20,0){\framebox(10,10)[cc]{4}}
\put(30,0){\framebox(10,10)[cc]{3}}
\put(40,0){\framebox(10,10)[cc]{2}}
\put(50,0){\framebox(10,10)[cc]{7}}
\put(60,0){\framebox(10,10)[cc]{5}}
\put(70,0){\framebox(10,10)[cc]{6}}
\put(80,0){\framebox(10,10)[cc]{8}}
\put(90,0){\framebox(10,10)[cc]{4}}
\put(100,0){\framebox(10,10)[cc]{1}}
\put(110,0){\framebox(10,10)[cc]{9}}
\put(120,0){\framebox(10,10)[cc]{\it 0}}
\put(130,0){\framebox(10,10)[cc]{\it 0}}
\put(140,0){\framebox(10,10)[cc]{\it 0}}
\put(150,0){\framebox(10,10)[cc]{\it 0}}
\put(160,0){\framebox(10,10)[cc]{\it 0}}
\put(25,40){\line(0,-1){5}}
\put(20,35){\line(0,-1){2}}
\put(30,35){\line(0,-1){2}}
\put(45,40){\line(0,-1){5}}
\put(40,35){\line(0,-1){2}}
\put(50,35){\line(0,-1){2}}
\put(35,40){\line(0,-1){10}}
\put(30,30){\line(0,-1){2}}
\put(50,30){\line(0,-1){2}}
\put(65,40){\line(0,-1){5}}
\put(60,35){\line(0,-1){2}}
\put(70,35){\line(0,-1){2}}
\put(85,40){\line(0,-1){5}}
\put(80,35){\line(0,-1){2}}
\put(90,35){\line(0,-1){2}}
\put(75,40){\line(0,-1){10}}
\put(70,30){\line(0,-1){2}}
\put(90,30){\line(0,-1){2}}
\put(55,40){\line(0,-1){15}}
\put(50,25){\line(0,-1){2}}
\put(90,25){\line(0,-1){2}}
\put(105,40){\line(0,-1){5}}
\put(100,35){\line(0,-1){2}}
\put(110,35){\line(0,-1){2}}
\put(125,40){\line(0,-1){5}}
\put(120,35){\line(0,-1){2}}
\put(130,35){\line(0,-1){2}}
\put(115,40){\line(0,-1){10}}
\put(110,30){\line(0,-1){2}}
\put(130,30){\line(0,-1){2}}
\put(145,40){\line(0,-1){5}}
\put(140,35){\line(0,-1){2}}
\put(150,35){\line(0,-1){2}}
\put(165,40){\line(0,-1){5}}
\put(160,35){\line(0,-1){2}}
\put(170,35){\line(0,-1){2}}
\put(155,40){\line(0,-1){10}}
\put(150,30){\line(0,-1){2}}
\put(170,30){\line(0,-1){2}}
\put(135,40){\line(0,-1){15}}
\put(130,25){\line(0,-1){2}}
\put(170,25){\line(0,-1){2}}
\put(95,40){\line(0,-1){20}}
\put(90,20){\line(0,-1){2}}
\put(170,20){\line(0,-1){2}}
\put(15,40){\line(0,-1){25}}
\put(10,15){\line(0,-1){2}}
\put(170,15){\line(0,-1){2}}
\thicklines
\put(20,35){\line(1,0){10}}
\put(40,35){\line(1,0){10}}
\put(30,30){\line(1,0){20}}
\put(60,35){\line(1,0){10}}
\put(80,35){\line(1,0){10}}
\put(70,30){\line(1,0){20}}
\put(50,25){\line(1,0){40}}
\put(100,35){\line(1,0){10}}
\put(120,35){\line(1,0){10}}
\put(110,30){\line(1,0){20}}
\put(140,35){\line(1,0){10}}
\put(160,35){\line(1,0){10}}
\put(150,30){\line(1,0){20}}
\put(130,25){\line(1,0){40}}
\put(90,20){\line(1,0){80}}
\put(10,15){\line(1,0){160}}
\put(0,120){\makebox(0,0)[lc]{A=}}
\put(0,45){\makebox(0,0)[lc]{A1=}}
\put(0,5){\makebox(0,0)[lc]{A=}}
\end{picture}
}{\label{AInit} Initialisierung von A ({\tt ProbSelInit}) }

Selektiert wird ein Element wie folgt (siehe auch Abbildung \ref{ASel}):
\begin{enumerate}
\item Ziehen einer gleichverteilten Zufallszahl {\tt z}
      zwischen {\tt 0} und \verb|S=A1[0]-1|.
\item Man denke sich {\tt z} von rechts abgetragen.
      Da \verb|A1[n/2]| die Summe der rechten H�lfte von Elementen
      aus {\tt A} enth�lt gilt:
  \begin{itemize}
  \item ist ${\tt z}<\verb|A1[n/2]|$, so liegt {\tt z} in der
	rechten H�lfte von {\tt A}. Betrachte im folgenden diese
	H�lfte als neues Array \verb|A2[0..n/2-1]=A1[n/2..n-1]|.
  \item ist ${\tt z}\ge\verb|A1[n/2]|$, so liegt {\tt z} in der
	linken H�lfte von {\tt A}.
	Betrachte im folgenden diese H�lfe als neues Array
	{\tt A2[0..n/2-1]=A[0..n/2-1]}. Da sich das rechte Ende ge�ndert hat,
	mu� zur Korrektur {\tt A1[n/2]} von {\tt z} abgezogen werden.
  \end{itemize}
\item Wiederhole Schritt 2 mit {\tt A2}, solange ${\tt n}>1$.
\item Die Komponente, bei der man am Ende dieser Iteration angelangt ist
      wird selektiert.
\end{enumerate}

\boxfig{
\unitlength=0.80mm
\begin{picture}(170,55)
\put(10,45){\framebox(10,10)[cc]{50}}
\put(20,45){\framebox(10,10)[cc]{4}}
\put(30,45){\framebox(10,10)[cc]{5}}
\put(40,45){\framebox(10,10)[cc]{2}}
\put(50,45){\framebox(10,10)[cc]{26}}
\put(60,45){\framebox(10,10)[cc]{5}}
\put(70,45){\framebox(10,10)[cc]{14}}
\put(80,45){\framebox(10,10)[cc]{8}}
\put(90,45){\framebox(10,10)[cc]{14}}
\put(100,45){\framebox(10,10)[cc]{1}}
\put(110,45){\framebox(10,10)[cc]{9}}
\put(120,45){\framebox(10,10)[cc]{\it 0}}
\put(130,45){\framebox(10,10)[cc]{\it 0}}
\put(140,45){\framebox(10,10)[cc]{\it 0}}
\put(150,45){\framebox(10,10)[cc]{\it 0}}
\put(160,45){\framebox(10,10)[cc]{\it 0}}
\put(15,45){\vector(0,-1){10}}
\put(25,45){\line(0,-1){10}}
\put(25,35){\vector(-1,0){10}}
\put(35,45){\vector(0,-1){10}}
\put(45,45){\line(0,-1){10}}
\put(45,35){\vector(-1,0){10}}
\put(15,35){\vector(0,-1){10}}
\put(35,35){\line(0,-1){10}}
\put(35,25){\vector(-1,0){20}}
\put(55,45){\vector(0,-1){10}}
\put(65,45){\line(0,-1){10}}
\put(65,35){\vector(-1,0){10}}
\put(75,45){\vector(0,-1){10}}
\put(85,45){\line(0,-1){10}}
\put(85,35){\vector(-1,0){10}}
\put(55,35){\vector(0,-1){10}}
\put(75,35){\line(0,-1){10}}
\put(75,25){\vector(-1,0){20}}
\put(15,25){\vector(0,-1){10}}
\put(55,25){\line(0,-1){10}}
\put(55,15){\vector(-1,0){40}}
\put(95,45){\vector(0,-1){10}}
\put(105,45){\line(0,-1){10}}
\put(105,35){\vector(-1,0){10}}
\put(115,45){\vector(0,-1){10}}
\put(125,45){\line(0,-1){10}}
\put(125,35){\vector(-1,0){10}}
\put(95,35){\vector(0,-1){10}}
\put(115,35){\line(0,-1){10}}
\put(115,25){\vector(-1,0){20}}
\put(135,45){\vector(0,-1){10}}
\put(145,45){\line(0,-1){10}}
\put(145,35){\vector(-1,0){10}}
\put(155,45){\vector(0,-1){10}}
\put(165,45){\line(0,-1){10}}
\put(165,35){\vector(-1,0){10}}
\put(135,35){\vector(0,-1){10}}
\put(155,35){\line(0,-1){10}}
\put(155,25){\vector(-1,0){20}}
\put(95,25){\vector(0,-1){10}}
\put(135,25){\line(0,-1){10}}
\put(135,15){\vector(-1,0){40}}
\put(15,15){\vector(0,-1){10}}
\put(95,15){\line(0,-1){10}}
\put(95,5){\vector(-1,0){80}}
\put(0,50){\makebox(0,0)[lc]{A1=}}
\put(15,5){\line(0,-1){5}}
\put(99,5){\circle{6}}
\put(99,5){\makebox(0,0)[cc]{25}}
\put(102,5){\makebox(0,0)[lc]{$>\!\!14$}}
\put(59,15){\circle{6}}
\put(59,15){\makebox(0,0)[cc]{11}}
\put(62,15){\makebox(0,0)[lc]{$<\!\!26$}}
\put(90,6){\vector(-4,1){25}}
\put(79,9){\makebox(0,0)[rt]{$^{25-14}$}}
\put(79,25){\circle{6}}
\put(79,25){\makebox(0,0)[cc]{11}}
\put(82,25){\makebox(0,0)[lc]{$<\!\!14$}}
\put(65,18){\vector(2,1){8}}
\put(89,35){\circle{6}}
\put(89,35){\makebox(0,0)[cc]{11}}
\put(89,32){\makebox(0,0)[ct]{$>\!\!8$}}
\put(80,29){\vector(3,2){5}}
\put(84,38){\vector(-1,1){6}}
\put(120,5){\makebox(0,0)[cc]{25}}
\put(120,5){\circle{6}}
\put(123,5){\makebox(0,0)[lc]{=z=random(50)}}
\end{picture}
}{\label{ASel} Selektion ({\tt ProbSel}) }

Um ein Element $k$ in {\tt A} zu ersetzen, bestimmt man die
urspr�ngliche Bewertung und korrigiert alle in der Hierarchie
h�her stehenden Elemente, indem man die neue minus die alte Bewertung
hinzuaddiert (\look Abbildung \ref{AModBew}).

\boxfig{
\unitlength=0.80mm
\begin{picture}(170,60)
\put(10,50){\framebox(10,10)[cc]{50}}
\put(20,50){\framebox(10,10)[cc]{4}}
\put(30,50){\framebox(10,10)[cc]{5}}
\put(40,50){\framebox(10,10)[cc]{2}}
\put(50,50){\framebox(10,10)[cc]{26}}
\put(60,50){\framebox(10,10)[cc]{5}}
\put(70,50){\framebox(10,10)[cc]{14}}
\put(80,50){\framebox(10,10)[cc]{8}}
\put(90,50){\framebox(10,10)[cc]{14}}
\put(100,50){\framebox(10,10)[cc]{1}}
\put(110,50){\framebox(10,10)[cc]{9}}
\put(120,50){\framebox(10,10)[cc]{\it 0}}
\put(130,50){\framebox(10,10)[cc]{\it 0}}
\put(140,50){\framebox(10,10)[cc]{\it 0}}
\put(150,50){\framebox(10,10)[cc]{\it 0}}
\put(160,50){\framebox(10,10)[cc]{\it 0}}
\put(15,50){\vector(0,-1){10}}
\put(25,50){\line(0,-1){10}}
\put(25,40){\vector(-1,0){10}}
\put(35,50){\vector(0,-1){10}}
\put(45,50){\line(0,-1){10}}
\put(45,40){\vector(-1,0){10}}
\put(15,40){\vector(0,-1){10}}
\put(35,40){\line(0,-1){10}}
\put(35,30){\vector(-1,0){20}}
\put(55,50){\vector(0,-1){10}}
\put(65,50){\line(0,-1){10}}
\put(65,40){\vector(-1,0){10}}
\put(75,50){\vector(0,-1){10}}
\put(85,50){\line(0,-1){10}}
\put(85,40){\vector(-1,0){10}}
\put(55,40){\vector(0,-1){10}}
\put(75,40){\line(0,-1){10}}
\put(75,30){\vector(-1,0){20}}
\put(15,30){\vector(0,-1){10}}
\put(55,30){\line(0,-1){10}}
\put(55,20){\vector(-1,0){40}}
\put(95,50){\vector(0,-1){10}}
\put(105,50){\line(0,-1){10}}
\put(105,40){\vector(-1,0){10}}
\put(115,50){\vector(0,-1){10}}
\put(125,50){\line(0,-1){10}}
\put(125,40){\vector(-1,0){10}}
\put(95,40){\vector(0,-1){10}}
\put(115,40){\line(0,-1){10}}
\put(115,30){\vector(-1,0){20}}
\put(135,50){\vector(0,-1){10}}
\put(145,50){\line(0,-1){10}}
\put(145,40){\vector(-1,0){10}}
\put(155,50){\vector(0,-1){10}}
\put(165,50){\line(0,-1){10}}
\put(165,40){\vector(-1,0){10}}
\put(135,40){\vector(0,-1){10}}
\put(155,40){\line(0,-1){10}}
\put(155,30){\vector(-1,0){20}}
\put(95,30){\vector(0,-1){10}}
\put(135,30){\line(0,-1){10}}
\put(135,20){\vector(-1,0){40}}
\put(15,20){\vector(0,-1){10}}
\put(95,20){\line(0,-1){10}}
\put(95,10){\vector(-1,0){80}}
\put(56,41){\makebox(0,0)[lb]{-}}
\put(54,40){\makebox(0,0)[rc]{21}}
\put(56,31){\makebox(0,0)[lb]{-}}
\put(54,30){\makebox(0,0)[rc]{7}}
\put(60,25){\circle{8}}
\put(60,25){\makebox(0,0)[cc]{$-4$}}
\put(50,11){\framebox(10,8)[cc]{22}}
\put(20,15){\circle{8}}
\put(20,15){\makebox(0,0)[cc]{$-4$}}
\put(10,1){\framebox(10,8)[cc]{46}}
\put(0,55){\makebox(0,0)[lc]{A1=}}
\put(105,10){\makebox(0,0)[lc]{
  $\tt A[4]=7\rightarrow A[4]=3$ (in {\tt A1})}}
\end{picture}
}{\label{AModBew} Rekonstruktion und Modifikation einer Bewertung }

Um ein Element $k$ in {\tt A} zu l�schen, ersetzt man dieses durch
das Element $n-1$, l�scht das Element $n-1$ und verk�rzt das Array um 1.

Die Initialisierung ben�tigt $n-1$ Additionen, die Selektion und das
L�schen  eines Elements $O(\log n)$ Operationen. Damit ergibt sich die
Gesamtkomplexit�t der Selektion von $k$ Elementen zu $O(n+k\log n)$.

In der Praxis treten zus�tzliche Probleme bei der Initialisierung auf;
da der integer-Bereich beschr�nkt ist, l�uft man Gefahr diesen bei der
Summation zu �berschreiten. Deshalb wurde jede Summe ({\tt a+b}) durch eine
Mittelwertsbildung  ({\tt (a+b)/2}) ersetzt und s�mtliche Routinen
dieser Korrektur angepa�t.

Bei Verminderung der Arrayl�nge von $2^n+1$
auf $2^n$, nimmt dabei die Hierarchieebene von {\tt A[0]} um eins ab und
{\tt A[0]} mu� entsprechend korrigiert werden.

Der Test auf eine Zweierpotenz kann im �brigen leicht wie folgt
implementiert werden:

       \hfil {\tt N} ist Zweierpotenz $\gdw$
	     \verb|N&(N-1)==0| (bitweises \verb|&|) \hfil
%
\subsubsection{ Probability-Selection ({\tt SelMode=6}) }
%               ---------------------------------------
Funktional ist dieser Selektions-Modus identisch mit vorherigem, der
Algorithmus ist aber wesentlich einfacher und unter gewissen Umst�nden
sogar schneller. Das Prinzip ist auch hier wiederum einfach:

Es wird eine gleichverteilte Zufallszahl $i$ zwischen 0 und $n-1$
wie in {\it Random-Selection} gezogen, allerdings wird das Element $i$ nur
mit Wahrscheinlichkeit $A_i/K$ ($K$ konstant) akzeptiert. Wird das
Element $i$ nicht akzeptiert,so wird nach diesem Verfahren weitergesucht.
Damit $A_i/K\le 1$ f�r alle $i$ ist, mu� $K\ge \max(A_i)$ gew�hlt werden.
Die mittlere Zahl an Zyklen, bis eine Zufallszahl akzeptiert wird, ist somit
$$ C\; = \;{1\over <\!\!\!A_i/K\!\!\!>_i}\; = \;
   {K\cdot n\over \sum_{i=0}^{n-1}{A_i}}\quad .$$
Man w�hlt also $K$ zweckm��igerweise m�glichst klein, also
$K=\max(A_i)$.
$C$ h�ngt somit wesentlich vom Verh�ltnis des
Fl�cheninhalts des der Funktion umbeschriebenen Rechtecks und der
Funktion selbst ab (\look Abbildung \ref{VertFkt}).

\begin{figure}\begin{center}
\unitlength=1mm
\thicklines
\begin{picture}(120,80)
\put(0,0){\vector(0,1){80}}
\put(0,0){\vector(1,0){120}}
\put(0,0){\dashbox{5}(110,70)[cc]{}}
\put(1,73){\makebox(0,0)[lb]{$A_i$}}
\put(115,1){\makebox(0,0)[cb]{$i$}}
\put(0,0){\line(5,1){10}}\put(0,0){\circle*{1}}
\put(10,2){\line(6,1){10}}\put(10,2){\circle*{1}}
\put(20,3.67){\line(3,1){10}}\put(20,3.67){\circle*{1}}
\put(30,7){\line(1,0){10}}\put(30,7){\circle*{1}}
\put(40,7){\line(3,1){10}}\put(40,7){\circle*{1}}
\put(50,10.33){\line(1,0){10}}\put(50,10.33){\circle*{1}}
\put(60,10.33){\line(1,1){10}}\put(60,10.33){\circle*{1}}
\put(70,20.33){\line(6,1){10}}\put(70,20.33){\circle*{1}}
\put(80,22){\line(1,0){10}}\put(80,22){\circle*{1}}
\put(90,22){\line(5,4){10}}\put(90,22){\circle*{1}}
\put(100,30){\line(1,4){10}}\put(100,30){\circle*{1}}
\thinlines
\put(108,32){\line(-1,1){4}}
\put(108,22){\line(-1,1){7}}
\put(108,12){\line(-1,1){12}}
\put(108,2){\line(-1,1){18}}
\put(98,2){\line(-1,1){18}}
\put(88,2){\line(-1,1){16}}
\put(78,2){\line(-1,1){11}}
\put(68,2){\line(-1,1){7}}
\put(58,2){\line(-1,1){6}}
\put(48,2){\line(-1,1){4}}
\put(38,2){\line(-1,1){3}}
\end{picture}
\caption{\label{VertFkt} Verteilung + einh�llendes Rechteck}
\end{center}\end{figure}

Bei einigerma�en gleichverteilten Zufallsgr��en ist $C$ klein und damit die
Zeitkomplexit�t eine kleine Konstante, also der Implementierung f�r
{\tt SelMode=2} mit Komplexit�t $O(\log n)$ vorzuziehen.

\subsubsection{ Best-Selection ({\tt SelMode=3}) }
%               --------------------------------
Bei iterierter Selektion wird $A$ mittels Quicksort ({\tt QSort}) zuerst
aufsteigend sortiert und dann bei jedem Zugriff die obersten Elemente
geliefert und gel�scht (Die L�nge von $A$ wird reduziert).
Mittlere Gesamtkomplexit�t: $O(n\log n)$

Bei einmaliger Selektion der $k$ gr��ten Elemente aus $A$ kann auf das
Sortieren verzichtet werden und durch einen quicksort-�hnlichen
Algorithmus ({\tt QMax}) mit nur noch linerarer Rekursion ersetzt werden.
W�hlt man wie in Quicksort ein Trennelement und sortiert die kleineren
Elemente an den Anfang des Arrays und die gr��eren an das Ende, so
kann man wie folgt weiter argumentieren:
%
\begin{itemize}
\item Liegen weniger als $k$ Elemente  in der oberen H�lfte, so werden
      {\it diese} garantiert und noch {\it einige} der unteren H�lfte
      selektiert. Man mu� also nur noch die untere H�lfte betrachten
      und {\tt QMax} (rekurviv) mit der restlichen Zahl zu
      selektierender Elemente aufrufen.
\item Liegen mehr als $k$ Elemente in der oberen H�lfte, so werden
      {\it einige} dieser und garantiert {\it keine} der unteren H�lfte
      selektiert. Man betrachtet hier also nur noch die obere H�lfte
      und ruft {\tt QMax} (rekursiv) mit der oberen H�lfte und $k$ auf.
\end{itemize}

Dieser Prozess bewirkt ein sukzessives Verschieben der Grenze, bis
diese ''pa�t''.

Mittlere Gesamtkomplexit�t: $O(n)$

\subsubsection{ Scaled-Selection ({\tt SelMode=4}) }\label{SclSelImpl}
%               ----------------------------------
An dieser Stelle sollen die �quivalenz der beiden in \cpref{SclSelFkt}
angedeuteten Interpretationen bewiesen, einige weitere
mathematische Untersuchungen angestellt und die Vorteile
dieser Selektionsart behandelt werden.

Die Implementierung der 1.~Interpretation ist trivial:

Ziehe zwei gleichverteilte Zufallszahlen $i$ und $j$ zwischen
0 und $n-1$ und w�hle aus $\{A_i,A_j\}$ das gr��ere Element mit
Wahrscheinlichkeit $p$ (entsprechend das kleinere
mit Wahrscheinlichkeit $q=1-p$) (*).

\paragraph{ Mathematische Analyse }\hfill\\
Seien $A_1,\ldots,A_n$ in aufsteigender Reihenfolge sortiert,
d.h. $A_1\le\ldots\le A_n$.
\footnote{
Man mache sich klar, da� die Nummerierung keinen Einflu� auf
die Selektion hat (da gleichverteilt) und somit im Programm beliebig
(also einfach die Array-Indizes) gew�hlt werden kann und nicht
wie man vermuten k�nnte, das Array zuerst sortiert werden mu�.}

Seien $X_1$ und $X_2$ die zwei gleichverteilten Zufallsgr��en,
$Y$ die sich aus obigem Proze� (*) f�r das selektierte Element
ergebende Zufallsgr��e, d.h.
$$ P(X_i=k)\;=\;1/n \quad\mbox{ f�r }\quad k\in\{1,\ldots,n\}$$
%
(*) mathematisch �bersetzt:
\begin{eqnarray*}
& P(Y=k)\quad=\quad p\cdot P(\max(X_1,X_2)=k)+
                      q\cdot P(\min(X_1,X_2)=k) &\\
&  \mbox{da } X_1<X_2 \gdw A_{X_1}<A_{X_2} &
\end{eqnarray*}
%
Als Verteilung geschrieben:
\begin{eqnarray*}
P(Y\le k)
&=& p\cdot P(X_1\le k\land X_2\le k)+
    q\cdot P(X_1\le k\lor X_2\le k)\quad= \\
&=& p\cdot\underbrace{P(X_1\le k)\cdot P(X_2\le k)}
    _{\mbox{\scriptsize unabh�ngig}}+
    q\cdot\Bigl[1-\underbrace{P(X_1>k)\cdot P(X_2>k)}
    _{\mbox{\scriptsize unabh�ngig}}\Bigr]\quad= \\
&=& p\cdot {k\over n}\cdot{k\over n}+
    q\cdot\Bigl[1-(1-{k\over n})\cdot(1-{k\over n})\Bigr]\quad= \\
&=& q{2k\over n}+(p-q)\Bigl({k\over n}\Bigl)^2
\end{eqnarray*}
%
und wieder als Wahrscheinlichkeit ausgedr�ckt:
\begin{eqnarray*}
P(Y=k)
&=& P(Y\le k)-P(Y\le k-1)\quad= \\
&=& \biggl[ q{2k\over n}+(p-q)\Bigl({k\over n}\Bigl)^2\biggr] -
 \biggl[q{2(k-1)\over n}+(p-q)\Bigl({k-1\over n}\Bigl)^2 \biggr]\quad= \\
&=& q{2\over n}+(p-q){2k-1\over n^2}\quad=\quad
 {2(p-q)\over n^2}\cdot k+\biggl({2q\over n}-{p-q\over n^2}\biggr)\quad \\
\end{eqnarray*}
%
$$\ff\quad\fbox{ $\displaystyle
P(Y=k)\;=\;ak+b\quad\mbox{mit}\quad
  a={2(p-q)\over n^2}\quad,\quad
  b={2q\over n}-{p-q\over n^2} $ } $$

$Y$ ist also eine linear verteilte Zufallsgr��e,
wie in \ref{SclSelFkt} behauptet wird.

$(A_1,\ldots,A_n)$ zu sortieren und mit Wahrscheinlichkeit proportional zu
$(a+b,a+2b,\ldots,a+nb)$ zu selektieren,
ist also zu obiger Methode �quivalent.

Frei ist noch der Parameter $p$, der z.B. so gew�hlt werden kann,
da� die Selektions-Wahrscheinlichkeit des
$\mbox{\scriptsize gr��ten}\over \mbox{\scriptsize kleinsten}$
Elements gleich $C$ ist, d.h.
%
\begin{eqnarray*}
C&:=&{P(Y=n)\over P(Y=1)}                         \quad=\quad
    {an+b\over a+b}                               \quad=\quad
    {2(p-q)n+2qn-(p-q)\over 2(p-q)+2qn-(p-q)}     \quad=\\
&=& {2n(2p-1)+2n(1-p)-(2p-1)\over (2p-1)+2n(1-p)} \quad=\\
&=& {2np-(2p-1)\over 2n(1-p)+(2p-1)}              \quad\toinfty{n}\quad
    {p\over 1-p} \\[2ex]
%
&\gdw& [2n(1-p)+(2p-1)]\cdot C                  \quad=\quad 2np-(2p-1) \\
&\gdw& [2(1-n)p+(2n-1)]\cdot C                  \quad=\quad 2(n-1)p+1 \\
&\gdw& 2(1-n)p(C+1)+(2n-1)C                     \quad=\quad 1 \\
&\gdw& p\quad=\quad{(2n-1)C-1\over 2(n-1)(C+1)} \quad\toinfty{n}\quad
       {C\over C+1}
\end{eqnarray*}

\paragraph{Beispiel 1:}\hfill\\
$C=1$: Kein Element wird bevorzugt $\ff$ \\
$p={(2n-1)-1\over2(n-1)(1+1)}={1\over 2}$:
       Rein gleichverteilter Zufall (klar) $\ff$ \\
$P(Y=k)=1/n$: Jedes Element mit Wahrscheinlichkeit $1/n$
%
\vspace{-3ex}
\paragraph{Beispiel 2:}\hfill\\
$C=2$: Wahrscheinlichkeit des
  ${\mbox{\scriptsize gr��ten}\over \mbox{\scriptsize kleinsten}}=2
  \quad\ff\quad p={4n-3\over 6n-6}\toinfty{n}{2\over 3}$
%
\vspace{-3ex}
\paragraph{Beispiel 3:}\hfill\\
$p=1\quad\ff\quad P(Y=k)={1\over n^2}(2k-1)\quad,\quad C=2n-1$:
   Sehr starke Selektion
%
\vspace{-3ex}
\paragraph{Beispiel 4:}\hfill\\
$p=2/3\quad\ff\quad P(Y=k)={1\over 3n^2}(2k+2n-1)\quad,\quad
   C={4n-1\over 2n+1}\toinfty{n}2$ : (\look Beispiel 2)

\paragraph{Vorteile:}\hfill\\
\begin{itemize}
\item {\bf Einfache Implementierung:} \\
  Linearisierung, ohne sortieren zu m�ssen
  (nicht zu verwechseln mit linerarer Skalierung,
  die h�ufig verwendet wird).
\item {\bf Gute Skalierung:} \\
  Linearisierung auch unangenehmer Funktionen
  (\look Abbildung \ref{VertFkt}).
\item {\bf Biologische Plausibilit�t:} \\
  Zwei Individuen (Elemente) k�mpfen ums �berleben (selektiert zu
  werden), und dasjenige mit h�herer Fitne� (Bewertung) siegt
  mit gr��erer Wahrscheinlichkeit ($p>q$ !).
\end{itemize}

\subsubsection{ Random-Selection ({\tt SelMode=5}) }
%               ----------------------------
Selektiere gleichverteilt, d.h. unabh�ngig von der Bewertung wird ein
Element mit Wahrscheinlichkeit $1/n$ selektiert.

\subsection{ Tupelalgorithmen }
%            ================
Die Routine {\it Bid}, die aus den {\sl Matching-Tupels} die
{\sl Bid-Tupels} erzeugt, mu� u.a. folgendes berechnen: \\
Gegeben ist eine Menge $M$ von {\sl Messages}, wobei jede {\sl Message}
eine Intensit�t besitzt, die durch $f\!:\!M\to\Re$ gegeben ist.
Teilmengen $M_i\subseteq M$ {\sl matchen} den Bedingungsteil $i$
eines festen {\sl Classifiers}. Nun werden s�mtliche {\sl Matching-Tupels}
$T=M_1\times\cdots\times M_r$
gebildet und hiervon die Gesamtintensit�t gleich dem {\sl Support}
$$ S\quad:=\nq\sum\limits_{(m_1,\ldots,m_r)\in T}\nq f(m_1)+\cdots+f(m_r) $$
berechnet. Durch eine kleine Transformation k�nnen diese
$|T|=|M_1|\cdot\ldots\cdot\ |M_r|$
Additionen auf $|M_1|+\ldots+|M_r|$ Additionen reduziert werden.
%
$$\mbox{Betrachte: }
   \sum_{(m_1,\ldots,m_r)\in T}\nq\!\!\! f(m_i)\;=\nq
   \sum_{(m_1,\ldots,m_{i-1},m_{i+1},\ldots,m_r) \atop
       \in M_1\times\cdots\times M_{i-1}\times M_{i+1}\times\cdots\times M_r}
   \sum_{m_i\in M_i}\!\!f(m_i)\;= $$
$$=\;|M_1\times\cdots\times M_{i-1}\times M_{i+1}\times\cdots\times M_r|
   \cdot\!\!\sum_{m_i\in M_i}\!\!f(m_i)\;= $$
$$=\;{|T|\over|M_i|}\cdot{\sum_{m_i\in M_i}\!\!f(m_i)}\;=\;
   |T|<\!\!f\!\!>_{M_i} $$
$$\ff\quad S\;=\nq\!\!\!
   \sum\limits_{(m_1,\ldots,m_r)\in T}\nq f(m_1)+\cdots+f(m_r)\;=\;
   |T|\left\{<\!\!f\!\!>_{M_1}+\cdots+<\!\!f\!\!>_{M_r} \right\} $$

F�r zwei Bedingungen ergibt sich:
$$\fbox{ $\displaystyle
\sum_{m_1\in M_1,m_2\in M_2}^{\rule{0ex}{1ex}}\nq\nq\;
   f(m_1)+f(m_2)\quad=\quad
   |M_2|\!\!\!\sum_{m_1\in M_1}\!\!\!f(m_1) \;+\;
   |M_1|\!\!\!\sum_{m_2\in M_2}\!\!\!f(m_2) $ } $$
%
Diese �quivalenz wird in der Routine {\it Bid} verwendet.

\subsection{ Zufallszahlen-Generatoren }
%            =========================

\subsubsection{ Gleichverteilte Zufallszahlen }
%               -----------------------------
Erstaunlicherweise sind selbst im hochentwickelten Compiler TC 2.0 von
Borland die angeblich gleichverteilten Zufallszahlen katastrophal
ungleichverteilt. Aus diesem Grund wurde
ein Einzeiler {\tt random2()} geschrieben, der {\tt random()} ersetzt
(und funktioniert !).

\subsubsection{ {\tt flip} }
%               ----------
{\tt flip(p)} liefert mit Wahrscheinlichkeit {\tt p} das Ergebnis {\tt TRUE},
wobei zu beachten ist, da� {\tt p} eine Fixpunktzahl ist
(\look\ref{FixP}).

\subsubsection{ Normalverteilung }
%               ----------------
Sehr schnell ist folgende Approximation der Normalverteilung, da:
\begin{itemize}
\item keine Flie�kommazahlen verwendet werden,       \vspace{-1ex}
\item nur {\it eine} 16-Bit Zufallszahl gezogen wird, \vspace{-1ex}
\item nur elementare (maschinennahe) Rechenoperationen ausgef�hrt werden.
\end{itemize}

Es werden die 1-Bits (Bits, deren Wert gleich 1 ist) der 16-Bit Zufallszahl
gez�hlt, durch 2 geteilt und 4 abgezogen. Da es 0 bis 16 1-Bits gibt
ist die Zufallsgr��e durch $\pm 4$ beschr�nkt.

\paragraph{ Mathematische Analyse }\hfill\\
%
Jedes Bit $i$ ist eine $\{0,1\}$ gleichverteilte Zufallsgr��e $B_i$,
d.h. 0 mit Wahrscheinlichkeit 1/2 und 1 mit Wahrscheinlichkeit 1/2.
$$ \ff\quad E(B_i)=1/2\quad,\quad Var(B_i)=1/4 $$
$$ \mbox{Sei}\qquad N={1\over 2}\sum_{i=1}^{16}{B_i} -4 $$
$$ \ff\quad E(N)={1\over 2}\cdot 16\cdot {1\over 2} -4=0 \quad,\quad
       Var(N)=\Bigl({1\over 2}\Bigr)^2\cdot 16\cdot {1\over 4} =1 $$
Nach dem zentralen Grenzwert-Satz geht eine $n$-fach-Summe einer
beliebigen Verteilung f�r $n\to\infty$ gegen eine Normalverteilung.

$\ff$ $N$ ist ungef�hr Standard-Normalverteilung ($n=16\;�\;\infty$),
wobei $N$ bei den Werten $\pm 4$ abgeschnitten ist.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{ Datenstrukturen }
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\subsection{ Konventionen }
%            ============
\subsubsection{ Anfangsbuchstaben }
%               -----------------
Um die Variablennamen einerseits nicht zu lang, das Progamm aber
andererseits nicht durch kryptische Namensgebung unleserlich zu machen,
wurden einige ein- oder mehrbuchstabige Namenskonventionen so weit wie
m�glich das ganze Programm durchgehalten.

Mittels Tabelle \ref{AId} und \ref{KzId} d�rften die meisten
Namensgebungen verst�ndlich werden.

\begin{table}\begin{center}
\begin{tabular}{|r@{ = }l|l|}\hline
\tt S  & Size of       & Konstante f�r den Compiler                            \\
\multicolumn{2}{|c|}{} & (z.B. physikalische Arrayl�nge)                       \\ \hline
\tt M  & Maximal       & Maximaler Wert                                        \\
\multicolumn{2}{|c|}{} & (z.B. gr��ter jemals benutzter Array-Index)          \\ \hline
\tt N  & Number of     & Anzahl, Zahl                                          \\
\multicolumn{2}{|c|}{} &  (z.B. gr��ter aktuell benutzter Array-Index)         \\ \hline
\tt T  & Type of       & Typen werden mit T begonnen                           \\ \hline
\tt pr & print         & Routinen, die etwas im Textmode anzeigen              \\ \hline
\tt in & input         & Routinen, die Eingaben von der Tastatur erwarten      \\ \hline
\tt N  & not/non       & Verneinung der Bedeutung der folgenden Buchstaben     \\ \hline
\tt D  & Default       & Defaultwerte (Konstanten)                             \\ \hline
\tt X  &               & Variablen, auf die nur indirekt �ber Zeiger zugegriffen wird \\ \hline
\tt P  & Pointer       & h�ufig auch als Endbuchstabe bei Ergebnisparametern   \\
\multicolumn{2}{|c|}{} & (z.B. NP = Pointer auf N)                             \\ \hline
\end{tabular}\end{center}\vspace{-3ex}
\caption{Bedeutung der Anfangsbuchstaben von Identifikatoren\label{AId}}\end{table}

\begin{table}\begin{center}
\begin{tabular}{|r|l|}\hline
\tt CFS & Classifier-System		\\ \hline
\tt M   & matching             		\\ \hline
\tt M   & Message              		\\ \hline
\tt MM  & matching Message     		\\ \hline
\tt C   & Classifier                	\\ \hline
\tt T   & Tupel                     	\\ \hline
\tt B   & Bid				\\ \hline
\tt H   & Help...			\\ \hline
\end{tabular}\end{center}\vspace{-3ex}
\caption{Abk�rzungen in Identifikatoren\label{KzId}}\end{table}

\subsubsection{ Konstanten und primitive Datentypen }
%               -----------------------------------
Einige zweckm��ige Definitionen von Konstanten und primitiven
Datentypen, wie {\tt bool}, {\tt byte}, {\tt index} u.a.
wurden eingef�hrt und k�nnen dem Programmlisting entnommen werden.
Im folgenden soll nur der Datentyp {\tt fixp},der {\tt float} ersetzt,
n�her erl�utert werden.
%
\paragraph{ FixPunkt-Zahlen }\hfill\label{FixP}

{\tt fixp} ist eine 2-Byte {\tt integer} Zahl,
wobei ein Byte als Vorkommateil,
der andere als Nachkommateil interpretiert wird.
Eine FixPunkt-Zahl {\tt fp} ist also als reelle Zahl {\tt fp/256} zu
interpretieren; umgekehrt kann eine reele Zahl {\tt r} mittels
{\tt (int)(r*256)} in FixPunkt-Format verwandelt werden, zu dem das Makro
{\tt FixP} zur Verf�gung steht. Aus diesem Grund werden im
{\tt EXAMPLE1.C}-File auch s�mtliche reelle Konstanten mittels

            \centerline{\tt fixp Name = FixP( xx.xx )}
definiert.

FixPunkt-Zahlen k�nnen wie {\tt int} mittels $+$ und $-$ addiert und
subtrahiert werden.
Zur Multiplikation, Division und Potenzierung stehen {\tt FPMult},
{\tt FPDiv} und {\tt FPPow} zur Verf�gung, die entweder mit Fehlerabfragen
({\tt SpeedF=FALSE}) implementiert sind oder als schnelle Makros
({\tt SpeedF=TRUE}) zur Verf�gung stehen.

\paragraph{ Strings, Messages, Conditions und Actions }\hfill

Eine Message ist eine Folge von 0en und 1en, deren L�nge mittels
{\tt SStr} (Size of String) festgelegt ist.
Die {\sl Condition-} und {\sl Action-}Teile von {\sl Classifiern} sind
Folgen von 0en, 1en und \#en, deren L�ngen ebenfalls durch {\tt SStr}
festgelegt sind.

Zur Codierung von {\sl Messages}, {\sl Conditions} und {\sl Actions}
wird als gemeinsamer Datentyp {\tt TString} verwendet, der je nach
{\tt SStr} 1 bis 4 Bytes im Speicher belegt:

\begin{table}[ht]\begin{center}
\begin{tabular}{|l|l|l|}\hline
\tt SStr  &\tt TString &\tt Bytes \\ \hline\hline
    1--8  &\tt byte    & 1        \\ \hline
    9--16 &\tt int     & 2        \\ \hline
    17--32&\tt long    & 4        \\ \hline
\end{tabular}\end{center}\vspace{-3ex}
\caption{Der Datentyp {\tt TString}}\end{table}

Eine 0/1-Stelle einer Message entspricht einfach einem Bit in {\tt TString}.
Unbenutzte Bits sind im Normalfall 0.

Zur Codierung von {\sl Conditions} werden zwei Variable (C und B) vom Typ
{\tt TString} verwendet und eine 0/1/\#-Stelle in einem korrespondierenden
Paar von Bits in C und B gespeichert, wobei C als {\sl Condition} und B als
Maske bezeichnet wird.

Bei einer spezifischen Stelle (0/1) wird in C (wie bei Messages) ein
Bit auf 0/1 gesetzt, das korrespondierende in C auf 1. Bei einer
unspezifischen Stelle (\#) werden  in C und B die korrespondierenden
Bits beide auf 0 gesetzt.

{\sl Actions} werden analog behandelt.

Diese Art der Codierung erlaubt ein effizientes
{\sl Message-Condition-Matching} und ben�tigt, nebenbei bemerkt,
nur wenig Speicher.

\begin{table}[ht]\begin{center}\begin{tabular}{|rcl|}\hline
\sl Condition &      & Bit 15 \dotfill\ 0 \\
01\#\#1101\#1 &$\gdw$& C=0000000100110101 \\
	      &	     & B=0000001100111101 \\ \hline
\end{tabular}\end{center}\vspace{-3ex}
\caption{Beispiel einer {\sl Condition}-Codierung}\end{table}

\paragraph{ Der Datentyp {\tt TIdVal} }\hfill

Ein zentraler Datentyp zur Selektion ist {\tt TIdVal}
oder besser \verb|TIdVal[]|, ein Array von {\tt TIdVal}.

\verb|    typedef struct { index Id; fixp  Val; } TIdVal;|

{\tt TIdVal} ist eine Struktur, die aus 2 integer-Werten besteht,
die im Normalfall folgende Bedeutung haben.

{\tt Id :} Ein Array-Index, der als {\tt Id} dieses Elements gilt. \\
{\tt Val:} Eine FixPunkt-Bewertung.

Da {\tt TIdVal} 4 Byte im Speicher belegt, kann {\tt TIdVal} auch
als {\tt long} aufgefa�t werden, was h�ufig vorteilhaft
(vor allem beim Kopieren) im Programm Verwendung findet.

\subsection{ Datenstruktur des Classifier-Systems }
%            ====================================
An dieser Stelle soll die gesamte Datenstruktur incl. deren Zugriff zu
Referenzzwecken graphisch dargestellt werden, Dokumentation der
einzelnen Strukturkomponenten findet man im Programmlisting.
\begin{itemize}
\item Eine mit {\tt x} beschriftete Linie bedeutet,
      da� der untere Datentyp eine Komponente des oberen ist,
      auf die mittels {\tt .x} zugegriffen werden kann.
\item Eine mit {\tt x} beschrifteter Pfeil bedeutet,
      da� der obere Datentyp eine Pointerkomponente \verb|->x| besitzt,
      die auf den unteren zeigt.
\item Eine unbeschriftete Kante zwischen zwei Komponenten deutet
      ihre �quivalenz an.
\end{itemize}
%
Mehrfachbeschriftungen sind als mehrfaches Auftreten von Komponenten
gleichen Typs zu interpretieren.

\boxfig{
\unitlength=1mm
\begin{picture}(110,40)
\put(55,35){\oval(20,10)[]}
\put(55,35){\makebox(0,0)[cc]{TCS}}
\put(40,5){\oval(20,10)[]}
\put(70,5){\oval(20,10)[]}
\put(100,5){\oval(20,10)[]}
\put(10,5){\oval(20,10)[]}
\put(49,30){\vector(-2,-1){40}}
\put(53,30){\vector(-2,-3){13.33}}
\put(57,30){\vector(2,-3){13.33}}
\put(61,30){\vector(2,-1){39}}
\put(10,5){\makebox(0,0)[cc]{TMessL}}
\put(40,5){\makebox(0,0)[cc]{TCFL}}
\put(70,5){\makebox(0,0)[cc]{TBidL}}
\put(100,5){\makebox(0,0)[cc]{TTupL}}
\put(39,25){\makebox(0,0)[rb]{MP}}
\put(29,20){\makebox(0,0)[rb]{NP}}
\put(19,15){\makebox(0,0)[rb]{OP}}
\put(46,20){\makebox(0,0)[rb]{CP}}
\put(43,15){\makebox(0,0)[rb]{EP}}
\put(64,20){\makebox(0,0)[lb]{CP}}
\put(67,15){\makebox(0,0)[lb]{EP}}
\put(81,20){\makebox(0,0)[lb]{TP}}
\put(91,15){\makebox(0,0)[lb]{UP}}
\end{picture}
}{Globale {\sl Classifier}-Datenstruktur TCS}

\boxfig{
\unitlength=1mm
\begin{picture}(110,78)
\put(70,73){\oval(20,10)[]}
\put(55,48){\oval(20,10)[]}
\put(10,23){\oval(20,10)[]}
\put(40,23){\oval(20,10)[]}
\put(70,23){\oval(20,10)[]}
\put(100,23){\oval(20,10)[]}
\put(65,68){\vector(-2,-3){10}}
\put(70,68){\vector(0,-1){15}}
\put(75,68){\vector(2,-3){10}}
\put(49,43){\line(-2,-1){31}}
\put(53,43){\line(-3,-4){11.33}}
\put(57,43){\line(3,-4){11.33}}
\put(61,43){\line(2,-1){31}}
\put(77,48){\makebox(0,0)[cc]{.....}}
\put(58,58){\makebox(0,0)[rb]{B}}
\put(70,58){\makebox(0,0)[rb]{C}}
\put(82,58){\makebox(0,0)[lb]{E}}
\put(70,73){\makebox(0,0)[cc]{TMessL}}
\put(55,48){\makebox(0,0)[cc]{TMess}}
\put(10,23){\makebox(0,0)[cc]{TString}}
\put(40,23){\makebox(0,0)[cc]{TIntens}}
\put(70,23){\makebox(0,0)[cc]{TCFId}}
\put(100,23){\makebox(0,0)[cc]{int}}
\put(28,33){\makebox(0,0)[rb]{M}}
\put(45,33){\makebox(0,0)[rb]{I}}
\put(65,33){\makebox(0,0)[lb]{CF}}
\put(82,33){\makebox(0,0)[lb]{H}}
\put(40,4){\oval(16,8)[]}
\put(40,18){\line(0,-1){10}}
\put(40,4){\makebox(0,0)[cc]{fixp}}
\put(70,4){\oval(16,8)[]}
\put(70,18){\line(0,-1){10}}
\put(70,4){\makebox(0,0)[cc]{index}}
\end{picture}
}{{\sl MessageList}-Datenstruktur {\tt TMessL}}

\boxfig{
\unitlength=1mm
\begin{picture}(145,118)
\put(75,113){\oval(20,10)[]}
\put(60,88){\oval(20,10)[]}
\put(70,108){\vector(-2,-3){10}}
\put(75,108){\vector(0,-1){15}}
\put(80,108){\vector(2,-3){10}}
\put(82,88){\makebox(0,0)[cc]{.....}}
\put(63,98){\makebox(0,0)[rb]{B}}
\put(75,98){\makebox(0,0)[rb]{C}}
\put(87,98){\makebox(0,0)[lb]{E}}
\put(10,53){\oval(20,10)[]}
\put(35,53){\oval(20,10)[]}
\put(60,53){\oval(20,10)[]}
\put(85,53){\oval(20,10)[]}
\put(110,53){\oval(20,10)[]}
\put(135,53){\oval(20,10)[]}
\put(55,83){\line(-2,-1){50}}
\put(57,83){\line(-1,-1){25}}
\put(59,83){\line(0,-1){25}}
\put(61,83){\line(3,-4){18.67}}
\put(63,83){\line(3,-2){39}}
\put(65,83){\line(3,-1){74}}
\put(15,63){\makebox(0,0)[rb]{C2}}
\put(25,68){\makebox(0,0)[rb]{C1}}
\put(37,63){\makebox(0,0)[rb]{Sp}}
\put(59,63){\makebox(0,0)[rb]{Act}}
\put(76,63){\makebox(0,0)[lb]{S}}
\put(80,72){\makebox(0,0)[lb]{Get}}
\put(86,68){\makebox(0,0)[lb]{Pay}}
\put(92,64){\makebox(0,0)[lb]{Tax}}
\put(98,60){\makebox(0,0)[lb]{PSP}}
\put(125,63){\makebox(0,0)[lb]{H}}
\put(86,109){\makebox(0,0)[lb]{\tiny BidMode}}
\put(88,107){\makebox(0,0)[lb]{\tiny SuppMode}}
\put(90,105){\makebox(0,0)[lb]{\tiny BidTupSelMode}}
\put(92,103){\makebox(0,0)[lb]{\tiny BidActSelMode}}
\put(94,101){\makebox(0,0)[lb]{\tiny FireBidSelMode}}
\put(96,99){\makebox(0,0)[lb]{\tiny FireTupSelMode}}
\put(98,97){\makebox(0,0)[lb]{\tiny MBids}}
\put(100,95){\makebox(0,0)[lb]{\tiny MAct}}
\put(102,93){\makebox(0,0)[lb]{\tiny MFire}}
\put(104,91){\makebox(0,0)[lb]{\tiny RiskFak}}
\put(106,89){\makebox(0,0)[lb]{\tiny SpecPow}}
\put(108,87){\makebox(0,0)[lb]{\tiny RelSuppPow}}
\put(110,85){\makebox(0,0)[lb]{\tiny EBidPow}}
\put(112,83){\makebox(0,0)[lb]{\tiny ESpecPow}}
\put(114,81){\makebox(0,0)[lb]{\tiny ClaimMode}}
\put(116,79){\makebox(0,0)[lb]{\tiny DisMode}}
\put(118,77){\makebox(0,0)[lb]{\tiny SumMode}}
\put(75,113){\makebox(0,0)[cc]{TCFL}}
\put(60,88){\makebox(0,0)[cc]{TCF}}
\put(10,53){\makebox(0,0)[cc]{TCond}}
\put(35,53){\makebox(0,0)[cc]{fixp}}
\put(60,53){\makebox(0,0)[cc]{TAct}}
\put(85,53){\makebox(0,0)[cc]{fixp}}
\put(110,53){\makebox(0,0)[cc]{fixp}}
\put(135,53){\makebox(0,0)[cc]{int}}
\put(10,23){\oval(20,10)[]}
\put(35,23){\oval(20,10)[]}
\put(60,23){\oval(20,10)[]}
\put(85,23){\oval(20,10)[]}
\put(10,23){\makebox(0,0)[cc]{TString}}
\put(35,23){\makebox(0,0)[cc]{TCType}}
\put(60,23){\makebox(0,0)[cc]{TString}}
\put(85,23){\makebox(0,0)[cc]{TCType}}
\put(10,48){\line(0,-1){20}}
\put(15,48){\line(1,-1){20}}
\put(60,48){\line(0,-1){20}}
\put(65,48){\line(1,-1){20}}
\put(10,38){\makebox(0,0)[rb]{C}}
\put(10,33){\makebox(0,0)[rb]{B}}
\put(30,33){\makebox(0,0)[lb]{T}}
\put(60,33){\makebox(0,0)[rb]{B}}
\put(60,38){\makebox(0,0)[rb]{A}}
\put(80,33){\makebox(0,0)[lb]{T}}
\put(84,110){\vector(1,-1){35}}
\put(119.50,72){\oval(11,6)[]}
\put(35,4){\oval(16,8)[]}
\put(35,18){\line(0,-1){10}}
\put(35,4){\makebox(0,0)[cc]{int}}
\put(85,4){\oval(16,8)[]}
\put(85,18){\line(0,-1){10}}
\put(85,4){\makebox(0,0)[cc]{int}}
\end{picture}
}{{\tt ClassifierList- \& EffectorList}-Datenstruktur {\tt TCFL}}

\boxfig{
\unitlength=1mm
\begin{picture}(145,83)
\put(75,78){\oval(20,10)[]}
\put(60,53){\oval(20,10)[]}
\put(70,73){\vector(-2,-3){10}}
\put(75,73){\vector(0,-1){15}}
\put(80,73){\vector(2,-3){10}}
\put(82,53){\makebox(0,0)[cc]{.....}}
\put(63,63){\makebox(0,0)[rb]{B}}
\put(75,63){\makebox(0,0)[rb]{C}}
\put(87,63){\makebox(0,0)[lb]{E}}
\put(10,23){\oval(20,10)[]}
\put(35,23){\oval(20,10)[]}
\put(60,23){\oval(20,10)[]}
\put(85,23){\oval(20,10)[]}
\put(110,23){\oval(20,10)[]}
\put(135,23){\oval(20,10)[]}
\put(55,48){\line(-2,-1){40}}
\put(57,48){\line(-1,-1){20}}
\put(59,48){\line(0,-1){20}}
\put(61,48){\line(1,-1){20}}
\put(63,48){\line(2,-1){40}}
\put(65,48){\line(3,-1){62}}
\put(75,78){\makebox(0,0)[cc]{TBidL}}
\put(60,53){\makebox(0,0)[cc]{TBid}}
\put(25,33){\makebox(0,0)[rb]{CF}}
\put(42,33){\makebox(0,0)[rb]{BV}}
\put(59,33){\makebox(0,0)[rb]{EV}}
\put(76,33){\makebox(0,0)[lb]{Tup}}
\put(93,33){\makebox(0,0)[lb]{N}}
\put(110,33){\makebox(0,0)[lb]{F}}
\put(10,23){\makebox(0,0)[cc]{TCFId}}
\put(35,23){\makebox(0,0)[cc]{fixp}}
\put(60,23){\makebox(0,0)[cc]{fixp}}
\put(85,23){\makebox(0,0)[cc]{TTupId}}
\put(110,23){\makebox(0,0)[cc]{int}}
\put(135,23){\makebox(0,0)[cc]{bool}}
\put(10,4){\oval(16,8)[]}
\put(10,18){\line(0,-1){10}}
\put(10,4){\makebox(0,0)[cc]{index}}
\put(47,10){\oval(44,10)[]}
\put(47,10){\makebox(0,0)[cc]{long}}
\put(85,4){\oval(16,8)[]}
\put(85,18){\line(0,-1){10}}
\put(85,4){\makebox(0,0)[cc]{index}}
\end{picture}
}{{\sl BidList}-Datenstruktur {\tt TBidL}}

\boxfig{
\unitlength=1mm
\begin{picture}(55,83)
\put(40,78){\oval(20,10)[]}
\put(25,53){\oval(20,10)[]}
\put(35,73){\vector(-2,-3){10}}
\put(40,73){\vector(0,-1){15}}
\put(45,73){\vector(2,-3){10}}
\put(47,53){\makebox(0,0)[cc]{.....}}
\put(28,63){\makebox(0,0)[rb]{B}}
\put(40,63){\makebox(0,0)[rb]{C}}
\put(52,63){\makebox(0,0)[lb]{E}}
\put(10,23){\oval(20,10)[]}
\put(40,23){\oval(20,10)[]}
\put(22,48){\line(-1,-2){10}}
\put(28,48){\line(1,-2){10}}
\put(14,33){\makebox(0,0)[rb]{M2}}
\put(17,38){\makebox(0,0)[rb]{M1}}
\put(35,35){\makebox(0,0)[lb]{S}}
\put(40,78){\makebox(0,0)[cc]{TTupL}}
\put(25,53){\makebox(0,0)[cc]{TTup}}
\put(10,23){\makebox(0,0)[cc]{TMessId}}
\put(40,23){\makebox(0,0)[cc]{fixp}}
\put(10,4){\oval(16,8)[]}
\put(10,18){\line(0,-1){10}}
\put(10,4){\makebox(0,0)[cc]{index}}
\end{picture}
}{{\sl TupelList}-Datenstruktur {\tt TTupL}}
\clearpage

%\subsection{ Simulationsdynamik }
%            ==================
%\boxfig{\input empty.PIC}{Dynamische \& Statische Beziehung}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% \section{ Hauptzyklus }
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

% {\it Siehe die in K�rze von Gerhard Wei� erscheinende
% Benutzerbeschreibung \cite{Weiss}}.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{ Benutzer-Oberfl�che }
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\subsection{ Start des Klassifizierungs-Systems }
%           ==================================
Es ist vorteilhaft (aber nicht zwingend notwendig) das \CFS\ unter einem
C-Compiler mit integrierter Entwicklungsumgebung (IDE) oder von einem
C-Debugger aus zu starten, da jene Umgebungen auch als Arbeitsumgebung
des \CFS\ verwendbar sind. Hier soll die Benutzung des \CFS\ bei
Verwendung des Turbo-C 2.0 oder Turbo-C++ Compilers beschrieben
werden.

Ben�tigt werden zwei C-Files:
\begin{description}
\item{\verb|CFSSIM.C  |:} Das Klassifizierungs-System
\item{\verb|EXAMPLEn.C|:} Die beispielspezifische Daten, wie
			  Benutzer-Parameter \& Benutzer-Funktionen
\end{description}
%
{\tt EXAMPLE1.C} enth�lt als Beispiel den 4:2-Decoder, der in
\cite{Goldberg} und \cite{Wilson} beschrieben ist, auf das ich mich
im folgenden beziehe.

Da die Beispiele einige Parameter (die mit \verb|#define| definierten)
enthalten, die den Objekt-Code von {\tt CFSSIM.OBJ} bestimmen, kann
{\tt CFSSIM.C} nicht {\it einmal} vorweg compiliert werden.
Daher wurde folgender Weg gew�hlt.

{\tt EXAMPLE$n$.C} ist {\it ihr} Bezugsfile (Main-File) den Sie mit dem
Turbo-C-Editor ggf. modifizieren und starten.
Die \verb|#include|-Zeile bewirkt dann, da� {\tt CFSSIM.C} mit den
aktuellen \verb|#define|-Paramtern compiliert wird.

Bevor Sie das Programm starten sollten Sie unbedingt in die Zeile, in
der \verb|BreakPoint()| steht, mit {\tt Ctrl-F8} einen Breakpoint setzen.
Damit k�nnen Sie wie in \ref{ParMod} beschrieben wird jederzeit
das \CFS\ kurz unterbrechen und in die IDE gelangen,
Parameter modifizieren und das \CFS\ an der Unterbrechungsstelle fortsetzen.

Die Schritte sind im einzelnen:

\begin{center}\begin{tabular}{ll}
\bf Eingabe            & \bf Bedeutung \\[1ex]
\tt{TC} o.�.           & Aufruf von Turbo-C \\
\tt Alt-F L EXAMPLE1.C & Laden des Beispiels \\
    ??                 & Eventuell modifizieren \\
\tt Ctrl-F8            & Breakpoint in Zeile \verb|BreakPoint()| setzen \\
\tt Alt-R R            & Start des \CFS\ \\
    ??                 & Verschiedene \CFS-Menu-Eingaben \ref{Menu} \\
\tt B                  & R�ckkehr in die IDE von Turbo-C \\
\tt Ctrl-F4 \it Name=Wert & Modifikation von Paramtern \\
\tt Alt-R R            & Fortsetzen der \CFS-Simulation \\
\ldots                 & \\
\end{tabular}\end{center}

\subsection{ Menusteuerung }\label{Menu}
%            =============
Nachdem Sie das \CFS\ mittles {\tt Alt-R R} gestartet haben, erscheint in der
1.~Zeile eine Menu-Leiste. Die Gro�buchstaben geben die den Menupunkt
aktivierenden Tasten an, deren Bedeutung im einzelnen in \ref{Menu1}
bis \ref{MenuN} erkl�rt wird. Unterhalb der Menu-Leiste erscheint die
Simulations�berschrift, die auch ins Protokoll aufgenommen wird.
Danach wird das Protokoll abgeschaltet und die Simulation gestartet
(Initialisierung u.a.) und knapp vor Eintritt in den 1.~Zyklus
unterbrochen. Danach erwartet das \CFS\ eine Menu-Eingabe
(z.B. {\tt C} um die Simulation fortzusetzen).
Solche Menu-Eingaben k�nnen auch sp�ter
{\it jederzeit}, d.h. auch w�hrend die Simulation l�uft, erfolgen.

\subsubsection{ Ausgabe ({\tt 0123}) ({\tt Display}) }\label{Menu1}
%               ------------------------------------
Mit der Taste \fbox D wird der aktuelle Status des \CFS\ angezeigt.
Mit den Tasten \fbox 0 bis \fbox 3 wird die Ausf�hrlichkeit
s�mtlicher Ausgaben beeinflu�t.
F�r Details \look\ref{StStAus} und Anhang C.

\subsubsection{ Einzelschritt-Abarbeitung ({\tt stEp}) ({\tt ESC}) ({\tt Cont}) }
%              ---------------------------------------------------------------
Im {\tt SingleStep-Mode} wird die Simulation nach jedem Zyklus oder
jeder Episode angehalten.
Ist {\tt SingleStep=OFF}, so l�uft die Simulation solange, bis
sie mit \fbox{ESC} (oder A oder B) unterbrochen wird.
In beiden F�llen kann die Simulation mit \fbox C oder \fbox{\it space}
fortgesetzt werden. Mit \fbox E kann der {\tt SingleStep-Mode}
aus- und auch wieder eingeschaltet werden.

\subsubsection{ Protokoll ({\tt Prot}) }
%               ---------------------
Die �berschrift incl. Zeitpunkt des Simulationsstarts wird immer
mitprotokolliert. Zu jedem Zeitpunkt kann man mit \fbox P die
Protokollierung ein- und auch wieder ausschalten. Ist {\tt Protocoll=ON},
so wird {\it alles}, was auf dem Bildschirm erscheint auch an das File,
deren Name in {\tt EXAMPLE$n$.C} durch {\tt ProtDev[]} angegeben wurde,
{\it angeh�ngt}; d.h. ein evtl. bestehendes Protokoll wird nicht gel�scht,
sondern erweitert.

�ndert man den Protokollnamen w�hrend der Simulation, so ist zu
beachten, da� dieser neue Name erst nach einmaligem Tastendruck \fbox P
aktiviert wird.

{\bf Tip:} Den Protokoll-File kann man einfach und schnell
	   mit dem Turbo-Editor inspizieren und evtl. aufbereiten.

\subsubsection{ Parameter-Modifikation ({\tt Break}) }\label{ParMod}
%               ------------------------------------
Parameter k�nnen nach Beendigung der Simulation mittels \fbox A im
{\tt EXAMPLE$n$.C}-File modifiziert und das \CFS\ neu compiliert und
gestartet werden.

Wesentlich schneller kann man dies auch erreichen, indem man mit
\fbox B die Simulation unterbricht
(nur wenn der Breakpoint gesetzt wurde, da dieser aufgerufen wird !).

Nun befinden Sie sich in der IDE (oder im
Debugger) und d�rfen alles machen, was ihnen die IDE gestattet; nur
den Source-File sollten Sie nicht modifizieren.

Die h�ufigste Anwendung wird wohl die Einsichtnahme in oder die
Modifikation von Benutzer-Parametern (\look Kapitel \ref{BenPar}) sein.
Dies k�nnen Sie mittels \\[2ex]
%
\centerline{\tt Ctrl-F4 $Name$ \fbox{\it return} $bzw.$ Ctrl-F4 $Name=Wert$ }

erreichen. F�r Details siehe Turbo-C-Beschreibung.

Die Simulation k�nnen Sie mit \fbox{Alt-R} \fbox R fortsetzen,
wollen Sie die Simulation neu starten, dr�cken Sie anschlie�end
noch R (Restart).
Auf keinen Fall sollten Sie den Neustart von der IDE aus z.B. mittels
Alt-R P Alt-R R vornehmen, da diese ihre Parametermodifikationen
r�ckg�ngig macht.

\subsubsection{ Sonstige Menu-Befehle }\label{MenuN}
%               ---------------------
Mit \fbox R (Restart) k�nnen Sie das \CFS\ neu starten. R ist in jeder
Hinsicht ein absoluter Neustart, auch der Zufallszahlen-Generator wird wie beim
Erstaufruf gesetzt. Somit lassen sich Simulationsl�ufe exakt
reproduzieren. \\
Mit \fbox Z ({\tt rdZ}) kann der Zufallszahlen-Generator zuf�llig
(nicht reproduzierbar) initialisiert werden. \\
Der Warnton bei Warnungen und Fehlern l��t sich mittels
\fbox S (Sound) aus- und einschalten.

\fbox T ({\tt Test}) ruft die Routine {\tt Test} auf,
die sich in {\tt CFSSIM.C} befindet,
aber auch nach {\tt EXAMPLE$n$.C} gelegt werden kann und bei Bedarf mit
beliebigem Inhalt gef�llt werden kann.

\subsubsection{ Status- \& Statistik-Ausgabe }\label{StStAus}
%               ----------------------------
Neben Fehlermeldungen, Warnungen und anderem ''Kleinkram'' k�nnen der
{\sl Classifier}status (CS) und die Statistik (ST) als Einzeiler oder
ausf�hrlich angezeigt werden. Dies erfolgt entweder mit der Taste D
(Display) oder automatisch w�hrend der Simulation. Wie und wann was
erscheint kann der Tabelle \ref{prmode} und dem Beispielprotokoll
im Anhang C entnommen werden.

\begin{table}[ht]\begin{center}\begin{tabular}{|c|c|c|c|}\hline
\tt prMode &\bf Anzeige pro Schritt &\bf Anzeige pro Episode &\bf weiteres \\ \hline\hline
3 & CS ausf�hrlich & CS \& ST ausf�hrlich &\sl Warnings \& Errors \\ \hline
2 & CS einzeilig   & CS \& ST ausf�hrlich &\sl Warnings \& Errors \\ \hline
1 & ---            & Stat einzeilig       &\sl Warnings \& Errors \\ \hline
0 & ---            & ---                  &\sl Errors             \\ \hline
\end{tabular}
\caption{Ausgabe in den verschiedenen {\sl Print-Modes}\label{prmode}}
\end{center}\end{table}

Jeder Warnung ist die H�ufigkeit ihres bisherigen Auftretens
vorangestellt. Dies hat folgenden Sinn: \\
Da manchmal Warnungen penetrant h�ufig auftreten,
man deren Ursache aber erst sp�ter beheben m�chte,
wird ab der vierten Warnung (eines Typs) diese nur noch
stichprobenartig ausgegeben, und zwar im Laufe der Zeit immer
seltener. An der Nummerierung erkennt man aber dennoch wie h�ufig die
Warnung in der Zwischenzeit erzeugt wurde. Dieses Konzept hat den
Vorteil, da� schon nach kurzer Zeit die Anzeige frei von l�stigen
Warnungen bleibt. Es versteht sich von selbst, da� man sich trotzdem
Gedanken dar�ber machen sollte, ob eine Warnung nicht doch ihre
Berechtigung hat.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% \section{ Benutzer-Funktionen }
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

% {\it Siehe die in K�rze von Gerhard Wei� erscheinende
% Benutzerbeschreibung \cite{Weiss}.}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{ Benutzer-Parameter }\label{BenPar}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\newenvironment{CFSParTab}{\begin{center}\begin{tabular}{|l|l|l|} \hline
  \bf Name & \bf Bereich & \bf Beschreibung\\\hline\hline}%
  {\end{tabular}\end{center}\vspace{-3ex} }

Eine ausf�hrliche Beschreibung aller Benutzer-Parameter und deren
Wirkungsweise findet man in \cite{Weiss}. Tabellarische �bersichten sind
hier abgebildet.

Zus�tzlich zu den theoretischen Bereichen ergeben sich noch
Einschr�nkungen durch die physikalischen Datentypen,
wie {\tt int}, {\tt long}, \ldots.

\begin{table}\begin{CFSParTab}
\tt SMessL  & 1\ldots$\infty$ & Max. L�nge der {\sl Message}-Liste incl. Detektor-{\sl Message}. \\ \hline
\tt SOutL   & 1\ldots$\infty$ & Max. Anzahl von Aktionen {(\sl Output-Message)}. \\ \hline
\tt SCFL    & 1\ldots$\infty$ & Anzahl der {\sl Classifier}. \\ \hline
\tt SEffL   & 1\ldots$\infty$ & Anzahl der Effektoren. \\ \hline
\tt SBidL   & 1\ldots$\infty$ & Max. Anzahl von {\sl Bid's} bzw. {\sl Bid-Tupels}. \\ \cline{1-2}
\tt STupL   & 1\ldots$\infty$ & W�hlen Sie {\tt SBidL} und {\tt STupL} so gro� wie m�glich. \\ \hline\hline
\tt SStr    & 1\ldots 32      & {\sl Message},{\sl Condition} \& {\sl Action}-L�nge, \\
	    &                 & d.h. Anzahl der 0/1/\#-Stellen. \\ \hline
\tt TwoCond &\tt FALSE        & {\sl Classifier} haben eine {\sl Condition}. \\ \cline{2-3}
	    &\tt TRUE         & {\sl Classifier} haben zwei {\sl Conditions}. \\ \hline
\tt SpeedF  &\tt FALSE        & Evtl. auftretende Fehler werden �berpr�ft \\
	    &                 & und als {\sl Warning} oder {\sl Error} angezeigt. \\ \cline{2-3}
	    &\tt TRUE         & CFS ist auf Zeit optimiert. \\ \hline
\end{CFSParTab}\caption{Array-Gr��en und andere Compiler-Information}\end{table}

\begin{table}\begin{CFSParTab}
\tt StRate    & 1\ldots$\infty$ & Episodenl�nge: Anzahl der Zyklen, nach denen und \\
	      &                 & f�r die eine Statistik berechnet und angezeigt wird. \\ \hline
\tt SclSel    &50\%\ldots 100\% & Skalierungsfaktor bei {\tt SelMode=4} (\look\ref{SclSelImpl}). \\ \hline
\tt ProtDev   &                 & Protokoll-Filename als String.\\ \hline
\tt DetMessTag&                 & {\it Tag's} f�r Detektor-{\sl Message} als String \\ \hline
\tt EffMessTag&                 & {\it Tag's} f�r Effektor-{\sl Message} als String \\ \hline
\end{CFSParTab}\caption{Allgemeine Variablen}\end{table}

\begin{table}\begin{CFSParTab}
\tt DetRate   & 1\ldots$\infty$ & Detektor-Aufruf-Rate \\ \hline
\tt MDetM     & 1\ldots\tt SMessL& Max. Anzahl von \sl Detector-Messages \\ \hline
\tt DefDetMI  & 0.0\ldots 9.0   & \sl Default-Detector-Message-Intensity \\ \hline
\tt DefStr    & 0.0\ldots 9.0   & \sl Default-Classifier-Strength \\ \hline
\tt DefStrDev & 0\ldots 25\%    & \sl Default-Classifier-Strength-Deviation\\ \hline
\end{CFSParTab}\caption{{\tt Detector}-Variablen}\end{table}

\begin{table}\begin{CFSParTab}
\tt DefNMI    & 0.0\ldots 9.0   & {\sl Default-Non-Match-Intensity:} \\
	      &                 & {\sl Message-Intensity}-Ersatzwert bei negativen \\
	      &                 & {\sl Conditions} \\ \hline
\tt Dev2      & 0\ldots 25\%    & \sl EBid-Deviation \\ \hline
\tt DelMessSelMode &-6\ldots 6  & {\sl Selection-Mode} bei zu vielen {\sl Messages} \\
		   &            & in abh. der {\sl Intensity} \\ \hline
\tt CleanHallF& \tt FALSE       & {\sl Classifier} mit {\sl Detector-Tag} werden nicht gel�scht \\
              & \tt TRUE        & {\sl Classifier} mit {\sl Detector-Tag} werden gel�scht \\ \hline
\tt EffRate   & 1\ldots$\infty$ & Effektor-Aufruf-Rate \\ \hline
\end{CFSParTab}\caption{{\tt Matching-, Bid-, Clean- \& Effector-}Variablen}\end{table}

\begin{table}\begin{CFSParTab}
\tt ReRate    & 1\ldots$\infty$ & {\sl Reinforcement}-Aufruf-Rate \\ \hline
\tt CreditMode& 1\ldots 4       & 1 = Expliziter {\sl Bucket-Brigade} \\
              &                 & 2 = Impliziter {\sl Bucket-Brigade} (nicht impl.) \\
	      &                 & 3 = {\sl Profit-Sharing-Plan} (PSP) \\
	      &                 & 4 = Kein {\sl Credit-Assignment} \\ \hline
\tt NMFrac    & 0\ldots 100\%   & Reduzierter {\sl Reinforcement / Credit} f�r \\
	      &                 & {\sl Classifier} mit negativer {\sl Condition} \\ \hline
\tt DetFrac   & 0\ldots 100\%   & Reduzierter {\sl Reinforcement / Credit} f�r \\
              &                 & {\sl Detector-Messages} \\ \hline
\tt PSPFrac   & 0\ldots 100\%   & PSP-Reduktions-Konstante \\ \hline
\tt PSPDisMode& 1\ldots 4       & PSP-{\sl Reinf.-Distr.} f�r {\sl Classifier} ist prop. \\
	      &                 & 1 = eins \\
	      &                 & 2 = Anzahl der {\sl Bids} \\
	      &                 & 3 = maximalem {\sl Bid}-Wert \\
	      &                 & 4 = Summe der {\sl Bid}-Werte \\ \hline
\end{CFSParTab}\caption{{\tt Credit}-Variablen}\end{table}

\begin{table}\begin{CFSParTab}
\tt HeadTax   & 0.0\ldots 9.0   & {\sl Taxes} pro Zyklus \\ \hline
\tt MessTax   & 0.0\ldots 9.0   & {\sl Taxes} f�r das Senden einer {\sl Message} \\ \hline
\tt BidTax    & 0.0\ldots 9.0   & {\sl Taxes} f�r das Bieten ({\sl Bid}) \\ \hline
\tt BidTaxMode& 1\ldots 2       & 2 = Zahle nur, falls Bieten nicht zum Feuern f�hrte \\
	      &                 & 1 = Zahle immer \\ \hline
\tt MultBidTaxF  & \tt TRUE     & Zahle f�r jeden {\sl Bid} extra \\ \cline{2-3}
		 & \tt FALSE    & Zahle einmal f�r alle {\sl Bids} \\ \hline
\tt MultMessTaxF & \tt TRUE     & Zahle f�r jede gefeuerte {\sl Message} \\ \cline{2-3}
		 & \tt FALSE    & Zahle einmal f�r alle gefeuerten {\sl Messages} extra \\ \hline
\end{CFSParTab}\caption{{\tt Taxes}-Variablen}\end{table}

\begin{table}\begin{CFSParTab}
\tt MaxStr    & 1.0\ldots 20.0  & Max. {\sl Classifier-Strength} \\ \hline
\tt MinStr    & 0.0\ldots 1.0   & Min. {\sl Classifier-Strength} \\ \hline
\end{CFSParTab}\caption{{\tt StrUpDate}-Variablen}\end{table}

\begin{table}\begin{CFSParTab}
\tt GenRate   & 1\ldots$\infty$ & Aufruf-Rate des genetischen Algorithmus' \\ \hline
\tt NCFRepl   & 0\ldots {\tt SCFL} & Anzahl der zu ersetzenden {\sl Classifier} \\ \hline
\tt ReplSelMode& -6\ldots 6     & {\sl Selection-Mode} beim Ersetzen der {\sl Classifier} \\
	      &                 & in abh. von {1/\sl Strength} \\ \hline
\tt NCFMut    & 0\ldots {\tt SCFL} & Anzahl der zu mutierenden {\sl Classifier} \\ \hline
\tt NMutate   & 0\ldots {\tt SStr} & Mutationen pro {\sl Condition / Action} \\ \hline
\tt MutSelMode& -6\ldots 6      & {\sl Selection-Mode} beim Mutieren der {\sl Classifier} \\
              &                 & in abh. von {1/\sl Strength} \\ \hline
\tt CondSp    & 0\ldots 100\%   & Spezifizit�t der {\sl Condition bzw. Action}, d.h. \\ \cline{1-2}
\tt ActSp     & 0\ldots 100\%   & Wahrscheinlichkeit einer nicht-\#-Stelle \\ \hline
\tt NegCondP  & 0\ldots 100\%   & Wahrscheinlichkeit einer negativen {\sl Condition} \\ \hline
\end{CFSParTab}\caption{{\tt Genetic}-Variablen}\end{table}

\begin{table}\begin{CFSParTab}
\tt DelMessMode & 0\ldots 2     & 0 = l�sche keine {\sl Messages}. \\
                &               & 1 = l�sche {\sl Messages} mit {\sl Effector-Tag}. \\
                &               & 2 = l�sche alle {\sl Messages} \\ \hline
\end{CFSParTab}\caption{{\tt ReInit}-Variablen}\end{table}

\begin{table}\begin{CFSParTab}
\tt BidMode   & 1\ldots 4       & 1 = ein {\sl Bid} pro {\sl Classifier} \\
              &                 & 2 = ein {\sl Bid} pro {\sl Matching-Tupel} \\
              &                 & 3 = Wie 1 -- nur: Aktionsliste statt Tupel-Liste \\
              &                 & 4 = Wie 2 -- nur: ein {\sl Bid} pro Aktion \\ \hline
\tt SuppMode  & 1\ldots 2       & 1 = Z�hle die {\sl Intensity} bei {\sl BidTupels} \\
              &                 & \qquad mit zwei gleichen {\sl Messages} nur einfach \\
              &                 & 2 = Addiere die {\sl Intensity} beider {\sl Messages} \\ \hline\hline
\tt BidTupSelMode & -6\ldots 6  & Mode zum Selektieren von Tupeln in {\tt MatchBid} \\ \hline
\tt BidActSelMode & -6\ldots 6  & Mode zum Selektieren von Aktionen in {\tt MatchBid} \\ \hline
\tt FireBidSelMode& -6\ldots 6  & Mode zum Selektieren von {\sl Bids} in {\tt Fire} \\ \hline
\tt FireTupSelMode& -6\ldots 6  & Mode zum Selektieren von Tupeln in {\tt Fire} \\ \hline\hline
\tt MBids     & 1\ldots$\infty$ & Max. Anzahl von {\sl Bids} pro {\sl Classifier} \\ \hline
\tt MAct      & 1\ldots$\infty$ & Max. Anzahl von {\sl Actions} pro {\sl Classifier} \\ \hline
\tt MFire     & 1\ldots$\infty$ & Max. Anzahl von gefeuerten {\sl Messages} pro {\sl Classifier} \\ \hline\hline
\tt RiskFak   & 0\ldots 100\%   & Berechnung des (effektiven) {\sl Bids} mittels: \\ \hline
\tt SpecPow   & 0\ldots 2       & \\ \cline{1-2}
\tt RelSuppPow& 0\ldots 2       & \raisebox{1.5ex}[-1.5ex]
  {$ Bid=RiskFak\cdot Strength\cdot Spec^{SpecPow}\cdot RelSupp^{RelSuppPow} $} \\ \hline
\tt EBidPow   & 0\ldots 2       & \\ \cline{1-2}
\tt ESpecPow  & 0\ldots 2       &  \raisebox{1.5ex}[-1.5ex]
  {$ EffBid=[Bid+Noise(Bid\cdot Dev2)]^{EBidPow}\cdot Spec^{ESpecPow} $} \\ \hline\hline
              &                 & Modes f�r expliziten {\sl Bucket-Brigade} \\ \hline
\tt ClaimMode & 1\ldots 2       & Mehrfache Verwendung einer {\sl Message} wird dem Sender \\
              &                 & 1 = nur einfach, 2 = mehrfach verg�tet. \\ \hline
\tt DisMode   & 1\ldots 2       & 1 = {\sl Credit} ist unabh�ngig von der {\sl Message-Intensity} \\
              &                 & 2 = {\sl Credit} ist prop. zur {\sl Message-Intensity} \\ \hline
\tt SumMode   & 1\ldots 3       & 1 = Teil des {\sl Reinf.} bzw. {\sl Bids} geht verloren ({\tt NMFrac}) \\
	      &                 & 2 = {\sl Reinf.} bzw. {\sl Bid} wird restlos aufgeteilt \\
	      &                 & 3 = Jeder {\sl Classifier} bekommt vollen {\sl Reinf.} bzw {\sl Bid} \\ \hline
\end{CFSParTab}\caption{{\sl Classifier/Effector}-Variablen}\end{table}
\clearpage

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{ Erg�nzungen und Ausblicke }
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

Das Programm ist so konzipiert, da� es in vielerlei Hinsicht erweitert
werden kann. Dies betrifft sowohl programmspezifische Erweiterungen,
wie z.B.
%
\begin{itemize}
\item Menu-Punkte, um Simulations-Status auf Diskette abzuspeichern
      und von Diskette zu laden.
\item Compileroptionen (besonders um {\sl Compiler-Warnings} zu unterdr�cken)
      mittels \verb|#pragma warn| $xyz$ ins Programm aufnehmen.
\item Per Menu ein- und ausschaltbare {\sl Warnings}.
\item Flexible Skalierung von FixPunkt-Zahlen.
\item Unterst�tzung von \CFS-Aufrufen durch {\sl Batch}-Prozesse.
\end{itemize}
%
als auch Erweiterungen des CFS selbst, wie z.B.
%
\begin{itemize}
\item Profit-Sharing-Plan ({\tt CreditMode=2}).
\item Erweiteter genetischer Algorithmus (Kreuzung, H�ufung,
      getriggerter GA,\ldots) \look\cite{Goldberg}
      (Wird bis Ende '91 zur Verf�gung stehen).
\item Tree \& Food Beispiel von Wilson \cite{Wilson}
      (und andere Beispiele).
\end{itemize}
%
Eine Benutzerbeschreibung des Klassifizierungs-Systems findet sich
in \cite{Weiss}

Abschlie�end sei noch darauf hingewiesen, da� f�r die
Fehlerfreiheit dieses Programms -- nat�rlich -- keine Garantie
�bernommen werden kann.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{ Was tun im Fehlerfall ? }
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

Im Folgenden werden eine Reihe von Warnungen und Fehlern beschrieben,
die evtl. beim Simulationslauf auftreten k�nnen und deren Ursache
meist in fehlerhaften oder kritischen Benutzer-Variablen oder
Benutzer-Funktionen liegt.

\subsection{ Warnungen }
%            =========
Warnungen sind im Normallfall ebenso wie Fehlermeldungen vom Benutzer
ernst zu nehmen und bei der n�chsten Gelegenheit zu beheben.
Allerdings wird bei Warnungen, im Gegensatz zu Fehlermeldungen, die
Simulation fortgesetzt (\look\ref{StStAus}).
%
\begin{description}
\item{\tt Warning 0: Unspecific Warning} \\
     Programmfehler: Benachrichtigen Sie den Programmierer.
\item{\tt Warning 1: Division underflow} \\
     {\it Bei der Division wird eine Zahl derart klein, da� sie
          in der FixPunkt-Darstellung zu Null wird} \\
     Tritt diese Warnung h�ufiger auf, und sind generell die
     FixPunkt-Werte, die in Status und Statistik angezeigt werden
     recht klein (alle kleiner als 5), so sollten Sie versuchen,
     alle Benutzer-Parameter {\sl (Taxes, Reinf, \ldots)} neu zu skalieren,
     d.h. alle mit einer Konstanten zu multiplizieren, was ja nichts
     an der Funktionalit�t �ndert.
\item{\tt Warning 2: QMax called with k=0} \\
     {\it{\tt QMax} sollte die Null gr��ten Elemente suchen} \\
     Programmfehler: Benachrichtigen Sie den Programmierer.
\item{\tt Warning 3: ProbSel called with N=0} \\
     {\it{\tt ProbSel} sollte aus Null Elementen $k>0$ ausw�hlen} \\
     Programmfehler: Benachrichtigen Sie den Programmierer.
\item{\tt Warning 4: Tupellist is full} \\
     {\it In der Liste der Bidtupels ist kein Platz mehr f�r weitere
          Eintragungen} \\
     Dimensionieren Sie die Tupelliste mit {\tt STupL} so gro� wie
     m�glich (es Ihre Speicherkapazit�t zul��t). Haben Sie trotz
     eines relativ kleinen Beispiels (wenig {\sl Classifier} und {\sl Messages})
     und gro�er Tupelliste Schwierigkeiten, so sollten Sie in Betracht
     ziehen, {\tt MBids} bzw. {\tt MAct} zu verkleinern.
     Eine �bervolle Tupelliste kann auch Ursache zu unspezifischer
     {\sl Classifier-Conditions} sein. Ist dies der Fall, so sollten Sie
     {\tt CondSp} erh�hen.
\item{\tt Warning 5: Bidlist is full} \\
     {\it In der Liste der Bids ist kein Platz mehr f�r weitere
          Eintragungen} \\
     Dimensionieren Sie die Bidliste mit {\tt SBidL} so gro� wie
     m�glich (es Ihre Speicherkapazit�t zul��t). Eine �bervolle
     Tupelliste kann auch Ursache zu unspezifischer
     Classifier-Conditions sein. Ist dies der Fall, so sollten Sie
     {\tt CondSp} erh�hen.
\item{\tt Warning 6: Selection of Zero-Values} \\
     {\it Bei einem Selektionsvorgang wurden Elemente mit Bewertung
	  {(\tt Val)} Null ausgew�hlt, die meist Ursache
	  vorangegangener Unterl�ufe sind} \\
     Beachten Sie die unter Warning 1 angegebenen Hinweise.
\item{\tt Warning 7: BestSelMode must be positive} \\
     {\it Die k besten Elemente mit Wiederholung zu selektieren
          macht keinen Sinn} \\
     Ersetzen Sie $x${\tt SelMode=-3} durch $x${\tt SelMode=+3}.
\item{\tt Warning 8: Too many matching tuples} \\
     {\it Es gibt {\rm einen} Classifier, den zu viele Tupels matchen} \\
     Beachten Sie die unter Warning 4 angegebenen Hinweise.
\end{description}

\subsection{ Fehlermeldungen }
%            ===============
\begin{description}
\item{\tt Error 0: Unspecific Error} \\
     Programmfehler: Benachrichtigen Sie den Programmierer.
\item{\tt Error 1: Multiplication Overflow} \\
     {\it �berlauf beim Multiplizieren zweier FixPunkt-Zahlen} \\
     Sie sollten versuchen alle Benutzer-Parameter ({\sl Taxes, Reinf, \ldots})
     neu zu skalieren, d.h. alle durch eine Konstante zu dividieren,
     was ja nichts an der Funktionalit�t �ndert. \\
     {\sl Fortsetzung kritisch -- System f�ngt sich aber meist nach
          einigen Runden}
\item{\tt Error 2: Division Overflow} \\
     {\it �berlauf beim Dividieren zweier FixPunkt-Zahlen} \\
     Beachten Sie die Hinweise unter Error 1. \\
     {\sl Fortsetzung kritisch -- System f�ngt sich aber meist nach
     einigen Runden}
\item{\tt Error 3: Wrong Selection-Mode} \\
     {\it $x${\tt SelMode} ist auf ung�ltige Werte gesetzt
          (erlaubt sind -6..6)} \\
     {\sl Fortsetzung nicht sinnvoll}
\item{\tt Error 4: Select more than possible} \\
     {\it Es sollten mehr (verschiedene) Elemente selektiert werden
          als vorhanden sind} \\
     Programmfehler: Benachrichtigen Sie den Programmierer.
\item{\tt Error 5: Wrong User-Classifier/Message} \\
     {\it Das Format der vordefinierten User-Classifier /
          Message-Strings ist falsch} \\
     �berpr�fen Sie {\tt MessSL}, {\tt CFSL} und {\tt EffSL}.
     Vielleicht ist die in {\tt SStr} angegebene L�nge
     inkonsistent besetzt. \\
     {\sl Fortsetzung nicht sinnvoll}
\item{\tt Error 6: Couldn't allocate Memory} \\
     {\it Fehler in der Speicherreservierung f�r die
          verschiedenen Listen} \\
     W�hlen Sie die mit \verb|#define S|$x$ definierten
     Listenl�ngen kleiner oder compilieren Sie mit dem
     Compiler-Modell {\tt Compact}, um mehr als 64 KByte f�r
     die Listen zur Verf�gung zu haben. \\
     {\sl Fortsetzung katastrophal (Absturzgefahr)}
\item{\tt Error 7: Wrong BidMode} \\
     {\it {\tt BidMode} ist auf ung�ltige Werte gesetzt
          (erlaubt sind 1..4)} \\
     {\sl Fortsetzung nicht sinnvoll}
\item{\tt Error 8: Wrong Credit-Assign-Mode} \\
     {\it {\tt CreditMode} ist auf ung�ltige Werte gesetzt
          (erlaubt sind 1,3 und 4)} \\
     {\sl Fortsetzung nicht sinnvoll}
\item{\tt Error 9: prf is called with {\tt prMode=0}} \\
     {\it Es wurde versucht etwas anzuzeigen, obwohl {\tt prMode}
          auf 0 gesetzt ist} \\
     Programmfehler: Benachrichtigen Sie den Programmierer.
\end{description}

\ifall
\begin{appendix}
\clearpage
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{ Programmlisting {\tt CFSSIM.C} }
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{listing}
\begin{verbatim}
/****************************************************************/
/*                                                              */
/*     C l a s s i f i e r - S y s t e m - S i m u l a t o r    */
/*                                                              */
/****************************************************************/
/*                  in Turbo-C 2.0 on IBM-AT                    */
/*       Diplomarbeit: Copyright 1991 by Marcus Hutter          */
/*                      Stand: 13.05.1991                       */
/****************************************************************/

/****************************************************************/
/*              R e m a r k s                                   */
/****************************************************************

- It is assumed, that 'int' is 16-bit and 'long' is 32-bit signed.
- Use Compact-Model (instead of Small), if your CFS-Example is so
  large, that you get Errors about 'too many dynamic Variables'
  (Mess,CF,..) and ignore warnings about loosing digits.
- Set an Breakpoint in and compile the EXAMPLE.C-File;
  this file is included.

 ****************************************************************/
/*              D e f i n i t i o n s                           */
/****************************************************************/

/*------------------------------*/
/*        Include-Files         */
/*------------------------------*/

#include <time.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <ctype.h>
#include <conio.h>
#include <dos.h>
#include <setjmp.h>

/*------------------------------*/
/*         Definitions          */
/*------------------------------*/

#define then    /**/            /* if then else                 */
#define ESC     27              /* define the escape key        */
#define FALSE   0               /* FALSE for bool               */
#define TRUE    1               /* TRUE  for bool               */
#define MaxInt  32767           /* Maximal signed integer       */
#define FOREVER for(;;)         /* infinite loop                */
#define PSize   sizeof(*)       /* Pointer-Size                 */
#define NScrL   50              /* # of Screen-Lines 25/43/50   */
#define STDCOL  YELLOW          /* Standard Color               */

#define MMask   (TString)~(~(long)0<<SStr) /* Cond/Act-Mask     */
#define NonId   -1              /* Not existing Id              */
#define DetId   -1              /* 'CF-Id' of Detector          */

#if TwoCond                     /* ifTC(x) eval. x if TwoCond   */
  #define ifTC(x) x             /* ifnTC(x)  "   x if not "     */
  #define ifnTC(x)
#else
  #define ifTC(x)
  #define ifnTC(x) x
#endif
\end{verbatim}

\begin{verbatim}
/*------------------------------*/
/*         Struct. & Types      */
/*------------------------------*/

typedef char            bool;   /* bool = { TRUE , FALSE }      */
typedef unsigned char   byte;   /* 0..255                       */
typedef signed char     sbyte;  /* -128..127                    */
typedef signed int      index;  /* Array-Indices                */
typedef signed int      fixp;   /* FixPoint: Range -128 to 127  */
                                /*         : step 1/256         */
                                /* real(constants) to FixPoint  */
#define FixP(x) ((fixp)(((float)x)*256))

#if FALSE /* (SStr<=sizeof(byte)*8) *//* Type of String         */
  typedef byte TString;         /* Test, da sonst Anz. bl�d */
#elif (SStr<=sizeof(int)*8)
  typedef int  TString;
#elif (SStr<=sizeof(long)*8)
  typedef long TString;
#else
  #error Message too long
#endif

typedef byte    TCType;         /* CF & Cond.-Type (ev.BitArray)*/
typedef index   TMessId;        /* Message-Index/Id             */
typedef index   TCFId;          /* Classifier-Index/Id          */
typedef index   TBidId;         /* Bid-Index/Id                 */
typedef index   TTupId;         /* MessTupel-Index/Id           */

typedef struct                  /* = long int for Sort & Select */
      { index   Id;             /* Inedx/Id                     */
        fixp    Val; }          /* Value/Prorpability/Helpinfo  */
        TIdVal;
#define Id(x)   (((TIdVal*)&(x))->Id)  /* first half of long    */
#define Val(x)  (((TIdVal*)&(x))->Val) /* second "   of long    */

typedef struct                  /*         CF-Condition         */
      { TString C;              /* String  ------------         */
        TString B;              /* #-Mask                       */
        TCType  T; }            /* Type                         */
        TCond;

typedef struct                  /*          CF-Action           */
      { TString A;              /* String   ---------           */
        TString B;              /* #-Mask                       */
        TCType  T; }            /* Type                         */
        TAct;

typedef struct                  /*          Classifier          */
      { TCond   C1;             /* Condition----------          */
  ifTC( TCond   C2; )           /* Condition 2                  */
        TAct    Act;            /* Action                       */
        fixp    Sp;             /* Specifity of Cond1 (& Cond2) */
        fixp    S;              /* Strength                     */
        fixp    Get;            /* Reinf + Pay from others      */
        fixp    Pay;            /* Pay to others                */
        fixp    Tax;            /* Taxes                        */
        fixp    PSP;            /* Bid-Sums over Reinf-Expisode */
        int     H; }            /* Help-Value                   */
        TCF;

typedef struct                  /*           CF-List            */
      { TCF     *B;             /* Begin     -------            */
        TCF     *C;             /* Current End                  */
        TCF     *E;             /* End of List                  */
        byte    BidMode;
        byte    SuppMode;
        sbyte   BidTupSelMode;
        sbyte   BidActSelMode;
        sbyte   FireBidSelMode;
        sbyte   FireTupSelMode;
        int     MBids;
        int     MAct;
        int     MFire;
        fixp    RiskFak;
        byte    SpecPow;
        byte    RelSuppPow;
        byte    EBidPow;
        byte    ESpecPow;
        byte    ClaimMode;
        byte    DisMode;
        byte    SumMode; }
        TCFL;

typedef struct                  /*            Message           */
      { TString M;              /* String     -------           */
        fixp    I;              /* Intensity                    */
        TCFId   CF;             /* Id of sending CF             */
        int     H; }            /* Help-Value                   */
        TMess;

typedef struct                  /*         Message-List         */
      { TMess   *B;             /*         ------------         */
        TMess   *C;
        TMess   *E; }
        TMessL;

typedef struct                  /*             Bid              */
      { TCFId   CF;             /* Bidding CF  ---              */
        fixp    BV;             /* Bid-Value                    */
        fixp    EV;             /* Effective-Bid-Value          */
        TTupId  Tup;            /* Matching-Tuples              */
        int     N;              /* Number of Bid-Tuples         */
        bool    F; }            /* Fired-Flag                   */
        TBid;

typedef struct                  /*           Bid-List           */
      { TBid    *B;             /*           --------           */
        TBid    *C;
        TBid    *E; }
        TBidL;

typedef struct                  /*           MessTupel          */
      { TMessId M1;             /* Message 1 ---------          */
  ifTC( TMessId M2; )           /* Message 2                    */
        fixp    S; }            /* Support                      */
        TTup;

typedef struct                  /*        MessTupel-List        */
      { TTup    *B;             /*        --------------        */
        TTup    *C;
        TTup    *E; }
        TTupL;

typedef struct                  /*      Classifier-System       */
      { TMessL  *MP;            /* Mess =================       */
        TMessL  *NP;            /* New-Mess                     */
        TMessL  *OP;            /* Output-Mess (from Eff)       */
        TCFL    *CP;            /* Classifier                   */
        TCFL    *EP;            /* Effectors                    */
        TBidL   *BP;            /* Bids                         */
        TBidL   *DP;            /* Eff-Bids (same list)         */
        TTupL   *TP;            /* MessTupel                    */
        TTupL   *UP; }          /* Eff-MessTupel (same list)    */
        TCS;

typedef struct                  /*              Statistic       */
      { long    CycleC;         /* Cycle-Counter---------       */
        long    ReVal;          /* � of Reinf                   */
        long    Str;            /* � of CF-Stregnth             */
        long    NCFMinStr;      /* # of CF with MinStr          */
        long    NCFMaxStr;      /* # of CF with MaxStr          */
        long    MCF;            /* # of NonMatched CF           */
        long    MMess;          /* # of NonMatched Mess.        */
        long    NCF;            /* # of CF                      */
        long    NBid;           /* # of Bids                    */
        long    NTup;           /* # of Tupels                  */
        long    NMess; }        /* # of Messages                */
        TStat;
\end{verbatim}

\begin{verbatim}
/*------------------------------*/
/*      Variables               */
/*------------------------------*/

TMessL  XM,XN,XO;
TBidL   XB,XD;
extern TCFL XC,XE;
TTupL   XT,XU;
TStat   cy,ep;

TCS     XCS = { &XM,&XN,&XO,&XC,&XE,&XB,&XD,&XT,&XU };
TCS     *o = &XCS;

long    CycleC;                 /* Main-Cycle-Step-Counter      */
fixp    ReVal;                  /* Reinforcement-Value          */
TString DetMTagC,DetMTagB;      /* Detector-Tags                */
TString EffMTagC,EffMTagB;      /* Effector-Tags                */

TMess   *GMB;                   /* Global-Mess-Pointer          */
TString *GStr;                  /* Global Strting-Pointer       */

jmp_buf jmp;                    /* jump-label                   */
FILE    *devP,*lpt1;            /* Output-Device                */
bool    ProtF;                  /* Protocoll is Off/On          */
bool    SStepF;                 /* Single-Step-Mode             */
bool    prM1F;                  /* printmode 1 - first flag     */
bool    SoundF = TRUE;          /* Sound On / Off               */
byte    prMode = 3;             /* Print-Mode 0=No ... 3=All    */

/*------------------------------*/
/*      Constants               */
/*------------------------------*/

char    FName[14] = "CFSSIM.C"; /* File-Name (not needed)       */
char    *ErrMess[] =            /* Error-Messages               */
      { "Unspecific Error",
        "Mutliplication Overflow",
        "Division Overflow",
        "Wrong Selection-Mode",
        "Select more than possible",
        "Wrong User-Classifier/Message",
        "Couldn't allocate Memory",
        "Wrong BidMode",
        "Wrong Credit-Assign-Mode",
        "pprint is call with prMode=0" };

char    *WarnMess[] =           /* Warnning-Messages            */
      { "Unspecific Warning",
        "Division Underflow",
        "QMax called with k=0",
        "ProbSel called with N=0",
        "Tupellist is full",
        "Bidlist is full",
        "Selection of Zero-Values",
        "BestSelMode must be positive",
        "Too many matching tuples" };

#define NWarn (sizeof(WarnMess)/sizeof(char*))
int     WC[NWarn];
int     WP[NWarn];

/*------------------------------*/
/*      Test-Variables          */
/*------------------------------*/

/*------------------------------*/
/*      Externals               */
/*------------------------------*/

/* Example-Specific variables and functions                     */
/* For explanation refer to Example1/2/...                      */
extern  int     StRate,DetRate,EffRate,ReRate,GenRate;
extern  int     MDetM,MEqMess,NMutate,NCFMut,NCFRepl;
extern  fixp    DefNMI,SclSel,DefDetMI,DefStr,DefStrDev;
extern  fixp    Dev1,Dev2,NMFrac,DetFrac,HeadTax,MessTax,BidTax;
extern  fixp    MaxStr,MinStr,CondSp,ActSp,NegCondP,PSPFrac;
extern  byte    NMIMode,CreditMode,BidTaxMode,PSPDisMode;
extern  byte    DelMessMode;
extern  sbyte   DelMessSelMode,MutSelMode,ReplSelMode;
extern  bool    CleanHallF,MultBidTaxF,MultMessTaxF;
extern  char    DetMessTag[],EffMessTag[],ProtDev[];
extern  char    *CFSL[],*EffSL[];
extern          InitEnv(),Detect(TMessL*,int),Effect(TMessL*);
extern          Display();
extern  fixp    Reinf();

/*------------------------------*/
/*      Forward Declarations    */
/*------------------------------*/

extern          Menu();
extern          main();
extern  char    event();
\end{verbatim}

\begin{verbatim}
/****************************************************************/
/*              G e n e r a l   P r o c e d u r e s             */
/****************************************************************/

#define Sound(h,l)                                              \
        { if (SoundF) { sound(h); delay(l); nosound(); } }

/*------------------------------*/
 prf(int Col,char*fmt,...)      /* printf to dev & devP         */
/*------------------------------*/
{ char  str[999];
  extern Error(int);
  if (Col!=0) then textcolor(Col);
  if (prMode>0) then
  { vsprintf(str,fmt,...);
    cprintf(str);
    if (ProtF) then fprintf(devP,str); }
  else Error(9);
  if (Col!=0) then textcolor(STDCOL);
}
/*------------------------------*/
        Error(n)                /* break with Error # 10+n      */
/*------------------------------*/
{ prMode++;
  textbackground(LIGHTRED);
  prf(WHITE,"Error #%d: %s\r\n",10+n,ErrMess[n]);
  textbackground(BLACK); clreol();
  textbackground(LIGHTRED);
  prf(WHITE,"Press any Menu-Key, but its risky to continue !!\r\n");
  textbackground(BLACK); clreol();
  prMode--;
  Sound(500,100);
  Menu();
}
/*------------------------------*/
        Warning(n)              /* write Warning # n            */
/*------------------------------*/
{ WC[n]++;
  if (WC[n]%((WP[n]>>2)+1)==0)  /* /4 = Warning decay-Rate      */
  { if (prMode>0) then prf(LIGHTGRAY,
      "%d.Warning #%d: %s\r\n",WC[n],20+n,WarnMess[n]);
    WP[n]+=1+(WP[n]>>1);
    Sound(1000,5);
} }
/* Random-Number between 0 and n-1 */
#define random2(n) ((int)(((long)rand()*n)>>15))

/* TRUE with Prob. p (p is fixp. !) */
#define flip(p)    ((p)>(rand()>>7))

/*------------------------------*/
char*   ActTime()               /* Actual Time in String        */
/*------------------------------*/
{ char  *s;
  time_t t;                     /* Actual Time                  */
  time(&t);
  s=ctime(&t);
  s[strlen(s)-1]='\0';
  return(s);
}
/*------------------------------*/
        memswap(P,Q,n)          /* swap n Bytes from P and Q    */
/*------------------------------*/
char    *P,*Q;
{ char  h,*E=P+n;
  while(P<E) { h=*P; *P++=*Q; *Q++=h; }
}
#if SpeedF                      /* fast Fix-Point-Operations    */
#define FPMult(x,y) (fixp)((long)(x)*(y)>>8)
#define FPDiv(x,y)  (fixp)(((long)(x)<<8)/(y))
#else
/*------------------------------*/
fixp    FPMult2(x,y)            /* Fix-Point-Mult with Test     */
/*------------------------------*/
long    x,y;
{ long h=(x*y)>>8;
  if ((h>0?h:-h)>MaxInt) then Error(1);
  return((fixp)h);
}
/*------------------------------*/
fixp    FPDiv2(x,y)             /* Fix-Point-Division with Test */
/*------------------------------*/
long    x,y;
{ long h=(x<<8)/y;
  if ((h>0?h:-h)>MaxInt) then Error(2);
  if (x!=0&&h==0) then Warning(1);
  return((fixp)h);
}                               /* secure Fix-Point-Operations  */
#define FPMult(x,y) FPMult2((long)(x),(long)(y))
#define FPDiv(x,y) FPDiv2((long)(x),(long)(y))
#endif
/*------------------------------*/
fixp    FPPow(y,x,n)            /* Fix-Point-Pow y*x^n          */
/*------------------------------*/
fixp y,x; byte n;
{ int i;
  for(i=0; i<n; i++) y=FPMult(y,x);
  return(y);
}
/*------------------------------*/
int     Noise(Dev)              /* Standard-Normal-Distribution */
/*------------------------------*  Cut at +-4 in .5 Steps       */
int     Dev;                    /* * deviation Dev              */
{ static int s=8;
  byte  c;
  int   b;
  if (Dev) then
  { c=0; b=rand();
    while(b) { c+=b&1; b>>=1; }
    return(Dev*(c-(s=15-s)) >> 1); }
  else return(0);
}
/* Order-Functions must be Reflexive, that means InOrder(x,x) ! */
/*------------------------------*/
bool    InStdOrd(x,y)           /* Standard-Order-Function      */
/*------------------------------*/
TIdVal  x,y;
{ return(x.Val<=y.Val);
}
/*------------------------------*/
bool    InMessOrder(x,y)        /* Mess-Order-Function          */
/*------------------------------*/
TIdVal  x,y;
{ return(GMB[x.Id].M<=GMB[y.Id].M);
}
/*------------------------------*/
bool    InStrOrder(x,y)         /* String-Order-Function        */
/*------------------------------*/
TIdVal  x,y;
{ return(GStr[x.Id]<=GStr[y.Id]);
}
/*------------------------------*/
byte    Count1s(s)              /* Count # of 1 Bits            */
/*------------------------------*/
TString s;
{ byte c=0;
  while(s) { if (s&1) then c++; s>>=1; }
  return(c);
}
\end{verbatim}%
\begin{verbatim}
/*------------------------------*/
        Shuffle(A,N)            /* Shuffle N El. of A           */
/*------------------------------*/
long    A[];
int     N;
{ index m;
  long  h;
  while(N>1)
  { m=random2(N);
    h=A[m]; A[m]=A[--N]; A[N]=h;
} }
/*------------------------------*/
#define QDivide()               /* Used in QMax and QSort */    \
/*------------------------------*/              \
{ d=*M;                                         \
  while(B<C)                                    \
  { if (M-B<C-M) then                           \
      if (InOrder(d,h=*C)) then C--;            \
      else { *C=*B; *B++=h; }                   \
    else                                        \
      if (InOrder(h=*B,d)) then B++;            \
      else { *B=*C; *C--=h; } }                 \
  if (InOrder(d,*C)) then B--; else C++;        \
}
/*------------------------------*/
        QMax(A,N,k,InOrder)     /* k biggest El. to bottom of A */
/*------------------------------*/
long    A[];                    /* Array of length N            */
int     N;                      /* Length of Array              */
int     k;                      /* # of El. to select           */
bool    InOrder(long,long);     /* Order-Criterium              */
{ long  *B,*B2,*C,*C2;          /* Begin & End of part of A     */
  long  *M,d;                   /* Div.-Point & -Element of A   */
  long  h;                      /* help-variable for exchange   */
  if (k==0) then { Warning(2); return; }
  B=B2=A; C=C2=A+N-1; M=C-k+1;
  FOREVER
  { QDivide();
    if (C<M)      then { B2=B; C=C2; }
    else if (C>M) then { B=B2; C2=C; }
    else break;
} }
/*------------------------------*/
        QSort(B2,C2,InOrder)    /* Sort A In-Order              */
/*------------------------------*/
long    *B2;                    /* Begin of Index-Array         */
long    *C2;                    /* End of Index-Array (B2+#El-1)*/
bool    InOrder(long,long);     /* Order-Criterium              */
{ long  *B,*C;                  /* Actual Begin & End -Pointer  */
  long  *M,d;                   /* Div.-Point & -Element of A   */
  long  h;                      /* help-variable for exchange   */
  if (B2<C2) then
  { B=B2; C=C2; M=B+((C-B+1)>>1);
    QDivide();
    QSort(B2,B,InOrder);
    QSort(C,C2,InOrder);
} }
/* TIdVal and long are used as synonyms                         */

/*------------------------------*/
int     MaxVal(A,N)             /* Maximal Value of A           */
/*------------------------------*/
TIdVal  A[];                    /* Elements                     */
int     N;                      /* Number of Elements           */
{ int   i;
  int   m=A[0].Val;
  for(i=1; i<N; i++) if (A[i].Val>m) then m=A[i].Val;
}
#define AL         ((long*)A)   /* long synonym for A           */
\end{verbatim}

\begin{verbatim}
/*------------------------------*/
        ProbSelInit(A,N)        /* Init Probability-Selection   */
/*------------------------------*/
TIdVal  A[];                    /* Elements                     */
int     N;                      /* Number of Elements           */
{ index i,k;
  fixp  m=MaxVal(A,N);
  if (m<8000 && m) then
  { m=16000/m;
    for(i=0; i<N; i++) A[i].Val*=m; }
  for(k=1; k<N; k<<=1)
    for(i=0; i<N; i+=k<<1)
    { if (i+k<N) then A[i].Val+=A[i+k].Val;
      A[i].Val>>=1; }
}
/*------------------------------*/
index   ProbSel(A,N)            /* Probability-Selection        */
/*------------------------------*/
TIdVal  A[];                    /* Elements                     */
int     N;                      /* Number of Elements           */
{ index i,k=0;
  TIdVal z;
  z.Id=rand()<<1;
  z.Val=random2(A[0].Val);
  for(i=1; i<N; i<<=1);
  for(i>>=1; i!=0; i>>=1)
  { *(long*)&z<<=1;
    if (i+k<N) then
      if (z.Val<A[k+i].Val) then k+=i;
      else z.Val-=A[k+i].Val; }
  return(k);
}
/*------------------------------*/
        ProbChg(A,N,k,p)        /* Probability-Selection        */
/*------------------------------*/
TIdVal  A[];                    /* Elements                     */
int     N;                      /* Number of Elements           */
index   k;                      /* Change Element k             */
fixp    p;                      /* ... to Probability p         */
{ int   i;
  for(i=1; !(i&k) && i<N; i<<=1)
  { if (i+k<N) then p+=A[i+k].Val;
    p>>=1; }
  p-=A[k].Val;
  for(; i<N; i<<=1)
  { if (k&i) then { A[k].Val+=p; k-=i; }
    p>>=1; }
  A[0].Val+=p;
}
/*------------------------------*/
        ProbSelInit2(A,N)       /* Init Probability-Selection   */
/*------------------------------*/
TIdVal  A[];                    /* Elements                     */
int     N;                      /* Number of Elements           */
{ index i,m=0;
  long  h;
  if (N==0) then Warning(3);
  for(i=1; i<N; i++) if (A[i].Val>A[m].Val) then m=i;
  h=AL[m]; AL[m]=AL[0]; AL[0]=h;
}
/*------------------------------*/
index   ProbSel2(A,N)           /* Probability-Selection        */
/*------------------------------*/
TIdVal  A[];                    /* Elements                     */
int     N;                      /* Number of Elements           */
{ index k;
  while(random2(A[0].Val)>=A[k=random2(N)].Val);
  return(k);
}
/*------------------------------*/
      MultSelInit(A,N,Mode)     /* Init Selection (for k<0)     */
/*------------------------------*/
TIdVal  A[];                    /* Elements & Values            */
int     N;                      /* Number of Elements           */
sbyte   Mode;                   /* Selection-Mode               */
{ switch(abs(Mode))
  { case 1: break;
    case 2: ProbSelInit(A,N); break;
    case 3: QSort(A,A+N-1,InStdOrd); break;
    case 4: break;
    case 5: break;
    case 6: ProbSelInit2(A,N); break;
    default:Error(3);
} }
\end{verbatim}
\begin{verbatim}
/*------------------------------*/
        Select(A,NP,B,k,Mode)   /* Select k of N Elements       */
/*------------------------------*/
TIdVal  A[];                    /* Elements & Values            */
int     *NP;                    /* Number of Elements           */
index   B[];                    /* Selected k Elements          */
int     k;                      /* Selection-Mode               */
sbyte   Mode;                   /* >0:different; <0:with repeat */
{ index i,h,m,m2;
  int   an;
  int   N=*NP;
  bool  once=(k>0);

/* treat special cases */
  k=abs(k);
  if (k==0) then return;
  if (k>N && (Mode>0 || N==0)) then { Error(4); Mode=-Mode; }
  if (k==N && Mode>0) then Mode=1;
#if !SpeedF                     /* Test slows down execution    */
  for(i=h=0; i<N; i++)
  if (A[i].Val) then h++;
  if (h<k) then Warning(6);
#endif

/* branch on selection-mode */
  switch(abs(Mode))
  { case  1:                    /* Dummy-Selection              */
      for(i=0; i<k; i++)
        B[i]=A[Mode>0?--N:0].Id;
      break;
    case  2:                    /* Probability-Selection        */
      if (once) then ProbSelInit(A,N);
      for(i=0; i<k; i++)
      { m=ProbSel(A,N);
        B[i]=A[m].Id;
        if (Mode>0 && N>1) then
        { an=A[N-1].Val;
          for(h=N-1; !(h&1); h>>=1) an<<=1;
          ProbChg(A,N,m,an);
          ProbChg(A,N,N-1,0);
          A[m].Id=A[--N].Id;
          if (!(N&N-1)) then A[0].Val<<=1;
      } }
      N=*NP-k; break;
    case  3:                    /* Best-Selection (Different)   */
      if (Mode<0) then Warning(7);
      if (once) then QMax(A,N,k,InStdOrd);
      for(i=0; i<k; i++) B[i]=A[--N].Id;
      break;
    case  4:                    /* Scaled-Selection             */
      for(i=0; i<k; i++)
      { m=random2(N); m2=random2(N);
        if ((A[m].Val>A[m2].Val)^flip(SclSel)) then m=m2;
        B[i]=A[m].Id;
        if (Mode>0) then AL[m]=AL[--N];
      } break;
    case  5:                    /* Random-Selection             */
      for(i=0; i<k; i++)
      { m=random2(N); B[i]=A[m].Id;
        if (Mode>0) then AL[m]=AL[--N];
      } break;
    case  6:                    /* Prob2-Selection (simple vers) */
      if (once) then m=0; else m=1;
      for(i=0; i<k; i++)
      { if (m==0) then ProbSelInit2(A,N);
        m=ProbSel2(A,N);
        B[i]=A[m].Id;
        if (Mode>0) then AL[m]=AL[--N];
      } break;
    default: Error(3);
  }
  *NP=N;
}
#define pprFlag(F,S)    \
        prf(LIGHTMAGENTA,"%s %s\r\n",S,((F)==TRUE)?"ON":"OFF")
#define SetSStep(F) pprFlag(SStepF=(F),"SingleStep")
#define SetSound(F) pprFlag(SoundF=(F),"Sound")

/*------------------------------*/
        SetProt(F)              /* Toggle Protocoll On/Off      */
/*------------------------------*/
bool    F;
{ if (F)
  then devP=fopen(ProtDev,"ab");
  else fclose(devP);
  pprFlag(ProtF=F,"Protocoll");
}
/*------------------------------*/
        SetprMode(n)            /* Set Print-Mode to 0,1,2 or 3 */
/*------------------------------*/
int     n;
{ prM1F= (n==1||n==2);
  prf(LIGHTMAGENTA,"PrintMode = %d\r\n",prMode=n);
}
\end{verbatim}

\begin{verbatim}
/****************************************************************/
/*              C F S - B a s i c - P r o c e d u r e s         */
/****************************************************************/

/* Bits 0 to SStr-1 of M define 0 and 1 positions               */
/* Corresponding Bits in C and B define CF-Cond/Action pos.     */
/* (0,1)=0, (1,1)=1, (0,1)=(0,0)=#                              */

/* Does Message M match Condition (C,B) ?                       */
#define MatchMC(M,C,B) !((M^C)&B)  /* for doc. look further     */

/* Match Message M with Action (A,B) to result                  */
#define MatchMA(M,A,B) ((A&B)|(M&~B))

/*------------------------------*/
        CalcSpec(C)             /* Calculate Specifity          */
/*------------------------------*/
TCF     *C;
{ fixp  Sp1,Sp2;
  Sp1=Count1s((long)C->C1.B);
  if (!(C->C1.T&2)) then Sp1=SStr-Sp1;
ifnTC( C->Sp=FPDiv(Sp1,SStr); )
ifTC( Sp2=Count1s((long)C->C2.B);
      if (!(C->C2.T&2)) then Sp2=SStr-Sp2;
      C->Sp=FPDiv(Sp1+Sp2,SStr<<1); )
}
#define CrSumM(n) M=MP->B+n;                                    \
        if (M->H>0 || ModeP->ClaimMode==2) then                 \
        { M->H=-abs(M->H); /* Visited */                        \
          R= ModeP->SumMode==1 ? FixP(1) : -M->H;               \
          Sum+= ModeP->DisMode==1 ? R : FPMult(R,M->I); }

/*------------------------------*/
long    CrSum(TS,N,MP,ModeP)    /* Calculate Credit-Sum         */
/*------------------------------*/
TTup    *TS;                    /* Start of Tupellist           */
int     N;                      /* # of Tupels to Check         */
TMessL  *MP;
TCFL    *ModeP;
{ TMess *M;
  TTup  *T;
  fixp  R;
  long  Sum=0;
  if (ModeP->SumMode==3) then return(FixP(1));
  for(T=TS; T<TS+N; T++)
  { CrSumM(T->M1); ifTC( CrSumM(T->M2); ) }
  return(Sum);
}
#define DistrM(n) M=MP->B+n;                                    \
        if (M->H<0 || ModeP->ClaimMode==2) then                 \
        { M->H=abs(M->H); /* Visited */                         \
          R= FPMult(M->H,Val);                                  \
          R= ModeP->DisMode==1 ? R : FPMult(R,M->I);            \
          Sum+=R; CP->B[M->CF].Get+=R; }

/*------------------------------*/
  Distr(TS,N,MP,ModeP,CP,Val)   /* Distribute Val. to CF        */
/*------------------------------*/
TTup    *TS;                    /* Start of Tupellist           */
int     N;                      /* # of Tupels to Check         */
TMessL  *MP;
TCFL    *ModeP,*CP;
fixp    Val;
{ TMess *M;
  TTup  *T;
  fixp  R,Sum=FixP(0);
  for(T=TS; T<TS+N; T++)
  { DistrM(T->M1); ifTC( DistrM(T->M2); ) }
  return(Sum);
}
/*------------------------------*/
        SetMFrac(MP)            /* Set Mess.-Credit-Fraction    */
/*------------------------------*/
TMessL  *MP;
{ TMess *M;
  MP->B[-1].H=NMFrac;
  for(M=MP->B; M<MP->C; M++)
    M->H= (M->CF==DetId) ? DetFrac : FixP(1);
}
/*------------------------------*/
TString RandStr(p)              /* Create Random-String         */
/*------------------------------*/
fixp p;                         /* p/256 = Prob. for a 1-Bit    */
{ TString s=1;
  while(!(s&~MMask))
  { s<<=1; if flip(p) then s|=1; }
  return(s&MMask);
}
/*------------------------------*/
        RandMess(M)             /* Create Random-Message        */
/*------------------------------*/
TMess   *M;
{ M->M=RandStr(FixP(0.5));
  M->I=DefNMI;
  M->CF=NonId;
}
/*------------------------------*/
        RandCF(C)               /* Create Random-Classifier     */
/*------------------------------*/
TCF     *C;                     /* Pointer to CF                */
{ C->C1.T=flip(NegCondP) ? 4 : 6 ;
  C->C1.B=RandStr(CondSp);
  C->C1.C= C->C1.B & RandStr(FixP(0.5));
ifTC( C->C2.T=flip(NegCondP) ? 4 : 6 ;
      C->C2.B=RandStr(CondSp);
      C->C2.C= C->C2.B & RandStr(FixP(0.5)); )
  C->Act.B=RandStr(ActSp);
  C->Act.A= C->Act.B & RandStr(FixP(0.5));
  C->S=DefStr+Noise(FPMult(DefStr,DefStrDev));
  C->Sp=CalcSpec(C);
  C->Get=C->Pay=C->Tax=C->PSP=FixP(0);
}
/*------------------------------*/
        MutateCA(CP,BP,Sp)      /* Mutate Cond/Act              */
/*------------------------------*/
TString *CP,*BP;                /* (*CP,*BP)= Cond/Act          */
fixp    Sp;                     /* Mean Specifity = 1- #Prob.   */
{ TString m;
  m=1<<random2(SStr);
  if flip(Sp) { *BP|=m;
    if flip(FixP(0.5)) then *CP|=m; else *CP&=~m; }
  else { *BP&=~m; *CP&=~m; }
}
\end{verbatim}

\begin{verbatim}
/****************************************************************/
/*              I n p u t   /   O u t p u t                     */
/****************************************************************/

/*------------------------------*/
char    *StoCB(S,PC,PB)         /* CharString to Condition      */
/*------------------------------*/
char    *S;                     /* String like "01##10"         */
TString *PC,*PB;                /* Condition (*PC,*PB)          */
{ char  *T;
  *PB=*PC=0;
  for(T=S+SStr; S<T; S++)
  { *PB<<=1; *PC<<=1;
    switch(*S)
    { case '0': (*PB)++;          break;
      case '1': (*PB)++; (*PC)++; break;
      case '#':                   break;
      case '*':          (*PC)++; break;
      default : Error(5);
  } }
  return(T);                    /* Pointer behind string        */
}
/*------------------------------*/
        StoCF(S,C,Str,Dev)      /* CharString to Classifier     */
/*------------------------------*/
char    *S;                     /* String like "+01##/110#"     */
TCF     *C;                     /* Pointer to CF                */
fixp    Str,Dev;                /* Strength and Deviation       */
{ C->C1.T=4+'-'-*S++;
  S=StoCB(S,&C->C1.C,&C->C1.B);
ifTC( C->C2.T=4+'-'-*S++;
      S=StoCB(S,&C->C2.C,&C->C2.B); )
  S++;
  C->S=Str+Noise(FPMult(Str,Dev));
  C->Sp=CalcSpec(C);
  S=StoCB(S,&C->Act.A,&C->Act.B);
  C->Get=C->Pay=C->Tax=C->PSP=FixP(0);
  if (*S) then Error(5);
}
/*------------------------------*/
        StoM(S,MP)              /* CharString to MessageString  */
/*------------------------------*/
char    *S;                     /* String like "010011"         */
TMess   *MP;
{ TString B;
  StoCB(S,&MP->M,&B);
  if (MMask^B) then Error(5);
  MP->CF=DetId;
  MP->I=DefDetMI;
}
/*------------------------------*/
char    *CBtoS(C,B)             /* Condition to CharString      */
/*------------------------------*/
TString C,B;
{ static char S[SStr+1];
  int   i;
  S[SStr]=0;
  for(i=SStr-1; i>=0; i--)
  { S[i]= (B&1) ? (C&1?'1':'0') : (C&1?'*':'#');
    B>>=1; C>>=1; }
  return(S);
}
/*------------------------------*/
        pprInfo()               /* Printf Help-Information      */
/*------------------------------*/
{ prf(LIGHTCYAN,"%s\r\n%s\r\n",
  "Press one of the upcase letters in Menu-Field ...",
  "For more information refer to documentation     ");
}
/*------------------------------*/
        pprCFL(CP)              /* pprint Classifier-List       */
/*------------------------------*/
TCFL    *CP;
{ TCF   *C;
  int   i=0;
  prf(LIGHTGREEN,
  "CFId   Str    Get    Pay  Taxes Condion/Action\r\n");
  for(C=CP->B; C<CP->C; C++)
  { prf(0,"%3d:%6.2f %6.2f %6.2f %6.2f %c%s",
      i++,C->S/256.0,C->Get/256.0,C->Pay/256.0,C->Tax/256.0,
      '-'-(C->C1.T&2),CBtoS(C->C1.C,C->C1.B));
ifTC( prf(0,"%c%s",'-'-(C->C2.T&2),CBtoS(C->C2.C,C->C2.B)); )
    prf(0,"/%s\r\n",CBtoS(C->Act.A,C->Act.B));
} }
/*------------------------------*/
        pprMessL(MP)            /* pprint Message-List          */
/*------------------------------*/
TMessL  *MP;
{ TMess *M;
  int   i=0;
  prf(LIGHTGREEN,"MId Intens Sender Message\r\n");
  for(M=MP->B; M<MP->C; M++)
  { prf(0,"%3d:%6.2f ",i++,M->I/256.0);
    if (M->CF==DetId)
    then prf(0,"  D    ");
    else prf(0,"%3d    ",M->CF);
    prf(0,"%s\r\n",CBtoS(M->M,MMask));
} }
/*------------------------------*/
        pprBidL(BP,TP)          /* pprint Bid-List              */
/*------------------------------*/
TBidL   *BP;
TTupL   *TP;
{ TBid  *B;
  TTup  *T,*TS;
  int   i=0;
  prf(LIGHTGREEN,
    "BidId CFId Bid EBid Fired BidTupel\r\n");
  for(B=BP->B; B<BP->C; B++)
  { prf(0,"%3d: %3d %6.2f %6.2f %c {",
      i,B->CF,B->BV/256.0,B->EV/256.0,B->F?'F':'-');
    for(T=TS=TP->B+B->Tup; T<TS+B->N; T++)
    { if (T->M1==NonId) then prf(0," N");
      else prf(0," %d",T->M1);
      ifTC( if (T->M2==NonId) then prf(0,":N");
            else prf(0,":%d",T->M2); )
    }
    prf(0," }\r\n");
    i++;
} }
/*------------------------------*/
        pprCS(prMode,o)         /* pprint whole CFS             */
/*------------------------------*/
TCS     *o;
{ extern pprStat(int,TStat*);
  Display();
  switch(prMode) {
  case 3:
    prf(WHITE,
    "-------------- Cycle %ld --------------\r\n",CycleC);
    prf(LIGHTGREEN,"\r\nMessage-List:\r\n");
    pprMessL(o->MP);
    prf(LIGHTGREEN,"\r\nClassifier-List:\r\n");
    pprCFL(o->CP);
    prf(LIGHTGREEN,"\r\nBid-List:\r\n");
    pprBidL(o->BP,o->TP);
    prf(LIGHTGREEN,"\r\nNew-Message-List:\r\n");
    pprMessL(o->NP);
    if (CycleC%EffRate==0) then
    { prf(LIGHTGREEN,"\r\nEffector-List:\r\n");
      pprCFL(o->EP);
      prf(LIGHTGREEN,"\r\nEff-Bid-List:\r\n");
      pprBidL(o->DP,o->UP);
      prf(LIGHTGREEN,"\r\nOutput-Message-List:\r\n");
      pprMessL(o->OP);
    }
    prf(0,"\r\n");
    prM1F=TRUE;
  case 2:
    pprStat(1,&cy); break;
} }
/*------------------------------*/
        pprStat(prMode,epp)     /* Print Statistic              */
/*------------------------------*/
int     prMode;
TStat   *epp;
{ int   n         = (int)max(epp->CycleC,1);
  float ReVal     = epp->ReVal/(256.0*n);
  float Str       = epp->Str/(256.0*n*(o->CP->C-o->CP->B));
  int   NCFMinStr = (int)(epp->NCFMinStr/n);
  int   NCFMaxStr = (int)(epp->NCFMaxStr/n);
  int   MCF       = (int)(epp->MCF/n);
  int   MMess     = (int)(epp->MMess/n);
  int   NCF       = (int)(epp->NCF/n);
  int   NBid      = (int)(epp->NBid/n);
  int   NTup      = (int)(epp->NTup/n);
  int   NMess     = (int)(epp->NMess/n);

  switch(prMode) {
  case 2: pprCS(3,o); /* no break; */
  case 3: prf(LIGHTGREEN,
    "\r\n  Statistic (Mean-Values) of Cycle %ld-%ld:\r\n",
            CycleC-n+1,CycleC);
    prf(0,"  External Reinforcement  : %.3f\r\n",ReVal);
    prf(0,"  mean CF-Strength        : %.3f\r\n",Str);
    prf(0,"  min/maximal Strength CF : %d/%d\r\n",
                                         NCFMinStr,NCFMaxStr);
    prf(0,"  (matched) Messages      : (%d) %d\r\n",MMess,NMess);
    prf(0,"  (matched) Classifers    : (%d) %d\r\n",MCF,NCF);
    prf(0,"  Bids (-Tupels)          : %d (%d)\r\n",NBid,NTup);
    prf(0,"\r\n");
    prM1F=TRUE;
    break;
  case 1:
    if (prM1F) then
    { prf(LIGHTGREEN,"%s\r\n%s\r\n",
      "Cycle-Cycle  Reinf Strength Min Max Mch Mch Bid Tup",
      "             Value          Str Str  CF Mess 's els");
      prM1F=FALSE; }
    prf(0,"%5ld-%-5ld:%7.3f %7.3f %3d %3d %3d %3d %3d %3d\r\n",
      CycleC-n+1,CycleC,ReVal,Str,NCFMinStr,
      NCFMaxStr,MCF,MMess,NBid,NTup);
    break;
  case 0: break;
  default: Error(8);
} }
\end{verbatim}

\begin{verbatim}
/****************************************************************/
/*              C F S - H i g h - P r o c e d u r e s           */
/****************************************************************/

/* Support of Tupel (m1,m2)  (used by MatchBid)                 */
#define TupSupp1(m1,m2) m1.Val                                  \
  ifTC(+ ((m1.Id==m2.Id && CP->SuppMode==1) ?  0 : m2.Val) )

/* Support of Tupel (m1,m2) (used by Fire)
*/
#define TupSupp2(m1,m2) (MP->B[m1].I                            \
  ifTC(+ ((m1==m2 && CP->SuppMode==1) ? 0 : MP->B[m2].I) ) )

/*------------------------------*/
        MatchBid(CP,MP,BP,TP)   /* Create BidList               */
/*------------------------------*/
TCFL    *CP;
TMessL  *MP;
TBidL   *BP;
TTupL   *TP;
{ TMess *M;
  TIdVal M1[SMessL];
ifTC( TIdVal M2[SMessL];
      TIdVal MM[SMessL+1];
      long s1; long s2; )
  TIdVal F[STupL];
  index G[STupL];
  int   H[STupL];               /* Copy of A[].Val              */
  TString Str[SMessL];
  TString as;
  int   n1,n2=1,nn;
  TCF   *C;
  int   h,i,k,k2,N;
  bool  mf;                     /* Matching Flag                */
  long  s,ss=0;                 /* Support                      */
  TBid  *B,*BPB=BP->C;          /* relevant beginning for this  */

for(M=MP->B; M<MP->C; M++) M->H=FALSE;          /* H=Matched    */

for(C=CP->B; C<CP->C; C++) /* for all CF do *//*** Match CF ***/

{ n1=0; ifTC( n2=nn=0; )
  for(i=0; i<MP->C-MP->B; i++) /* for all Mess do               */
  { mf=FALSE;
    if (MatchMC(MP->B[i].M,C->C1.C,C->C1.B)) then
    { M1[n1].Id=i; M1[n1++].Val=MP->B[i].I; mf=TRUE; }
ifTC( if (MatchMC(MP->B[i].M,C->C2.C,C->C2.B)) then
      { M2[n2].Id=i; M2[n2++].Val=MP->B[i].I; mf=TRUE; }
      if (mf) then
      { MM[nn].Id=i; MM[nn++].Val=MP->B[i].I; MP->B[i].H=TRUE; } )
  }
  if (!(C->C1.T&2)) then
  { if (n1) then n1=0;
    else { M1[n1].Id=NonId; M1[n1++].Val=DefNMI;
     ifTC( MM[nn].Id=NonId; M1[nn++].Val=DefNMI; ) } }
ifTC(
  if (!(C->C2.T&2)) then
  { if (n2) then n2=0;
    else
    { M2[n2].Id=NonId; M2[n2++].Val=DefNMI;
      if (MM[nn].Id!=NonId)
      then MM[nn].Id=NonId; MM[nn++].Val=DefNMI; }
  } )
  if (n1&&n2) then
  { cy.MCF++;                   /* for Statistic                */
    if (CP->BidMode>2) then
    { for(i=0; i<n1; i++)
        Str[M1[i].Id]=MatchMA(MP->B[M1[i].Id].M,C->Act.A,C->Act.B);
      GStr=Str;
      QSort(M1,M1+n1-1,InStrOrder);
      for(i=k=0; i<n1; k++)
      { as=Str[M1[i].Id];
        for(h=i,s=0; i<n1 && as==Str[M1[i].Id]; i++)
        { s+=M1[i].Val;         /* maybe max better             */
          if (M1[i].Val>M1[h].Val) then h=i;
        }
        M1[k].Id=M1[h].Id; M1[k].Val=(int)min(s,MaxInt);
      }
      n1=k;
ifTC( for(s=h=i=0; i<n2; i++)
      { s+=M2[i].Val;
        if (M2[i].Val>M2[h].Val) then h=i; }
      M2[0].Id=M2[h].Id;
      M2[0].Val=(int)min(s,MaxInt); n2=1; )
    }
/*** Bid CF ***/
    switch(CP->BidMode) {
    case 1: case 3:                     /* BidMode = 1          */
      if (BP->C>=BP->E) then { Warning(5); goto Full; }
      BP->C->CF=C-CP->B;
ifTC( if (CP->SuppMode==1) then         /* SuppMode = 1 / 2     */
      { for(s=i=0; i<nn; i++) s+=MM[i].Val; }
      else
      { for(s1=i=0; i<n1; i++) s1+=M1[i].Val;
        for(s2=i=0; i<n2; i++) s2+=M2[i].Val;
        s=n2*s1+n1*s2; } )              /* =Sum over all Tuples */
ifnTC( for(s=i=0; i<n1; i++) s+=M1[i].Val; )
      *(long*)&BP->C->BV=s;             /* Supp in .BV & .EV    */
      ss+=s;
      BP->C->N=n1*n2;                   /* Est-Calc will follow */
      BP->C->Tup=TP->C-TP->B;
      for(i=0; i<n1; i++) ifTC( for(k=0; k<n2; k++) )
      { if (TP->C>=TP->E) then { Warning(4); goto Full; }
        TP->C->M1=M1[i].Id;
ifTC(   TP->C->M2=M2[k].Id; )
        TP->C++; }
      BP->C->F=FALSE;
      BP->C++;
      break;
    case 2: case 4:                     /* BidMode = 2          */
      for(i=h=0; i<n1; i++) ifTC( for(k=0; k<n2; k++) )
      { F[h].Id=h;
        F[h].Val=H[h]=TupSupp1(M1[i],M2[k]);
        if (++h>STupL) then { Warning(8); break; }
      }
      k=min(CP->MBids,h);
      if (k>(k2=TP->E-TP->C)) then { k=k2; Warning(4); }
      if (k>(k2=BP->E-BP->C)) then { k=k2; Warning(5); }
      Select(F,&h,G,k,CP->BidTupSelMode); /* normally h=n1*n2 */
      for(h=0; h<k; h++)
      { BP->C->CF=C-CP->B;
        BP->C->BV=H[G[h]];
        BP->C->N=1;
        BP->C->Tup=TP->C-TP->B;
        BP->C->F=FALSE;
        TP->C->M1=M1[G[h]/n2].Id;
ifTC(   TP->C->M2=M2[G[h]%n2].Id; )
        BP->C++; TP->C++; }
      break;
    default: Error(7);
} } }
Full:;
for(M=MP->B; M<MP->C; M++)              /* matching statistic   */
  if (M->H) then cy.MMess++;

/*** Calc BidVal ***/
for(B=BPB; B<BP->C; B++)                /* for all Bids do      */
{ if (CP->BidMode==1) then              /* BV is Supp           */
    B->BV=FPDiv(*(long*)&B->BV,ss);     /* BV is RelSupp / Est  */
  C=CP->B+B->CF;
  B->BV=FPMult(FPPow(CP->RiskFak,B->BV,CP->RelSuppPow),
               FPPow(C->S,C->Sp,CP->SpecPow));/* BV is BidValue */
  B->EV=B->BV+Noise(FPMult(B->BV,Dev2));      /* EV=BV+Noise    */
  B->EV=FPMult(FPPow(FixP(1),B->EV,CP->EBidPow),
                 FPPow(FixP(1),C->Sp,CP->ESpecPow));/* Eff-Bid  */
} }
\end{verbatim}
\begin{verbatim}
/*------------------------------*/
        Fire(CP,MP,BP,TP,NP)    /* Fire Messages                */
/*------------------------------*/
TCFL    *CP;
TMessL  *MP;
TBidL   *BP;
TTupL   *TP;
TMessL  *NP;
{ TIdVal FB[SBidL],FT[STupL];
  index S,GT[STupL];
  int   i,k,NT;
  TCF   *C;
  TBid  *B;
  TTup  *T;
  int   N=BP->C-BP->B;
  bool  Stop=FALSE;
  int   r=NP->E-NP->C;

  for(C=CP->B; C<CP->C; C++) C->H=CP->MFire; /* Fire-Counter    */
  for(i=0; i<N; i++)
  { FB[i].Id=i;
    FB[i].Val=BP->B[i].EV; }
  MultSelInit(FB,N,CP->FireBidSelMode);

  while(r>0 && N!=0)
  { Select(FB,&N,&S,-1,CP->FireBidSelMode); /* -1 = multiple sel*/
    B=BP->B+S; C=CP->B+B->CF; NT=B->N; T=TP->B+B->Tup;
    k=min(NT,min(r,C->H));
    if (k>0) then
    { for(i=0; i<NT; i++)
      { FT[i].Id=B->Tup+i;
        FT[i].Val=TupSupp2(T->M1,T->M2); }
      Select(FT,&NT,GT,k,CP->FireTupSelMode);
      for(i=0; i<k; i++)
      { NP->C->M=MatchMA(MP->B[TP->B[GT[i]].M1].M,
                         C->Act.A,C->Act.B);
        NP->C->I=B->BV;
        NP->C->CF=B->CF;
        NP->C++; }
      C->H-=k; r-=k;
      B->F=TRUE;
    }
} }
/*------------------------------*/
        Clean(MP)               /* Clean Message-List           */
/*------------------------------*/
TMessL  *MP;                    /* MessList to Clean MP --> MP  */
{ TMess  H[SMessL],*HC=H;       /* should and will be empty     */
  TIdVal F[SMessL+1],*F1=F;
  index  G[SMessL];
  int   i;
  TString as;
  TMess *M;
  int   N=MP->C-MP->B;
  TIdVal *F2,*FE=F+N;

  if (N>=MEqMess) then
  { GMB=MP->B;
    for(i=0; i<N; i++)
    { F[i].Id=i; F[i].Val=GMB[i].I; }
    QSort(F,F+N-1,InMessOrder);

    while(F1<FE)
    { as=GMB[F1->Id].M;
      for(F2=F1+1; F2<FE && GMB[F2->Id].M==as; F2++);
      N=F2-F1;
      if (N>MEqMess) then
      { Select(F1,&N,G,MEqMess,DelMessSelMode);
        for(i=0; i<MEqMess; i++)
          memcpy(HC++,GMB+G[i],sizeof(TMess));
        F1=F2; }
      else
        for(; F1<F2; F1++)
          memcpy(HC++,GMB+F1->Id,sizeof(TMess));
    }
    memcpy(MP->B,H,(HC-H)*sizeof(TMess));
    MP->C=GMB+(HC-H);
  }
  if (CleanHallF) then
  { for(M=MP->B; M<MP->C;)
      if (MatchMC(M->M,DetMTagC,DetMTagB)) then
        memcpy(M,--MP->C,sizeof(TMess));
      else M++;
} }
/*------------------------------*/
Credit(CP,EP,MP,NP,BP,DP,TP,UP) /* Credit-Assignment            */
/*------------------------------*/
TCFL    *CP,*EP;
TMessL  *MP,*NP;
TBidL   *BP,*DP;
TTupL   *TP,*UP;
{ index BidN;
  fixp  Val;
  long  Sum;
  TCF   *C;
  TMess *M;
  TBid  *B;
  switch(CreditMode) {
  case 1:                       /* Explicit Bucket-Brigade      */
    for(C=CP->B-1; C<CP->C; C++) /* Test */
      C->Get=C->Pay=FixP(0);
  /* Set .H = +-Rate, - = Visited */
    SetMFrac(NP); SetMFrac(MP);
  /* Distribute Reinforcement */
    Sum=0;
    for(B=DP->B; B<DP->C; B++)
      if (B->F) Sum+=CrSum(UP->B+B->Tup,B->N,NP,EP);
    if (Sum) then
    { Val=FPDiv(ReVal,Sum);
      for(B=DP->B; B<DP->C; B++)
        if (B->F) Distr(UP->B+B->Tup,B->N,NP,EP,CP,Val);
    }
  /* Distribute Bids */
    for(B=BP->B; B<BP->C; B++) if (B->F) then
      if (B->N) then
      { Sum=CrSum(TP->B+B->Tup,B->N,MP,CP);
        if (Sum) then
        { Val=FPDiv(B->BV,Sum);
          CP->B[B->CF].Pay=Distr(TP->B+B->Tup,B->N,MP,CP,CP,Val);
      } }
    break;
  case 2: Error(8); break;      /* Implicit Bucket-Brigade      */
  case 3:                       /* Profit Sharing Plan          */
    for(B=BP->B; B<BP->C; B++) if (B->F) then
    { C=CP->B+B->CF;
      Val= (PSPDisMode<3) ? FixP(1) : B->BV;
      if (PSPDisMode&1)
      then C->PSP=max(C->PSP,Val);
      else if ((FixP(127)-C->PSP)<Val)
           then C->PSP=FixP(127);
           else C->PSP+=Val;
    }
    if (CycleC%ReRate==0) then
      for(C=CP->B; C<CP->C; C++)
      if (C->PSP) then
      { C->Pay=FPMult(PSPFrac,C->PSP);
        C->Get=FPMult(PSPFrac,ReVal);
        C->PSP=FixP(0); }
      else { C->Pay=C->Get=0; }
    break;
  case 4: /* no Credit-Asignment */
  default: Error(8);            /* No Credit Assignment         */}
}
\end{verbatim}
\begin{verbatim}
/*------------------------------*/
        Taxes(CP,NP,BP)         /* Tax-Payment                  */
/*------------------------------*/
TCFL    *CP;
TMessL  *NP;
TBidL   *BP;
{ TCF   *C;
  TMess *M;
  TBid  *B;

  for(C=CP->B-1; C<CP->C; C++)
  { C->Tax=HeadTax; C->H=0; }

  for(M=NP->B; M<NP->C; M++)
  { C=CP->B+M->CF;
    if (!C->H || MultMessTaxF) then
    { C->Tax+=MessTax; C->H=1; }
  }
  for(B=BP->B; B<BP->C; B++)
  { C=CP->B+B->CF;
    if ((!(C->H&2) || MultBidTaxF) &&
        (!(C->H&1) || BidTaxMode==1)) then
    { C->Tax+=BidTax; C->H|=2; }
  }
  for(C=CP->B; C<CP->C; C++)
    C->Tax=FPMult(C->S,C->Tax);
}
/*------------------------------*/
        StrUpDate(CP)           /* Strength-Update (Test !!)    */
/*------------------------------*/
TCFL    *CP;
{ TCF   *C;
  for(C=CP->B; C<CP->C; C++)
    C->S=max(MinStr,min(MaxStr,
         C->S+C->Get-C->Pay-C->Tax));
}
/*------------------------------*/
        Genetic(CP)             /* Genetic Operations           */
/*------------------------------*/
TCFL    *CP;
{ TIdVal F[SCFL];
  index  G[SCFL];
  TCF   *C;
  int   i,k;
  int   N=CP->C-CP->B;

  if (prMode>1) then
    prf(LIGHTBLUE,
    "%ld.genetic algorithm envocation\r\n",CycleC/GenRate);

/* Replace CF (and Sender in MessL, not impl.) */
  for(i=0; i<N; i++)
  { F[i].Id=i;
    F[i].Val= CP->B[i].S ? FPDiv(FixP(0.49),CP->B[i].S) : FixP(127);
  }
  Select(F,&N,G,NCFRepl,ReplSelMode);
  for(i=0; i<NCFRepl; i++) RandCF(CP->B+G[i]);

/* Mutate CF */
  for(i=0; i<N; i++)
  { F[i].Id=i;
    F[i].Val= CP->B[i].S ? FPDiv(FixP(0.5),CP->B[i].S) : FixP(127);
  }
  Select(F,&N,G,NCFMut,MutSelMode);
  for(i=0; i<NCFMut; i++)
  { C=CP->B+G[i];
    for(k=0; k<NMutate; k++)
    { MutateCA(&C->C1.C,&C->C1.B,CondSp);
      ifTC( MutateCA(&C->C2.C,&C->C2.B,CondSp); )
      MutateCA(&C->Act.A,&C->Act.B,ActSp);
  } }
}
/*------------------------------*/
        ReInit(o)               /* Re-Initialize                */
/*------------------------------*/
TCS     *o;
{ TMessL *h;
  TMess  *M;
  memswap(o->MP,o->NP,sizeof(TMessL));
  o->NP->C=o->NP->B;
  o->OP->C=o->OP->B;
  o->BP->C=o->BP->B;
  o->TP->C=o->TP->B;

  if (DelMessMode) then
  { for(M=o->MP->B; M<o->MP->C;)
      if (DelMessMode==2 || MatchMC(M->M,EffMTagC,EffMTagB)) then
        memcpy(M,--o->MP->C,sizeof(TMess));
      else M++;
} }
/*------------------------------*/
        InitStat(stp)           /* Initialize Statistic         */
/*------------------------------*/
TStat   *stp;
{ memset(stp,0,sizeof(TStat));
}
/*------------------------------*/
        UpdStat(o)              /* Update Statistic             */
/*------------------------------*/
TCS     *o;
{ TCF   *C;
  int   i;
  cy.CycleC=1;
  cy.ReVal=ReVal;
  cy.NCFMinStr=cy.NCFMaxStr=cy.Str=0;
  for(C=o->CP->B; C<o->CP->C; C++)
  { cy.Str+=C->S;
    if (C->S==MinStr) then cy.NCFMinStr++;
    if (C->S==MaxStr) then cy.NCFMaxStr++; }
  /* cy.MCF and cy.MMess are updated in MatchBid() */
  cy.NCF  =o->CP->C-o->CP->B;
  cy.NBid =o->BP->C-o->BP->B;
  cy.NTup =o->TP->C-o->TP->B;
  cy.NMess=o->MP->C-o->MP->B;
  for(i=0; i<sizeof(TStat)/sizeof(long); i++)   /* TStat =      */
    ((long*)&ep)[i]+=((long*)&cy)[i];           /* long A[8]    */
}
/*------------------------------*/
        MainStep(o)             /* Main Evaluation Cycle        */
/*------------------------------*/
TCS     *o;
{ if (CycleC%StRate==0) then InitStat(&ep);
  CycleC++;  Detect(o->MP,MDetM);
  cy.MCF=cy.MMess=0;                          /* for Stat       */

  MatchBid(o->CP,o->MP,o->BP,o->TP);
  if (DelMessMode!=2) then o->NP->E-=MDetM; /* res. for DetMess */
  Fire(o->CP,o->MP,o->BP,o->TP,o->NP);
  if (DelMessMode!=2) then o->NP->E+=MDetM; /* free reserved "  */
  Clean(o->NP);

  if (CycleC%EffRate==0) then
  { o->DP->B=o->DP->C=o->BP->C; /* because DP=BP,UP=TP          */
    o->UP->B=o->UP->C=o->TP->C;
    MatchBid(o->EP,o->NP,o->DP,o->UP);
    Fire(o->EP,o->NP,o->DP,o->UP,o->OP);
    /* maybe create EMess, if OP is Empty */
    Effect(o->OP);
  }
  if (CycleC%ReRate==0)
  then ReVal=Reinf(o->OP);
  else ReVal=FixP(0);
  Credit(o->CP,o->EP,o->MP,o->NP,o->BP,o->DP,o->TP,o->UP);
  Taxes(o->CP,o->NP,o->BP);
  pprCS(prMode,o);
  StrUpDate(o->CP);
  if (CycleC%GenRate==0) then Genetic(o->CP);
  UpdStat(o);
  if (CycleC%StRate==0) then pprStat(prMode,&ep);
  if (SStepF && ((prMode>1)||(CycleC%StRate==0)))
  then  Menu(); else event();
  ReInit(o);
}
\end{verbatim}

\begin{verbatim}
/****************************************************************/
/*              M e n u - C o n t r o l                         */
/****************************************************************/

/*------------------------------*/
char    GetKey()                /* Get a Key                    */
/*------------------------------*/
{ char c=getch();
  if (c==0) then c=128+getch();
}
/*------------------------------*/
        Menu()                  /* Wait for Key/Menu-Selection  */
/*------------------------------*/
{ char  c;
  extern chdo(char c);
  do { c=GetKey(); if (c!=ESC) chdo(c); }
  while(!strchr("Cc ",c));
  if (!SStepF) prf(LIGHTGREEN,"Simulation Continued\r\n");
}
/*------------------------------*/
        prMenu()                /* Display Menu                 */
/*------------------------------*/
{ window(1,1,80,1);
  textbackground(BLUE);
  clrscr();
  cprintf("Retart ESC Cont Break Abort Prot stEp ");
  cprintf("Help Display Sound 0123 rdZ Test\r");
  window(1,3,80,NScrL);
  textbackground(BLACK);
}
/*------------------------------*/
        chdo(char c)            /* Branch on Menu-Selection c   */
/*------------------------------*/
{ extern CFSMain(),CFSExit(),TestFunc();
  switch(toupper(c)) {
  case 'R': CFSExit(); longjmp(jmp,1);     /* ReStart CFS-Simul.*/
  case 'B': BreakPoint();                  /* Break to TC++     */
  case ESC: prf(LIGHTGREEN,                /* Interrupt Simul.  */
    "Simulation Interrupted in Cycle %ld\r\n",CycleC);
    Menu(); break;
  case 'C': case ' ': break;               /* Continue Simul.   */
  case 'A': CFSExit(); exit(0);            /* Abort to CFS      */
  case 'P': SetProt(!ProtF);  break;       /* Protocoll on/off  */
  case 'E': SetSStep(!SStepF);break;       /* SingleStep on/off */
  case 'H': case 187: pprInfo(); break;    /* Printf Help-Info  */
  case 'D': pprCS(max(prMode,2),o); break; /* Print Status      */
  case '0': case '1': case '2':            /* PrintMode 0123    */
  case '3': SetprMode(c-'0'); break;
  case 'S': SetSound(!SoundF); break;      /* Sound on/off      */
  case 'Z': randomize(); break;            /* randomize         */
  case 'T': TestFunc(); break;             /* Testfunction      */
  default : Sound(2500,10);                /* Wrong Key         */
} }
/*------------------------------*/
char    event()                 /* look for KeyBoard-Event      */
/*------------------------------*/
{ char  c;
  if (!kbhit()) then return(0);
  c=GetKey(); chdo(c); return(c);
}
/****************************************************************/
/*                T e s t - P r o c e d u r e s                 */
/****************************************************************/

/*------------------------------*/
        TestFunc()              /* Testfunction                 */
/*------------------------------*/
{ int i;
  prf(LIGHTCYAN,"This is a test ...\r\n");
  Error(0);
}
\end{verbatim}

\begin{verbatim}
/****************************************************************/
/*      I n i t - E x i t - M a i n - P r o c e d u r e s       */
/****************************************************************/

#define oalloc(P,S)                             \
        P->B=malloc((S+1)*sizeof(*P->B));       \
        if (P->B==NULL) then Error(6);          \
        P->B=P->C=P->B+1; P->E=P->B+S;

/*------------------------------*/
        InitMessL(MP,S)         /* Init Mess-List               */
/*------------------------------*/
TMessL  *MP;
int     S;
{ MP->B=malloc((S+1)*sizeof(TMess));
  if (MP->B==NULL) then Error(6);
  MP->B->M=0; MP->B->I=DefNMI; MP->B->CF=NonId;
  MP->B=MP->C=MP->B+1; MP->E=MP->B+S;
}
/*------------------------------*/
        InitCFL(CP,S)           /* Init CF-List                 */
/*------------------------------*/
TCFL    *CP;
int     S;
{ CP->B=malloc((S+1)*sizeof(TCF));
  if (CP->B==NULL) then Error(6);
  CP->B->S=FixP(1); /* ... */
  CP->B=CP->C=CP->B+1; CP->E=CP->B+S;
}
/*------------------------------*/
             CFSInit()          /*      Initialisierung         */
/*------------------------------*/
{ char  **S;
  char  T[SStr+1];

/* Other Initializations */
  memset(WC,0,sizeof(WC));
  memset(WP,0,sizeof(WP));
  srand(12345);

/* Create Arrays */
  InitMessL(o->MP,SMessL);
  InitMessL(o->NP,SMessL);
  InitMessL(o->OP,SOutL);
  InitCFL(o->CP,SCFL);
  InitCFL(o->EP,SEffL);
  oalloc(o->BP,SBidL);
  memcpy(o->DP,o->BP,sizeof(TBidL));
  oalloc(o->TP,STupL);
  memcpy(o->UP,o->TP,sizeof(TTupL));

/* Init Classifier & Effectors & Enviroment */
  for(S=CFSL; *S; S++)
    StoCF(*S,o->CP->C++,DefStr,DefStrDev);
  while(o->CP->C<o->CP->E) RandCF(o->CP->C++);
  for(S=EffSL;*S; S++)
    StoCF(*S,o->EP->C++,FixP(1),FixP(0));
  InitEnv();

/* Read Detector/Effector-Tags */
  memset(T,'#',SStr); T[SStr]='\0';
  memcpy(T,DetMessTag,min(strlen(DetMessTag),SStr));
  StoCB(T,&DetMTagC,&DetMTagB);
  memset(T,'#',SStr); T[SStr]='\0';
  memcpy(T,EffMessTag,min(strlen(EffMessTag),SStr));
  StoCB(T,&EffMTagC,&EffMTagB);

/* Open Devices */
  textmode(C4350); textcolor(YELLOW);
  devP=fopen(ProtDev,"ab");
  CycleC=0; ProtF=TRUE; SStepF=FALSE;
  textbackground(BLACK);
  clrscr(); prMenu();
  if (prMode>0) then { prf(LIGHTCYAN,
    "%s\r\n%s\r\n%s\r\n%s\r\n%s\r\n%s%s%s\r\n%s\r\n\n",
    "+---------------------------------------------------------+",
    "|  C l a s s i f i e r - S y s t e m - S i m u l a t o r  |",
    "|---------------------------------------------------------|",
    "|  Copyright by Marcus Hutter     01.04.91     Vers. 1.0  |",
    "|---------------------------------------------------------|",
    "|       Simulation Run ("  ,   ActTime()   ,   ")         |",
    "+---------------------------------------------------------+");
  }
  SetProt(FALSE);
  SetSStep(TRUE);
}
/*------------------------------*/
             CFSMain()          /*      Main-Routinen           */
/*------------------------------*/
{ prf(LIGHTGREEN,
  "Press <C> to continue ... or any other Menu-Key\r\n");
  Menu();
  FOREVER MainStep(o);
}
/*------------------------------*/
             CFSExit()          /*      Exit-Routinen           */
/*------------------------------*/
{ fclose(devP); fclose(lpt1);
  free(o->TP->B-1); free(o->BP->B-1);
  free(o->EP->B-1); free(o->CP->B-1);
  free(o->OP->B-1); free(o->NP->B-1); free(o->MP->B-1);
}
/*------------------------------*/
             main()             /*      Main-Program            */
/*------------------------------*/
{ setjmp(jmp);
  CFSInit();
  CFSMain();
  CFSExit();                    /* not needed */
  exit(0);                      /* not needed */
}
\end{verbatim}
\end{listing}

\clearpage
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{ Beispiellisting {\tt EXAMPLE1.C} }
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{listing}
\begin{verbatim}
/****************************************************************/
/*      C l a s s i f i e r - S y s t e m - E x a m p l e   1   */
/****************************************************************/
/*      T e s t    (c) by Marcus Hutter  01.04.1991             */
/****************************************************************/

/* USER-Variables are Model-dependend                           */
/* user-Variables are Program-Specific                          */

/*------------------------------*/
/*      Variables               */
/*------------------------------*/

/* Array-Sizes and other Compiler-Information */
#define SMessL          1       /* USER: # of Messages          */
#define SOutL           1       /* USER: # of Mess prod. by Eff */
#define SCFL          100       /* USER: # of Classifiers       */
#define SEffL           1       /* USER: # of Effectors         */
#define SBidL         100       /* user: # of matching-mess     */
#define STupL         100       /* user: # of matching-tuples   */

#define SStr            6       /* USER: # of Bits per String   */
#define TwoCond      FALSE      /* USER: two Conditions (or one)*/
#define SpeedF        TRUE      /* user: Optimize for Speed     */

BreakPoint() {}         /* Set a BreakPoint in this Line !!     */

#include "D:\TC\MYPROGS\CFSSIM.C" /* Classifier-System-Sim.     */

/* General - Variables  */
int     StRate  =      100;     /* USER: Statistic-Activ-Rare   */
fixp    SclSel  =  FixP(2/3);   /* USER: Scale-Factor  50%-100% */
char ProtDev[30]="example1.lst";/* USER: Protocoll-Device       */
char    DetMessTag[] =  "#";    /* USER: {0,1,#}*               */
char    EffMessTag[] =  "##";   /* USER: {0,1,#}*               */

/* Detector - Variables */
int     DetRate  =      1;      /* USER: Det.-Sampling-Rate     */
int     MDetM    =      1;      /* USER: # of Det.Mess.         */
fixp    DefDetMI = FixP(1.0);   /* USER: Detector-Mess-Intens.  */
fixp    DefStr   = FixP(2.0);   /* USER: DefaultStrength 0..9   */
fixp    DefStrDev= FixP(0.1);   /* USER: DefaultStrDev   0..25% */

/* Matching - Variables */
fixp    DefNMI  =  FixP(1.0);   /* USER: Default NonMatchIntens */

/* Bid - Variables */
fixp    Dev2    =  FixP(0.0);   /* USER: EBid-Deviation  0..25% */

/* Clean - Variables */
int     MEqMess       = MaxInt; /* USER: # of Equal Mess.       */
sbyte   DelMessSelMode= 2;      /* USER: DelMode       -6..6    */
bool    CleanHallF    = FALSE;  /* USER: Clean Hallunc.Mess.    */

/* Effector - Variables */
int     EffRate       = 1;      /* USER: Eff.-Sampling-Rate     */

/* Credit - Variables   */
int     ReRate    =     1;      /* USER: Reinf.Act.Rate         */
byte    CreditMode=     1;      /* USER: Credit-Assign-Mode     */
fixp    NMFrac    =FixP(0.3);   /* USER: NonMatchCreditFrac.in% */
fixp    DetFrac   =FixP(0.5);   /* USER: DetectorCreditFrac.in% */
fixpPSPFrac   =FixP(0.1);       /* USER: PSP-Reduc.-Constant.in%*/
byte    PSPDisMode=     4;      /* USRR: PSP-Distr.-Mode 1..4   */

/* Taxes - Variables    */
fixp    HeadTax  = FixP(0.00);  /* USER: Head-Tax (CF-Tax)      */
fixp    MessTax  = FixP(1.00);  /* USER: Mess-Tax               */
fixp    BidTax   = FixP(0.00);  /* USER: Bid-Tax                */
byte    BidTaxMode   =  2;      /* USER: BidTaxMode      1..2   */
bool    MultBidTaxF  =  FALSE;  /* USER: Tax for each Bid       */
bool    MultMessTaxF =  FALSE;  /* USER: Tax for each Mess      */

/* StrUpDate - Variables*/
fixp    MaxStr  =   FixP(20.0); /* USER: Maximal Strength of CF */
fixp    MinStr  =   FixP( 0.0); /* USER: Minimal Strength of CF */

/* Genetic - Variables  */
int     GenRate   =     50;     /* USER: Genetic-Activ.-Rate    */
int     NCFRepl   =     50;     /* USER: # of CF to Replace     */
sbyte   ReplSelMode=    3;      /* USER: Replace-SelMode        */
int     NCFMut    =     0;      /* USER: # of CF to Mutate      */
int     NMutate   =     1;      /* USER: # of Mutations per CF  */
sbyte   MutSelMode=     3;      /* USER: Mutation-SelMode       */
fixp    CondSp    =FixP(0.50);  /* USER: Mean Cond-Specifity  % */
fixp    ActSp     =FixP(1.0);   /* USER: Mean Act.-Specifity  % */
fixp    NegCondP  =FixP(0.00);  /* USER: Prob. of neg. Cond   % */

/* ReInit - Variables   */
byte    DelMessMode =   2;      /* USER: Del.Mess-Mode   0..2   */
\end{verbatim}

\begin{verbatim}
TCFL    XC      = { 0,0,0,      /* Classifier-Parameters        */
        2,                      /* USER: BidMode         1..4   */
        2,                      /* USER: SuppMode        1..2   */
        2,                      /* USER: BidTupSelMode  -6..6   */
        2,                      /* USER: BidActSelMode  -6..6   */
        3,                      /* USER: FireBidSelMode -6..6   */
        2,                      /* USER: FireTupSelMode -6..6   */
        5,                      /* USER: MBids      1..MaxInt   */
        MaxInt,                 /* USER: MAct       1..MaxInt   */
        MaxInt,                 /* USER: MFire      1..MaxInt   */
        FixP(1.0),              /* USER: RiskFak   FixP(0..1) % */
        1,                      /* USER: SpecPow         0..2   */
        1,                      /* USER: RelSuppPow      0..2   */
        1,                      /* USER: EBidPow         0..2   */
        0,                      /* USER: ESpecPow        0..2   */
        1,                      /* USER: ClaimMode       1..2   */
        1,                      /* USER: DisMode         1..5   */
        2 };                    /* USER: SumMode         1..3   */

TCFL    XE      = { 0,0,0,      /* Effector-Parameters          */
        2,                      /* USER: BidMode         1..4   */
        2,                      /* USER: SuppMode        1..2   */
        2,                      /* USER: BidTupSelMode  -6..6   */
        2,                      /* USER: BidActSelMode  -6..6   */
        2,                      /* USER: FireBidSelMode -6..6   */
        2,                      /* USER: FireTupSelMode -6..6   */
        5,                      /* USER: MBids      1..MaxInt   */
        MaxInt,                 /* USER: MAct       1..MaxInt   */
        1,                      /* Should be 1 (MFire)          */
        FixP(0.5),              /* USER: RiskFak   FixP(0..1) % */
        1,                      /* USER: SpecPow         0..2   */
        1,                      /* USER: RelSuppPow      0..2   */
        1,                      /* USER: EBidPow         0..2   */
        0,                      /* USER: ESpecPow        0..2   */
        1,                      /* USER: ClaimMode       1..2   */
        1,                      /* USER: DisMode         1..5   */
        2 };                    /* USER: SumMode         1..3   */


char    *MessSL[] =             /* Predefined Messages          */
      { /* "1111",
        "1000",
        "1001",
        "0000", */
        NULL };

char    *CFSL[] =               /* Predefined Classifiers       */
      { /* "+1###+#11#/01#1",
        "-0###-0###/111#",
        "+0###-0000/1###", */
        NULL };

char    *EffSL[] =              /* Predefined Effectors         */
      { "+######/00000#",
        NULL };

typedef struct                  /* Enviroment                   */
      { int     inp;
        int     out;
        bool    success;
        /*...*/ }
        TEnv;

TEnv    Env;                    /* Current Enviroment           */

/*------------------------------*/
        InitEnv()               /* Init Enviroment              */
/*------------------------------*/
{ memset(&Env,0,sizeof(Env));
}
/*------------------------------*/
        Detect(MP,N)            /* Detect Messages              */
/*------------------------------*/
TMessL  *MP;                    /* Message-List                 */
int     N;                      /* Max.# of Det.Mess            */
{ Env.inp=rand()&63;            /* 2 Addr. & 4 Inp. Bits        */
  Env.out=(Env.inp>>(5-(Env.inp&3)))&1;
  MP->C->M = Env.inp;
  MP->C->I = DefDetMI;
  MP->C->CF= DetId;
  MP->C++;
}
/*------------------------------*/
        Effect(OP)              /* Effect Messages              */
/*------------------------------*/
TMessL  *OP;
{/* Change Enviroment in dependence on MP */
 /* prf(0,"Output-Mess = Env.Change:\n");
  pprMessL(MP); */
}
/*------------------------------*/
fixp    Reinf(OP)               /* Calculate Reinforcement      */
/*------------------------------*/
TMessL  *OP;
{ Env.success = (OP->C>OP->B) && (Env.out==(OP->B->M));
  return(FixP((Env.success) ? 10 : 0 ));
}
/*------------------------------*/
        Display()               /* Display Information          */
/*------------------------------*/
{ if (prMode>1) then
    prf(LIGHTRED,"4to1Decoder: %s->%d %s\r\n",
      CBtoS(Env.inp,MMask),Env.out,
      (Env.success) ? "Success" : "Failure");
}

/********************** End of Example 1 ************************/
\end{verbatim}
\end{listing}

\clearpage
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{ Beispielprotokoll {\tt EXAMPLE1.LST} }
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{listing}
\begin{verbatim}
+---------------------------------------------------------+
|  C l a s s i f i e r - S y s t e m - S i m u l a t o r  |
|---------------------------------------------------------|
|  Copyright by Marcus Hutter     01.04.91     Vers. 1.0  |
|---------------------------------------------------------|
|       Simulation Run (Sun May 12 09:01:02 1991)         |
+---------------------------------------------------------+
Protocoll ON
4to1Decoder: 101011->0 Failure
-------------- Cycle 1 --------------

Message-List:
MId Intens Sender Message
  0:  1.00   D    101011

Classifier-List:
CFId   Str    Get    Pay  Taxes Condion/Action
  0:  1.71   0.00   0.00   0.00 +#0##0#/111011
  1:  1.90   0.00   0.00   0.00 +10#01#/000000
  2:  1.90   0.00   0.00   0.00 +#11#00/100100
  3:  2.00   0.00   0.00   0.00 +1101#1/110110
  4:  2.29   0.00   0.00   0.00 +##0#1#/000110
  5:  1.80   0.00   0.00   0.00 +##000#/001010
  6:  1.90   0.00   0.00   0.00 +0#1###/111111
  7:  2.39   0.00   0.00   0.00 +11####/010001
  8:  2.00   0.00   0.00   0.00 +0#10#0/010111
  9:  2.10   0.00   0.00   0.00 +##10#0/110001
 10:  2.20   0.00   0.00   0.00 +0#1101/011010
 11:  1.90   0.00   0.00   0.00 +#0#01#/100000
 12:  1.80   0.00   0.00   0.00 +#00#00/110101
 13:  2.00   0.00   0.00   0.00 +##100#/111111
 14:  2.00   0.00   0.00   0.00 +####1#/110000
 15:  2.00   0.00   0.00   0.00 +000##1/010100
 16:  1.80   0.00   0.00   0.00 +##0#10/100100
 17:  1.90   0.00   0.00   0.00 +###1#0/110111
 18:  2.10   0.00   0.00   0.00 +0###1#/001110
 19:  1.71   0.00   0.00   0.00 +1#1###/011011
 20:  1.80   0.00   0.00   0.00 +#01110/001101
 21:  1.90   0.00   0.00   0.00 +#01#1#/011100
 22:  1.51   0.00   0.00   0.00 +##0##1/111100
 23:  2.10   0.00   0.00   0.00 +110###/000011
 24:  2.10   0.00   0.00   0.00 +###1##/000010
 25:  2.10   0.00   0.00   0.00 +10##1#/010010
 26:  2.20   0.00   0.00   0.00 +1##11#/010110
 27:  1.90   0.00   0.00   0.00 +##1#11/100000
 28:  2.39   0.00   0.00   0.00 +###0##/000010
 29:  1.90   0.00   0.00   0.00 +##001#/011100
 30:  2.29   0.00   0.00   0.00 +0#0###/000101
 31:  2.10   0.00   0.00   0.00 +#0#001/100000
 32:  1.90   0.00   0.00   0.00 +#0##0#/001101
 33:  1.90   0.00   0.00   0.00 +#0#100/100111
 34:  1.90   0.00   0.00   0.00 +101#10/001100
 35:  1.71   0.00   0.00   0.00 +######/011000
 36:  2.10   0.00   0.00   0.00 +0#10#0/111010
 37:  1.90   0.00   0.00   0.00 +100#1#/010100
 38:  1.90   0.00   0.00   0.00 +##1#1#/011110
 39:  1.71   0.00   0.00   0.00 +0#####/000111
 40:  2.20   0.00   0.00   0.00 +10#00#/001010
 41:  2.10   0.00   1.74   2.10 +10101#/100011
 42:  2.20   0.00   0.00   0.00 +###01#/111010
 43:  2.00   0.00   0.00   0.00 +1#####/000011
 44:  2.20   0.00   0.00   0.00 +###0#0/011001
 45:  2.00   0.00   0.00   0.00 +0#00##/010111
 46:  2.10   0.00   0.00   0.00 +10####/110001
 47:  1.90   0.00   0.00   0.00 +10####/001011
 48:  1.32   0.00   0.00   0.00 +#0###1/000001
 49:  1.90   0.00   0.00   0.00 +0000##/001101
 50:  1.80   0.00   0.00   0.00 +#11###/000011
 51:  2.10   0.00   0.00   0.00 +10#10#/011100
 52:  2.00   0.00   0.00   0.00 +##010#/010111
 53:  1.80   0.00   0.00   0.00 +#00##1/100100
 54:  1.90   0.00   0.00   0.00 +1#1011/111001
 55:  2.10   0.00   0.00   0.00 +00##1#/000110
 56:  1.90   0.00   0.00   0.00 +1#1111/111111
 57:  2.20   0.00   0.00   0.00 +10##0#/011111
 58:  2.00   0.00   0.00   0.00 +0#11##/001100
 59:  1.71   0.00   0.00   0.00 +#0#1#0/001010
 60:  2.39   0.00   0.00   0.00 +####10/010111
 61:  2.00   0.00   0.00   0.00 +11#0##/101000
 62:  2.10   0.00   0.00   0.00 +0#00##/001100
 63:  2.39   0.00   0.00   0.00 +##001#/101010
 64:  1.71   0.00   0.00   0.00 +1##1#1/100000
 65:  2.00   0.00   0.00   0.00 +11##01/001001
 66:  2.29   0.00   0.00   0.00 +#10110/010011
 67:  2.00   0.00   0.00   0.00 +1#11##/010000
 68:  2.00   0.00   0.00   0.00 +10001#/011000
 69:  2.10   0.00   0.00   0.00 +#11###/100100
 70:  2.20   0.00   0.00   0.00 +##0001/111010
 71:  2.00   0.00   0.00   0.00 +1##111/010111
 72:  1.80   0.00   0.00   0.00 +###0##/001100
 73:  2.00   0.00   0.00   0.00 +0##1#1/100010
 74:  2.10   0.00   0.00   0.00 +0####0/101110
 75:  2.00   0.00   0.00   0.00 +#110##/000010
 76:  1.90   0.00   0.00   0.00 +#0##11/101101
 77:  2.10   0.00   0.00   0.00 +##01#1/100101
 78:  1.90   0.00   0.00   0.00 +1#####/100010
 79:  1.90   0.00   0.00   0.00 +0#00#1/010001
 80:  2.00   0.00   0.00   0.00 +##1##1/111110
 81:  2.20   0.00   0.00   0.00 +#101#1/000101
 82:  1.90   0.00   0.00   0.00 +00100#/100101
 83:  2.10   0.00   0.00   0.00 +##0111/010100
 84:  1.90   0.00   0.00   0.00 +00####/001010
 85:  2.10   0.00   0.00   0.00 +1111#1/011001
 86:  2.10   0.00   0.00   0.00 +#001#1/001000
 87:  2.10   0.00   0.00   0.00 +1##1#0/100010
 88:  2.39   0.00   0.00   0.00 +###0#0/110000
 89:  1.90   0.00   0.00   0.00 +1###0#/001111
 90:  2.00   0.00   0.00   0.00 +#0###1/001000
 91:  1.80   0.00   0.00   0.00 +1####1/110100
 92:  2.10   0.00   0.00   0.00 +##11#0/110100
 93:  1.71   0.00   0.00   0.00 +0###1#/011011
 94:  2.00   0.00   0.00   0.00 +100#11/000001
 95:  1.41   0.00   0.00   0.00 +###10#/110111
 96:  2.20   0.00   0.00   0.00 +##11##/111101
 97:  2.00   0.00   0.00   0.00 +1#0###/101010
 98:  1.90   0.00   0.00   0.00 +##01#0/001000
 99:  2.10   0.00   0.00   0.00 +#0#10#/000111

Bid-List:
BidId CFId Bid EBid Fired BidTupel
  0:   1   1.26   1.26 - { 0 }
  1:  11   0.95   0.95 - { 0 }
  2:  14   0.33   0.33 - { 0 }
  3:  19   0.57   0.57 - { 0 }
  4:  21   0.95   0.95 - { 0 }
  5:  25   1.05   1.05 - { 0 }
  6:  27   0.95   0.95 - { 0 }
  7:  28   0.39   0.39 - { 0 }
  8:  35   0.00   0.00 - { 0 }
  9:  38   0.63   0.63 - { 0 }
 10:  41   1.74   1.74 F { 0 }
 11:  42   0.73   0.73 - { 0 }
 12:  43   0.33   0.33 - { 0 }
 13:  46   0.70   0.70 - { 0 }
 14:  47   0.63   0.63 - { 0 }
 15:  48   0.43   0.43 - { 0 }
 16:  54   1.58   1.58 - { 0 }
 17:  72   0.29   0.29 - { 0 }
 18:  76   0.95   0.95 - { 0 }
 19:  78   0.31   0.31 - { 0 }
 20:  80   0.66   0.66 - { 0 }
 21:  90   0.66   0.66 - { 0 }
 22:  91   0.60   0.60 - { 0 }

New-Message-List:
MId Intens Sender Message
  0:  1.74  41    100011

Effector-List:
CFId   Str    Get    Pay  Taxes Condion/Action
  0:  1.00   0.00   0.00   0.00 +######/00000#

Eff-Bid-List:
BidId CFId Bid EBid Fired BidTupel
  0:   0   0.00   0.00 F { 0 }

Output-Message-List:
MId Intens Sender Message
  0:  0.00   0    000001

Cycle-Cycle  Reinf Strength Min Max Mch Mch Bid Tup
             Value          Str Str  CF Mess 's els
    1-1    :  0.000   0.000   0   0  24   0   0   0
PrintMode = 2
4to1Decoder: 011101->1 Failure
Cycle-Cycle  Reinf Strength Min Max Mch Mch Bid Tup
             Value          Str Str  CF Mess 's els
    2-2    :  0.000   1.968   1   0  13   0  23  23
4to1Decoder: 011111->1 Failure
    3-3    :  0.000   1.946   2   0  16   0  12  12
4to1Decoder: 111010->1 Success
    4-4    :  0.000   1.926   3   0  19   0  15  15
4to1Decoder: 000110->0 Success
    5-5    : 10.000   1.995   3   0  17   0  18  18
4to1Decoder: 011000->0 Failure
    6-6    : 10.000   2.063   3   0  17   0  16  16
\end{verbatim}

\begin{verbatim}
PrintMode = 1
SingleStep OFF
Simulation Continued
Cycle-Cycle  Reinf Strength Min Max Mch Mch Bid Tup
             Value          Str Str  CF Mess 's els
    1-100  :  6.400   2.268   8   0  18   0  17  17
  101-200  :  7.800   2.525   5   0  19   0  18  18
  201-300  :  8.900   2.718   2   0  18   0  17  17
  301-400  :  8.900   2.887   2   0  19   0  18  18
  401-500  :  8.700   2.851   3   0  17   0  16  16
  501-600  :  8.600   2.792   4   0  18   0  17  17
  601-700  :  9.300   2.926   1   0  19   0  18  18
  701-800  :  9.600   2.999   1   0  17   0  16  16
  801-900  :  9.500   2.991   1   0  17   0  16  16
  901-1000 :  9.700   3.042   0   0  18   0  17  17
 1001-1100 :  9.300   3.101   1   0  17   0  16  16
 1101-1200 :  9.800   3.156   0   0  16   0  15  15
 1201-1300 :  9.600   3.100   0   0  16   0  15  15
 1301-1400 :  9.600   3.094   1   0  17   0  16  16
 1401-1500 :  9.900   3.145   0   0  17   0  16  16
 1501-1600 :  9.900   3.165   0   0  18   0  17  17
 1601-1700 :  9.900   3.174   0   0  17   0  16  16
 1701-1800 :  9.900   3.163   0   0  16   0  15  15
 1801-1900 : 10.000   3.204   0   0  17   0  16  16
 1901-2000 : 10.000   3.207   0   0  16   0  15  15
 2001-2100 : 10.000   3.195   0   0  16   0  15  15
Simulation Interrupted in Cycle 2151
PrintMode = 3
4to1Decoder: 111100->1 Success
-------------- Cycle 2151 --------------

Message-List:
MId Intens Sender Message
  0:  1.00   D    111100

Classifier-List:
CFId   Str    Get    Pay  Taxes Condion/Action
  0:  6.01   0.00   0.00   0.00 +0#1#00/110010
  1:  5.45   0.00   0.00   0.00 +011#01/000001
  2:  6.01   0.00   0.00   0.00 +0#1#10/011001
  3:  2.59   0.00   0.00   0.00 +110#11/111010
  4:  1.80   0.00   0.00   0.00 +11####/101011
  5:  2.49   0.00   0.00   0.00 +##11##/101111
  6:  2.10   0.00   0.00   0.00 +01#10#/101010
  7:  1.80   0.00   0.00   0.00 +##10##/110100
  8:  2.10   0.00   0.00   0.00 +1####0/000010
  9:  1.80   0.00   0.00   0.00 +000###/011111
 10:  2.39   0.00   0.00   0.00 +0#10#0/011101
 11:  1.90   0.00   0.00   0.00 +###0##/011111
 12:  1.80   0.00   0.00   0.00 +1##000/101011
 13:  6.67   0.00   0.00   0.00 +#1#10#/110111
 14:  2.20   0.00   0.00   0.00 +#0#1##/011011
 15:  1.90   0.00   0.00   0.00 +#01#00/110111
 16:  1.80   0.00   0.00   0.00 +##00#0/011101
 17:  2.49   0.00   0.00   0.00 +#0###1/111101
 18:  1.80   0.00   0.00   0.00 +#####0/011111
 19:  6.01   0.00   0.00   0.00 +1##000/101001
 20:  2.00   0.00   0.00   0.00 +0#10##/110100
 21:  2.39   0.00   0.00   0.00 +#101#1/101000
 22:  2.59   0.00   0.00   0.00 +###011/000010
 23:  5.46   0.00   0.00   0.00 +10#100/110011
 24:  1.71   0.00   0.00   0.00 +##10##/101101
 25:  1.51   0.00   0.00   0.00 +11##1#/111010
 26:  6.67   0.00   0.00   0.00 +###111/011101
 27:  2.10   0.00   0.00   0.00 +0##001/111101
 28:  2.00   0.00   0.00   0.00 +#00#1#/100111
 29:  2.49   0.00   0.00   0.00 +01#0#1/101110
 30:  2.29   0.00   0.00   0.00 +0###1#/101001
 31:  6.01   0.00   0.00   0.00 +#0#001/100000
 32:  3.13   0.00   0.00   0.00 +010#10/011100
 33:  6.01   0.00   0.00   0.00 +1#0#10/010010
 34:  2.00   0.00   0.00   0.00 +####1#/101000
 35:  1.90   0.00   0.00   0.00 +#1#01#/101110
 36:  2.29   0.00   0.00   0.00 +#11##0/000110
 37:  2.10   0.00   0.00   0.00 +0##100/011111
 38:  2.49   0.00   0.00   0.00 +###1##/011101
 39:  1.80   0.00   0.00   0.00 +0#1100/010001
 40:  2.10   0.00   0.00   0.00 +010#1#/101101
 41:  2.00   0.00   0.00   0.00 +00#0##/101000
 42:  1.71   0.00   0.00   0.00 +###1#1/011001
 43:  1.90   0.00   0.00   0.00 +1#0##1/010111
 44:  2.49   0.00   0.00   0.00 +#11###/111011
 45:  2.20   0.00   0.00   0.00 +#00010/110001
 46:  1.80   0.00   0.00   0.00 +0##1#0/010110
 47:  1.90   0.00   0.00   0.00 +#1#1#1/001101
 48:  1.90   0.00   0.00   0.00 +##1###/101001
 49:  2.49   0.00   0.00   0.00 +0##0#0/111000
 50:  6.01   0.00   0.00   0.00 +10##01/100010
 51:  2.20   0.00   0.00   0.00 +1###1#/010011
 52:  2.10   0.00   0.00   0.00 +110##1/001110
 53:  1.90   0.00   0.00   0.00 +##1000/110000
 54:  2.10   0.00   0.00   0.00 +0#0#1#/110100
 55:  5.45   0.00   0.00   0.00 +01#000/101100
 56:  2.10   0.00   0.00   0.00 +###1#1/000111
 57:  6.01   0.00   0.00   0.00 +00#00#/111110
 58:  2.20   0.00   0.00   0.00 +#0####/010010
 59:  1.71   0.00   0.00   0.00 +0##10#/100111
 60:  7.51   0.00   0.00   0.00 +####10/010111
 61:  2.10   0.00   0.00   0.00 +1#01##/000010
 62:  2.49   0.00   0.00   0.00 +##1000/111110
 63:  6.67   0.00   0.00   0.00 +##001#/101010
 64:  2.49   0.00   0.00   0.00 +#10#0#/110101
 65:  6.01   0.00   0.00   0.00 +11##01/001001
 66:  2.00   0.00   0.00   0.00 +###100/010000
 67:  2.59   0.00   0.00   0.00 +##1###/111011
 68:  3.07   0.00   0.00   0.00 +10001#/011000
 69:  6.67   0.00   0.00   0.00 +##10#1/010110
 70:  2.00   0.00   0.00   0.00 +0###0#/111011
 71:  2.39   0.00   0.00   0.00 +#1#1#0/100001
 72:  2.59   0.00   0.00   0.00 +1##111/111100
 73:  2.49   0.00   0.00   0.00 +0#1##1/100100
 74:  2.49   0.00   0.00   0.00 +1#110#/001110
 75:  2.00   0.00   0.00   0.00 +10#1#0/110000
 76:  2.59   0.00   0.00   0.00 +0####1/010001
 77:  2.49   0.00   0.00   0.00 +011#01/001101
 78:  2.29   0.00   0.00   0.00 +1####0/000110
 79:  2.49   0.00   0.00   0.00 +###0##/010010
 80:  2.49   0.00   0.00   0.00 +010100/000101
 81:  6.01   0.00   0.00   0.00 +#101#1/000101
 82:  8.59   0.00   0.00   0.00 +0#####/111010
 83:  2.59   0.00   0.00   0.00 +##1#1#/100101
 84:  2.10   0.00   0.00   0.00 +#111#1/011011
 85:  5.45   0.00   0.00   0.00 +1111#1/011001
 86:  2.39   0.00   0.00   0.00 +##0##0/110001
 87:  7.51   0.00   0.00   0.00 +##00##/001011
 88:  2.39   0.00   0.00   0.00 +###0##/101110
 89:  2.10   0.00   0.00   0.00 +001100/011111
 90:  5.50   0.00   0.00   0.00 +00#101/100100
 91:  6.67  10.00   3.33   6.67 +#11##0/110111
 92:  1.90   0.00   0.00   0.00 +##1111/110011
 93:  2.00   0.00   0.00   0.00 +10###0/100111
 94:  2.29   0.00   0.00   0.00 +####01/010110
 95:  6.67   0.00   0.00   0.00 +##1#01/110100
 96:  6.01   0.00   0.00   0.00 +##0110/010110
 97:  6.01   0.00   0.00   0.00 +0##100/001100
 98:  1.80   0.00   0.00   0.00 +######/000001
 99:  2.49   0.00   0.00   0.00 +1##011/001110

Bid-List:
BidId CFId Bid EBid Fired BidTupel
  0:   4   0.60   0.60 - { 0 }
  1:   5   0.82   0.82 - { 0 }
  2:   8   0.70   0.70 - { 0 }
  3:  13   3.33   3.33 - { 0 }
  4:  18   0.29   0.29 - { 0 }
  5:  36   1.14   1.14 - { 0 }
  6:  38   0.41   0.41 - { 0 }
  7:  44   0.82   0.82 - { 0 }
  8:  48   0.31   0.31 - { 0 }
  9:  66   1.00   1.00 - { 0 }
 10:  67   0.42   0.42 - { 0 }
 11:  71   1.20   1.20 - { 0 }
 12:  74   1.65   1.65 - { 0 }
 13:  78   0.76   0.76 - { 0 }
 14:  91   3.33   3.33 F { 0 }
 15:  98   0.00   0.00 - { 0 }

New-Message-List:
MId Intens Sender Message
  0:  3.33  91    110111

Effector-List:
CFId   Str    Get    Pay  Taxes Condion/Action
  0:  1.00   0.00   0.00   0.00 +######/00000#

Eff-Bid-List:
BidId CFId Bid EBid Fired BidTupel
  0:   0   0.00   0.00 F { 0 }

Output-Message-List:
MId Intens Sender Message
  0:  0.00   0    000001

Cycle-Cycle  Reinf Strength Min Max Mch Mch Bid Tup
             Value          Str Str  CF Mess 's els
 2151-2151 : 10.000   3.207   0   0  17   0  16  16
\end{verbatim}
\end{listing}

\end{appendix}
\fi
\clearpage
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%         Bibliography        %
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\addcontentsline{toc}{section}{Literatur}
\begin{thebibliography}{9}
\bibitem{Holland}
  {\bf Holland J.H.}:
  {\it Escaping Brittleness: The possibilities of general-purpose
       learning algorithms applied to parallel rule-based systems};
  {\rm Machine Learning Vol 2 Kaufmann Publ., 1986}
\bibitem{Booker}
  {\bf Booker L.B., Goldberg D.E., Holland J.H.}:
  {\it Classifier systems and genetic algorithms};
  {\rm Artificial Intelligence 40,235-282, 1989}
\bibitem{Proc}
  {\it Proceedings of the third international conference on genetic
       algorithms};
  {\rm Kaufmann Publ., 1989}
\bibitem{Goldberg}
  {\bf Goldberg D.E.}:
  {\it Genetic algorithms in search, optimization machine learning};
  {\rm Addison-Wesley, 1989}
\bibitem{Wilson}
  {\bf Wilson S.W.}:
  {\it Classifier systems and the animat problem};
  {\rm Kluwer Academic Publishers, Bosten, 1987}
\bibitem{Weiss}
  {\bf Weiss G.}:
  {\it Benutzerbeschreibung zum Klassifizierungssystem}
  {\rm TU-M�nchen, 1991}
% ...
\end{thebibliography}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%            Index            %
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

%\addcontentsline{toc}{section}{Index}
\end{document}
